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 Value type 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 obc with the -b flag 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 apply1 and apply2 for applying closures, but these operations can be inlined using the DUP and SWAP instructions 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 NEWFLEX see the comments in lib/Builtin.m.

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 n instruction), so a tail call can only be short-circuited if it has the same number of args as the parent function.