Now that we have basic descriptions of each location, we need descriptions of paths to other locations as well. We’ll create a second variable, *edges*, that contains the paths that players can take to move between places on our map. (We use the term edges because that’s the proper math term for the lines connecting nodes in a graph.)
(defparameter *edges* '((living-room (garden west door)
(attic upstairs ladder))
(garden (living-room east door))
(attic (living-room downstairs ladder))))Using this structure, we create the describe-path function, which builds a textual description of a given edge using our symbols system.
(defun describe-path (edge) `(there is a ,(caddr edge) going ,(cadr edge) from here.))
This describe-path function looks pretty strange—almost like a piece of data more than a function. Let’s try it, and then figure out how it works.
> (describe-path '(garden west door))
(THERE IS A DOOR GOING WEST FROM HERE.)This function basically returns a piece of data with small bits of calculated information inserted into it. This feature of Lisp, called quasiquoting, allows us to create chunks of data that have small pieces of Lisp code embedded in them.
To enable quasiquoting, you must use a backquote [`] not a single quote ['] when switching from code to data mode. The describe-path function has just such a backquote in it.
Both the single quote and backquote in Lisp “flip” a piece of code into data mode, but only a backquote can also be unquoted using the comma character, to flip back into code mode.
With a little imagination, this should make sense to you. After all, a comma does look just like an upside-down backquote, doesn’t it? Here’s how the flip-flop in the describe-path function works (the parts in code mode are shaded):
Lisp attempts to make list manipulation as easy as possible. Here, you can see how our program, which uses lists of symbols to store our text, can now leverage the quasiquoting feature to construct sentences in a very concise and clear way.
Now let’s use our describe-path function to create a more advanced function. Since a location may have any number of paths exiting from it, we need a function that can generate descriptions for all edges from a given location by looking up the location from our data structure of edges:
(defun describe-paths (location edges) (apply #'append (mapcar #'describe-path (cdr (assoc location edges)))))
This function uses a bunch of commands that may seem very exotic to a person not accustomed to the world of Lisp. Many programming languages would use some kind of for-next loop to run through the edges, and then cram the descriptions of each path together using a temporary variable. Lisp uses a much more elegant approach. Let’s see it in action:
> (describe-paths 'living-room *edges*)
(THERE IS A DOOR GOING WEST FROM HERE. THERE IS A LADDER GOING UPSTAIRS FROM HERE.)The describe-paths function takes the following steps:
Find the relevant edges.
Convert the edges to descriptions.
Join the descriptions.
Let’s see how it performs each of these steps.
The first, inner part of the describe-paths function is pretty straightforward. To find the relevant paths and edges leading from the living room, we use assoc again to look up the location in our list of edges:
> (cdr (assoc 'living-room *edges*))
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))Next, the edges are converted to descriptions. Here is just the code to accomplish this, shown in isolation:
> (mapcar #'describe-path '((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER)))
((THERE IS A DOOR GOING WEST FROM HERE.)
(THERE IS A LADDER GOING UPSTAIRS FROM HERE.))The mapcar function is used frequently by Lispers. This function takes another function and a list, and then applies this function to every member of a list. Here’s an example:
> (mapcar #'sqrt '(1 2 3 4 5))
(1 1.4142135 1.7320508 2 2.236068)This example passes the sqrt (square root) function, along with the (1 2 3 4 5) list, into mapcar. As a result, the function generates a list of the square roots of the original numbers by applying sqrt to every member of the list and creating a new list.
Functions that take other functions as parameters, such as mapcar, are very useful and a distinguishing feature of Lisp. Such functions are called higher-order functions.
Here is another example:
> (mapcar #'car '((foo bar) (baz qux)))
(foo baz)This time, our source list contains two smaller lists. The car function, which grabs the first item in a list, causes mapcar to return the first items from each smaller list, foo and baz.
You may be wondering why the function names we pass into mapcar have the #' symbols in front of them. This symbol sequence is a shorthand for the function operator. The Lisp reader (the part of your Lisp environment that reads the code you type) will convert the previous example into the following longer version:
> (mapcar (function car) '((foo bar) (baz qux)))
(foo baz)Common Lisp requires you to use the function operator when referring to a function as a value directly like this, because the name of a function may conflict with other named items in a program, causing unpredictable errors. For instance, imagine if we added more stuff to the previous example, like this:
>
(let ((car "Honda Civic"))
(mapcar #'car '((foo bar) (baz qux))))(foo baz)
In this version, the car symbol could have two different meanings. The first meaning of car is that it is a standard function built into Lisp (introduced in Chapter 3). However, we’re also creating a local variable named car . Because we prepended the word car with #' in our call to mapcar , there is no confusion about which car we are talking about.
Now let’s look at the describe-paths function again:
(defun describe-paths (location edges) (apply #'append (mapcar #'describe-path (cdr (assoc location edges)))))
Notice how the append and describe-path functions are passed in as values to the apply and mapcar functions, which are designed to receive and use the functions.
Common Lisp tracks function names differently from variable names. It has multiple namespaces, including one for variables and one for functions. (We’ll learn more about namespaces later, especially in Chapter 16.) Scheme, the other popular Lisp dialect, doesn’t force you to mark functions with a function operator when using them as values.
In other words, Scheme has only one namespace for both functions and variables. For instance, in Scheme, you can just write (map sqrt '(1 2 3 4 5)) to generate the square roots of the numbers 1 through 5 without generating an error (map is the Scheme version of mapcar). As a result of this design, in Scheme, a variable and a separate function can’t be available in the same block of code. That design decision is one of the great benefits (or curses) of Scheme, depending on your point of view. Because of this difference in the number of namespaces, Scheme is sometimes called a Lisp-1, whereas Common Lisp is sometimes referred to as a Lisp-2.
Once we’ve used mapcar to generate a list of descriptions for all the paths and edges, we need to combine them into a single description. We accomplish this with the append function, which joins several lists into one big list:
> (append '(mary had) '(a) '(little lamb))
(MARY HAD A LITTLE LAMB)We use the append function to cram the list of path descriptions into one list that describes the whole enchilada, in one swoop. The problem is that append needs all of the lists handed to it as separate parameters. In describe-paths, we have our lists in one big list, not as separate objects we can pass as parameters. Heck, we don’t even know how many paths there may be from any given spot.
The apply function solves this problem. You pass it a function and a list of objects, and it pretends that the items in the list are separate objects and passes them to the given function as such. For example, if we have the nested list '((mary had) (a) (little lamb)), the apply function will add in that little bit of duct tape needed to make the append function work with a single big list:
> (apply #'append '((mary had) (a) (little lamb)))
(MARY HAD A LITTLE LAMB)Warning
Since the apply function passes each item in a list as an argument to the target function, you can run into problems when calling it on very large lists that have thousands of items or more. You can check the value of the call-arguments-limit variable in the REPL to see the maximum number of allowed arguments to a function. (More recent dialects of Lisp are typically designed to allow argument lists of any size, without an artificial limit.)
You can see how apply enables the describe-paths function to build one long list describing all paths leading from a single location. Let’s use this same approach on the path description lists we constructed:
>(apply #'append '((THERE IS A DOOR GOING WEST FROM HERE.)(THERE IS A LADDER GOING UPSTAIRS FROM HERE.)))(THERE IS A DOOR GOING WEST FROM HERE. THERE IS A LADDER GOING UPSTAIRS FROM HERE.)
Now that we’ve looked at each part of the describe-paths function, let’s review how it works:
(defun describe-paths (location edges) (apply #'append (mapcar #'describe-path (cdr (assoc location edges)))))
The function takes two parameters: the current player’s location, as well as an alist of edges/paths for the game map. First, it uses assoc to look up the correct location from the edge alist. Since assoc returns both the key and the value from the alist, we call cdr to retrieve only the value. Next, we use mapcar to map the describe-path function against each edge that we found. Finally, we concatenate the lists for describing all the paths into one long list by applying append against the list.
The programming style used by describe-path is very typical for Lisp code. It involves passing along a complicated chunk of data and manipulating it in several steps, often using higher-order functions. To become a proficient Lisp programmer, you should try to get comfortable reading code written in this way.