Chapter 16 - How to Find Your Way Around, Part 2

It's once again time to take a break and learn about some more of the tools you can use to grok [1] the inner workings of Lisp and your programs. In this chapter, we'll learn what the Lisp compiler does to your code, and how to watch what your code does as it runs.

DISASSEMBLE: I always wondered what they put inside those things...

If you understand a little about compilers and assembly language -- or if you're just interminably curious -- you can find out exactly how the Lisp compiler translates your Lisp code. DISASSEMBLE takes a function name or object and lists the assembly-language instructions that would have been emitted by the Lisp compiler if it actually emitted assembly-language code -- most compilers directly generate machine instructions without invoking an assembler.

The output of DISASSEMBLE is dependent both upon the instruction set architecture of the machine you're using to run Lisp and upon the Lisp implementation itself. Here's an example of using DISASSEMBLE on a very simple function; this was done using Macintosh Common Lisp on a PowerPC processor.

? (defun add1 (n) (1+ n))
ADD1
? (disassemble 'add1)
  (TWNEI NARGS 4)
  (MFLR LOC-PC)
  (BLA .SPSAVECONTEXTVSP)
  (VPUSH ARG_Z)
  (LWZ NARGS 331 RNIL)
  (TWGTI NARGS 0)
  (LI ARG_Y '1)
  (LWZ ARG_Z 0 VSP)
  (BLA .SPRESTORECONTEXT)
  (MTLR LOC-PC)
  (BA .SPBUILTIN-PLUS)

The first thing you'll note about this listing is that it looks "Lisp-ish" with the parentheses. The second thing you'll notice -- if you are familiar with the PowerPC instruction set -- is that most of these forms are familiar; it's as if someone took part of a real PowerPC assembly language program and bracketed each line of text in parentheses. You may also notice that there are no comments in the assembly code, that there are some pseudo-instructions such as VPUSH, and that this is not a complete program that you could feed into an assembler (even after you stripped off the parentheses). I'll explain all of these points.

Many Lisp systems include an assembler that accepts statements in the form generated by DISASSEMBLE. These statements are often named LAP, for Lisp Assembly Program. With the proper documentation, you can write LAP code and have it invoked by your own functions. But you do need the vendor's documentation for this; you can't just find the LAP assembler and feed it a list of LAP instructions. You need to know how to use reserved registers, what subroutines to call, what stack protocol to follow, and many other low-level details. You also need to associate the code with a function name so you can call it later; this is one of the pieces that is missing from the output of DISASSEMBLE.

Some Lisp systems provide additional information (beyond raw assembler instructions) in their DISASSEMBLE output. In the code above, you'll see that certain reserved registers or memory locations are identified by a distinguishing name, such as NARGS, LOC-PC, ARG_Y, ARG_Z, VSP and RNIL. Sometimes certain instructions (or even short instruction sequences) will be given a mnemonic name that reflects their use by the Lisp compiler; VPUSH is one such mnemonic used by this Lisp system.

Some Lisp systems are better than others at including explanatory comments with the disassembled code. Systems that do include comments typically synthesize comments to explain the code, or save information that allows DISASSEMBLE to intersperse source program fragments within the disassembly listing.

One useful thing you can do with DISASSEMBLE is to see whether declarations have any effect on your compiler. Declarations are forms that provide advice to the compiler. With the one exception of the SPECIAL declaration, which alters the meaning of code that uses it (see Chapter 8) a compiler may or may not use the information that you provide in a declaration. Your Lisp vendor's documentation may provide some guidance as to the effect of declarations, but the best (and most accurate) assessment is made by reading the listing that DISASSEMBLE generates.

The previous disassembly of ADD1 shows that it calls several subroutines: .SPSAVECONTEXTVSP, .SPRESTORECONTEXT, and .SPBUILTIN-PLUS. If that seems like an awful lot of work just to add one to a number, consider that (1) the number can be of any type (including bignum, which is an "infinite" precision integer type), (2) non-numeric arguments are handled gracefully -- you'll get a break into the Lisp debugger rather than a crash or a core dump, and (3) the function probably makes an extra effort to make its presence known to the Lisp debugger.

So, what if we want to play fast and loose, assume that ADD1 will only be called for small integer arguments, and stoically suffer the ungraceful consequences if we screw up and pass the wrong type of data? We can add declarations to express our intent, and then use DISASSEMBLE again to see whether the compiler paid any attention to our wishes.

? (defun int-add1 (n)
    (declare (fixnum n)
             (optimize (speed 3) (safety 0) (debug 0)))
    (the fixnum (1+ n)))
INT-ADD1
? (disassemble 'int-add1)
  (MFLR LOC-PC)
  (STWU SP -16 SP)
  (STW FN 4 SP)
  (STW LOC-PC 8 SP)
  (STW VSP 12 SP)
  (MR FN TEMP2)
  (LWZ IMM0 -117 RNIL)
  (TWLLT SP IMM0)
  (VPUSH ARG_Z)
  (LWZ ARG_Z 0 VSP)
  (ADDI ARG_Z ARG_Z 4)
  (LWZ LOC-PC 8 SP)
  (MTLR LOC-PC)
  (LWZ VSP 12 SP)
  (LWZ FN 4 SP)
  (LA SP 16 SP)
  (BLR)

The DECLARE form in INT-ADD1 includes two kinds of advice. (FIXNUM N) declares that the function parameter N is a small integer. (The range depends upon your Lisp implementation, but you'll typically get 29-bit fixnums on a 32-bit processor; the remaining three bits are often used by the Lisp system to encode type information.) The (OPTIMIZE ... declaration is advice to the compiler that you'd like it to emphasize certain properties of the compiled code. Here, I've said that speed is of ultimate importance, and that I could care less about runtime safety or debuggability. If the compiler pays attention to all of this, I should get code that is optimized for fixnums, runs fast, and falls over if I pass it anything other than a fixnum or cause it to generate a result that isn't a fixnum.

Looking at the generated code, it appears that the compiler has paid attention to my declarations. The compiled code for INT-ADD1 is a bit longer than the code for ADD1, but there are no subroutine calls. Every instruction generated for INT-ADD1 is a simple PowerPC instruction (even the VPUSH instruction, which is just an alias for a single PowerPC instruction). The addition is performed by PowerPC instructions instead of a subroutine. In fact, most of the code in INT-ADD1 has to do with entering and leaving the function.

By the way, some optimization setting is always in effect if you don't use an (OPTIMIZE ... declaration. To find out what are the global optimization settings, do this:

? (declaration-information 'optimize)
((SPEED 1) (SAFETY 1) (COMPILATION-SPEED 1) (SPACE 1) (DEBUG 1))
DECLARATION-INFORMATION may not exist in a pre-ANSI Common Lisp implementation, but there may be an alternative way to access this information. Consult the vendor's documentation. If that fails, see whether APROPOS (see Chapter 10) turns up anything that might be useful.

BREAK and backtrace: How did I end up here?

If you ever need to figure out exactly what's going on at a particular point in your program, you can insert a BREAK form at the point of interest; when your program evaluates the BREAK, the Lisp system will immediately stop your program (without losing any information), and transfer control to the Lisp debugger. Once in the debugger, you can do things like examine the call stack (sometimes named a backtrace, since the stack frames are a trace of your program's current call history, backward in time) and look at local variables at any level in the stack. And, of course, you can execute any Lisp code that you like. But wait, there's more! You can exit the debugger, and your program will continue from where the BREAK interrupted it. Or you can change the values of some variables before you continue. If you want, you can provide a value to be returned by the interrupted function. You can even redefine and restart functions anywhere in the call stack.

The fact that BREAK is just a Lisp form has its advantages. You can wrap it in a conditional expression of arbitrary complexity, so that your program will trigger the break exactly when it's needed; this is especially useful in debugging loops or recursive functions.

If you have more than one BREAK statement in your code, you may find it useful to identify the particular BREAK that invokes the debugger. You can provide a format control string and arguments that BREAK will use to print a message upon entry to the debugger. The control string and arguments are the same as you'd use for FORMAT. (We've seen examples of FORMAT in Chapters 4, 5, and 6. Chapter 24 give a a more complete treatment of FORMAT.)

The downside? Most Lisp IDE's don't give you a point-and-click interface to set BREAKs. (That is a downside, right?)

Lisp defines BREAK, the interface for your program to gain entry into the debugger. Once there, the commands that you'll use to navigate are entirely implementation-specific. If you're lucky, you'll get a window-and-menus interface to at least the most common actions. If, instead of a GUI, the debugger presents you with just get a message and a prompt, you may have to crack open the manual. But before you get so desperate, try to get the debugger to print a help text or menu: one of the commands H, ?, :H, or :HELP may work for your Lisp system.

TRACE and STEP: I'm watching you!

When you need to know exactly how a function is working at a particular point in your code, BREAK and the Lisp debugger are indispensable tools. But they are labor intensive and slow (at least relative to the program's normal execution) -- nothing happens except when you issue commands to the debugger.

Sometimes, it's enough to know that a particular function has been called and returned a value. TRACE gives you this ability. You simply invoke trace with one or more function names, and the Lisp environment arranges to print the name of the function and its arguments upon entry, and the name of the function and its values upon exit. All this happens without changing the source code for the function.

? (defun factorial (n)
    (if (plusp n)
      (* n (factorial (1- n)))
      1))
FACTORIAL
? (factorial 6)
720
? (trace factorial)
NIL
? (factorial 6)
 Calling (FACTORIAL 6) 
  Calling (FACTORIAL 5) 
   Calling (FACTORIAL 4) 
    Calling (FACTORIAL 3) 
     Calling (FACTORIAL 2) 
      Calling (FACTORIAL 1) 
       Calling (FACTORIAL 0) 
       FACTORIAL returned 1
      FACTORIAL returned 1
     FACTORIAL returned 2
    FACTORIAL returned 6
   FACTORIAL returned 24
  FACTORIAL returned 120
 FACTORIAL returned 720
720
Some Lisp systems may print only the first and last lines of this trace, because of compiler optimizations. If you want to see recursive calls, it may help to evaluate (DECLAIM (OPTIMIZE (DEBUG 3))) before defining any functions to be traced.

Notice how indentation is used to represent call stack depth. This, and other details of the TRACE presentation, are implementation dependent.

When you no longer want to trace a function, evaluate UNTRACE, passing the function name (or names). UNTRACE without any arguments will stop tracing of all currently traced functions.

Sometimes, despite your best efforts, you're just not sure what parts of a function are being executed. If you're this confused, and you'd rather forge ahead than try to simplify the function, Lisp gives you the STEP form. STEP takes a complete Lisp form as an argument; it evaluates the form and returns what the form returns. Along the way, though, it lets you see all of the evaluations that happen -- step by step, as it were. Like BREAK, STEP only has a standard program interface; the user interface is implementation dependent.

The quality of information available through STEP varies widely among implementations. The most common shortcoming is that you see some transformed version of the program source, rather than the original source code. Generally, you'll be able to spot enough clues (variable names, functions, etc.) so that you can keep your bearings as you execute the stepped code one form at a time.

Footnotes:

[1] :grok: /grok/, var. /grohk/ /vt./ [from the novel "Stranger in a Strange Land", by Robert A. Heinlein, where it is a Martian word meaning literally `to drink' and metaphorically `to be one with'] The emphatic form is `grok in fullness'. 1. To understand, usually in a global sense. Connotes intimate and exhaustive knowledge. Contrast {zen}, which is similar supernal understanding experienced as a single brief flash. 2. Used of programs, may connote merely sufficient understanding.


Contents | Cover
Chapter 15 | Chapter 17
Copyright © 1995-1999, David B. Lamkins
All Rights Reserved Worldwide

This book may not be reproduced without the written consent of its author. Online distribution is restricted to the author's site.