TL;DR: Download Racket, run plt-r6rs my-file.scm
. Bookmark this book and check it when you have questions.
Scheme is an old programming language, hailing from the mid-seventies. Its hallmark is minimalism - there really isn't that much language here. That should not be confused with expressive power - you can use Scheme to code up anything you currently write in your favourite language.
However, this minimalism makes it specifically suited towards academic study. The language gets out of the way and lets you focus on the actual logic.
Some people who took the traditional CS college route were probably exposed to this tool as part of your curriculum. Not all curricula use it, though - mine doesn't - and self-learners might not stumble across it. I'm of the opinion that you're missing out on a perfectly suited tool for studying algorithms and programming languages. Scheme is a great language for talking about computation itself, almost as a formal notation. There's no noise there to distract you - it's just you and your algorithms.
Here's a common example. This is how one (specifically me) might code up Euclid's algorithm for finding the greatest common divisor of two numbers in C:
// euclid.c
#include <stdio.h>
/**Calculate the greatest common divisor of positive integers m and n.
* Returns -1 on error
*/
int gcd(int,int);
int main(void)
{
int m = 119, n = 544, res;
res = gcd(m,n);
printf("%d", res);
return 0;
}
int gcd(int dividend, int divisor)
{
int m = dividend, n = divisor;
// Out of bounds
if (n <= 0 || m <= 0)
return -1;
for (;;)
{
// 1. Let `r` be the remainder of diving `m / n`.
int r = m % n;
// 2. If `r == 0`, complete. Return `n`.
if (r == 0)
return n;
// 3. `m <- n`, `n <- r`, goto 1.
m = n;
n = r;
}
}
C is a good language for algorithmic study for a similar reason - it's a small language. There is not a ton of syntactic noise, and even less implicit magic - the programmer bears the brunt of the burden when it comes to telling the computer what you need. This limitation isn't actually a limitation at all - you're completely in the driver's seat, and when studying and optimizing algorithms to build understanding, that's exactly what you want.
However, it's still a little bit noisy. What's <stdio.h>
? What's "%d"
? Why does it say int
everywhere?
Here's an implementation of the same algorithm in Scheme:
; euclid.scm
(import (rnrs))
(define (gcd m n)
(if (and (>= m 0) (>= n 0))
(cond [(= n 0) m]
[else (gcd n (mod m n))])
(- 1)))
(display (gcd 119 544))
That's a lot more concise! You get to code your syntax tree directly in tree form.
To define a binding, you use define
:
(define my-name "Ben")
(display my-name)
This also works for functions, and the above snippet is using a shorthand for this. Every function in Scheme is actually an anonymous lambda that you are welcome to create a binding for, and because that's such a common operation we can use this syntactic sugar. Without it, this program looks like this:
(define gcd
(lambda (m n)
(if (and (>= m 0) (>= n 0))
(cond [(= n 0) m]
[else (gcd n (mod m n))])
(- 1))))
The function itself is an anonymous lambda for which we define a binding gcd
. When you use the shorter (define (gcd m n) (...))
, this is actually what happens.
This regularity extends to all parts of the language. A function call is a list wrapped in parens with the function itself in first position:
(= n 0) ; n == 0
(mod m n) ; n % m
Instead of condA && condB
, we use (and condA condB)
. This nearly entirely removes ambiguity - just follow the paren nesting and you will be able to trace the logic. The if
expression looks like this:
(if predicate onTrue onFalse)
You can replace all three arguments with the actual forms you need. If your code starts getting too convoluted, you can either define
blocks outside of your function, or use let
to create a local binding. The cond
statement is a shorthand for an if
with multiple arms, like a switch
.
One gotcha is that you can't even write a negative number directly: -1
won't work in the failure arm. With only one argument, -
means "negate" - so (- 3 2)
subtracts, yielding 1
, and (- 1)
negates, yielding -1
.
Notably, this version is written in recursive fashion, whereas our C was imperative. Scheme is standardized to support proper tail recursion, so while this function is syntactically recursive, because the recursion occurs in tail position it will actually be executed more like an imperative loop, reusing the stack frame and swapping the operands.
You are able to write any imperative algorithm you come across in a recursive fashion, though they may not always be similarly convenient. If it's not clear immediately how you might do so for an algorithm you're working with, you might want to break out some Scheme and try it!
The standard I'm using is called R6RS
, or more generally RNRS
to refer to version-agnostic Scheme. Much like C++ or ECMAScript, Scheme exists as a standard only, and many competing implementations exist. Somewhat frustratingly these implementations actually diverge somewhat significantly from each other, but the core language will be consistent - that's the whole point of a standard! The R6RS standard can be found here.
There's actually an R7RS scheme now, too, but don't worry too much about it unless you start getting serious about Scheme work. There's apparently some contention in the community about minimalism and values and whatever - you know, politics. I'm not here for politics, I'm here for algorithms. R6RS is completely fine.
I've found the easiest way to start using Scheme is via Racket. Racket is a system that is much more powerful than just RNRS Scheme, but supports a feature called #lang
directives that let you restrict Racket to specific standards like this. You can place this #!r6rs
directive directly in your file and use the standard Racket build tooling, but Racket also ships with a CLI tool called plt-r6rs
. You can invoke this directly on a scheme file, no #lang
required:
$ plt-r6rs euclid.scm
17
More information about using R6RS via Racket can be found here. Here's the Scheme book again, and the R6RS standard again. Those links should get you up and running for your own experimentation. If you're itching for the next level of Scheme enlightenment, RUN (do not walk) directly to The Little Schemer and make yourself a sandwich.
Have fun!
Photo by Chinh Le Duc on Unsplash
Top comments (23)
Dan Friedman was one of my professors!! 🤯 Seeing these books mentioned brings back lots of memories...
(mostly (of ('parentheses)))
I bet @daniel13rady would enjoy this post 😊
Probably so! Will read soon 😄
I used to think that scheme is locked down in academia, but it turns out I was wrong about that. You should check out GUILE, the official extension language for GNU, and turns out it's a scheme dialect . There's a whole ecosystem written in it like GUIX, shepherd(an alternative init system) and a bunch of other cool stuff. For books to read, I'd strongly recommond Structure and Interpretation of Computer Programs(SICP).
I've only come across GUILE in the context of GUIX, when I was deep-diving through NixOS. Do you use Guile or Guix?
I've been using GUILE for a while(wrt prototyping random things) now. I want to setup GUIX on a spare machine. I run FreeBSD so unfortunately alot of linux tooling doesn't really work out of the box. I want to create a monitoring tool in that ecosystem.
Update. I've been using GUIX now for the past 3 months and I've kinda even got my hands dirty hacking on some things in that ecosystem like: gitlab.inria.fr/guix-hpc/guix-past
That brings back memories. We used Scheme in university for the Functional Programming course back in 1994.
No highlighting of opening and closing parentheses in editors. That was fun.
Highlighting is for the weak.
I program like a man. I use "copy con program.exe". :)
(((()(()()()))))
!!!I had a lot of fun with Scheme / Racket at school, good times 😁
I can't remember how, but we plugged in a way to visualize the results of our programs and I even was able to animate the thing! My professor's mind was blown and I started realizing I liked "the front end" side of my projects more than anything 😛
Can't quite say the same about Prolog though.. that broke my brain.
I've created bookmarklet that runs Scheme REPL on any website, you can use it on book or this site. The Scheme implementation is LIPS: my Scheme interpreter written in JavaScript.
Note that
mod
is not in R7RS standard function, so it's not defined in LIPS (it may be in R6RS but no one is using it). In order to run your example you need(define mod modulo)
or changemod
in thegdc
function definition.I don't understand how anyone can recommend book like "The Little Schemer". I've got 3 books in the series without looking inside and they were worse programming books I've ever seen.
I can only see benefit if someone is learning scheme elsewhere and this is just exercises book. Since the structure of that book doesn't make any sense to me if you want to learn on your own. For me the those books were useless.
Well, conversely, I don't understand how anyone can not get a lot out of this series, I devoured every entry as a self-learner. No, they were not the only material I used to learn Scheme and recursion, but but I've never learned any concept from just one resource. It's an unorthodox format, I agree. But everyone has a different learning style. I'm sorry to hear it didn't work for you, but clearly it's worked for a lot of other people. i'm glad there's a massive range of learning materials for self-learners, so if one recommendation doesn't sit well, there's always more to try.
I would love to see experience from someone that has 0 knowledge and start with this book. And this is what people recommend as first book. I can understand if someone want to use this book when she already know Scheme. But the target for this book are complete newbies, which for them I would never recommend it.
For me personally best book about Scheme is Sketchy Scheme by Nils M Holm.
I recognize it as a "Lisp", right? What about Clojure, how does Scheme compare to Clojure? Clojure is/was sort of getting popular and creating a community ...
Yup! It's the oldest of the commonly used Lisp families, alongside Common Lisp and Clojure. I think the rough analogy goes like this:
Scheme : C
Common Lisp : C++
Clojure : Java
Of these, Scheme and Clojure are "functional" languages, or at least functional-first, and Common Lisp is truly multi-paradigm. It's very "kitchen sink", it has a massive amount of features, like C++.
Clojure is designed specifically with interop in mind. It can be used seamlessly as a hosted language targetting either JVM bytecode or JavaScript via the Closure Compiler. It also ships with a set of persistent data structures, and Clojure code is highly suited for concurrency and immutability. It's partially a response to the relatively stagnant development models of Scheme and Common Lisp, bringing the Lisp sensibility to a more pragmatic type of tool.
In a sentence, Clojure has a focus on actually building large, robust, reliable software, whereas Scheme is primarily an academic tool focused studying abstract concepts.
Emacs Lisp gets a shout-out as the fourth "category" still in wide use, but I don't believe it really has a life outside of Emacs itself.
The Little Schemer is one of my favorite books, period, not just technical. I'm also interested in The Little Typer but I'm not sure I'm smart enough.
I wrote a much, much more basic how to here: dev.to/jamesliudotcc/use-dr-racket.... It is more for someone with this problem: "I got suggested The Little Schemer and the code won't run."
Always good to see more Lisp and Scheme code. Hopefully you can use Racket for production code at your workplace!
Workplace at all first, racket second ;)