I'm still a bit of a beginner to Scheme myself, so this will be very basic.

However, Scheme is a natural language for me and I learn it rather quickly so I'll likely be adding updates when I learn more.

Anyway, let's begin.

First off, Scheme is in a family of languages called LISP, short for list-processing. As such, the language specializes in processing lists (go figure).

Lists can be very powerful tools if used properly. You can manage entire sets of data at once using lists. There are a few peculiarities of the LISP languages that date back to its initial inception. I will make an attempt to explain these the best I can as I go along.

First things I would like to discuss about the language. The basic design of the language is oriented towards 'functional programming'. Basically, functional programming attempts to create clean, concise functions without the types of side-effects that can arise in object-oriented languages and the like.

The method for producing functions is based on Alonzo Church's Lambda Calculus. As I am not an expert at this topic, I won't go into it at depth. Suffice it to say that functions are generally formed using lambda notation derived from the lambda calculus. Also, the syntax of the language is in prefix notation like the lambda calculus (in other words instead of most languages that would say something like f(x, y) Scheme says (f x y)).

One of the cool things about Scheme is that defined data are merely symbols and can represent anything. Not only that, but certain alphanumeric characters that are normally restricted from use in naming are not restricted in Scheme. Still, it's best not to get too wild with your naming conventions. One reason I point this out is there is a specific naming convention in Scheme that all predicate symbols are followed with a ? and all symbols that cause side-effects are followed with a !

Anyway, onto some coding.

Since Scheme is a powerful calculating language, most of this tutorial will be about forming powerful calculating functions. As such I will not include the typical "Hello world" example in this tutorial. Instead I will start by giving some examples of how to form basic statements in Scheme.

First of all, there is something called 'arity' which describes how many arguments a function can have. If you attempt to use a function defined for a different number of arguments than what you have supplied, Scheme will produce an arity-error.

(+ 1 2)

This means the same as 1 + 2.

Since it's in prefix notation, even things like + and - are used at the beginning of a function. The only common exception to this is the use of complex numbers of the form #.#+#.#i .

let's try some more

(+ (* 2 3) (/ 6 2))

This will yield (2 * 3) + (6 / 2) or (6 + 3) or 9

you can layer your code as deep as you want.

(+ (* (+ (* (+ 2 3) 4) 5) (+ 2 8)) (- 7 4))

this would yield (((((2 + 3) * 4) + 5) * (2 + 8)) + (7 - 4))

when you get more parentheses, sometimes it's easier to add them on new lines

(+ 2 (* 3 (+ 5) ) )

or you can indent if you'd like

(+ 3 (- 7 (* 2 3)))

now let's introduce some basic list concepts.

There are two ways to form lists. You can either construct a list using a single data item and a list to add it onto. Or you can take two data items.

However, if you construct a list using only two data items, you'll get what is called a 'dotted pair'. This can easily be remedied by using the list keyword.

Also, Scheme reads your statements starting with the definition of the first item in the list (something like (+ 2 3) can be considered a list of 3 elements) and attempts to evaluate it. If you don't want it to be evaluated, you have to quote it. You can either do this using the keyword quote or by using '. Thus (quote a) and 'a would both yield a whereas (a) would attempt to evaluate whatever a is. If a is not defined as anything (a) would yield an error.

(cons 'a '(b c)) (cons 'a 'b) (list 'a 'b)

The above code will yield the following:

(a b c)

(a . b)

(a b)

You can also form a list by constructing a list (via the cons keyword) using a data item and the empty list ()

(cons 'a (cons 'b (cons 'c ())))

The above code should yield (a b c) as well.

Now let's discuss breaking a list into pieces. Suppose you start out with a list such as (a b c). There are two very special keywords that can be used to access particular pieces of the list.

The first keyword is car... this is a keyword that originally meant 'contents of the address register' back when LISP was first created. Also, there is the keyword cdr... this meant 'contents of the decrement register'. The car of a list is the first data item in a list, even if that data item is a list itself. The cdr (pronounced "could-er") of a list is every element less the first one. Thus if you had a list named z that was defined as (a b c) then

(cons (car z) (cdr z))

will yield z back again.

If you want to access other elements of a list, you have to do combinations of these keywords. So, if z is still defined as (a b c) then:

(car z) (car (cdr z)) (car (cdr (cdr z))) (cdr z) (cdr (cdr z)) (cdr (cdr (cdr z)))

will yield the following:

a

b

c

(b c)

( c )

()

As you may have noticed in the last example if you're only left with a list of one element, the car will be the element while the cdr will be the empty list.

Now that we've covered constructing and destructing lists, let's do something useful with this knowledge.

First, I want to tell you about the let and define keywords. The let keyword allows you to temporarily set a value to a symbol for use in a single expression. The define keyword allows you to set a value on a function until it's changed or until you end the session.

(let ( (x 2) (y 3) ) (+ x y) )

This will first set the variables x and y temporarily to 2 and 3 respectively. Then it adds them together. The value 5 should result.

Now let's try it with define.

(define x 2) (define y 3) (+ x y)

The first two lines will evaluate, then after the third line it will yield 5. Then if you type x or y after that they will evaluate to 2 or 3 respectively.

Let's define something a little bit more difficult. Let's make a function that will accept two values x and y and do a little arithmetic.

(define f (lambda (x y) (* x y) ) )

This should evaluate and say something like "function f".

Now let's make an absolute value function.

(define absol-val (lambda (x) (if (< x 0) (- 0 x) x )))

In this case I've introduced the if keyword.

If automatically has the so-called 'else' statement built into it.

It's a one condition keyword. It works as follows:

If - condition - consequence - alternative

However, you can form the equivalent of an if/else statement with it.

If - condition - consequence - if...

However, there is a keyword cond that takes conditional statements.

Based on the way the if keyword works, it's pretty self-evident how cond works, so I'll not cover it here.

Anyway, the above code works like so: if x is less than 0 then subtract x from 0 (hence getting the negative of the number) else return x

Now that we know how to do this, let's get into a deeper concept: recursion. Recursion allows you to define something in terms of itself. By changing the value being checked each time and setting some termination condition, one can make a clean and concise function by using recursion.

Let's use the common factorial function as an example.

(define fact (lambda (x) (if (<= x 1) 1 (* x (fact (- x 1) ) ) )))

What this code is saying basically is that if x is less than or equal to 1 then return 1, otherwise return x * fact(x - 1)

So, if we take the number 5 for example...

(* 5 (* 4 (* 3 (* 2 1)))) -> (* 5 (* 4 (* 3 2))) -> (* 5 (* 4 6)) -> (* 5 24) -> 120

Now let's have some fun... next we're going to use the list processing that we learned earlier and our fact function we just defined and make a new function that will take a list of values such as (1 2 3 4 5) and return a new list of equal length of their factorials such as (1 2 6 24 120).

(define fact-list (if (eq? x ()) x (cons (fact (car x) ) (fact-list (cdr x) ) ) ))

Now this function's really neat. First we check to see if x is equal to the empty list (= is only used to check numbers, thus a predicate like eq? must be used to check if it's a list) and if it is then simply return the empty list. Otherwise, construct a list of the fact of the first element and the fact-list of the rest of the list. Intuitively, this may seem difficult to grasp what's going on at first, but let me elaborate with an illustration... Suppose we started with the list (1 2 3 4 5) so the statement was

(fact-list '(1 2 3 4 5))

then it would evaluate as follows:

x is not empty -> fact of car (1 2 3 4 5) is 1, cdr x is (2 3 4 5) ->

x is not empty -> fact of car (2 3 4 5) is 2, cdr x is (3 4 5) ->

x is not empty -> fact of car (3 4 5) is 6, cdr x is (4 5) ->

x is not empty -> fact of car (4 5) is 24, cdr x is (5) ->

x is not empty -> fact of car (5) is 120, cdr x is () ->

x is empty...

This will look like

(cons (fact 1) (cons (fact 2) (cons (fact 3) (cons (fact 4) (cons (fact 5) ())))))

according to Scheme. Thus yielding (1 2 6 24 120).

Now you know some of the basics of Scheme... Have fun scheming!

This post has been edited by **Jaakuuta**: 19 July 2009 - 12:15 PM