I'm reading Peter Norvig's <Paradigms of Artificial Intelligence
Programming>. In section 9.6, there's an example showing how to compile
algebra simplification rules into LISP code. I'm quite confused about
the idea showed in the compiler, especially why use delayed evaluation
here. The book didn't give a detailed explanation. Can anybody give me
some clue how to understand the following code?
;;; single rule compiler
(defvar *bindings* nil
"A list of bindings used by the rule compiler.")
(defun compile-rule (rule)
"Compile a single rule."
(let ((*bindings* nil))
`(lambda (x)
,(compile-exp 'x (exp-lhs rule) ; x is the lambda parameter
(delay (build-exp (exp-rhs rule)
*bindings*))))))
(defun compile-exp (var pattern consequent)
;; consequent is a continuation function,
;; it means the continuation for generating the code is the test
passes.
"Compile code that tests the expression, and does consequent
if it matches. Assumes bindings in *bindings*."
(cond ((get-binding pattern *bindings*)
;; Test a previously bound variable
`(if (equal ,var ,(lookup pattern *bindings*))
,(force consequent)))
((variable? pattern)
;; Add a new bindings; do type checking if needed.
(push (cons pattern var) *bindings*)
(force consequent))
((atom pattern)
;; Match a literal atom
`(if (eql ,var ',pattern)
,(force consequent)))
((starts-with pattern '?is)
(push (cons (second pattern) var) *bindings*)
`(if (,(third pattern) ,var)
,(force consequent)))
;; So, far, only the ?is pattern is covered, because
;; it is the only one used in simplification rules.
;; Other patterns could be compiled by adding code here.
;; Or we could switch to a data-driven approach.
(t ;; Check the oprerator and arguments
`(if (op? ,var ',(exp-op pattern))
,(compile-args var pattern consequent)))))
(defun compile-args (var pattern consequent)
"Compile code that checks the arg or args, and
does consequent if the arg(s) match."
;; First make up variable names for the arg(s).
(let ((L (symbol var 'L))
(R (symbol var 'R)))
(if (exp-rhs pattern)
;; two arg case
`(let ((,L (exp-lhs ,var))
(,R (exp-rhs ,var)))
,(compile-exp L (exp-lhs pattern)
(delay
(compile-exp R (exp-rhs pattern)
consequent))))
;; one arg case
`(let ((,L (exp-lhs ,var)))
,(compile-exp L (exp-lhs pattern) consequent)))))
(defun build-exp (exp bindings)
"Compile code that will build the exp, given the bindings."
(cond ((assoc exp bindings) (rest (assoc exp bindings)))
((variable? exp)
(error "Variable ~a occurred on right-hand side, but not
left." exp))
((atom exp) `',exp)
(t (let ((new-exp (mapcar #'(lambda (x)
(build-exp x bindings))
exp)))
`(simplify-exp (list ,@new-exp))))))
(defun op? (exp op)
"Does the exp have the given op as its operator?"
(and (exp? exp) (eq (exp-op exp) op)))
(defun exp? (x)
"Is x a valid expression?"
(listp x))
(defun symbol (&rest args)
"Concatenate symbols or strings to form an interned symbol."
(intern (format nil "~{~a~}" args)))
===========================================
;;; Running examples
;; simp-rule :- expression with infix operators ==> expression with
prefix operators
(compile-rule (simp-rule '(log (e ^ x) = x)))
==>
(LAMBDA (X)
(IF (OP? X 'LOG)
(LET ((XL (EXP-LHS X)))
(IF (OP? XL '^)
(LET ((XLL (EXP-LHS XL)) (XLR (EXP-RHS XL)))
(IF (EQL XLL 'E) XLR)))))
;;; another example in the book
;;; assume we have defined that N and M can only be matched to numbers
;;; X can be anything (number or expression).
(compile-rule (simp-rule '(n * (m * x) = (n * m) * x)))
==>
(LAMBDA (X)
(IF (OP? X '*)
(LET ((XL (EXP-LHS X)) (XR (EXP-RHS X)))
(IF (NUMBERP XL)
(IF (OP? XR '*)
(LET ((XRL (EXP-LHS XR)) (XRR (EXP-RHS XR)))
(IF (NUMBERP XRL)
(SIMPLIFY-EXP (LIST
'*
(SIMPLIFY-EXP (LIST '* XL XRL))
XRR))))))))
"Pebblestone" <··········@gmail.com> writes:
> I'm reading Peter Norvig's <Paradigms of Artificial Intelligence
> Programming>. In section 9.6, there's an example showing how to compile
> algebra simplification rules into LISP code. I'm quite confused about
> the idea showed in the compiler, especially why use delayed evaluation
> here. The book didn't give a detailed explanation. Can anybody give me
> some clue how to understand the following code?
>
>
> ;;; single rule compiler
> (defvar *bindings* nil
> "A list of bindings used by the rule compiler.")
>
> (defun compile-rule (rule)
> "Compile a single rule."
> (let ((*bindings* nil))
> `(lambda (x)
> ,(compile-exp 'x (exp-lhs rule) ; x is the lambda parameter
> (delay (build-exp (exp-rhs rule)
> *bindings*))))))
>
> (defun compile-exp (var pattern consequent)
> ;; consequent is a continuation function,
> ;; it means the continuation for generating the code is the test
> passes.
Because when you call a function such as COMPILE-EXP, all the
arguments to the functions are _evaluated_ even before the function
call.
Wel don't want to call: (build-exp (exp-rhs rule) *bindings*) before
compile-exp. We want this expression to be called as a continuation
of compile-exp, that is at the end of compile-exp. That's why we pass
this delayed expression. (and compile-exp explicitely forces it as the
last thing it does).
Now, this use of DELAY and FORCE in compile-exp is made explicit
because in Common Lisp there are no real continuations. In scheme, we
would have used call/cc and had no use of delay & force.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The mighty hunter
Returns with gifts of plump birds,
Your foot just squashed one.