< = > and or not
(+ 1 2)
naming: assign name to something ("object")
(define foo 1)
(define (bar arg1) (+ 1 2))
environment: memory of name-object pairs
steps of "applicative order"
(define (<name> <formal parameters>) <body>)
The `<body>' part may contain multiple expressions. The value of the final expression becomes the value of the procedure application.
evaluate the body of procedure with the formal parameters replaced by the corresponding arguments
is presented to help think about the process of application, and is not how interpreter works
order of execution
if is a special form and not a procedure.
It only evalutes the predicate and one of the consequent / alternative expression.
(if (> 1 0) #t #f)
cond is a special form and not a procedure.
It only evalutes the predicates till the correct branch, and that corresponding branch.
(cond ((= a 1) 1) ((= a 2) 3))
(define (newton-sqrt aim) (define (guess-till-good-enough current next-guess good-enough?) (if (good-enough? current) current (guess-till-good-enough (next-guess current) next-guess good-enough?))) (define (small-enough? delta) (< delta 1e-5)) (define (close-enough? current) (small-enough? (abs (- (* current current) aim)))) (define (better-approximation-of-sqrt current) (/ (+ current (/ aim current)) 2)) ;; << the ``Newton'' part (define initial-guess 1.1) (guess-till-good-enough initial-guess better-approximation-of-sqrt close-enough?)) (display (newton-sqrt 2.0)) ; => 1.4142
The definition suppresses the details.
The user of a procedure does not need to know the internal.
(define (square x) (* x x))contains a bound variable
xand a free variable
Internal definitions (refer to previous
(define (close-enough? current <body>).
Recursive computation of factorial
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
Iterative computation of factorial
(define (factorial n) (define (factorial-iter cumulative-product current max) (if (> max current) cumulative-product (factorial-iter (* cumulative-product current) (+ current 1) max))) (factorial-iter 1 1 n))
The preceding 2 procedures produce different shape of computation.
Example: recursive definition of
Example: counting change
(define (change coins rest) (cond ((< rest 0) 0) ((= rest 0) 1) ((= (length coins) 0) 0) (else (+ (change coins (- rest (car coins))) (change (cdr coins) rest))))) (display (change (list 50 25 10 5 1) 100)) ; => 292
(power base exp) with linear recursion
(power base exp) with log recursion
(fib n)with log recursion (let ((a 1)) (+ a 2))
(define (prime? n) (define (find-first-divisor current) (cond ((= (remainder n current) 0) current) ((> (* current current) n) #f) (else (find-first-divisor (+ 1 current))))) (define first-divisor (find-first-divisor 2)) (if (and first-divisor (not (= n first-divisor))) #f #t))
One can create (anonymous) procedures with the special form
(lambda (formal-parameters) <body>)
(map (lambda (x) (* x x)) '(1 2 3))
One can use
lambda to bind local variables, but the special form
let makes it more convenient.
(let ((<name> <expression>)+) <body>)
"is but syntactic sugar of underlying lambda expression"
The name-expression pairs in
let are parallel. One expression cannot refer to another name.
Example: finding zero-point with the half-interval method
Example: finding fixed-point