Center for Analysis and Design of Intelligent Agents

Lab 1: Introduction to Lisp

Material:
- The history of Lisp written by its author John McCarthy (interesting read)
- Lisp Tutorial: Part I, Part II and Part III.
- Lisp cheat sheet: (PS Format) or (PDF Format).
More material for learning Lisp:
- Another Tutorial: Lisp Primer.
- A freely available book on Lisp: Practical Common Lisp.
IDE and Lisp Implementations:
- Lispbox 0.7 (Stable Release), an Emacs + SLIME + Common Lisp easy to install package (Win32) or (MAC OS X).
  - Lispbox (Latest Unstable Beta Version): (Linux 32-bit, Linux 64-bit), (Win32) or (MAC OS X).
- Eclipse Lisp Plugin (Win32, MAC OS X and Linux): Dandelion.
- Emacs reference card: (PDF Format).

To work through these exercises, refer to the above material for more information.

Emacs and REPL:
Install LispBox on your computer and start it up. The lower window is the Lisp REPL (read-eval-print loop) where you can enter Lisp expressions and have them evaluated.
Hello World:
Type an expression that prints “Hello World!” on the screen.
```
;; HINT: A typical print expression
(print "Here is some text")
```
Note that in the REPL, you can recall your last command with Alt+P (P stands for previous) and that tab completion works on most lisp symbols.
Lisp basics:
Go through the sections Evaluating simple expressions, Evaluating Lists as Functions and Control Structures and Variables in Lisp Tutorial (Part I). Some expressions will generate an error, in that case the top window will show a message and a list of options. The safe option is always [ABORT REQUEST].
Defining functions:
Go through the section Writing Functions in the tutorial. Make sure to try into REPL the examples in boxes 1 and 2, you can skip typing the examples in the remaining boxes 3, 5, 6, 7, 8 and 9 - but read and try to understand them. Write a function called sum-numbers taking in input two numbers and returning the sum.
```
;; HINT: Declaring and calling a function taking one parameter and printing it
(defun my-func (param1)
    (print param1))
(my-func "hello")
```
Note that in the REPL, you will see the printed output as well as the return value of the function. The return value is (as you should know by now) the result of the last expression of the function body. Since the PRINT function returns its argument, the function above also returns it, which is why it is printed twice in the REPL.
Lists as data:
So far we've only seen lists used to call functions. However they can also be used to store data. Go through the section Lists and Symbols as Data in the tutorial. Feel free to skip the exercises that you feel you understand well, but make sure you understand how quoting (e.g. '(1 2 3)) works.
The tutorial does not talk about keyword lists, which we will use later.
```
;; HINT: Lists as data are created using the following syntax (quote (item1 item2 item3 item4 ...))
(quote (1 2 3))
;; or using the abbreviation
'(1 2 3)
;; Keyword lists are created with the following syntax '(:keyword1 numberfield1 :keyword2 numberfield2 :keyword3 numberfield3 ...)
'(:a 1 :b 2 :c 3)
```
You can access the fields of a keyword list with the GETF function:
```
CL-USER> (getf '(:a 1 :b 2 :c 3) :b)
2
```
You can read more about keyword lists in chapter 2 of Practical Common Lisp. For more information about quoting, see this page of the Lisp Primer, and remember that quoting simply prevents a list from being evaluated and instead treats it as data.
Symbols as data:
Lisp allows us to use symbols (e.g. variable names) as data. They are created with the same quoting syntax as lists:
```
'symbol
```
Symbols are simply short strings, except they are case-insensitive (the REPL always prints them in uppercase) and cannot be changed or manipulated. Like with lists, quoting a symbol simply stops it from being evaluated (i.e. treated as a variable) and instead treats the symbol itself as data.
Write a function called lookup-test that takes a keyword list of numbers, looks up the number with key :test and returns the symbol YES if it is less than 10, and NO otherwise.
```
;; HINT: declaration and use of a keyword list
CL-USER> (setf my-list '(:x 10 :y 33 :z 9))
(:X 10 :Y 33 :Z 9)
CL-USER> (getf my-list :y)
33
```
```
;; HINT: using the conditional statement and returning a Symbol
CL-USER> (if (< a b)
	     'SMALLER
	     'BIGGER)
```
Loading files:
Typing things into the REPL every time is of course not the way we usually use Lisp. Instead we load a file with definitions of functions and variables, and then use the REPL to invoke them.
1. Start by downloading the file agents.zip, unzip it and save the file agents.lisp in a folder for this lab session.
2. In the REPL window type the following command: , (comma); this invokes the command mode of the REPL. You should have now the focus on the lower window with the prompt changed into Command: .
3. Type the command cd and press ENTER. Emacs will prompt you for a file path, enter the file path to the folder where you saved the file (you can use TAB for useful auto-completion).
4. Now type (back in the REPL window) the expression (load “agents.lisp”).
5. At this point the definitions inside the file have been loaded in the REPL. To see what definitions are available, open the file in the upper half of Emacs. To do this, you can click in the upper half and then press (in sequence) Ctrl+X and Ctrl+F and type the path to the file. Alternatively just select “File → Open” If Emacs asks you to allow it to apply local variables from the file, then answer with Yes.
  - Note: if you are not familiar with emacs you can open and modify the file using a different (but advanced ) editor, for example Notepad++ on Windows or Kate on GNU/Linux). Then you can easily load the file as shown in steps I-IV.
6. In the given file there is an implementation of A simple reflex agent in the two-state vacuum environment. Have a look at it and see if you can understand the code. Don't worry too much if you don't. At the bottom of the file there are three example expressions. Try typing them (in the same order) in the REPL and see what happens.

Writing an agent program:
The function EXAMPLE-AGENT-PROGRAM gives an example of how to create a program to control an agent in the vacuum-cleaner world assuming a 2×1 environment as shown in the figure:

The given example program is an implementation of the code in figure 2.8 on page 48 in the textbook. The program is a function that takes a keyword list representing the percept value, and it should return one of the symbols LEFT, RIGHT or SUCK. A percept keyword list looks like this:

'(:x 0 :y 0 :dirty T)

Here, :x and :y are the location of the agent and :dirty tells us if the current square has dirt or not.

Write a new agent program called random-agent-program, that has two options: Walk around the environment randomly or remain idle when it finds a clean square; Suck up dirt when it finds it.
Your agent program should return one of the symbols LEFT, RIGHT, UP, DOWN, SUCK or IDLE. You can either write your function directly in the REPL or add it to the file. If you add it to the file, you have to save the file (keyboard shortcut is Ctrl+X, Ctrl+S in emacs) and then reload the file in the REPL (recommended option).

;; HINT: Getting a random value.
;; This function returns a random nonnegative number less than number, and of the same type (either integer or floating-point)
(random number)

;; HINT: cond is a powerful generalization of case. It takes the form:
(cond (test1 expr expr ... )
      (test2 expr expr ... )
      (test3 expr expr ... )
      ... )
;; cond works like this. First, test1 is evaluated. If this is true, the following expressions are evaluated and the last one is returned.
;; If not, then test2 is evaluated. If this is true, its following expressions are evaluated and the last one is true. And so on.
;; If no test evaluates to true, then nil is returned.

;; HINT: you don't have to worry about the action (UP, DOWN, ...) and environment boundaries,
;; (i.e. giving as input a 10x20 environment and having the agent at [0,0] performing the UP action)
;; since the update-env function already takes care of this when receiving boundaries coordinates.

;; HINT: Remember to initialize the environment first!
;; Init example where 10 and 20 are the width and height, respectively, and .5 is the probability
;; of a square containing dirt
(init-env 10 20 .5)

Use the SIMULATE and SIMULATE-QUIET functions from the last step to test your new agent program. Remember to Does it give better performance evaluation than the old one?

Writing a performance evaluation function:
The function EXAMPLE-MEASURE shows how simple performance evaluation functions look. This function takes an environment and an agent as parameters, and returns a number indicating the performance of the agent so far.
Both the agent and the environment are so called structures. Their fields are defined in the file agents.lisp with calls to the DEFSTRUCT macro. This macro defines a function for constructing an instance of the structure, e.g. for the ENV structure, this function is called MAKE-ENV.
The macro also defines functions for accessing the fields of a structure, e.g. the width field of an ENV structure in the variable env can be accessed using (env-width env).
Write a performance evaluation function called random-agent-measure that awards 10 points for every clean square but deducts one point for every move the agent makes. The number of moves is stored in the moves-so-far field. Now run the simulations again.
```
;; HINT: counting the number of times an object appears in a sequence: (count object sequence keywords...)
;; For example, we can count the number of times the character 'l' appears in the Sequence "Hello World"
(count #\l "hello world")
```
```
;; The count function also has count-if and count-if-not variants.
;; (count-if test-predicate sequence keywords...) counts the number of times in which test-predicate (a function pointer) returns true 
;; for the elements in the sequence. 
;; Counting the number of clean squares (in agents.lisp)
;; Note: the not function has the following syntax (not x) and returns T if x is NIL, otherwise returns NIL
(count-if #'not (env-dirt-vector env)))
```
How does this change the evaluation score? Can you think of ways to change the agent program so that it scores better with this new evaluation function?