Function name and dynamic binding in Common Lisp

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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))))