The Adder compiler
Adder doesn't expose a compilation step, but there is a compiler
under the hood, translating Adder to Python. (There was an earlier
prototype which targeted Python bytecode; but Python bytecode
changes too quickly. The compiler needed substantial rework to
target Python 3.1 instead of 3.0.)
The intermediate languages
The Adder compiler uses two intermediate languages: Gomer
and Pyle. Adder is reduced to Gomer, which is reduced to Pyle,
which is then transliterated to
Python. Broadly, Gomer is Adder with lexical scopes erased, while
Pyle is a Lispy encoding of a subset of Python.
Gomer
Gomer is actually a subset of Adder, a core language with no
macros. Gomer expressions get built into ASTs, which are annotated
with knowledge of lexical scopes (and probably other stuff,
eventually). With the new version of Pyle, the process of
transforming Gomer to Pyle is purely context-free. The intelligence
formerly embodied in the Gomer-to-Pyle translation is going to have
to move to the Adder-to-Gomer translation. As a result, Gomer no
longer includes constructs such as (scope) and (defvar).
Reducing Gomer to Pyle
Gomer is reduced to Pyle via a series of reduction rules. There's a
default rule for Gomer functions; all other Gomer forms need their
own rules. Rules are implemented as subclasses of
adder.gomer.Reducer. The current state of rules:
Gomer special forms
- begin
- import
- defun
- class
- if
- lambda
- quote
- try
- while
- break
- continue
- yield
- return
- and
- or
- :=
- .
Gomer functions
- raise
- exec-py
- Default rule
- print
- Takes a separate rule, because I want it to return the last arg.
- ==
- Default rule
- !=
- Default rule
- <=
- Default rule
- <
- Default rule
- >=
- Default rule
- >
- Default rule
- +
- -
- *
- /
- //
- %
- in
- gensym
- Default rule
- []
- getattr
- Default rule
- slice
- to-list
- to-tuple
- to-set
- to-dict
- isinstance
- mk-list
- mk-tuple
- mk-set
- mk-dict
- mk-symbol
- reverse
- apply
Misc. TODO
- Compile ((. foo bar)) to foo.bar(), not scratch=foo.bar;
scratch().
Pyle
Pyle (Python Lisplike Encoding) encodes a subset of Python into
Lispy data structures. As an IL, it's loosely based on
register-based instruction sets. The
main characteristic is that there are no function arguments which
include function calls, to avoid the problems that arose when I was
less careful about statements which appeared inside expressions.
For example, the translation of
(if a (:= b ([] a 0)) None), as an expression, used to
put the assignment statement before the if, which is obviously not
the goal.
In Pyle, the
only legal arguments to a function are constants and variable
names. Most statement arguments, such as the body of
a (while), are limited to single statements; to use
multiple statements, wrap them in a (begin)—which
is the only exception to this rule; obviously, it has to support
multiple statement arguments.
The syntax is as follows:
- symbol ::= [instance of adder.common.Symbol]
- literal ::= [instance of int, str, float, bool, or None]
- list ::= [instance of list]
- var ::= $symbol
- any ::= $var | $literal | $list
- simple ::= $var | $literal
- fcall ::= LIST(call $var LIST($simple*)
LIST((LIST($var $simple))*)
$var?
)
- lvalue ::= $var | $dot | $subscript
- assign ::= LIST(:= $lvalue ($simple | $fcall | $binop
| $dot | $subscript | $slice | $quote
| $mk-list | $mk-tuple | $mk-set | $mk-dict
))
- return ::= LIST(return $simple?)
- yield ::= LIST(yield $simple)
- try ::= LIST(try $stmt LIST(:$var $var $stmt)* LIST(:finally $stmt)?)
- raise ::= LIST(raise $var)
- reraise ::= LIST(reraise)
- binop ::= LIST(binop $var $simple $simple)
- quote ::= LIST(quote $any)
- if ::= LIST(if $simple $stmt $stmt?)
- while ::= LIST(while $simple $stmt)
- def ::= LIST(def $var LIST($var*) $stmt)
- class ::= LIST(class $var LIST($var*) $stmt*)
- break ::= LIST(break)
- continue ::= LIST(continue)
- pass ::= LIST(pass)
- begin ::= LIST(begin $stmt*)
- import ::= LIST(import,$var)
- import-as ::= LIST(import-as $var $var)
- import-from ::= LIST(import-from $var LIST('* | LIST($var)))
- mk-list ::= LIST(mk-list $simple)
- mk-tuple ::= LIST(mk-tuple $simple)
- mk-set ::= LIST(mk-set $simple)
- mk-dict ::= LIST(mk-dict LIST($var $simple)*)
- dot ::= LIST(. $simple $var*)
- subscript ::= LIST([] $simple $simple [$simple])
- slice ::= LIST(slice $simple $simple $simple)
- Second and third args are the range of the slice. If None,
omitted. So (slice x None 5) is x[:5]; (slice x 5 None) is x[5:],
(slice x None None) s x[:], which, yes, is legal Python, and doesn't
necessarily mean the same as x. (x[a:b] is equivalent to
x.__getitem__(slice(a,b,None)), which could return just about
anything.)
- nop ::= LIST(nop $anything*)
- stmt ::= $return | $yield | $try | $raise | $reraise
| $if | $while | $break | $continue | $def | $class
| $assign | $pass | $begin | $import | $import-as | $import-from
| $fcall | $nop