;;; Construct a simple dictionary. (define courses '((1505ICT . "Programming II") (2503ICT . "Web Programming") (3130CIT . "Theory of Computation") (3136CIT . "Programming Language Implementation"))) ;;; (find key dict) returns the binding for key in dict, else '(). (define (find key dict) (cond ((null? dict) '()) ((equal? key (caar dict)) (car dict)) (else (find key (cdr dict))))) ;;; (map f vals) returns the list resulting from ;;; applying function f to each value in the list values. (define (map f vals) (if (null? vals) '() (cons (f (first vals)) (map f (rest vals))))) ;;; (factorial n) returns n factorial, for n>=0 (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) ;;; (factorial n) returns n factorial, for n>=0, ;;; using an iterative local definition. (define (factorial n) (define (f-iter n val) (if (= n 0) val (f-iter (- n 1) (* val n)))) (f-iter n 1)) ;;; Here's another example of the same transformation... ;;; (fib n) returns the n'th Fibonacci number, for n>=0 (define (fib n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))) ;;; An iterative implementation of the same function (define (fib n) (define (f-iter n val prev-val) (if (<= n 1) val (f-iter (- n 1) (+ val prev-val) val))) (f-iter n 1 1)) ;;; (sqrt x) returns an approximation to the square root of x, ;;; iteratively, using several local definitions. (define (sqrt x) (define (good-enough? guess) (< (abs (- (* guess guess) x)) 0.0001)) (define (improve guess) (/ (+ guess (/ x guess)) 2)) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0) ) ;;; Returns ascending list of all prime factors of positive integer n ;;; (in imperative programming style). (define (factors n) (let ((fs '())) (do ((f 2)) ((or (= n 1) (> (remainder n 2) 0))) (set! n (quotient n 2)) (set! fs (cons 2 fs))) (do ((f 3 (+ f 2))) ((or (= n 1) (> (* f f) n))) (do ((f f)) ((or (= n 1) (> (remainder n f) 0))) (set! n (quotient n f)) (set! fs (cons f fs)))) (if (> n 1) (set! fs (cons n fs))) (reverse fs))) ;;; The remaining functions implement a simple expression evaluator. ;;; See the separate sequence of evaluators for alternatives. ;;; (ev exp) returns the value of the arithmetic expression ex. ;;; Examples of legal expressions are 1, (+ 1 2), (+ (* 1 2 3) 4 5). (define (ev exp) (cond ((number? exp) exp) ((sum? exp) (ap '+ (map ev (summands exp)))) ((product? exp) (ap '* (map ev (factors exp)))) (else (error ("invalid expression" exp))))) ;;; (ap proc args) returns the result of applying procedure proc ;;; to arguments args. (define (ap proc args) (cond ((equal? proc '+) (sum args)) ((equal? proc '*) (product args)) (else (error "invalid procedure for ap" proc)))) ;;; (sum args) returns the sum of the numbers in args. (define (sum args) (if (null? args) 0 (+ (first args) (sum (rest args))))) ;;; (product args) returns the product of the numbers in args. (define (product args) (if (null? args) 1 (* (first args) (product (rest args))))) ;;; (deriv exp var) returns the result of differentiating ;;; the symbolic expression exp wrt the variable var. (define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) ; e.g., (+ 2 x (* 3 y)) (make-sum (map (lambda (exp) (deriv exp var)) (summands exp)))) ((product? exp) ; e.g., (* (+ x 1) (* (+ 2 y) 3)) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var)) (make-product (deriv (multiplier exp) var) (multiplicand exp)))) (else (error "unknown expression type -- DERIV" exp)))) ;;; Utility functions ;;; (define first car) (define rest cdr) (define (sum? exp) (and (pair? exp) (equal? (operator exp) '+))) (define (summands exp) (cdr exp)) (define (product? exp) (and (pair? exp) (equal? (operator exp) '*))) (define (factors exp) (cdr exp)) (define variable? symbol?) (define same-variable? equal?) (define operator car) (define (make-sum args) (cons '+ args)) (define (make-product args) (cons '* product)) (define (multiplier exp) (cadr exp)) (define (multiplicand exp) (caddr exp))