cinnabar.tex

\batchmode

\documentclass[a4paper,11pt]{article}
\author{Piotr Bakalarski}
\title{The Language Cinnabar}
\setlength{\parindent}{0mm}
\setlength{\parskip}{1mm}

\usepackage{minted}

\begin{document}

\maketitle

\newcommand{\emptyP}{\mbox{$\epsilon$}}
\newcommand{\terminal}[1]{\mbox{{\texttt {#1}}}}
\newcommand{\nonterminal}[1]{\mbox{$\langle \mbox{{\sl #1 }} \! \rangle$}}
\newcommand{\arrow}{\mbox{::=}}
\newcommand{\delimit}{\mbox{$|$}}
\newcommand{\reserved}[1]{\mbox{{\texttt {#1}}}}
\newcommand{\literal}[1]{\mbox{{\texttt {#1}}}}
\newcommand{\symb}[1]{\mbox{{\texttt {#1}}}}

\section*{Language features}

Cinnabar is an object-oriented, imperative programming language drawing inspiration from Python and JavaScript. 

\subsection*{Types}

Cinnabar is a dynamically-typed language. Values are always accessed by reference. Built-in types are:
\begin{itemize}
\item \emph{char} -- immutable Unicode character;
\item \emph{bool} -- immutable, either \emph{true} or \emph{false};
\item \emph{int} -- immutable, fixed-precision integer with at least the range
$\left[ -2^{29}, 2^{29}-1 \right]$;
\item \emph{list} -- fixed length, mutable list with mixed type elements, length is accessible via the {\tt length} field;
\item \emph{dictionary} -- mutable, mixed type dictionary, list of keys can be accessed via the {\tt keys} field, list of pairs \emph{[key, value]} can be accessed via the {\tt keys\_values} field;
\item \emph{object} -- mutable object with fields and methods;
\item \emph{function} -- immutable, anonymous function with side effects.
\end{itemize} 

\subsection*{Statements}
Cinnabar has loops, conditional expressions, assignment with list unpacking, run-time assertions. It also supports writing to standard output via the {\tt print} statement.

\subsection*{Expressions}

Cinnabar supports arithmetic, boolean and lambda expressions, python-style \emph{if-then-else}, list and dictionary literals, list comprehension and inheritance expressions.

\subsection*{Strings}

Strings are implemented as lists of characters.

\subsection*{Comparisons}

Comparing values of different types always results in a runtime error.
\begin{itemize}
\item Characters and integers support ordering comparisons.
\item Booleans, lists, dictionaries, objects and functions can only be tested for equality.
\item Lists are equal iff their lengths are equal and elements on equivalent positions are comparable and equal.
\item Dictionaries are equal iff their key sets are comparable and equal and, for each key, assigned values are comparable and equal.
\item Objects and functions are equal only to themselves.
\end{itemize}

\subsection*{Functions}

Functions are first class citizens in cinnabar.\\
There are no named functions -- only anonymous ones. \\
If no {\tt return} statement is executed, the function returns $0$.\\
Calls with missing or excess parameters are considered errors.\\
Arguments are always passed by reference.\\
Functions are implemented as closures -- they persist the variable-to-reference mapping form the time of creation. Changes made to values referenced by either arguments or non-local variables will be persisted.

\subsection*{Objects}

Cinnabar uses prototype inheritance: {\tt new} operator creates a factory function that returns a shallow copy and calls the {\tt init} method on it with given parameters; {\tt extend with} operator creates a shallow copy, then adds or replaces fields and methods with data from a provided dictionary. Only \emph{string} type keys are allowed.\\
Object methods are internally passed the object as the first parameter.

\subsection*{Built-ins}
Cinnabar has one built-in object: {\tt object}, with empty {\tt init} method and {\tt to\_str} method that returns the string \emph{[object]}.

Built-in functions:
\begin{itemize}
\item {\tt str(v)} -- convert value to string representation. For objects, it calls their {\tt to\_str} method,
\item {\tt read()} -- read a single character from standard input.
\end{itemize}


\section*{The lexical structure of cinnabar}
\subsection*{Identifiers}
Identifiers \nonterminal{Ident} are unquoted strings beginning with a letter,
followed by any combination of letters, digits, and the characters {\tt \_ '},
reserved words excluded.


\subsection*{Literals}

Integer literals \nonterminal{Integer} are sequences of decimal digits.\\
String literals \nonterminal{String} are sequences of Unicode characters surrounded with double quotes.\\
Character literals \nonterminal{Char} are single Unicode characters surrounded with single quotes.

\subsection*{Reserved words and symbols}

The reserved words used in cinnabar are the following: \\

\begin{tabular}{lll}
{\reserved{assert}} &{\reserved{else}} &{\reserved{extend}} \\
{\reserved{false}} &{\reserved{for}} &{\reserved{fun}} \\
{\reserved{if}} &{\reserved{in}} &{\reserved{lambda}} \\
{\reserved{new}} &{\reserved{print}} &{\reserved{return}} \\
{\reserved{true}} &{\reserved{while}} &{\reserved{with}} \\
\end{tabular}\\

The symbols used in cinnabar are the following: \\

\begin{tabular}{lll}
{\symb{\{}} &{\symb{\}}} &{\symb{(}} \\
{\symb{)}} &{\symb{{$=$}}} &{\symb{;}} \\
{\symb{,}} &{\symb{[}} &{\symb{]}} \\
{\symb{.}} &{\symb{:}} &{\symb{{$|$}{$|$}}} \\
{\symb{\&\&}} &{\symb{{\textasciicircum}}} &{\symb{!}} \\
{\symb{{$-$}}} &{\symb{\#\{}} &{\symb{{$<$}}} \\
{\symb{{$<$}{$=$}}} &{\symb{{$>$}}} &{\symb{{$>$}{$=$}}} \\
{\symb{{$=$}{$=$}}} &{\symb{!{$=$}}} &{\symb{{$+$}}} \\
{\symb{*}} &{\symb{/}} &{\symb{\%}} \\
\end{tabular}\\

\subsection*{Comments}
Single-line comments begin with {\symb{//}}. \\Multiple-line comments are  enclosed with {\symb{/*}} and {\symb{*/}}.

\section*{The syntactic structure of cinnabar}
Non-terminals are enclosed between $\langle$ and $\rangle$. 
The symbols  {\arrow}  (production),  {\delimit}  (union) 
and {\emptyP} (empty rule) belong to the BNF notation. 
All other symbols are terminals.\\

\begin{tabular}{lll}
{\nonterminal{Program}} & {\arrow}  &{\nonterminal{ListStmt}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Block}} & {\arrow}  &{\terminal{\{}} {\nonterminal{ListStmt}} {\terminal{\}}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{ListStmt}} & {\arrow}  &{\emptyP} \\
 & {\delimit}  &{\nonterminal{Stmt}} {\nonterminal{ListStmt}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Stmt}} & {\arrow}  &{\terminal{while}} {\terminal{(}} {\nonterminal{Expr}} {\terminal{)}} {\nonterminal{Block}}  \\
 & {\delimit}  &{\terminal{if}} {\terminal{(}} {\nonterminal{Expr}} {\terminal{)}} {\nonterminal{Block}}  \\
 & {\delimit}  &{\terminal{if}} {\terminal{(}} {\nonterminal{Expr}} {\terminal{)}} {\nonterminal{Block}} {\terminal{else}} {\nonterminal{Block}}  \\
 & {\delimit}  &{\nonterminal{LVal}} {\terminal{{$=$}}} {\nonterminal{Expr}} {\terminal{;}}  \\
 & {\delimit}  &{\terminal{return}} {\nonterminal{Expr}} {\terminal{;}}  \\
 & {\delimit}  &{\terminal{print}} {\nonterminal{Expr}} {\terminal{;}}  \\
 & {\delimit}  &{\terminal{assert}} {\nonterminal{Expr}} {\terminal{;}}  \\
 & {\delimit}  &{\nonterminal{Expr}} {\terminal{;}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{LVal}} & {\arrow}  &{\nonterminal{LVal1}}  \\
 & {\delimit}  &{\terminal{\{}} {\nonterminal{ListLVal1}} {\terminal{\}}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{ListLVal1}} & {\arrow}  &{\nonterminal{LVal1}}  \\
 & {\delimit}  &{\nonterminal{LVal1}} {\terminal{,}} {\nonterminal{ListLVal1}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{LVal1}} & {\arrow}  &{\nonterminal{Expr8}} {\terminal{[}} {\nonterminal{Expr}} {\terminal{]}}  \\
 & {\delimit}  &{\nonterminal{Expr8}} {\terminal{.}} {\nonterminal{Ident}}  \\
 & {\delimit}  &{\nonterminal{Ident}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr}} & {\arrow}  &{\terminal{lambda}} {\nonterminal{ListIdent}} {\terminal{:}} {\nonterminal{Expr}}  \\
 & {\delimit}  &{\terminal{fun}} {\terminal{(}} {\nonterminal{ListIdent}} {\terminal{)}} {\nonterminal{Block}}  \\
 & {\delimit}  &{\nonterminal{Expr1}} {\terminal{if}} {\nonterminal{Expr}} {\terminal{else}} {\nonterminal{Expr}}  \\
 & {\delimit}  &{\nonterminal{Expr1}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{ListIdent}} & {\arrow}  &{\emptyP} \\
 & {\delimit}  &{\nonterminal{Ident}}  \\
 & {\delimit}  &{\nonterminal{Ident}} {\terminal{,}} {\nonterminal{ListIdent}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr1}} & {\arrow}  &{\nonterminal{Expr2}} {\terminal{{$|$}{$|$}}} {\nonterminal{Expr1}}  \\
 & {\delimit}  &{\nonterminal{Expr2}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr2}} & {\arrow}  &{\nonterminal{Expr3}} {\terminal{\&\&}} {\nonterminal{Expr2}}  \\
 & {\delimit}  &{\nonterminal{Expr3}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr3}} & {\arrow}  &{\nonterminal{Expr4}} {\nonterminal{RelOp}} {\nonterminal{Expr4}}  \\
 & {\delimit}  &{\nonterminal{Expr4}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr4}} & {\arrow}  &{\nonterminal{Expr4}} {\nonterminal{AddOp}} {\nonterminal{Expr5}}  \\
 & {\delimit}  &{\nonterminal{Expr5}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr5}} & {\arrow}  &{\nonterminal{Expr5}} {\nonterminal{MulOp}} {\nonterminal{Expr6}}  \\
 & {\delimit}  &{\nonterminal{Expr6}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr6}} & {\arrow}  &{\nonterminal{Expr6}} {\terminal{{\textasciicircum}}} {\nonterminal{Expr7}}  \\
 & {\delimit}  &{\nonterminal{Expr7}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr7}} & {\arrow}  &{\terminal{!}} {\nonterminal{Expr7}}  \\
 & {\delimit}  &{\terminal{{$-$}}} {\nonterminal{Expr7}}  \\
 & {\delimit}  &{\nonterminal{Expr8}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr8}} & {\arrow}  &{\nonterminal{Expr8}} {\terminal{(}} {\nonterminal{ListExpr}} {\terminal{)}}  \\
 & {\delimit}  &{\nonterminal{Expr8}} {\terminal{.}} {\nonterminal{Ident}}  \\
 & {\delimit}  &{\nonterminal{Expr8}} {\terminal{[}} {\nonterminal{Expr}} {\terminal{]}}  \\
 & {\delimit}  &{\nonterminal{Expr9}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr9}} & {\arrow}  &{\terminal{extend}} {\nonterminal{Expr}} {\terminal{with}} {\nonterminal{Expr9}}  \\
 & {\delimit}  &{\terminal{new}} {\nonterminal{Expr9}} {\terminal{(}} {\nonterminal{ListExpr}} {\terminal{)}}  \\
 & {\delimit}  &{\nonterminal{Expr10}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{Expr10}} & {\arrow}  &{\nonterminal{Char}}  \\
 & {\delimit}  &{\nonterminal{String}}  \\
 & {\delimit}  &{\nonterminal{Integer}}  \\
 & {\delimit}  &{\terminal{true}}  \\
 & {\delimit}  &{\terminal{false}}  \\
 & {\delimit}  &{\nonterminal{Ident}}  \\
 & {\delimit}  &{\terminal{[}} {\nonterminal{ListExpr}} {\terminal{]}}  \\
 & {\delimit}  &{\terminal{[}} {\nonterminal{Expr}} {\terminal{for}} {\nonterminal{LVal}} {\terminal{in}} {\nonterminal{Expr}} {\terminal{]}}  \\
 & {\delimit}  &{\terminal{\#\{}} {\nonterminal{ListDictMap}} {\terminal{\}}}  \\
 & {\delimit}  &{\terminal{(}} {\nonterminal{Expr}} {\terminal{)}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{ListExpr}} & {\arrow}  &{\emptyP} \\
 & {\delimit}  &{\nonterminal{Expr}}  \\
 & {\delimit}  &{\nonterminal{Expr}} {\terminal{,}} {\nonterminal{ListExpr}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{DictMap}} & {\arrow}  &{\nonterminal{Expr}} {\terminal{:}} {\nonterminal{Expr}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{ListDictMap}} & {\arrow}  &{\emptyP} \\
 & {\delimit}  &{\nonterminal{DictMap}}  \\
 & {\delimit}  &{\nonterminal{DictMap}} {\terminal{,}} {\nonterminal{ListDictMap}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{RelOp}} & {\arrow}  &{\terminal{{$<$}}}  \\
 & {\delimit}  &{\terminal{{$<$}{$=$}}}  \\
 & {\delimit}  &{\terminal{{$>$}}}  \\
 & {\delimit}  &{\terminal{{$>$}{$=$}}}  \\
 & {\delimit}  &{\terminal{{$=$}{$=$}}}  \\
 & {\delimit}  &{\terminal{!{$=$}}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{AddOp}} & {\arrow}  &{\terminal{{$+$}}}  \\
 & {\delimit}  &{\terminal{{$-$}}}  \\
\end{tabular}\\

\begin{tabular}{lll}
{\nonterminal{MulOp}} & {\arrow}  &{\terminal{*}}  \\
 & {\delimit}  &{\terminal{/}}  \\
 & {\delimit}  &{\terminal{\%}}  \\
\end{tabular}\\

\section*{Example programs}
\begin{listing}[H]
\inputminted{python}{good/simple.cb}
\caption{A simple example of the syntax}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/lists.cb}
\caption{List example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/dict.cb}
\caption{Dictionary example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/expr.cb}
\caption{Expressions example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/funstack.cb}
\caption{Lambda example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/closures.cb}
\caption{Closures example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/recurse.cb}
\caption{Recursion example}
\label{lst:simple}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/inherit.cb}
\caption{Inheritance example}
\end{listing}

\begin{listing}[H]
\inputminted{python}{good/qsort.cb}
\caption{Example quicksort implementation in cinnabar}
\end{listing}

\end{document}