**utilities.lisp**Basic utility functions and macros, used throughout the code.**binary-tree.lisp**The following definitions implement binary search trees.**queue.lisp**The Queue datatype**cltl2.lisp**Compatibility package for 'Common Lisp the Language: 2nd edition'**test-utilities.lisp**Test cases for the basic utilities

**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.

**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.

**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?

**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

**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.

**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.

**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*** *variable*

**dprint** *function* (&rest
args)

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

**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?

**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

**q** *type* (key
last
elements)

**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.

**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.

**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.

**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.

**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.

AIMA Home | Authors | Lisp Code | AI Programming | Instructors Pages |