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)?

[dolomiti7]

The function inlining was just a consideration and referring to the principal tendency of functional languages generating more calls (before optimization). And since a function call is even more expensive on the Hack platform than it is in general, a plain vanilla VM translator (or backend) would probably generate relatively inefficient machine code out of the VM code. So I'm just curious how much of this functional overhead would easily be optimised away (i.e. inlining). When I have the time, I may benchmark some jack vs Jill code on the generated ASM code level.

[pm100]

I factored out the common code for function call and return and included it just once.

Function call just needed 3 things to be setup

        // common call routine
        // entered with
        // D= return label
        // R13 = arg count
        // R14 = sub to call

return from call doesnt need any args

this enabled me to fit large programs into the hack memory

[dolomiti7]

I did the same. That's efficient in terms of code size, but in terms of speed it is very costly - even when not using a global function handler.