Scheme
Table of Contents
1. Expressions
Scheme programs consist of expressions, which can be:
- primitive expressions:
2,3.3,true,+,quotient, etc. - combinations:
(quotient 10 2),(not true), etc.
1.1. Call Expressions
Call expressions are a type of combination, which include an operator and zero or more operands in parantheses:
(<operator> <operand> ...)
Call expressions can also be spread across multiple lines:
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
In Scheme, spacing and indentation don't matter, as long as you close all of the parantheses that you open.
1.1.1. Arithmetic Operators
Scheme includes the four basic arithmetic operators:
(+ 1 2)
(* 1 2)
(- 1 2)
(/ 1 2)
1.2. Special Forms
A combination that is not a call expression is known as a special form.
1.2.1. if Expression
The if expression evaluates the predicate expression, and then evaluates the consequent if it is true and the alternative otherwise:
(if <predicate> <consequent> <alternative>)
1.2.2. cond Expression
The cond expression behaves like if-elif-else statements in Python. For example, the following Python code:
if x > 10:
print('big')
elif x > 5:
print('medium')
else:
print('small')
can instead by written using cond expressions in Scheme like so:
(print
(cond ((> x 10) 'big)
((> x 5) 'medium)
(else 'small)))
1.2.3. begin Expression
The begin expression combines multiple expressions into one expression:
(begin <expression> ...)
1.2.4. Boolean Expressions
and and or are special forms that evaluate to booleans:
(and <e1> ...)
(or <e1> ...)
1.2.5. Defining Symbols
Binding a symbol to some expression is a special form:
(define <symbol> <expression>)
We can use this to define a variable:
(define pi 3.14)
This can also be used to define a new procedure, which can be differentiated from a variable by noting the presence of parantheses in the first operand:
(define (abs x)
(if (< x 0)
(- x)
x))
Procedures are similar to functions, which are a reusable block of code that can take arguments, perform some computation, and then evaluate to some result. Note that there is no return in Scheme; the value of a call expression is the value of the last body expression of the procedure.
1.3. Lambda Expressions
In Scheme, lambda expressions evaluate to anonymous procedures:
(lambda (<parameter> ...) <body>)
For example, the following two expressions are equivalent:
(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))
2. Recursion
Scheme has no for/while statements, so recursion is required to iterate. In Python, to sum the first n numbers:
def sum_first_n(n):
k = 1
total = 0
while k <= n:
k, total = k + 1, total + k
return total
However, in Scheme, we can do:
(define (sum-first-n n)
(define (f k total)
(if (> k n)
total
(f (+ k 1) (+ total k))))
(f 1 0))
3. Lists
Scheme has pairs, which are created with the cons built-in function, and accessed using car and cdr:
(define x (cons 1 2))
(car x) ; 1
(cdr x) ; 2
Lists in Scheme are defined using recursive pairs, like so:
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
The empty list is denoted with nil or '(). We can also use:
(list 1 2 3 4)
Whether a list is empty can be determined using null?.
3.1. Built-in List Procedures
We can also merge another list onto the end of one list by using the append procedure:
(define s (list 1 2 3))
(append s s) ; (1 2 3 1 2 3)
We can call a procedure f on each element of a list and list the results using the map procedure:
(map (lambda (x) (* x 2)) (list 1 2 3 4)) ; (2 4 6 8)
We can filter elements in a list based on a condition and then list the results using the filter procedure:
(filter (lambda (x) (= 0 (modulo x 2))) (list 1 2 3 4)) ; (2 4)
We can apply some procedure with the items in a list as its operands with the apply procedure:
(apply + (list 1 2 3 4)) ; 10, same as (+ 1 2 3 4)
4. Symbolic Data
Scheme has the ability to work with arbitrary symbols as data. Symbols and lists, unlike primitive values, are not self-evaluating. This is because a symbol in the source code does a variable lookup. For example, doing (+ 1 2) looks at the first element, the + symbol, and looks up the function associated with it.
Therefore, to "turn off" this special evaluating behavior for arbitrary symbols, we can quote them. Suppose we want to construct the list (a b). We can't accomplish this with (list a b), because this would construct a list of the values associated with a and b instead of a and b themselves. Instead, we could do:
(define a 1)
(define b 2)
(list a b) ; (1 2)
(list 'a 'b) ; (a b)
No matter what you give quote, it will always spit the same thing back out. Note that quoting a list will distribute itself over its arguments, so '(+ 1 2) is the same as (list '+ '1 '2).
4.1. Expressions as Lists
The built-in list data structure can be used to represent combinations. For example, the combination (quotient 10 2) can be constructed with (list 'quotient 10 2). We can then evaluate this combination (that is represented by a list) using (eval (list 'quotient 10 2)), which returns 5.
We can also use this idea to return expressions from procedures. In the example below, fact calculates the factorial of a number, but fact-exp returns the expression that evaluates to the factorial of a number:
(define (fact n)
(if (= n 0) 1 (* n (fact (- n 1)))))
(define (fact-exp n)
(if (= n 0) 1 (list '* n (fact-exp (- n 1)))))
(fact 5) ; 120
(fact-exp 5) ; (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
4.2. Quasiquotation
We can also quote an expression using a quasiquote, which is done with the symbol `. The main difference between normal quotes and quasiquotes is that parts of a quasiquoted expression can be unquoted with ,: in other words, we can tell Scheme to still evaluate certain parts of a quoted list:
(define b 4)
'(a ,(+ b 1)) ; (a (unquote (+ b 1)))
`(a ,(+ b 1)) ; (a 5)
Quasiquotation is particularly convenient for generating Scheme expressions:
(define (make-add-procedure n) `(lambda (d) (+ d ,n)))
(make-add-procedure 2) ; (lambda (d) (+ d 2))
5. Macros
A macro is an operation performed on the source code that transforms it before evaluation. Scheme uses the define-macro special form that defines this transformation. For example:
(define-macro (twice expr)
(list 'begin expr expr))
(twice (print 2)) ; (begin (print 2) (print 2))
The macro "replaces" the (twice (print 2)) with the result of evaluating the macro, which is (begin (print 2) (print 2)). It binds the This is done before evaluation of the source code happens.
Example: For macro
Scheme doesn't have for loops, but we can use a macro to make one ourselves:
(define-macro (for sym vals expr)
(list 'map (list 'lambda (list sym) expr) vals))