Scheme Lisp - Feel the Cool

Intro

Scheme is

simple,
weird, and
cool

Simple

Scheme is simple by design.

Designed for teaching¹
Used as the basis of the Computer Science course at MIT
Based on Lambda Calculus²

Simple to try

$ sudo apt install racket
$ mzscheme
>

Simple to use

Scheme has:

One thing you can do
One data structure

Both are actually the same.

Simple syntax

(operator operand1 operand2 ...)

Simple expressions

> (+ 3 4)

Simple expressions

> (+ 3 4)
7

Simple expressions

> (+ 3 4)
7
> (* 3 4)

Simple expressions

> (+ 3 4)
7
> (* 3 4)
12

Simple expressions

> (+ 3 4)
7
> (* 3 4)
12
> (+ 5 (* 2 2))

Simple expressions

> (+ 3 4)
7
> (* 3 4)
12
> (+ 5 (* 2 2))
9

Simple definitions

> (define foo 3)

Simple definitions

> (define foo 3)

> foo

Simple definitions

> (define foo 3)

> foo
3

Simple definitions

> (define foo 3)

> foo
3
> (* foo 4)

Simple definitions

> (define foo 3)

> foo
3
> (* foo 4)
12

Simple functions

> (define (square x) (* x x))

Simple functions

> (define (square x) (* x x))

> (square 4)

Simple functions

> (define (square x) (* x x))

> (square 4)
16

Simple functions

> (define (square x) (* x x))

> (square 4)
16
> (+ (square 2) (square 3))

Simple functions

> (define (square x) (* x x))

> (square 4)
16
> (+ (square 2) (square 3))
13

Simple flow control

(define (abs x)
        (if (< x 0)
            (- x)
            x))

Simple flow control

(define (abs x)
        (if (< x 0)
            (- x)
            x))

> (abs -3)

Simple flow control

(define (abs x)
        (if (< x 0)
            (- x)
            x))

> (abs -3)
3

Simple flow control

(define (abs x)
        (if (< x 0)
            (- x)
            x))

> (abs -3)
3
> (abs 3)

Simple flow control

(define (abs x)
        (if (< x 0)
            (- x)
            x))

> (abs -3)
3
> (abs 3)
3

Simple data structure

> (list 9 3 5)

Simple data structure

> (list 9 3 5)
(9 3 5)

Simple data structure

> (list 9 3 5)
(9 3 5)
> (sort (list 9 3 5) <)

Simple data structure

> (list 9 3 5)
(9 3 5)
> (sort (list 9 3 5) <)
(3 5 9)

Simple data structure

> (list 9 3 5)
(9 3 5)
> (sort (list 9 3 5) <)
(3 5 9)
> (length (list 3 2))

Simple data structure

> (list 9 3 5)
(9 3 5)
> (sort (list 9 3 5) <)
(3 5 9)
> (length (list 3 2))
2

Weird

Scheme is weird.

Building lists from pairs
Recursion for everything
Passing functions into functions
Data/code duality

Weird lists

> (define x (list 1 2 3))

Weird lists

> (define x (list 1 2 3))

> (car x)

Weird lists

> (define x (list 1 2 3))

> (car x)
1

Weird lists

> (define x (list 1 2 3))

> (car x)
1
> (cdr x)

Weird lists

> (define x (list 1 2 3))

> (car x)
1
> (cdr x)
(2 3)

Weird pairs

> (cons "a" "b")

Weird pairs

> (cons "a" "b")
("a" . "b")

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)
> (define p (cons 1 2))

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)
> (define p (cons 1 2))

> (car p)

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)
> (define p (cons 1 2))

> (car p)
1

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)
> (define p (cons 1 2))

> (car p)
1
> (cdr p)

Weird pairs

> (cons "a" "b")
("a" . "b")
> (cons (cons 5 6) 7)
((5 . 6) . 7)
> (define p (cons 1 2))

> (car p)
1
> (cdr p)
2

Weird list-building

> null

Weird list-building

> null
()

Weird list-building

> null
()
> (cons 2 null)

Weird list-building

> null
()
> (cons 2 null)
(2)

Weird list-building

> null
()
> (cons 2 null)
(2)
> (cons 1 (cons 2 null))

Weird list-building

> null
()
> (cons 2 null)
(2)
> (cons 1 (cons 2 null))
(1 2)

Weird list-building

> null
()
> (cons 2 null)
(2)
> (cons 1 (cons 2 null))
(1 2)
> (list 1 2)

Weird list-building

> null
()
> (cons 2 null)
(2)
> (cons 1 (cons 2 null))
(1 2)
> (list 1 2)
(1 2)

Weird lists made of pairs

(list 1 2 3)

Weirdly named functions

cons sticks things together
car gives you the first thing
cdr gives you the second thing

Weirdly named functions

cons sticks things together
car gives you the "head"
cdr gives you the "tail"

Weirdly named functions

So cadddr's meaning should be obvious

Weirdly named functions

So cadddr's meaning should be obvious
Right?

Weirdly named functions

(cadddr v)
Returns (car (cdr (cdr (cdr v))))

Weird recursion

(define (sum vs)
        (if (= 1 (length vs))
            (car vs)
            (+ (car vs)
               (sum (cdr vs)))))

Weird recursion

(define (sum vs)
        (if (= 1 (length vs))
            (car vs)
            (+ (car vs)
               (sum (cdr vs)))))

> (sum (list 5 6 7))

Weird recursion

(define (sum vs)
        (if (= 1 (length vs))
            (car vs)
            (+ (car vs)
               (sum (cdr vs)))))

> (sum (list 5 6 7))
18

Weird recursion

(define (sum vs)
        (if (= 1 (length vs))
            (car vs)
            (+ (car vs)
               (sum (cdr vs)))))

Weird recursion

(define (sum vs)
        (if (= 1 (length vs))
            (car vs)
            (+ (car vs)
               (sum (cdr vs)))))

Weird meta-functions

(define (double value)
        (* 2 value))

(define (apply-twice fn value)
        (fn (fn value)))

> (apply-twice double 2)

Weird meta-functions

(define (double value)
        (* 2 value))

(define (apply-twice fn value)
        (fn (fn value)))

> (apply-twice double 2)
8

Weird meta-functions

(define (apply-twice fn value)
        (fn (fn value)))

Weird functions as values

> (map double (list 3 4 5))

Weird functions as values

> (map double (list 3 4 5))
(6 8 10)

Weird code as data

> (define s (list '+ 4 7))

Weird code as data

> (define s (list '+ 4 7))
> s

Weird code as data

> (define s (list '+ 4 7))
> s
(+ 4 7)

Weird code as data

> (define s (list '+ 4 7))
> s
(+ 4 7)
> (eval s)

Weird code as data

> (define s (list '+ 4 7))
> s
(+ 4 7)
> (eval s)
11

Weird code as data

> (define (switchop a) (cons '* (cdr a)))

Weird code as data

> (define (switchop a) (cons '* (cdr a)))
> (define s2 (switchop s))

Weird code as data

> (define (switchop a) (cons '* (cdr a)))
> (define s2 (switchop s))
> s2

Weird code as data

> (define (switchop a) (cons '* (cdr a)))
> (define s2 (switchop s))
> s2
(* 4 7)

Weird code as data

> (define (switchop a) (cons '* (cdr a)))
> (define s2 (switchop s))
> s2
(* 4 7)
> (eval s2)

Weird code as data

> (define (switchop a) (cons '* (cdr a)))
> (define s2 (switchop s))
> s2
(* 4 7)
> (eval s2)
28

Cool

Quoting
Better names
Duck typing (generics)
Lambdas & Closures
Metaprogramming

Cool quoting

> '(* 3 6)

Cool quoting

> '(* 3 6)
(* 3 6)

Cool quoting

> '(* 3 6)
(* 3 6)

> '(foo (bar "a" 3))

Cool quoting

> '(* 3 6)
(* 3 6)

> '(foo (bar "a" 3))
(foo (bar "a" 3))

Cool names

These are all valid names in Scheme:

equal?
boom!
a*b
co-ordinates
<10
+

This is cool.

Cool replacement

This works:

> (define (+ x y) 5)
> (+ 2 2)
5

This is cool.

Cool Duck Typing

> (sort (list 5 4 3 2 1) <)
(1 2 3 4 5)
> (sort (list "abc" "a" "ab") string<?)
("a" "ab" "abc")

This is somewhat uncool, but useful.

Cool lambdas

> (map
       (lambda (x) (+ x 1))
       (list 1 2 3))
(2 3 4)

Cool closures

(define (counter)
        (define c 0)
        (lambda ()
                (set! c (+ c 1))
                c))

Cool closures

(define (counter)
        (define c 0)
        (lambda ()
                (set! c (+ c 1))
                c))

Cool closures

> (define a (counter))
> (a)

Cool closures

> (define a (counter))
> (a)
1

Cool closures

> (define a (counter))
> (a)
1
> (a)

Cool closures

> (define a (counter))
> (a)
1
> (a)
2

Cool closures

> (define a (counter))
> (a)
1
> (a)
2
> (a)

Cool closures

> (define a (counter))
> (a)
1
> (a)
2
> (a)
3

Cool closures

> (define b (counter))
> (b)

Cool closures

> (define b (counter))
> (b)
1

Cool closures

> (define b (counter))
> (b)
1
> (a)

Cool closures

> (define b (counter))
> (b)
1
> (a)
4

Cool metaprogramming

Metaprogramming is just programming.

> (define (times-n n) (lambda (x) (* n x)))

Cool metaprogramming

Metaprogramming is just programming.

> (define (times-n n) (lambda (x) (* n x)))
> (define times3 (times-n 3))

Cool metaprogramming

Metaprogramming is just programming.

> (define (times-n n) (lambda (x) (* n x)))
> (define times3 (times-n 3))
> (define (trpl lst) (map times3 lst))

Cool metaprogramming

Metaprogramming is just programming.

> (define (times-n n) (lambda (x) (* n x)))
> (define times3 (times-n 3))
> (define (trpl lst) (map times3 lst))
> (trpl (list 1 2 3))

Cool metaprogramming

Metaprogramming is just programming.

> (define (times-n n) (lambda (x) (* n x)))
> (define times3 (times-n 3))
> (define (trpl lst) (map times3 lst))
> (trpl (list 1 2 3))
(3 6 9)

Cool things I haven't mentioned

Macros
Streams
The Metacircular Evaluator

Cool reading

Structure and Interpretation of Computer Programs³ changed my life

Questions

This presentation is available under cc by-sa at github.com/andybalaam/videos-scheme-accu2018.

Extra - data from functions (1)

(define (mcons a b)
    (lambda (cmd)
        (if (equal? cmd "car")
            a
            b)))

(define (mcar pair) (pair "car"))
(define (mcdr pair) (pair "cdr"))

Extra - data from functions (2)

> (define foo (mcons 1 2))
> (mcar foo)
1
> (mcdr foo)
2

Extra - numbers from functions (1)

(define n0 (lambda () null))

(define (minc x) (lambda () x))

(define (mdec x) (x))

Extra - numbers from functions (2)

(define n1 (minc n0))
(define n2 (minc n1))
(define n3 (minc n2))
(define n4 (minc n3))
(define n5 (minc n4))

Extra - numbers from functions (3)

(define (mzero? x) (null? (x)))

(define (mequal? x y)
    (cond
        ((mzero? x) (mzero? y))
        ((mzero? y) (mzero? x))
        (else (mequal? (mdec x) (mdec y)))))

Extra - numbers from functions (4)

> (mequal? n1 n0)
#f
> (mequal? n1 n1)
#t

Extra - numbers from functions (5)

(define (m+ x y)
    (if (mzero? y)
        x
        (m+ (minc x) (mdec y))))

Extra - numbers from functions (6)

> (mequal? (m+ n0 n2) n2)
#t
> (mequal? (m+ n0 n2) n3)
#f
> (mequal? (m+ n0 n2) (m+ n1 n2))
#f
> (mequal? (m+ n2 n3) n5)
#t