Utilities (Subsystem of AIMA Code)

The utilities system provides a set of basic functions, macros, and data types that are used throughout the other systems. For example, we define the while and for iteration macros, the two-dimensional point (and operations on it), the queue and binary tree types, and some debugging and testing code.


File utilities/utilities.lisp

Basic utility functions and macros, used throughout the code.

The utilities are divided into control flow macros, list utilities, functions for 2-dimensional points, numeric utilities, some trivial functions, utilities for strings, symbols and printing, a debugging tool, and a testing tool."

Control Flow Macros

We define iteration macros to match the book's pseudo-code. This could all be done with LOOP, but some users don't have the LOOP from the 2nd edition of 'Common Lisp: the Language'.

while macro (test do &body body)

Execute body while the test is true.

for-each macro (var in list do &body body)

Execute body for each element of list. VAR can be a list or tree of variables, in which case the elements are destructured.

for macro (var = start to end do &body body)

Execute body with var bound to succesive integers.

deletef macro (item sequence &rest keys &environment env)

Destructively delete item from sequence, which must be SETF-able.

define-if-undefined macro (&rest definitions)

Use this to conditionally define functions, variables, or macros that may or may not be pre-defined in this Lisp. This can be used to provide CLtL2 compatibility for older Lisps.

List Utilities

length>1 function (list)

Is this a list of 2 or more elements?

length=1 function (list)

Is this a list of exactly one element?

random-element function (list)

Return some element of the list, chosen at random.

mappend function (fn &rest lists)

Apply fn to respective elements of list(s), and append results.

starts-with function (list element)

Is this a list that starts with the given element?

last1 function (list)

Return the last element of a list.

left-rotate function (list)

Move the first element to the end of the list.

right-rotate function (list)

Move the last element to the front of the list.

transpose function (list-of-lists)

Transpose a matrix represented as a list of lists. Example: (transpose '((a b c) (d e f))) => ((a d) (b e) (c f)).

reuse-cons function (x y x-y)

Return (cons x y), or reuse x-y if it is equal to (cons x y)

make-exp function (op &rest args)

op function (exp)

Operator of an expression

args function (exp)

Arguments of an expression

arg1 function (exp)

First argument

arg2 function (exp)

Second argument

prefix->infix function (exp)

Convert a fully parenthesized prefix expression into infix notation.

insert-between function (item list)

Insert item between every element of list.

Functions for manipulating 2-dimensional points

xy type (x y)

A two-dimensional (i.e. x and y) point.

xy-p function (arg)

Is the argument a 2-D point?

@ function (x y)

Create a 2-D point

xy-equal function (p q)

xy-add function (p q)

Add two points, component-wise.

xy-distance function (p q)

The distance between two points.

x+y-distance function (p q)

The 'city block distance' between two points.

xy-between function (xy1 xy2 xy3)

Predicate; return t iff xy1 is between xy2 and xy3. Points are collinear.

rotate function (o a b c d)

inside function (l xmax ymax)

Is the point l inside a rectangle from 0,0 to xmax,ymax?

Numeric Utilities

infinity constant

minus-infinity constant

average function (numbers)

Numerical average (mean) of a list of numbers.

running-average function (avg new n)

Calculate new average given previous average over n data points

square function (x)

sum function (numbers &optional key)

Add up all the numbers; if KEY is given, apply it to each number first.

between function (x y z)

Predicate; return t iff number x is between numbers y and z.

rms-error function (predicted target)

Compute root mean square error between predicted list and target list

ms-error function (predicted target)

Compute mean square error between predicted list and target list

boolean-error function (predicted target)

dot-product function (l1 l2)

iota function (n &optional start-at)

Return a list of n consecutive integers, by default starting at 0.

random-integer function (from to)

Return an integer chosen at random from the given interval.

normal function (x mu sigma)

sample-with-replacement function (n population)

sample-without-replacement function (n population &optional m)

fuzz function (quantity &optional proportion round-off)

Add and also subtract a random fuzz-factor to a quantity.

round-off function (number precision)

Round off the number to specified precision. E.g. (round-off 1.23 .1) = 1.2

Trivial Functions

nothing function (&rest args)

Don't do anything, and return nil.

declare-ignore function (&rest args)

Ignore the arguments.

true function (&rest args)

Always return true.

false function (&rest args)

Always return false.

required function (&optional msg &rest args)

If this ever gets called, it means something that was required was not supplied. Use as default value for &key args or defstruct slots.

Utilities for strings and symbols and printing

stringify function (exp)

Coerce argument to a string.

concat-symbol function (&rest args)

Concatenate the args into one string, and turn that into a symbol.

print-grid function (array &key stream key width)

Print the contents of a 2-D array, numbering the edges.

print-centered function (string width &optional stream)

Print STRING centered in a field WIDTH wide.

print-repeated function (string n &optional stream)

Print the string n times.

print-dashes function (width &optional stream separate-line)

Print a line of dashes WIDTH wide.

Assorted conversion utilities and predicates

copy-array function (a)

Make a copy of an array.

copy-subarray function (a b indices dim)

array->vector function (array)

Convert a multi-dimensional array to a vector with the same elements.

plot-alist function (alist file)

copy-hash-table function (h1 &optional copy-fn)

hash-table->list function (table)

Convert a hash table into a list of (key . val) pairs.

hprint function (h &optional stream)

prints a hash table line by line

compose function (f g)

Return a function h such that (h x) = (f (g x)).

the-biggest function (fn l)

the-biggest-random-tie function (fn l)

the-biggest-that function (fn p l)

the-smallest function (fn l)

the-smallest-random-tie function (fn l)

the-smallest-that function (fn p l)

Debugging tool

*debugging* variable

dprint function (&rest args)

Echo all the args when *debugging* is true. Return the first one.

Testing Tool: deftest and test

deftest macro (name &rest examples)

Define a set of test examples. Each example is of the form (exp test) or (exp). Evaluate exp and see if the result passes the test. Within the test, the result is bound to *. The example ((f 2))) has no test to fail, so it alweays passes the test. But ((+ 2 2) (= * 3)) has the test (= * 3), which fails because * will be bound to the result 4, so the test fails. Call (TEST name) to count how many tests are failed within the named test. NAME is the name of an aima-system.

add-test function (name examples)

The functional interface for deftest: adds test examples to a system.

test function (&optional name print?)

Run a test suite and sum the number of errors. If all is well, this should return 0. The second argument says what to print: nil for nothing, t for everything, or FAIL for just those examples that fail. If there are no test examples in the named system, put the system has other systems as parts, run the tests for all those and sum the result.

test-example function (example &optional print?)

Does the EXP part of this example pass the TEST?

File utilities/binary-tree.lisp

The following definitions implement binary search trees.

They are not balanced as yet. Currently, they all order their elements by #'<, and test for identity of elements by #'eq.

search-tree-node type (value num-elements key parent leftson rightson)

node for binary search tree

make-search-tree function (root-elem root-key)

return dummy header for binary search tree, with initial element root-elem whose key is root-key.

create-sorted-tree function (list-of-elems key-fun)

return binary search tree containing list-of-elems ordered according tp key-fun

empty-tree function (root)

Predicate of search trees; return t iff empty.

leftmost function (tree-node)

return leftmost descendant of tree-node

rightmost function (header)

return rightmost descendant of header

pop-least-element function (header)

return least element of binary search tree; delete from tree as side-effect

pop-largest-element function (header)

return largest element of binary search tree; delete from tree as side-effect

least-key function (header)

return least key of binary search tree; no side effects

largest-key function (header)

return least key of binary search tree; no side effects

insert-element function (element parent key &optional direction)

insert new element at proper place in binary search tree

randomized-insert-element function (element parent key &optional direction)

insert new element at proper place in binary search tree -- break ties randomly

randomized-push function (element list)

return list with element destructively inserted at random into list

find-element function (element parent key &optional direction)

return t if element is int tree

delete-element function (element parent key &optional error-p)

delete element from binary search tree

inorder-successor function (tree-node)

return inorder-successor of tree-node assuming it has a right son

list-elements function (parent)

return list of elements in tree

File utilities/queue.lisp

The Queue datatype

We can remove elements form the front of a queue. We can add elements in three ways: to the front, to the back, or ordered by some numeric score. This is done with the following enqueing functions, which make use of the following implementations of the elements: ENQUEUE-AT-FRONT - elements are a list ENQUEUE-AT-END - elements are a list, with a pointer to end ENQUEUE-BY-PRIORITY - elements are a heap, implemented as an array The best element in the queue is always in position 0. The heap implementation is taken from "Introduction to Algorithms" by Cormen, Lieserson & Rivest [CL&R], Chapter 7. We could certainly speed up the constant factors of this implementation. It is meant to be clear and simple and O(log n), but not super efficient. Consider a Fibonacci heap [Page 420 CL&R] if you really have large queues to deal with.

q type (key last elements)

Basic Operations on Queues

make-empty-queue function ()

empty-queue? function (q)

Are there no elements in the queue?

queue-front function (q)

Return the element at the front of the queue.

remove-front function (q)

Remove the element from the front of the queue and return it.

The Three Enqueing Functions

enqueue-at-front function (q items)

Add a list of items to the front of the queue.

enqueue-at-end function (q items)

Add a list of items to the end of the queue.

enqueue-by-priority function (q items key)

Insert the items by priority according to the key function.

The Heap Implementation of Priority Queues

The idea is to store a heap in an array so that the heap property is maintained for all elements: heap[Parent(i)] <= heap[i]. Note that we start at index 0, not 1, and that we put the lowest value at the top of the heap, not the highest value.

heap-val function (heap i key)

heap-parent function (i)

heap-left function (i)

heap-right function (i)

heapify function (heap i key)

Assume that the children of i are heaps, but that heap[i] may be larger than its children. If it is, move heap[i] down where it belongs. [Page 143 CL&R].

heap-extract-min function (heap key)

Pop the best (lowest valued) item off the heap. [Page 150 CL&R].

heap-insert function (heap item key)

Put an item into a heap. [Page 150 CL&R].

make-heap function (&optional size)

heap-sort function (numbers &key key)

Return a sorted list, with elements that are < according to key first.

File utilities/cltl2.lisp

Compatibility package for 'Common Lisp the Language: 2nd edition'

Functions and macros in CLtL2 that are not in the first edition of the book, and thus not in some old implementations of Common Lisp.

with-simple-restart macro (restart &rest body)

Like PROGN, except provides control over restarts if there is an error.

destructuring-bind macro (lambda-list list &body body)

Bind the variables in lambda-list to the result list and execute body.

Mini Implementation of CLOS

If you don't have CLOS (the Common Lisp Object System) installed, then this defines a simple version of DEFMETHOD which only dispatches on the first argument, and works for structures (and some other types) but not classes. Note that you can still do (single) inheritance with structures using the :include option. To properly inform DEFMETHOD of the inheritance tree, you should use DEFSTRUCTURE rather than DEFSTRUCT. This has the added benefit of allowing you to write PRINT-STRUCTURE methods rather than :print-function functions, if you like (they will be inherited properly, and they don't have the silly DEPTH argument).

defstructure macro (type-and-args &rest slots)

This is just like DEFSTRUCT, except it keeps track of :include types, for the benefit of METHOD-FOR, and it makes printing go through PRINT-STRUCTURE.

print-structure method ((structure t) stream)

Print a structure. You can specialize this function. It will be called to print anything defined with DEFSTRUCTURE.

defmethod macro (name ((var class) &rest other-args) &rest body)

This version of DEFMETHOD is like the CLOS version, except it only dispatches on the first argument, and it only handles structures and some built-in types, not classes.

ensure-generic-function function (name)

Define NAME to be a generic function.

supertype function (type)

Find the most specific supertype of this type.

call-method-for function (name type var args)

Find the method for this type, following :supertype links if needed.

File utilities/test-utilities.lisp

Test cases for the basic utilities

AIMA Home Authors Lisp Code AI Programming Instructors Pages