uLisp port to C and WebAssembly

#1

Hello fellow Lispers,

I’m pleased to share some progress made on porting uLisp to C and WebAssembly.

30

The C port is adapted from the ESP32 version written for Arduino (a variant/subset of C++).

For the conversion, I studied this prior art posted here:

Based on this example I gradually rewrote or patched the Arduino/ESP-related parts of ulisp-esp (~8000 lines) into generic C99. It’s compiled with CMake and Clang.

It can now evaluate Lisp expressions but missing most features like I/O devices. So far I’ve run it on desktop Linux (Ubuntu) and Raspberry Pi Zero (32-bit Raspbian). A start of a tiny command-line interface (CLI) and interactive shell (REPL) in the terminal.

image

The WebAssembly binary is built from the same C code using Emscripten.

It runs in the browser, and on server-side JavaScript runtimes like V8, Node/Bun/Deno. A few functions were added to the uLisp interpreter to communicate to/from the host, to send messages or emulate ports and devices. This build target has potential to extend uLisp with features provided by the host, like network access (HTTP, WebSocket), servers, file system, database.

A much smaller bare Wasm binary can be built using Clang, that runs on Wasm runtimes with WebAssembly System Interface (WASI) - a kind of abstract interface for POSIX-like I/O. I’m still learning how to make it work.

The test suite from ulisp-builder was ported to the project, and eventually I got ulisp-wasm to pass all 640 tests.

For the code editor on the web, I used CodeMirror with language extension for Lisp syntax highlight and Paredit for basic structural editing (experimental).

It’s all still a rough prototype, made using tools I’m comfortable with, like TypeScript and Docker. I plan to extract the core into a small standalone C library - but in its current state it’s probably not usable by anyone yet. It’s been fun, technically challenging, and I’m learning a lot.

Next steps and ideas:

  • Playground with editor and live preview
  • Documentation with runnable code examples
  • Import/export, shareable links
  • Emulate ports and devices - LED lights, display/canvas, local storage
  • Single-file executable binary for major operating systems: Linux, macOS, Windows
  • uLisp-based OS with Wasm unikernel on bare metal :¬)
#2

One of the problems with the Web Assembly virtual machine is lack of support for deep recursion.
I think the parser needs to turn a tail recursive form into an imperative form.

It would be very natural in Lisp to write a recursive main “loop” that cycles forever.

Error: Maximum steps exceeded: 999999
#3

uLisp already turns tail recursive forms into imperative forms. You can see this by printing (locals), which is the Lisp stack.

For example:

(defun tail-recursive (n)
  (print n)
  (print (locals))
  (delay 500)
  (tail-recursive (incf n)))

> (tail-recursive 1)

1 
((n . 1)) 
2 
(nil (n . 2) nil (n . 2)) 
3 
(nil (n . 3) nil (n . 2)) 
4 
(nil (n . 4) nil (n . 2)) 
5 
(nil (n . 5) nil (n . 2))

In this case the stack doesn’t grow.

If you prevent the function from being tail recursive:

(defun not-tail-recursive (n)
  (print n)
  (print (locals))
  (delay 500)
  (+ (not-tail-recursive (incf n)) 2)

> (not-tail-recursive 2)

2 
((n . 2)) 
3 
((n . 3) (n . 3)) 
4 
((n . 4) (n . 4) (n . 3)) 
5 
((n . 5) (n . 5) (n . 4) (n . 3)) 
6 
((n . 6) (n . 6) (n . 5) (n . 4) (n . 3))

In this case the stack grows continuously.

#4

I’ll have to try once more with his online REPL (link in the post).
I may have made a typo but I don’t know how to enter Ctrl on this phone so his REPL accepts it

I will say I used 1+ in tail position with 500,000 loops not incf (no need to mutate).

I’ll try again once I get home on a computer. Could be my error.

EDIT:

Hmm the following does indeed still produce an error in his REPL.

(defun test (n limit)
  (if (>= n limit)
    (print n)
    (test (1+ n) limit)))

(test 0 500000)

Console

Error: Maximum steps exceeded: 999999
#5

It may be nothing to do with the recursion stack. The error message implies that the test is for iterations rather than stack size. Have you tried:

(dotimes (n 1000000) (print n))
#6 
...
249995 
249996 Error: Maximum steps exceeded: 999999
#7

OK, so it’s nothing to do with recursion. There’s something either in WebAssembly, or in the port of uLisp by @eliot, limiting the number of statements it can execute.

#8

Is the locals function documented anywhere? Cause that’s really useful

#9

It’s in the built-in documentation:

> (? locals)
(locals)
Returns an association list of local variables and their values.

I should probably add it to the Language Reference.

#10

Error: Maximum steps exceeded: 999999

To clarify, this is an optional and customizable limit added to the host. It’s meant to prevent locking up the editor interface if the execution takes too long in terms of “steps”.

It’s actually a temporary measure, as I’m still working on running the uLisp interpreter in a worker thread separate from the main execution thread (JavaScript and UI). Then it will be able to loop indefinitely in parallel, without interfering with the editor.

Web Assembly virtual machine is lack of support for deep recursion. I think the parser needs to turn a tail recursive form into an imperative form

Good point, Wasm did indeed lack tail-call optimization until recently. Apparently it’s now supported by major browsers. https://webassembly.org/features/#:~:text=Tail,Call

But that’s for tail recursion in the Wasm bytecode as a compile target. There’s an example given in this article when V8 (JS/Wasm engine) added support for it. So if the uLisp interpreter used tail recursion in its C source code (and the tail was explicitly marked as such using an attribute __musttail__) then that would be compiled by Emscripten to use the new tail call instructions in Wasm.

When running Lisp code, the uLisp interpreter handles tail calls - if I’m not mistaken, here in the eval function.

while (form != NULL){
  object *obj = cons(eval(car(form),env),NULL);
  cdr(tail) = obj;
  tail = obj;
  form = cdr(form);
  nargs++;
}

I love this part of Lisp interpreters in general, it’s elegant how recursion is unrolled into a single while loop.

limiting the number of statements it can execute

For this I added a function yield_loop() to the interpreter to call the host on every “step”. A step is each part of a statement, including function arguments - I guess it’s more properly termed a “node” of an expression in the abstract syntax tree.

The host can decide when to advance to the next step, effectively pausing the runtime; or to stop execution for any reason, like timeout or user action. (Aha, so I can add a play/pause/stop button in the web interface, when it supports infinite loop.)

This feature to run the code step by step, I’m hoping to also use it for educational purpose - for example in a tutorial, visually highlighting parts of the code as it runs.

I did find a way to cause an actual stack overflow error in the web interface though, simply by running (fib 511).

That shouldn’t have happened, since the tail call is supposed to be eliminated to not use the stack. And the loop should have been stopped by the maximum steps limit instead.

So that’s something to solve. I’ll need to find out if the error is thrown from JS or uLisp side. …Oh, since the error message is in lowercase, stack overflow, I found it here in the interpreter.

(defun fib (n)
  (if (< n 3) 1
    (+ (fib (- n 1)) (fib (- n 2)))))

(fib 511)

When it’s (fib 51) it stops due to max steps limit. When it’s (fib 511) it causes stack overflow.

Maybe because fib is calling itself twice in the final statement, and the first one is not considered part of the “tail”?