Programs that Write Programs

Laboratory Exercise 5

810:161

Artificial Intelligence Laboratory

Goals for the Laboratory Exercise

The goal of this lab is to expose you to give some experience with Common Lisp macros, which are programs that generate other programs based on syntactic translation.

Background

Students often ask me why Common Lisp is the lingua franca of AI programming. One reason is its emphasis on and support for symbolic programming. While Lisp provides plenty of support for traditional numeric programming (indeed, its support for vectors and large numbers make it ideal for doing scientific programming), it distinguishes itself from most other languages in its support for symbols and lists. AI programs have to reason about goals and plans and states and assertions and ... -- all being concepts, not numeric structures. So AI programmers need a language that helps them write programs that manipulate symbols.

A second and more seductive reason for Lisp's role in AI programming is its treating of data and programs as equivalent. Lisp programs are just lists of symbols that can be treated as data; data values can be passed around and, if they correspond to programs, evaluated as code. Few languages support the blurring of the line between data and program to the degree that Lisp does.

Because programs are data, programs can generate programs as their output. Such higher-level functions make it possible for a program to customize itself in response to its environment, making the program more flexible and thus more able to exhibit the features of an intelligent agent. And a program can learn new functionality and implement it in new programs of its own creation.

Common Lisp supports another form of "program-writing program" called the macro. A macro takes arguments as input that allow it to generate a function as its output. Macros generally work at the level of translating syntax. If I don't like the form of Lisp's if primitive, then I can use a macro to create my own if form. If I find myself doing the same set of actions together all the time, and I can't implement a function to do them for me, then I can probably use a macro to create a function that does them for me. If I want to write an AI program in terms of a higher-level language, say, one that includes primitives for search and planning, then I can use macros to define a whole new language within Common Lisp.

Try doing that in your other favorite programming language. :-)

Pre-Lab Activities

Prior to doing the in-lab activity, be sure that you have done the following:

1. Read Chapters 10 in Graham. Pay close attention to his examples.

2. Read this document in its entirety.

Deliverables

Submit by 4:00 PM on Monday an e-mail message that contains an answer to Exercise 10-1 on Page 174 of Graham.

In-Lab Activities

1. Common Lisp provides an unless primitive that works like an "if not ...". (See Page 85 of Graham.) Write a special-purpose version of unless named unless-positive that returns the value of its body unless its "test" value is negative. For example:

        * (unless-positive -1 (car '(a b c)))
        A
        * (unless-positive 42 (car '(a b c)))
        NIL
   

2. If we do a lot of work with property lists, we may become tired of quoting all of the symbols we use as targets and properties. We may also tire of the lack of parallelism between retrieving (a simple get) and setting (a setf to a get form) properties. To remove these difficulties, write two macros:
   • (getq sym prop) translates to (get 'sym 'prop)
   • (putq sym prop val) translates to (setf (get 'sym 'prop) val)

   For example:

        * (putq foo color 'red)
        RED
        * (putq foo age 32)
        32
        * (getq foo color)
        RED
        * (getq foo age)
        32
   

3. I like the built-in macro with-open-file, but I get tired of sending the :direction argument. Write for me a macro named with-input-file that saves me the trouble. This macro should generate an equivalent with-open-file expression with the :direction set to :input. For example, with your macro I will be able to change Graham's pseudo-cat function (Page 122) to:

        (defun pseudo-cat (file)
           (with-input-file (str file)
              (do ((line (read-line str nil 'eof) (read-line str nil 'eof)))
                  ((eql line 'eof))
                  (format t "~A~%" line))
           ))
   

   The change is marked in italics. Your macro should translate the with-input-file expression into the with-open-file expression Graham used in his function.

4. Some of the C programmers in our midst are big fans of the pre- and post-increment operators, ++i and i++. Write two macros named ++setf and setf++ that behave as follows:
   • (++setf x y) is equal to x = ++y; in C
   • (setf++ x y) is equal to x = y++; in C

   For example:

        * (setf x 10 y 20)
        20
        * (setf++ x y)
        21
        * (list x y)
        (20 21)
   
        * (setf x 10 y 20)
        20
        * (++setf x y)
        21
        * (list x y)
        (21 21)
   

5. Many of you have commented on the fact that Common Lisp's if expression doesn't allow you to say then and else, and that the resulting expressions are hard to read, even with good indentation. Now you know enough to change that. Write a macro named iff that translates expressions of the form

   (iff <exp> then <exp>⁺ [else <exp>⁺])

   into an equivalent if or cond. <exp>⁺ means one or more expressions, and the [] around the else mean that it is optional. Be sure that iff returns nil in the case that the expression has no else part and the test expression fails.

Deliverables

Submit an e-mail message (whose Subject: line includes [161]) containing only a single, gcl-loadable file that contains your solutions to the above exercises by Wednesday at 4:00 PM. If you forget what "gcl-loadable" means, please review the instructions in Laboratory Exercise 2.

By that same time, submit a print-out of the same file, to me in person or to the department office.

If you have comments or questions that you would like to send accompanying your submission, please send a separate message.

Post-Lab Exercise

None this week. Enjoy the break!

Further Information

Macros are cool. They allow you to define new constructs and whole new languages within Lisp--that behave just like the rest of Lisp! Graham does a good job covering macros, but you can do even more with them. If you are interested in learning more, take a look at Chapter 8 of (Common Lisp: The Language) and other sections of the book that "macros" index entry points you to.

One useful tool that you did not explore in this lab is the idea of a macro character, which instructs the Lisp reader to treat an input in a special way. Quote and backquote are macro characters. Like full macros, macro characters can make difficult tasks much easier...