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

utilities/:

- 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

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