I've been going through SICP again (this time I'm going to go all the way through it), and I got distracted after solving exercise 1.19. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.19 Spoiler alert: If you haven't encountered this exercise yet, it's very fun to try solving by yourself first. I initially tried it using sweet expressions atop guile (http://readable.sourceforge.net), but I wasn't happy with how it looked: ;; T:
;; a = a + b
;; b = a
;;
;; T_pq:
;; a' = ap + (b+a)q
;; b' = bp + aq
;;
;; T_pq^2:
;; a'' = b'q + a'q + a'p
;; = (bp + aq)q + (bq + aq + ap)(p + q)
;; = bpq + aqq + bpq + apq + app + bqq + aqq + apq
;; = (a+b)2pq + (a+b)qq + a(pp + qq)
;; = a(pp+qq) + (b+a)(2pq+qq)
;;
;; b'' = b'p + a'q
;; = (bp + aq)p + (bq + aq + ap)q
;; = bpp + apq + bqq + aqq + apq
;; = b(pp+qq) + a(2pq+qq)
;;
;; Therefore, T_pq^2 = T_(pp+qq)(2pq+qq)
define fib2(n)
fib-iter(1 0 0 1 n)
define fib-iter(a b p q n)
cond
{n = 0} b
even?(n) fib-iter(a
b
{square(p) + square(q)}
{{2 * p * q} + square(q)}
{n / 2})
else fib-iter({{b * q} + {a * q} + {a * p}}
{{b * p} + {a * q}}
p
q
{n - 1})
The curlies were too visually heavy, and the ability to use infix was counterbalanced by requiring spaces around operators.In wart: def fib-iter(a b p q n)
(if
(iso n 0)
b
even?.n
(fib-iter a
b
(+ square.p square.q)
(+ square.q (* 2 p q))
(/ n 2))
:else
(fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- n 1)))
Mildly better, but it still suffered from the lisp problem that arithmetic becomes hard to read.I find the right macro helps group sums and products separately far better than infix: mac perform(op1 op2 . list-of-args/over)
`(,op1 ,@(map (fn(args) `(,op2 ,@args))
list-of-args))
Now: def fib-iter(a b p q n)
(if
(iso n 0)
b
even?.n
(fib-iter a
b
(perform + * :over p.p q.q)
(perform + * :over q.q (2 p q))
(/ n 2))
:else
(fib-iter (perform + * :over b.q a.q a.p)
(perform + * :over b.p a.q)
p
q
(- n 1)))
What do y'all think? Too clever? Is there a nicer way to write it in Shen or Nulan? |