Copyright © 2003, 2004, 2007 Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.
CyberTiggyr Tigris is a library of miscellaneous functions for Lisp. Many of the functions were inspired (or directly copied) from books & articles about Lisp.
The source code for CyberTiggyr Tigris is licensed according to the terms of the Gnu Public License (GPL) [1].
The documentation (the document you are reading now) is copyrighted by Gene Michael Stover. The official copyright notice is at the beginning of the document. It is not licensed according to the GPL.
Added MAKE-GUID.
The source code is in tigris.lisp. Save it to a file on your local system, then LOAD it into Lisp.
Unit tests are in test.lisp. Again: Save, then LOAD.
package
cybertiggyr-tigris
The package containing & exporting all of the symbols documented in this chapter.
To use CyberTiggyr Tigris, first load it:
1> (load "tigris.lisp") ;; Loading file tigris.lisp ... ;; Loading of file tigris.lisp is finished. T
Then import all the symbols from package cybertiggyr-tigris, like this:
2> (use-package 'cybertiggyr-tigris) T
or import only specific symbols, like this:
4> (import 'cybertiggyr-tigris:array-equal) T 5> (import 'cybertiggyr-tigris:shuffle!) T
function
array-equal x y &key (test #'equal)
Compares two arrays, element by element. Both arguments must be arrays. If they have different lengths, they are automatically unequal. If their lengths are the same, the elements are compared one at a time. They are compared with the test function. If you want the elements themselves to be compared recursively, like if they are arrays, you must choose an appropriate test function. Maybe that's a bug. Maybe it should automatically recurse into elements that are themselves arrays. I don't know.
Returns true if the arrays have the same length & every element in them is equal (according to test). Returns false otherwise.
8> (array-equal #(1 2 3) #(1 2 3)) T 9> (setq x (make-array 3 :initial-contents '(a b c))) #(A B C) 10> (setq y (make-array 3 :initial-contents '(a b c))) #(A B C) 11> (eq x y) NIL 12> (eql x y) NIL 13> (equal x y) NIL 14> (array-equal x y) T 15> (array-equal #(1 2 3) #(1 2 3 4)) NIL 16> (array-equal #(1 2 3) #(1 3 2)) NIL
macro
until expr &body body
Evaluate body repeatedly as long as expr is not true. It's a pre-exit loop; in other words, it might execute body zero times.
[58]> (let ((i 0))
(until (>= i 10)
(incf i))
i)
10
macro
while expr &body body
Evaluate body until expr is not true. It's a pre-exit loop; in other words, it might evaluate body zero times.
[59]> (let ((i 0))
(while (< i 10)
(incf i))
i)
10
function
assoc-to-hash-table assoc &key (type #'eql)
Returns a new hash table that contains the same associations that are in assoc. Assoc is an association list.
lisp> (assoc-to-hash-table '((a . 1) (b . 2))) #<hash-table containing (A . 1), (B . 2)>
It's okay if assoc is empty.
lisp> (assoc-to-hash-table ()) #<hash-table that is empty>
If assoc contains duplicate keys, you can't predict which value associated with a duplicate key will be in the hash table. For example:
lisp> (defvar
*ht*
(assoc-to-hash-table
(list (cons 'x 1)
(cons 'x 2)
(cons 'x 3))))
*HT*
After evaluating that expression, ``(gethash 'x *ht*)'' could return 1, 2, or 3. Whichever it is is implementation-dependent.
function
maphashcar fn ht
Like maphash except that it collects the results in a list, as does mapcar. Thus, maphashcar.
Fn is a function is two arguments: a key & a value. No guarrantees are made about the order of the elements in the resulting list. It's sort-of as if the entires in the hash table were visited in parallel.
[16]> (setq h (make-hash-table))
#S(HASH-TABLE EQL)
[17]> (setf (gethash 1 h) 'a)
A
[18]> (setf (gethash 2 h) 'b
(gethash 3 h) 'c)
C
[19]> h
#S(HASH-TABLE EQL (3 . C) (2 . B) (1 . A))
[20]> (maphashcar #'(lambda (k v) (cons k v)) h)
((1 . A) (2 . B) (3 . C))
function
hashtable-keys ht
Return a list of the keys in the hash table. No guarrantees about order.
21> (setq h (make-hash-table)) #S(HASH-TABLE EQL) 22> (setf (gethash 'a h) 1) 1 23> (setf (gethash 'b h) 2) 2 24> (setf (gethash 'c h) 3) 3 25> (setf (gethash 'd h) 4) 4 26> (hashtable-keys h) (A B C D)
function
hashtable-values ht
Return a list of the values in the hash table. No guarrantees about order.
21> (setq h (make-hash-table)) #S(HASH-TABLE EQL) 22> (setf (gethash 'a h) 1) 1 23> (setf (gethash 'b h) 2) 2 24> (setf (gethash 'c h) 3) 3 25> (setf (gethash 'd h) 4) 4 27> (hashtable-values h) (1 2 3 4)
function
create-heap less-fn &key (order 2)
(initial-contents nil)
Creates a new heap with make-heap, initializes it with heap-init, & returns it.
Items in the heap are ordered according to less-fn. In other words, if two elements a & b are in the heap, a will be before b if (funcall less-fn a b) returns truth.
Initial-contents must be a list, though nil is acceptable. If initial-contents is a non-empty list, the heap's contents are intiailized to the values in that list.
order is the number of children each node in the heap has. It defaults to 2, which is a binary heap. It could be, say, 3 or 4 or 10. It must be an integer greater than 1.
structure
heap
Normally, you don't need to think about the innards of the heap structure.
Here are the members of the heap structure:
Because heap is a structure, each of the members has an accessor defined by defstruct in the usual way. The heap-less-fn & heap-max-count accessors, used for read-only, might be useful fairly often. The heap-a accessor should be used only if terribly necessary.
Using (setf heap-max-count) might be useful if you want to reset the max-count to zero because, say, you want to measure the heap capacity required by sections of a program.
function
heap-clear heap
Removes all elements from the heap. Does not return them. Faster than calling heap-remove in a loop until the heap is empty.
function
heap-count heap
Returns the number of items in the heap. That is the number of times heap-insert has been called, less the number of times heap-remove has been called. The count of an empty heap is zero, but if you just need to test whether a heap is empty, it might be a good idea to use heap-empty-p instead.
function
heap-empty-p heap
Returns true if & only if the heap is empty.
I recommend using heap-empty-p to test for an empty heap because it is probably more readable than fetching the count & comparing it to zero, & because heap-empty-p might be slightly more efficient than using heap-count for the task.
function
heap-foreach heap fn
Call the function fn on each item in the heap. Fn is a function of one argument, the item from the heap. Heap-foreach makes no guarrantee on the order in which the items are visited.
Returns nothing of importance at this time; returns NIL.
[6]> (setq hp (create-heap #'<))
#S(HEAP :LESS-FN #<SYSTEM-FUNCTION <>
:ORDER 2 :A #(NIL) :MAX-COUNT 0)
[7]> (dotimes (i 5) (heap-insert hp i))
NIL
[8]> (let ((lst ()))
(heap-foreach hp
#'(lambda (x)
(push x lst)))
lst)
(0 1 2 3 4)
[9]>
Maybe should have called it heap-map. Oh well.
function
heap-init heap less-fn &key (order 2) (initial-contents nil)
Initialize the indicated heap. If initial-contents is a non-empty list, the heap's contents are intiailized to the values in that list; they are ordered according to less-fn. initial-contents must be a list or nil.
Instead of using make-heap & then heap-init, it's recommended that you create a heap with create-heap.
function
heap-insert heap x
Insert item x into the heap. Return x, which probably isn't very useful.
function
heap-peek heap
If the heap is not empty, return the minimum (first) item in the heap. Do not remove that item from the heap.
It is an error if the heap is empty.
function
heap-remove heap (fn #'(lambda (h x) t))
Remove the first element in the heap that satisfies the predicate fn. Returns the element that was removed, or nil if no element matched the predicate.
The default value for fn is a predicate which matches the first item in the heap. So ``(heap-remove h)'' removes & returns the first element in the heap, or nil if the heap was already empty.
function
make-heap &optional ...
Returns a new heap structure. Before you use it, you should initialize it with heap-init.
Instead of using make-heap & then heap-init, it's recommended that you create a heap with create-heap.
function
slurp-file pn
Return a string containing the entire contents of a text file.
Pn is a pathname or a string which can serve as a pathname or any other datum which can serve as the pathname argument to the OPEN function.
;; Create a temporary file for the example.
> (with-open-file (strm "booga.wooga" :direction :output)
(format strm "booga wooga woo"))
NIL
> (slurp-file "booga.wooga")
"booga wooga woo"
;; Remove the file.
> (delete-file "booga.wooga")
function
slurp-stream strm
Return a string containing the entire contents of the rest of a stream.
Strm is a stream which can be read with READ-CHAR . SLURP-STREAM will read everything from strm until it encouters the end of stream. Then it will return a string containing everything it read.
> (setq strm (make-string-input-stream "nobody knows the troubles I've seen")) #<INPUT STRING-INPUT-STREAM> > (slurp-stream strm) "nobody knows the troubles I've seen" > (close strm) T
function
generate-list len make-elt-fn
Returns a new list of length len whose elements were created by calling the function bound to make-elt-fn. (We call make-elt-fn for each element.) Returns an empty list for a len of zero.
Make-elt-fn is a function of no arguments.
Interestingly, the original, recursive version of this function was limited by stack size to a len of less than 50,000. I experimented with iterative implementions, one that used loop and one that used loop. It's possible that the dotimes implementation was faster, but by something like 1 percent, or less, so I decided to keep the loop implementation, since it is simpler.
13> (generate-list 0 #'(lambda () (random 5))) NIL 14> (generate-list 10 #'(lambda () (random 5))) (2 0 0 0 3 0 2 1 3 2) 15> (generate-list 5 (let ((i 0)) #'(lambda () (incf i)))) (1 2 3 4 5)
function
mappend fn &rest the-lists
Apply to each element of the lists and append the results.
I think I got this function from [2].
[30]> (mappend #'list '(a b c d)) (A B C D) [31]> (mappend #'(lambda (x) (and x (list x))) '(1 () 2 () 3 ())) (1 2 3)
function
snoc lst x
Return (append lst (list x)). lst must be a list.
I got this from [3].
function
make-guid
Create & return a new Globally Unique Identifier as a string.
Uses the RANDOM function. There is a decent possibility that GUIDs created by different processes that run at the same time will not be unique. MAKE-GUID does not take cryptographic steps to hide the state of your random number generator. Using a random number generator to make the GUIDs is risky in the first place. In the future, many of these problems might change.
> (import 'cybertiggyr-tigris:make-guid)
T
> (loop for i from 1 to 5 collect (make-guid))
("DB83D5F0-E528-AD27-4563-916B76550788"
"5CC614AA-6202-204C-DAA9-E2A2428FD86B"
"3BD64455-AC5A-93DD-BA4D-A6B7FE2B0549"
"0F5FE082-68BE-F5DA-058B-8937B1A8FECE"
"B5FAB84A-95BB-1193-77F1-7E945207655C")
function
tree-size tr
Returns the number of nodes (internal & external) in the indicated tree.
This function exists for a special case in a genetic programming library I wrote. It should be in that library, not in CyberTiggyr Tigris. If I ever need more functions for manipulating trees, I should write a more comprehensive (but still small) suite of them. Maybe functions for building trees, traversing (in-order, post, pre).
function
fibonacci n
Returns the Fibonacci number for N.
5> (mapcar #'fibonacci '(0 1 2 3 4 10)) (1 1 2 3 5 89)
function
relative-error value expected
Returns the relative error. If expected is zero, returns the absolute error. Value & expected must be floating-point.
[36]> (relative-error 1.1 1.0) 0.100000024 [37]> (relative-error 1.99 2.0) 0.004999995 [38]> (relative-error 1.0 0.0) 1.0
function
find-all-if predicate sqnc
Return a list of all items from the sequence which satisfy the predicate. Predicate is a function of one argument.
10> (find-all-if #'identity '(1 2 3 a b c)) (1 2 3 A B C) 11> (find-all-if #'identity '(nil 1 nil 2 nil 3 nil)) (1 2 3) 12> (find-all-if #'(lambda (x) (and (numberp x) (< x 5))) '(1 3 5 7 a b)) (1 3)
function
random-elt seq
Returns a randomly selected element from the sequence seq.
[32]> (setq a
(make-array
10
:initial-contents (loop for x from 0 to 9
collect x)))
#(0 1 2 3 4 5 6 7 8 9)
[34]> (random-elt a)
3
[35]> (do ((s () (push (random-elt a) s))
(i 0 (1+ i)))
((>= i 15) s))
(8 4 3 8 8 6 8 8 3 9 7 1 0 6 2)
function
search-plain needle haystack test
Needle is a sequence. Haystack is a sequence.
Return the position of needle in haystack, if needle is in haystack. If needle is not in haystack, you get a number that is at least (LENGTH HAYSTACK), larger if haystack is empty.
Like the Common Lisp function SEARCH except that SEARCH-PLAIN uses a brute-force search algorithm.
The test function is used to compare elements. It is required. It should be a function or a symbol whose SYMBOL-FUNCTION is bound to a function.
A special case is a needle that is NIL. It can be found at position 0 in any haystack.
Another special case is an empty haystack. It contains the empty needle but no other subsequences. For an empty needle in an empty haystack, you get zero, but for any other needle in an empty haystack, you get 1.
If needle is longer than haystack, you get (LENGTH HAYSTACK).
For most cases, you should use the Common Lisp function SEARCH. I wrote SEARCH-PLAIN for comparing performances.
function
shuffle seq &optional (r #'random)
Return a shuffled copy of the sequence. Does not affect seq.
[50]> (setq x
(loop for i from 0 to 9
collect i))
(0 1 2 3 4 5 6 7 8 9)
[51]> (shuffle x)
(7 1 6 0 2 4 3 9 8 5)
[52]> (shuffle x)
(7 5 9 4 2 1 0 6 8 3)
[53]> x
(0 1 2 3 4 5 6 7 8 9)
function
shuffle! sequence &optional (r #'random)
Destructively shuffles sequence in-place and returns sequence. Sequence will hold the same elements, but they will be in a randomized order. R is a random number genrator function. Defaults to #'random.
[39]> (setq x
(loop for i from 0 to 10
collect i))
(0 1 2 3 4 5 6 7 8 9 10)
[40]> (shuffle! x)
(4 8 10 5 7 0 6 1 3 2 9)
[41]> x
(4 8 10 5 7 0 6 1 3 2 9)
function
join separator &rest strings
Like Perl's join operator. Separator may be a string, character, or symbol. Strings is a a list of strings, characters, or symbols, or strings is empty. If strings is empty, join returns the empty string. Otherwise, it returns a string that is the concatenation of the elements in strings, separated by separator. The separator will not prefix or terminate the resulting string.
[11]> (import 'cybertiggyr-tigris:join) T [12]> (describe 'join) JOIN is the symbol JOIN, lies in #<PACKAGE CYBERTIGGYR-TIGRIS>, is accessible ;; ... blah blah blah removed for brevity ... [13]> ;; Basic functionality (join ":" "puce" "aqua" "dots") "puce:aqua:dots" [14]> ;; The separator can be a character. (join #\: "puce" "aqua" "dots") "puce:aqua:dots" [15]> ;; The separator can be a symbol. (join '- "puce" "aqua" "dots") "puce-aqua-dots" [16]> ;; The components may be characters, ;; numbers or strings. (join ":" #\x 1 'x) "x:1:X" [17]> ;; No components results in empty string. (join ":") "" [18]> ;; When components are empty strings, you can ;; get strange results. (join ":" "" "" "") "::" [19]
function
split separator string
Like Perl's split operator. Separator must be a character. String is a string; the empty string is okay.
Returns a list of the substrings from string that are separated by the separator character. The separator character is not in the substrings. Separator characters that are next to each other in the original string demark an empty substring.
> (import 'cybertiggyr-tigris:split)
T
> (describe 'split)
SPLIT is the symbol SPLIT, lies in #<PACKAGE CYBERTIGGYR-TIGRIS>, is accessible
;; ... blah blah blah removed for brevity ...
> (split #\: "puce:aqua:dots")
("puce" "aqua" "dots")
> (split #\, "")
"" ; empty string gives empty list
> (split #\: "::")
("" "" "") ; substrings can be empty
function
day-of-week when &optional (how :by-number)
Returns the day-of-week for when. When is a universal time. If how is :by-number, returns the number of the day of the week. (Monday is 0.) If how is :english, returns an English name for the day (Sunday, Monday, ... Saturday) in a string. If how is :by-name, returns system-specific name as a string (currently in English). In the future, there may be other possible values for how. Maybe :french or :japanese or :venusian. Otherwise, signals an error.
Example from Pacific Time Zone when Daylight Stupid Time was in effect:
22> (get-universal-time) 3260153585 23> (day-of-week * :english) "Wednesday"
function
parse-date str
Calculates & returns a UNIVERSAL TIME that represents the time-&-date expressed in the human-readable string, str.
Recognizes a variety of different formats. It's not that this function is intelligent about time-&-date formats; it's simply hard-coded to recognize many formats. In general, missing components of the date are assumed to be the current date, while missing components of the time are assumed zero.
Here are discussions of the time-&-date formats recognized by PARSE-DATE.
At least, I think this is the format specified by ISO.
The general form of this format is
The components may be separated by single hyphens (-), single colons (:), or any amount of white-space.
.
. Second may be a floating point number, but the
fractional part may be ignored depending on the limit of
resolution of your computer's clock & Common Lisp's universal time.
Examples of using the ISO format are:
Here is the grammar the parser actually understands.
S 
year `-' month `-' day tee hour `:' minute `:' second ampm
or year `-' month `-' day tee hour `:' minute
or year `-' month `-' day
or time
or date time
or time date
;
time hour `:' minute `:' second ampm
or hour `:' minute ampm
;
date day month-name year
or day month-abbreviation year
or month-name day `,' year
or month-abbreviation day `,' year
or month `/' day `/' year
;
year digits ;
month digits or month-name or
month-abbreviation ;
day digits ;
hour digits ;
minute digits ;
second digits or digits `.' digits ;
spaces one or more space or tab
characters
digits one or more decimal digits
tee `T' or `t' ;
This chapter documents some of the internals of CyberTiggyr Tigris. The symbols here are for Tigris's programmer(s), not for programmers using Tigris. Programmers using Tigris should confince themselves to the symbols documented in Chapter 5.
function
heap-find-idx heap fnp
Return the index of the element in heap which satisfies the predicate fnp. If there is no such element, return the fill pointer of heap's array A.
fnp is a function of two arguments, the heap & an element in the heap.
function
lesser-child heap parent
Parent is the index of an element in (heap-a heap).
Return the index of the lesser child of parent. If there's one child, returns the index of that child. If there are no children, return (fill-pointer (heap-a heap)).
function
percolate-down heap hole x
Move the ``hole'' (unused element) of the heap to larger indexes until its position is appropriate to hold x. Return the new index of the hole.
Heap is a heap as returned by create-heap.
Hole is the index of an element in the heap's array
((heap-a heap)). Assume
,
where len is (length (heap-a heap)).
X is an object that (heap-less-fn heap) can compare to other objects in the heap.
function
percolate-up heap hole x
Private. Moves the hole until it's in a location suitable for holding x. Does not actually bind x to the hole. Returns the new index of the hole. The hole itself percolates down; it's the x that percolates up.
You can view the sources for the test programs in tigris/src/test.lisptest.lisp.
This is reference material for developers of CyberTiggyr Tigris.
It's complex enough to deserve automation, but I need to debug it by following it manually a few times, then I'll automate it.
On a terminal, cd to $HOME/src/tigris & run clisp. In Lisp, evaluate ``(load "src/tigris.lisp")'' & then ``(load "src/test.lisp")''. To run the test programs, evaluate ``(check *tests*)''.
You can also run the test programs from the command line: ``make check''.