Jill - a functional programming language for Nand2Tetris

[mpatajac]

Jill is a functional programming language built for the Nand2Tetris platform, as an alternative to the Jack high-level language.

It is designed as a drop-in replacement for Jack, as it uses the same VM instruction set and underlying HACK architecture, and follows similar design principles (willing to sacrifice ease of use to favour ease of implementation), while offering a functional alternative to Jack's very object-oriented, verbose style (I like to think of Jill as Jack's more elegant, modern sister).

Some notable features include:
- functions as first-class citizens (ability to store them in variables, pass them on to other functions as arguments, and return from functions as a result)
- optimized tail-call recursion to use constant stack space (single stack frame)
- data modeling using algebraic data types with primitive pattern-matching (per type variant)
  - note that, as with Jack, all variables are still effectively 16-bit integers, therefore Jill is dynamically typed
- minimal language design
  - only 3 main concepts (types, variables and functions)
  - expressions can only be literals, variables or function calls
- expanded standard library which is lazily-generated (instructions are generated only for modules and functions which were used in codebase)
- common design choices of functional languages (no loops, variables are immutable, code is organized into modules etc.)

You can find code examples, compiler source code and more in the project repository.

[dolomiti7]

Great project! Finally functional programming on nand2tetris. I saw that some of the stdlib functions don't have a Jill or Jack source code equivalent. Did you implement those directly as VM instructions (i.e. List.repeat)? Or did I overlook something?

The generated VM code looks quite good, since you already mapped basic functions to VM commands (i.e. Bool.gt). Still there are more calls as a result of the functional approach. I haven't tried it in combination with my VM translator, but I believe lots of them would be eliminated at that stage by inlining and and thus resulting in efficient ASM code.

[mpatajac]

Hi, glad you like it! I tried to find any existing functional implementations (or at least attempts), but I didn't find any, so I decided to give it a try myself.

Yes, not all stdlib functions have their Jill equivalents - since their implementation doesn't change on a per-project basis, it is enough to have their pre-compiled ("cached", if you will) VM instructions, which we then output for the requested (used) functions.
I implemented those functions by writing them in Jill, compiling that, and then doing some basic cleanup on the generated VM instructions (removed redundant/unused labels, pop->push combinations of the exact same segment space etc.). However, for some reason, at the time I did not think to save those Jill implementations as well (as a "reference implementation" of sorts); it was only recently that I added those for map, filter and dispose functions, and I will hopefully do the same for the rest of the functions (at least for the List/Random modules, I believe that the other modules/functions are trivial enough to be understood from the VM instructions alone).

Regarding "function inlining", are you referring to the way functions-as-variables are called (i.e. the Fn.call and the dynamic dispatch), or the general inlining of the functions themselves (i.e. putting the instructions of the function body in place of the call {function_name} instruction)?