Scheme is a functional programming language, and the target language for the interpreter built in the final project of CS61A. Please add your descriptions and simple examples of the basic forms of Scheme here.
Below are various syntax examples of how to use scheme. For more information on scheme and functional programming see John DeNero's Functional Programming.  You can play around with an online scheme interpreter here.
Scheme syntax for defining expressions and statements are as follows:
(define (function/variable name and arguments go here) (return statement if it's a function))
So, for example, if you wanted to define a simple square function, that would take in some value x and return it's square it would look something like this:
>>> (define (square x) (* x x))
The first statement after
Define is read as the name of the function or variable and the arguments of the function, then the return value. To give a function multiple arguments, simply declare all the arguments inside a parenthetical like so:
>>> (define (multiply x y) (* x y)) >>> (multiply 3 2) >>> 6
Conditional statements such as
if are used much the same as in python with the exception of the
(if (condition) (true value) (false value))
if statement is a conditional that contains three statements. It first evaluates its condition, and from there returns either the true or the false value based on its evaluation.
>>> (if #t (* 3 2) (- 1 2)) >>> 6 >>> (if #f (* 3 2) (- 1 2)) >>> -1
(and (condition) ... (tail value))
and statement evaluates its arguments one by one until either:
- It evaluates a false expression, in which case it'll return false.
- It evaluates all of its condition as true, in which case it'll return it's tail value.
- If no arguments are given, it'll return true.
- If only one expression is given it'll consider it the tail value and return the tail value.
>>> (and #t #f 1/0) ;this will never reach 1/0 >>> #f >>> (and #t #t 100) ;will return the tail value no matter how many expressions if they're all true. >>> 100 >>> (and #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t 100) ;see? >>> 100 >>> (and) ;no conditions returns true. >>> #t >>> (and '(1/0)) ;only one expression = tail value >>> (1/0) ;nothing broke. Yet. Just don't ever use this. It's not even in the right syntax. >> (and #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #f '(<--scumbag false)) >>> #f
(or (condition) ... (more conditions))
or statement takes in only expressions to use as conditions. If any one of these statements return true, then the entire expression returns true. This means that the expression will always try to evaluate all of its arguments.
(or #f #f #f #f #f #f #f #f #f #f #f #f 1/0)
In Scheme, pairs will often be expressed using dot notation. The two values in a dotted pair are separated by a dot.
> (equal? (cons 1 2) '(1 . 2)) #t > (equal? '(1 2 3 4) '(1 . (2 . (3 . (4 . ()))))) #t
In the following example, the first expression is false because '(1 2) represents a list in which the first value is 1 and the second value is another list with first value 1 and second value null. '(1 . 2) simply represents the pair in which the first value is 1 and the second value is 2.
> (equal? '(1 2) '(1 . 2)) #f > (equal? '(1 2) (cons 1 (cons 2 ()))) #t > (equal? '(1 . 2) (cons 1 2)) #t
Lambda functions work just like they do in Python. By defining a lambda function and assigning it to a variable, you are then able to call that function by applying that variable.
STk> (define x (lambda (y) (* y y))) x STk> (x 4) 16
They can also be used as a type of operator. Just like we would use addition or multiplication. Lambda allow for more flexibility, however.
STk> (+ 4 4) 8 ((lambda (a b) (+ a b)) 4 4) ;These two lines do the same thing 8
cons statement allows users to join together values to form lists. There are a few distinct cases in which the
cons statement produces different results.
1. "Cons-ing" two single values produces what is known as a "badly formed list". A pair, separated by a dot.
STk> (cons 4 5) (4 . 5)
Continuing to "cons" on single values continues the "badly formed list".
STk> (define x (cons 4 5)) x STk> x (4 . 5) STk> (cons x 6) ((4 . 5) . 6) STk> (define y (cons x 6)) y STk> y ((4 . 5) . 6) STk> (cons y 7) (((4 . 5) . 6) . 7)
2. A correctly formed list, using
cons requires a special format. Any time a dot is followed by a left parentheses in Scheme, it collapses to create a list. For instance.
STk> (cons 5 nil) (5)
What would have ordinarily been
(5 . ()) now turns into
(5). Here's a better example of how to create a list using
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) (1 2 3 4)
Cons is ultimately useful in recursive processes that require one element to be added at a time. Each recursive step can be completed by using
cons to link one element to a growing list.
car statement allows the user to draw the first element from a list. The
cdr statement provides the "rest" of the list, returning a list that includes every element except the first one. These two statements can be used to traverse any list and obtain their elements for processing.
STk> (car (list 1 2 3)) 1 STk> (cdr (list 1 2 3)) (2 3) STk> (define lst (list (list 1 2 3) 4 5)) ;( ( 1 2 3) 4 5 ) lst STk> (car lst ) (1 2 3) STk> (car (car lst )) 1 STk> (cdr (car lst )) (2 3) STk> (car (cdr (car lst ))) 2
cdr are invaluable tools to navigating and creating scheme algorithms.