Scheming a mise-en-abîme in BQN

We will build an interpreter for a subset of the Scheme programming language, following an essay by Peter Norvig. An alternative reference would have been of course SICP's metacircular evaluator¹, but I consider lispy to be a very elegant implementation targeting a non-Lisp host². Please beware this post is a learning exercise. Most of what I know about language implementation comes from self-study of a handful of books³.

Our goal is to adhere to the Revised\(^5\) Report on the Algorithmic Language Scheme (R5RS). However, seasoned schemers will quickly notice that our implementation still has quite some distance to cover in reaching full compliance.

Let's start by defining some utilities. One aspect I don't like about Scheme is that it uses special values for Booleans, so we unfortunately need the 1-modifier. The function, on the other hand, is a fine example of the minimalistic OOP features BQN provides. It is used to create a class for the environment used in the Scheme interpreter.

_bool ← {𝔽◶"#f"‿"#t"}
C ← {𝕨𝕊p‿v:
  o‿h ⇐ 𝕨 ⋈ p •HashMap v
  F ⇐ {h.Has 𝕩 ? h; @≢o ? o.F 𝕩; 0}
}

We then define a global environment (instance of the C class) with the Scheme primitives of the target subset, expressed as BQN functions:

env ← @ C ⟨
  "sin", "cos", "tan", "asin", "acos", "atan"
  "log", "+", "-", "*", "/", ">", "<", ">=", "<=", "="
  "abs", "append", "apply", "begin", "car", "cdr", "cons"
  "eq?", "expt", "equal?", "length", "list", "list?"
  "map", "max", "min", "not", "null?", "number?"
  "print", "round", "symbol?", "nil", "pi"
⟩ ⋈ ⟨
  ⋆⁼, +´, -´, ×´, ÷´, >´, <´, ≥´, ≤´, =´
  |, ∾´, {𝕎𝕩}´, {∾𝕩}, ⊑∘∾, 1⊸↓∘∾, <⊸∾´
  ≡´_bool, ⋆´, =´_bool, ≠∘∾, ⊢, (0=•Type∘⊑)_bool
  {𝕎∘⋈¨𝕩}´, ⌈´, ⌊´, 0⊸≠_bool¬, @⊸=_bool, (1=•Type∘⊑)_bool 
  •Show, ⌊0.5+⊢, 2⊸=_bool{•Type⊑∾𝕩}, @, π
⟩ ∾˜ •math •ns.Get¨ "sin"‿"cos"‿"tan"‿"asin"‿"acos"‿"atan"

The interpreter is defined as a 1-modifier. This gives us the flexibility to create different subsets of the language by changing the input global environment:

_sch ← {
  T ← (⊢/˜·∨´¨' '⊸≠)·(-⟜1·+`·¬⊸∧⟜»⊸∨·+˝"( )"=⌜⊢)⊸⊔(⊢+22×@=10-˜⊢)
  R ← {
    𝕊⟨⟩: "Empty program"!0;
    𝕊𝕩: {
      "("≡⊑𝕨 ? l←⟨⟩ ⋄ l⋈1↓{t‿ts: ts⊣l∾↩<t}∘R•_while_(")"≢⊑) 𝕩;
      ")"≡⊑𝕨 ? "Unexpected )"!0 ;
      𝕩 ⋈˜ •ParseFloat⎊⊢ ⊑𝕨
    }´ 1(↑⋈↓)𝕩
  }
  E ← {
    0≠𝕨.F 𝕩 ? (𝕨.F 𝕩).Get 𝕩;
    1=•Type⊑⟨𝕩⟩ ? 𝕩;
    "quote"≡⊑𝕩 ? ·‿arg ← 𝕩 ⋄ arg;
    "if"≡⊑𝕩 ? ·‿tst‿cnd‿alt ← 𝕩 ⋄ 𝕨(⊣𝕊𝕊◶alt‿cnd)tst;
    "define"≡⊑𝕩 ? ·‿var‿val ← 𝕩 ⋄ ⟨⟩ ⊣ var 𝕨.h.Set 𝕨𝕊val;
    "lambda"≡⊑𝕩 ? ·‿par‿bod ← 𝕩 ⋄ 𝕨{bod E˜ 𝕗 C par‿𝕩};
    f ← 𝕨𝕊⊑𝕩 ⋄ F 𝕨⊸𝕊¨1↓𝕩 
  }
  P ← (⊢+˝("(   )"-"⟨"",‿⟩")×"⟨"",‿⟩"=⌜⊢)∘•Repr·1⊸=∘≠◶⊢‿⊑(0<≠¨)⊸/⎊⊢
  P 𝕗⊸E⊑R∘T 𝕩
}

And now for the climax. Our interpreter inherits all the limitations of the one in the reference essay, the most critical being the lack of proper error handling. Additionally, as the names of the functions inside the modifier suggest, an L is missing to complete the Read → Eval → Print loop. In terms of golfing statistics, lispy has 117 non-comment non-blank lines, whereas Scheme has only 42.

Scheme ← env _sch

Given the title of this post, it's only fitting that we test our interpreter with a quine. In fact, building this interpreter was, for me, an exercise in bootstrapping the necessary machinery to produce this recursive effect:

Scheme "((lambda (x) (list x (list (quote quote) x)))
         (quote (lambda (x) (list x (list (quote quote) x)))))"

"(( lambda  ( x ) ( list   x  ( list  ( quote   quote )  x ))) ( quote  ( lambda  ( x ) ( list   x  ( list  ( quote   quote )  x )))))"

Naturally, we can do more rigorous tests by comparing to my favorite Scheme implementation⁴. To achieve this, we'll leverage BQN's foreign function interface:

ch ← "../supp/chicken/libchicken.so" •FFI "*u8"‿"eval_scheme"‿">*u8:c8"
R5RS ← {@+𝕩.Read¨ ↕1⊸+•_while_(0≠𝕩.Read)0}Ch

But fear not, there’s no room for monotony here. After all, people much prefer dealing with machinery to dealing with bureaucracies⁵:

(Scheme⋈R5RS)¨ ⟨
  "(+ 10 122)"
  "(* 4 2)"
  "(begin (define r 10) (+ (/ 4 2) (* r r)))"
  "(number? (quote b))"
  "(symbol? (quote var))"
  "(if (> (* 11 11) 120) (* 7 6) oops)"
  "(car (quote (1 2 3)))"
  "(list? (quote (1 2 3)))"
  "(length (quote ((1 2) 3)))"
  "(begin
     (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
     (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
     (map fib (range 0 10)))"
⟩

⟨ ⟨ "132" "132" ⟩ ⟨ "8" "8" ⟩ ⟨ "102" "102" ⟩ ⟨ " #f " "#f" ⟩ ⟨ " #t " "#t" ⟩ ⟨ "42" "42" ⟩ ⟨ "1" "1" ⟩ ⟨ " #t " "#t" ⟩ ⟨ "2" "2" ⟩ ⟨ "1 1 2 3 5 8 13 21 34 55" "(1 1 2 3 5 8 13 21 34 55)" ⟩ ⟩

If you manage to find any sneaky corner cases that break the interpreter in the given subset, let me know! And please forgive the formatting problems, I'm tired of fiddling with the printer at this point.