A quick Scheme programming cheat sheet Note - for the workshop (and to do a lot of things in fluxus) you only need to understand as far as and including recursion. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Expressions All scheme expressions take the form: (operator operand operand operand ...) This is called prefix notation, and everything in Scheme works this way. (+ 137 349) evaluates to: 486 (* 3 2.4) => 7.2 (- 3 2) => 1 (+ 4 253 5) => 262 Nesting expressions (+ (+ 4 2) (- 46 9)) => 43 ** Naming things ** (define size 2) size => 2 (* 5 size) => 10 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Naming procedures Scheme, and programming in general is about making procedures as building blocks that you can use without concerning yourself with the details, this is known as abstraction. (define (square x) (* x x)) (square 4) => 16 Which can be read as: (define (square x) (* x x)) to square something multiply it by itself Procedures can be formalised as: (define ( ) ) Body can contain multiple expressions, the procedure will return the value of the last expression called in the body. Using procedures as building blocks inside other procedures (define (sum-of-squares x y) (+ (square x) (square y))) (sum-of-squares 3 4) => 25 How it works: The substitution model (sum-of-squares 3 4) becomes: (+ (square 3) (square 4)) becomes: (+ (* 3 3) (* 4 4)) becomes: (+ 9 16) becomes: 25 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Miscellaneous Printing information (display "hello world")(newline) hello world (display 103)(display " ")(display "apples")(newline) 103 apples (display size)(newline) 2 Comments are semicolons: ; drunk, fix later ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Conditionals, or making choices There are two ways of defining conditionals in Scheme: Using cond (define (abs x) (cond ((< x 0) (- x) (else x))) and using if (define (abs x) (if (< x 0) (- x) x)) Both use predicate expressions (the < in this case) which return true or false. The "if" is simpler, but only allows you to evaluate one expression for each branch. (if ) cond allows you to pick from one of many choices (like a switch in C), and allows you to have as many expressions as you want for each choice - called a clause. (cond (

) (

) ... (else )) More predicates (> 1 2) => #f (>= 1 2) => #f (<= 1 2) => #t (eq? 1 1) => #t (zero? 0) => #t Combining predicates (and (eq? 1 1) (<= 1 2)) => #f (or (eq? 1 1) (<= 1 2)) => #t (not (eq? 1 1)) => #f ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Recursion Recursion is where procedures are defined partly in terms of themselves. This is possible as every time a procedure is run it gets it's own copy of it's arguments and environment for the duration of it's execution. Recursion is the only form of looping in Scheme: (define (loop n) (display n)(newline) (if (zero? n) 0 ; returns 0 instead of calling loop again (loop (- n 1)))) ; recurse! (loop 10) 10 9 8 7 6 5 4 3 2 1 0 => 0 The factorial is the common example of recursion (define (factorial x) (if (eq? x 1) 1 (* x (factorial (- x 1))))) (factorial 10) => 3628800 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Local variables Sometimes you need to use local variables within procedures to store data temporarily. Scheme allows you to use scoped name bindings which do this with let: (let ((x 10) (y 30)) ; defines x to be 10 and y to be 30 ... ; code that uses x and y ) ; close the scope, x and y no longer bound ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Set Sometimes you need to change the values of named bindings (variables). This isn't as common in functional programming as it is in other types of language, but it's sometimes needed. (define a 10) (set! a 9) a => 9 (let ((a 10)) (set! a 9) a) => 9 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Data structures ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Pairs Pairs are the only structured data type availible in Scheme, and are used to construct lists, trees and all other data structures. Pairs are denoted by the two values seperated by a . sometimes called a "dotted pair" (cons 1 2) => (1 . 2) car and cdr (named after ancient machine code instructions) can be read as returning the first and last of a pair (car (cons 1 2)) => 1 (cdr (cons 1 2)) => 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Lists Lists are formed by nesting pairs together with a special value, the empty list () which is used to specify the last element of the list. (1 . ("hello" . (323 . ()))) Is known as a "proper" list, and can also be written as: (1 "hello" 323) Improper lists are lists which do not contain an empty list terminator, eg (1 . 2) or (1 . (3 . 3)) To specify the empty list in a program, we need to quote it with a ' to prevent the interpreter from thinking it's a procedure that needs evaluating. (cons 1 '()) => (1) (cons 1 '(2 3)) => (1 2 3) In this last example, we made a list in a similar way to the empty list by quoting it: '(2 3) The quote is needed again to prevent the interpreter from trying to run 2 as a function with 3 as an argument, but treat it as a literal list of items. We can also construct lists using the list procedure: (list 1 2 3) => (1 2 3) Back to car and cdr, which now do some interesting things: (car '(1 2 3)) => 1 car returns the first element of the list (cdr '(1 2 3)) => (2 3) cdr returns the list containing everything but the first element This is clear if we remember that the list really looks like this: (1 . (2 . (3 . ()))) car returns 1 while cdr returns (2 . (3 . ())) (cdr '(3 . ())) or (cdr '(3)) => () To find out if a list is empty, you can either use: (define list '(1 2 3)) (eq? list '()) => #f or (null? list) => #f Looping over lists These features all work together to allow lists to be easily handled by recursive procedures. (define (print-list l) (cond ((null? l) 0) (else (display (car l))(newline) (print-list (cdr l))))) (print-list '(4 2 "hello" 23 2.4)) 4 2 hello 23 2.4 => 0 Building lists (define (build-list n l) (if (zero? n) l (cons n (build-list (- n 1) l)))) (build-list 10 '()) => (10 9 8 7 6 5 4 3 2 1) Direct access to elements of a list (define colours '("red" "blue" "silver" "violet")) (list-ref colours 2) => "silver" (list-set! colours 2 "pink") colours => ("red" "blue" "pink" "violet")