Roboguy.net

Scheme Tutorial

Contents

About this tutorial
About 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:

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: The parenthesis are there because it's actually calling the function +. That's also why it's in prefix notation. The + function (along most of the other basic math functions such as -, *, etc) can take 1 or more arguments. Functions in Scheme are called similarly to languages such as Python and C:
(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:

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).