8 ms·

A Scheme Primer

164 points by signa11 4y ago

smcn 4y ago
Great read! The Scheme in Scheme section was really fun. Always enjoy Christine's writing.
nonrandomstring 4y ago
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.
- paroneayea 4y 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 4y ago
  I had no idea that's where 'primer' came from!
  - CRConrad 4y 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 https://en.wikipedia.org/wiki/Primer_%28textbook%29 (Then again, maybe your comment was just a way of saying "ISWYDT!" to the GP?)
Hammershaft 4y 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.
- agumonkey 4y 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 4y 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.
    - agumonkey 4y ago
      true, the middle ground ~dsl approach is probably how to do thins in lisps and in general but .. maybe I'm lacking maturity still.
singaporecode 4y ago
Love this guide!
Syzygies 4y 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 4y ago
  Clojure is derived from Scheme and supports parallel programming.
  - sigzero 4y ago
    Clojure is a dialect of Lisp according to its website.
    - SomeHacker44 4y ago
      ...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.
    - bmitc 4y ago
      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.
      - agumonkey 4y ago
        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
    - 4y ago
deleted 4y ago
[deleted]
crims0n 4y ago
Going through Dr Brian Harvey's CS 61A - so this is well timed, thank you for sharing.
- paroneayea 4y ago
  I'm glad it could be helpful!
tmm84 4y 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.
newaccount2021 4y ago
e63f67dd-065b 4y 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 4y ago
  But does it create a good springboard for language design?
  - e63f67dd-065b 4y 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.
spapas82 4y ago
The little schemer book https://mitpress.mit.edu/books/little-schemer-fourth-edition 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 https://github.com/spapas/little-schemer Unfortunately, I was never able to understand the Y combinator chapter :(
- pmoriarty 4y ago
  I found the book's tones to be insufferably annoying.
- panzerklein 4y 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_schemer/little_schemer.lisp https://github.com/tsumo/solutions/blob/master/little_scheme...
nesarkvechnep 4y ago
I love seeing pages generated by org-mode.

164 points by signa11 4y ago

smcn 4y 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.

paroneayea 4y 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 4y ago
I had no idea that's where 'primer' came from!
- CRConrad 4y 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 https://en.wikipedia.org/wiki/Primer_%28textbook%29 (Then again, maybe your comment was just a way of saying "ISWYDT!" to the GP?)

Hammershaft 4y 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.

agumonkey 4y 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 4y 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.
  - agumonkey 4y ago
    true, the middle ground ~dsl approach is probably how to do thins in lisps and in general but .. maybe I'm lacking maturity still.

singaporecode 4y ago

Love this guide!

Syzygies 4y 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 4y ago
Clojure is derived from Scheme and supports parallel programming.
- sigzero 4y ago
  Clojure is a dialect of Lisp according to its website.
  - SomeHacker44 4y ago
    ...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.
  - bmitc 4y ago
    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.
    - agumonkey 4y ago
      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
  - 4y ago

deleted 4y ago

[deleted]

crims0n 4y ago

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

paroneayea 4y ago
I'm glad it could be helpful!

tmm84 4y 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.

newaccount2021 4y ago

e63f67dd-065b 4y 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 4y ago
But does it create a good springboard for language design?
- e63f67dd-065b 4y 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.

spapas82 4y ago

The little schemer book https://mitpress.mit.edu/books/little-schemer-fourth-edition 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 https://github.com/spapas/little-schemer Unfortunately, I was never able to understand the Y combinator chapter :(

pmoriarty 4y ago
I found the book's tones to be insufferably annoying.
panzerklein 4y 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_schemer/little_schemer.lisp https://github.com/tsumo/solutions/blob/master/little_scheme...

nesarkvechnep 4y ago

I love seeing pages generated by org-mode.