;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;; ;;;;;;;;
;;;;;; All files in this directory or any subdirectories are ;;;;;;;;
;;;;;; copyright 1997, 1998, 1999, 2000, 2002, 2003. ;;;;;;;;
;;;;;; by Rafael D. Sorkin. All rights reserved. ;;;;;;;;
;;;;;; ;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
A PACKAGE OF LISP FUNCTIONS FOR USE WITH POSETS
The documentation in this file supplements that in README
Contents of this file
=====================
Uses of this package
Why use Lisp for posets/causal sets?
How posets are represented in this package
Some poset terminology used in the documentation
Some of the poset functions defined in this package
Lisp functions and macros of general utility in this package
Improvements to Lisp in this package
Other packages available for posets
Drawbacks of Lisp
Elisp versus Common Lisp
Lisp versus C
Uses of this package
====================
This package can be used as a "scratch pad" for working with posets; it
also makes possible a large range of causal set simulations. For
example, one can generate causal sets randomly with certain families of
probability distributions and collect statistics about properties such
as their fractal dimensions. The package can also be used to validate
(or prototype) programs for posets written in other languages like C or
Fortran.
Note: I'm always using use the word `package' in its informal English
sense. This library is not designed as a package in the technical
Common Lisp sense. (It could not be, because such packages are not
implemented in Elisp, and this library is designed to work with both
Common Lisp and Elisp.)
Why use Lisp for posets/causal sets?
====================================
Posets are more combinatorial than numerical in nature. Conceptually,
they are more naturally expressed as either mappings or sets of ordered
pairs, than as matrices of 1's and 0's. Thus, for example, a poset can
be represented as the mapping that takes each element to the set of
elements strictly to its past.
Such a representation is congenial to Lisp because `symbols' and `lists'
are the basic structural elements of the language and `evaluation' is
the basic activity of the Lisp interpreter. Thus, symbols can serve as
the poset elements and lists can serve as their pasts. The mapping from
an element to its past can be represented by making the symbol evaluate
to its past. Other pertinent properties of an element (its level in the
poset, its future, the value of some scalar field at that element, etc.)
can be kept conveniently on the symbol's `property list'.
An important convenience of using Lisp is that lists can change size
"dynamically", whence storage for them does not have to be allocated
explicitly. For example, in taking the transitive closure of a
relation (or in a Monte Carlo type simulation), the pasts of the
individual elements are constantly changing in size. All this is
handled automatically by the Lisp housekeeping routines.
Lisp is interactive like Maple or APL. This makes it especially
useful for "developmental" work, as opposed to "production" runs (aka
playing around with posets in order to get a feel for them). It also
makes for more flexibility in "one off" situations, since one is not
required to write and compile a special purpose program for each
computation. A particular convenience in this connection is that the
emacs editor offers very flexible facilities for running elisp, and
for running other dialects of Lisp from within emacs.
Lisp is a high level language, making it easier to code simply and
accurately. This also makes it useful for checking code written in
other languages, e.g. Alan Daughton's and Roberto Salgado's Fortran and
C code for studying a scalar field on a background causal set, or David
Rideout's C code for simulating causet dynamics. The qualitative
difference between Lisp and Fortran or C makes such a check all the more
effective.
Finally, Lisp code is written in a way that would seem to lend itself to
parallelization. For example the function `mapcar' could just be made
to act on all the elements of its argument-list simultaneously, rather
than sequentially.
How posets are represented in this package
==========================================
In this package, symbols serve as the poset elements and lists-as-sets
serve as their pasts. By default, the mapping from an element to its
past is represented by making the symbol evaluate to its past. Other
pertinent properties of an element (its level in the poset, the number
of its ancestors or parents, its coordinates in some embedding, etc.)
can be kept conveniently on the symbol's `property list'.
The function `past' returns the past of a given element, and one can
modify an element's past using `setf'. For example
(past 'a)
will return the past of the symbol `a' and
(setf (past 'a) (list 'b 'c))
will cause that past to equal (b c). By convention, we use the
exclusive past, ie an element does not precede itself.
If you wish to change any of this, you can do so (at least in principle)
by redefining the function `past' and its associated setf.
Some poset terminology used in the documentation
================================================
[A much fuller glossary is maintained by Peter Cameron at
http://www.maths.qmul.ac.uk/~pjc/csg.html .
See the links "Causal set glossary and bibliography"]
order = poset = partial order = acyclic transitive directed graph
preorder = preposet = acyclic irreflexive relation
NB: some people define `preorder' differently
past : will be taken with respect to the *irreflexive* convention
pre-pseudo-order = directed graph = digraph = relation
link = an irreducible relation in an order = covering relation
chain = a linearly ordered subset of an order
path = saturated chain
= chain all of whose links are links of the ambient order
substrate = the underlying set of symbols "carrying" the partial order
causet = causal set = poset regarded as a discrete spacetime
Some of the poset functions defined in this package
====================================================
See the files "bibliotek.poset.l" and "bibliotek.extras.l" for a full
listing and more complete documentation. (In elisp the command
`describe-function' will tell you most of what you need to know about
any given function.)
The following are all present in this package. In addition I have
written several others which work well, but have not yet been fully
tested. Example: a function to find the width of a poset (cardinality
of the biggest antichain). If you are interested in obtaining any of
these, please email me (at sorkin@physics.syr.edu).
past (returns the past of an element, setf method also provided)
past-of (extensions to relative past, past of set, inclusive past)
prec (is x < y ?)
jana (the set of ``past nearest neighbors'' or ``parents'' of an element)
stem-p (does this subset include the pasts of all its elements?)
chain-p (is this subset a chain?)
antichain-p (is this subset an antichain?)
order-interval (the interval or ``Alexandrov set'' between two elements)
future (the future of an element rel a set)
maximal (the set of maximal elements of a subset of a poset)
minimal (the set of minimal elements of a subset of a poset)
connected-parts (the set of connected components of a poset)
antichains (the set of antichains of a poset)
midpoints
compute-links
compute-levels
count-relations
count-links
count-chains
count-paths
log2-spanning-trees
log2-spanning-Hasse-trees
ordering-fraction
myrheim-meyer-dim
mps-dim
posort (sorts a subposet upward)
sort-pasts-downward
t-close (forms the transitive closure of an acyclic relation)
t-close-digraph (a transitive closer that allows for cycles)
transitive-p (is this relation transitive?)
n-delete-from-poset (deletes an element from a poset)
prepare-substrate (makes a "blank" substrate)
create-order (useful for making small posets by hand)
create-relation (useful for making small relations by hand)
make-chain
percolate-unoriginated-order (generates a poset by transitive percolation)
percolate-originary-poset
make-KR-order (generates a poset of Kleitman-Rothschild type)
poset-subobject
copy-poset
poset-to-plist
plist-to-poset
invert-poset-destructively
make-test-preposet
Lisp functions and macros of general utility in this package
============================================================
These include a large number of set-theoretic functions, arithmetic
functions, statistics functions, and other functions and macros of
general utility. They can be found mainly in the following files:
bibliotek.general.el
bibliotek.float.el
bibliotek.extras.el
bibliotek.macros.l
See those files for a complete listing and for further documentation.
The set-functions include functions tailored specially for sets of
symbols and that operate in linear time. Their names end in "%%":
union%%, intersection%%, equal%%, disjointp%%, symmetric-difference%%,
etc.
The statistics functions like `stats' find mean, standard deviation
sigma, etc, including an "error bar" on sigma.
In addition, there are many other functions and macros with a variety of
applications, for example the combinatorial function `choose', a
root-finding function `solve-monotone', a function `fibers' to form
equivalence classes, a macro `image' that provides the equivalent of
`mapcar' but with a very compact syntax, a timing macro for elisp, and
many others.
Improvements to Lisp in this package
=====================================
(To be found mainly in the file bibliotek.macros.l
See especially the macro `deff' and its documentation.)
The main improvement is the provision of truly local variables/symbols.
In addition, there are macros to facilitate a more convenient syntax
that can be used in preference to `let' , `flet' and `macrolet'
A deficiency of elisp is that all its variables are what is called
`special' in Lisp terminology. This means for example that two "local"
variables used in different functions are not really distinct if they
have the same name. In true Common Lisp, this problem is partly
alleviated by the rules of "lexical scoping", but it still persists to a
lesser extent. (For example any two symbols with the same name will
share the same property list, because they are really the same symbol,
even though they may have different "bindings".)
This kind of name collision is a serious problem in general, but in the
present context, it is is a recipe for disaster, because it means there
is no way to avoid a function's inadvertently changing the values of
poset elements whose names it doesn't necessarily know.
This package contains a set of macros that cure this localization
problem by providing true local variables for use within defined
functions. By including something like `(&localize x y z)' in the
function you insure that the symbols x, y, and z will be entirely
distinct from any other symbols of the same name. (See the macro `deff'
for more details.)
In addition the package utilizes several macros designed to simplify the
syntax of commonly used Lisp constructs. For example, instead of
writing, `(let ((x 3)) ...)' you can say simply `(varbind x 3)'. (See
the macros `deff' and `csynf' for more details.)
Other packages available for posets
===================================
John Stembridge has written an interesting looking one in Maple.
He mentions that, for greater efficiency, one should probably use
either Lisp or C.
Drawbacks of Lisp
=================
Lisp is slower than C and Fortran, even after compilation. In many
cases it is dramatically slower. To some extent this seems to be the
ineveitable tradeoff one makes in exchange for the transparency and
flexibility of a high level language like Lisp. However, I believe it
is partly just that more efficient lisp compilers have not yet been
written, a partial exception being CMU lisp. (Also, in the case of
elisp, only "byte compilation" is available, not true compilation.)
Potentially, a good compiler should be able to speed things up
considerably, especially when type declarations are provided, as one is
required to do in languages like C.
The printed representation of lisp code can be awkward, with virtually
all grouping done by parentheses, in contrast to languages which utilize
separating words like `then' and `else'. However, the formatting
facilities of editors like emacs make the visual parsing of multiple
parentheses fairly painless. Moreover, my package introduces several
macros like `vbind' that help make lisp syntax still clearer (see
above).
Elisp versus Common Lisp
========================
Emacs Lisp (elisp) is widely available since virtually all unix
systems come with emacs; other lisps are not as ubiquitous.
Using the CL package distributed with emacs provides most of the Common
Lisp functions which Elisp lacks. Not having truly local
function-parameters (variables with `lexical scope') is a major
nuisance. However, my package compensates for this problem with the
macro `deff' (see above).
Lisp versus C
=============
C has structures and pointers, so in principle it affords
the same possibilities as Lisp does for representing
posets naturally.
Sets with dynamically changing sizes are possible in C, as
in Lisp. A difference is that memory allocation is done
automatically in Lisp, but must be controlled explicitly by the
programmer in C.
C is not interactive, Lisp is.
C is not as high level as Lisp.
C lacks built-ins for dealing with sets.
C code runs much faster than Lisp code.