Stefan pushed to branch report/els-2017 at Stefan / Typer

Commits: 6a1f5c7c by Stefan Monnier at 2017-01-29T23:17:35-05:00 -

- - - - -

1 changed file:

- paper.tex

Changes:

===================================== paper.tex ===================================== --- a/paper.tex +++ b/paper.tex @@ -15,7 +15,7 @@

\citestyle{acmauthoryear}

-\acmConference[ELS'2017]{European Lisp Conference}{April 2017} +\acmConference[ELS'2017]{European Lisp Symposium}{April 2017} {Vrije Universiteit Brussel, Belgium} \acmYear{2017} %% \copyrightyear{2017} @@ -250,23 +250,29 @@ The power of Lisp's macros relies on the following:

\subsection{S-expressions}

+\newcommand \FigLispSexp { + \begin{figure} + \begin{displaymath} + \MAlign{ + \kw{type}~\id{Sexp} \ + ~~|~\id{cons}~(\id{car} : \id{Sexp})~(\id{cdr} : \id{Sexp}) \ + ~~|~\id{symbol}~(\id{name} : \id{String}) \ + ~~|~\id{number}~\id{Int} \ + ~~|~\id{string}~\id{String} \ + } + \end{displaymath} + \caption{Definition of Lisp's S-expressions} + \label{fig:Lisp-Sexp} + \end{figure} +} Once lexical analysis is performed, rather than performing the syntactic analysis in one step, Lisp languages further subdivide the syntactic analysis phase into two steps. The first step does a rudimentary analysis that only extracts a generic tree structure, called S-expression. The shape -of S-expressions could be described with the following algebraic datatype: -%% -\begin{displaymath} - \MAlign{ - \kw{type}~\id{Sexp} \ - ~~|~\id{cons}~\id{Sexp}~\id{Sexp} \ - ~~|~\id{symbol}~\id{String} \ - ~~|~\id{number}~\id{Int} \ - ~~|~\id{string}~\id{String} \ - ~~~\ldots - } -\end{displaymath} -%% +of S-expressions could be described with the datatype shown in Fig.~\ref{fig:Lisp-Sexp}. + +\FigLispSexp + Note how, at this stage, there is no notion of bindings, functions, or function calls. It's only in a second step that S-expressions are analyzed to distinguish the various constructs such as macro calls, function calls, @@ -470,15 +476,38 @@ one used in Template Haskell and \id{return} is the unit of that monad. \section{Parsing into S-expressions} \label{sec:parsing}

+\newcommand \FigTyperSexp { + \begin{figure} + \begin{displaymath} + \MAlign{ + \kw{type}~\id{Sexp} \ + ~~|~\id{node}~(\id{head} : \id{Sexp})~(\id{args} : \id{List}~\id{Sexp}) \ + ~~|~\id{symbol}~(\id{name} : \id{String}) \ + ~~|~\id{number}~\id{Int} \ + ~~|~\id{string}~\id{String} \ + } + \end{displaymath} + \caption{Definition of Typer's S-expressions} + \label{fig:Typer-Sexp} + \end{figure} +} +\FigTyperSexp + Like Lisp, Typer's parsing is done in 3 steps: the first turns the input into a stream of tokens; the second turns this stream into an S-expression tree; and the third finally recognizes the actual language's constructs. -We will first look at the middle step, and we will return to tokenizing later. +Fig.~\ref{fig:Typer-Sexp} shows how Typer's S-expressions are represented +internally. This is very similar to Lisp's representation except that +the \id{cons} constructor is replaced by a \id{node} constructor which +basically enforces that sub-lists are \emph{proper} lists. + +We will first look at the actual syntax analysis step, and we will return to +tokenizing later.

\subsection{Operator precedence grammar}

-Typer's notion of S-expression is more flexible than Lisp's, since it allows -infix notation. It relies on operator precedence grammars +Typer's external notion of S-expression is more flexible than Lisp's, since +it allows infix notation. It relies on operator precedence grammars (OPG)~\cite{Floyd63} for that. An OPG is a very restrictive subset of context free grammars, much more restrictive than LALR, for example.

@@ -665,21 +694,45 @@ it was natural and important to be able to distinguish those two cases. \section{Elaboration to core Typer} \label{sec:elaboration}

-\begin{figure} - \begin{displaymath} - \MAlign{ - \kw{type}~\id{Lexp} \ - ~~|~\id{var}~\id{Id} \ - ~~|~\id{app}~\id{Lexp}~(\id{List}~\id{Lexp}) \ - ~~|~\id{fun}~(\id{List}~\id{Id})~\id{Lexp} \ - ~~|~\id{let}~\id{Id}~\id{Lexp}~\id{Lexp} \ - ~~|~\id{case}~\id{Lexp}~(\id{List}~\id{Lbranch}) \ - ~~~\ldots - } - \end{displaymath} - \label{fig:Lexp} - \caption{Definition of $\lambda$-expressions} -\end{figure} +\newcommand \FigLexp { + \begin{figure} + \begin{displaymath} + \MAlign{ + \kw{type}~\id{Lexp} \ + \hspace{5pt}\begin{array}{@{|~}l@{~}l} + \id{var} & \id{Id} \ + \id{app} & (f : \id{Lexp})~(\id{arg} : \id{Lexp}) \ + \id{fun} & (\id{arg} : \id{Id})~(\id{atype} : \id{Lexp}) + ~(\id{body} : \id{Lexp}) \ + \id{arw} & (\id{arg} : \id{Id})~(\id{atype} : \id{Lexp}) + ~(\id{rtype} : \id{Lexp}) \ + \id{let} & (\id{var} : \id{Id})~(\id{val} : \id{Lexp}) + ~(\id{body} : \id{Lexp}) \ + \id{case}& (\id{val} : \id{Lexp}) + ~(\id{cases} : \id{List}~\id{Lbranch}) \ + \id{con} & (\id{adt} : \id{Lexp})~(\id{name} : \id{Id}) \ + \id{adt} & (\id{params} : \id{List}~\id{Id}) + ~(\id{cases} : \id{List}~\id{LadtCase}) \ + \id{prim}& (\id{id} : \id{String}) \ + \end{array} \medskip \ + \kw{type}~\id{LadtCase} \ + \hspace{5pt}\begin{array}{@{|~}l@{~}l} + \id{adtcase} & (\id{name} : \id{Id})~(\id{fields} : + \id{List}~\id{Lexp}) + \end{array} \medskip \ + \kw{type}~\id{Lbranch} \ + \hspace{5pt}\begin{array}{@{|~}l@{~}l} + \id{case} & (\id{pattern} : \id{List}~\id{Id}) + ~(\id{body} : \id{Lexp}) + \end{array} + } + \end{displaymath} + \label{fig:Lexp} + \caption{Definition of core $\lambda$-expressions} + \end{figure} +} + +\FigLexp

No hard coded names: just initial bindings of constructs to special forms and primitive functions.

View it on GitLab: https://gitlab.com/monnier/typer/commit/6a1f5c7c19764ee964272ab9d902564f0b3c...