Lisp application areas:
(function arg1 arg2 ... argN)
This means all functions, including arithmetic ones, have prefix syntax. Arguments are passed by value (except with special forms, discussed later, to allow for things such as short circuiting for boolean operators).
Examples:(+ 2 3) (abs -4) (+ (* 2 3) 8) (+ 3 4 5 1) ;; note that + and * can take an arbitrary number of arguments ;; actually so can - and / but you'll get a headache trying to remember ;; what it means ;; ;; semicolon means the rest of the line is a comment
(x) (elmer fudd) (2 3 5 7 11) (2 3 x y "zoo" 2.9) ()Box-and-arrow representation of lists:
_______________ ________________ | | | | | | | o | ----|----->| o | o | |___|___|_______| |____|___|___|___| | | | | | | elmer fudd ()Or
_______________ _____________ | | | | | / | | o | ----|----->| o | / | |___|___|_______| |____|___|/___| | | | | elmer fudd
Notes:
Scheme also predefines compositions of
car
and cdr
, e.g., (cadr s)
is
defined as (car (cdr s))
.) All 28 combinations of 2, 3, and 4
a's and d's are defined.
<S-expression> => <return-value>when we want to show an S-expression and the evaluation of that S-expression. For instance:
(+ 2 3) => 5 (not #t ) => #fEvaluation rules:
(+ 2 3) => 5 (+ (* 3 3) 10) => 19 (= 10 (+ 4 6)) => #t
'x => x (list elmer fudd) => error! elmer is unbound symbol (list 'elmer 'fudd) => (elmer fudd) (elmer fudd) => error! elmer is unknown function '(elmer fudd) => (elmer fudd) (equal? (x) (x)) => error! x is unknown function (equal? '(x) '(x)) => #t (cons 'x '(y z)) => (x y z) (cons 'x '() ) => (x) (car '(1 2 3)) => 1 (cdr (cons 1 '(2 3))) => (2 3)Note that there are several ways to make a list:
'x => x (quote x) => x(Alan Perlis: "syntactic sugar causes cancer of the semicolon".)
(define symbol expression)
Using define
binds symbol
(your variable
name) to the result of evaluating expression
.
define
is a special form because the first parameter,
symbol
, is not evaluated.
The line below declares a variable called clam (if one doesn't exist) and makes it refer to 17:
(define clam 17) clam => 17 (define clam 23) ; this rebinds clam to 23 (+ clam 1) => 24
(define bert '(a b c)) (define ernie bert)Scheme uses pointers: bert and ernie now both point at the same list.
In 341 we'll only use define to bind global variables, and we won't rebind them once they are bound, except when debugging.
;; general form of let (let ((name1 value1) (name2 value2) ... (nameN valueN)) expression1 expression2 ... expressionQ) ;; reverse a list and double it ;; less efficient version: (define (r2 x) (append (reverse x) (reverse x))) ;; more efficient version: (define (r2 x) (let ((r (reverse x))) (append r r)))A problem with let in some situations is that while the bindings are being created, expressions cannot refer to bindings that have been made previously. For example, this doesn't work, since x isn't known outside the body:
(let ((x 3) (y (+ x 1))) (+ x y))To get around this problem, Scheme provides us with let*:
(let* ((x 3) (y (+ x 1))) (+ x y))Personally I prefer to use let, unless there is a particular reason to use let*.
You can use the lambda
special form to create
anonymous functions. This special form takes
(lambda (param1 param2 ... paramk) ; list of formals expr) ; body
lambda
expression evaluates to an anonymous function
that, when applied (executed), takes k arguments and returns the
result of evaluating expr
. As you would expect, the
parameters are lexically scoped and can only be used in
expr
.
Example:
(lambda (x1 x2) (* (- x1 x2) (- x1 x2)))
Evaluating the above example only results in an anonymous function,
but we're not doing anything with it yet. The result of a
lambda
expression can be directly applied by providing
arguments, as in this example, which evaluates to 49:
((lambda (x1 x2) (* (- x1 x2) (- x1 x2))) 2 -5) ; <--- note actuals here
If you go to the trouble of defining a function, you often want to
save it for later use. You accomplish this by binding the result of a
lambda
to a variable using define
, just as
you would with any other value. (This illustrates how functions are
first-class in Scheme. This usage of define
is no
different from binding variables to other kinds of values.)
(define square-diff (lambda (x1 x2) (* (- x1 x2) (- x1 x2))))
Because defining functions is a very common task, Scheme provides a
special shortcut version of define
that doesn't use
lambda
explicitly:
(define (function-name param1 param2 ... paramk) expr)
Here are some more examples using define
in this
way:
(define (double x) (* 2 x)) (double 4) => 8 (define (centigrade-to-fahrenheit c) (+ (* 1.8 c) 32.0)) (centigrade-to-fahrenheit 100.0) => 212.0The
x
in the double
function is the formal
parameter. It has scope only within the function. Consider the three
different x
's here...
(define x 10) (define (add1 x) (+ x 1)) (define (double-add x) (double (add1 x))) (double-add x) => 22
Functions can take 0 arguments:
(define (test) 3) (test) => 3
Note that this is not the same as binding a variable to a value:
(define not-a-function 3) not-a-function => 3 (not-a-function) => ;The object 3 is not applicable.
If Scheme finds a line of text with a semicolon, the rest of the line (after the semicolon) is treated as whitespace. However, a frequently used convention is that one semicolon is used for a short comment on a line of code, two semicolons are used for a comment within a function on its own line, and three semicolons are used for an introductory or global comment (outside a function definition).
(define clam '(1 2 3)) (define octopus clam) ; clam and octopus refer to the same list (eq? 'clam 'clam) => #t (eq? clam clam) => #t (eq? clam octopus) => #t (eq? clam '(1 2 3)) => #f ; (eq? '(1 2 3) '(1 2 3)) => #f (eq? 10 10) => #t ; (generally, but implementation-dependent) (eq? 10.0 10.0) => #f ; (generally, but implementation-dependent) (eqv? 10 10) => #t ; always (eqv? 10.0 10.0) => #t ; always (eqv? 10.0 10) => #f ; no conversion between types (equal? clam '(1 2 3)) => #t (equal? '(1 2 3) '(1 2 3)) => #tScheme provides
=
for comparing
two numbers, and will coerce one type to another.
For example, (equal? 0 0.0)
returns #f
, but
(= 0 0.0)
returns #t
.
#t
or #f
(like
the && and || operators in Java and C++). However, one could
easily write a version that evaluates all of its arguments.
(and expr1 expr2 ... expr-n) ; return true if all the expr's are true ; ... or more precisely, return expr-n if all the expr's evaluate to ; something other than #f. Otherwise return #f (and (equal? 2 3) (equal? 2 2) #t) => #f (or expr1 expr2 ... expr-n) ; return true if at least one of the expr's is true ; ... or more precisely, return expr-j if expr-j is the first expr that ; evaluates to something other than #f. Otherwise return #f. (or (equal? 2 3) (equal? 2 2) #t) => #t (or (equal? 2 3) 'fred (equal? 3 (/ 1 0))) => 'fred (define (single-digit x) (and (> x 0) (< x 10))) (not expr) ; return true if expr is false (not (= 10 20)) => #t
(if condition true_expression false_expression)
If condition
evaluates to true, then the result of
evaluating true_expression
is returned; otherwise the
result of evaluating false_expression
is returned.
if is a special form, like quote
, because it
does not automatically evaluate all of its arguments.
(if (= 5 (+ 2 3)) 10 20) => 10 (if (= 0 1) (/ 1 0) (+ 2 3)) => 5 ; note that the (/ 1 0) is not evaluated (define (my-max x y) (if (> x y) x y)) (my-max 10 20) => 20 (define (my-max3 x y z) (if (and (> x y) (> x z)) x (if (> y z) y z)))
(cond (test1 expr1) (test2 expr2) .... (else exprn))As soon as we find a test that evaluates to true, then we evaluate the corresponding expr and return its value. The remaining tests are not evaluated, and all the other expr's are not evaluated. If none of the tests evaluate to true then we evaluate exprn (the "else" part) and return its value. (You can leave off the else part but it's not good style.)
(define (sign n) (cond ((> n 0) 1) ((< n 0) -1) (else 0)))
A tail recursive function is one that returns the result of the recursive call back without alteration. (So unlike a function like append, we don't build up a solution as the recursion unwinds.) Examples:
(define (all-positive x) (cond ((null? x) #t) ((<= (car x) 0) #f) (else (all-positive (cdr x))))) ;; (all-positive '(3 5 6)) => #t ;; (all-positive '(3 5 -6)) => #f (define (my-member e x) (cond ((null? x) #f) ((equal? e (car x)) #t) (else (my-member e (cdr x)))))
Scheme compilers handle tail recursion very efficiently, as efficiently as a program that just uses loops instead of recursion. (In particular, tail recursive functions don't use stack space for every recursive call.)
(define (std-factorial n) (if (zero? n) 1 (* n (std-factorial (- n 1)))))Here is a version that is tail recursive:
(define (factorial n) (acc-factorial n 1)) ;; auxiliary function that takes an additional parameter (the accumulator, ;; i.e. the result computed so far) (define (acc-factorial n sofar) (if (zero? n) sofar (acc-factorial (- n 1) (* sofar n))))
Scheme includes higher-order functions such as map and filter, similar to those in Haskell:
(map function list) ;; general form (map null? '(3 () () 5)) => (() T T ()) (map round '(3 3.3 4.6 5)) => (3 3 5 5) (map cdr '((1 2) (3 4) (5 6))) => ((2) (4) (6)) (map (lambda (x) (* 2 x)) '(3 4 5)) (filter (lambda (n) (> n 10)) '(5 10 15 20)) => (15 20) (define (add-n-to-list alist n) (map (lambda (x) (+ n x)) alist))
Note that in the add-n-to-list function, the body of the lambda function can refer to the variable n, which is in the lexical scope of the lambda expression.
map can also be used with functions that take more than one argument. Examples:
(map + '(1 2 3) '(10 11 12)) => (11 13 15) (map (lambda (x y) (list x y)) '(a b c) '(j k l)) => ((a j) (b k) (c l))
(This doesn't work in Haskell. Why not?)
(define (my-map f s) (if (null? s) '() (cons (f (car s)) (my-map f (cdr s)))))
(define (add-n-to-list alist n) (my-map (lambda (x) (+ n x)) alist))When the lambda expression is used in my-map, it needs to know where to look up the variable name n. It can get the right value for n, because it retains its lexical environment.
As an example, let's define a simple function test:
(define (test x) (+ x 1))Evaluating (test 10) gives 11.
However, if we evaluate
(let ((test (lambda (x) (* x 2))) (test 10))we get 20 -- within the let, test is rebound to a different function.