Clementson's Blog

Doing the Undoable

Wednesday, September 14, 2005

Have you ever wanted to do something that wasn't supported by your programming language? For example, trace the execution of something that wasn't trace-able? An example of this in CL might be a LABELS definition which has no global name that can be specified for a TRACE. This was the question that was recently asked on c.l.l.:

"I am currently in the phase of "paradigm switch" and I am trying to understand various beautiful recursive functions like flatten and prune (especially - their invocation order, since it's not so obvious for imperative guy like I was for several years). The functions are from On Lisp, and many examples there are written in style, when some helper function is defined using "labels", and that's the place where the core stuff is done.

But when I want to trace it (I still have some problems with invocation order), "trace" on such functions does not help, because

CL-USER> (trace flatten)
(FLATTEN)
CL-USER> *l1*
(1 2 (3 (4 5) 6) 7 8 (9))
CL-USER> (flatten *l1*)
  0: (FLATTEN (1 2 (3 # 6) 7 8 ...))
  0: FLATTEN returned (1 2 3 4 5 ...)
(1 2 3 4 5 6 7 8 9)

and it does not go into the function defined in "labels".

Is there any way how to see trace output in such functions? "

1. Recursion: By re-stating the problem with recursion, it is possible to trace the execution: [15]> (defun rec (x acc) (cond ((null x) acc) ((atom x) (cons x acc)) (t (rec (car x) (rec (cdr x) acc))))) REC [16]> (trace rec) ;; Tracing function REC. (REC) [17]> (rec '(((1 2)) 3) nil) 1. Trace: (REC '(((1 2)) 3) 'NIL) 2. Trace: (REC '(3) 'NIL) 3. Trace: (REC 'NIL 'NIL) 3. Trace: REC ==> NIL 3. Trace: (REC '3 'NIL) 3. Trace: REC ==> (3) 2. Trace: REC ==> (3) 2. Trace: (REC '((1 2)) '(3)) 3. Trace: (REC 'NIL '(3)) 3. Trace: REC ==> (3) 3. Trace: (REC '(1 2) '(3)) 4. Trace: (REC '(2) '(3)) 5. Trace: (REC 'NIL '(3)) 5. Trace: REC ==> (3) 5. Trace: (REC '2 '(3)) 5. Trace: REC ==> (2 3) 4. Trace: REC ==> (2 3) 4. Trace: (REC '1 '(2 3)) 4. Trace: REC ==> (1 2 3) 3. Trace: REC ==> (1 2 3) 2. Trace: REC ==> (1 2 3) 1. Trace: REC ==> (1 2 3) (1 2 3) [18]>
2. Re-implement TRACE: By re-implementing TRACE and shadowing the original definition, it is possible to trace the execution of the original function with the LABELS code:

   [85]> (defun flatten (x)
           (labels ((rec (x acc)
                      (cond ((null x) acc)
                            ((atom x) (cons x acc))
                            (t (rec (car x) (rec (cdr x) acc))))))
             (rec x nil)))
   FLATTEN
   [86]> (flatten '((1 (2)) 3))
   Entering REC (((1 (2)) 3) NIL)
   Entering REC ((3) NIL)
   Entering REC (NIL NIL)
   Exiting REC --> NIL
   Unwinding REC
   Entering REC (3 NIL)
   Exiting REC --> (3)
   Unwinding REC
   Exiting REC --> (3)
   Unwinding REC
   Entering REC ((1 (2)) (3))
   Entering REC (((2)) (3))
   Entering REC (NIL (3))
   Exiting REC --> (3)
   Unwinding REC
   Entering REC ((2) (3))
   Entering REC (NIL (3))
   Exiting REC --> (3)
   Unwinding REC
   Entering REC (2 (3))
   Exiting REC --> (2 3)
   Unwinding REC
   Exiting REC --> (2 3)
   Unwinding REC
   Exiting REC --> (2 3)
   Unwinding REC
   Entering REC (1 (2 3))
   Exiting REC --> (1 2 3)
   Unwinding REC
   Exiting REC --> (1 2 3)
   Unwinding REC
   Exiting REC --> (1 2 3)
   Unwinding REC
   (1 2 3)
   [87]> 

   For the curious, here is a link to the full code of Pascal's solution.

"This is a fantastic example of how Lisp *really* wins. Pascal has incrementally redefined one of the basic constructs in the language and seamlessly integrated the new definition into the system. Another user could take existing code and *without modifying it* run it in this system and have the output traced.

Few languages let you do this as easily. "