Programs as data
- A scheme expression is just a scheme list. Thus, we may use scheme to write scheme programs ourselves
- Built-in Scheme list data strucutre may represent combinations
- Ex:
1
2
3
4
scm> (list 'quotient 10 2)
(quotient 10 2)
scm> (eval (list 'quotient 10 2))
5
-Ex: fact procedure to generate an expression to calculate a factorial
1
2
3
4
5
6
7
8
scm> (define (fact-exp n) (if (<= n 1) n (list '* n (fact-exp (- n 1)))))
fact-exp
scm> (fact-exp 4)
(* 4 (* 3 (* 2 1)))
scm> (list? (fact-exp 4))
#t
scm> (eval (fact-exp 4))
24
Discussion Question: Automatically Simplifying Code
- We want to flatten a nested expression, in this case
- Ex: (* 1 2 (* 3 (* 4)) (+ 5 (* 6 (* 7 8)))) to (* 1 2 3 4 (+ 5 (* 6 7 8)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (is-*-call expr)
(and (list? expr) (equal? '* (car expr)))
)
(define flatten-nested-* expr
(if (not (list? expr))
expr
(let ((expr (map flatten-nested-* expr))) ; Now expr is (* 1 2 (* 3 4) (+ 5 (*6 7 8)))
(if (is-*-call expr)
(apply append (map (lambda (e) (if (is-*-call e) (cdr e) (list e))) expr))
expr
)
)
)
)