`Formula{ "Addition",
`Formula"{ "Exponent",
`Variable "e",
- `Formula{ "Multiplication", `Variable "i", `Variable "pi" } },
+ `Formula{ "Multiplication",
+ `Variable "i",
+ `Variable "pi" } },
`Number 1 }
\end{verbatim}
-This is the way you'll actually write ADT in Metalua, although
-expressions are not represented with this ``formula'' data type.
+Notice that this is a valid description of some tree structure in metalua, but
+it's not a representation of metalua code: metalua code is represented as tree
+structures indeed, but a structure different from this example's one. In other
+words, this is an ADT, but not an AST.
+
+For the record, the metalua (AST) representation of the code {\tt"1+e\^\ (i*pi)"}
+is:
+\begin{verbatim}
+`Op{ "add", `Number 1,
+ `Op{ "pow", `Id "e",
+ `Op{ "mul", `Id "i", `Id "pi" } } }
+\end{verbatim}
+
+After reading more about AST definition and manipulation tools, you'll hopefully
+be convinced that the latter representation is more powerful.
\subsection{Abstract Syntax Trees (AST)}
\paragraph{String constants}
A string is represented by an AST with tag \verb+String+ and the
string as its sole child. For instance, \verb+"foobar"+ is
-represented by \verb+`String "foobar"+.
+represented by:\\
+\verb+`String "foobar"+.
\paragraph{Variable names}
A variable identifier is represented by an AST with tag \verb+Id+ and the
\begin{itemize}
\item the AST of an expression, for array-part entries without an
explicit associated key;
-\item a pair of expression AST, tagged with \verb+Key+: the first
+\item a pair of expression AST, tagged with \verb+Pair+: the first
expression AST represents a key, and the second represents the value
associated to this key.
\end{itemize}
\verb+`Table{ `Number 1, `Number 2, `String "a" }+;
\item \verb+{x=1, y=2}+ is syntax sugar for \verb+{["x"]=1, ["y"]=2}+,
- and is represented by:\\
- \verb+`Table{ `Key{ `String "x", `Number 1 }, `Key{ `String "y", `Number 2} }+;
+ and is represented by {\tt`Table\{ `Pair\{ `String "x", `Number 1
+ \}, `Pair\{ `String "y", `Number 2\} \}};
\item indexed and non-indexed entries can be mixed:
- \verb+{ 1, [100]="foo", 3}+ is represented as \\
- \verb+`Table{ `Number 1, `Key{ `Number 100, `String "foo"}, `Number 3 }+;
+ \verb+{ 1, [100]="foo", 3}+ is represented as {\tt`Table\{ `Number
+ 1, `Pair\{ `Number 100, `String "foo"\}, `Number 3 \}};
\end{itemize}
\paragraph{Binary Operators}
-Binary operations are represented by
-\verb+`Op{ operator, left, right}+, where \verb+operator+ is a
-childless AST describing the operator, \verb+left+ is the AST of the
-left operand, and \verb+right+ the AST of the right operand.
+Binary operations are represented by {\tt`Op\{ operator, left,
+ right\}}, where \verb+operator+ is a the operator's name as one of
+the strings below, \verb+left+ is the AST of the left operand, and
+\verb+right+ the AST of the right operand.
-The following table associates a Lua operator to its AST:
+The following table associates a Lua operator to its AST name:
\begin{center}
\begin{tabular}{|c|c||c|c||c|c||c|c|}
\verb+<=+ & \verb+"le"+ &
\verb+and+ & \verb+"and"+ &
\verb+or+ & \verb+"or"+ \\
- \cline{1-6} %%%%%%%%%%%%%%%%%%
+ \hline %%%%%%%%%%%%%%%%%%%%%%%
\end{tabular}
\end{center}
Operator names are the sames as the corresponding Lua metatable entry,
-without the prefix \verb+"__"+. There are no operator for operators
-\verb+~=+, \verb+>=+ and \verb+>+. They can be simulated by swapping
+without the prefix {\tt"\_\,\_"}. There are no operator for operators
+\verb+~=+, \verb+>=+ and \verb+>+: they can be simulated by swapping
the arguments of \verb+<=+ and \verb+<+, or adding a \verb+not+ to
operator \verb+==+.
\subparagraph{Examples}
\begin{itemize}
\item \verb|2+2| is represented as
- \verb|`Op{ `Add, `Number 2, `Number 2 }|;
-\item \verb|1+2*3| is represented as
- \verb|`Op{ `Add, `Number 1, `Op{ `Mul, `Number 2, `Number 3 } }|;
-\item \verb|(1+2)*3| is represented as
- \verb|`Op{ `Mul, `Op{ `Add, `Number 1, `Number 2 }, `Number 3 }|
-\item \verb|x>=1 and x<42 | is represented as:
+ \verb|`Op{ 'add', `Number 2, `Number 2 }|;
+\item \verb|1+2*3| is represented as:\\[-2em]
+\begin{verbatim}
+`Op{ 'add', `Number 1,
+ `Op{ 'mul', `Number 2, `Number 3 } }
+\end{verbatim}
+\item \verb|(1+2)*3| is represented as:\\[-2em]
\begin{verbatim}
-`Op{ `And, `Op{ `Le, `Number 1, `Id "x" },
- `Op{ `Lt, `Id "x", `Number 42 } }
+`Op{ 'mul, `Op{ 'add', `Number 1, `Number 2 },
+ `Number 3 } }
+\end{verbatim}
+
+ \verb|`Op{ 'mul', `Op{ 'add', `Number 1, `Number 2 }, `Number 3 }|
+\item \verb|x>=1 and x<42 | is represented as:\\[-2em]
+\begin{verbatim}
+`Op{ 'and', `Op{ 'le', `Number 1, `Id "x" },
+ `Op{ 'lt', `Id "x", `Number 42 } }
\end{verbatim}
\end{itemize}
\subparagraph{Examples}
\begin{itemize}
\item \verb|-x| is represented as \verb|`Op{ `Sub, `Id "x" }|;
-\item \verb|-(1+2)| is represented as
+\item \verb|-(1+2)| is represented as:\\
\verb|`Op{ `Sub, `Op{ `Add, `Number 1, `Number 2 } }|
\item \verb|#x| is represented as
\verb|`Op{ `Len, `Id "x" }|
\subparagraph{Examples}
\begin{itemize}
\item \verb+x[3]+ is represented as \verb+`Index{ `Id "x", `Number 3 }+;
-\item \verb+x[3][5]+ is represented as
- \verb+`Index{ `Index{ `Id "x", `Number 3 }, `Number 5 }+;
-\item \verb+x.y+ is syntax sugar for \verb+x["y"]+, and is represented as
- \verb+`Index{ `Id "x", `String "y" }+;
+\item \verb+x[3][5]+ is represented as:\\
+ \verb+`Index{ `Index{ `Id "x", `Number 3 }, `Number 5 }+
+\item \verb+x.y+ is syntax sugar for \verb+x["y"]+, and is represented as:\\
+ \verb+`Index{ `Id "x", `String "y" }+
\end{itemize}
Notice that index AST can also appear as left-hand side of
\subparagraph{Examples}
\begin{itemize}
\item \verb+o:f()+ is represented as \verb+`Invoke{ `Id "o", String "f" }+;
-\item \verb+o:f(x, 1)+ is represented as
+\item \verb+o:f(x, 1)+ is represented as:\\
\verb+`Invoke{ `Id "o", `String "f", `Id "x", `Number 1 }+;
-\item \verb+o:f(x, ...)+ is represented as
+\item \verb+o:f(x, ...)+ is represented as:\\
\verb+`Invoke{ `Id "o", `String "f", `Id "x", `Dots }+;
\end{itemize}
\begin{verbatim}
`Function{ { `Id "fmt", `Dots }
{ `Call{ `Id "print",
- `Call{ `Index{ `Id "string", `String "format" },
+ `Call{ `Index{ `Id "string",
+ `String "format" },
`Id "fmt",
`Dots } } } }
\end{verbatim}
\item \verb+function f (x) return x end+ is not an expression, but a
- statement: it is actually syntax sugar for the assignment
- \verb+f = function (x) return x end+, and as such, is represented
- as:
+ statement: it is actually syntax sugar for the assignment {\tt f =
+ function (x) return x end}, and as such, is represented as:
\begin{verbatim}
`Let{ { `Id "f" },
- { `Function{ { `Id x } { `Return{ `Id "x" } } } } }
+ { `Function{ {`Id 'x'} {`Return{`Id 'x'} } } } }
\end{verbatim}
(see assignment in the statements subsection for more details);
\begin{verbatim}
{ `Localrec{ { `Id "f" },
{ `Function{ { },
- `Return{ `Number 1, `Number 2, `Number 3 } } } },
+ `Return{ `Number 1,
+ `Number 2,
+ `Number 3 } } } },
`Return{ `Table{ `Paren{ `Call{ `Id "f" } } } } }
\end{verbatim}
\item \verb+a = 1, 2, 3+ is represented as:\\
\verb+`Set{ { `Id "a" }, { `Number 1, `Number 2, `Number 3 } }+;
-\item \verb+function f(x) return x end+ is syntax sugar for
- \verb+f = function (x) return x end+, and as such, is represented as:\\
- \verb+`Set{ { `Id "f" }, { `Function{ { `Id x } { `Return{ `Id "x" } } } } }+
+\item \verb+function f(x) return x end+ is syntax sugar for:\\
+ \verb+f = function (x) return x end+. As such, is represented as:\\[-2em]
+\begin{verbatim}
+`Set{ { `Id "f" },
+ { `Function{ {`Id 'x'} {`Return{ `Id "x" } } } } }
+\end{verbatim}
\item \verb+function o:m(x) return x end+ is syntax sugar for:\\
\verb+o["f"] = function (self, x) return x end+, and as such, is
- represented as:
+ represented as:\\[-2em]
\begin{verbatim}
`Set{ { `Index{ `Id "o", `String "f" } },
{ `Function{ { `Id "self, "`Id x }
\subparagraph{Examples}
\begin{itemize}
-\item \verb+local x=2+ is represented as
+\item \verb+local x=2+ is represented as:\\
\verb+`Local{ { `Id "x" }, { `Number 2 } }+;
-\item \verb+local a, b+ is represented as
+\item \verb+local a, b+ is represented as:\\
\verb+`Local{ { `Id "a",`Id "b" }, { } }+;
\end{itemize}
\subparagraph{Examples}
\begin{itemize}
-\item \verb+if <foo> then <bar>; <baz> end+ is represented as:
+\item \verb+if <foo> then <bar>; <baz> end+ is represented as:\\
\verb+`If{ <foo>, { <bar>, <baz> } }+;
\item \verb+if <foo> then <bar1> else <bar2>; <baz2> end+
- is represented as: \\
+ is represented as:
\verb+`If{ <foo>, { <bar1> }, { <bar2>, <baz2> } }+;
\item
retpresented by the (possibly empty) list of returned values.
\subparagraph{Example}
-{\tt return 1, 2, 3} is represented as {\tt`Return\{ `Number 1, `Number
- 2, `Number 3 \}}.
+{\tt return 1, 2, 3} is represented as:\\
+{\tt`Return\{ `Number 1, `Number 2, `Number 3 \}}.
\subsubsection{Extensions with no syntax}
For instance, {\tt `Stat\{ +\{local x=3\}, +\{x\}\}} evaluates to 3.
-\subsubsection{Formal translation defintion}
+%\subsubsection{Formal translation defintion}
-\caveat{FIXME: here should go a formal, inductive definition of
- AST/syntax translation, to serve as a reference}
+%\caveat{FIXME: here should go a formal, inductive definition of
+% AST/syntax translation, to serve as a reference}
projects / metalua.git / blobdiff