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