https://panadestein.github.io/blog/posts/si.html#fnr.2

Scheming a mise-en-abime in BQN

Prelude

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^1,
but I consider lispy to be a very elegant implementation targeting a
non-Lisp host^2. 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^3.

A R5RS dialect

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#"#f"_"#t"}
C - {wSp_v:
  o_h = w [?] p *HashMap v
  F = {h.Has x ? h; @[?]o ? o.F x; 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"
>  [?] <
  [?]=, +', -~'[?], x', /~'[?], >', <', >=', <=', ='
  |, [?]', {Wx}', {[?]x}, [?][?][?], 1[?]|[?][?], <[?][?]'
  [?]'_bool, [?]', ='_bool, [?][?][?], [?], (0=*Type[?][?])_bool
  {W[?][?]"x}', [?]', [?]', 0[?][?]_bool!, @[?]=_bool, (1=*Type[?][?])_bool
  {x}, [?]0.5+[?], 2[?]=_bool{*Type[?][?]x}, @, p
>  [?]~ *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*+`*![?][?][?]>>[?][?]*+""( )"=[?][?])[?][?]([?]+22x@=10-~[?])
  R - {
    S<> : "Empty program"!0;
    Sx: {
      "("[?][?]w ? l-<>  [?] l[?]1|{t_ts: ts[?]l[?]-<t}[?]R*_while_(")"[?][?]) x;
      ")"[?][?]w ? "Unexpected )"!0 ;
      x [?]~ *ParseFloat[?][?] [?]w
    }' 1(|[?]|)x
  }
  E - f[?]{
    0[?]w.F x ? (w.F x).Get x;
    1=*Type[?]<x>  ? x;
    wS"quote"_arg: arg;
    wS"quasiquote"_arg: w{"unquote"[?][?]x ? fG1|x; (2<=[?])#[?]_(S")x}Sarg;
    wS"if"_tst_cnd_alt: w([?]SS#alt_cnd)tst;
    wS"define"_var_val: <>  [?] var w.h.Set wSval;
    wS"lambda"_par_bod: w{bod g~ f C par_x}S;
    f - wS[?]x [?] F w[?]S"1|x
  }[?][?]
  P - "-(@  )" {'@'[?][?][?]/*([?]+"(f-g)xg=[?][?])[?]*Repr*1[?]=[?][?]#[?]_[?](0<[?]")[?]/[?][?]} "-<"",_> "
  P[?]E[?]R[?]T x
}

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 43. Ours,
however, is a larger subset, because we include the basic
metaprogramming building blocks.

Scheme - env _sch

A Lisp quine

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^4. To achieve this, we'll leverage BQN's
foreign function interface:

ch - "../../supp/chicken/libchicken.so" *FFI "*u8"_"eval_scheme"_">*u8:c8"
R5RS - {@+x.Read" |1[?]+*_while_(0[?]x.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^5:

("Not Compliant"[?]!Scheme[?]R5RS)" <
  "(+ 10 122)"
  "(max 5 6 7 1)"
  "(* 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)))"
  "(quasiquote (unquote (quote pointless)))"
  "(quasiquote (apply + (list 1 1 2 (unquote (+ 1 2)))))"
  "(begin
     (define our-goal (quote macros))
     (quasiquote (A little step towards (unquote our-goal) mate!)))"
  "(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)))))
     (apply - (map fib (range 0 10))))"
> 

< 1 1 1 1 1 1 1 1 1 1 1 1 1 1 > 

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.

Footnotes:

^1

I recommend SICP as further reading. Much like Louis Reasoner, I
attempted solving all the problems in the book, but I haven't gotten
very far. I believe there are some interesting Racket bits in my
solutions, though.

^2

I am not alone in this view; for instance, the Lizard Book dedicates
an entire section to it.

^3

In addition to the great SICP, I also studied from Crafting
Interpreters and Introduction to Compilers and Language Design.

^4

One of my favorite hacker guidelines is The Brutalist Programming
Manifesto, written by the creator of Chicken Scheme.

^5

John McCarthy, 1986.

[?][?][?]