2

I'm reading Peter Norvig's Paradigms of AI. In chapter 6.2, the author uses code like below (not the original code, I picked out the troubling part):

Code Snippet:

(progv '(op arg) '(1+ 1)
(eval '(op arg)))

As the author's original intent, this code should return 2, but in sbcl 1.1.1, the interpreter is apparently not looking up op in the environment, throwing out op: undefined function.

Is this implementation specific? Since the code must have been tested on some other lisp.

p.s Original code

Denim Datta
  • 3,740
  • 3
  • 27
  • 53
Jiaji
  • 175
  • 11

4 Answers4

5

You probably mean

(progv '(op arg) '(1+ 1)
  (eval '(funcall op arg)))

Edit(2013-08-21):

PAIP was written in pre-ANSI-Common-Lisp era, so it's possible the code there contains a few noncompliances wrt the standard. We can make the examples work with the following revision:

(defun match-if (pattern input bindings)
  "Test an arbitrary expression involving variables.
  The pattern looks like ((?if code) . rest)."
  (and (eval (reduce (lambda (code binding)
                       (destructuring-bind (var . val) binding
                         (subst val var code)))
                     bindings :initial-value (second (first pattern))))
       (pat-match (rest pattern) input bindings)))

;; CL-USER> (pat-match '(?x ?op ?y is ?z (?if (eql (?op ?x ?y) ?z))) '(3 + 4 is 7))
;; ((?Z . 7) (?Y . 4) (?OP . +) (?X . 3) (T . T))
;; CL-USER> (pat-match '(?x ?op ?y (?if (?op ?x ?y))) '(3 > 4))
;; NIL
huaiyuan
  • 26,129
  • 5
  • 57
  • 63
  • I think I mean it the other way, please look at Norvig's [original text](http://books.google.com.hk/books?id=QzGuHnDhvZIC&lpg=PA186&vq=here%20are%20two%20examples%20using%20%3Fif&pg=PA186#v=snippet&q=here%20are%20two%20examples%20using%20?if&f=false). – Jiaji Aug 21 '13 at 03:28
  • 1
    Following works without changing PAIP code: (pat-match '(?x ?op ?y is ?z (?if (eql (funcall ?op ?x ?y) ?z))) '(3 + 4 is 7)) – ahsankhan Feb 19 '14 at 02:32
  • @ahsankhan - agreed, much the easiest way. – QuesterZen Apr 10 '18 at 04:13
  • The alternative would be to write a new version of 'eval' for the pattern-matcher that either tests for bindings that are functions, or spots binding variables in the car position of an evaluated cons pair and adds funcall to the expression - either way is a bit messy. Using 'subst' as suggested by huaiyuan is a nice quick fix, but potentially changes the evaluation value, although it doesn't seem to matter for any of the uses in the book. Personally, coming from Scheme to Common Lisp, I find the function-namespace thing irritating. – QuesterZen Apr 10 '18 at 04:30
  • @Jiaji, Norvig's code doesn't work in my version SBCL because (eval '(op arg)) is not correct code in ANSI-Common Lisp when op is bound to a function, but may have been OK in whichever version of Common Lisp he was using (perhaps it had a smarter progv implementation?). (progv '(op arg) '(1+ 1) (eval '(funcall op arg))) is necessary. How to get the pattern matcher to do the right thing is the problem. – QuesterZen Apr 10 '18 at 04:43
3

Elements in first positions are not looked up as values, but as functions and there is no concept of dynamic binding in the function namespace.

I'd say after a quick look that the original code was designed to evaluate in a context like

 (progv '(x y) '(12 34)
   (eval '(> (+ x y) 99)))

i.e. evaluating a formula providing substitution for variables, not for function names.

6502
  • 112,025
  • 15
  • 165
  • 265
  • Thanks for your reply, but the author seemed to use it my way [in his book?](http://books.google.com.hk/books?id=QzGuHnDhvZIC&lpg=PA186&vq=here%20are%20two%20examples%20using%20%3Fif&pg=PA186#v=snippet&q=here%20are%20two%20examples%20using%20?if&f=false) – Jiaji Aug 21 '13 at 03:24
2

The other answers so far are right, in that the actual form being evaluated is not the variables being bound by progv (simply (op arg)), but none have mentioned what is being evaluated. In fact, the comments in the code you linked to provide a (very) short explanation (this is the only code in that file that uses progv):

(defun match-if (pattern input bindings)
  "Test an arbitrary expression involving variables.
  The pattern looks like ((?if code) . rest)."
  ;; *** fix, rjf 10/1/92 (used to eval binding values)
  (and (progv (mapcar #'car bindings)
              (mapcar #'cdr bindings)
          (eval (second (first pattern))))
       (pat-match (rest pattern) input bindings)))

The idea is that a call to match-if gets called like

(match-if '((?if code) . rest) input ((v1 val1) (v2 val2) ...))

and eval is called with (second (first pattern)), which the value of code. However, eval is called within the progv that binds v1, v2, &c., to the corresponding val1, val2, &c., so that if any of those variables appear free in code, then they are bound when code is evaluated.

Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
0

Problem

The problem that I see here is that, by the code we can't tell if the value is to be saved as the variable's symbol-value or symbol-function. Thus when you put a + as a value to some corresponding variable, say v, then it'll always be saved as the symbol-value of var, not it's symbol-function.
Therefore when you'll try to use it as, say (v 1 2) , it won't work. Because there is no function named v in the functions' namespace(see this).

So, what to do?

A probable solution can be explicit checking for the value that is to be bound to a variable. If the value is a function, then it should be bound to the variable's function value. This checking can be done via fboundp.

So, we can make a macro functioner and a modified version of match-if. functioner checks if the value is a function, and sets it aptly. match-if does the dynamic local bindings, and allows other code in the scope of the bound variables. 

(defmacro functioner (var val)
  `(if (and (symbolp ',val)
            (fboundp ',val))
       (setf (symbol-function ',var) #',val)
       (setf ,var ,val)))


(defun match-if (pattern input bindings)
  (eval `(and (let ,(mapcar #'(lambda (x) (list (car x))) bindings)
                (declare (special ,@ (mapcar #'car bindings)))
                (loop for i in ',bindings
                      do (eval `(functioner ,(first i) ,(rest i))))
                (eval (second (first ',pattern))))
              (pat-match (rest ',pattern) ',input ',bindings))))
Mooncrater
  • 4,146
  • 4
  • 33
  • 62