1

  • Notice how easy it is to pass a function (as a parameter) to a function in Scheme, it is kind of like MACRO.

  • One of the meaning of brackets is function call.

  • Quotation is kind of like MACRO.

  • define-syntax is totally MACRO

Pairs

1
2
3
4
5
6
7
8
9
10
11
12
> (cons 1 2)
(1 . 2)
> (cons (cons 1 2) 3)
((1 . 2) . 3)
> (define foo (cons 1 2))
> foo
(1 . 2)

> (car foo)		; car gets the first element in a pair.
1
> (cdr foo)		; while cdr gets the second
2

Lists

Pair is basically a little list.

The definition of a list is a set of pairs and the last pair in that has null on the right hand side. If you don’t believe that, check out the code below.

1
2
3
4
5
6
7
8
9
10
11
12
> (cons 1 null)		; it's indeed a pair of 1 and null but the way the interpreter writes it is a list containing only 1.
(1)

> (cons 1 2)
(1 . 2)		; it's a pair.
> (cons 1 (cons 2 null))
(1 2)		; it's a list
> (cons 1 (cons 2 (cons 3 null)))
(1 2 3)

> (equal? (cons 1 (cons 2 null)) (list 1 2))
#t

List is a bunch of pairs cascading down and ending in null.

car & cdr

1
2
3
4
5
6
7
8
9
10
11
12
13
> (define mylist (cons 1 (cons 2 (cons 3 null))))
> mylist
(1 2 3)

> (car mylist)
1		; the first element 1 in the pair mylist
> (cdr mylist)
(2 3)		; the second element (cons 2 (cons 3 null)) in the pair mylist, which is precisely the rest of the list mylist.

> (cadr mylist)		; d, then a.
2	
> (caddr mylist)		; double d, then a.
3

list-ref

1
2
3
4
> (list-ref (list "a" "b" "c") 1)
"b"
> (list-ref (list "a" "b" "c") 2)
"c"

“Loops”

Loops are actually recursion.

A bad implementation of list-ref.

1
2
3
4
5
6
> (define (my-list-ref lst n)
      (if (zero? n)
          (car lst)
          (my-list-ref (cdr lst) (- n 1))))
> (my-list-ref (list "a" "b" "c") 1)
"b"

Map

Map applies the function you give it to every element in the list you give it. Difference between it and Python’s map is the latter one returns a map object which is a kind of iterator, but Scheme’s map directly give you a list.

1
2
3
4
5
6
7
> (define baz (list 1 2 3))
> (define (double x) (* x 2))
> (map double baz)
(2 4 6)

> baz
(1 2 3)

A bad implementation of map.

1
2
3
4
5
6
7
8
1 ]=> (define (my-map fn lst)
        (if (equal? () lst)
                ()
                (cons (fn (car lst)) (my-map fn (cdr lst)))))

1 ]=> (my-map double baz)

;Value: (2 4 6)

Fold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
> (define qux (list 1 2 3 4))
> (foldr + 0 qux)	; 4 + 3 + 2 + 1 + 0
10
> (foldr + 2000 qux)	; 1 + (2 + (3 + (4 + 2000)))
2010
> (foldr + -100 qux)	; 1 + (2 + (3 + (4 + -100)))
-90

> (foldr - 0 qux)	; 1 - (2 - (3 - (4 - 0)))
-2
> (foldr - 2000 qux)	; 1 - (2 - (3 - (4 - 2000)))
1998

> (foldr * 1 qux)	; 1 * (2 * (3 * (4 * 1)))
24
> (foldr * 0 qux)
0

>> (my-foldr / 1 qux)	; 1 / (2 / (3 / (4 / 1)))
3/8

A bad implementation of foldr.

1
2
3
4
> (define (my-foldr fn start lst)
    (if (null? lst)
        start
        (fn (car lst) (my-foldr fn start (cdr lst)))))

Using outer symbols

1
2
3
4
5
6
7
8
9
10
11
> (define (assert-equal a b)
    (define (print-error)
      (display a)
      (display " is not equal to ")
      (display b)
      (newline))
    (if (not (equal? a b))
        (print-error) null))
> (assert-equal 3 3)
> (assert-equal 3 4)
3 is not equal to 4
1
2
3
4
5
6
7
> (define (circle-details r)
    (define pi 3.1415926)
    (define (area) (round (* pi r r)))
    (define (circum) (round (* 2 pi r)))
    (list (area) (circum)))
> (circle-details 3)
'(28.0 19.0)

The inner function can access the symbols of the outer function unless you override them within the inner function.

Returning functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
> (define (make-add-one)
    (define (inc x) (+ 1 x))
    inc)
> make-add-one
#<procedure:make-add-one>

> (define add-one make-add-one)		; no bracket, no function call
> add-one(2)
#<procedure:make-add-one>
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 2
  arguments...: [none]

> (define add-one (make-add-one))
> (add-one 3)
4

> (define (make-add-x x)
    (define (add-x y) (+ x y))
    add-x)
> (define add-ten (make-add-x 10))
> (add-ten 19)
29

Holding state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> (define (make-counter)
    (define value 0)
    (define (counter)
      (set! value (+ value 1))	; basically is value += 1
      value)
    counter)
> (define counter (make-counter))
> (counter)
1
> (counter)
2
> (counter)
3
> (counter)
4

In this case, value is nonlocal in inner procedure counter, but you don’t need to claim it explicitly.

So we can see function call is not simply Macro, it can remember the state of the system (group).

Uses-Testing

1
2
3
4
5
6
7
8
9
10
> (define (shout display-fn txt)
    (display-fn
     (list->string
      (map
       char-upcase
       (string->list txt)))))
> (shout display "what the fuck")
WHAT THE FUCK
> (shout print "what the fuck")
"WHAT THE FUCK"

Now I’m gonna test it.

1
2
3
4
5
6
7
8
9
10
> (define (test-shout-displays-upper-case)
    (define displayed "")
    (define (fake-display txt)
      (set! displayed txt))
    (shout fake-display "Hello Andy")
    (assert-equal displayed "HELLO ANDY"))
> assert-equal
#<procedure:assert-equal>
> (test-shout-displays-upper-case)
'()

Uses-Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
> (define (make-balance)
    (define value 0)
    (define (bal method)
      (define (add-method x)
        (set! value (+ value x)))
      (define (get-method) value)
      (if (equal? method "add")
          add-method
          get-method))
    bal)
> (define balance (make-balance))

> (define get (balance 'get))
> (define add (balance "add"))
> (get)
0
> (add 10)
> (get)
10

> (define get2 (balance 'get))
> (define add2 (balance "add"))
> (get2)
10
> (add2 100)
> (get)
110

As you can see, it’s a simulation of a class balance

Tail-Recursion Version Fibonacci

1
2
3
4
5
6
(define (fib-it n))
	(define (impl acc1 acc2 countg)
      (if (= count 2)
          acc1
          (impl (+ acc1 acc2) acc1 (- count 1))))
    (impl 1 1 n)

Data made from code

If we want to make a list of three symbols, we get an error.

1
2
3
> (list a b c)
. . a: undefined;
 cannot reference an identifier before its definition

We don’t have there definition, but if we define them, we get a list of what they refer to.

1
2
3
> (define a 1)(define b 2)(define c 3)
> (list a b c)
'(1 2 3)

How to make a list of the symbols themselves instead of what they refer to? The answer is by quoting.

1
2
> (list 'a 'b 'c)
'(a b c)

Quoting can apply to anything you like. Because of that quote symbol there, it’s not threated as a piece of code we’re going to run.

1
2
3
4
5
> '(a (b1 b2) c)
'(a (b1 b2) c)

> (equal? '(a (b1 b2) c) (list 'a (list 'b1 'b2) 'c))
#t

When you execute a bracketed list you always have to have at least one thing in that list which is the name of the procedure you want to execute. But how to create a list with no element?

1
2
3
4
5
6
7
8
9
10
11
12
13
> ()
. #%app: missing procedure expression;
 probably originally (), which is an illegal empty application in: (#%app)
 
> (list)	; it's a way.
'()
> '()	; with the power of quotation, this is another way.
'()
> null
'()

> 'null
'null

Asking about data

Before a procedure get executed, all the arguments get evaluated.

1
2
3
4
5
6
7
8
> (symbol? 'z)
#t
> (symbol? z)
. . z: undefined;
 cannot reference an identifier before its definition
> (define z 1)
> (symbol? z)
#f

Generic type safety

Quote this stuff looks like code. 

1
2
3
4
5
(define generic-safe-sum
    '(define (safe-sum x y)
       (if (and (TEST x) (TEST y))	; we don't know what TEST is so far but we will.
           (+ x y)
           "INCORRECT TYPES")))

Another procedure that replace find with repl.

1
2
3
4
5
6
7
8
(define (replace lst find repl)
    (if (pair? lst)
        (cons
         (replace (car lst) find repl)
         (replace (cdr lst) find repl))
        (if (equal? lst find)
            repl
            lst)))

So here is what we can do.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> (define safe-sum-int
    (replace generic-safe-sum 'TEST 'integer?))
> (eval safe-sum-int)
> (safe-sum 1 2)
3
> (safe-sum 2.1 2.2)
"INCORRECT TYPES"

> (define (nonint? x)
    (and (real? x) (not (integer? x))))
> (eval (replace generic-safe-sum 'TEST 'nonint?))
> (safe-sum 12 21)
"INCORRECT TYPES"
> (safe-sum 2.4 2.2)
4.6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
> (define (mcons a b)
    (lambda (cmd)
      (if (equal? cmd "car")
          a
          b)))
> ((mcons 1 2) "car")
1

> (define (mcar pair) (pair "car"))
> (define (mcdr pair) (pair "cdr"))
> (mcar (mcons 1 2))
1
> (mcdr (mcons 1 2))
2

m in mcons/mcar/mcdr means meta.

Numbers magic

用高阶函数模拟数字，函数的阶数代表数字的值。

1
2
3
4
5
6
7
8
9
10
> (define n0 (lambda () null))
> (define (minc x) (lambda () x))
> (define (mdec x) (x))
> (n0)
'()
> (define n1 (minc n0))
> (equal? (n1) n0)
#t
> (equal? (mdec n1) n0)
#t

n1 是 n0 的高一阶的函数，即 n0() = null, n1() = n0.

那么我们用 meual? 检查两个函数是否同阶，用 mzero? 检查函数是否是元函数（最低阶，即返回 null 的 n0）。

1
2
3
4
5
6
7
8
9
10
11
> (define (mzero? x) (null? (x)))
> (define (mequal? x y)
    (cond
      ((mzero? x) (mzero? y))
      ((mzero? y) (mzero? x))
      (else (mequal? (mdec x) (mdec y)))))

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

还可以定义函数阶数的加法 m+， (m+ n1 n2) => n3

1
2
3
4
5
6
7
8
9
10
11
12
> (define (m+ x y)
    (if (mzero? y)
        x
        (m+ (minc x) (mdec y))))

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

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

以上行为都可以自定义，我们可以自定义元函数（0）的行为，以及函数增阶的规则，做到一些看起来很酷的事情。

You can define numbers in Scheme without any concept of numbers.