2005-04-11

purelisp: introduction

Some time ago (I just re-checked and... Good Lord it was in October of 2003, time moves fast indeed) I wrote simple LISP interpreter (purelisp) in Java. This, otherwise seemingly pointless activity could be justified as an exercise in SableCC usage.

SableCC

SableCC is a nice compiler building toolkit with pretty standard (by nowaday standards) set of features: on input it takes a description of the language, and produces Java classes with lexer and skeleton parser. Language is defined by a grammar and terminals are defined by regular expressions. Our simple version of LISP uses lisp.grammar as the definition, note that larger fraction of language definition is a table indicating what unicode characters are "letters" in the sense of being acceptable as part of an identifier.

From language definition SableCC generates:

  • Java classes corresponding to tokens of the grammar.
  • Lexer class that transforms input stream into sequence of tokens (optionally omitting some tokens, e.g., white-spaces).
  • Parser class that constructs typed AST (abstract syntax tree) from the sequence of tokens.
  • Set of tree-walker base classes. Tree-walkers traverse tree in specific order, calling certain methods of tree node object when entering and leaving it. This is called "visitor pattern" by the people in dire need of names.
The only thing left to do to finish simple interpreter is to subclass suitable tree-walker with the class that interprets program while traversing its AST. LISP program (as LISP fans will never cease to remind us) is but a LISP data, hence, natural choice for our interpreter is to build LISP object as a result of tree traversal. And building such an object is indeed simple: local.purelisp.eval.TreeBuilder.

purelisp introduction

Computational universe of purelisp consists of objects, partitioned into disjoint types. Objects can be evaluated. Evaluation takes as input an object to be evaluated and auxiliary object of type environment that affects evaluation. Result of evaluation is an object again. This can be the same object that is being evaluated, some already existing object, or new object. Ultimately, evaluation can result in error, and no result is produced in this case. Rules of evaluation for some objects are hard-wired into interpreter. For other objects, evaluation is multi-step process defined in terms of some actions performed on other objects.

In particular, one important type of objects, viz. cons cells have evaluation defined in terms of application of an object to a sequence of objects (referred to as arguments of application). Rules of application are again type-dependent: hard-wired into interpreter (e.g. for built-in functions), or defined through combination of evaluation and application.

Evaluation and application are fundamental mutually-recursive operations on top of which computation is implemented in LISP.

LISP program is actually nothing more than description of object according to some standard syntax. LISP interpreter reads this description, build corresponding objects and evaluates it in some "current" environment.

[in next installation: object types in purelisp.]
--Tags:-[]-[]-----------

No comments:

Post a Comment