Scheme Tutorial
Contents
About this tutorialAbout the notation used in the tutorial
Introduction
Functions and variables
Recursion
Higher-order functions and lambdas
Delayed evaluation
Continuations and call/cc (Work in progress)
About this tutorial
This tutorial expects a small amount of prior programming experience (understanding what a function is, if statements, etc). If you have more than a passing knowledge of programming, you can probably skim through the first 2 sections and skip the section on recursion all together (if you understand recursion, that is).Note: This tutorial is still a rough draft.
About the notation used in the tutorial
In this tutorial, the following notation will be used:- In code examples to be executed by an interactive interpreter, the code the user types in will be in italics and the result will be bold
- For the standard R5RS function call-with-current-continuation, I will use the pseudo-standard call/cc abbreviation. This is because I am too lazy to type call-with-current-continuation every time I want to use it.
Introduction
Scheme is a functional (I'll cover what that means in later sections) Lisp dialect. Lisp is a programming language that was originally created in the late '50s, by John McCarthy. Lisp dialects have a very distict look compared to other modern languages, which makes them easy to recognize. For example, here is a snippet of code that adds together 1, 2, 3, 4 and 5:(+ 1 2 3 4 5)
15
Most likely, you will immediately notice a few unusual things about it:
- It has parenthesis around it (these are not optional, I will soon explain why)
- It is in prefix notation (I will also explain this soon)
- The + can have a list of numbers, which it adds together
(function arg1 arg2 arg3 etc)
Would be equivalent to the Python or C code:
function(arg1, arg2, arg3, etc);
Not a whole lot different, except that the function name is in the parenthesis
and the arguments are space delimited rather than comma delimited. Another thing
you might notice, is that function calls are basically just lists that the interpreter
interprets. This is one of the more interesting features of Scheme and other Lisp
dialects: Code is data. Programs are just collections of lists. This makes
it relatively easy to do metaprogramming (basically, programs which write programs),
which will be covered in one of my next tutorials.Now, you might be wondering "How can I define functions or have if statements? Those wouldn't be functions!". That's a good question. You're right, they wouldn't be functions, they would be special forms. Special forms are similar to macros in other languages, except they are more powerful than most. I will call them special forms in my tutorials to avoid confusion with other languages' macros. Basically, they are like functions, except their arguments are not evaluated and they are executed at compile time.
The special form for an if statement is if. It takes three arguments: The test (which will evaluate to either #t (true) or #f (false)), the expression to be evaluated if the test is true, and the expression to be evaluated if the test is false. It looks like this:
(if test
then-expression
else-expression)
Note: The whitespace does not affect how the code is executed (except as token delimiters),
it is normally put in for readability.
Here is an example, which evaluates to (the Scheme equivalent of returning, basically) 1:
(if #f
2
1)
You can define new variables (and, as we'll see in the next section, functions) with the define special form. The format is:
(define var-name value)
Here is an example which sets the variable example to 1 (Note: We are not defining a function,
the if special form expansion evaluates to 1 because it's test is #t (which is true)):
(define example
(if #t
1
3))
A few other common built in functions are:
- cons: Takes two arguments. Evaluates to a new pair (which is usually a list), whose head (first element) is it's first argument and whose tail (every element after the first) is the second argument (which is usually a list)
- display: Writes some text to the current output port (which is, by default, the screen). Note: This does not print a newline at the end.
- newline: Writes a newline to the current output port.
- car: Evaluates to the head of the given list
- cdr: Evaluates to the tail of the given list
- length: Evaluates to the length of the given list
- null?: Evaluates to #t if the given list is empty, otherwise it returns #f
- set!: Takes two arguments. The first argument is a variable or function which is already defined. It sets the variable or function given in the first argument to the second argument.
- eq?: Compares it's two arguments. If they are equal, it returns #t. Otherwise, it returns #f. Note: It does not work on lists (except when comparing to empty lists), pairs, vectors, symbols or strings. When it compares two variables, it compares the location they point to in memory, not the actual values.
- eqv?: Returns #t if it's arguments are equivalent, returns #f otherwise.
- equal?: Recursively applies eqv? to lists, vectors and strings. Otherwise it behaves like eqv?
Functions and variables
Functions, like global variables, are also defined with the define special form, however the syntax for using it to define functions is slightly different:(define (fn-name arg1 arg2 arg3 etc)
expression1
expression2
expression3
etc)
Here is an example function, which prints Hello, world! followed by a newline (the canonical first program):
(define (greet)
(display "Hello, world!")
(newline))
Functions return (in C and Python terminology) the value of the last expression evaluated in it:
(define (example)
(+ 1 1))
(example)
2
So far, you have only learned to define global variables (with define). You can also define
local variables (variables which only exist in a certain block of code) with the let special form.
The syntax for let looks like this:
(let ((var1 value1) (var2 value2) etc)
expression1
expression2
expression3
etc)
Here is an example of it's use:
(let ((x 1) (y 2))
(+ x y))
This sets x to 1 and y 2, but
only for the expressions after the first argument (in this case, (+ x y)).
Like functions, let expressions evaluate to the last expression evaluated in it's body.
Variables defined this way cannot be accessed outside of the body. Let's look at a less trival example, here is a function that evaluates the binomial ax + by2, given the values of a, b, x and y:
(define (binomial a b x y)
(+ (* a x)
(* b (expt y 2))))
(binomial 1 2 3 4)
35
expt raises it's first argument to it's second argument (for example
(expt a n) would evaluate to an).
Recursion
Recursion is when a function calls itself. Recursion is the main form of looping in Scheme (we will discuss other methods in the section Higher-order functions and lambdas). Most recursive functions have terminating condition (A condition when it stops calling itself). Here is the general structure of a typical recursive function:(define (fn arg1 etc)
(if terminating condition
final expression [not a recursive call]
recursive call))
Here is a simple factorial function, to demonstrate:
(define (factorial n)
(if (eqv? n 0)
1
(* n (factorial (- n 1)))))
The terminating condition of this function is (eqv? n 0). That is, when n is equivalent to 0, it stops recursively calling itself.
Higher-order functions and lambdas
In Scheme, and other functional languages such as Python, functions are values. They can be stored in variables and passed as arguments to other functions. Functions which take a function as an argument is called a higher-order function. It is best explained with a code example:(define (print-result operation)
(display (operation 2 1))
(newline))
(print-result +)
3
(print-result -)
1
(print-result *)
2
Since functions can be passed around like this, you can have lambdas. A lambda is basically a nameless function.
They are defined with the lambda special form. Using the print-result function from the previous example:
(print-result (lambda (x y) (+ x y 1)))
4
The standard function apply is applies a given function to a list:
(apply + (list 1 2))
3
The function for-each applies the given function to each element of the given list:
(for-each display (list 1 2))
(newline)
12
The function map is similar to for-each, except it collects the results
of the function applications it makes into a list:
(map
(lambda (x)
(+ x 1))
(list 1 2))
(2 3)
Functions (and lambdas) that have state through an enclosing let are called closures. Here is an example of one:
(define (example)
(let ((x 0))
(lambda ()
(set! x (+ x 1))
x)))
(define f (example))
(f)
1
(f)
2
In later sections, you will see more uses for this feature.
Delayed Evaluation
Delayed evaluation is when (as it's name suggests) an expression is delayed to be evaluated later. In Scheme, this is done with the delay (to delay an expression) and force (to force evaluation of the value of a delayed expression). For example:(define example (delay (display "Hello, world!")))
example
#<procedure>
(force example)
Hello, world!
Continuations and call/cc (Work in progress)
Continuations are a complicated subject, so you might have to read through this section a few times before you understand them. Basically, continuations are closures which represent part of the program. The current continuation is everything which will be executed after the time you find the current continuation. Let's look at this bit of code:(f 1)
(g 2)
(h 3)
At line one, the current continuation is a closure which executes (g 2) and (h 3). This may not seem useful at the
moment, but it's very powerful (for reasons which I will explain later in this section). The function call/cc (which stands for
call with current continuation) takes one argument, then applies it to the current continuation. Probably the most basic example
of it would be using it as a Scheme equivalent of C's and Python's return statement:
(define (f return)
1
(return 2)
3)
(call/cc f)
2
Note: When the current continuation is applied to an argument, it is inserted where the function call is. The main reason continuations are useful is that you can save them, and go to the place where it was originally saved (Note: They are not the same as gotos, although they can sometimes function similarly). Here is an example of this (Important note: The following code example will print the string Hello, world! until it is terminated or killed):
(define (f)
(let ((saved-continuation #f))
(define (g continuation)
(set! saved-continuation continuation))
(call/cc g)
(write "Hello, world!")
(newline)
(saved-continuation)))
(f)
Hello, world!
Hello, world!
Hello, world!
...
Continuations can be used to implement any form of control flow (loops, generators, coroutines, etc).