A Scheme Primer(spritely.institute)
spritely.institute
A Scheme Primer
https://spritely.institute/static/papers/scheme-primer.html
34 comments
Scheme is probably my favorite language for learning and tinkering, precisely because of its simplicity and minimalist standard library. Starting with the most simple elements and then building up to powerful abstractions is a satisfying experience.
I loved most things I've read that used scheme, that said I struggle to write mid-sized programs in it (I have the same problem with clojure).
A primer and a main charge. Very dense. Goes from nothing to walking
binary trees and macros in about a hundred nicely sequenced
steps. Wish I'd had this when we did SICP. Bookmarked to give to
students.
Haha, thanks! Going from nothing to some of the deeper ideas of SICP and friends was definitely a goal, glad to hear it landed that way for some people. Hope it's helpful for your students... if it is, let me know! :)
I had no idea that's where 'primer' came from!
> I had no idea that's where 'primer' came from!
It isn't. That was the GP either misunderstanding or, perhaps more probably, making a pun. The usage here is this sense of the word: https://en.wikipedia.org/wiki/Primer_%28textbook%29
(Then again, maybe your comment was just a way of saying "ISWYDT!" to the GP?)
It isn't. That was the GP either misunderstanding or, perhaps more probably, making a pun. The usage here is this sense of the word: https://en.wikipedia.org/wiki/Primer_%28textbook%29
(Then again, maybe your comment was just a way of saying "ISWYDT!" to the GP?)
The little schemer book https://mitpress.mit.edu/books/little-schemer-fourth-edition is my favourite introduction to scheme and to functional programming.
Fair warning: Don't be fooled by its cute images. This is a difficult book. It needs heavy work from you to understand; I've done some analysis on racket in this gh repo for anyboddy interested: https://github.com/spapas/little-schemer
Unfortunately, I was never able to understand the Y combinator chapter :(
Fair warning: Don't be fooled by its cute images. This is a difficult book. It needs heavy work from you to understand; I've done some analysis on racket in this gh repo for anyboddy interested: https://github.com/spapas/little-schemer
Unfortunately, I was never able to understand the Y combinator chapter :(
Racket is great for this book. With some work it's also doable in Common Lisp, here's my take: https://github.com/tsumo/solutions/blob/master/little_scheme...
I found the book's tones to be insufferably annoying.
I'm glad the author wrote this with Guile scheme in mind and mentioned Racket/DrRacket. Both are certainly beginner friendly ways of getting started with scheme in my opinion. I love how this goes from here's how to define a procedure to really showing some muscle flexing. I think the real way of getting someone turned towards scheme or lisp is taking them from the easy stuff to doing things that would be harder to understand/implement in other programming languages without lots of expertise in those languages.
Scheme is a language I love. Chez Scheme is even fast. I don't use it because the support for parallel programming looks like 1990. In contrast, one can add a handful of lines to a Haskell program and keep 16 cores busy on a Mac Studio. Even Ruby now cleanly supports parallel execution. We're fast reaching the point where any language that doesn't support parallelism, or only via cumbersome locks and so forth, is a toy.
Do you mean like fibers ( https://github.com/wingo/fibers ), or something beyond that?
For me CML is probably the nicest concurrency thing I know. It might not be as general as the actor model, but is much nicer to work with.
What made me look into it was an interview with Mike Sperber where he said that CML was usually the first thing he implemented in a new language so that he could get work done.
What made me look into it was an interview with Mike Sperber where he said that CML was usually the first thing he implemented in a new language so that he could get work done.
Interesting! Here's one of the co-developers of Guile Scheme (and the author of that fibers library) pondering about CML: https://wingolog.org/archives/2016/09/21/is-go-an-acceptable...
Clojure is derived from Scheme and supports parallel programming.
Clojure is a dialect of Lisp according to its website.
Lisp and Scheme's histories are tightly coupled. I would say Clojure is Scheme-like in its preference for functional programming and immutable data. I think Lisp is as much an imperative and OOP language as it is functional.
It's probably true but I don't think I recall rich hickey mention scheme once. He said he worked in CL .. it's strange because the minimalist aspect are really close to scheme, but really I don't remember him mentionning that. Funny
ps: not contradicting you btw
ps: not contradicting you btw
...and Scheme is a dialect of Lisp. Clojure and Scheme are similar in that they are Lisp-1s. You can look that up too, but it is a rough reference to a count of namespaces.
Clojure looks an feels more like a Scheme than Common Lisp
The "scheme in scheme" section is cheating, imo. I like to imagine language implementation on a line between:
- Implement JS in one line with `eval(input)`
- Hand-crafted asm compiler with manual lexing, parsing, codegen, etc
This article is far closer to `(eval input)` than to a real interpreter. The entire front-end is pushed onto the native implementation, and even the tree-walking interpreter just mostly delegates to the host implementation.
I'm not saying that it's useless; it's a very elegant demonstration of how a tree-walking interpreter works at the very simplest level: for each node, evaluate their children, with literals evaluating to themselves and symbols resolving according to their environment. It neatly demonstrates the core principles, but fails to demonstrate any of the parts about language implementation that's actually interesting.
You don't get details (that somebody ultimately has to write) about memory layout, GC implementation, continuations, etc. This is all punted to the host implementation.
- Implement JS in one line with `eval(input)`
- Hand-crafted asm compiler with manual lexing, parsing, codegen, etc
This article is far closer to `(eval input)` than to a real interpreter. The entire front-end is pushed onto the native implementation, and even the tree-walking interpreter just mostly delegates to the host implementation.
I'm not saying that it's useless; it's a very elegant demonstration of how a tree-walking interpreter works at the very simplest level: for each node, evaluate their children, with literals evaluating to themselves and symbols resolving according to their environment. It neatly demonstrates the core principles, but fails to demonstrate any of the parts about language implementation that's actually interesting.
You don't get details (that somebody ultimately has to write) about memory layout, GC implementation, continuations, etc. This is all punted to the host implementation.
While you are right that there are a lot deeper topics, the point of this primer was to be a primer, not a language design piece. It was also to show off one of the more powerful pieces of Lisp/Scheme: that metacircular evaluators (or, as you say, tree walking interpreters) are trivially easy to write partly because of how the language works in a way that is fairly unique to those languages.
If you read SICP, chapter 4 is basically a long-form introduction to the tree walking interpreter I introduce in the document, and chapter 5 gets into how to write a register VM with the lower level details you describe. However chapter 4 is where the most important unlocks of demystifying how programming languages work. Much design of programming languages in lisp has happened within metacircular evaluators first, and the efficient implementation later. Within a few tweaks, you can change your language to a logic programming language like Prolog, or switch from lexical scoping to dynamic scoping. This is power. And it isn't possible in most other programming languages. SICP was recently ported to Javascript, and it's an amazing conversion, but there's an extra step for parsing the source text which turns it into something that doesn't look like javascript anymore, whereas a lispy evaluator looks just like lisp.
Again, this is a primer. Showing off that you can do such a thing in 30 lines of code is something that few primers which are less than 30 pages would dare to do. It's possible to demonstrate in lisp/scheme partly because of lisp's language choices. And it's hopefully useful: I know when I wrote my first metacircular evaluator at the end of reading The Little Schemer, it demystified programming languages for me in a huge way. I hope a bit of that demystification shows up here for others too.
If you read SICP, chapter 4 is basically a long-form introduction to the tree walking interpreter I introduce in the document, and chapter 5 gets into how to write a register VM with the lower level details you describe. However chapter 4 is where the most important unlocks of demystifying how programming languages work. Much design of programming languages in lisp has happened within metacircular evaluators first, and the efficient implementation later. Within a few tweaks, you can change your language to a logic programming language like Prolog, or switch from lexical scoping to dynamic scoping. This is power. And it isn't possible in most other programming languages. SICP was recently ported to Javascript, and it's an amazing conversion, but there's an extra step for parsing the source text which turns it into something that doesn't look like javascript anymore, whereas a lispy evaluator looks just like lisp.
Again, this is a primer. Showing off that you can do such a thing in 30 lines of code is something that few primers which are less than 30 pages would dare to do. It's possible to demonstrate in lisp/scheme partly because of lisp's language choices. And it's hopefully useful: I know when I wrote my first metacircular evaluator at the end of reading The Little Schemer, it demystified programming languages for me in a huge way. I hope a bit of that demystification shows up here for others too.
But does it create a good springboard for language design?
Depends on what you mean by language design. The interesting parts of modern language design, imo, is around type systems, invariants that the compiler manages, concurrency models, verification, memory models, etc.
The 30 lines or so just demonstrates on a very high level how you walk a tree. Sure, it's a good demonstration, but if you handed those 30 lines and their accompanying explanation to an intro undergrad class they would still have very little idea about how to go about building interpreters beyond a high-level idea of recursively evaluating subtrees, which I would argue is probably the least interesting part about building interpreters. It's a foundational concept, yes, but not much beyond that.
In my mind a good springboard for language design would be a fast tour through a bunch of interesting languages, of which scheme would be one of many. Haskell, Rust, C, Scheme, Erlang, Smalltalk, OCaml, etc all combined would be a wonderful exploration of both the history and major debates around how programmers write and think about code.
A good springboard around the implementation of languages would be to actually go through and build an interpreter for scheme in C. This can cover lexing, a simple recursive descent parser, tree-walking interpreter, mark-and-sweep GC, TCO detection, CPS transformations, etc.
The natural follow-up is then building the mid-backend targeting a bytecode VM. This will also include the major code analysis areas like tree-shaking, data-flow analysis, dependency analysis, etc. Targeting a real ISA is less interesting imo because at that point you're dealing more with the peculiarities with x64/ARM/whatever than with general code analysis techniques, but there's still valuable lessons to be learnt here.
Anyways, all the long tangent to say that tree-walking interpreters are such a small part of language design and implementation that I personally don't see the value in talking about it too much. Yes, it's elegant, yes, it's fundamental, but the concept is simple and not really that interesting imo.
The 30 lines or so just demonstrates on a very high level how you walk a tree. Sure, it's a good demonstration, but if you handed those 30 lines and their accompanying explanation to an intro undergrad class they would still have very little idea about how to go about building interpreters beyond a high-level idea of recursively evaluating subtrees, which I would argue is probably the least interesting part about building interpreters. It's a foundational concept, yes, but not much beyond that.
In my mind a good springboard for language design would be a fast tour through a bunch of interesting languages, of which scheme would be one of many. Haskell, Rust, C, Scheme, Erlang, Smalltalk, OCaml, etc all combined would be a wonderful exploration of both the history and major debates around how programmers write and think about code.
A good springboard around the implementation of languages would be to actually go through and build an interpreter for scheme in C. This can cover lexing, a simple recursive descent parser, tree-walking interpreter, mark-and-sweep GC, TCO detection, CPS transformations, etc.
The natural follow-up is then building the mid-backend targeting a bytecode VM. This will also include the major code analysis areas like tree-shaking, data-flow analysis, dependency analysis, etc. Targeting a real ISA is less interesting imo because at that point you're dealing more with the peculiarities with x64/ARM/whatever than with general code analysis techniques, but there's still valuable lessons to be learnt here.
Anyways, all the long tangent to say that tree-walking interpreters are such a small part of language design and implementation that I personally don't see the value in talking about it too much. Yes, it's elegant, yes, it's fundamental, but the concept is simple and not really that interesting imo.
A tree walking intrepreter can be an excellent way to prototype type systems, concurrency models, verification, etc.
Again, this is a tutorial, for newcomers, which happens to include a tree walking interpreter. I think you've pushed the goalpost pretty far back just because a reasonably interesting one was hit at all.
Again, this is a tutorial, for newcomers, which happens to include a tree walking interpreter. I think you've pushed the goalpost pretty far back just because a reasonably interesting one was hit at all.
Great read! The Scheme in Scheme section was really fun. Always enjoy Christine's writing.
[deleted]
Going through Dr Brian Harvey's CS 61A - so this is well timed, thank you for sharing.
I'm glad it could be helpful!
I love seeing pages generated by org-mode.
Love this guide!