summaryrefslogtreecommitdiffstats
path: root/books/Little Schemer.page
blob: 7490698ccb171d6a875d1588717c0b423ee6af64 (plain)
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
---
format: rst
categories: book
toc: no
...

============================
The Little Schemer
============================

:by: Daniel Friedman and Matthias Felleisen 
:Edition: Fourth (4rth)

See also `Scheme </software/scheme/>`_.

I read this book before starting on a scheme/physics project. I had programmed
in scheme previously as an algebra/analysis tool, but never really sat down
and got comfortable with the language. Working through all the examples
has made me *much* more comfortable with this style of programming. Despite
the humble tone and ambitions of the book I think I learned deeply.

The first 7 chapters were very straight forward, the end of chapter 8 took 
some more thought and I'm not sure how happy I am with the description of
collectors and continuations.

For a better description of the Y-combinator, see these `course notes 
<http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html>`_.

This book is followed by `The Seasoned Schemer <Seasoned+Schemer>`_
and The Reasoned Schemer.

Preface Definitions
------------------------
This primitive function is required for most of the functions in the book::

    (define atom?
      (lambda (x)
        (and (not (pair? x)) (not (null? x)))))

Laws
-----------------------
Law of Car
    The primitive *car* is defined only for non-empty lists.
 
Law of Cdr
    The primitive *cdr* is defined only for non-empty lists. The *cdr* of any 
    non-empty list is always another list.

Law of Cons
    The primitive *cons* takes two arguments. The second argument to *cons* 
    must be a list. The result is a list.

Law of Null?
    The primitive *null?* is defined only for lists.

Law of Eq?
    The primitive *eq?* takes two arguments. Each must be a non-numeric atom.

Commandments
------------------------

The First Commandment
    When recurring on a list of atoms, *lat*, ask two questions about it:
    *(null? lat)* and **else**. When recurring on a number, *n*, ask two
    questions about it: *(zero? n)* and **else**.

    When recurring on a list of S-expressions, *l*, ask three questions
    about it: *(null? l)*, *(atom? (car l))*, and **else**.

The Second Commandment
    Use *cons* to build lists.

The Third Commandment
    When building a list, describe the first typical element, and then
    *cons* it onto the natural recursion.

The Fourth Commandment
    Always change at least one argument while recurring. It must be changed to 
    be closer to termination. The changing argument must be tested in the 
    termination condition: 

    when using *cdr*, test termination with *null?* and

    when using *sub1*, test termination with *zero?*.

The Fifth Commandment
    When building a value with +, always use 0 for the value of the terminating
    line, for adding 0 does not change the value of an addition.
    
    When building a value with x, always use 1 for the value of the terminating
    line, for multiplying by 1 does not change the value of a multiplication.
    
    When building a value with cons, always consider () for the value of the
    terminating line.

The Sixth Commandment
    Simplify only after the function is correct.


The Seventh Commandment
    Recur on the subpart that are of the same nature:

    * on the sublists of a list.
    * on the subexpressions of an arithmetic expression.

The Eighth Commandment
    Use help functions to abstract from representations.

The Ninth Commandment
    Abstract common patterns with a new function.

The Tenth Commandment
    Build functions to collect more than one value at a time.