1 Meta-circular what?
The idea for this workshop comes from the classic book Structure and Interpretation of Computer Programs (SICP). It is a good book, you should read it!
1.1 Programming languages and evaluators
A programming language is a language with a certain syntax and given rules, that makes you able to write programs that hopefully do what you expect them do do.
There are different strategies for how an implementation of a programming language executes programs. One approach is to make an evaluator. An evaluator (or interpreter) for a language is a program that rather directly executes expressions written in that language. In order to execute the program, the evaluator needs to parse the expressions to something meaningful for the evaluator, and then evalute the expressions.
When making a new language we can implement an evaluator in more or less any kind of language, but we will typically have to spend quite some time working on lexing and parsing before we have something meaningful or fun. We will use a subset of Racket’s syntax for our language, and we will implement the evaluator in Racket. Reusing bits of our “host language” like that is what we do when we’re making meta-circular evaluator.
Is fun.
It can be easier to modify and experiment with a tiny language we have made ourselves. Easier to do things like, changing the evaluation order of things so that it’s more lazier, or, as we will do in this workshop, add support for “nondeterministic” computaion.
1.2 amb and logic programming
The way we will make Racket nondeterministic is by extending it with the form amb, which takes multiple expressions and returns one of them, and with require, which will allow us to specify constraints that must be satisfied. With those extensions we can write programs where the evaluator must search for solutions by choosing different values for the different amb-expressions.
This is a step towards logic programming where a problem is defined in terms of facts or rules, that might result in more than one answer. Unknown values are represented by variables, and unification is used for solving the "equations" and determine the valid values.
1.3 Outline
In this workshop we will start with a simple calculator evaluator, which allows us to calculate the value of expressions with the four basic operators +, -, * and /. And then gradually, through several steps, extend it until we have our nondeterministic evaluator amb.
To begin with we will expand the calculator into a “normal,” but minimal and lispy, functional programming language. Mostly dealing with variables and functions: Lookup in the environment, Definitions, Functions.
Starting with Continuation-passing style, we add the things we need for Ambiguousness. Booleans can be added kind of whenever, only we need them before moving Towards zebras, our ultimate goal.
Not everything is new to everyone. It is possible to skip to where things get interesting. Every step has a corresponding Racket file that can be used as a starting point.
1.4 Goals for the workshop
Our goals for this workshop is that you hopefully learn something new about
The Racket programming language
How evaluators work
Continuation-passing style
Logic programming
Get inspiration and new ideas
Have fun!