#9: Cleaner `define*`

Tagged as challenge

Written on 2018-01-30

In challenge #8, you wrote a define macro called define*. However, this can be awkward and even inefficient when we have a cond or a case. Consider:

(define* (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Each time we compute a yet-uncomputed Fibonacci number, we have to check if it's 0 first, then 1, then we can proceed to compute.

In this challenge, we want to be allowed to define constant cases which add to the memoization table immediately. Let's call this definition procedure def. The syntax looks as follows:

(def fib
  (0) => 0
  (1) => 1
  (n) => (+ (fib (- n 1))
            (fib (- n 2))))

This will create a function fib which will have the results of (fib 0) and (fib 1) memoized, and allow for the general case. When we do call the general case for an unmemoized function, we no longer have to crawl the cond, because there is none. So we save comparisons each time it's called.

For multi-argument functions, it would be illegal to have clauses like (4 b c) => .... You can safely assume the last case will be the variable case.

Unless otherwise credited all material copyright © 2010–2018 by Robert Smith