Introduction to Scheme

§1. Historical background

John McCarthy developed LISP in 1958, just a few years after the introduction of the first programming language, FORTRAN. McCarthy actually intended to develop a more complex language, but he started by developing an engine that accepted a very simple language as its input. That simple language — what we now know as LISP — took off, and McCarthy never got around to his more complex language. The name LISP stands for LISt Processor, because the language depends so heavily on lists.

McCarthy's initial version wasn't really intended as an end product and it had some problems Over the years, there have been many alternative LISP versions designed to repair shortcomings, real and perceived, in McCarthy's language. One of the most notable of these is Scheme, developed in the 1970's. Scheme is basically a clean version of LISP, emphasizing a small, well-designed core of functionality.

§2. Basic syntax

Scheme programs are built up of two concepts, the atom and the list. An atom is a simple word-like item, such as sqrt or 5 or +, while a list is a sequence of lists or atoms enclosed in parentheses, with the individual elements separated by spaces. The following is a list written in Scheme-like notation.

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

This represents a list of four elements, in which the first is a list of two elements, the second is the atom 3, the third is a list of three elements (of which the second and third elements are lists), and the fourth is the atom 6.

In evaluating an expression, Scheme consistently uses parentheses to indicate function applications. In mathematics and most programming languages, we'd write f(x, y) to apply a function f with parameters x and y. But in Scheme we instead write (f x y).

Thus, to compute the square root of 169, we want to apply the sqrt function to the parameter 169, and so we'd write (sqrt 169), which will evaluate to 13.

Scheme treats arithmetic operators like addition and subtraction the same way as it treats functions. As a result, if you want to add the numbers 2 and 3, you would write (+ 2 3), not 2 + 3 as you would in many other languages. numbers 2 and 3. Naturally, an argument can itself be the result of an arithmetic operation represented as a list. If you want to compute (2 ⋅ x) + (4 − i), you would write:

(+ (* 2 x) (- 4 i))

Parentheses are important! Parentheses always represent function application in Scheme. If you omit them, Scheme will complain. For example, the expression (+ * 2 x 4) actually indicates that the computer is to add four values together, of which the first is *. The Scheme interpreter will complain that it can't add numbers to a function such as the multiplication function.

Likewise, you can't add extra parentheses. If you do, Scheme will think that you want to apply a function. If you write ((+ 2 3)), then the interpreter will reduce this to (5), but it will then understand that this says to call the 5 function with no arguments; the interpreter will complain that 5 isn't a function.

§3. Defining functions

To define functions, we use the define operation, whose first argument is a list consisting of the function name followed by the parameter names, and whose second argument is the expression indicating how to compute the return value.

(define (sq x) (* x x))

The if operation takes three arguments and returns either the second or the third depending on whether the first argument is true (#t) or false (#f). Naturally, there are comparison operations for comparing numbers (such as =, <, and <>) and logical operations for Boolean values (including not, and, and or). We can use the if operation to define a function that rounds its parameter to the nearest multiple of 10.

(define (round10 n)
   (if (>= (remainder n 10) 5)
       (+ n (- 10 (remainder n 10)))
       (- n (remainder n 10))))

(Parentheses, you quickly learn with LISP-like languages, are frequent. In fact, some joke that LISP stands for Lost In a Sea of Parentheses.)

Note: In contrast to many other programming languages, the if operation is not a statement! It is an operation that forms part of an expression, and it must always computes a result. Consequently, the else portion of the if operation is required, since the expression must have a value even if the condition turns out to be false.

§4. Language categories

In fact, this fact touches on one of the most interesting and important features of Scheme: Classical Scheme doesn't have statements! That is, there's no concept of do this, then afterwards do that. Instead, a computation is expressed entirely as an expression. In the terminology of the more widely used languages, every Scheme function consists only of a single statement, which is a return statement.

Not only does that mean no if statements, it also means assignment statements and no while statements. Among other things, that means that classical Scheme doesn't have variables in the sense of names whole values change over time.

Languages that support statements are called imperative languages; this includes languages such as C, Python, Pascal, and Visual Basic. By contrast, Scheme is called a functional language; other functional languages include Haskell, ML, and Common Lisp.

But if a language is to be useful at all, it must be able to deal with computations that involve some form of repetitive processing. How can a functional language such as Scheme do this? Such a language doesn't have loops, but it does have recursion. To compute the factorial of an integer, we would define it recursively.

(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))

Let's see how Scheme would evaluate (fact 3) using this definition.

	(fact 3)
⇒	(if (= 3 0) 1 (* 3 (fact (- 3 1))))
⇒	(* 3 (fact 2))
⇒	(* 3 (if (= 2 0) 1 (* 2 (fact (- 2 1)))))
⇒	(* 3 (* 2 (fact 1)))
⇒	(* 3 (* 2 (if (= 1 0) 1 (* 1 (fact (- 1 1))))))
⇒	(* 3 (* 2 (* 1 (fact 0))))
⇒	(* 3 (* 2 (* 1 (if (= 0 0) 1 (* 0 (fact (- 0 1)))))))
⇒	(* 3 (* 2 (* 1 1)))
⇒	(* 3 (* 2 1))
⇒	(* 3 2)
⇒	6

Writing the evaluation of an expression in this fashion is called a reduction.

You may object: Sure, you can do that for factorial. But what about other problems where you need a variable? Well, there aren't any such problems. But there are problems where you end up needing to define an additional function.

Determining whether a number is prime is an example. We can't write a single function prime? that takes a single parameter n and returns true (#t) if n is prime and false (#f) otherwise. After all, at least with the obvious technique, we need a counter that goes through all possible divisors of n. However, we can get this counter by adding a helper function help-prime.

(define (help-prime i n)
   (if (> (* i i) n)
       #t
       (if (= (remainder n i) 0)
           #f
           (help-prime (+ i 1) n))))

(define (prime? n) (help-prime 2 n))

As you can see, our helper function takes an extra parameter corresponding essentially to the counter that we would normally use in an imperative language. This extra parameter will have successively larger values as the function descends through its recursion tree.

§5. Lists

The array data type that is so popular in imperative languages relies on being able to change the value at a particular index. This is inherently an imperative concept, and so the notion cannot translate over to functional languages.

Of course, we still need to store the data sequences that would normally go into arrays in an imperative language. In functional languages, we do this using the list, which is simply a single linked list.

Scheme defines a variety of operations for working with a list. First, we'll use the null symbol to represent the empty list, and Scheme has a cons operation that takes an element and a list and returns a new list headed by that element and followed by the rest of the elements. Thus, the expression (cons 2 (cons 3 null)) constructs the list (2 3). The list operations are as follows. [The peculiar names of the car and cdr functions derive from assembly language instructions on a 1950's computer. The names, unfortunately, stuck.]

empty	A constant identifier corresponding to the empty list
list	Constructs a list with the given elements
cons	Constructs a list with the given head and tail
car	Returns the head of the given list
cdr	Returns the tail of the given list
null?	Returns #T if the list is empty

The following examples illustrate how these functions work.

(list 2 3 4)	⇒ (2 3 4)
(cons 2 (cons 3 empty))	⇒ (2 3)
(car (list 2 3 4))	⇒ 2
(cdr (list 2 3 4))	⇒ (3 4)
(car (cdr (list 2 3 4)))	⇒ 3
(null? (cdr (cdr (list 2 3))))	⇒ #t

To see how to work with lists, we'll build two functions. The first takes a list and computes the sum of all its values.

(define (sum data)
   (if (null? (cdr data))
       (car data)
       (+ (car data) (sum (cdr data)))))

Let's look at a reduction illustrating this function at work.

	(sum (list 13 3 42))
⇒	(+ 13 (sum (list 3 42)))
⇒	(+ 13 (+ 3 (sum (list 42))))
⇒	(+ 13 (+ 3 42))
⇒	(+ 13 45)
⇒	58

The second takes a number num and a list data and returns a list that contains everything in data except with any instances of num removed.

(define (remove num data)
   (if (null? data)
       empty
       (if (= (car data) num)
           (remove num (cdr data))
           (cons (car data) (remove num (cdr data))))))

Again, a reduction illustrates it working.

	(remove 3 (list 3 13 3 42))
⇒	(remove 3 (list 13 3 42))
⇒	(cons 13 (remove 3 (list 3 42)))
⇒	(cons 13 (remove 3 (list 42)))
⇒	(cons 13 (cons 42 (remove 3 empty)))
⇒	(cons 13 (cons 42 empty))
⇒	(cons 13 (list 42))
⇒	(list 13 42)

§6. Mergesort

A much more sophisticated example of building a Scheme program is a sort function that takes a list of numbers as a parameter and returns a list of the same numbers, but in sorted order. Mergesort is arguably the easiest way of accomplishing this in Scheme; we have only to build three functions.

; Returns a list with the 1st, 3rd, 5th, ... elements in parameter
(define (alternates data)
   (if (or (null? data) (null? (cdr data)))
       data
       (cons (car data) (alternates (cdr (cdr data))))))

; Returns a list with elements of parameter lists merged together.
(define (merge a b)
   (if (null? a)
       b
       (if (null? b)
           a
           (if (< (car a) (car b))
               (cons (car a) (merge (cdr a) b))
               (cons (car b) (merge a (cdr b)))))))

; Returns the a list with values from parameter list in increasing order
(define (sort data)
   (if (null? (cdr data))
       data
       (merge (sort (alternates data)) (sort (alternates (cdr data))))))

§7. Higher-order functions

Scheme, along with many other functional languages, treats functions as first-class data (as its advocates say). This phrase refers to the fact that in these languages functions can be stored in variables, passed as parameters, and returned from functions. This characteristic distinguishes it from most imperative languages, where a function is typically a static feature that cannot be manipulated.

An example is the following filter function, which takes a function and a list as parameters and returns all the elements of the list for which the function returns true.

(define (filter condition data)
  (if (null? data)
      null
      (if (condition (car data))
          (cons (car data) (filter condition (cdr data)))
          (filter condition (cdr data)))))

The following illustration uses the built-in odd? operation, which returns true if the argument is odd.

(filter odd? (list 1 3 6 10 15 21))

⇒ (1 3 15 21)

Scheme also allows us to construct expressions that build functions using its lambda operator. As an example, (lambda (x) (+ x 3)) creates an unnamed function that takes any parameter x and returns the value x + 3. The following is legitimate.

((lambda (x) (+ x 3)) 6)

The outermost parentheses represent a function application. In this case, the function being applied is our earlier unnamed function, to which we are passing the parameter 6. Given 6, our unnamed function returns 9, so this is the value of the expression.

Using lambda can be useful in conjunction with our filter function. To select out those numbers in a list that are more than 10, for example, we can write:

(filter (lambda (n) (> n 10)) (list 1 10 3 15 6 21))

⇒ (15 21)

We can use lambda to write functions that generate new functions. For example, the following function computes the composition of two functions. (In mathematics, the composition of two functions f and g is represented as f ° g and is defined by (f ° g)(x) = f(g(x)).)

(define (compose f g)
  (lambda (x) (f (g x))))

This function constructs and returns a new function based on its parameters f and g. We can use this to compose the built-in not function with odd?. (We could simply use even?, but that wouldn't illustrate compose at work.)

(filter (compose not odd?) (list 1 3 6 10 15 21))

⇒ (6 10)