A Scheme Primer

https://spritely.institute/static/papers/scheme-primer.html

by signa11 • 4 years ago

164 32 4 years ago

smcn• 4 years ago

Great read! The Scheme in Scheme section was really fun. Always enjoy Christine's writing.

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.

paroneayea4• 4 years ago

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! :)

anitil• 4 years ago

I had no idea that's where 'primer' came from!

CRConrad• 4 years ago

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?)

Hammershaft• 4 years ago

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.

agumonkey3• 4 years ago

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).

bandrami• 4 years ago

I was hitting that wall for a while until I realized that was scheme telling me to write multiple small programs for the task in question.

singaporecode• 4 years ago

Love this guide!

Syzygies• 4 years ago

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.

timbit42• 4 years ago

Clojure is derived from Scheme and supports parallel programming.

sigzero• 4 years ago

Clojure is a dialect of Lisp according to its website.

dannyobrien2• 4 years ago

Do you mean like fibers ( https://github.com/wingo/fibers ), or something beyond that?

bjoli• 4 years ago

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.

crims0n• 4 years ago

Going through Dr Brian Harvey's CS 61A - so this is well timed, thank you for sharing.

paroneayea4• 4 years ago

I'm glad it could be helpful!

tmm84• 4 years ago

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.

e63f67dd-065b2• 4 years ago

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.

dbtc• 4 years ago

But does it create a good springboard for language design?

e63f67dd-065b2• 4 years ago

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.

paroneayea4• 4 years ago

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.

spapas82• 4 years ago

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 :(

pmoriarty• 4 years ago

I found the book's tones to be insufferably annoying.

panzerklein• 4 years ago

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...

nesarkvechnep• 4 years ago

I love seeing pages generated by org-mode.

A Scheme Primer

Related Stories