Continuing with Scheme, possibly moving on to some lambda calculus if we have time.

More Scheme

Adding to a list

Last time we saw making a list with the list function. But how do we add to a list?

Answer: use cons. (cons x L) returns a new list whose first element is x and whose subsequent elements are the elements of L.

> (cons 3 '(4 5 6))
(3 4 5 6)

> (define L '(hello goodbye))
> L
(hello goodbye)
> (cons 'seeya L)
(seeya hello goodbye)
> L
(hello goodbye)
> ; Note that this does not change the value of L,
> ; because variables can't change.

Also, an important side-note: Scheme is case-insensitive:

> l
(hello goodbye)

Let’s try an example using it. How would you define a function (numsfrom N M) that returns a list of the numbers from N to M?

Remember your recursive thinking:

(define (numsfrom N M)
    (if (= N M)
        (list M) ; Base case
        (cons N (numsfrom (+ N 1) M)) ; Recursive case
    )
)

Accessing elements of a list

There are only two functions that handle accessing elements of a list: one gives you the first element of a list, and one gives you a list containing everything but the first element. The first is car, and the second is cdr.

> (car '(2 4 6 8))
2
> (cdr '(2 4 6 8))
(4 6 8)

Other languages often call this “first” and “rest”, or “head” and “tail”. The names in Lisp are historical, having to do with the names of registers used in the machine where the first implementation of Lisp was made. The pointer to the first element was stored in the “address register” and the pointer to the rest of the list was stored in the “decrement register”. Thus, contents of the address register, and contents of the decrement register.

More useful list functions

Checking whether a list is empty can be done using the null? function.

> (null? '()) ; Returns true
#t
> (null? '(2 3 4)) ; Returns false
#f

Putting it all together

Let’s write a function that takes a list and returns its length. Remember, think recursively.

(define (mylength L)
    (if (null? L)
        0
        (+ 1 (mylength (cdr L)))
    )
)

Note that this function doesn’t count nested lists:

> (mylength '(1 2 (3 4) 5))
4

Concatenating two lists

You can use append to join two lists into one list:

(append '(1 2 3) '(4 5 6))

But note that unlike the functions we’ve seen so far, append isn’t a primitive function, and in fact is easy to write using only car, cdr, and cons.

Thinking recursively, the base case is that when the first list is empty, the result is the second list. The recursive hypothesis is that appending the cdr of L1 to L2 will work. And the recursive case, assuming the recursive hypothesis, is that you can cons on the front element from L1 and trust the recursion to handle the rest.

(define (myappend L1 L2)
    (if (null? L1)
        L2
        (cons (car L1) (myappend (cdr L1) L2))
    )
)

Note that this is an O(N) algorithm: cons, car, and cdr are all constant-time operations, and you end up making (length L1) recursive calls.

Reversing a list

Use the function reverse.

> L
(hello goodbye)
> (reverse L)
(goodbye hello)

We can define this one ourselves as well:

(define (myreverse L)
    (if (null? L)
        '()
        (append (myreverse (cdr L)) (list (car L)))
    )
)

Note that this is a quadratic algorithm: append is linear in the size of its first parameter, and you’re calling that (length L) times. That seems pretty inefficient. Can we make it faster?

In fact we can, by building a new list as we go. For that, we need a helper function to move the elements from one list to another.

(define (rev L result)
    ; This function will move all elements
    ; from L to result in reverse order
    (if (null? L)
        result ; Base case: this is the reversed list
        (rev ; Recursively call our helper
            ; With the tail of L
            (cdr L)
            ; And the head of L prepended to the result
            (cons (car L) result))
    )
)

(define (myreverse L)
    (rev L '()) ; Call our helper.
)

And this is linear-time.

Nested scope

You can use let to define a new scope with some new things defined.

(let ((x 10) (y 15)) ; x and y are only defined within
                     ; this scope. Note that the value of
                     ; y cannot depend on the value of x,
                     ; as these variables are assigned
                     ; simultaneously.
    (+ x (* y 2)) ; This is the body of the let-expression,
                  ; this result is what's returned.
)

If you need the variables to be assigned in order, and you don’t want to define a bunch of nested lets, you can use let*:

(let* ((x 10) (y (+ x 5)) (z (* y 2))) ; This works
    (+ x y z) ; Returns 55
)

Note this consequence of this behaviour, though:

> (define x 100)
> (let ((x 10) (y (+ x 5))) (+ x y))
115
> (let* ((x 10) (y (+ x 5))) (+ x y))
25

This is because in the let case, the x in the definition of y is the x in the outer scope.

First-class functions

Functions can be used as any other values. You can even put them into lists.

> (define (add1 x) (+ x 1))
> (define (sub1 x) (- x 1))
> (list add1 sub1)
(#<procedure:add1> #<procedure:sub1>)
> (define fnlist (list add1 sub1))
> (car fnlist)
#<procedure:add1>
> (cdr fnlist)
(#<procedure:sub1>)
> ((car fnlist) 10) ; Calls add1
11

Note the last line: for the first element in the list, you can have an expression that evaluates to a function.

Higher-order functions

A function that takes another function as a parameter is a higher-order function. For example:

> (define (bigger f x)
    (f (+ x 1)))
> (bigger add1 10)
12

There’s a useful built-in higher-order function called map. It takes in a function and a list, applies the function to every element of the list, and returns a list of the results.

> (map sub1 '(2 4 6 8))
(1 3 5 7)

We can define map ourselves as well, since it’s not primitive:

(define (mymap f L)
    (if (null? L)
        '()
        (cons (f (car L)) (mymap f (cdr L)))
    )
)

Anonymous functions

What if you wanted to double every element of a list? Would you have to define a named function, maybe called double, to map it? No: you can create an expression that returns an anonymous function, using the lambda keyword.

> (map (lambda (x) (* x 2)) '(1 2 3 4 5))
(2 4 6 8 10)

The overall syntax for this is (lambda (arguments) body).

More higher-order functions

Functions can also return other functions:

(define (choose x)
    (if (<= x 0)
        add1
        sub1
    )
)

Or, alternately:

(define (choose x)
    (if (<= x 0)
        (lambda (y) (+ y 1))
        (lambda (y) (- y 1))
    )
)

And then:

> ((choose 5) 30) ; Calls sub1 or its equivalent
29

Here’s another example:

> (define (makeadder z)
    (lambda (x) (+ x z)))
> (define add50 (makeadder 50))
> (add50 10)
60

And note that Scheme is statically-scoped. Even if you had (define z 100) above the first line of the definition, the z in the function will still refer to the argument of makeadder, even though makeadder has totally been popped off the stack. This does mean, however, that some variables, like our z, have to be copied to the heap.

Lies

We’ve been lied to. Scheme isn’t a purely functional language. Scheme still allows assignment and modification of variables. Don’t use them, at least not for this course.

Non-functional features of Scheme

set! modifies an existing variable.

> (define z 100)
> z
100
> (set! z (+ z 1))
> z
101
> (set! z (+ z 1))
> z
102

set-car! modifies the head element of a list. set-cdr! sets its tail.

> (define L '(1 2 3 4))
> (set-car! L 56)
> L
(56 2 3 4)
> (set-cdr! L '(9 10 11))
> L
(56 9 10 11)

Note that you can do abject nonsense with this, yet another reason why you don’t want to do this:

> (set-cdr! L L)
> L
#0=(56 . #0#)

Older implementations would infinite loop when you attempt to print L. Here, we get… this.

The lists in Scheme are just linked lists, and what you’re doing is setting the pointer for the cdr of L to just be a pointer back to L. This implementation of Scheme is smart enough to detect the cycle.

That’s all for today.