Auto-defining functions

Here's a puzzle I've been playing around with lately: How would you go about defining functions automatically in Common Lisp?

Try to put out of your mind why you would want to do this for the time being (I'll make my reasons for doing so known in another post).

First of all, some definitions and ground rules. "Auto-defining a function" means that if you have code executing and an attempt to evaluate a form signals an undefined function, a function is defined for the symbol and called without interrupting the evaluation. That is to say, the debugger is not entered and execution continues.

(Yes, this is fraught with potential problems, like making a function that does what was intended. Again, I'll worry about this later.)

The hurdle in this is to be able to continue the execution. I'll take advantage of restarts to accomplish this, but it requires that the Lisp implementation supply a continuable restart at the correct time. Allegro CL does, so that's what I'll use.

The general principle can be seen in this interaction at the REPL.

  CL-USER(1): (square 5)
  Error: attempt to call `SQUARE' which is an undefined function.
    [condition type: UNDEFINED-FUNCTION]

  Restart actions (select using :continue):
   0: Try calling SQUARE again.
   1: Return a value instead of calling SQUARE.
   2: Try calling a function other than SQUARE.
   3: Setf the symbol-function of SQUARE and call it again.
   4: Return to Top Level (an "abort" restart).
   5: Abort entirely from this (lisp) process.
  [1] CL-USER(2): (setf (fdefinition 'square) #'(lambda (x) (* x x)))
  #<Interpreted Function FOO>
  [1] CL-USER(3): (invoke-restart 'excl::try-again)
  25

The above is actually possible using one of the provided interactive restarts, but the goal is to avoid interaction. The name of the restart (excl::try-again) was obtained using compute-restarts and inspecting the results, which was not shown.

To do this programmatically, you need to set up a handler for undefined-function and do the above. Again, ignoring the notion of actually building a "correct" function, there is a small problem: undefined-function only tells you the name of the function and nothing about the arguments.

Getting around this can be done using a two stage process: define a dummy function that works for any number of arguments that does the real work of defining the function. This prevents the messiness that would result from trying to get this information by inspecting the stack, for example.

For demonstration purposes, I'll only be concerned with auto-defining the square function.

(defun auto-definable-function-p (name args)
  (and (eql name 'square) (= 1 (length args))))

(defun auto-define-function-stage-one (name)
  (setf (fdefinition name)
        #'(lambda (&rest args)
            (auto-define-function-stage-two name args))))

(defun auto-define-function-stage-two (name args)
  (cond
    ((auto-definable-function-p name args)
     (setf (fdefinition name) #'(lambda (arg) (* arg arg)))
     (apply name args))
    (t (fmakunbound name)
       (error 'undefined-function :name name))))

(defun handle-undefined-function (condition)
  (when (find-restart 'excl::try-again condition)
    (auto-define-function-stage-one (cell-error-name condition))
    (invoke-restart 'excl::try-again)))

(defmacro try-undefined (&body body)
  `(handler-bind
       ((undefined-function (function handle-undefined-function)))
     ,@body))

Here it is at work.

CL-USER> (fboundp 'square)
NIL
CL-USER> (trace auto-define-function-stage-one)
(AUTO-DEFINE-FUNCTION-STAGE-ONE)
CL-USER> (trace auto-define-function-stage-two)
(AUTO-DEFINE-FUNCTION-STAGE-TWO)
CL-USER> (try-undefined (square 25))
 0[7]: (AUTO-DEFINE-FUNCTION-STAGE-ONE SQUARE)
 0[7]: returned
         #<Closure (:INTERNAL AUTO-DEFINE-FUNCTION-STAGE-ONE
                    0) [SQUARE]
           @ #x105642c2>
 0[7]: (AUTO-DEFINE-FUNCTION-STAGE-TWO SQUARE (25))
 0[7]: returned 625
625
CL-USER> (fboundp 'square)
#<Function (:INTERNAL AUTO-DEFINE-FUNCTION-STAGE-TWO 0)>
CL-USER> (square 100)
10000

This is clearly a rough implementation and only a proof of concept, but it provides a foothold for further work. I've offered no compelling reason for actually doing this; I've only shown that it is technically possible to do so. I'll elaborate on the why soon enough. (It may be a bit delayed because I've started lecturing a programming languages course and I first have to convince my students that Scheme — as foreign as it is to them — isn't as awful as they may think!)