This is a fast overview of the most critical features of scheme and scheme48, to get you started. If you have never used lisp or scheme before, I strongly recommend working through this tutorial, typing examples into the scheme interpreter as you go.
After you feel confident with writing simple programs, go back and read through the Scheme Report. Also look through the list of additional features pre-loaded into the class binary.
Page numbers refer to the R5RS Scheme report.
Scheme should be run from inside Emacs. Although you can start it directly from the Unix shell, it is difficult to use the interpreter without the editor interface. In principle, I suppose it could be connected to vi. However, I don't know of a "canned" way to do this and I suspect it would be a big time sink to set one up from scratch.
To run scheme, you must first edit your init files. Put the following lines into your emacs init file (.emacs in your home directory), changing "yourusername" to the right thing.
(setq load-path
(append load-path '("/usr/local/vision/scheme/scheme48-0.51/src/emacs")))
(setq scheme-program-name
"/home/yourusername/scheme-script")
(autoload 'run-scheme "cmuscheme48" "Run an inferior Scheme process." t)
Then create a file named "scheme-script" in your home directory containing the following lines:
#!/bin/sh lib=/usr/local/vision/scheme/scheme48-0.51/lib/scheme48 exec $lib/scheme48vm -o $lib/scheme48vm -i /usr/local/vision/scheme/cs151/class.image -h 6000000 -s 2500"$@"
If you want your scheme script elsewhere, or differently named, make the obvious modifications. Notice, however, that the script's file permissions should be set to make it executable.
Restart emacs. The command "M-x run-scheme" should now start scheme48.
Apparently some broken Windows telnet programs set the TERM variable incorrectly. Certain misconfigured Unix systems can also do this. If you seem to have terminal type problems (e.g. emacs refuses to start), try typing the following when you login.
setenv TERM vt100
This version of scheme, including emacs, can run on a machine with as little as 16M RAM. However, it needs significant swap space beyond that, e.g. the scheme image may be as large as 25M.
If you wish to keep your memory requirements as small as possible, change the number 6000000 in your scheme-script file to something smaller. 4000000 will almost certainly work. 2000000 might. This number determines the heap size of the scheme image, but is expressed in some odd unit (not bytes). If scheme gives you the error message "post-gc," you have set the heapsize too small: edit your scheme-script file and restart scheme.
On turing, your account defaults to allowing only 8M per process. This may not be enough. The shell command limit (with no arguments) will report your current limits. To reset the heapsize for your processes, do the following, either at the shell or in your .cshrc file.
limit datasize 16000 limit datasize unlimited
Resetting your limit implies that you assume responsibility for keeping an eye on your memory usage, so that you don't create a run-away process that messes up turing for everyone. The following shell command will report the processes currently using the most RAM on turing.
top -ores
Top's display can be adjusted dynamically. Type ? at top to see its interactive commands.
Your scheme process should not exceed the memory limit established when you started it: errors in your code cannot (at least in theory) cause run-away memory allocation in the manner of a broken C(++) program. However, it's still worth keeping an eye on turing's memory usage, especially if you are experimenting with different heapsizes.
When scheme48 starts up, it will print a welcome message followed by a prompt (>). At the prompt, you can type either a Scheme form (expression or definition), or a command (usually beginning with a comma).
The most useful commands are as follows:
If scheme seems to be wedged, try hitting ENTER a few times and typing a combination of control-d and #t. If the interpreter doesn't start acting reasonably (e.g. echoing the #t back at you), then go to a Unix shell, get a ps listing, and kill off the scheme48 process.
The lovely thing about an interpreted interface is that you can try out individual fragments of code, to make sure they run properly and/or do what you intended. Try typing some simple expressions at the prompt (each followed by ENTER):
> 3 > 3.14159 > 'scripps > "this is a string > #t
These expressions are literal values: two numbers, a symbol, a string, and a boolean. When you enter these expressions, the interpreter should simply echo back the same value.
> (define xxx 3.1549) > (+ xxx 7) > (set! xxx 20) > xxx
In scheme, when you apply an operator to some arguments, the operator comes first and the whole expression is surrounded by parentheses. This simple rule covers almost all the syntax of scheme.
The operator define (p. 16) is used to define a variable. The operator set! is used to reset a variable's value. It is legal to define a variable more than once, but it is not legal to set! a variable that you haven't yet defined. To inspect the value of a variable, simply type its name (e.g. xxx).
Section 6.2 (pp. 19-25) describes scheme numbers and numerical operators. Try out a few of them. Notice that you can nest one operation inside another:
> (< (+ xxx 3) 20) > (* 2.5 (quotient 17 5))
Objects in scheme have types (e.g. 3 is an integer) but variables do not have types. So the following is legal (though unusual except when typing at the interpreter or when processing user/file input).
> (define yyy 3.1549) > (set! yyy "harvey mudd")
The basic type of an object can be determined using the predicates listed on p. 6. These predicates return a boolean value, either #t (true) or #f (false). For example:
> (number? yyy)
> (string? yyy)
Boolean values can be combined using the operators and, or, not. Like the corresponding operators in C, the items inside an "and" or an "or" are evaluated from left to right, and the evaluation stops as soon as the output value can be determined. For example, the following expression does not produce an error, because the form "(< yyy 20)" is never evaluated.
> (and (number? yyy)
(< yyy 20))
Scheme supports several different notions of equality. The operator = is used to test whether numbers are equal. The operator equal? is used to test whether objects of any type (including numbers) are equal in the sense of looking alike.
> (= xxx 0) > (equal? "foo" "foo")
The list (pp. 25-27) is the basic data structure used for organizing data in scheme. Literal lists can be specified by enclosing the list of items in parentheses and preceding the whole thing with a quote. The items in a list do not all have to have the same type. The operator null? tests whether the list is empty.
> (define mylist '(a b 3 c)) > (define list2 '()) > (null? list2) > (null? mylist) > (list? mylist)
Scheme lists are implemented as linked lists. Each node in the linked list is a pair whose first element is the first item in the list and whose second element is the rest of the list. The functions car and cdr return the two items of the pair.
> (car mylist) > (cdr mylist)
The operator list creates a list out of some number of input elements. The operator cons adds an element to the start of a list.
> (define csdept (list 'keller 'wing 'mike 'geoff 'fleck 'hodas 'hadas)) > (define josh (cons 'hodas (cons 27 mylist))) > josh
Other useful list operations (p. 27) include append, reverse, length, member, and assoc. The unfamiliar one, assoc, takes as input an item and a list of pairs. It scans down the list of pairs looking for a pair whose first element is the item.
> (define firstnames (list '(keller bob) '(hodas josh) '(erlinger mike))) > (assoc 'hodas firstnames)
In addition to lists, scheme provides vectors, which are 1D arrays (p. 31). The extensions loaded into our copy of scheme also provide multi-dimensional arrays and records (like structs in C).
Functions such as cons and make-vector automatically allocate space for the objects they are creating or extending. The scheme interpreter automatically deallocates this space when you lose all ways to get at an object (e.g. reset the variables pointing to it). (The error message "post gc" means that the interpreter ran out of space: see the installation directions for how to increase the size of scheme's heap.)
The operator equal? tests whether two lists are equal, in the sense of looking alike. If you need to test whether they occupy the same memory location, use eq? or eqv? instead. Operations like cons or list allocate new pairs from memory, so lists created by distinct calls to cons occupy different memory locations.
> (define test1 (cons 'a '(c d))) > (define test2 (cons 'a '(c d))) > (equal? test1 test2) > (eq? test1 test2)
Operations that require testing objects for equality (e.g. assoc) frequently have variants that use eq? or eqv? rather than equal?.
Most list-handing operations (e.g. reverse, append, cons) create new list structure, so that they don't modify the lists that are given to them as input. They sometimes have "evil twins" (e.g. reverse!) that modify or trash their input lists. The basic operators for changing the contents of a list's memory locations are set-car! and set-cdr! (p. 26). Don't use such operations (frequently called "destructive") unless/until you have a specific reason for needing them.
Functions for writing output to the terminal can be found on p. 37. Our extended scheme also contains the function format, which produces formatted output. The function error creates an error break, printing a formatted message.
> (display '(a b c)) > (newline) > (format #t "The output of foo is ~s.~%" (+ 2 7 9)) > (error "Unexpected form ~s~%" yyy)
The first input to a format command is the file: #t specifies the terminal. The second input is a format string. Inputs after the second are values to be substituted into the format string. In a format, the special character sequence ~s is replaced by one of the inputs. The special sequence ~% produces a newline.
Functions are defined as follows (see p. 16):
> (define (my-polynomial x y)
(+ (* 4 x) (* -2 y)))
A call to this function looks like:
> (my-polynomial 2 7)
So, when defining a function, the first item after the "define" is an expression that looks exactly like a call to the function except that the inputs have been replaced by variables. The remaining items in the definition are the code for the function.
There is no explicit return statement. Rather, a function returns the value from the last expression in its code.
Defining interesting functions requires creating local variables, writing loops, and writing tests. Local variables are created using the operator let* (p. 11). (The operators let and letrec are similar.)
> (define (fff x y)
(let* ((x-squared (* x x))
(y-squared (* y y)))
(format #t "Squares are ~s and ~s~.%" x-squared y-squared)
(+ x-squared y-squared)))
The first input to let* is a list of pairs. Each pair contains the name of a local variable (e.g. x-squared) and its initial value. The rest of the inputs to let* are the statements to be executed using these local variables. In this case, the function executes a format statement, then evaluates a piece of arithmetic. The value of the let* is the value of the last statement (in this case, the arithmetic).
The operation if (p. 10) is like similar statements in other programming languages, except that it returns the value from the statement that is chosen. For example, here is the famous factorial function:
> (define (factorial x)
(if (<= x 0)
(error "factorial only accepts positive inputs."))
(if (= x 1)
1
(* x (factorial (- x 1)))))
When you need to choose among several possibilities, a cond statement (p. 10) is usually more readable. For example, the following function examines an input of unknown type and returns a string describing its type.
> (define (what-am-i input)
(cond ((number? input)
"number")
((list? input)
"list")
((boolean? input)
"boolean")
(else
(error "what-am-i got a wierd input ~s" input))))
Each clause in the cond statement is a list. The first element of the list is a test, the other items in the list are code to be executed. If the test returns true, then the code is executed and the cond statement returns the value from the last expression in the code. If the test returns false, then scheme tries the remaining clauses of the cond statement.
If you wish to make sure something happens, no matter what, end a cond with a clause whose test is else or #t. This clause will always be executed if no previous clause was executed.
Loops are created using the operator do (p. 12). Its syntax is a bit baroque. Here's an example
> (do ((x 0 (+ x 2))
(y 10 (- y 2)))
((> x y) "done")
(format #t "step~%")
(format #t "x = ~s, y = ~s~%" x y))
The first input to the do is a list of variable definitions. Each definition is a triple: variable name, initial value, expression to compute subsequent values. (The third item can be omitted.)
The second input to the do is a list, consisting of a test and zero or more expressions. When the test returns true, the loop halts, the expressions are evaluated, and the value from the last expression is returned.
The subsequent inputs are expressions to be evaluated each time the loop executes.
Here's another example, this time walking down a list:
> (define (foo mylist)
(format #t "Input list is ~s.~%" mylist)
(do ((rest mylist (cdr rest))
(count 0 (+ count 1)))
((null? rest))
(format #t "Position ~s in the list contains value ~s~%"
count (car rest))))
If you need to put a sequence of expressions where scheme syntax expects only one, use the operator begin (similar to curly brackets in C-like languages).
> (define (test x)
(begin (newline)
(display x)
(newline)
(display '(a b c))
(newline)))
Variables in scheme can contain a wider range of symbols than in many other programming languages: see the list on p. 5. When creating a multi-word variable, it is conventional to separate the words with a hyphen rather than an underscore.
> (define ultra-special-magic-constant 26)
Notice, however, that Scheme does not distinguish uppercase letters from lowercase letters in variable names. It is traditional to use only lowercase letters when writing scheme (or lisp) code.
Names of scheme functions usually follow these conventions
The interpreter will not force you to follow these conventions, but following them will make your code easier to read.
It is very common to apply a function to all elements of a list, or all parallel elements of two lists. The operator map (p. 32) does this:
> (map + '(1 2 3) '(20 30 40)) > (define (test x y) (+ (* 2 x) y)) > (map test '(1 2 3) '(20 30 40))
The operator for-each (p. 32) is similar. The difference is that map returns a list containing the values from applying the function. Although the output list is in the same order as the input lists, map does not have to compute the values in this order. For-each does not return a value, but it is guaranteed to process its input lists in order.
> (define (print-me x) (format #t "~s~%" x)) > (for-each print-me (list 'x 3 "foo"))
Sometimes it is inconvenient to define a named function to give to for-each or map. An unnamed function can be defined using the operator lambda:
> (map (lambda (x y) (* x y y))
'(3 5 2)
'(5 2 2))
The first input to lambda is a list of arguments to the function (in this case, x and y). The second and later inputs are code to be executed.
To write real programs, you will want to put the code in a file. Create a file with extension .scm (e.g. unify.scm). Edit the file using emacs. Emacs should recognize a file with extension .scm as a scheme file and provide you with various useful features:
Lines beginning with a semicolon (;) are interpreted as comments. Standard lisp/scheme style suggests that
;;; The factorial function computes the factorial of a
;;; non-negative integer.
(define (factorial x)
;; test for illegal inputs
(if (<= x 0)
(error "factorial only accepts positive inputs."))
;; do the computation
(if (= x 1)
1 ; base case
(* x (factorial (- x 1))))) ; call factorial recursively
To load a file of code into the scheme interpreter, use the ,load command:
> ,load /home/fleck/solve-ai.scm
Ownership, Maintenance and Disclaimers
Last modified