Scheme in Scheme on Wasm in the browser

Hey, folks! Today we want to talk about the wonderful read-eval-print-loop (REPL). Thanks to WebAssembly (Wasm), it's becoming increasingly common for programming language websites to embed a REPL in which passersby can easily evaluate code and get a feel for the language without having to install anything on their computer. We'd like to do the same thing for our language of choice, Guile Scheme, using Guile Hoot.

Guile Hoot is a Scheme-to-Wasm compiler that leverages the Wasm garbage collection (GC) extension that has been rolling out to major browsers recently. Wasm GC has finally made it possible to use dynamic languages besides JavaScript on the client-side web, but it will still take some additional effort to bring our favorite tools along for the ride. In this post, we'll walk through building a tiny Scheme interpreter with a simple user interface and explain what's in store for the future.

To learn more about Hoot, check out the 0.2.0 release announcement from a couple of weeks ago!

The case of the missing REPL

For Scheme programmers (and Lisp programmers in general), the REPL is at the core of our development workflow. We modify some code in our text editor, evaluate it in the REPL, inspect the output or enter a debugger, and repeat the process until the program behaves the way we want.

We're used to having a native REPL process running directly on our operating system, but since Hoot is putting Scheme on the web, we'd really like a REPL available in the browser, too. A web REPL would be convenient for seasoned Schemers and newcomers alike. However, at this early stage in Hoot's development, a fully-featured Scheme REPL is not yet possible. We don't have access to the macro expander, interpreter, etc. from the comfort of our Wasm runtime... yet.

We'll have these things eventually, but what can we have now?

Well, we could implement an interpreter for a small subset of Scheme... in Scheme! Sounds pretty recursive, and if you know anything about Schemers you know we love recursion (and also, that we love recursion), so let's give it a shot!

Scheme in Scheme

In Chapter 4 of the classic computer science textbook Structure and Interpretation of Computer Programs (SICP), Gerald Sussman and Hal Abelson walk through building a small Scheme interpreter embedded in Scheme. They called this the "metacircular evaluator", meaning that it's an interpreter written in the language that it is interpreting.

This sounds pretty fancy — the kind of task reserved for MIT professors that write iconic textbooks — but implementing a Scheme interpreter is simpler than one might think! For one thing, since Scheme can manipulate its own syntax by design, we don't need to spend any time parsing, a notoriously complex subject in its own right. We can skip directly to the fun part instead: evaluation!

Spritely's own Scheme Primer distills SICP's interpreter into a much simpler form intended for people who are brand new to Scheme. The code examples in the rest of this post are derived from the "Scheme in Scheme" section of the Primer. If you're completely new to Scheme and want to better understand the code in this post, consider working through our Primer sometime!

The metacircular evaluator is composed of two main components: eval and apply:

• eval processes an expression in the context of an environment.
• apply calls a procedure (function) with a list of arguments.

The output of eval is fed to apply, which may feed more input to eval, and this mutually recursive cycle continues until the program runs out of expressions to evaluate.

In order to implement eval, we first need a way to represent environments. An environment maps variable names to their bound values. We'll use association lists for our environments.

An empty environment with no variable bindings is represented by the empty list '().

The first bit of code from the metacircular evaluator we'll cover is the extend-env procedure, which creates a new environment by extending an existing one:

(define (extend-env env names vals)
  ;; If there are no more variables to add to env, return env.
  (if (null? names)
      env
      ;; Otherwise, add the first binding to the recursive
      ;; extension of env with the rest of the bindings.
      (cons (cons (car names) (car vals))
            (extend-env env (cdr names) (cdr vals)))))

We can extend the empty environment to make a new environment that includes the variable foo:

(extend-env '() '(foo) '(1)) ; => ((foo . 1))

We can further extend that environment to make a new environment that includes the variable bar:

(extend-env '((foo . 1)) '(bar) '(2)) ; => ((bar . 2) (foo . 1))

Note that environment manipulation is implemented in a functional style. Extending an environment does not mutate the original one. This is because mutating the original environment would propagate the new bindings to other evaluation contexts, potentially breaking Scheme's lexical scoping rules.

We can look up a variable's value using the env-lookup procedure:

(define (env-lookup env name)
  ;; Lookup name in association list.
  (match (assq name env)
    ;; Success: return the bound value.
    ((_ . val) val)
    ;; Failure: throw an error.
    (#f (error "Variable unbound:" name))))

Example:

(env-lookup '((foo . 1)) 'foo) ; => 1

And now for the rest of the owl. Our toy eval supports:

• booleans
• numbers
• strings
• quoted expressions
• conditionals
• procedures as values
• procedure calls

(define (eval expr env)
  (match expr
    ;; Booleans, numbers, strings
    ((or (? boolean?) (? number?) (? string?))
     expr)
    ;; Quoted expressions
    (('quote quoted-expr)
     quoted-expr)
    ;; Variable lookup
    ((? symbol? name)
     (env-lookup env name))
    ;; Conditionals
    (('if test consequent alternate)
     (if (eval test env)
         (eval consequent env)
         (eval alternate env)))
    ;; Procedures
    (('lambda args body)
     (lambda vals
       (eval body (extend-env env args vals))))
    ;; Procedure application
    ((proc-expr . arg-exprs)
     ;; Recursively evaluate the procedure expression and all
     ;; argument expressions, then apply the procedure with the
     ;; arguments.
     (apply (eval proc-expr env)
            ;; Recursively evaluate the arguments.
            (map (lambda (arg-expr)
                   (eval arg-expr env))
                 arg-exprs)))))

Fortunately, we don't need to implement apply ourselves. Since lambda forms in our interpreter evaluate to regular Scheme procedures, we can just use Scheme's built-in apply to pass arguments to them. Calling a procedure will recursively call eval on the procedure's body expression.

Example:

(eval '(+ 1 2 3) `((+ . ,+))) ; => 6

Incidentally, we've created a capability-secure system reminiscent of Wasm's security model! The program (+ 1 2 3) only has access to the + procedure from our Scheme runtime. Aside from creating unbounded loops, a devious developer can't do any harm if their code is evaluated in this restricted environment. Neat!

Scheme in Scheme on Wasm

Now that we have a simple evaluator, we can compile it with Hoot to run it inside a web browser. But to actually use it, we need a user interface. To make one, we can borrow the React-like rendering code we walked through in our previous tutorial on rendering web pages with Wasm, "Building interactive web pages with Guile Hoot"!

For simplicity, we'll go for a minimalist design reminiscent of a terminal. As for the REPL output log, we can store it as a list of strings. Let's pre-populate it with a friendly welcome message:

(define *log*
  '("Welcome to the Hoot metacircular evaluator demo!

This is a miniature Scheme interpreter written in Scheme that's been
compiled to WebAssembly, and is running directly in the browser!  Its
UI is also written in Scheme, and uses the Hoot FFI to render itself
to the DOM.

"))

(define (log-append! . lines)
  (set! *log* (append *log* lines)))

Here's the rendering template, which prints all the log lines, and appends the classic > prompt and a textarea to the bottom so the user can write some Scheme code:

(define prompt "> ")

(define (render)
  `(div (@ (class "container"))
        (h1 "Hoot REPL")
        (div (@ (id "repl")
                (class "repl repl-text"))
             (div (@ (class "log")) ,@*log*)
             (div (@ (class "prompt"))
                  ,prompt
                  (textarea (@ (id "expression")
                               (class "repl-text")
                               (placeholder "(+ 1 2 3)")
                               (keyup ,maybe-eval)))))))

Every time the user presses a key while focused on the textarea, we call the maybe-eval procedure shown below. When the user presses the Enter key, the REPL

• evaluates their code
• clears the textarea
• appends any new output
• scrolls to the bottom of the log to keep the terminal screen up to date

(define (maybe-eval event)
  ;; Get the event's key.
  (let ((key (keyboard-event-key event)))
    ;; Evaluate user code when Enter is pressed, but not when
    ;; Shift is being held so the user can edit across multiple
    ;; lines.
    (when (and (string-=? key "Enter")
               (not (keyboard-event-shift? event)))
      ;; Get the text within the expression textarea.
      (let* ((input (get-element-by-id "expression"))
             (exp (element-value input)))
        ;; If the textarea is empty, do nothing.
        (unless (string-=? exp "")
          ;; Clear the textarea.
          (set-element-value! input "")
          ;; Evaluate and append output to log.
          (eval! exp)
          ;; Update UI.
          (refresh!)
          ;; Scroll the log to show the next output.
          (scroll-to-bottom!))))))

At the bottom, you'll notice maybe-eval uses a new procedure we've called eval! (how exciting). eval! is eval + read — it parses the user's text using Scheme's built-in read procedure, calls eval, and prints the output to the log:

(define (eval! str)
  ;; Parse user input.
  (let ((exp (read (open-input-string str)))
        ;; Open output port.
        (output (open-output-string)))
    ;; Redirect all output to our output port.
    (parameterize ((current-output-port output))
      ;; Echo the prompt and user code.
      (display prompt)
      (display str)
      ;; Invoke the interpreter.
      (call-with-values (lambda () (eval exp init-env))
        ;; Display each returned value on its own line.
        (lambda vals
          (if (null? vals)
              (display "\n")
              (for-each (lambda (val)
                          (unless (unspecified? val)
                            (display "=> ")
                            (write val))
                          (newline))
                        vals)))))
    ;; Append output to log.
    (log-append! (get-output-string output))))

(Note how, thanks to read, we've elided the messy work of parsing.)

Expressions are evaluated within the context of the following environment that provides capabilities for basic arithmetic, lists, multiple value return, and printing:

(define init-env
  `((+ . ,+)
    (- . ,-)
    (* . ,*)
    (/ . ,/)
    (= . ,=)
    (cons . ,cons)
    (car . ,car)
    (cdr . ,cdr)
    (list . ,list)
    (pair? . ,pair?)
    (null? . ,null?)
    (values . ,values)
    (display . ,display)
    (newline . ,newline)))

The initial environment describes the primitive functionality of our interpreter. Primitives are simple things that the programmer can take for granted. This environment doesn't provide much, but it's enough to have a bit of fun.

And...

🥁

🥁

🥁

...here's the finished program!

Some expressions you could try:

Greet the world:

(display "Hello, world!")

Make a list of the veggies you want on your sandwich:

'(lettuce tomato onion pepper pickles)

Display all your favorite pets as multiple return values:

(values 'cat 'dog 'chicken)

Apply a procedure that squares numbers:

((lambda (x) (* x x)) 4)

Recursively apply a procedure to compute the nth Fibonacci number:

((lambda (f x) (f f x))
 (lambda (fib n)
   (if (= n 0)
       0
       (if (= n 1)
           1
           (+ (fib fib (- n 1))
              (fib fib (- n 2))))))
 10)

Whoa, that last one was kinda wild, huh? That's because our little interpreter lacks even the ability to bind variables outside of lambda. There is no let nor define, so recursive code gets weird fast! Talk about minimalism...

Scheming ahead

The interpreter we've shown here is just a toy, but in the coming months we expect to add support for the R7RS-small standard's eval, taking our REPL from toy to full Scheme interpreter.

Once we do so, we could embed Scheme REPLs directly into documents like the Scheme Primer, further reducing the activation energy required to get started with Scheme. And who knows what exciting integrations our community will come up with?

In the meantime, if you'd like to start immediately hacking on the REPL demo, you can find the complete source code on GitLab. If you're into homework assignments, try adding support for more Scheme syntax such as let, or adding more procedures to the environment to grant more power to the interpreter.

And be sure to show off what you build with Hoot in our community forum! (Use OCAPN2023 for the invite code when you join.)

Happy hooting! 🦉