# Lisp in Small Pieces
> A comprehensive account of the semantics and the implementation of the whole Lisp family of languages, namely Lisp, Scheme and related dialects. It describes 11 interpreters and 2 compilers, including very recent techniques of interpretation and compilation. The book is in two parts. The first starts from a simple evaluation function and enriches it with multiple name spaces, continuations and side-effects with commented variants, while at the same time the language used to define these features is reduced to a simple lambda-calculus. Denotational semantics is then naturally introduced. The second part focuses more on implementation techniques and discusses precompilation for fast interpretation: threaded code or bytecode; compilation towards C. Some extensions are also described such as dynamic evaluation, reflection, macros and objects.
## Reference
- My take
- [[Lisp in Small Pieces-Christian Queinnec and Kathleen Callaway|Kindle Highlights]] _note: unpublished, copyright reasons_
- [pmbauer/LiSP-2022](http://github.com/pmbauer/LiSP-2022) code
- [Christian Queinnec's Book Site](https://christian.queinnec.org/WWW/LiSP.html)
- [1st Edition Code](https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/bookcode/queinnec/lisp.tgz) ^e2a6cb
- [2nd Edition Code](https://christian.queinnec.org/Books/LiSP-2ndEdition-2006Dec11.tgz)
### Bibliography
Source links I found interesting from the book's extensive Bibliography.
- [McC78b](x-devonthink-item://949B17C3-ECED-40BB-981C-A11E992907F0) [alt source](https://www.uraimo.com/files/MicroManual-LISP.pdf) - In Proc. SIGPLAN History of Programming Languages Conference, pages 214-216, 1978. ^1f01a1
- > the shortest article ever written that still presents an evaluator. (Ch1 Recommended Reading)
## Preface - To The Reader
It's interesting that Queinnec says "_Lisp is the most representative of the_ [[Lisp in Small Pieces-Christian Queinnec and Kathleen Callaway#^6f12e2|applicative languages]]" even though most Lisps wouldn't be considered purely functional - Common Lisp, Clojure and Scheme included.
Structure section [[Lisp in Small Pieces-Christian Queinnec and Kathleen Callaway#^321803142|promises some instruction]] in [denotational semantics](https://en.wikipedia.org/wiki/Denotational_semantics)
The S-expression-as-chapter-summary in Figure 1 is clever, pithy, helpful.
![[LiSP Fig 001.png]]
### Notation
| symbol | meaning |
| ------ | -------------------------------- |
| `->` | has this for its value |
| `≡` | equivalence, same value as |
| \| | indicates evaluation environment |
![[LiSP notation.png]]
### Scheme Summary
- [MIT/GNU Scheme Reference Manual](https://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-ref.pdf)
- [r6rs](http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-2.html#node_toc_start)
- [racket-lang forms](https://docs.racket-lang.org/reference/syntax.html)
## Ch1 - The Basics of Interpretation
> Literature about Lisp rarely resists that narcissistic pleasure of describing Lisp in Lisp. ([Location 484](https://readwise.io/to_kindle?action=open&asin=B00AKE1U6O&location=484))
^bee440
See [[#^1f01a1|McC78b]] for an `eval` that fits in one column of an A4 paper.
See [[Lisp in Small Pieces-Christian Queinnec and Kathleen Callaway|Kindle Highlights]] (not published for copyright reasons)
### 1.1 Evaluation
> The fact that the definition of `eval` is available in Lisp means that the programming environment is part of the language, too, and costs little. [...] writing [a tracer, debugger, etc] to control evaluation is just a matter of elaborating the code for `eval`.
`eval` enables powerful tooling with little effort. The cost of this power is including an entire interpreter or compiler in the execution environment, forfeiting some advanced optimizations.
### My goals and implementation for Ch1
[_baby_](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L115) Scheme: [LiSP/ch01.clj](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj)
```clojure
;; baby scheme
(def baby
(-> {}
(definitial |t| true)
(definitial |f| ::false)
(lift cons cons 2)
(lift car first 1)
(lift cdr rest 1)
...))
(defn a-corner [thing]
(if (= baby thing)
(wrong "Nobody puts baby in a-corner.")))
```
#### Goals
Porting is a great way to comprehend code and meets my goal getting back to speed writing [[Clojure]]. The [[#Downsides|downside]] is it limits my ability to complete some of the chapter exercises.
[It's been a bit](https://bauer.codes/post/2022/04/the-cdr-fell-off/) since I wrote [[Clojure]] for work and I want to learn:
- [[Clojure#Built-in Tooling tools deps tools build and cli CLI|Clojure's built-in build tooling]]
- [doom](https://github.com/doomemacs/doomemacs) [[emacs]] with [[Clojure]]
- a test workflow with [[Rich Comment Forms]]
#### Implementation
Beyond idiomatic [[Clojure]] [sequences](https://clojure.org/reference/sequences) and [destructuring](https://clojure.org/guides/destructuring) in place of [cons cells](https://en.wikipedia.org/wiki/Cons), my implementation departs from [[#^e2a6cb|the book code]] in significant ways.
##### Environment
Rather than a global mutable [association list](https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node153.html), _baby_'s [environment is represented](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L115) as [an immutable map](https://clojure.org/reference/data_structures#Maps). This changes the signature for `evaluate` `eprogn` and `evlis` from
> (expressions env) -> result
to
> (env expressions) -> (env' result)
```clojure
(evaluate '{a 1} '(set! b a))
;;=> [{a 1, b 1} 1]
(evaluate '{a 1} '(quote a))
;;=> [{a 1} a]
```
##### `set!`
As [[#^e2a6cb|the book's Scheme implementation]] has no special form or mechanism to define variables, it forces some awkward use of the `definitial` macro in the host language prior to launching the language [REPL](https://en.wikipedia.org/wiki/Read–eval–print_loop) - `set!` throws an exception if a var doesn't exist already.
I chose to deviate here and only throw an exception on lookup of an undefined variable. The `set!` special form serves both mutation and initial definition duties.
##### lexical and dynamic scopes
Using an immutable map for the environment forced me to think explicitly about scoping rules around nested closures, and made for a neat dynamic scope implementation. I went through several buggy iterations, guided by this little test ...
```clojure
"side effects and closures"
(-> (evaluate '{a 0}
'(((lambda (c)
(set! e c) ;; captures local c
(set! c 4) ;; updates local c
(lambda (a) ;; shadows global a
(set! d a) ;; captures local a
(set! a c) ;; writes to local a
(set! b a))) ;; captures closed over c value, final return
2)
3))) := ['{a 0, b 4, d 3, e 2, ::locals nil} 4]
```
For fun, I ran that expression through a [racket](https://racket-lang.org) R5RS REPL with the book's interpreter and verified the semantics and final values for the globals `a`, `b`, `d`, and `e` ...
... and ended up with this `make-function`.
```clojure
(defn invocation-env [defenv callenv params vals]
(if (= (count params) (count vals))
(assoc callenv ::locals (merge (::locals (choose-binding defenv callenv))
(zipmap params vals)))
(wrong "incorrect number of args")))
(defn make-function
"[definition-env params body] -> [env argvals] -> [env' result]"
[defenv params body]
(fn [env vals]
(let [caller-locals (::locals env)
env-with-locals (invocation-env defenv env params vals)
[env' res] (eprogn env-with-locals body)]
[(assoc env' ::locals caller-locals) res])))
```
As local scoping is only additive for keys, we can get away with a map merge on `::locals` instead of a stack to define precedence.
The `make-function`'s return value has access to both definition and calling environments, so switching between lexical and dynamic scope is as [easy as redefining](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L202) `choose-binding`.
```clojure
(defn ^:dynamic choose-binding [lexical dynamic]
lexical)
...
(binding [choose-binding (comp second list)]
(evaluate baby ...))
```
##### Advantages
[[Clojure]]'s `seq` abstraction and destructuring make for some expressive code. Here's `eprogn` and `evseq` (`evlis`).
```clojure
(defn evreduce [env f val s]
(reduce (fn [[env col] exp]
(let [[env' res] (evaluate env exp)]
[env' (f col res)]))
[env val]
s))
(defn eprogn
"[env exp-seq] -> [env' last-result]"
[env s]
(evreduce env (comp second list) nil s))
(defn evseq
"[env exp-seq] -> [env' result-col]"
[env s]
(evreduce env conj [] s))
```
Testing _baby_ at a _baby_ REPL as the book example code does is an inferior UX to quickly running the entire test suite on save, and pure functions make testing easy, repeatable. ^68d265
##### Downsides
This nagging feeling that _baby_ isn't a "real" Lisp. [[#^bee440|It can't eval itself]]. I'd need to re-implement `evaluate` using a restricted set of primitives, removing or re-implementing [[Clojure]]'s rich `let` bindings, destructuring, immutable maps, `::false` representation for booleans, [[Clojure]] seqs, `reduce`, `merge`, `zipmap`, `fn?`, `condp` ...
This is making me re-think [[Clojure]] as a choice for [[LiSP 2022]].
So maybe it's not a real Lisp, [however](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L146) ...
```clojure
(a-corner baby)
;;=> Execution error ...
;; Nobody buts baby in a-corner.
```
#### Exercises
- 1.1 - [trivial](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L55)
- 1.2 - N/A; already used [[Clojure]] seq abstraction and reduce
- 1.3 - N/A
- 1.4 - see [[#lexical and dynamic scopes]]
- 1.5 - used a namespace-qualified keyword - `::false`
- 1.6 - [code](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L130); used `apply list` to coerce vals into a list, maybe not necessary
- 1.7 - `call/cc` "_for those who are fond of continuations_" I chose to temporarily identify as "not fond" and skipped. I'm implementing this in [[Clojure]] and using the host language runtime stack. Continuations on the [[JVM]] are non-trivial, so no easy way to hoist this into the interpreter without a rewrite. See [[#Downsides]]
- 1.8 - [code](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L133); a little tricky flattening [the valid args](https://github.com/pmbauer/LiSP-2022/blob/trunk/src/codes/bauer/LiSP/ch01.clj#L190), but `(apply list* args)` seems the cleanest way to do it rather than some `mapcat` or `concat` contortions testing for `sequential?`
- 1.9 - skipped as [[#^68d265|I didn't find using the interpreter REPL useful]]; trivial
- 1.10 - see [[#Downsides]]
- 1.11 - N/A