A simple functional language
GeomLab is based on a simple functional language called Fun, and a still simpler language with the same name (but without the pattern-matching) is implemented by interpreter in the Principles of Programming Languages course. (GeomLab has a self-hosting compiler that targets the JVM).
The goal of this project is to produce another prototype implementation of Fun, or a language like it, via a compiler that targets some other platform. One possibility is to modify Keiko by allowing heap-allocated activation records; another is to compile to the existing Keiko machine but use closure conversion.
Ideas for an implementation on Keiko
- Use this development snapshot of OBC and the Keiko machine:
$ hg clone http://bitbucket.org/Spivey/obc-3 -u proj2018 $ autoconf $ ./configure --disable-debugger --disable-jit --enable-debug $ make
- Begin with this Oberon program
MapInc.m, which simulates a simple but higher-order functional program using closure-conversion. It uses extensible records to express the
Valuetype as the union of (boxed) integers, cons cells and closures, and a dynamically allocated flexible array to hold the free variables for each non-trivial closure.
- Compile the program using
-bflag so as to remove distracting runtime checks.
- Study the Keiko object code and try to understand and simplify it.
- For example, closures with 1 and 2 arguments are represented by different record types in the Oberon program, but these can be merged together by editing the Keiko code.
- Also, the Oberon program uses helper functions
apply2for applying closures, but these operations can be inlined using the
SWAPinstructions to give better code.
- With runtime checks turned off, the only part of a record descriptor that is used is the first word – the garbage collector map. You can delete the rest of the descriptor and the associated ancestor table.
- Try adding another function to the program at the Oberon level, or by coding it directly at the Keiko level.
- For explanation of
NEWFLEXsee the comments in
To investigate later
- Whether a curried-style language is possible.
- I contemplated this for GeomLab, by making the apply_n methods deal smartly with too few (make a closure) or too many (call and then apply the result) arguments – but the upshot was that the error message "f called with too many args" would be unhelpfully replaced by "calling a non-function" in most contexts.
- Pattern-matching, perhaps with an efficient implementation.
- Tail recursion, by adding an instruction to Keiko. Note that the caller pops the arguments (as the second half of the
CALL ninstruction), so a tail call can only be short-circuited if it has the same number of args as the parent function.