Full message

11show conditionals
ifmaxminfactorial
14introduce pairs
conscarcdr
15introduce mutable cells
make-cellset!get!
16introduce lists
listundefinedheadtaillist-lengthlist-reffunction?equallist=prependpairfirstsecond
19some more list functions
list:findlastexcept-lastlist:reverseappendselect-match
20introduce pi and e
minusfracabswithinrangeevenodddecimalepipower:10pow:intpowexp
25some pure lambda calculus definitions - optional
pure:ifpure:truepure:falsepure:conspure:carpure:cdrpure:0pure:1pure:2pure:nextpure:+pure:*pure:prevpure:=:0fixed-pointpure:int:get
29introduce sets and set membership
elementset:<=set:=set:0
30introduce graph structures
graph:makeexists:graph:2exists:graph:2:list
32introduce environment/hashmap structure
hash-addhash-refhash-nullhash-defaultmake-hash
34introduce turing machine model
tape:dotape:maketape:resultdemo:tape:function:+:1
42introduce the elements
protonelectronneutronmasshydrogenheliumcarbonnitrogenoxygenhydrogen:2oxygen:2oxygen:3waternitrogen:2ammoniamethaneethane
44simulating unless gates
unlessmake-matrixmatrix-setmatrix-getsimulate-unlessbit-getmake-imageimage-getimage-heightimage-widthdistill-circuit
#   Author: Paul Fitzpatrick, paulfitz@alum.mit.edu
#   Copyright (c) 2018 Paul Fitzpatrick
#
#   This file is part of CosmicOS.
#
#   CosmicOS is free software; you can redistribute it and/or modify
#   it under the terms of the GNU General Public License as published by
#   the Free Software Foundation; either version 2 of the License, or
#   (at your option) any later version.
#
#   CosmicOS is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with CosmicOS; if not, write to the Free Software
#   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#

0. introduce numbers (in unary notation)

Here we count up from zero, go through some primes, that sort of thing. Just like in the movies! There is some syntax around the numbers, and a structure to the “lesson,” but it will be fine for the listener to ignore all that for now. Hopefully what they will pick up on is:

  • There are some repeating patterns.
  • Between those patterns, there’s a specific short unit repeating a varying number of times (we count in unary).
  • The number of times it varies smells like math.

We’ll get to a more compact representation of numbers later, once we’ve established the basics.


intro unary;

intro is;

intro int;

is int | unary 0;

is int | unary 1 0;

is int | unary 1 1 0;

is int | unary 1 1 1 0;

is int | unary 1 1 1 1 0;

is int | unary 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is int | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

intro square;

is square | unary 0;

is square | unary 1 0;

is square | unary 1 1 1 1 0;

is square | unary 1 1 1 1 1 1 1 1 1 0;

is square | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is square | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

intro prime;

is prime | unary 1 1 0;

is prime | unary 1 1 1 0;

is prime | unary 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

is prime | unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0;

1. introduce equality and inequality of numbers

We’ve hopefully cued our listeners to be looking for mathematical patterns. So let’s give them some more. It doesn’t matter so much what patterns we give, as long as they are clear, and that there are several of them. Eventually we’ll want the listener to start turning things around, and use the parts of the message they understand (the mathematical patterns) to learn something about the parts they don’t (the message structure and syntax).

Let’s take a shot at introducing ways of comparing numbers. No doubt we’re revealing a feudal, reductive mindset in which all things must be ranked in a hierachy. ¯\_(ツ)_/¯.

Equality is introduced by a series of true statements of the form X = X (the syntax is a little different than regular math, more like = X X, but that isn’t important yet). The listener will hopefully discern a number getting repeated twice within the “sentence” structure they’ve been seeing, but won’t be sure yet what we are driving at until we introduce non-equality and contrast with it.


intro =;

= (unary 1 0) (unary 1 0);

= (unary 1 1 0) (unary 1 1 0);

= (unary 1 1 1 0) (unary 1 1 1 0);

= (unary 1 1 1 1 0) (unary 1 1 1 1 0);

= (unary 1 1 1 1 1 0) (unary 1 1 1 1 1 0);

= (unary 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 0);

= (unary 1 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 1 0);

= (unary 1 1 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 1 1 0);

= (unary 1 0) (unary 1 0);

= (unary 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 0);

= (unary 1 1 0) (unary 1 1 0);

Now introduce symbols for ‘greater than’ and ‘less than,’ and contrast with equality. Hopefully the listener will start to understand what part of the sentences are numbers, what part is a function of the relationship between the numbers, and what parts are just meaningless (for now) scaffolding around all that. There’s an ambiguity between the ‘greater than’ and ‘less than’ symbols, depending on how you interpret the sentences, but it doesn’t matter yet.


intro >;

intro <;

= (unary 1 0) (unary 1 0);

< (unary 1 0) (unary 1 1 0);

< (unary 1 0) (unary 1 1 1 0);

< (unary 1 0) (unary 1 1 1 1 0);

> (unary 1 1 0) (unary 1 0);

= (unary 1 1 0) (unary 1 1 0);

< (unary 1 1 0) (unary 1 1 1 0);

< (unary 1 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 0) (unary 1 0);

> (unary 1 1 1 0) (unary 1 1 0);

= (unary 1 1 1 0) (unary 1 1 1 0);

< (unary 1 1 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 1 0) (unary 1 0);

> (unary 1 1 1 1 0) (unary 1 1 0);

> (unary 1 1 1 1 0) (unary 1 1 1 0);

= (unary 1 1 1 1 0) (unary 1 1 1 1 0);

Add some random examples.


> (unary 1 1 1 1 0) (unary 1 1 1 0);

> (unary 1 1 1 0) (unary 0);

> (unary 1 0) (unary 0);

> (unary 1 1 1 1 1 1 1 1 0) (unary 0);

> (unary 1 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 0);

> (unary 1 1 1 1 1 1 0) (unary 1 1 0);

> (unary 1 1 1 1 1 0) (unary 0);

> (unary 1 1 1 1 1 1 1 1 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 1 1 0) (unary 1 0);

> (unary 1 1 0) (unary 0);

> (unary 1 1 1 0) (unary 1 0);

< (unary 1 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 1 1 1 0);

< (unary 1 1 1 0) (unary 1 1 1 1 1 1 0);

< (unary 1 1 0) (unary 1 1 1 0);

< (unary 1 1 0) (unary 1 1 1 1 0);

< (unary 0) (unary 1 0);

< (unary 0) (unary 1 1 1 1 1 1 1 1 1 1 0);

< (unary 0) (unary 1 1 1 0);

< (unary 0) (unary 1 1 1 1 0);

< (unary 1 1 1 1 0) (unary 1 1 1 1 1 1 0);

< (unary 0) (unary 1 1 0);

< (unary 1 0) (unary 1 1 1 1 1 1 1 1 0);

Even more random examples. We shouldn’t be shy about piling on examples at this early stage of the message. Even just the repetition of the sentence structure with many small variations could help guide the listener at a more fundamental level than what we’re ostensibly trying to communicate here.


= (unary 1 1 1 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 1 0) (unary 1 1 0);

< (unary 1 0) (unary 1 1 0);

> (unary 1 1 1 0) (unary 1 1 0);

> (unary 1 1 1 1 0) (unary 0);

> (unary 1 1 1 0) (unary 1 0);

< (unary 0) (unary 1 1 0);

> (unary 1 1 1 0) (unary 0);

> (unary 1 1 0) (unary 1 0);

< (unary 1 1 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 0) (unary 1 1 0);

> (unary 1 1 1 1 0) (unary 1 1 0);

= (unary 1 1 0) (unary 1 1 0);

< (unary 0) (unary 1 1 0);

> (unary 1 1 1 1 0) (unary 0);

< (unary 1 1 0) (unary 1 1 1 1 0);

< (unary 1 0) (unary 1 1 1 1 0);

> (unary 1 1 1 1 0) (unary 1 1 1 0);

< (unary 0) (unary 1 1 1 1 0);

< (unary 1 1 0) (unary 1 1 1 1 0);

< (unary 1 1 0) (unary 1 1 1 1 0);

2. introduce logical negation

At this point, the listener can find numbers in our sentences, and has some idea of symbols related to equality and inequality. But the structure of the sentences remains a mystery. Let’s introduce more math, so that we can show different sentence structures. First, let’s introduce logical negation. We construct some sentences the listener should know are wrong, and put “not” in front of them.


intro not;

Show an equality, then negate two conflicting inequalities.


= (unary  0) (unary  0);

not | < (unary  0) (unary  0);

not | > (unary  0) (unary  0);

= (unary  1 1 1 1 0) (unary  1 1 1 1 0);

not | < (unary  1 1 1 1 0) (unary  1 1 1 1 0);

not | > (unary  1 1 1 1 0) (unary  1 1 1 1 0);

= (unary  1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

not | < (unary  1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

not | > (unary  1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

= (unary  1 1 0) (unary  1 1 0);

not | < (unary  1 1 0) (unary  1 1 0);

not | > (unary  1 1 0) (unary  1 1 0);

= (unary  1 1 1 0) (unary  1 1 1 0);

not | < (unary  1 1 1 0) (unary  1 1 1 0);

not | > (unary  1 1 1 0) (unary  1 1 1 0);

Show an inequality, then two negations.


< (unary  1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 0);

not | = (unary  1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 0);

not | > (unary  1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 0);

< (unary  1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

not | = (unary  1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

not | > (unary  1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

< (unary  1 0) (unary  1 1 0);

not | = (unary  1 0) (unary  1 1 0);

not | > (unary  1 0) (unary  1 1 0);

< (unary  0) (unary  1 1 1 1 1 0);

not | = (unary  0) (unary  1 1 1 1 1 0);

not | > (unary  0) (unary  1 1 1 1 1 0);

< (unary  1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

not | = (unary  1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

not | > (unary  1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

Show another batch of inequalities with negations.


> (unary  1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

not | = (unary  1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

not | < (unary  1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 0);

> (unary  1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 0);

not | = (unary  1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 0);

not | < (unary  1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 0);

> (unary  1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

not | = (unary  1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

not | < (unary  1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 0);

> (unary  1 1 1 1 0) (unary  0);

not | = (unary  1 1 1 1 0) (unary  0);

not | < (unary  1 1 1 1 0) (unary  0);

> (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 0);

not | = (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 0);

not | < (unary  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0) (unary  1 1 1 1 1 1 1 1 1 0);

3. introduce addition

Let’s introduce some arithmetic, to show off still more sentence structure. We show sentences of the mathematical form X = Y + Z, which in our message look like = X | + Y Z. From this, and the negation lesson, the listener will hopefully start picking up on how to chain operations.

If the listener didn’t already have a pretty clear idea of what = is, then these sentences could just as easily be interpreted as being about subtraction. Even having an idea of =, syntax is still fuzzy enough that this lesson may not be unambiguous by itself.


intro +;

= (unary  1 1 0) | + (unary  0) (unary  1 1 0);

= (unary  1 1 1 1 1 0) | + (unary  1 1 1 1 0) (unary  1 0);

= (unary  1 1 0) | + (unary  1 1 0) (unary  0);

= (unary  1 1 1 1 0) | + (unary  0) (unary  1 1 1 1 0);

= (unary  1 1 1 1 0) | + (unary  1 1 1 0) (unary  1 0);

= (unary  1 1 1 0) | + (unary  1 0) (unary  1 1 0);

= (unary  0) | + (unary  0) (unary  0);

= (unary  1 1 1 1 0) | + (unary  1 1 1 1 0) (unary  0);

= (unary  1 1 1 0) | + (unary  1 1 0) (unary  1 0);

= (unary  1 1 1 1 0) | + (unary  1 1 1 1 0) (unary  0);

4. introduce subtraction

Introduce subtraction via = X | - Y Z sentences. Until syntax is fully understood, an ambiguity may remain between this and addition.


intro -;

= (unary  0) | - (unary  1 1 0) (unary  1 1 0);

= (unary  1 1 1 1 0) | - (unary  1 1 1 1 1 0) (unary  1 0);

= (unary  1 1 0) | - (unary  1 1 0) (unary  0);

= (unary  0) | - (unary  1 1 1 1 0) (unary  1 1 1 1 0);

= (unary  1 1 1 0) | - (unary  1 1 1 1 0) (unary  1 0);

= (unary  1 0) | - (unary  1 1 1 0) (unary  1 1 0);

= (unary  0) | - (unary  0) (unary  0);

= (unary  1 1 1 1 0) | - (unary  1 1 1 1 0) (unary  0);

= (unary  1 1 0) | - (unary  1 1 1 0) (unary  1 0);

= (unary  1 1 1 1 0) | - (unary  1 1 1 1 0) (unary  0);

5. introduce multiplication

While we’re at it, let’s introduce multiplication with = X | * Y Z sentences. As for addition and subtraction, there will be some ambiguity as to whether we are presenting multiplication or division here, until syntax is clearly understood.


intro *;

= (unary  0) | * (unary  0) (unary  0);

= (unary  0) | * (unary  0) (unary  1 0);

= (unary  0) | * (unary  0) (unary  1 1 0);

= (unary  0) | * (unary  0) (unary  1 1 1 0);

= (unary  0) | * (unary  1 0) (unary  0);

= (unary  1 0) | * (unary  1 0) (unary  1 0);

= (unary  1 1 0) | * (unary  1 0) (unary  1 1 0);

= (unary  1 1 1 0) | * (unary  1 0) (unary  1 1 1 0);

= (unary  0) | * (unary  1 1 0) (unary  0);

= (unary  1 1 0) | * (unary  1 1 0) (unary  1 0);

= (unary  1 1 1 1 0) | * (unary  1 1 0) (unary  1 1 0);

= (unary  1 1 1 1 1 1 0) | * (unary  1 1 0) (unary  1 1 1 0);

= (unary  0) | * (unary  1 1 1 0) (unary  0);

= (unary  1 1 1 0) | * (unary  1 1 1 0) (unary  1 0);

= (unary  1 1 1 1 1 1 0) | * (unary  1 1 1 0) (unary  1 1 0);

= (unary  1 1 1 1 1 1 1 1 1 0) | * (unary  1 1 1 0) (unary  1 1 1 0);

= (unary  0) | * (unary  0) (unary  1 0);

= (unary  1 1 1 0) | * (unary  1 1 1 0) (unary  1 0);

= (unary  0) | * (unary  1 1 0) (unary  0);

= (unary  0) | * (unary  0) (unary  1 1 1 0);

= (unary  1 1 1 0) | * (unary  1 1 1 0) (unary  1 0);

= (unary  1 1 0) | * (unary  1 0) (unary  1 1 0);

= (unary  0) | * (unary  0) (unary  0);

= (unary  0) | * (unary  1 1 1 0) (unary  0);

= (unary  0) | * (unary  1 1 0) (unary  0);

= (unary  0) | * (unary  1 1 1 0) (unary  0);

6. introduce non-unary representation of numbers

Switch from unary numbers to another representation. The best representation will depend on the details of how the message is being transmitted, and the rest of the message doesn’t depend on that choice for correctness (though the choice will have implications for how easy the message will be to interpret). As a base-line, imagine we use a binary representation.

It isn’t important for the listener to understand, but it might be worth explaining at this point how the unary representation worked. In fact there’s no special syntax used, just three objects:

  • The number 0.
  • The number 1.
  • A function (called unary in English) that takes a value and:
    • If passed 0, the function returns 0
    • If passed 1, the function returns another function, just like itself, except with any ultimate return value increased by 1.

Using syntax defined later in the message, unary could be defined as:

@ unary-v | ? v | ? x | if (= $x 0) $v (unary-v | + $v 1)
@ unary | unary-v 0

If you know Lisp/Scheme/etc, just read @ as define, ? as lambda, and | as opening a parenthesis that gets closed at the end of the statement.

Anyway, all of this is a digression, but it is worth knowing that as much as possible the message is built from itself, so that in the end everything dovetails nicely.


= 0 (unary 0);

= 1 (unary 1 0);

= 2 (unary 1 1 0);

= 3 (unary 1 1 1 0);

= 4 (unary 1 1 1 1 0);

= 5 (unary 1 1 1 1 1 0);

= 6 (unary 1 1 1 1 1 1 0);

= 7 (unary 1 1 1 1 1 1 1 0);

= 8 (unary 1 1 1 1 1 1 1 1 0);

= 9 (unary 1 1 1 1 1 1 1 1 1 0);

= 10 (unary 1 1 1 1 1 1 1 1 1 1 0);

= 11 (unary 1 1 1 1 1 1 1 1 1 1 1 0);

= 12 (unary 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 13 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 14 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 15 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 1 (unary 1 0);

= 2 (unary 1 1 0);

= 4 (unary 1 1 1 1 0);

= 8 (unary 1 1 1 1 1 1 1 1 0);

= 16 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 5 (unary 1 1 1 1 1 0);

= 14 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 2 (unary 1 1 0);

= 3 (unary 1 1 1 0);

= 0 (unary 0);

= 13 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 11 (unary 1 1 1 1 1 1 1 1 1 1 1 0);

= 1 (unary 1 0);

= 9 (unary 1 1 1 1 1 1 1 1 1 0);

= 15 (unary 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 8 (unary 1 1 1 1 1 1 1 1 0);

= 7 (unary 1 1 1 1 1 1 1 0);

= 6 (unary 1 1 1 1 1 1 0);

= 4 (unary 1 1 1 1 0);

= 12 (unary 1 1 1 1 1 1 1 1 1 1 1 1 0);

= 10 (unary 1 1 1 1 1 1 1 1 1 1 0);

= (unary 1 1 1 1 1 1 1 1 1 0) | + (unary 1 1 1 1 1 1 0) (unary 1 1 1 0);

= 9 | + 6 3;

= (unary 1 1 1 1 1 1 0) | + (unary 0) (unary 1 1 1 1 1 1 0);

= 6 | + 0 6;

= (unary 1 1 1 1 1 1 1 1 1 1 0) | + (unary 1 1 1 1 1 1 0) (unary 1 1 1 1 0);

= 10 | + 6 4;

= (unary 1 1 1 1 1 0) | + (unary 1 1 1 0) (unary 1 1 0);

= 5 | + 3 2;

= (unary 1 0) | + (unary 1 0) (unary 0);

= 1 | + 1 0;

= (unary 1 1 1 1 1 1 0) | + (unary 1 1 0) (unary 1 1 1 1 0);

= 6 | + 2 4;

= (unary 1 1 1 1 1 1 1 1 1 1 1 1 0) | + (unary 1 1 1 1 1 1 0) (unary 1 1 1 1 1 1 0);

= 12 | + 6 6;

= (unary 1 1 1 1 1 1 1 1 0) | + (unary 1 1 1 1 0) (unary 1 1 1 1 0);

= 8 | + 4 4;

= (unary 0) | * (unary 0) (unary 1 1 0);

= 0 | * 0 2;

= (unary 1 1 0) | * (unary 1 0) (unary 1 1 0);

= 2 | * 1 2;

= (unary 0) | * (unary 0) (unary 1 0);

= 0 | * 0 1;

= (unary 0) | * (unary 1 1 1 0) (unary 0);

= 0 | * 3 0;

= (unary 0) | * (unary 0) (unary 0);

= 0 | * 0 0;

= (unary 0) | * (unary 1 0) (unary 0);

= 0 | * 1 0;

= (unary 1 1 1 1 0) | * (unary 1 1 0) (unary 1 1 0);

= 4 | * 2 2;

= (unary 1 1 1 1 1 1 1 1 1 0) | * (unary 1 1 1 0) (unary 1 1 1 0);

= 9 | * 3 3;

7. show alternative groupings

We’ve advanced enough that we’re starting to have choices about how something is expressed. Let’s pause to acknowledge that, and reinforce some syntactic equivalences so the listener can be confident of them.

Parentheses play a role in grouping expressions, just like in regular math. To reduce the mental burden of tracking nesting, we use a | shortcut that means “add parentheses between this point and as far as you can go.” So for example (= 7 | + 3 4) is equivalent to (= 7 (+ 3 4)).


= 6 6;

= 6 (+ 1 5);

= 6 | + 1 5;

= 6 | + 1 (+ 4 1);

= 6 | + 1 | + 4 1;

= 6 (+ 1 5);

= (+ 3 3) (+ 1 5);

= (+ 3 (- 5 2)) (+ 1 5);

= (+ 3 | - 5 2) (+ 1 5);

= (+ 3 | - 5 2) | + 1 5;

8. show local assignment

An expression starting with assign is a way to name values for use within that expression. To use the assigned value, simply place its name at the beginning of an expression. For example, a value assigned to x can be used by writing (x). The name is entirely arbitrary, and can be just an integer.


intro assign;

assign x 1 | = (x) 1;

assign x 2 | = (x) 2;

assign x 3 | = (x) 3;

assign y 1 | = (y) 1;

assign y 2 | = (y) 2;

assign y 3 | = (y) 3;

assign x 3 | = 9 (* (x) (x));

assign x 4 | = 16 (* (x) (x));

assign z 3 | = 9 (* (z) (z));

assign z 4 | = 16 (* (z) (z));

assign x (+) | = 7 (x 4 3);

assign y (+) | = 12 (y 6 6);

assign z (+) | = 9 (z 7 2);

assign a (-) | = 1 (a 4 3);

assign b (-) | = 0 (b 6 6);

assign c (-) | = 5 (c 7 2);

assign z (*) | = 12 (z 4 3);

assign y (*) | = 36 (y 6 6);

assign x (*) | = 14 (x 7 2);

assign x (=) | x 4 4;

assign x (=) | x 4 (+ 2 2);

assign x 1 | assign y 2 | = 3 (+ (x) (y));

assign x 2 | assign y 7 | = 5 (- (y) (x));

assign x (+) | assign y 3 | = 4 (x 1 (y));

We are pretty ruthless about adding syntax to reduce parentheses. So let’s allow writing (x) as $x (or equivalent in other renderings). This and | are in fact global options for the message that you can turn off if they are not to your taste.


assign x 1 | = (x) 1;

assign x 1 | = $x 1;

assign x 4 | = 16 (* (x) (x));

assign x 4 | = 16 (* $x $x);

assign x 4 | = 16 | * $x $x;

Add more examples to give hints about scoping and other odd corners.


= 2 | assign x 1 | + $x 1;

= 1 | assign x 1 $x;

= 14 | assign x 1 14;

= 4 | assign x (assign y 3 | + 1 $y) $x;

= 4 | assign x (assign x 3 | + 1 $x) $x;

We’re ready for functions. ? starts a lambda function. Now we can have fun!


= 0 | (? x $x) 0;

= 1 | (? x $x) 1;

= 2 | (? x $x) 2;

= 3 | (? x $x) 3;

= 4 | (? x $x) 4;

= 5 | (? x $x) 5;

= 1 | (? x | + 1 $x) 0;

= 2 | (? x | + 1 $x) 1;

= 3 | (? x | + 1 $x) 2;

= 4 | (? x | + 1 $x) 3;

= 5 | (? x | + 1 $x) 4;

= 6 | (? x | + 1 $x) 5;

= 0 | (? x | * $x $x) 0;

= 1 | (? x | * $x $x) 1;

= 4 | (? x | * $x $x) 2;

= 9 | (? x | * $x $x) 3;

= 16 | (? x | * $x $x) 4;

= 25 | (? x | * $x $x) 5;

= 0 | (? y | * $y $y) 0;

= 1 | (? y | * $y $y) 1;

= 4 | (? y | * $y $y) 2;

= 9 | (? y | * $y $y) 3;

= 16 | (? y | * $y $y) 4;

= 25 | (? y | * $y $y) 5;

Emphasize the arbitrary nature of names, and hint that things we’ve learned already like addition could possibly be re-imagined as a named value.


= 0 | (? + | * $+ $+) 0;

= 1 | (? + | * $+ $+) 1;

= 4 | (? + | * $+ $+) 2;

= 9 | (? + | * $+ $+) 3;

= 16 | (? + | * $+ $+) 4;

= 25 | (? + | * $+ $+) 5;

= 0 | (? 5 | * $5 $5) 0;

= 1 | (? 5 | * $5 $5) 1;

= 4 | (? 5 | * $5 $5) 2;

= 9 | (? 5 | * $5 $5) 3;

= 16 | (? 5 | * $5 $5) 4;

= 25 | (? 5 | * $5 $5) 5;

Show that we can name functions and use them later - still within a single expression for now.


assign x (? y | * $y $y) | = 25 | x 5;

assign x (? y | + $y 1) | = 6 | x 5;

assign x (? x | + $x 1) | = 6 | x 5;

assign y (? x | + $x 1) | = 6 | y 5;

Show that we can nest functions to take multiple values.


= 52 | * 4 13;

= 52 | (? x | * $x 4) 13;

= 52 | (? x | ? y | * $x $y) 13 4;

= 53 | (? x | ? y | + 1 | * $x $y) 13 4;

assign z (? x | ? y | + 1 | * $x $y) | = 53 | z 13 4;

9. demonstrate existence of memory

We’ve set up a way to name a value within an expression. Now let’s go beyond that, and introduce a way to name a value in one sentence and use it in a later sentence. In other words, a message-level memory. After this, we’ll be able to define new symbols from existing ones, with less need for large numbers of examples.

We introduce a define symbol that works just like assign, except that it applies to the rest of the message rather than the rest of the sentence.

A sentence of the form define X Y means that $X will evaluate to Y from that point on (unless X is changed by another define).

The meaning-of-life-universe-everything symbol here is entirely arbitrary, and won’t be encoded as anything particularly meaningful in the message.


define meaning-of-life-universe-everything 39;

= 39 $meaning-of-life-universe-everything;

= $meaning-of-life-universe-everything 39;

= 49 | + 10 $meaning-of-life-universe-everything;

define meaning-of-life-universe-everything 40;

= $meaning-of-life-universe-everything 40;

= 80 | * $meaning-of-life-universe-everything 2;

define meaning-of-life-universe-everything | + 1 $meaning-of-life-universe-everything;

= $meaning-of-life-universe-everything 41;

assign x (+ 1 $meaning-of-life-universe-everything) | define meaning-of-life-universe-everything $x;

= $meaning-of-life-universe-everything 42;

Now we can start defining and naming functions. Here’s one to square an integer.


intro square;

define square | ? x | * $x $x;

= 9 | square 3;

= 81 | square 9;

= 1 | square 1;

= 4 | square 2;

= 0 | square 0;

Here’s a function to increment an integer.


intro ++;

define ++ | ? x | + $x 1;

= 4 | ++ 3;

= 10 | ++ 9;

= 2 | ++ 1;

= 3 | ++ 2;

= 1 | ++ 0;

10. introduce true and false

Now that we have functions, we could introduce some clever definitions of true, false, and conditionals, where:

  • if is ? x | ? y | ? z | x $y $z
  • true is ? y | ? z | y
  • false is ? y | ? z | z

This is a neat implementation, but maybe a bit confusing. So let’s not actually commit to a type for truth values in the message yet, but just equate them with the results of equality =.

Once we have truth values, we can introduce conditionals and build up to fun stuff.

One slightly sneaky thing we do is to code true and false as $1 and $0. This could be helpful, or confusing, I’m not sure. Nothing else in the message depends on this so it can be adjusted to taste.


intro true;

intro false;

define true | = 0 0;

define false | = 0 1;

= $true (= 2 2);

= $true (> 4 2);

= $true (= 1 1);

= $true (> 6 4);

= $true (< 3 4);

= (= 5 5) $true;

= (= 3 3) $true;

= (= 4 4) $true;

= (= 3 3) $true;

= (= 0 0) $true;

= $false (< 6 2);

= $false (< 4 2);

= $false (< 4 1);

= $false (> 0 0);

= $false (> 0 5);

= (= 3 2) $false;

= (> 2 3) $false;

= (> 4 5) $false;

= (> 2 6) $false;

= (> 1 6) $false;

= $true $true;

= $false $false;

not | = $true $false;

not | = $false $true;

= (> 4 2) (< 1 4);

= (= 3 3) (< 3 5);

= (= 0 0) (= 4 4);

= (> 6 4) (< 3 5);

= (< 5 6) (< 0 2);

= (= 5 1) (> 2 4);

= (> 4 6) (> 1 3);

= (> 2 5) (= 5 3);

= (< 2 1) (< 6 4);

= (< 6 2) (> 4 5);

not | = (> 0 1) (= 0 0);

not | = (< 6 4) (= 5 5);

not | = (= 4 2) (> 1 0);

not | = (> 5 6) (< 1 3);

not | = (> 3 6) (> 5 4);

not | = (= 2 2) (> 0 3);

not | = (> 5 2) (= 2 3);

not | = (> 4 1) (< 2 0);

not | = (= 2 2) (< 3 2);

not | = (< 0 1) (> 3 4);

11. show conditionals

Now that we spent some time looking at true and false, let’s show a way to build conditional expressions. We start with an if expression, of the form if CONDITION E1 E2, which evaluates to E1 if the CONDITION is true, otherwise E2.

If the listener is trying to map the language we are describing onto their own system of computation, it is pretty important that if be “lazy,” and completely skip evaluating the branch not taken. That should become clear fairly soon if they were to try an “eager” if.


intro if;

= 28 | if (< 3 0) 24 28;

= 27 | if (> 2 4) 29 27;

= 29 | if (= 3 1) 20 29;

= 21 | if (= 0 0) 21 26;

= 29 | if (> 5 3) 29 23;

= 26 | if (> 1 0) 26 22;

= 21 | if (= 3 3) 21 27;

= 23 | if (> 4 4) 25 23;

We can now define more interesting functions. Here’s the maximum of two integers:


intro max;

define max | ? x | ? y | if (> $x $y) $x $y;

= 0 | max 0 0;

= 1 | max 0 1;

= 2 | max 0 2;

= 1 | max 1 0;

= 1 | max 1 1;

= 2 | max 1 2;

= 2 | max 2 0;

= 2 | max 2 1;

= 2 | max 2 2;

Now the minimum of two integers:


intro min;

define min | ? x | ? y | if (< $x $y) $x $y;

= 0 | min 0 0;

= 0 | min 0 1;

= 0 | min 0 2;

= 0 | min 1 0;

= 1 | min 1 1;

= 1 | min 1 2;

= 0 | min 2 0;

= 1 | min 2 1;

= 2 | min 2 2;

Why should human CS students be the only ones the factorial example is inflicted on…


intro factorial;

define factorial | ? x | if (< $x 1) 1 | * $x | factorial | - $x 1;

= 1 | factorial 1;

= 2 | factorial 2;

= 6 | factorial 3;

= 24 | factorial 4;

= 120 | factorial 5;

12. introduce the AND logical operator

We continue introducing symbols related to math and logic. Now we will often be able to both define them and give examples, so the listener has multiple paths to understanding.

Here is and, which evaluates to true if both its two arguments are true, and false otherwise. We don’t talk about wbat happens if you pass it integers or something funky. There’d be value in getting into talking about types, but it might be a bit much just now.


intro and;

define and | ? x | ? y | if $x $y $false;

not | and $false $false;

not | and $false $true;

not | and $true $false;

and $true $true;

= $false | and $false $false;

= $false | and $false $true;

= $false | and $true $false;

= $true | and $true $true;

and (= 2 2) (> 4 2);

and (= 1 1) (> 6 4);

and (< 3 4) (= 5 5);

and (= 3 3) (= 4 4);

and (= 3 3) (= 0 0);

and (< 5 7) (> 5 3);

and (> 5 4) (> 1 0);

and (> 3 0) (= 3 3);

and (< 3 4) (< 3 6);

and (> 5 4) (> 5 4);

not | and (> 6 4) (< 3 1);

not | and (> 3 1) (> 3 3);

not | and (= 0 0) (= 5 4);

not | and (< 2 4) (> 4 6);

not | and (= 3 3) (= 3 1);

not | and (> 1 5) (< 3 6);

not | and (< 6 2) (= 2 2);

not | and (> 2 5) (= 5 5);

not | and (< 6 2) (= 3 3);

not | and (< 4 3) (> 5 2);

not | and (< 5 4) (= 1 2);

not | and (< 6 4) (= 5 1);

not | and (> 2 6) (= 1 5);

not | and (< 6 3) (= 2 3);

not | and (< 6 4) (> 0 1);

not | and (= 3 5) (< 4 1);

not | and (= 4 1) (< 4 2);

not | and (< 6 3) (= 3 0);

not | and (< 4 2) (< 4 6);

not | and (> 4 1) (< 5 2);

not | and (> 0 1) (> 7 5);

not | and (< 3 4) (> 3 6);

not | and (> 1 2) (> 6 4);

not | and (< 0 1) (= 4 5);

and (< 4 6) (< 5 7);

13. introduce the OR logical operator

Here is or, which evaluates to true if either of its arguments are true, and false otherwise. Again, we just don’t talk about what happens if you pass in any unexpected values, like integers or functions. The message is constructed so that the problem never comes up.


intro or;

define or | ? x | ? y | if $x $true $y

not | or $false $false;

or $false $true;

or $true $false;

or $true $true;

= $false | or $false $false;

= $true | or $false $true;

= $true | or $true $false;

= $true | or $true $true;

or (= 2 2) (> 4 2);

or (= 1 1) (> 6 4);

or (< 3 4) (= 5 5);

or (= 3 3) (= 4 4);

or (= 3 3) (= 0 0);

or (< 5 7) (> 5 3);

or (> 5 4) (> 1 0);

or (> 3 0) (= 3 3);

or (< 3 4) (< 3 6);

or (> 5 4) (> 5 4);

or (> 6 4) (< 3 1);

or (> 3 1) (> 3 3);

or (= 0 0) (= 5 4);

or (< 2 4) (> 4 6);

or (= 3 3) (= 3 1);

or (> 1 5) (< 3 6);

or (< 6 2) (= 2 2);

or (> 2 5) (= 5 5);

or (< 6 2) (= 3 3);

or (< 4 3) (> 5 2);

not | or (< 5 4) (= 1 2);

not | or (< 6 4) (= 5 1);

not | or (> 2 6) (= 1 5);

not | or (< 6 3) (= 2 3);

not | or (< 6 4) (> 0 1);

not | or (= 3 5) (< 4 1);

not | or (= 4 1) (< 4 2);

not | or (< 6 3) (= 3 0);

or (< 4 2) (< 4 6);

or (> 4 1) (< 5 2);

or (> 0 1) (> 7 5);

or (< 3 4) (> 3 6);

or (> 1 2) (> 6 4);

or (< 0 1) (= 4 5);

or (< 4 6) (< 5 7);

Now is an opportune moment to add <= and >= definitions. There are shorter definitions, like just negating > and <, but this feels more natural?


define >= | ? x | ? y | or (> $x $y) (= $x $y);

define <= | ? x | ? y | or (< $x $y) (= $x $y);

>= 0 0;

<= 0 0;

not | >= 0 1;

<= 0 1;

not | >= 0 2;

<= 0 2;

>= 1 0;

not | <= 1 0;

>= 1 1;

<= 1 1;

not | >= 1 2;

<= 1 2;

>= 2 0;

not | <= 2 0;

>= 2 1;

not | <= 2 1;

>= 2 2;

<= 2 2;

14. introduce pairs

Now we introduce our first data structure. The expression cons X Y stores X and Y in a pair. We can then pull X out from the pair with car (cons X Y), and we can get Y out from the pair with cdr (cons X Y). Apologies for the arcane names, they are inherited from Lisp (and they’ll be encoded as something else in the message anyway).

We give a definition of cons that is a bit funky. The cons X Y expression constructs a function which takes a single argument, also a function. That argument gets called with X and Y. That means to pull X back out, we just need to call cons X Y with a function like ? a | ? b $a. Likewise for Y. That is exactly what car and cdr do.

Definitions like that can be a bit hard to think about. But the great thing is that you can apply definitions like these without initially understanding them. So if the listener wants to try them out, they can there’s an element of interactivity beyond what a plain text message could give.


intro cons;

intro car;

intro cdr;

define cons | ? x | ? y | ? z | z $x $y;

define car | ? z | z | ? x | ? y $x;

define cdr | ? z | z | ? x | ? y $y;

assign x (cons 0 4) | = 0 | car $x;

assign x (cons 0 4) | = 4 | cdr $x;

assign x (cons 6 2) | = 6 | car $x;

assign x (cons 6 2) | = 2 | cdr $x;

assign x (cons 3 9) | = 3 | car $x;

assign x (cons 3 9) | = 9 | cdr $x;

assign x (cons 7 | cons 10 2) | = 7 | car $x;

assign x (cons 7 | cons 10 2) | = 10 | car | cdr $x;

assign x (cons 7 | cons 10 2) | = 2 | cdr | cdr $x;

assign x (cons 1 | cons 15 17) | = 1 | car $x;

assign x (cons 1 | cons 15 17) | = 15 | car | cdr $x;

assign x (cons 1 | cons 15 17) | = 17 | cdr | cdr $x;

assign x (cons 8 | cons 14 9) | = 8 | car $x;

assign x (cons 8 | cons 14 9) | = 14 | car | cdr $x;

assign x (cons 8 | cons 14 9) | = 9 | cdr | cdr $x;

assign x (cons 3 | cons 0 | cons 2 | cons 4 1) | = 3 | car $x;

assign x (cons 3 | cons 0 | cons 2 | cons 4 1) | = 0 | car | cdr $x;

assign x (cons 3 | cons 0 | cons 2 | cons 4 1) | = 2 | car | cdr | cdr $x;

assign x (cons 3 | cons 0 | cons 2 | cons 4 1) | = 4 | car | cdr | cdr | cdr $x;

assign x (cons 3 | cons 0 | cons 2 | cons 4 1) | = 1 | cdr | cdr | cdr | cdr $x;

15. introduce mutable cells

With define, we showed that there is a global memory, where we can associate a symbol with a value. That’s nice, but it can be handy to separate memory from naming. In this section we introduce make-cell X, which creates a “cell” of memory and puts X in it. The cell can be read with get!, like get! | make-cell X, or written to with set!, like set! (make-cell-X) Y.


intro make-cell;

intro set!;

intro get!;

define demo:make-cell:x | make-cell 14;

= (get! $demo:make-cell:x) 14;

set! $demo:make-cell:x 15;

= (get! $demo:make-cell:x) 15;

set! $demo:make-cell:x 5;

set! $demo:make-cell:x 7;

= (get! $demo:make-cell:x) 7;

define demo:make-cell:y | make-cell 11;

= (get! $demo:make-cell:y) 11;

set! $demo:make-cell:y 22;

= (get! $demo:make-cell:y) 22;

= (get! $demo:make-cell:x) 7;

= 29 (+ (get! $demo:make-cell:x) | get! $demo:make-cell:y);

if (= (get! $demo:make-cell:x) 7) (set! $demo:make-cell:x 88) (set! $demo:make-cell:x 99);

= (get! $demo:make-cell:x) 88;

if (= (get! $demo:make-cell:x) 7) (set! $demo:make-cell:x 88) (set! $demo:make-cell:x 99);

= (get! $demo:make-cell:x) 99;

16. introduce lists

Lists are a handy data structure to have. We’d like to get to the point in the message where we can make lists like this: vector 1 4 5, vector 77 $undefined (vector 1 2 3) 14, etc. But vector can’t be a function in the language we’ve described up to now, it just can’t work syntactically. What we can do is make lists like this: (list 3) 1 4 5, (list 4) 77 $undefined ((list 3) 1 2 3) 14, where we manually specify how many values are in the list. And then we can introduce a way to transform the syntax of the language, so that vector 1 4 5 gets rewritten to (list 3) 1 4 5 prior to being evaluated.

An alternative would be just to introduce some special new syntax for lists, and give examples. If the listener finds our transformation approach confusing, they can simply ignore it and pick the message up again once vector is in place. But by giving the transformation, we offer a second way to understand and experiment with the concepts being introduced.


intro list;

define list:n | ? n | ? ret |
  if (= $n 1) (? x | ret 1 $x) |
  ? x | list:n (- $n 1) | ? y | ? z | ret (+ 1 $y) | cons $x $z;

define list | ? n | if (= $n 0) (cons 0 0) (list:n $n $cons);

intro undefined;

= $undefined $undefined;

not | = $undefined 0;

not | = $undefined 1;

not | = $undefined 2;

intro head;

define head | ? x:list |
  if (= 0 | car $x:list) $undefined |
  if (= 1 | car $x:list) (cdr $x:list) |
  car | cdr $x:list;

intro tail;

define tail | ? x:list |
  if (= 0 | car $x:list) $undefined |
  if (= 1 | car $x:list) (cons 0 0) |
  cons (- (car $x:list) 1) | cdr | cdr $x:list;

= 17 | head | (list 4) 17 4 3 0;

= 14 | head | (list 9) 14 0 12 19 11 9 8 0 17;

= 16 | head | (list 6) 16 9 0 17 17 10;

= 5 | head | (list 5) 5 3 1 5 11;

= 15 | head | (list 9) 15 10 12 4 13 6 13 1 6;

= 4 | head | tail | (list 10) 1 4 3 7 0 1 2 11 13 3;

= 3 | head | tail | (list 5) 15 3 19 16 17;

= 8 | head | tail | (list 6) 6 8 13 9 18 2;

= 3 | head | tail | (list 8) 5 3 10 13 2 8 6 12;

= 11 | head | tail | (list 10) 14 11 18 9 9 11 3 10 16 2;

= 16 | head | tail | tail | (list 7) 19 7 16 17 12 1 18;

= 18 | head | tail | tail | (list 6) 16 9 18 5 11 17;

= 15 | head | tail | tail | (list 4) 1 0 15 18;

= 4 | head | tail | tail | (list 6) 0 0 4 19 1 5;

= 7 | head | tail | tail | (list 4) 7 1 7 14;

intro list-length;

define list-length $car;

= 4 | list-length | (list 4) 1 9 3 6;

= 1 | list-length | (list 1) 6;

= 9 | list-length | (list 9) 6 2 5 8 7 4 1 3 0;

= 7 | list-length | (list 7) 6 0 1 9 4 5 2;

= 6 | list-length | (list 6) 2 4 7 0 3 8;

intro list-ref;

define list-ref | ? x:list | ? n |
  if (= 0 | car $x:list) $undefined |
  if (= $n 0) (head $x:list) |
  list-ref (tail $x:list) | - $n 1;

= 15 | list-ref ((list 4) 5 8 15 3) 2;

= 7 | list-ref ((list 7) 12 19 0 15 1 8 7) 6;

= 4 | list-ref ((list 2) 4 6) 0;

= 13 | list-ref ((list 4) 11 10 13 8) 2;

= 2 | list-ref ((list 6) 9 2 9 8 10 12) 1;

= 7 | list-ref ((list 4) 18 7 12 13) 1;

= 2 | list-ref ((list 9) 3 3 5 6 2 16 10 1 1) 4;

= 13 | list-ref ((list 7) 11 13 9 12 5 7 5) 1;

= 17 | list-ref ((list 9) 13 17 14 16 0 2 9 3 5) 1;

= 1 | list-ref ((list 9) 18 10 4 1 17 18 8 8 8) 3;

intro function?;

function? | ? x 1;

not | function? 1;

not | function? | + 1 1;

function? | ? y | + $y 2;

function? $*;

not | function? | = 1 2;

intro equal;

define equal | ? x | ? y |
  if (not | = (function? $x) (function? $y)) $false |
  if (function? $x) (list= $x $y) (= $x $y);

intro list=;

define list= | ? x | ? y |
  if (not | = (list-length $x) (list-length $y)) $false |
  if (= 0 | list-length $x) $true |
  if (not | equal (head $x) (head $y)) $false |
  list= (tail $x) (tail $y);

equal 1 1;

equal ((list 2) 5 3) ((list 2) 5 3);

not | equal ((list 2) 5 3) ((list 3) 5 3 9);

not | equal ((list 2) 5 3) ((list 2) 5 4);

not | equal ((list 2) 5 3) ((list 2) 4 3);

not | equal ((list 2) 5 3) 12;

equal ((list 3) 5 3 9) ((list 3) 5 3 9);

equal ((list 3) 5 ((list 2) 15 1) 9) ((list 3) 5 ((list 2) 15 1) 9);

not | equal ((list 3) 5 ((list 2) 15 1) 9) ((list 3) 5 ((list 2) 14 1) 9);

not | equal ((list 3) 5 3 9) ((list 3) 5 ((list 2) 14 1) 9);

= (head | (list 8) 7 15 18 11 13 0 13 6) 7;

list= (tail | (list 8) 7 15 18 11 13 0 13 6) ((list 7) 15 18 11 13 0 13 6);

= (head | (list 9) 7 17 11 10 1 3 18 13 5) 7;

list= (tail | (list 9) 7 17 11 10 1 3 18 13 5) ((list 8) 17 11 10 1 3 18 13 5);

= (head | (list 7) 0 15 15 10 12 2 4) 0;

list= (tail | (list 7) 0 15 15 10 12 2 4) ((list 6) 15 15 10 12 2 4);

= (head | (list 5) 18 12 3 18 8) 18;

list= (tail | (list 5) 18 12 3 18 8) ((list 4) 12 3 18 8);

= (head | (list 2) 17 13) 17;

list= (tail | (list 2) 17 13) ((list 1) 13);

= (head | (list 5) 5 6 1 19 13) 5;

list= (tail | (list 5) 5 6 1 19 13) ((list 4) 6 1 19 13);

= (head | (list 9) 5 1 6 14 6 15 4 16 5) 5;

list= (tail | (list 9) 5 1 6 14 6 15 4 16 5) ((list 8) 1 6 14 6 15 4 16 5);

= (head | (list 4) 16 8 6 18) 16;

list= (tail | (list 4) 16 8 6 18) ((list 3) 8 6 18);

= (head | (list 3) 9 1 1) 9;

list= (tail | (list 3) 9 1 1) ((list 2) 1 1);

= (head | (list 4) 11 16 11 2) 11;

list= (tail | (list 4) 11 16 11 2) ((list 3) 16 11 2);

intro prepend;

define prepend | ? x | ? x:list |
  cons (+ (car $x:list) 1)
       (if (= (car $x:list) 0) $x | cons $x | cdr $x:list);

list= (prepend 14 | (list 0)) ((list 1) 14);

list= (prepend 6 | (list 1) 4) ((list 2) 6 4);

list= (prepend 19 | (list 2) 17 14) ((list 3) 19 17 14);

list= (prepend 13 | (list 3) 12 7 16) ((list 4) 13 12 7 16);

list= (prepend 4 | (list 4) 15 18 6 10) ((list 5) 4 15 18 6 10);

list= (prepend 8 | (list 5) 2 19 15 13 13) ((list 6) 8 2 19 15 13 13);

list= (prepend 11 | (list 6) 0 17 15 4 10 7) ((list 7) 11 0 17 15 4 10 7);

list= (prepend 15 | (list 7) 2 12 18 12 4 1 12) ((list 8) 15 2 12 18 12 4 1 12);

intro pair;

intro first;

intro second;

define pair | list 2;

define first | ? x:list | head $x:list;

define second | ? x:list | head | tail $x:list;

list= (pair 4 5) | (list 2) 4 5;

= (first | pair 4 5) 4;

= (second | pair 4 5) 5;

list= (pair 6 4) | (list 2) 6 4;

= (first | pair 6 4) 6;

= (second | pair 6 4) 4;

list= (pair 8 9) | (list 2) 8 9;

= (first | pair 8 9) 8;

= (second | pair 8 9) 9;

17. introduce map and reduce

For programming and for math, it is handy to be able to apply an element-wise transform to a list, and some kind of accumulator to pull out a summary.


intro map;

define map | ? x:? | ? x:list |
  if (= 0 | list-length $x:list) (list 0) |
  prepend (x:? | head $x:list) (map $x:? | tail $x:list);

list= ((list 3) 12 34 6) | map (? x | * $x 2) | (list 3) 6 17 3;

list= ((list 4) 34 20 14 8) | map (? x | * $x 2) | (list 4) 17 10 7 4;

list= ((list 5) 8 4 16 0 6) | map (? x | * $x 2) | (list 5) 4 2 8 0 3;

list= ((list 6) 36 4 28 10 6 20) | map (? x | * $x 2) | (list 6) 18 2 14 5 3 10;

list= ((list 3) 42 42 42) | map (? x 42) | (list 3) 16 2 11;

list= ((list 4) 42 42 42 42) | map (? x 42) | (list 4) 15 18 6 0;

list= ((list 5) 42 42 42 42 42) | map (? x 42) | (list 5) 19 11 5 17 2;

list= ((list 6) 42 42 42 42 42 42) | map (? x 42) | (list 6) 11 19 5 3 12 6;

intro reduce;

define reduce | ? x:? | ? x:list |
  if (= 0 | list-length $x:list) $undefined |
  if (= 1 | list-length $x:list) (head $x:list) |
  x:? (head $x:list) (reduce $x:? | tail $x:list);

= 21 | reduce $+ | (list 3) 3 7 11;

= 43 | reduce $+ | (list 4) 13 11 19 0;

= 41 | reduce $+ | (list 5) 9 2 10 8 12;

= 50 | reduce $+ | (list 6) 10 1 2 12 14 11;

18. how to change the imagined interpreter


intro translate;

define translate:begin $translate;

define translate | ? x | if (= $x 32) 64 | translate:begin $x;

= 32 64;

= (+ 32 64) 128;

define translate $translate:begin;

not | = 32 64;

= (+ 32 64) 96;

Now let’s do something useful: define a special form for lists.


intro vector;

define translate | ? x |
  if (not | function? $x) (translate:begin $x) |
  if (not | = vector | head $x) (translate:begin $x) |
  translate | prepend ((list 2) list | list-length | tail $x) | tail $x;

list= (vector 1 2 3) | (list 3) 1 2 3;

19. some more list functions


intro list:find;

define list:find:0 | ? x:list | ? y | ? n |
  if (= (list-length $x:list) 0) $undefined |
  if (equal (head $x:list) $y) $n |
  list:find:0 (tail $x:list) $y (+ $n 1);

define list:find | ? x:list | ? y | list:find:0 $x:list $y 0;

= (list:find ((list 4) 17 4 3 0) 0) 3;

= (list:find ((list 8) 0 12 19 11 9 8 0 17) 9) 4;

= (list:find ((list 9) 9 0 17 17 10 8 5 3 1) 17) 2;

= (list:find ((list 6) 17 15 10 12 4 13) 15) 1;

= (list:find ((list 7) 1 6 18 1 4 3 7) 1) 0;

= (list:find ((list 1) 2) 2) 0;

= (list:find ((list 7) 3 7 15 3 19 16 17) 3) 0;

= (list:find ((list 4) 8 13 9 18) 8) 0;

= (list:find ((list 8) 5 3 10 13 2 8 6 12) 12) 7;

= (list:find ((list 8) 11 18 9 9 11 3 10 16) 18) 1;

= (list:find ((list 4) 19 6 15 16) 11) $undefined;

= (list:find ((list 6) 0 1 5 19 2 8) 7) $undefined;

= (list:find ((list 8) 18 2 17 7 12 3 11 8) 6) $undefined;

intro last;

define last | ? x | list-ref $x | - (list-length $x) 1;

intro except-last;

define except-last | ? x |
  if (>= 1 | list-length $x) (vector) |
  prepend (head $x) | except-last | tail $x;

= 15 | last | vector 4 5 15;

list= (vector 4 5) | except-last | vector 4 5 15;

intro list:reverse;

define list:reverse | ? x:list |
  if (<= (list-length $x:list) 1) $x:list |
  prepend (last $x:list) | list:reverse | except-last $x:list;

list= (list:reverse | vector 1 2 3) (vector 3 2 1);

list= (list:reverse | vector 50 1 33 99) (vector 99 33 1 50);

intro append;

define append | ? x | ? lst |
  if (= 0 | list-length $lst) (vector $x) |
  prepend (head | $lst) | append $x | tail $lst;

list= (vector 1 2 5) | append 5 | vector 1 2;

intro select-match;

define select-match | ? test | ? lst |
  if (= 0 | list-length $lst) $lst |
  if (not | test | head $lst) (select-match $test | tail $lst) |
  prepend (head $lst) (select-match $test | tail $lst);

list= (vector 14 19 13) | select-match (? x | > $x 10) | vector 1 14 19 3 13 0 4;

20. introduce pi and e

Just in passing, give approximate values for pi and e.


intro minus;

define minus | ? x | - 0 $x;

= 0 | + 4 | minus 4;

= 8 | + 10 | minus 2;

intro frac;

= 40 | frac 40 1;

= 20 | frac 40 2;

= 10 | frac 40 4;

= 5 | frac 40 8;

= 1 | + (frac 1 2) (frac 1 2);

= 2 | + (frac 3 2) (frac 1 2);

= 1 | + (frac 3 5) (frac 2 5);

intro abs;

define abs | ? x | if (> $x 0) $x (- 0 $x);

= 4 | abs 4;

= 4 | abs | minus 4;

intro within;

define demo:epsilon | frac 1 10000;

define within | ? epsilon | ? x | ? y | < (abs | - $x $y) $epsilon;

not | within $demo:epsilon 1 2;

not | within $demo:epsilon 2 1;

within $demo:epsilon 2 2;

within $demo:epsilon 2 | + 2 (frac $demo:epsilon 2);

not | within $demo:epsilon 2 | + 2 (* $demo:epsilon 2);

intro range;

define range | ? x:- | ? x:+ |
  if (<= $x:+ $x:-) (vector) |
  prepend $x:- | range (+ 1 $x:-) $x:+;

= 6 | reduce $+ | range 0 4;

= 12 | reduce $+ | map (? x | * $x 2) | range 0 4;

= 3 | reduce $+ | range 3 4;

intro even;

not | even 1;

even 2;

not | even 3;

even 4;

not | even 5;

intro odd;

define odd | ? x | not | even $x;

odd 1;

even 2;

odd 3;

even 4;

odd 5;

intro decimal;

define float | ? x:list | ? y | ? z |
  if (= 0 | list-length | $x:list) 0 |
  + (* $z | head $x:list) |
  float (tail $x:list) $y (* $y $z);

define decimal | ? x | ? x:list | + $x | float $x:list (frac 1 10) (frac 1 10);

within $demo:epsilon (frac 1 3) | decimal 0 | vector 3 3 3 3 3 3;

within $demo:epsilon (frac 9 7) | decimal 1 | vector 2 8 5 7 1 4;

intro e;

define e:hat | reduce $+ | map (? x | frac 1 | factorial $x) | range 0 100;

within $demo:epsilon $e $e:hat;

within $demo:epsilon $e | decimal 2 | vector 7 1 8 2 8;

intro pi;

define pi:part | ? x | frac (if (even $x) (minus 1) 1) | * (* $x 2) | * (+ 1 | * $x 2) (+ 2 | * $x 2);

define pi:hat | + 3 | * 4 | reduce $+ | map $pi:part | range 1 100;

within $demo:epsilon $pi $pi:hat;

within $demo:epsilon $pi | decimal 3 | vector 1 4 1 5 9 2 6 5 3 5;

intro power:10;

define power:10 | ? n |
  if (= $n 0) 1 |
  assign part (if (>= $n 0) 10 (frac 1 10)) |
  reduce $* | map (? x $part) | range 0 (abs $n);

define float:= | ? x | ? y |
  if (= $x $y) $true |
  within (frac (+ $x $y) 200000) $x $y;

float:= 10 | power:10 1;

float:= 100 | power:10 2;

float:= 1000 | power:10 3;

float:= (frac 1 10) | power:10 | minus 1;

float:= (frac 1 100) | power:10 | minus 2;

float:= 1 | power:10 0;

define decimal:power | ? x:power | ? x:int | ? x:list |
  * (power:10 $x:power) (decimal $x:int $x:list);

float:= 1530 | decimal:power 3 1 | vector 5 3;

float:= 15300 | decimal:power 4 1 | vector 5 3;

float:= (decimal 1 | vector 5 3) | decimal:power 0 1 | vector 5 3;

float:= (decimal 0 | vector 0 0 1 5 3) | decimal:power (minus 3) 1 | vector 5 3;

intro pow:int;

define pow:int | ? x | ? n |
  if (= $n 0) 1 |
  assign part (if (>= $n 0) $x (frac 1 $x)) |
  reduce $* | map (? y $part) | range 0 (abs $n);

= 100 | pow:int 10 2;

= 25 | pow:int 5 2;

= 4 | pow:int 2 2;

= 8 | pow:int 2 3;

= 16 | pow:int 2 4;

= 1 | pow:int 2 0;

= (frac 1 2) | pow:int 2 | minus 1;

intro pow;

= 1 | pow 2 0;

= 2 | pow 2 1;

= 4 | pow 2 2;

= 8 | pow 2 3;

= 16 | pow 2 4;

= 1 | pow 3 0;

= 3 | pow 3 1;

= 9 | pow 3 2;

= 27 | pow 3 3;

= 81 | pow 3 4;

= 1 | pow 4 0;

= 4 | pow 4 1;

= 16 | pow 4 2;

= 64 | pow 4 3;

= 256 | pow 4 4;

= 1 | pow 5 0;

= 5 | pow 5 1;

= 25 | pow 5 2;

= 125 | pow 5 3;

= 625 | pow 5 4;

float:= 1 | pow 2 0;

float:= (decimal 1 | vector 1 8 9 2 0) | pow 2 (decimal 0 | vector 2 5);

float:= (decimal 1 | vector 4 1 4 2 1) | pow 2 (decimal 0 | vector 5);

float:= (decimal 1 | vector 6 8 1 7 9) | pow 2 (decimal 0 | vector 7 5);

float:= 2 | pow 2 1;

float:= (decimal 2 | vector 3 7 8 4 1) | pow 2 (decimal 1 | vector 2 5);

float:= (decimal 2 | vector 8 2 8 4 2) | pow 2 (decimal 1 | vector 5);

float:= (decimal 3 | vector 3 6 3 5 8) | pow 2 (decimal 1 | vector 7 5);

float:= 4 | pow 2 2;

float:= (decimal 4 | vector 7 5 6 8 2) | pow 2 (decimal 2 | vector 2 5);

float:= (decimal 5 | vector 6 5 6 8 5) | pow 2 (decimal 2 | vector 5);

float:= (decimal 6 | vector 7 2 7 1 7) | pow 2 (decimal 2 | vector 7 5);

float:= 8 | pow 2 3;

float:= 1 | pow 3 0;

float:= (decimal 1 | vector 3 1 6 0 7) | pow 3 (decimal 0 | vector 2 5);

float:= (decimal 1 | vector 7 3 2 0 5) | pow 3 (decimal 0 | vector 5);

float:= (decimal 2 | vector 2 7 9 5 0) | pow 3 (decimal 0 | vector 7 5);

float:= 3 | pow 3 1;

float:= (decimal 3 | vector 9 4 8 2 2) | pow 3 (decimal 1 | vector 2 5);

float:= (decimal 5 | vector 1 9 6 1 5) | pow 3 (decimal 1 | vector 5);

float:= (decimal 6 | vector 8 3 8 5 2) | pow 3 (decimal 1 | vector 7 5);

float:= 9 | pow 3 2;

float:= (decimal 11 | vector 8 4 4 6 6) | pow 3 (decimal 2 | vector 2 5);

float:= (decimal 15 | vector 5 8 8 4 5) | pow 3 (decimal 2 | vector 5);

float:= (decimal 20 | vector 5 1 5 5 6) | pow 3 (decimal 2 | vector 7 5);

float:= 27 | pow 3 3;

float:= 1 | pow 4 0;

float:= (decimal 1 | vector 4 1 4 2 1) | pow 4 (decimal 0 | vector 2 5);

float:= 2 | pow 4 (decimal 0 | vector 5);

float:= (decimal 2 | vector 8 2 8 4 2) | pow 4 (decimal 0 | vector 7 5);

float:= 4 | pow 4 1;

float:= (decimal 5 | vector 6 5 6 8 5) | pow 4 (decimal 1 | vector 2 5);

float:= 8 | pow 4 (decimal 1 | vector 5);

float:= (decimal 11 | vector 3 1 3 7 0) | pow 4 (decimal 1 | vector 7 5);

float:= 16 | pow 4 2;

float:= (decimal 22 | vector 6 2 7 4 1) | pow 4 (decimal 2 | vector 2 5);

float:= 32 | pow 4 (decimal 2 | vector 5);

float:= (decimal 45 | vector 2 5 4 8 3) | pow 4 (decimal 2 | vector 7 5);

float:= 64 | pow 4 3;

intro exp;

define exp:hat | ? x |
  reduce $+ | map (? n | frac (pow:int $x $n) | factorial $n) | range 0 50;

float:= $e | exp:hat 1;

define ln:10:hat | decimal 2 | vector 3 0 2 5 8 5 0 9 2 9 9;

float:= (pow:int 10 2) (exp:hat | * 2 $ln:10:hat);

float:= (pow:int 10 3) (exp:hat | * 3 $ln:10:hat);

float:= (pow:int 10 4) (exp:hat | * 4 $ln:10:hat);

21. introduce i

A very very abbreviated introduction of complex numbers


define all-equal | ? x:list |
  if (>= 1 | list-length $x:list) $true |
  and (= (list-ref $x:list 0) (list-ref $x:list 1))
      (all-equal | tail $x:list);

all-equal | vector 2 2 2;

not | all-equal | vector 2 2 1;

not | all-equal | vector 2 1 2;

not | all-equal | vector 1 2 2;

intro sum;

define sum | reduce $+;

intro i;

= (minus 1) | * $i $i;

define complex | ? x | ? y | + $x | * $y $i;

= (complex 5 6) | + (complex 3 2) (complex 2 4);

= (complex 7 22) | * (complex 5 4) (complex 3 2);

= (complex 10 8) | * (complex 5 4) 2;

= (complex 10 8) | * 2 (complex 5 4);

should work through how to divide complex numbers (multiply by conjugate)


= (complex (frac 6 25) (frac 17 25)) | frac (complex 3 2) (complex 4 | minus 3);

all-equal | vector
  (+ 7 | * 22 $i)
  (* (+ 5 | * 4 $i) (+ 3 | * 2 $i))
  (sum | vector
    (* 5 3)
    (* 5 (* 2 $i))
    (* (* 4 $i) 3)
    (* (* 4 $i) (* 2 $i)))
  (sum | vector
    15 (* 10 $i) (* 12 $i) (minus 8))
  (sum | vector
    (+ 15 (minus 8)) (* (+ 10 12) $i));

Hint at Euler’s identity


float:= 0 | + 1 | exp:hat | * $pi $i;

22. define let expressions

Sometimes it is nice to do a lot of assignments at once. We introduce let ((k1 v1) (k2 v2)) body which is equivalent to assign k1 v1 | assign k2 v2 | body.


intro let;

define translate:let:begin $translate;

define translate:let | ? x | ? y |
  if (= 0 | list-length $x) (translate $y) |
  translate:let (tail $x) |
    vector assign (head | head $x) (head | tail | head $x) $y;

define translate | ? x |
  if (not | function? $x) (translate:let:begin $x) |
  if (not | = let | head $x) (translate:let:begin $x) |
  translate:let (head | tail $x) (head | tail | tail $x);

let ((x 20)) | = $x 20;

let ((x 50) (y 20)) | = 30 | - $x $y;

= (let ((x 10)) | + $x 5) (assign x 10 | + $x 5);

= (let ((x 10)) | + $x 5) ((? x | + $x 5) 10);

= (let ((x 10) (y 5)) | + $x $y) (assign x 10 | assign y 5 | + $x $y);

= (let ((x 10) (y 5)) | + $x $y) ((? x | ? y | + $x $y) 10 5);

23. lambda functions


intro lambda;

define translate:lambda:begin $translate;

define translate |
  let ((x:translate $translate:lambda:begin)) |
  ? x |
    if (not | function? $x) (x:translate $x) |
    if (not | = lambda | head $x) (x:translate $x) |
    let ((x:list | head | tail $x)
         (y | head | tail | tail $x)) |
      if (= 0 | list-length $x:list) (translate $y) |
      translate | vector lambda (except-last $x:list) |
        vector ? (last $x:list) $y;

= 8 | (lambda (x y) | - $x $y) 8 0;

= 2 | (lambda (x y) | - $x $y) 4 2;

= 3 | (lambda (x y) | - $x $y) 9 6;

= 3 | (lambda (x y) | - $x $y) 4 1;

= 0 | (lambda (x y) | - $x $y) 4 4;

24. end of part 1, start of part 2

# The following parts of the message are experimental, and not
# carefully integrated with the main body

intro part2;

25. some pure lambda calculus definitions - optional

# these definitions are not quite what we want
# since thinking of everything as a function requires headscratching
# it would be better to use these as a parallel means of evaluation
# ... for expressions

intro pure:if;

define pure:if | ? x | ? y | ? z | x $y $z;

intro pure:true;

define pure:true | ? y | ? z | y;

intro pure:false;

define pure:false | ? y | ? z | z;

intro pure:cons;

define pure:cons | ? x | ? y | ? z | pure:if $z $x $y;

intro pure:car;

define pure:car | ? x | x $pure:true;

intro pure:cdr;

define pure:cdr | ? x | x $pure:false;

intro pure:0;

define pure:0 | ? y | ? x $x;

intro pure:1;

define pure:1 | ? y | ? x | y $x;

intro pure:2;

define pure:2 | ? y | ? x | y (y $