CSE 341 -- Scheme Cheat Sheet

Scheme is an extraordinarily simple language. It implements just a few fundamental concepts that can be combined in interesting and powerful ways to build up complex systems.

The Read-Eval-Print loop

This is the heart of the scheme interpreter. The evaluator implements the following algorithm: Eval(expr: symbolic-expression)
  1. Is expr an atom? If it is self-evaluating, just return it. Otherwise (it is a name), return its value from the current environment
  2. Else, is the expression a list? If the first element is a special form, do the rule for that form. Otherwise (it must be a function), evaluate the first element of the list and apply it to the values of the rest of the list.

Special Forms: define, quote, lambda, cond, let/let*

;; Define is used to define new names.  Names may refer to any value
;; (which may be data or a function)
(define x 10)
(define double (lambda (x) (* x 2)))

;; Quote is used to "quote" literal data (symbols or lists)
(quote hello)           => hello
(quote (1 2 3))         => (1 2 3)
'(1 2 foo bar)          => (1 2 foo bar)  ; the tick-mark ' is syntactic sugar

;; Lambda is used to generate new functions
(lambda (x) (+ x 10)                    ; an anonymous function
(define plus10 (lambda (x) (+ x 10)))   ; we've named the function now

;; Cond is a general conditional
(cond 
  ((eq? 'foo 'bar) 'hello)
  ((= 10 20) 'goodbye)
  (#t 'sorry))                  => sorry

;; Let is used to declare/use temporary variables
(let
  ((x 10)
   (y 20))
  (+ x y))

Built-in Types and Functions

Scheme supports numbers (integers, rationals, floats), characters, strings, booleans, symbols, lists, and vectors. Below are some examples of the built-in functions we can use on these types: 
;; arithmetic:  +, -, *, / 
;; relational: <, <=, >, >=, =
(+ 1 2)                    => 3       
(= 1 2)                    => #f   ; use = for numbers

;; Equality and identity:  eq? and equal?
(eq? 'hello 'goodbye)      => #f   ; eq? is an identity test
(eq? 'hello 'hello)        => #t   ; two values are eq if they are the same
(eq? '(1 2) '(1 2))        => #f   ; object...
(define foo '(1 2))      
(define foo bar)
(eq? foo bar)              => #t
(equal? foo bar)           => #t   ; two values are equal if they look the same
(equal? foo '(1 2))        => #t

;; Lists:  cons, car, and cdr
;; Making new lists, via quoting, cons, or list
(define foo '(1 2 3))     
(define bar (cons 1 (cons 2 (cons 3 ()))))
(define baz (list 1 2 3))

;; Process lists with car, cdr, and null?
(null? '(1 2))             => #f
(null? ())                 => #t
(car '(1 2))               => 1
(cdr '(1 2))               => (2)

Iteration via recursion

;; Exponentiation function x^n
(define expt 
  (lambda (x n)
    (cond ((= n 0) 1)
	  (#t (* x (expt x (- n 1)))))))

;; List length
(define length
  (lambda (a-list)
    (cond ((null? a-list) 0)
	  (#t (+ 1 (length (cdr a-list)))))))

Higher order functions

Functions are first-class in Scheme, meaning we can pass them as arguments to other functions. 
;; takes two functions and an argument, returns (f (g x))
(define compose 
  (lambda (f g x)
    (f (g x))))

(compose even? (lambda (x) (- x 1)) 10)   => #f

;; takes a function and applies it to every element of a list
(define map 
  (lambda (f a-list)
    (cond ((null? a-list) a-list)
	  (#t (cons (f (car a-list)) (map f (cdr a-list)))))))

(map even? '(1 2 3 4))        => (#f #t #f #t)
dugan@cs.washington.edu (Last Update: )