Homegrown closures for uxn

at least, kind of...

For a week or so now, I've been writing niënor, a "lispy environment for uxn". I did not want it to become a full-blown lisp but just another way of writing uxntal. Uxntal is a bit too dense for my liking, and I prefer lisp/scheme s-expression syntax. Niënor is just a compiler and a macroexpander that takes in scheme-like code and spits out uxn roms.

This article describes my homegrown method of creating lexically scoped closures in this environment.

Lambdas

Or, anonymous functions.

When ignoring lexical scope lambdas are really simple to implement if we can already compile named functions.

Here is some simplified code with commentary from the compiler that does exactly that (I've skipped some boring parts). We simply give the anonymous function a name, skip the compilation for now (add to epilogue), and push the name (that will get resolved later by the compiler) in its place.

(tuple-case (list->tuple exp)
  ;; [...]
  ((_λ args body)                ; if it's a lambda
   (let ((used-locals            ; check what symbols the lambda uses,
          (intersect             ; intersect them with the list of known locals (function arguments, local values declared in let expressions)
           (get env 'locals #n)  ; to get a list of used locals
           (code->used-symbols body)))) 
     (if (null? used-locals)     ; if there are no locals, 
         (let ((name (gensym)))  ; generate a random name for that function
           ;; [...]
           (put env 'epilogue    ; <- put this function into the epilogue, so it gets compiled at the end of the program
                (append (get env 'epilogue #n)
                        `((_defun ,name ,args ,body))))
           ;; [...]
           ;; in this place, the gensymmed name gets pushed, and later resolved to the functions' location
           ;; so an expression like
           ;;   (let ((f (λ (x) (+ x 1))))
           ;;     ...)
           ;; would resolve to
           ;;   (let ((f @@gensym__1))
           ;;     ...)
           ;; @@gensym__1 being the generated name of the now de-anonymized function :P
           )))))

Closures

Or, lambdas with extra steps.

Closures are anonymous functions that capture variables from the environment. Consider this classic example:

(define (make-adder a)
  (λ (b) (+ a b)))

Here, the lambda captures the variable a, to later add it to b. If we would try to simply name the lambda and compile it somewhere else, we wouldn't be able to resolve the symbol a, as it wouldn't be visible in global scope.

We could simply disallow closures. Niënor was meant to be quite low-level and closures are, well, quite high-level-ish in my opinion. That is a valid method, but not really a solution. I keep closures close to my heart, so I really wanted to have them in my lispy uxn.

I decided to create objects that tied the required environment to functions. Well, kind of... Because there are no types on runtime, I can't really detect if I'm trying to call a closure, a function, or something else.

This, for example, is perfectly valid way to restart a program:

(#x100)

;; or

(let ((f #x100))
  (f)) ; this would quickly exhaust the local variable stack though
       ; as we're not doing any cleanups, because they would be done after a return from f, which never happens

This means that we have to generate executable code at runtime to later jump to - yikes!

I thought of copying the entire function to somewhere else and replacing the unbound variables with environment-specified values during runtime, but that wouldn't work as absolute jumps would always go back to the original function, not our copied version. We could (probably) find all internal jumps and calculate new positions at runtime, but that's expensive (slow) and hard.

The solution i came up with (while showering) is the following:

At compile time, when we know what values from the environment the function will need, add them as parameters

;; this:
(define (make-adder a)
  (λ (b) (+ a b)))

;; would become this:
(define (make-adder a)
  (λ (a b) (+ a b)))

This makes it so all the variables will always be bound, and we can generate code for this like for a normal lambda. Of course, we can't just return this to the user, because they will expect a single-argument function with environment attached.

Generate wrapper at runtime

At runtime, we generate a portal - a "function" we'll return to the user, that adds the environment to the normal function call.

For example, if we called the upper-mentioned make-adder with 32 at runtime, this would happen:

(define (make-adder a)
  (let ((pointer (malloc this-closure-size)))     ; this is lisp pseudocode. this is written by the compiler so the source is plain uxntal
    (generate-and-return-the-function-at pointer) ; but it does exactly that: malloc is used to allocate space after the end of rom for the closure, it gets generated
    pointer))                                     ; and the pointer to it gets returned
  
;; [...]
(define (main)
  (let ((func (make-adder 3)))
    ...))
  
;; [...]
(define (@@gensym__1 a b) ; <- this is the internal make-adder lambda, generated at compile-time
  (+ a b))

;;; -- [end of rom]
;; The following will be uxntal pseudocode generated at runtime on the call (make-adder 3)
LIT2 00 20       ; push 0x0020 (32) as the 1st argument (we call function passing arguments with reverse order so this being evaluated)
                 ; as last makes it the first argument
LIT2 @@gensym__1 ; push the lambda without environment - @@gensym__1 will of course be resolved to a place in memory
JMP2             ; jump to this function (not JSR2 to save space - @@gensym__1 will return back to the original caller)

Then if func was to be called with 10, the program counter would firstly land on the freshly generated closure code, 0x0020 would be pushed and @@gensym__1 would be called with 32 and 10 as a and b.

Example

This is a small example of a gui program that draws hearts in random spots.

(define *width* 400)
(define *height* 300)

(alloc! *heart-texture*
  #b01000010
  #b11100111
  #b11111111
  #b11111111
  #b01111110
  #b00111100
  #b00011000
  #b00000000)

(defvar heart!)

(define (make-drawer sprite)
  (λ (x y)
    (sprite! x y sprite 0 layer-1 0 0 1)))

(define (main)
  (set-draw-handler! draw)
  (set-colors! #x0f00 #x00f0 #x000f)
  (set-screen-width! *width*)
  (set-screen-height! *height*)

  (set! heart! (make-drawer *heart-texture*)))

(define-vector (draw)
  (let ((x (modulo (rand) *width*))
        (y (modulo (rand) *height*)))
    (heart! x y)))

make-drawer returns a closure, we'll take a closer look at what the generated code for it looks like. This is a decompilation spat out by nienor -OD with some extra commentary on top.

( defun normal make-drawer (sprite) )
( label: make-drawer )
( _with-locals! (sprite) ;; locals = (sprite) )
|06af   a0 01 0b    (  )
|06b2   ae          ( JSR2k )
|06b3   22          ( POP2 )
( label: make-drawer__skip-prologue )
( λ CLOSURE @@gensym__7 [ (sprite) ] (x y) )
( here we begin generating the closure )
( push closure size   ) |06b4   a0 00 07    (  )
( push malloc         ) |06b7   a0 06 41    (  )
( get place in memory ) |06ba   2e          ( JSR2 )
( for the function from malloc )
                        |06bb   26          ( DUP2 )
                        |06bc   80 a0       ( )
                        |06be   05          ( ROT )
                        |06bf   05          ( ROT )
( append LIT to the )   |06c0   95          ( STAk )
( new function )
                        |06c1   05          ( ROT )
                        |06c2   02          ( POP )
                        |06c3   21          ( INC2 )
                        |06c4   80 00       ( )
                        |06c6   10          ( LDZ )
                        |06c7   80 00       ( )
                        |06c9   19          ( SUB )
                        |06ca   80 02       ( )
                        |06cc   1a          ( MUL )
( load the local we're) |06cd   30          ( LDZ2 )
( saving from the zero-page - nienor stores locals in the zero-page [memory addresses from 0 to 255] )
                        |06ce   24          ( SWP2 )
( append the local to ) |06cf   b5          ( STA2k )
( the new function )
                        |06d0   23          ( NIP2 )
                        |06d1   21          ( INC2 )
                        |06d2   21          ( INC2 )
                        |06d3   80 a0       ( )
                        |06d5   05          ( ROT )
                        |06d6   05          ( ROT )
( append another LIT )  |06d7   95          ( STAk )
                        |06d8   05          ( ROT )
                        |06d9   02          ( POP )
                        |06da   21          ( INC2 )
                        |06db   a0 07 7b    (  )
                        |06de   24          ( SWP2 )
( append the full )     |06df   b5          ( STA2k )
( lambda location to the new function. here it's called @@gensym__7 and captures one argument [sprite] )
                        |06e0   23          ( NIP2 )
                        |06e1   21          ( INC2 )
                        |06e2   21          ( INC2 )
                        |06e3   80 2c       ( )
                        |06e5   05          ( ROT )
                        |06e6   05          ( ROT )
( append JMP2 to the )  |06e7   15          ( STA )
( new function )

( this is the end of the code generation on runtime. the value left on stack is the previously DUP2'd )
( pointer to the new function - the one we got from malloc )

( freeing 1 locals ;; locals = () )
|06e8   80 00       ( )
|06ea   10          ( LDZ )
|06eb   80 01       ( )
|06ed   19          ( SUB )
|06ee   80 00       ( )
|06f0   11          ( STZ )
|06f1   6c          ( JMP2r )

So, the code that gets generated at runtime in this case would be:

( |somewhere )
( we're assuming *heart-texture* is at #x110 )
( we're assuming @@gensym__7 is at #x500 )

LIT2 01 10 ( push *heart-texture* )
LIT2 05 00 ( push @@gensym__7 )
JMP2       ( jump to @@gensym__7 )

This is the entirety of the portal that we'll return to the user.

malloc?

I've implemented malloc & free to manually manage the memory left in the RAM after the ROM. They are also used to allocate closures - this means that when the user is done with a closure, they can simply free it to return unused memory to the pool.

For example:

(define (make-closure n)
  (λ () n))

(define (main)
  (let ((f1 (make 1))
        (f2 (make 2)))
    (print-number f1)
    (print-number f2)
    (free f1)
    (let ((f3 (make 3)))
      (print-number f3))))

This program yields:

1811
1820
1811

Because memory used by f1 (1811) got freed, f3 got allocated in the same spot (also 1811).

epilogue

This has not been battle-tested yet and is (of course) purely experimental. Thank you for reading. If I've sparked your interest, you can download niënor and follow its development here.