Introduction to Scheme
======================

Scheme_ is a popular dialect of Lisp_, a language developed in the 1950s and
1960s by `John McCarthy
<https://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)>`_ and his
students. Lisp_ is based on the `lambda calculus
<https://en.wikipedia.org/wiki/Lambda_calculus>`_, a mathematical formalism
for defining and executing functions.

Despite being so simple and not quite having achieved mainstream success on
its own, Lisp_ has proven to be an extremely flexible and powerful language,
and has been the source of ideas found in many other languages.


Getting Scheme
--------------

These notes will be using `MIT Scheme <https://www.gnu.org/software/mit-
scheme/>`_, a popular version of Scheme_ that is easy to use. 

To install MIT Scheme on Ubuntu Linux, run this command in a shell::

    $  sudo apt-get install mit-scheme

For other systems, see the `MIT Scheme <https://www.gnu.org/software/mit-
scheme/>`_ home page.


Running Scheme
--------------

Once it's installed, you can run it at the command-line like this::

    $ mit-scheme

    MIT/GNU Scheme running under GNU/Linux
    Type `^C' (control-C) followed by `H' to obtain information about interrupts.

    Copyright (C) 2011 Massachusetts Institute of Technology
    This is free software; see the source for copying conditions. There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    Image saved on Tuesday October 22, 2013 at 12:31:09 PM
      Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/i386 4.118
      Edwin 3.116

    1 ]=>

``]=>`` is the interpreter prompt, and means that it is waiting for you to
type something. So try this::

    1 ]=> (* 2 3 5)

    ;Value: 30

    1 ]=> 

The Scheme_ expression ``(* 2 3 5)`` calculates the product of 2, 3, and 5,
i.e. :math:`2 \cdot 3 \cdot 5 = 30`.

While it is possible to compile Scheme_, we will stick to just the interpreter
for this course.


Quitting Scheme
---------------

To exit the interpreter, type ctrl-d::

    1 ]=> 


    Kill Scheme (y or n)? Yes
    Moriturus te saluto.


Or by typing ``(exit)`` and return::

    1 ]=> (exit)


    Kill Scheme (y or n)? Yes
    Moriturus te saluto.


.. note:: The ending message "Moriturus te saluto." is Latin for "I who am
   about to die salute you."


Loading Files
-------------

We'll usually be putting Scheme_ functions in text files and then loading that
text file into the interpreter. For example, suppose the file ``circle.scm``
contains this::

    ;;; (circle-perim r) calculates perimeter of a circle of radius r
    (define circle-perim
        (lambda (radius) 
            (* 2 3.14 radius)
        )
    )

Then in Scheme_ we can load and run it like this::

    1 ]=> (load "circle.scm")

    1 ]=> (circle-perim 2)

    ;Value: 12.56

    1 ]=> 


Using Scheme in an Editor
-------------------------

While you can use MIT-Scheme directly at the command-line, it lacks many basic
editing features and so is a very unpleasant experience. Most programmers
prefer to run it directly in their text editor.

For example, if you are using Sublime Text as your editor, then you can
install `the SublimeREPL package <https://github.com/wuub/SublimeREPL>`_,
which lets you run an interpreter in a Sublime window.

Another popular editor for Lisp-like languages is Emacs, which comes already
to run Scheme_ in an editor window.


Using Scheme's Interactive Interpreter
--------------------------------------

We'll mostly be using Scheme_ via its interpreter, or **REPL**. REPL stands
for **read-eval-print loop**, and it lets us evaluate Scheme_ expressions one
at a time. For instance::

    1 ]=> (+ 3 2)

    ;Value: 5

    1 ]=> (* 10 4)

    ;Value: 40

    1 ]=> (- 5 8)

    ;Value: -3

    1 ]=> (/ 5 2)

    ;Value: 5/2

    1 ]=> (/ 6 2)

    ;Value: 3

    1 ]=> (/ 5 2)

    ;Value: 5/2   ;; 5/2 is a rational value


Right away you can see that Scheme_ is a bit different than most languages.
*All* functions in Scheme_ are called using **prefix notation**. This can seem
strange, at first, especially for arithmetic. Most languages use **infix**
notation for arithmetic expressions, e.g. ``3 + 2``, since that's we learn in
elementary school. However, when we evaluate functions, we normally use prefix
notation, e.g. ``f(2, 3)``. Scheme_ uses prefix notation for everything,
which, once you get used to it, is simple and consistent.

The other interesting feature of Scheme_ notation is that expressions are
always delineated by open ``(`` and closed ``)`` brackets. As you will see,
Scheme_ programs can end up having a *lot* of brackets, and making sure they
all match can be tricky.

You can pass multiple arguments to arithmetic operations::

    => (+ 1 2 3)
    6
    => (* 1 6 2 2)
    24
    => (/ 100 10 5)
    2
    => (- 1 2 3)
    -4

Or combine numbers and expressions::

    => (+ (- 1 2 3) (* 4 5))
    16

Notice that Scheme_ supports a rational numeric type, which is not common in
mainstream languages::

    1 ]=> (+ 1/2 1/2)

    ;Value: 1

    1 ]=> (+ 1/2 1/2 1/2)

    ;Value: 3/2


Number Basics
-------------

Lets look at the basic types of values in Scheme_.

The standard Scheme_ functions ``integer?``, ``rational?``, ``real?``,
``complex?``, and ``number?`` can be used to test for various kinds of
numbers. For example::

    ;;
    ;; integers
    ;;
    1 ]=> (integer? 5)

    ;Value: #t

    1 ]=> (integer? 6.0)

    ;Value: #t

    1 ]=> (integer? 6.1)

    ;Value: #f

    ;;
    ;; rationals
    ;;
    1 ]=> (rational? 6/3)

    ;Value: #t

    1 ]=> (rational? 6)

    ;Value: #t

    1 ]=> (rational? 6.1)

    ;Value: #t

    ;;
    ;; reals
    ;;
    1 ]=> (real? 2)

    ;Value: #t

    1 ]=> (real? 2.1)

    ;Value: #t

    1 ]=> (real? 6/17)

    ;Value: #t


    ;;
    ;; complex
    ;;
    1 ]=> (complex? 3.1+4i)

    ;Value: #t

    1 ]=> (complex? 3.1+0i)

    ;Value: #t

    1 ]=> (complex? 6)

    ;Value: #t

The value ``#t`` means true, and ``#f`` means false. The ``number?`` function
can be used to test if a value is any kind of number at all.

Here are a few handy built-in numerical functions: ``zero?``, ``positive?``,
``negative?``, ``odd?``, ``even?``. For example::

    1 ]=> (zero? (- 5 5))

    ;Value: #t

    1 ]=> (positive? (- 5 5))

    ;Value: #f

    1 ]=> (positive? 22)

    ;Value: #t

    1 ]=> (negative? 0)

    ;Value: #f

    1 ]=> (negative? -3)

    ;Value: #t

    1 ]=> (odd? 101)

    ;Value: #t

    1 ]=> (even? 2038)

    ;Value: #t

There's also ``min`` and ``max``::

    1 ]=> (min 8 3 -2 9 1 0)

    ;Value: -2

    1 ]=> (max 8 3 -2 9 1 0)

    ;Value: 9

See the `MIT Scheme documentation <https://www.gnu.org/software/mit-
scheme/documentation/mit-scheme-ref/Numerical-operations.html#Numerical-
operations>`_ for a list of the other mathematical functions.


Symbol Basics
-------------

Symbol are a kind of value that is not found in many other mainstream
languages. Use ``symbol?`` to test if a value is a symbol::

    1 ]=> (symbol? 'a)

    ;Value: #t

    1 ]=> (symbol? 'apple)

    ;Value: #t

    1 ]=> (symbol? 'first-ever-airplane)

    ;Value: #t

    1 ]=> (symbol? 4)

    ;Value: #f

    1 ]=> (symbol? odd?)

    ;Value: #f

    1 ]=> (symbol? x)

    ;Unbound variable: x

While they may look like strings, they are not. Symbols are just values with
names, and we don't usually care about their individual characters. Like other
Scheme_ names, symbol names cannot contain certain characters (such as
spaces).

Note the ``'`` in front of all the valid symbols. Quoting is an important part
of Scheme_, and it is necessary to distinguish a symbol from a variable. For
example, ``x`` is a variable, while ``'x'`` is a symbol::

    1 ]=> (symbol? 'x)

    ;Value: #t

    1 ]=> (symbol? x)

    ;Unbound variable: x

The expression ``(symbol? x)`` does not evaluate because Scheme_ does not know
about the variable ``x``.

Like numbers, symbols evaluate to themselves::

    1 ]=> 'a

    ;Value: a

    1 ]=> 'cat

    ;Value: cat

This contrasts with variables, which evaluate to the value they're bound to.

``define`` is one way to create new variables::

    1 ]=> (define pi 3.14)

    ;Value: pi

    1 ]=> pi

    ;Value: 3.14

    1 ]=> (* 2 pi)

    ;Value: 6.28

Here, ``pi`` is a variable bound to the value 3.14. Thus, ``pi`` evaluates to
3.14, and can be used anywhere a number is needed.

Notice also that the variable ``pi`` does *not* have a type. This is a key
feature of Scheme_: it is a weakly typed language, meaning that the type of
most expressions is not known until the expression is evaluated (in contrast
to more strongly typed languages where types are often known at compile-time).

``pi`` is not a symbol, it's a variable::

    1 ]=> (symbol? pi)    ;; pi is a variable

    ;Value: #f

    1 ]=> (symbol? 'pi)   ;; 'pi is a symbol

    ;Value: #t


Basics of Lists
---------------

A list is a sequence of 0, or more, values. The values an in a list can be any
Scheme_ value: numbers, symbols, other lists, etc.

As with symbols, literal lists usually begin with a ``'``::

    1 ]=> '(1 2 3)

    ;Value 13: (1 2 3)

    1 ]=> '(my dog has fleas)

    ;Value 14: (my dog has fleas)

    1 ]=> '(my dog (and hamster) have 10 fleas each))

    ;Value 15: (my dog (and hamster) have 10 fleas each)

The empty list is a list with 0 values in it, and is written as either ``()``
or ``'()``. Use ``null?`` to test if a list is empty::

    1 ]=> (null? '(1 2))

    ;Value: #f

    1 ]=> (null? '())

    ;Value: #t

If you try to evaluate a list with the ``'`` at the start, you will sometimes
get an error::

    1 ]=> (my dog has fleas)

    ;Unbound variable: fleas

By default, Scheme_ treats the first element of a list as a function, and the
remaining elements as inputs to that function. Since ``my`` is not bound to a
function (or anything at all!), Scheme_ reports an error.

Compare it to this example::

    1 ]=> (min 3 1)

    ;Value: 1

``(min 3 1)`` is an unquoted list, so Scheme_ assumes it is a function call.
It replaces the variable ``min`` with the function it is bound to, and then
passes 3 and 1 to it as parameters.

If you put a ``'`` in front of this list, then it evaluates to itself::

    1 ]=> '(min 3 1)

    ;Value 16: (min 3 1)

.. note:: Quoted lists are similar in spirit to strings in other languages.
   For example, in Go_, this statement prints 3::

      fmt.Println(1 + 2)

   But this statement prints ``"1 + 2"``:

      fmt.Println("1 + 2")

   The difference is that, on its own, ``1 + 2`` is an expression that
   evaluates to 3. But put it inside quotes, then it's just a string of 5
   characters that are not evaluated.

   Quoted lists are the same idea: the unquoted expression ``(+ 1 2)``
   evaluates to 3, while the quoted expression ``'(+ 1 2)`` evaluates to the
   list ``(+ 1 2)``.

Scheme_ lists are essentially singly-linked lists, and so that has a big
impact on their performance characteristics. 


List Processing
---------------

Scheme_ has a number of useful built-in list processing functions. When
thinking about the performance characteristics of these functions, keep in
mind that Scheme_ lists are essentially singly-linked lists.

The ``car`` function returns the first element of a list::

    1 ]=> (car '(1 2 3))

    ;Value: 1

    1 ]=> (car '((1 2) 3 4))

    ;Value 18: (1 2)

    1 ]=> (car '(my dog has fleas))

    ;Value: my

    1 ]=> (car '())

    ;The object (), passed as the first argument to car, is not the correct type.

The empty list has no first element, so ``(car '())`` is an error.

The ``cdr`` function returns everything on a list except for the first
element::

    1 ]=> (cdr '(1 2 3))

    ;Value 19: (2 3)

    1 ]=> (cdr '((1 2) 3 4))

    ;Value 20: (3 4)

    1 ]=> (cdr '(my dog has fleas))

    ;Value 21: (dog has fleas)

    1 ]=> (cdr '())

    ;The object (), passed as the first argument to cdr, is not the correct type.

.. note:: The names ``car`` and ``cdr`` are traditional, and refer to the
   underlying hardware of the original computer on which Lisp_ was first
   implemented.

   Some languages use the name ``first`` instead of ``car``, and ``rest``
   instead of ``cdr``.

The ``cons`` function returns a new list by adding a new element to the start
of the list::

    1 ]=> (cons 1 '(2 3))

    ;Value 22: (1 2 3)

    1 ]=> (cons '(2 3) '(3 4))

    ;Value 23: ((2 3) 3 4)

    1 ]=> (cons 'my '(dog has fleas))

    ;Value 24: (my dog has fleas)

    1 ]=> (cons 'x '())

    ;Value 25: (x)

``car``, ``cdr``, and ``cons`` work well together, e.g.::

    1 ]=> (cons (car '(1 2 3)) (cdr '(1 2 3)))

    ;Value 26: (1 2 3)

It's sometimes useful to think of a list as a nested series of calls to
``cons``. For example, the list ``'(a b c d)`` could be written like this::

    1 ]=> (cons 'a (cons 'b (cons 'c (cons 'd '()))))

    ;Value 27: (a b c d)

Recall that because Scheme_ implements lists as singly-linked lists, then
``car``, ``cdr``, and ``cons`` all run very quickly, no matter the size of the
list: they all run in worst-case :math:`O(1)` time.

Another convenient way to create a list is to use the ``list`` function::

    1 ]=> (list 1 2 3)

    ;Value 28: (1 2 3)

    1 ]=> (list '(1 2) 3 4)

    ;Value 29: ((1 2) 3 4)

    1 ]=> (list 'my 'dog 'has 'fleas)

    ;Value 30: (my dog has fleas)

    1 ]=> (list)

    ;Value: ()

These functions can be combined to many different useful things. For example,
the ``car`` of a lists ``cdr`` is its second element::

    1 ]=> (car (cdr '(a b c d)))

    ;Value: b

Be aware that Scheme_ expressions are quite general, so you can even do things
like this::

    1 ]=> ((car (list min max)) 41 2 3)

    ;Value: 2

To evaluate this entire expression, ``(car (list min max))`` is evaluated.
First, the sub-expression ``(list min max)`` evaluates to ``(list <min-fn>
<max-fn>)``, i.e. the variables ``min`` and ``max`` are replaced by the
functions they're bound to. Then ``(list <min-fn> <max-fn>)`` evaluates to the
list ``(<min-fn> <max-fn>)``. So ``(car (list min max))`` then becomes ``(car
(<min-fn> <max-fn))``, which is just ``<min-fn>``.


Functions
---------

Functions are the heart of Lisp_, and there are a number of ways to create
them. One way is to use ``defn``::

    (define add1
        (lambda (n) 
            (+ n 1)
        )
    )

This defines a function named ``add1`` that takes a single value, ``n``, as
input. It returns the value of ``(+ 1 n)``::

    1 ]=> (add1 5)

    ;Value: 6

    1 ]=> (add1 (add1 (add1 3)))

    ;Value: 6

Notice the type of ``n`` is not specified. Scheme_ is **dynamically typed**:
it doesn't check the type of ``n`` until run-time.

Here's another function::

    (define circle-area
        (lambda (radius)
            (* 3.14 radius radius)
        )
    )

    1 ]=> (circle-area 3)

    ;Value: 28.259999999999998

    1 ]=> (circle-area (add1 4))

    ;Value: 78.5

In the following function, ``p1`` and ``p2`` are assumed to both be of the
form  ``(x y)``::

    (define add-points 
        (lambda (p1 p2)
            (list (+ (first p1) (first p2))
                  (+ (second p1) (second p2))
            )
        )
    )

    1 ]=> (add-points '(2 1) '(5 9))

    ;Value 11: (7 10)


Logical Expressions
-------------------

You can use ``and``, ``or``, and ``not`` to evaluate logical expressions in
Scheme_. For example::

    (define all-diff? 
        (lambda (x y z)
            (and (not (equal? x y))
                 (not (equal? x z))
                 (not (equal? y z))
            )
        )
    )

    1 ]=> (all-diff? 1 2 1)

    ;Value: #f

    1 ]=> (all-diff? 1 2 -5)

    ;Value: #t

``and`` is what is known in Scheme_ as a **special form**. It is different
than an ordinary function because it does **not** immediately evaluate the
expressions passed to it. Instead, ``and`` evaluates the expression one at a
time from left to right, and stops immediately after the first expression that
evaluates to false; none of the expressions after this are evaluated.

``or`` is also a special form, e.g.::

    (define any-same? 
        (lambda (x y z)
            (or (equal? x y)
                (equal? x z)
                (equal? y z)
            )
        )
    )

    1 ]=> (any-same? 3 5 3)

    ;Value: #t

    1 ]=> (any-same? 3 5 13)

    ;Value: #f

Similar to ``and``, the ``or`` special form evaluates its inputs one at a
time, from left to right, stopping after finding the first true expression
(and not evaluating anything after that).

``not`` works as expected, i.e. it flips true to false and false to true::

    (define any-same2?
        (lambda (x y z)
            (not (all-diff? x y z))
        )
    )


Decisions with cond
-------------------

``cond`` is a special form in Scheme_ that it is similar to if-else structures
in other languages. Consider this function::

    (define sign
        (lambda (n)
            (cond ((< n 0) 'negative)
                  ((= n 0) 'zero)
                  (#t      'positive)
            )
        )
    )

    1 ]=> (sign -4)

    ;Value: negative

    1 ]=> (sign 0)

    ;Value: zero

    1 ]=> (sign 5)

    ;Value: positive


A ``cond`` expression consists of a number of 2-element ``(test value)``
lists. For example, ``(< n 0)`` is a test, and ``'negative`` is it's
corresponding value.

``cond`` evaluates its pairs one at a time in left to right order. If a test
evaluates to true, its corresponding value is returned, and the which always
evaluates to ``true``, and so its corresponding value is always returned if
it's reach. It serves the same purpose as an else clause in an if-else
statement.

Instead of ``#t`` in the final test, you can also use ``else``::

    (define sign
        (lambda (n)
            (cond ((< n 0) 'negative)
                  ((= n 0) 'zero)
                  (else    'positive)
            )
        )
    )


Recursive Functions
-------------------

If you want to determine the length of a list, Scheme_ provides a built-in
``length`` function::

    1 ]=> (length '(1 (2 3) 4))

    ;Value: 3

We could also write our own function using recursion like this::

    (define len
        (lambda (lst)
            (cond
                ((null? lst) 0)             ;; base case
                (#t (+ 1 (len (cdr lst))))  ;; recursive case
            )
        )
    )

``len`` has two cases:

- base case: when the list ``lst`` is empty

- recursive case: calculate the length of the ``cdr`` of ``lst``, then add 1

As you can see, you must take care to get all the parentheses to match!


Here's another good example of recursion::

    ;; Returns true if x is in lst, and false otherwise.
    (define member
        (lambda (x lst)
            (cond
                ((null? lst)          #f)
                ((equal? x (car lst)) #t)
                (#t                   (member x (cdr lst)))
            )
        )
    )

Recall that the ``symbol?`` functions tests if an object is a symbol (such as
``'cat``). The following function returns the number of symbols in a list::

    (define count-sym
        (lambda (lst)
            (cond
                ((null? lst)         0)
                ((symbol? (car lst)) (+ 1 (count-sym (cdr lst))))
                (#t                  (count-sym (cdr lst)))
            )
        )
    )

If instead we want to count how many numbers are in a list, a small
modification to ``count-sym`` is all that's needed::

    (define count-num
        (lambda (lst)
            (cond
                ((null? lst)         0)
                ((number? (car lst)) (+ 1 (count-num (cdr lst))))
                (#t                  (count-num (cdr lst)))
            )
        )
    )

Compared to ``count-sym``, ``count-num`` is the same except for two
differences: ``number?`` is used instead of ``symbol?``, and each occurrence
of ``count-sym`` has been changed to ``count-num``.

So what we can do is write a general-purpose counting function that takes a
list and a predicate function (i.e. a function that takes one value as input
and returns a boolean value) as input::

    (define count-fn
        (lambda (fn? lst)
            (cond
                ((null? lst)     0)
                ((fn? (car lst)) (+ 1 (count-fn fn? (cdr lst))))
                (#t              (count-fn fn? (cdr lst)))
            )
        )
    )

To use it we pass in any function that takes a single input value and returns
either ``true`` or ``false``::

    1 ]=> (count-fn even? '(1 2 3 4 5 6 7))

    ;Value: 3

    1 ]=> (count-fn odd? '(1 2 3 4 5 6 7))

    ;Value: 4

    1 ]=> (count-fn number? '(1 2 3 4 5 6 7))

    ;Value: 7

    1 ]=> (count-fn symbol? '(1 2 3 4 5 6 7))

    ;Value: 0

Using count-fn, it is easy to re-write the previous functions like this::

    (define count-symbol (lambda (lst) (count-fn symbol? lst)))

    (define count-number (lambda (lst) (count-fn number? lst)))


More Examples
-------------

::

    ;;
    ;; Remove all top-level occurrences of x from lst.
    ;;
    (define remove-all
        (lambda (x lst)
            (cond
                ((null? lst)
                    '())
                ((equal? x (car lst))
                    (remove-all x (cdr lst)))
                (else
                    (cons (car lst) (remove-all x (cdr lst))))
            )
        )
    )

    ;;
    ;; Replace all top-level occurrences of 'clinton with 'trump.
    ;;
    (define trumpify
        (lambda (lst)
            (cond
                ((null? lst) 
                    '())
                ((equal? 'clinton (car lst))
                    (cons 'trump (trumpify (cdr lst))))
                (else
                    (cons (car lst) (trumpify (cdr lst))))
            )
        )
    )

    ;;
    ;; Replace all top-level occurrences of old with new.
    ;;
    (define replace
        (lambda (old new lst)
            (cond
                ((null? lst) 
                    '())
                ((equal? old (car lst))
                    (cons new (replace old new (cdr lst))))
                (else
                    (cons (car lst) (replace old new (cdr lst))))
            )
        )
    )

    ;;
    ;; Returns a function that, when called, replaces all occurrences of old
    ;; with new on a given list.
    ;;
    (define make-replacer
        (lambda (old new)
            (lambda (lst) (replace old new lst))
        )
    )

    ;;
    ;; Returns the number of numbers on lst, even numbers inside of lists.
    ;;
    (define deep-count-num
        (lambda (lst)
            (cond
                ((null? lst)
                    0)
                ((list? (car lst))
                    (+ (deep-count-num (car lst)) (deep-count-num (cdr lst))))
                ((number? (car lst))
                    (+ 1 (deep-count-num (cdr lst))))
                (else
                    (deep-count-num (cdr lst)))
            )
        )
    )

Lambda Functions
----------------

In Scheme_, a **lambda function** is essentially a function without a name.
We've been using lambda functions to define named functions, so you should be
somewhat familiar with them. 

Here's a lambda function that adds 1 to its input::

    (lambda (n) (+ n 1))

This function takes one input which it names ``n``, and returns the value of
``n + 1``. Notice that the function has no name! So to call it, you must do
something like this::

    ((lambda (n) (+ n 1)) 5)

This passes 5 to the lambda function, and so the entire expression evaluates
to 6.

Lambda functions are often a convenient way to write small functions. For
example, suppose we want to count how many times 2 or 5 occurs in a list. Then
we could do it like this::

    (count-fn (lambda (n) (or (= n 2) (= n 5))) 
              '(2 2 6 5 7 5 2 1)
    )

Once you get the hang of them, using lambda functions in this way is often
very convenient.


Here's another example where lambda functions are useful. The ``keep-if``
function returns a list containing all the elements of a given list that match
a given test function::

    (define keep-if 
        (lambda (pred? lst)
            (cond
                ((null? lst)
                    '())
                ((pred? (car lst))
                    (cons (car lst) (keep-if pred? (cdr lst))))
                (else
                    (keep-if pred? (cdr lst)))
            )
        )
    )

    1 ]=> (keep-if even? '(1 2 3 4 5))

    ;Value 13: (2 4)

    1 ]=> (keep-if (lambda (n) (or (= n 1) (even? n))) '(1 2 3 4 5))

    ;Value 14: (1 2 4)

Here's an expression that partitions a list of numbers so that all the evens
come before all the odds::

    1 ]=> (append (keep-if even? '(1 2 3 4 5)) (keep-if odd? '(1 2 3 4 5)))

    ;Value 18: (2 4 1 3 5)

The ``append`` function appends two (or more) lists together to form a single
list. 

We can write this as a function::

    (define parity-partition
        (lambda (nums)
            (append (keep-if even? nums) (keep-if odd? nums))
        )
    )

    1 ]=> (parity-partition '(1 2 3 4 5))

    ;Value 21: (2 4 1 3 5)

Note that Scheme_ has a built-in function called ``filter`` that does the same
thing as ``keep-if``.

Another useful function is called ``map``: it applies a function to each
element of a list. Scheme_ already has a ``map`` function built in, but lets
write our own version called ``mymap``::

    (define mymap
        (lambda (f lst)
            (cond
                ((null? lst)
                    '())
                (else
                    (cons (f (car lst)) (mymap f (cdr lst))))
            )
        )
    )

    1 ]=> (mymap (lambda (n) (* n n)) '(1 2 3))

    ;Value 23: (1 4 9)

    1 ]=> (mymap list '(1 2 3))

    ;Value 24: ((1) (2) (3))

Notice that the function, ``f``, that is passed into ``mymap`` takes one item
as input. The idea is that ``f`` is applied to every element of the list, e.g.
``(mymap f (a b c d))`` returns ``((f a) (f b) (f c) (f d))``. Thus, it is
similar to a loop in other languages.


Folding a List
--------------

Consider the following function for summing a list of numbers::

    (define sum-list
        (lambda (nums)
            (cond
                ((null? nums)
                    0)
                (else
                    (+ (car nums) (sum-list (cdr nums))))
            )
        )
    )

    1 ]=> (sum-list '(1 4 2))

    ;Value: 7

Compare it to this function that calculates the product of a list of numbers::

    (define prod-list
        (lambda (nums)
            (cond
                ((null? nums)
                    1)
                (else
                    (* (car nums) (prod-list (cdr nums))))
            )
        )
    )

    1 ]=> (prod-list '(1 4 2))

    ;Value: 8

``sum-list`` and ``prod-list`` are very similar. There are three main
differences. First, notice that ``sum-list`` returns 0 for an empty list,
while ``prod-list`` returns 1. Second, in the recursive case, ``sum-list`` use
``+`` and ``prod-list`` uses ``*``. Finally, the names of the recursive calls
are different.

Now lets write a general-purpose function that implements this pattern, taking
the base case value and function to be passed in as parameters::

    (define my-fold
        (lambda (f empty-val lst)
            (cond
                ((null? lst)
                    empty-val)
                (else
                    (f (car lst) (my-fold f empty-val (cdr lst))))
            )
        )
    )

    1 ]=> (my-fold + 0 '(1 2 4))

    ;Value: 7

    1 ]=> (my-fold * 1 '(1 2 4))

    ;Value: 8

In Scheme_, there are a number of  built-in functions similar to ``my-fold``,
such as  ``reduce-left``, ``reduce-right``, ``fold-left``, and ``fold-right``.
Each of these functions implements a variation of the same essential pattern
as ``my-fold``.

An interesting way to think about ``my-fold`` is to see what it does to a list
when it is expanded into nested calls to ``cons``. For example, we can write
the list ``(1 4 2)`` in the form ``(cons 1 (cons 4 (cons 2 ())))``. When you
call ``my-fold`` on it, it as if each ``cons`` is replaced by ``f``, and the
empty list is replaced by ``empty-val``. For example::

      (my-fold + 0 '(1 4 2))
    = (my-fold + 0 (cons 1 (cons 4 (cons 2 ()))))
    = (+ 1 (+ 4 (+ 2 0))
    = 7

And::

      (my-fold * 1 '(1 4 2))
    = (my-fold * 1 (cons 1 (cons 4 (cons 2 ()))))
    = (* 1 (* 4 (* 2 1))
    = 8

With this trick in mind, it is easy to see, for instance, that ``(my-fold cons
() lst)`` returns ``lst`` itself.

It is also worth noting that the order in which ``my-fold`` evaluates its list
is from right to left, i.e. the first things that get evaluated are the last
element of ``lst`` and ``empty-val``. Thus, this version of ``my-fold`` is
sometimes called a *right fold* (sometimes abbreviated ``foldr``).

For functions like ``+`` and ``*`` the order of evaluation doesn't matter
much, but it might for other functions. So another way to fold a list is from
left to right (a *left fold*)::

    (define my-fold-left
        (lambda (f z lst)
            (cond
                ((null? lst)
                    z)
                (else
                    (my-fold-left f (f z (car lst)) (cdr lst)))
            )
        )
    )

Here's a trace::

      (my-fold-left + 0                   '(1 4 2))
    = (my-fold-left + (+ 0 1)             '(4 2))
    = (my-fold-left + (+ (+ 0 1) 4))      '(2))
    = (my-fold-left + (+ (+ (+ 0 1) 4) 2) '())
    = (+ (+ (+ 0 1) 4) 2)
    = 7

An advantage of ``my-fold-left`` over ``my-fold`` (i.e. a right fold) is that
the final function call of ``my-fold-left`` is a recursive call to ``my-fold-
left`` itself. This is an instance of **tail recursion**, and it is important
because Scheme_ automatically converts such recursion to a loop, thus avoiding
the use of the call stack. In contrast, the last function called in ``my-
fold`` function is to ``f``, and so it must use the stack because there is no
general-purpose way to replace its recursive calls with a loop that avoids
using a linear amount of memory. Thus ``my-fold`` can run out of memory on
large lists that ``my-fold-left`` can handle without a problem.


Let
---

An important and useful feature of Scheme_ is the ``let`` environment. Using
``let``, you can bind values to variables. For example::

    (define operator
        (lambda (e)
            (let ((op (car e))
                 )
                (cond
                    ((equal? op '+) 'addition)
                    ((equal? op '-) 'subtraction)
                    ((equal? op '*) 'multiplication)
                    ((equal? op '/) 'division)
                    (else 'unknown)
                )
            )
        )
    )

    1 ]=> (operator '(+ 1 2 3))

    ;Value: addition

    1 ]=> (operator '(/ 1 2 3))

    ;Value: division

We assign the first element of the list ``e`` to ``op`` so that we don't have
to keep re-calculating it. Once a symbol is assigned in a ``let``, it cannot
be changed.

Here's another example that evaluates numeric expressions of the form ``(left
op right)``::

    (define eval-basic
        (lambda (e)
            (let ((left (car e))
                  (op (car (cdr e)))
                  (right (car (cdr (cdr e))))
                 )
                (cond
                    ((equal? op '+) (+ left right))
                    ((equal? op '-) (- left right))
                    ((equal? op '*) (* left right))
                    ((equal? op '/) (/ left right))
                    (else 'err)
                )
            )
        )
    )

    1 ]=> (eval-basic '(1 + 2))

    ;Value: 3

    1 ]=> (eval-basic '(1 - 2))

    ;Value: -1

Another example where a let-environment is in the ``deepmap`` function.
``deepmap`` is a variation on ``map`` that works like ``map``, except the
passed-in mapping function is applied to every non-list value on the list,
even those nested inside lists. For example::

    1 ]=> (deepmap 1+ '(1 (2 (1 1)) 3))

    ;Value 31: (2 (3 (2 2)) 4)

Here's a definition for ``deepmap``::

    (define deepmap 
        (lambda (f lst)
            (cond 
                ((null? lst) 
                    ())
                (else 
                    (let* ((head (car lst))
                           (body (cdr lst))
                           (new_body (deepmap f body))
                          )
                        (cond
                            ((list? head) 
                                (cons (deepmap f head) new_body))
                            (else
                                (cons (f head) new_body))
                        )
                    )
                )
            )
        )
    )

Notice that this uses ``let*`` instead of ``let``. That's because binding for
``new_body`` uses ``body``, which is defined in the same let-environment. If
we had used a regular ``let``, then we'd get an error saying ``body`` is
unbound. ``let*`` is designed specifically to allow already-bound variables to
be used.


An Expression Evaluator
-----------------------

The ``eval-basic`` function given in the previous section only evaluates
expressions of the form ``(num op num)``, where ``num`` is a number. But it is
not much more work to evaluate *any* arithmetic expression of the form ``(expr
op expr)``::

    (define my-eval
        (lambda (e)
            (cond
                ((number? e)
                    e)
                (else
                    (let ((left (my-eval (car e)))
                          (op (car (cdr e)))
                          (right (my-eval (car (cdr (cdr e)))))
                         )
                        (cond
                            ((equal? op '+) (+ left right))
                            ((equal? op '-) (- left right))
                            ((equal? op '*) (* left right))
                            ((equal? op '/) (/ left right))
    ))))))  ;; closing brackets all on one live to save space


    1 ]=> (my-eval '(2 * (2 + 3)))

    ;Value: 10

    1 ]=> (my-eval '((10 - 5) / (2 * (2 + 3))))

    ;Value: 1/2

This is a recursive function: the expressions assigned to ``left`` and
``right`` both call ``my-eval`` recursively.

The expression ``(car (cdr e))`` returns the second element of ``e``. A short-
hand way to write this is ``(cadr e)``; notice how the ``a`` and the ``d`` of
``cadr`` mirror the order of those letters in ``car`` and ``cdr``. Similarly,
the expression ``(car (cdr (cdr e)))`` can be re-written as ``(caddr e)``.


A Propositional Expression Evaluator
------------------------------------

Lets write another evaluator, this time for infix propositional expressions
like ``(t and (not f))``. We will assume that the symbols ``t`` and ``f``
stand for true and false respectively, and that there no variables allowed in
the expressions.

First, we define a series of functions that test if an object has a particular
form::

    (define is-literal?
        (lambda (e)
            (or (equal? e 't) (equal? e 'f))
        )
    )

    ;; returns true iff lst is a list of length n
    (define nlist
        (lambda (n lst)
            (and (list? lst) 
                 (= n (length lst))
            )
        )
    )

    ;; (not expr)
    (define is-not?
        (lambda (e)
            (and (nlist 2 e)
                 (equal? 'not (car e))
            )
        )
    )

    ;; (and expr)
    (define is-and?
        (lambda (e)
            (and (nlist 3 e)
                 (equal? 'and (cadr e))
            )
        )
    )

    ;; (or expr)
    (define is-or?
        (lambda (e)
            (and (nlist 3 e)
                 (equal? 'or (cadr e))
            )
        )
    )

These are all non-recursive functions that check that the top-level form of an
expressions is correct. They don't go into the sub-expressions.

Next, lets write a function that tests if an expression is a valid
proposition::

    ;; Returns true iff e is a valid propositional expression.
    (define is-expr?
        (lambda (e)
            (cond
                ((is-literal? e)
                    #t)
                ((is-not? e)
                    (is-expr? (cadr e)))
                ((is-and? e)
                    (and (is-expr? (car e)) (is-expr? (third e))))
                ((is-or? e)
                    (and (is-expr? (car e)) (is-expr? (third e))))
                ((is-nand? e)
                    (and (is-expr? (car e)) (is-expr? (third e))))
                (else
                    #f)
            )
        )
    )

The idea of this function is to first check that ``e`` has a valid top-level
form, and to then recursively check that its sub-expressions are also valid.

Next, lets write an evaluator that calculates whether the value of a valid
proposition::

    (define eval-prop-bool
        (lambda (e)
            (cond
                ((is-literal? e)
                    (equal? e 't))
                ((is-not? e)  ;; (not expr)
                    (not (eval-prop-bool (second e))))
                ((is-and? e)  ;; (expr and expr)
                    (and (eval-prop-bool (first e)) (eval-prop-bool (third e))))
                ((is-or? e)   ;; (expr or expr)
                    (or (eval-prop-bool (first e)) (eval-prop-bool (third e))))
                (else
                    #f)
            )
        )
    )

    (define eval-prop
        (lambda (e)
            (if (eval-prop-bool e) 't 'f)
        )
    )

For example::

    1 ]=> (eval-prop '((not t) and (t or (not f))))

    ;Value: f


Simplifying a Propositional Expression
--------------------------------------

Something else we can do with a propositional expression is to simplify it.
For example, any propositional expression of the form ``(not (not p))`` can be
simplified to ``p``.

Lets write a simplifier that applies this rule to expressions::

    ;; double negation elimination
    ;; (not (not expr)) ==> expr
    (define simplify
        (lambda (e)
            (cond
                ((is-literal? e)
                    e)
                ;; (not (not e))
                ((and (is-not? e) (is-not? (second e)))
                    (simplify (second (second e))))
                ((is-not? e)
                    (list 'not (simplify (second e))))
                ((is-and? e)
                    (list (simplify (first e)) 'and (simplify (third e))))
                ((is-or? e)
                    (list (simplify (first e)) 'or (simplify (third e))))
                (else
                    'error)
            )
        )
    )

``simplify`` first checks if ``e`` is of the form ``(not (not X))``. If so,
then it extracts the ``X`` (using ``(second (second e))``) and returns the
simplification of it. Otherwise, it tries to simplify the parts of the sub-
expressions (if any) of ``e``.

For example::

    1 ]=> (simplify '((not (not t)) and (not (not t))))

    ;Value 34: (t and t)


Rewriting an Expression with Only nand
--------------------------------------

An basic fact about propositional logic is that any expression can be re-
written using just the ``nand`` operator. The expression ``(p nand q)`` is
true just when either ``p``, or ``q``, or both, are false. In other words,
``(p nand q)`` is equivalent to ``(not (p and q))``.

Here are the rules for writing propositional expressions using just ``and``:

- ``(not p)`` is logically equivalent to ``(p nand p)``

- ``(p and q)`` is logically equivalent to ``((p nand q) nand (p nand q))``

- ``(p or q)`` is logically equivalent to ``((p nand p) nand (q nand q))``

These rules are enough to transform any propositional expression into a
logically equivalent one using only ``nand``.

Here's some code that does the transformation::

    (define is-prop-literal?
        (lambda (x)
            (symbol? x)
        )
    )

    (define make-nand
        (lambda (p q)
            (list p 'nand q)
        )
    )

    ;; Rewrites propositional logic expression e to a logically equivalent
    ;; expression that uses "nand" as the only connective.
    (define nand-rewrite
        (lambda (e)
            (cond
                ((is-prop-literal? e)
                    e)
                ((is-not? e)
                    (let ((np (nand-rewrite (second e)))
                         )
                         (make-nand np np)))
                ((is-and? e) 
                    (let* ((p (nand-rewrite (first e)))
                           (q (nand-rewrite (third e)))
                           (pnq (make-nand p q))
                          )
                        (make-nand pnq pnq)))            
                ((is-or? e)
                    (let* ((p (nand-rewrite (first e)))
                           (q (nand-rewrite (third e)))
                           (pnp (make-nand p p))
                           (qnq (make-nand q q))
                          )
                        (make-nand pnp qnq)))
            )
        )
    )

    1 ]=> (pp (nand-rewrite '((p and q) or ((not p) or q))))
    ((((p nand q) nand (p nand q)) nand ((p nand q) nand (p nand q)))
     nand
     ((((p nand p) nand (p nand p)) nand (q nand q))
      nand
      (((p nand p) nand (p nand p)) nand (q nand q))))

Note the use of the ``pp`` function: it "pretty prints" a Scheme_ expression,
making it is easier for humans to read.

Lisp_ is often a good choice for writing language-processing code as in the
last couple of examples. Non-recursive versions of these functions would be
much harder to write and understand. Thus, Lisp is often a good language for
experimenting with new programming ideas, especially if they can be
implemented in an interpreter.


Example: Binary Search Trees
----------------------------

The following is a sample Scheme_ implementation of a basic binary search
tree's.

::

    ;;; bst.scm

    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    ;;
    ;; An implementation of a binary search tree (BST). Nodes are lists of the
    ;; form (value left-tree right-tree).
    ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    ;; '() is the empty tree
    (define is-empty? (lambda (t) (null? t)))

    ;; getters
    (define value (lambda (node) (first node)))
    (define left (lambda (node) (second node)))
    (define right (lambda (node) (third node)))

    ;; insert value x into tree t
    (define insert 
        (lambda (x t)
            (if (is-empty? t)
                (list x '() '())
                (let ((V (value t))
                      (L (left t))
                      (R (right t))
                     )
                    (cond
                        ((is-empty? t)
                            (list x '() '()))
                        ((= x V) ;; x already in the tree, so do nothing
                            t)
                        ((< x V)
                            (list V (insert x L) R))
                        (else
                            (list V L (insert x R)))
                    )
                )
            ) 
        )
    )

    ;; convert a list of things into a tree
    (define make-tree
        (lambda (lst)
            (if (null? lst)
                '()
                (insert (car lst) (make-tree (cdr lst))))))


    ;; return a list of the values of tree in "inorder" order, i.e. for
    ;; a BST the list of values will be in ascending sorted order
    (define list-inorder 
        (lambda (t)
            (cond
                ((is-empty? t) '())
                (else (append (list-inorder (left t))
                              (list (value t))
                              (list-inorder (right t))))
            )
        )
    )

    (define treesort
        (lambda (lst)
            (list-inorder (make-tree lst))
        )
    )

    ;; Returns the depth of a tree
    (define depth
        (lambda (t)
            (cond
                ((is-empty? t)
                    0)
                (else
                    (+ 1 (max (depth (left t)) (depth (right t))))
                )
            )
        )
    )

    ;; return the max value in a tree
    (define tree-max 
        (lambda (t)
            (cond
                ((is-empty? t)
                    'error)
                ((is-empty? (right t)) 
                    (value t))
                (else
                    (tree-max (right t)))
            )
        )
    )

    ;; test if x is a value in tree t
    (define contains 
        (lambda (x t)
            (cond
                ((is-empty? t)  
                    #f)
                ((= x (value t)) 
                    #t)
                ((< x (value t)) 
                    (contains x (left t)))
                (else              
                    (contains x (right t)))
            )
        )
    )