9.5 Suppose f is a function of one (real) argument, and that
min and max are nonzero reals such that
f has a root (returns zero) for one argument i such
that min<i<max, and
f(min) and f(max) have different signs. Define a
function, findRoot, that takes four argument, f,
min, max, and epsilon, and returns
an approximation of i accurate to within plus or minus that value
of epsilon.
For example,
> (findRoot #'(lambda (z) (- (* z z) 9.0)) -2.0 5.0 .01)
Should return a number between 2.99 and 3.01, as the given function (here, a lambda expression) has a root at 3.00.
;;; My solution to the "find the root problem" is to use Newton's method.
;;; Pretty standard stuff: at each iteration, move MIN halfway toward MAX.
;;; If MIN has gone past the root, move MAX to that location, and MIN to
;;; its previous location, thus guaranteeing that the root is always
;;; between MIN and MAX. When f(MIN) is within epsilon of 0, return MIN as
;;; the result. Below, I've added some debugging code so that you can
;;; watch the movements of MIN and MAX during an execution.
(defun findroot (f min max epsilon)
(if (< (abs (funcall f min)) (abs epsilon))
min
(let ((diff (- max min))
(f-at-min (funcall f min))
(f-at-max (funcall f max)))
(cond
((or (and (plusp f-at-max) (minusp f-at-min))
(and (minusp f-at-max) (plusp f-at-min)))
(format t "Min = ~12f, Diff = ~12f~%" min diff)
(findroot f (+ min (/ diff 2.0)) max epsilon))
(t
(findroot f (- min diff) min epsilon))))))
> (findRoot #'(lambda (z) (- (* z z) 7.0)) -5.0 2.0 .01)
Min = -5.0, Diff = 7.0
Min = -5.0, Diff = 3.5
Min = -3.25, Diff = 1.75
Min = -3.25, Diff = 0.875
Min = -2.8125, Diff = 0.4375
Min = -2.8125, Diff = 0.21875
Min = -2.703125, Diff = 0.109375
Min = -2.6484375, Diff = 0.0546875
Min = -2.6484375, Diff = 0.02734375
Min = -2.6484375, Diff = 0.013671875
Min = -2.6484375, Diff = 0.0068359375
-2.64501953125
>
10.1 If x is a, y is b, and z is (c d), write backquoted expressions containing only variables that yield each of the following:((c d) a z)
(x b c d)
((c d a) z)
10.3 Define a macro, nth-expr, that takes a number n followed by one or more expressions, and returns that value of the nth expression:
> (let ((n 2))
(nth-expr n (/ 1 0) (+ 1 2) (/ 1 3)))
3
Note: The book does not explain very well when macro
expansion actually occurs, which is at compile-time, which precedes
execution-time. This means that nth-expr cannot access the value of the
variable n during macro expansion, because n has no value until
execution-time.
Recall the read-eval-print loop. The evaluation of the let
expression above would occur something like this: the reader receives the
let s-expression and attempts to parse it. It detects that
one of the symbols, nth-exp, references a macro. The macro is
executed, resulting in a piece of code, which effectively takes the place
of the nth-exp s-expression. The resulting s-expression would
look something like:
(let ((n 2)) <result of macro
expansion>)
This completes the reader's work, and this
s-expression is passed on to the evaluator. The evaluator sees the
let and instantiates the variable n on the
program stack, giving it a value of 2. Only now can the value of
n be referenced (i.e., can n be evaluated). In
particular, <result of macro expansion> could contain references to
n.
;;;The following solution works, but is inefficient, because the expression
;;;to be executed can't be evaluted until execution time--i.e., it can't be
;;;compiled. This could be a problem if the expression is particularly
;;;large, instead of a simple atom, as below.
(defmacro nth-exp (n &rest body)
`(eval (nth ,n ',body)))
> (macroexpand-1 '(let ((bob 1)) (nth-exp bob 'first 'second 'third)))
((LAMBDA (BOB) (NTH-EXP BOB (QUOTE FIRST) (QUOTE SECOND) (QUOTE THIRD))) 1)
T
> (let ((bob 1)) (nth-exp bob 'first 'second 'third))
SECOND
;;; The next implementation of the macro is much better. It expands into a
;;; CASE statement, which can be compiled fully at compile-time.
(defmacro nth-exp (n &rest body)
(let ((exp-counter -1))
`(case ,n
,@(mapcar
#'(lambda (exp) (incf exp-counter) `(,exp-counter ,exp))
body))))
> (macroexpand-1 '(nth-exp bob 'first 'second 'third))
(CASE BOB (0 (QUOTE FIRST)) (1 (QUOTE SECOND)) (2 (QUOTE THIRD)))
T
>
10.4 Define ntimes (page 167) to expand into a (local) recursive function instead of a do.
Note: the macro is not itself recursive, just the code
that it expands into. You'll want to look into the use of either
flet or labels.
(defmacro ntimes (n &rest body)
(let ((fnctName (gensym))
(cntrName (gensym)))
`(labels ((,fnctName (,cntrName)
(when (< 0 ,cntrName)
,@body
(,fnctName (1- ,cntrName)))))
(,fnctName ,n))))
10.6 Define a macro, protect, that takes a list of variables and a body of code, and ensures that the variables revert to their original values after the body of code is evaluated.For example,
(let ((x 3))
(protect (x)
(setq x (* x 2))
(format t "Doubled value of x is ~d~%" x))
(format t "Value of x is ~d~%" x))Should print out "Doubled value of x is 6" and then "Value of x is 3".
(defmacro protect (vars &rest body)
`(let ,(mapcar #'list vars vars)
,@body))