Initial population.

1 files changed, 803 insertions, 0 deletions

diff --git a/src/algebra/list.spad.pamphlet b/src/algebra/list.spad.pamphlet
new file mode 100644
index 00000000..d773bb61
--- /dev/null
+++ b/src/algebra/list.spad.pamphlet
@@ -0,0 +1,803 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra list.spad}
+\author{Michael Monagon, Manuel Bronstein}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{domain ILIST IndexedList}
+<<domain ILIST IndexedList>>=
+)abbrev domain ILIST IndexedList
+++ Author: Michael Monagan
+++ Date Created: Sep 1987
+++ Change History:
+++ Basic Operations:
+++   \#, concat, concat!, construct, copy, elt, elt, empty,
+++   empty?, eq?, first, member?, merge!, mergeSort, minIndex,
+++   parts, removeDuplicates!, rest, rest, reverse, reverse!,
+++   setelt, setfirst!, setrest!, sort!, split!
+++ Related Constructors: List
+++ Also See:
+++ AMS Classification:
+++ Keywords: list, aggregate, index
+++ Description:
+++   \spadtype{IndexedList} is a basic implementation of the functions
+++   in \spadtype{ListAggregate}, often using functions in the underlying
+++   LISP system. The second parameter to the constructor (\spad{mn})
+++   is the beginning index of the list. That is, if \spad{l} is a
+++   list, then \spad{elt(l,mn)} is the first value. This constructor
+++   is probably best viewed as the implementation of singly-linked
+++   lists that are addressable by index rather than as a mere wrapper
+++   for LISP lists.
+IndexedList(S:Type, mn:Integer): Exports == Implementation where
+ cycleMax ==> 1000        -- value used in checking for cycles
+
+-- The following seems to be a bit out of date, but is kept in case
+-- a knowledgeable person wants to update it:
+--   The following LISP dependencies are divided into two groups
+--   Those that are required
+--   CONS, EQ, NIL, NULL, QCAR, QCDR, RPLACA, RPLACD
+--   Those that are included for efficiency only
+--   NEQ, LIST, CAR, CDR, NCONC2, NREVERSE, LENGTH
+--   Also REVERSE, since it's called in Polynomial Ring
+
+ Qfirst  ==> QCAR$Lisp
+ Qrest   ==> QCDR$Lisp
+ Qnull   ==> NULL$Lisp
+ Qeq     ==> EQ$Lisp
+ Qneq    ==> NEQ$Lisp
+ Qcons   ==> CONS$Lisp
+ Qpush   ==> PUSH$Lisp
+ 
+ Exports ==> ListAggregate S 
+ Implementation ==>
+  add
+   #x                  == LENGTH(x)$Lisp
+   concat(s:S,x:%)     == CONS(s,x)$Lisp
+   eq?(x,y)            == EQ(x,y)$Lisp
+   first x             == SPADfirst(x)$Lisp
+   elt(x,"first")      == SPADfirst(x)$Lisp
+   empty()             == NIL$Lisp
+   empty? x            == NULL(x)$Lisp
+   rest x              == CDR(x)$Lisp
+   elt(x,"rest")       == CDR(x)$Lisp
+   setfirst_!(x,s)     ==
+      empty? x => error "Cannot update an empty list"
+      Qfirst RPLACA(x,s)$Lisp
+   setelt(x,"first",s) ==
+      empty? x => error "Cannot update an empty list"
+      Qfirst RPLACA(x,s)$Lisp
+   setrest_!(x,y)      ==
+      empty? x => error "Cannot update an empty list"
+      Qrest RPLACD(x,y)$Lisp
+   setelt(x,"rest",y)  ==
+      empty? x => error "Cannot update an empty list"
+      Qrest RPLACD(x,y)$Lisp
+   construct l         == l pretend %
+   parts s             == s pretend List S
+   reverse_! x         == NREVERSE(x)$Lisp
+   reverse x           == REVERSE(x)$Lisp
+   minIndex x          == mn
+
+   rest(x, n) ==
+      for i in 1..n repeat
+         if Qnull x then error "index out of range"
+         x := Qrest x
+      x
+
+   copy x ==
+      y := empty()
+      for i in 0.. while not Qnull x repeat
+         if Qeq(i,cycleMax) and cyclic? x then error "cyclic list"
+         y := Qcons(Qfirst x,y)
+         x := Qrest x
+      (NREVERSE(y)$Lisp)@%
+
+   if S has SetCategory then
+     coerce(x):OutputForm ==
+        -- displays cycle with overbar over the cycle
+        y := empty()$List(OutputForm)
+        s := cycleEntry x
+        while Qneq(x, s) repeat
+          y := concat((first x)::OutputForm, y)
+          x := rest x
+        y := reverse_! y
+        empty? s => bracket y
+        -- cyclic case: z is cylic part
+        z := list((first x)::OutputForm)
+        while Qneq(s, rest x) repeat
+           x := rest x
+           z := concat((first x)::OutputForm, z)
+        bracket concat_!(y, overbar commaSeparate reverse_! z)
+
+     x = y ==
+       Qeq(x,y) => true
+       while not Qnull x and not Qnull y repeat
+          Qfirst x ^=$S Qfirst y => return false
+          x := Qrest x
+          y := Qrest y
+       Qnull x and Qnull y
+
+     latex(x : %): String ==
+       s : String := "\left["
+       while not Qnull x repeat
+         s := concat(s, latex(Qfirst x)$S)$String
+         x := Qrest x
+         if not Qnull x then s := concat(s, ", ")$String
+       concat(s, " \right]")$String
+
+     member?(s,x) ==
+        while not Qnull x repeat
+           if s = Qfirst x then return true else x := Qrest x
+        false
+
+   -- Lots of code from parts of AGGCAT, repeated here to
+   -- get faster compilation
+   concat_!(x:%,y:%) ==
+      Qnull x => 
+        Qnull y => x
+        Qpush(first y,x)
+        QRPLACD(x,rest y)$Lisp
+        x
+      z:=x
+      while not Qnull Qrest z repeat
+        z:=Qrest z
+      QRPLACD(z,y)$Lisp
+      x
+
+   -- Then a quicky:
+   if S has SetCategory then
+     removeDuplicates_! l ==
+       p := l
+       while not Qnull p repeat
+--       p := setrest_!(p, remove_!(#1 = Qfirst p, Qrest p))
+-- far too expensive - builds closures etc.
+         pp:=p
+         f:S:=Qfirst p
+         p:=Qrest p
+         while not Qnull (pr:=Qrest pp) repeat
+           if (Qfirst pr)@S = f then QRPLACD(pp,Qrest pr)$Lisp
+           else pp:=pr
+       l
+
+   -- then sorting
+   mergeSort: ((S, S) -> Boolean, %, Integer) -> %
+
+   sort_!(f, l)       == mergeSort(f, l, #l)
+
+   merge_!(f, p, q) ==
+     Qnull p => q
+     Qnull q => p
+     Qeq(p, q) => error "cannot merge a list into itself"
+     if f(Qfirst p, Qfirst q)
+       then (r := t := p; p := Qrest p)
+       else (r := t := q; q := Qrest q)
+     while not Qnull p and not Qnull q repeat
+       if f(Qfirst p, Qfirst q)
+         then (QRPLACD(t, p)$Lisp; t := p; p := Qrest p)
+         else (QRPLACD(t, q)$Lisp; t := q; q := Qrest q)
+     QRPLACD(t, if Qnull p then q else p)$Lisp
+     r
+
+   split_!(p, n) ==
+      n < 1 => error "index out of range"
+      p := rest(p, (n - 1)::NonNegativeInteger)
+      q := Qrest p
+      QRPLACD(p, NIL$Lisp)$Lisp
+      q
+
+   mergeSort(f, p, n) ==
+     if n = 2 and f(first rest p, first p) then p := reverse_! p
+     n < 3 => p
+     l := (n quo 2)::NonNegativeInteger
+     q := split_!(p, l)
+     p := mergeSort(f, p, l)
+     q := mergeSort(f, q, n - l)
+     merge_!(f, p, q)
+
+@
+\section{ILIST.lsp BOOTSTRAP} 
+{\bf ILIST} depends on a chain of
+files. We need to break this cycle to build the algebra. So we keep a
+cached copy of the translated {\bf ILIST} category which we can write
+into the {\bf MID} directory. We compile the lisp code and copy the
+{\bf ILIST.o} file to the {\bf OUT} directory.  This is eventually
+forcibly replaced by a recompiled version.
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<ILIST.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(PUT (QUOTE |ILIST;#;$Nni;1|) (QUOTE |SPADreplace|) (QUOTE LENGTH)) 
+
+(DEFUN |ILIST;#;$Nni;1| (|x| |$|) (LENGTH |x|)) 
+
+(PUT (QUOTE |ILIST;concat;S2$;2|) (QUOTE |SPADreplace|) (QUOTE CONS)) 
+
+(DEFUN |ILIST;concat;S2$;2| (|s| |x| |$|) (CONS |s| |x|)) 
+
+(PUT (QUOTE |ILIST;eq?;2$B;3|) (QUOTE |SPADreplace|) (QUOTE EQ)) 
+
+(DEFUN |ILIST;eq?;2$B;3| (|x| |y| |$|) (EQ |x| |y|)) 
+
+(PUT (QUOTE |ILIST;first;$S;4|) (QUOTE |SPADreplace|) (QUOTE |SPADfirst|)) 
+
+(DEFUN |ILIST;first;$S;4| (|x| |$|) (|SPADfirst| |x|)) 
+
+(PUT (QUOTE |ILIST;elt;$firstS;5|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x| "first") (|SPADfirst| |x|)))) 
+
+(DEFUN |ILIST;elt;$firstS;5| (|x| G101995 |$|) (|SPADfirst| |x|)) 
+
+(PUT (QUOTE |ILIST;empty;$;6|) (QUOTE |SPADreplace|) (QUOTE (XLAM NIL NIL))) 
+
+(DEFUN |ILIST;empty;$;6| (|$|) NIL) 
+
+(PUT (QUOTE |ILIST;empty?;$B;7|) (QUOTE |SPADreplace|) (QUOTE NULL)) 
+
+(DEFUN |ILIST;empty?;$B;7| (|x| |$|) (NULL |x|)) 
+
+(PUT (QUOTE |ILIST;rest;2$;8|) (QUOTE |SPADreplace|) (QUOTE CDR)) 
+
+(DEFUN |ILIST;rest;2$;8| (|x| |$|) (CDR |x|)) 
+
+(PUT (QUOTE |ILIST;elt;$rest$;9|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|x| "rest") (CDR |x|)))) 
+
+(DEFUN |ILIST;elt;$rest$;9| (|x| G102000 |$|) (CDR |x|)) 
+
+(DEFUN |ILIST;setfirst!;$2S;10| (|x| |s| |$|) (COND ((SPADCALL |x| (QREFELT |$| 17)) (|error| "Cannot update an empty list")) ((QUOTE T) (QCAR (RPLACA |x| |s|))))) 
+
+(DEFUN |ILIST;setelt;$first2S;11| (|x| G102005 |s| |$|) (COND ((SPADCALL |x| (QREFELT |$| 17)) (|error| "Cannot update an empty list")) ((QUOTE T) (QCAR (RPLACA |x| |s|))))) 
+
+(DEFUN |ILIST;setrest!;3$;12| (|x| |y| |$|) (COND ((SPADCALL |x| (QREFELT |$| 17)) (|error| "Cannot update an empty list")) ((QUOTE T) (QCDR (RPLACD |x| |y|))))) 
+
+(DEFUN |ILIST;setelt;$rest2$;13| (|x| G102010 |y| |$|) (COND ((SPADCALL |x| (QREFELT |$| 17)) (|error| "Cannot update an empty list")) ((QUOTE T) (QCDR (RPLACD |x| |y|))))) 
+
+(PUT (QUOTE |ILIST;construct;L$;14|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|l|) |l|))) 
+
+(DEFUN |ILIST;construct;L$;14| (|l| |$|) |l|) 
+
+(PUT (QUOTE |ILIST;parts;$L;15|) (QUOTE |SPADreplace|) (QUOTE (XLAM (|s|) |s|))) 
+
+(DEFUN |ILIST;parts;$L;15| (|s| |$|) |s|) 
+
+(PUT (QUOTE |ILIST;reverse!;2$;16|) (QUOTE |SPADreplace|) (QUOTE NREVERSE)) 
+
+(DEFUN |ILIST;reverse!;2$;16| (|x| |$|) (NREVERSE |x|)) 
+
+(PUT (QUOTE |ILIST;reverse;2$;17|) (QUOTE |SPADreplace|) (QUOTE REVERSE)) 
+
+(DEFUN |ILIST;reverse;2$;17| (|x| |$|) (REVERSE |x|)) 
+
+(DEFUN |ILIST;minIndex;$I;18| (|x| |$|) (QREFELT |$| 7)) 
+
+(DEFUN |ILIST;rest;$Nni$;19| (|x| |n| |$|) (PROG (|i|) (RETURN (SEQ (SEQ (LETT |i| 1 |ILIST;rest;$Nni$;19|) G190 (COND ((QSGREATERP |i| |n|) (GO G191))) (SEQ (COND ((NULL |x|) (|error| "index out of range"))) (EXIT (LETT |x| (QCDR |x|) |ILIST;rest;$Nni$;19|))) (LETT |i| (QSADD1 |i|) |ILIST;rest;$Nni$;19|) (GO G190) G191 (EXIT NIL)) (EXIT |x|))))) 
+
+(DEFUN |ILIST;copy;2$;20| (|x| |$|) (PROG (|i| |y|) (RETURN (SEQ (LETT |y| (SPADCALL (QREFELT |$| 16)) |ILIST;copy;2$;20|) (SEQ (LETT |i| 0 |ILIST;copy;2$;20|) G190 (COND ((NULL (COND ((NULL |x|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (COND ((EQ |i| 1000) (COND ((SPADCALL |x| (QREFELT |$| 33)) (|error| "cyclic list"))))) (LETT |y| (CONS (QCAR |x|) |y|) |ILIST;copy;2$;20|) (EXIT (LETT |x| (QCDR |x|) |ILIST;copy;2$;20|))) (LETT |i| (QSADD1 |i|) |ILIST;copy;2$;20|) (GO G190) G191 (EXIT NIL)) (EXIT (NREVERSE |y|)))))) 
+
+(DEFUN |ILIST;coerce;$Of;21| (|x| |$|) (PROG (|s| |y| |z|) (RETURN (SEQ (LETT |y| NIL |ILIST;coerce;$Of;21|) (LETT |s| (SPADCALL |x| (QREFELT |$| 35)) |ILIST;coerce;$Of;21|) (SEQ G190 (COND ((NULL (NEQ |x| |s|)) (GO G191))) (SEQ (LETT |y| (CONS (SPADCALL (SPADCALL |x| (QREFELT |$| 13)) (QREFELT |$| 37)) |y|) |ILIST;coerce;$Of;21|) (EXIT (LETT |x| (SPADCALL |x| (QREFELT |$| 18)) |ILIST;coerce;$Of;21|))) NIL (GO G190) G191 (EXIT NIL)) (LETT |y| (NREVERSE |y|) |ILIST;coerce;$Of;21|) (EXIT (COND ((SPADCALL |s| (QREFELT |$| 17)) (SPADCALL |y| (QREFELT |$| 39))) ((QUOTE T) (SEQ (LETT |z| (SPADCALL (SPADCALL (SPADCALL |x| (QREFELT |$| 13)) (QREFELT |$| 37)) (QREFELT |$| 41)) |ILIST;coerce;$Of;21|) (SEQ G190 (COND ((NULL (NEQ |s| (SPADCALL |x| (QREFELT |$| 18)))) (GO G191))) (SEQ (LETT |x| (SPADCALL |x| (QREFELT |$| 18)) |ILIST;coerce;$Of;21|) (EXIT (LETT |z| (CONS (SPADCALL (SPADCALL |x| (QREFELT |$| 13)) (QREFELT |$| 37)) |z|) |ILIST;coerce;$Of;21|))) NIL (GO G190) G191 (EXIT NIL)) (EXIT (SPADCALL (SPADCALL |y| (SPADCALL (SPADCALL (NREVERSE |z|) (QREFELT |$| 42)) (QREFELT |$| 43)) (QREFELT |$| 44)) (QREFELT |$| 39))))))))))) 
+
+(DEFUN |ILIST;=;2$B;22| (|x| |y| |$|) (PROG (#1=#:G102042) (RETURN (SEQ (EXIT (COND ((EQ |x| |y|) (QUOTE T)) ((QUOTE T) (SEQ (SEQ G190 (COND ((NULL (COND ((OR (NULL |x|) (NULL |y|)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (EXIT (COND ((NULL (SPADCALL (QCAR |x|) (QCAR |y|) (QREFELT |$| 46))) (PROGN (LETT #1# (QUOTE NIL) |ILIST;=;2$B;22|) (GO #1#))) ((QUOTE T) (SEQ (LETT |x| (QCDR |x|) |ILIST;=;2$B;22|) (EXIT (LETT |y| (QCDR |y|) |ILIST;=;2$B;22|))))))) NIL (GO G190) G191 (EXIT NIL)) (EXIT (COND ((NULL |x|) (NULL |y|)) ((QUOTE T) (QUOTE NIL)))))))) #1# (EXIT #1#))))) 
+
+(DEFUN |ILIST;latex;$S;23| (|x| |$|) (PROG (|s|) (RETURN (SEQ (LETT |s| "\\left[" |ILIST;latex;$S;23|) (SEQ G190 (COND ((NULL (COND ((NULL |x|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (LETT |s| (STRCONC |s| (SPADCALL (QCAR |x|) (QREFELT |$| 49))) |ILIST;latex;$S;23|) (LETT |x| (QCDR |x|) |ILIST;latex;$S;23|) (EXIT (COND ((NULL (NULL |x|)) (LETT |s| (STRCONC |s| ", ") |ILIST;latex;$S;23|))))) NIL (GO G190) G191 (EXIT NIL)) (EXIT (STRCONC |s| " \\right]")))))) 
+
+(DEFUN |ILIST;member?;S$B;24| (|s| |x| |$|) (PROG (#1=#:G102052) (RETURN (SEQ (EXIT (SEQ (SEQ G190 (COND ((NULL (COND ((NULL |x|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (EXIT (COND ((SPADCALL |s| (QCAR |x|) (QREFELT |$| 46)) (PROGN (LETT #1# (QUOTE T) |ILIST;member?;S$B;24|) (GO #1#))) ((QUOTE T) (LETT |x| (QCDR |x|) |ILIST;member?;S$B;24|))))) NIL (GO G190) G191 (EXIT NIL)) (EXIT (QUOTE NIL)))) #1# (EXIT #1#))))) 
+
+(DEFUN |ILIST;concat!;3$;25| (|x| |y| |$|) (PROG (|z|) (RETURN (SEQ (COND ((NULL |x|) (COND ((NULL |y|) |x|) ((QUOTE T) (SEQ (PUSH (SPADCALL |y| (QREFELT |$| 13)) |x|) (QRPLACD |x| (SPADCALL |y| (QREFELT |$| 18))) (EXIT |x|))))) ((QUOTE T) (SEQ (LETT |z| |x| |ILIST;concat!;3$;25|) (SEQ G190 (COND ((NULL (COND ((NULL (QCDR |z|)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (EXIT (LETT |z| (QCDR |z|) |ILIST;concat!;3$;25|))) NIL (GO G190) G191 (EXIT NIL)) (QRPLACD |z| |y|) (EXIT |x|)))))))) 
+
+(DEFUN |ILIST;removeDuplicates!;2$;26| (|l| |$|) (PROG (|f| |p| |pr| |pp|) (RETURN (SEQ (LETT |p| |l| |ILIST;removeDuplicates!;2$;26|) (SEQ G190 (COND ((NULL (COND ((NULL |p|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (LETT |pp| |p| |ILIST;removeDuplicates!;2$;26|) (LETT |f| (QCAR |p|) |ILIST;removeDuplicates!;2$;26|) (LETT |p| (QCDR |p|) |ILIST;removeDuplicates!;2$;26|) (EXIT (SEQ G190 (COND ((NULL (COND ((NULL (LETT |pr| (QCDR |pp|) |ILIST;removeDuplicates!;2$;26|)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (EXIT (COND ((SPADCALL (QCAR |pr|) |f| (QREFELT |$| 46)) (QRPLACD |pp| (QCDR |pr|))) ((QUOTE T) (LETT |pp| |pr| |ILIST;removeDuplicates!;2$;26|))))) NIL (GO G190) G191 (EXIT NIL)))) NIL (GO G190) G191 (EXIT NIL)) (EXIT |l|))))) 
+
+(DEFUN |ILIST;sort!;M2$;27| (|f| |l| |$|) (|ILIST;mergeSort| |f| |l| (SPADCALL |l| (QREFELT |$| 9)) |$|)) 
+
+(DEFUN |ILIST;merge!;M3$;28| (|f| |p| |q| |$|) (PROG (|r| |t|) (RETURN (SEQ (COND ((NULL |p|) |q|) ((NULL |q|) |p|) ((EQ |p| |q|) (|error| "cannot merge a list into itself")) ((QUOTE T) (SEQ (COND ((SPADCALL (QCAR |p|) (QCAR |q|) |f|) (SEQ (LETT |r| (LETT |t| |p| |ILIST;merge!;M3$;28|) |ILIST;merge!;M3$;28|) (EXIT (LETT |p| (QCDR |p|) |ILIST;merge!;M3$;28|)))) ((QUOTE T) (SEQ (LETT |r| (LETT |t| |q| |ILIST;merge!;M3$;28|) |ILIST;merge!;M3$;28|) (EXIT (LETT |q| (QCDR |q|) |ILIST;merge!;M3$;28|))))) (SEQ G190 (COND ((NULL (COND ((OR (NULL |p|) (NULL |q|)) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (EXIT (COND ((SPADCALL (QCAR |p|) (QCAR |q|) |f|) (SEQ (QRPLACD |t| |p|) (LETT |t| |p| |ILIST;merge!;M3$;28|) (EXIT (LETT |p| (QCDR |p|) |ILIST;merge!;M3$;28|)))) ((QUOTE T) (SEQ (QRPLACD |t| |q|) (LETT |t| |q| |ILIST;merge!;M3$;28|) (EXIT (LETT |q| (QCDR |q|) |ILIST;merge!;M3$;28|))))))) NIL (GO G190) G191 (EXIT NIL)) (QRPLACD |t| (COND ((NULL |p|) |q|) ((QUOTE T) |p|))) (EXIT |r|)))))))) 
+
+(DEFUN |ILIST;split!;$I$;29| (|p| |n| |$|) (PROG (#1=#:G102085 |q|) (RETURN (SEQ (COND ((|<| |n| 1) (|error| "index out of range")) ((QUOTE T) (SEQ (LETT |p| (SPADCALL |p| (PROG1 (LETT #1# (|-| |n| 1) |ILIST;split!;$I$;29|) (|check-subtype| (|>=| #1# 0) (QUOTE (|NonNegativeInteger|)) #1#)) (QREFELT |$| 32)) |ILIST;split!;$I$;29|) (LETT |q| (QCDR |p|) |ILIST;split!;$I$;29|) (QRPLACD |p| NIL) (EXIT |q|)))))))) 
+
+(DEFUN |ILIST;mergeSort| (|f| |p| |n| |$|) (PROG (#1=#:G102089 |l| |q|) (RETURN (SEQ (COND ((EQL |n| 2) (COND ((SPADCALL (SPADCALL (SPADCALL |p| (QREFELT |$| 18)) (QREFELT |$| 13)) (SPADCALL |p| (QREFELT |$| 13)) |f|) (LETT |p| (SPADCALL |p| (QREFELT |$| 28)) |ILIST;mergeSort|))))) (EXIT (COND ((|<| |n| 3) |p|) ((QUOTE T) (SEQ (LETT |l| (PROG1 (LETT #1# (QUOTIENT2 |n| 2) |ILIST;mergeSort|) (|check-subtype| (|>=| #1# 0) (QUOTE (|NonNegativeInteger|)) #1#)) |ILIST;mergeSort|) (LETT |q| (SPADCALL |p| |l| (QREFELT |$| 57)) |ILIST;mergeSort|) (LETT |p| (|ILIST;mergeSort| |f| |p| |l| |$|) |ILIST;mergeSort|) (LETT |q| (|ILIST;mergeSort| |f| |q| (|-| |n| |l|) |$|) |ILIST;mergeSort|) (EXIT (SPADCALL |f| |p| |q| (QREFELT |$| 56))))))))))) 
+
+(DEFUN |IndexedList| (|&REST| #1=#:G102103 |&AUX| #2=#:G102101) (DSETQ #2# #1#) (PROG NIL (RETURN (PROG (#3=#:G102102) (RETURN (COND ((LETT #3# (|lassocShiftWithFunction| (|devaluateList| #2#) (HGET |$ConstructorCache| (QUOTE |IndexedList|)) (QUOTE |domainEqualList|)) |IndexedList|) (|CDRwithIncrement| #3#)) ((QUOTE T) (|UNWIND-PROTECT| (PROG1 (APPLY (|function| |IndexedList;|) #2#) (LETT #3# T |IndexedList|)) (COND ((NOT #3#) (HREM |$ConstructorCache| (QUOTE |IndexedList|)))))))))))) 
+
+(DEFUN |IndexedList;| (|#1| |#2|) (PROG (|DV$1| |DV$2| |dv$| |$| #1=#:G102100 |pv$|) (RETURN (PROGN (LETT |DV$1| (|devaluate| |#1|) . #2=(|IndexedList|)) (LETT |DV$2| (|devaluate| |#2|) . #2#) (LETT |dv$| (LIST (QUOTE |IndexedList|) |DV$1| |DV$2|) . #2#) (LETT |$| (GETREFV 71) . #2#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 (LIST (|HasCategory| |#1| (QUOTE (|SetCategory|))) (|HasCategory| |#1| (QUOTE (|ConvertibleTo| (|InputForm|)))) (LETT #1# (|HasCategory| |#1| (QUOTE (|OrderedSet|))) . #2#) (OR #1# (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (|HasCategory| (|Integer|) (QUOTE (|OrderedSet|))) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (OR (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) #1#) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|))))))) . #2#)) (|haddProp| |$ConstructorCache| (QUOTE |IndexedList|) (LIST |DV$1| |DV$2|) (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 |#1|) (QSETREFV |$| 7 |#2|) (COND ((|testBitVector| |pv$| 1) (PROGN (QSETREFV |$| 45 (CONS (|dispatchFunction| |ILIST;coerce;$Of;21|) |$|)) (QSETREFV |$| 47 (CONS (|dispatchFunction| |ILIST;=;2$B;22|) |$|)) (QSETREFV |$| 50 (CONS (|dispatchFunction| |ILIST;latex;$S;23|) |$|)) (QSETREFV |$| 51 (CONS (|dispatchFunction| |ILIST;member?;S$B;24|) |$|))))) (COND ((|testBitVector| |pv$| 1) (QSETREFV |$| 53 (CONS (|dispatchFunction| |ILIST;removeDuplicates!;2$;26|) |$|)))) |$|)))) 
+
+(MAKEPROP (QUOTE |IndexedList|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL NIL (|local| |#1|) (|local| |#2|) (|NonNegativeInteger|) |ILIST;#;$Nni;1| |ILIST;concat;S2$;2| (|Boolean|) |ILIST;eq?;2$B;3| |ILIST;first;$S;4| (QUOTE "first") |ILIST;elt;$firstS;5| |ILIST;empty;$;6| |ILIST;empty?;$B;7| |ILIST;rest;2$;8| (QUOTE "rest") |ILIST;elt;$rest$;9| |ILIST;setfirst!;$2S;10| |ILIST;setelt;$first2S;11| |ILIST;setrest!;3$;12| |ILIST;setelt;$rest2$;13| (|List| 6) |ILIST;construct;L$;14| |ILIST;parts;$L;15| |ILIST;reverse!;2$;16| |ILIST;reverse;2$;17| (|Integer|) |ILIST;minIndex;$I;18| |ILIST;rest;$Nni$;19| (0 . |cyclic?|) |ILIST;copy;2$;20| (5 . |cycleEntry|) (|OutputForm|) (10 . |coerce|) (|List| |$|) (15 . |bracket|) (|List| 36) (20 . |list|) (25 . |commaSeparate|) (30 . |overbar|) (35 . |concat!|) (41 . |coerce|) (46 . |=|) (52 . |=|) (|String|) (58 . |latex|) (63 . |latex|) (68 . |member?|) |ILIST;concat!;3$;25| (74 . |removeDuplicates!|) (|Mapping| 11 6 6) |ILIST;sort!;M2$;27| |ILIST;merge!;M3$;28| |ILIST;split!;$I$;29| (|Mapping| 6 6 6) (|Equation| 6) (|List| 59) (|Mapping| 11 6) (|Void|) (|UniversalSegment| 30) (QUOTE "last") (QUOTE "value") (|Mapping| 6 6) (|InputForm|) (|SingleInteger|) (|List| 30) (|Union| 6 (QUOTE "failed")))) (QUOTE #(|~=| 79 |value| 85 |third| 90 |tail| 95 |swap!| 100 |split!| 107 |sorted?| 113 |sort!| 124 |sort| 135 |size?| 146 |setvalue!| 152 |setrest!| 158 |setlast!| 164 |setfirst!| 170 |setelt| 176 |setchildren!| 218 |select!| 224 |select| 230 |second| 236 |sample| 241 |reverse!| 245 |reverse| 250 |rest| 255 |removeDuplicates!| 266 |removeDuplicates| 271 |remove!| 276 |remove| 288 |reduce| 300 |qsetelt!| 321 |qelt| 328 |possiblyInfinite?| 334 |position| 339 |parts| 358 |nodes| 363 |node?| 368 |new| 374 |more?| 380 |minIndex| 386 |min| 391 |merge!| 397 |merge| 410 |members| 423 |member?| 428 |maxIndex| 434 |max| 439 |map!| 445 |map| 451 |list| 464 |less?| 469 |leaves| 475 |leaf?| 480 |latex| 485 |last| 490 |insert!| 501 |insert| 515 |indices| 529 |index?| 534 |hash| 540 |first| 545 |find| 556 |fill!| 562 |explicitlyFinite?| 568 |every?| 573 |eval| 579 |eq?| 605 |entry?| 611 |entries| 617 |empty?| 622 |empty| 627 |elt| 631 |distance| 674 |delete!| 680 |delete| 692 |cyclic?| 704 |cycleTail| 709 |cycleSplit!| 714 |cycleLength| 719 |cycleEntry| 724 |count| 729 |copyInto!| 741 |copy| 748 |convert| 753 |construct| 758 |concat!| 763 |concat| 775 |coerce| 798 |children| 803 |child?| 808 |any?| 814 |>=| 820 |>| 826 |=| 832 |<=| 838 |<| 844 |#| 850)) (QUOTE ((|shallowlyMutable| . 0) (|finiteAggregate| . 0))) (CONS (|makeByteWordVec2| 7 (QUOTE (0 0 0 0 0 0 0 0 0 0 3 0 0 7 4 0 0 7 1 2 4))) (CONS (QUOTE #(|ListAggregate&| |StreamAggregate&| |ExtensibleLinearAggregate&| |FiniteLinearAggregate&| |UnaryRecursiveAggregate&| |LinearAggregate&| |RecursiveAggregate&| |IndexedAggregate&| |Collection&| |HomogeneousAggregate&| |OrderedSet&| |Aggregate&| |EltableAggregate&| |Evalable&| |SetCategory&| NIL NIL |InnerEvalable&| NIL NIL |BasicType&|)) (CONS (QUOTE #((|ListAggregate| 6) (|StreamAggregate| 6) (|ExtensibleLinearAggregate| 6) (|FiniteLinearAggregate| 6) (|UnaryRecursiveAggregate| 6) (|LinearAggregate| 6) (|RecursiveAggregate| 6) (|IndexedAggregate| 30 6) (|Collection| 6) (|HomogeneousAggregate| 6) (|OrderedSet|) (|Aggregate|) (|EltableAggregate| 30 6) (|Evalable| 6) (|SetCategory|) (|Type|) (|Eltable| 30 6) (|InnerEvalable| 6 6) (|CoercibleTo| 36) (|ConvertibleTo| 67) (|BasicType|))) (|makeByteWordVec2| 70 (QUOTE (1 0 11 0 33 1 0 0 0 35 1 6 36 0 37 1 36 0 38 39 1 40 0 36 41 1 36 0 38 42 1 36 0 0 43 2 40 0 0 36 44 1 0 36 0 45 2 6 11 0 0 46 2 0 11 0 0 47 1 6 48 0 49 1 0 48 0 50 2 0 11 6 0 51 1 0 0 0 53 2 1 11 0 0 1 1 0 6 0 1 1 0 6 0 1 1 0 0 0 1 3 0 62 0 30 30 1 2 0 0 0 30 57 1 3 11 0 1 2 0 11 54 0 1 1 3 0 0 1 2 0 0 54 0 55 1 3 0 0 1 2 0 0 54 0 1 2 0 11 0 8 1 2 0 6 0 6 1 2 0 0 0 0 23 2 0 6 0 6 1 2 0 6 0 6 21 3 0 6 0 30 6 1 3 0 6 0 63 6 1 3 0 6 0 64 6 1 3 0 0 0 19 0 24 3 0 6 0 14 6 22 3 0 6 0 65 6 1 2 0 0 0 38 1 2 0 0 61 0 1 2 0 0 61 0 1 1 0 6 0 1 0 0 0 1 1 0 0 0 28 1 0 0 0 29 2 0 0 0 8 32 1 0 0 0 18 1 1 0 0 53 1 1 0 0 1 2 1 0 6 0 1 2 0 0 61 0 1 2 1 0 6 0 1 2 0 0 61 0 1 4 1 6 58 0 6 6 1 2 0 6 58 0 1 3 0 6 58 0 6 1 3 0 6 0 30 6 1 2 0 6 0 30 1 1 0 11 0 1 2 1 30 6 0 1 3 1 30 6 0 30 1 2 0 30 61 0 1 1 0 25 0 27 1 0 38 0 1 2 1 11 0 0 1 2 0 0 8 6 1 2 0 11 0 8 1 1 5 30 0 31 2 3 0 0 0 1 2 3 0 0 0 1 3 0 0 54 0 0 56 2 3 0 0 0 1 3 0 0 54 0 0 1 1 0 25 0 1 2 1 11 6 0 51 1 5 30 0 1 2 3 0 0 0 1 2 0 0 66 0 1 3 0 0 58 0 0 1 2 0 0 66 0 1 1 0 0 6 1 2 0 11 0 8 1 1 0 25 0 1 1 0 11 0 1 1 1 48 0 50 2 0 0 0 8 1 1 0 6 0 1 3 0 0 6 0 30 1 3 0 0 0 0 30 1 3 0 0 0 0 30 1 3 0 0 6 0 30 1 1 0 69 0 1 2 0 11 30 0 1 1 1 68 0 1 2 0 0 0 8 1 1 0 6 0 13 2 0 70 61 0 1 2 0 0 0 6 1 1 0 11 0 1 2 0 11 61 0 1 3 6 0 0 6 6 1 3 6 0 0 25 25 1 2 6 0 0 59 1 2 6 0 0 60 1 2 0 11 0 0 12 2 1 11 6 0 1 1 0 25 0 1 1 0 11 0 17 0 0 0 16 2 0 6 0 30 1 3 0 6 0 30 6 1 2 0 0 0 63 1 2 0 6 0 64 1 2 0 0 0 19 20 2 0 6 0 14 15 2 0 6 0 65 1 2 0 30 0 0 1 2 0 0 0 63 1 2 0 0 0 30 1 2 0 0 0 63 1 2 0 0 0 30 1 1 0 11 0 33 1 0 0 0 1 1 0 0 0 1 1 0 8 0 1 1 0 0 0 35 2 1 8 6 0 1 2 0 8 61 0 1 3 0 0 0 0 30 1 1 0 0 0 34 1 2 67 0 1 1 0 0 25 26 2 0 0 0 0 52 2 0 0 0 6 1 1 0 0 38 1 2 0 0 0 6 1 2 0 0 6 0 10 2 0 0 0 0 1 1 1 36 0 45 1 0 38 0 1 2 1 11 0 0 1 2 0 11 61 0 1 2 3 11 0 0 1 2 3 11 0 0 1 2 1 11 0 0 47 2 3 11 0 0 1 2 3 11 0 0 1 1 0 8 0 9)))))) (QUOTE |lookupComplete|))) 
+@
+\section{domain LIST List}
+<<domain LIST List>>=
+)abbrev domain LIST List
+++ Author: Michael Monagan
+++ Date Created: Sep 1987
+++ Change History:
+++ Basic Operations:
+++   \#, append, concat, concat!, cons, construct, copy, elt, elt,
+++   empty, empty?, eq?, first, member?, merge!, mergeSort, minIndex,
+++   nil, null, parts, removeDuplicates!, rest, rest, reverse,
+++   reverse!, setDifference, setIntersection, setUnion, setelt,
+++   setfirst!, setrest!, sort!, split!
+++ Related Constructors: ListFunctions2, ListFunctions3, ListToMap
+++ Also See: IndexList, ListAggregate
+++ AMS Classification:
+++ Keywords: list, index, aggregate, lisp
+++ Description:
+++   \spadtype{List} implements singly-linked lists that are
+++   addressable by indices; the index of the first element
+++   is 1. In addition to the operations provided by
+++   \spadtype{IndexedList}, this constructor provides some
+++   LISP-like functions such as \spadfun{null} and \spadfun{cons}.
+List(S:Type): Exports == Implementation where 
+ LISTMININDEX ==> 1       -- this is the minimum list index
+
+ Exports ==> ListAggregate S with
+  nil             : ()     -> %
+    ++ nil() returns the empty list.
+  null            : %      -> Boolean
+    ++ null(u) tests if list \spad{u} is the
+    ++ empty list.
+  cons            : (S, %) -> %
+    ++ cons(element,u) appends \spad{element} onto the front
+    ++ of list \spad{u} and returns the new list. This new list
+    ++ and the old one will share some structure.
+  append          : (%, %) -> %
+    ++ append(u1,u2) appends the elements of list \spad{u1}
+    ++ onto the front of list \spad{u2}. This new list
+    ++ and \spad{u2} will share some structure.
+  if S has SetCategory then
+    setUnion        : (%, %) -> %
+      ++ setUnion(u1,u2) appends the two lists u1 and u2, then
+      ++ removes all duplicates. The order of elements in the
+      ++ resulting list is unspecified.
+    setIntersection : (%, %) -> %
+      ++ setIntersection(u1,u2) returns a list of the elements
+      ++ that lists \spad{u1} and \spad{u2} have in common.
+      ++ The order of elements in the resulting list is unspecified.
+    setDifference   : (%, %) -> %
+      ++ setDifference(u1,u2) returns a list of the elements
+      ++ of \spad{u1} that are not also in \spad{u2}.
+      ++ The order of elements in the resulting list is unspecified.
+  if S has OpenMath then OpenMath
+
+ Implementation ==>
+   IndexedList(S, LISTMININDEX) add
+      nil()                    == NIL$Lisp
+      null l                   == NULL(l)$Lisp
+      cons(s, l)               == CONS(s, l)$Lisp
+      append(l:%, t:%)         == APPEND(l, t)$Lisp
+
+      if S has OpenMath then
+        writeOMList(dev: OpenMathDevice, x: %): Void ==
+          OMputApp(dev)
+          OMputSymbol(dev, "list1", "list")
+          -- The following didn't compile because the compiler isn't
+          -- convinced that `xval' is a S.  Duhhh! MCD.
+          --for xval in x repeat
+          --  OMwrite(dev, xval, false)
+          while not null x repeat
+            OMwrite(dev,first x,false)
+            x := rest x
+          OMputEndApp(dev)
+
+        OMwrite(x: %): String ==
+          s: String := ""
+          sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
+          dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
+          OMputObject(dev)
+          writeOMList(dev, x)
+          OMputEndObject(dev)
+          OMclose(dev)
+          s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
+          s
+
+        OMwrite(x: %, wholeObj: Boolean): String ==
+          s: String := ""
+          sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
+          dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML)
+          if wholeObj then
+            OMputObject(dev)
+          writeOMList(dev, x)
+          if wholeObj then
+            OMputEndObject(dev)
+          OMclose(dev)
+          s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
+          s
+
+        OMwrite(dev: OpenMathDevice, x: %): Void ==
+          OMputObject(dev)
+          writeOMList(dev, x)
+          OMputEndObject(dev)
+
+        OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
+          if wholeObj then
+            OMputObject(dev)
+          writeOMList(dev, x)
+          if wholeObj then
+            OMputEndObject(dev)
+
+      if S has SetCategory then
+        setUnion(l1:%,l2:%)      == removeDuplicates concat(l1,l2)
+
+        setIntersection(l1:%,l2:%) ==
+          u :% := empty()
+          l1 := removeDuplicates l1
+          while not empty? l1 repeat
+            if member?(first l1,l2) then u := cons(first l1,u)
+            l1 := rest l1
+          u
+
+        setDifference(l1:%,l2:%) ==
+          l1 := removeDuplicates l1
+          lu:% := empty()
+          while not empty? l1 repeat
+            l11:=l1.1
+            if not member?(l11,l2) then lu := concat(l11,lu)
+            l1 := rest l1
+          lu
+
+      if S has ConvertibleTo InputForm then
+        convert(x:%):InputForm ==
+          convert concat(convert("construct"::Symbol)@InputForm,
+                [convert a for a in (x pretend List S)]$List(InputForm))
+
+@
+\section{LIST.lsp BOOTSTRAP} 
+{\bf LIST} depends on a chain of
+files. We need to break this cycle to build the algebra. So we keep a
+cached copy of the translated {\bf LIST} category which we can write
+into the {\bf MID} directory. We compile the lisp code and copy the
+{\bf LIST.o} file to the {\bf OUT} directory.  This is eventually
+forcibly replaced by a recompiled version.
+
+Note that this code is not included in the generated catdef.spad file.
+
+<<LIST.lsp BOOTSTRAP>>=
+
+(|/VERSIONCHECK| 2) 
+
+(PUT (QUOTE |LIST;nil;$;1|) (QUOTE |SPADreplace|) (QUOTE (XLAM NIL NIL))) 
+
+(DEFUN |LIST;nil;$;1| (|$|) NIL) 
+
+(PUT (QUOTE |LIST;null;$B;2|) (QUOTE |SPADreplace|) (QUOTE NULL)) 
+
+(DEFUN |LIST;null;$B;2| (|l| |$|) (NULL |l|)) 
+
+(PUT (QUOTE |LIST;cons;S2$;3|) (QUOTE |SPADreplace|) (QUOTE CONS)) 
+
+(DEFUN |LIST;cons;S2$;3| (|s| |l| |$|) (CONS |s| |l|)) 
+
+(PUT (QUOTE |LIST;append;3$;4|) (QUOTE |SPADreplace|) (QUOTE APPEND)) 
+
+(DEFUN |LIST;append;3$;4| (|l| |t| |$|) (APPEND |l| |t|)) 
+
+(DEFUN |LIST;writeOMList| (|dev| |x| |$|) (SEQ (SPADCALL |dev| (QREFELT |$| 14)) (SPADCALL |dev| "list1" "list" (QREFELT |$| 16)) (SEQ G190 (COND ((NULL (COND ((NULL |x|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (SPADCALL |dev| (|SPADfirst| |x|) (QUOTE NIL) (QREFELT |$| 17)) (EXIT (LETT |x| (CDR |x|) |LIST;writeOMList|))) NIL (GO G190) G191 (EXIT NIL)) (EXIT (SPADCALL |dev| (QREFELT |$| 18))))) 
+
+(DEFUN |LIST;OMwrite;$S;6| (|x| |$|) (PROG (|sp| |dev| |s|) (RETURN (SEQ (LETT |s| "" |LIST;OMwrite;$S;6|) (LETT |sp| (|OM-STRINGTOSTRINGPTR| |s|) |LIST;OMwrite;$S;6|) (LETT |dev| (SPADCALL |sp| (SPADCALL (QREFELT |$| 20)) (QREFELT |$| 21)) |LIST;OMwrite;$S;6|) (SPADCALL |dev| (QREFELT |$| 22)) (|LIST;writeOMList| |dev| |x| |$|) (SPADCALL |dev| (QREFELT |$| 23)) (SPADCALL |dev| (QREFELT |$| 24)) (LETT |s| (|OM-STRINGPTRTOSTRING| |sp|) |LIST;OMwrite;$S;6|) (EXIT |s|))))) 
+
+(DEFUN |LIST;OMwrite;$BS;7| (|x| |wholeObj| |$|) (PROG (|sp| |dev| |s|) (RETURN (SEQ (LETT |s| "" |LIST;OMwrite;$BS;7|) (LETT |sp| (|OM-STRINGTOSTRINGPTR| |s|) |LIST;OMwrite;$BS;7|) (LETT |dev| (SPADCALL |sp| (SPADCALL (QREFELT |$| 20)) (QREFELT |$| 21)) |LIST;OMwrite;$BS;7|) (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 22)))) (|LIST;writeOMList| |dev| |x| |$|) (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 23)))) (SPADCALL |dev| (QREFELT |$| 24)) (LETT |s| (|OM-STRINGPTRTOSTRING| |sp|) |LIST;OMwrite;$BS;7|) (EXIT |s|))))) 
+
+(DEFUN |LIST;OMwrite;Omd$V;8| (|dev| |x| |$|) (SEQ (SPADCALL |dev| (QREFELT |$| 22)) (|LIST;writeOMList| |dev| |x| |$|) (EXIT (SPADCALL |dev| (QREFELT |$| 23))))) 
+
+(DEFUN |LIST;OMwrite;Omd$BV;9| (|dev| |x| |wholeObj| |$|) (SEQ (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 22)))) (|LIST;writeOMList| |dev| |x| |$|) (EXIT (COND (|wholeObj| (SPADCALL |dev| (QREFELT |$| 23))))))) 
+
+(DEFUN |LIST;setUnion;3$;10| (|l1| |l2| |$|) (SPADCALL (SPADCALL |l1| |l2| (QREFELT |$| 29)) (QREFELT |$| 30))) 
+
+(DEFUN |LIST;setIntersection;3$;11| (|l1| |l2| |$|) (PROG (|u|) (RETURN (SEQ (LETT |u| NIL |LIST;setIntersection;3$;11|) (LETT |l1| (SPADCALL |l1| (QREFELT |$| 30)) |LIST;setIntersection;3$;11|) (SEQ G190 (COND ((NULL (COND ((NULL |l1|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (COND ((SPADCALL (|SPADfirst| |l1|) |l2| (QREFELT |$| 32)) (LETT |u| (CONS (|SPADfirst| |l1|) |u|) |LIST;setIntersection;3$;11|))) (EXIT (LETT |l1| (CDR |l1|) |LIST;setIntersection;3$;11|))) NIL (GO G190) G191 (EXIT NIL)) (EXIT |u|))))) 
+
+(DEFUN |LIST;setDifference;3$;12| (|l1| |l2| |$|) (PROG (|l11| |lu|) (RETURN (SEQ (LETT |l1| (SPADCALL |l1| (QREFELT |$| 30)) |LIST;setDifference;3$;12|) (LETT |lu| NIL |LIST;setDifference;3$;12|) (SEQ G190 (COND ((NULL (COND ((NULL |l1|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) (GO G191))) (SEQ (LETT |l11| (SPADCALL |l1| 1 (QREFELT |$| 35)) |LIST;setDifference;3$;12|) (COND ((NULL (SPADCALL |l11| |l2| (QREFELT |$| 32))) (LETT |lu| (CONS |l11| |lu|) |LIST;setDifference;3$;12|))) (EXIT (LETT |l1| (CDR |l1|) |LIST;setDifference;3$;12|))) NIL (GO G190) G191 (EXIT NIL)) (EXIT |lu|))))) 
+
+(DEFUN |LIST;convert;$If;13| (|x| |$|) (PROG (#1=#:G102544 |a| #2=#:G102545) (RETURN (SEQ (SPADCALL (CONS (SPADCALL (SPADCALL "construct" (QREFELT |$| 38)) (QREFELT |$| 40)) (PROGN (LETT #1# NIL |LIST;convert;$If;13|) (SEQ (LETT |a| NIL |LIST;convert;$If;13|) (LETT #2# |x| |LIST;convert;$If;13|) G190 (COND ((OR (ATOM #2#) (PROGN (LETT |a| (CAR #2#) |LIST;convert;$If;13|) NIL)) (GO G191))) (SEQ (EXIT (LETT #1# (CONS (SPADCALL |a| (QREFELT |$| 41)) #1#) |LIST;convert;$If;13|))) (LETT #2# (CDR #2#) |LIST;convert;$If;13|) (GO G190) G191 (EXIT (NREVERSE0 #1#))))) (QREFELT |$| 43)))))) 
+
+(DEFUN |List| (#1=#:G102555) (PROG NIL (RETURN (PROG (#2=#:G102556) (RETURN (COND ((LETT #2# (|lassocShiftWithFunction| (LIST (|devaluate| #1#)) (HGET |$ConstructorCache| (QUOTE |List|)) (QUOTE |domainEqualList|)) |List|) (|CDRwithIncrement| #2#)) ((QUOTE T) (|UNWIND-PROTECT| (PROG1 (|List;| #1#) (LETT #2# T |List|)) (COND ((NOT #2#) (HREM |$ConstructorCache| (QUOTE |List|)))))))))))) 
+
+(DEFUN |List;| (|#1|) (PROG (|DV$1| |dv$| |$| #1=#:G102554 |pv$|) (RETURN (PROGN (LETT |DV$1| (|devaluate| |#1|) . #2=(|List|)) (LETT |dv$| (LIST (QUOTE |List|) |DV$1|) . #2#) (LETT |$| (GETREFV 62) . #2#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 (LIST (|HasCategory| |#1| (QUOTE (|SetCategory|))) (|HasCategory| |#1| (QUOTE (|ConvertibleTo| (|InputForm|)))) (LETT #1# (|HasCategory| |#1| (QUOTE (|OrderedSet|))) . #2#) (OR #1# (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (|HasCategory| |#1| (QUOTE (|OpenMath|))) (|HasCategory| (|Integer|) (QUOTE (|OrderedSet|))) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (OR (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) #1#) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|))))))) . #2#)) (|haddProp| |$ConstructorCache| (QUOTE |List|) (LIST |DV$1|) (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 |#1|) (COND ((|testBitVector| |pv$| 5) (PROGN (QSETREFV |$| 25 (CONS (|dispatchFunction| |LIST;OMwrite;$S;6|) |$|)) (QSETREFV |$| 26 (CONS (|dispatchFunction| |LIST;OMwrite;$BS;7|) |$|)) (QSETREFV |$| 27 (CONS (|dispatchFunction| |LIST;OMwrite;Omd$V;8|) |$|)) (QSETREFV |$| 28 (CONS (|dispatchFunction| |LIST;OMwrite;Omd$BV;9|) |$|))))) (COND ((|testBitVector| |pv$| 1) (PROGN (QSETREFV |$| 31 (CONS (|dispatchFunction| |LIST;setUnion;3$;10|) |$|)) (QSETREFV |$| 33 (CONS (|dispatchFunction| |LIST;setIntersection;3$;11|) |$|)) (QSETREFV |$| 36 (CONS (|dispatchFunction| |LIST;setDifference;3$;12|) |$|))))) (COND ((|testBitVector| |pv$| 2) (QSETREFV |$| 44 (CONS (|dispatchFunction| |LIST;convert;$If;13|) |$|)))) |$|)))) 
+
+(MAKEPROP (QUOTE |List|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL (|IndexedList| 6 (NRTEVAL 1)) (|local| |#1|) |LIST;nil;$;1| (|Boolean|) |LIST;null;$B;2| |LIST;cons;S2$;3| |LIST;append;3$;4| (|Void|) (|OpenMathDevice|) (0 . |OMputApp|) (|String|) (5 . |OMputSymbol|) (12 . |OMwrite|) (19 . |OMputEndApp|) (|OpenMathEncoding|) (24 . |OMencodingXML|) (28 . |OMopenString|) (34 . |OMputObject|) (39 . |OMputEndObject|) (44 . |OMclose|) (49 . |OMwrite|) (54 . |OMwrite|) (60 . |OMwrite|) (66 . |OMwrite|) (73 . |concat|) (79 . |removeDuplicates|) (84 . |setUnion|) (90 . |member?|) (96 . |setIntersection|) (|Integer|) (102 . |elt|) (108 . |setDifference|) (|Symbol|) (114 . |coerce|) (|InputForm|) (119 . |convert|) (124 . |convert|) (|List| |$|) (129 . |convert|) (134 . |convert|) (|Mapping| 6 6 6) (|NonNegativeInteger|) (|List| 6) (|List| 49) (|Equation| 6) (|Mapping| 8 6) (|Mapping| 8 6 6) (|UniversalSegment| 34) (QUOTE "last") (QUOTE "rest") (QUOTE "first") (QUOTE "value") (|Mapping| 6 6) (|SingleInteger|) (|OutputForm|) (|List| 34) (|Union| 6 (QUOTE "failed")))) (QUOTE #(|setUnion| 139 |setIntersection| 145 |setDifference| 151 |removeDuplicates| 157 |null| 162 |nil| 167 |member?| 171 |elt| 177 |convert| 183 |cons| 188 |concat| 194 |append| 200 |OMwrite| 206)) (QUOTE ((|shallowlyMutable| . 0) (|finiteAggregate| . 0))) (CONS (|makeByteWordVec2| 8 (QUOTE (0 0 0 0 0 0 0 0 0 0 3 0 0 8 4 0 0 8 1 2 4 5))) (CONS (QUOTE #(|ListAggregate&| |StreamAggregate&| |ExtensibleLinearAggregate&| |FiniteLinearAggregate&| |UnaryRecursiveAggregate&| |LinearAggregate&| |RecursiveAggregate&| |IndexedAggregate&| |Collection&| |HomogeneousAggregate&| |OrderedSet&| |Aggregate&| |EltableAggregate&| |Evalable&| |SetCategory&| NIL NIL |InnerEvalable&| NIL NIL |BasicType&| NIL)) (CONS (QUOTE #((|ListAggregate| 6) (|StreamAggregate| 6) (|ExtensibleLinearAggregate| 6) (|FiniteLinearAggregate| 6) (|UnaryRecursiveAggregate| 6) (|LinearAggregate| 6) (|RecursiveAggregate| 6) (|IndexedAggregate| 34 6) (|Collection| 6) (|HomogeneousAggregate| 6) (|OrderedSet|) (|Aggregate|) (|EltableAggregate| 34 6) (|Evalable| 6) (|SetCategory|) (|Type|) (|Eltable| 34 6) (|InnerEvalable| 6 6) (|CoercibleTo| 59) (|ConvertibleTo| 39) (|BasicType|) (|OpenMath|))) (|makeByteWordVec2| 44 (QUOTE (1 13 12 0 14 3 13 12 0 15 15 16 3 6 12 13 0 8 17 1 13 12 0 18 0 19 0 20 2 13 0 15 19 21 1 13 12 0 22 1 13 12 0 23 1 13 12 0 24 1 0 15 0 25 2 0 15 0 8 26 2 0 12 13 0 27 3 0 12 13 0 8 28 2 0 0 0 0 29 1 0 0 0 30 2 0 0 0 0 31 2 0 8 6 0 32 2 0 0 0 0 33 2 0 6 0 34 35 2 0 0 0 0 36 1 37 0 15 38 1 39 0 37 40 1 6 39 0 41 1 39 0 42 43 1 0 39 0 44 2 1 0 0 0 31 2 1 0 0 0 33 2 1 0 0 0 36 1 1 0 0 30 1 0 8 0 9 0 0 0 7 2 1 8 6 0 32 2 0 6 0 34 35 1 2 39 0 44 2 0 0 6 0 10 2 0 0 0 0 29 2 0 0 0 0 11 3 5 12 13 0 8 28 2 5 12 13 0 27 1 5 15 0 25 2 5 15 0 8 26)))))) (QUOTE |lookupIncomplete|))) 
+@
+\section{package LIST2 ListFunctions2}
+<<package LIST2 ListFunctions2>>=
+)abbrev package LIST2 ListFunctions2
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations: map, reduce, scan
+++ Related Constructors: List
+++ Also See: ListFunctions3
+++ AMS Classification:
+++ Keywords: list, aggregate, map, reduce
+++ Description:
+++   \spadtype{ListFunctions2} implements utility functions that
+++   operate on two kinds of lists, each with a possibly different
+++   type of element.
+ListFunctions2(A:Type, B:Type): public == private where
+  LA     ==> List A
+  LB     ==> List B
+  O2     ==> FiniteLinearAggregateFunctions2(A, LA, B, LB)
+
+  public ==> with
+    scan:    ((A, B) -> B, LA, B) -> LB
+      ++ scan(fn,u,ident) successively uses the binary function
+      ++ \spad{fn} to reduce more and more of list \spad{u}.
+      ++ \spad{ident} is returned if the \spad{u} is empty.
+      ++ The result is a list of the reductions at each step. See
+      ++ \spadfun{reduce} for more information. Examples:
+      ++ \spad{scan(fn,[1,2],0) = [fn(2,fn(1,0)),fn(1,0)]} and
+      ++ \spad{scan(*,[2,3],1) = [2 * 1, 3 * (2 * 1)]}.
+    reduce:  ((A, B) -> B, LA, B) -> B
+      ++ reduce(fn,u,ident) successively uses the binary function
+      ++ \spad{fn} on the elements of list \spad{u} and the result
+      ++ of previous applications. \spad{ident} is returned if the
+      ++ \spad{u} is empty. Note the order of application in
+      ++ the following examples:
+      ++ \spad{reduce(fn,[1,2,3],0) = fn(3,fn(2,fn(1,0)))} and
+      ++ \spad{reduce(*,[2,3],1) = 3 * (2 * 1)}.
+    map:      (A -> B, LA) -> LB
+      ++ map(fn,u) applies \spad{fn} to each element of
+      ++ list \spad{u} and returns a new list with the results.
+      ++ For example \spad{map(square,[1,2,3]) = [1,4,9]}.
+
+  private ==> add
+    map(f, l)       == map(f, l)$O2
+    scan(f, l, b)   == scan(f, l, b)$O2
+    reduce(f, l, b) == reduce(f, l, b)$O2
+
+@
+\section{package LIST3 ListFunctions3}
+<<package LIST3 ListFunctions3>>=
+)abbrev package LIST3 ListFunctions3
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations: map
+++ Related Constructors: List
+++ Also See: ListFunctions2
+++ AMS Classification:
+++ Keywords: list, aggregate, map
+++ Description:
+++   \spadtype{ListFunctions3} implements utility functions that
+++   operate on three kinds of lists, each with a possibly different
+++   type of element.
+ListFunctions3(A:Type, B:Type, C:Type): public == private where
+  LA     ==> List A
+  LB     ==> List B
+  LC     ==> List C
+
+  public ==> with
+    map: ( (A,B)->C, LA, LB) -> LC
+      ++ map(fn,list1, u2) applies the binary function \spad{fn}
+      ++ to corresponding elements of lists \spad{u1} and \spad{u2}
+      ++ and returns a list of the results (in the same order). Thus
+      ++ \spad{map(/,[1,2,3],[4,5,6]) = [1/4,2/4,1/2]}. The computation
+      ++ terminates when the end of either list is reached. That is,
+      ++ the length of the result list is equal to the minimum of the
+      ++ lengths of \spad{u1} and \spad{u2}.
+
+  private ==> add
+    map(fn : (A,B) -> C, la : LA, lb : LB): LC ==
+      empty?(la) or empty?(lb) => empty()$LC
+      concat(fn(first la, first lb), map(fn, rest la, rest lb))
+
+@
+\section{package LIST2MAP ListToMap}
+<<package LIST2MAP ListToMap>>=
+)abbrev package LIST2MAP ListToMap
+++ Author: Manuel Bronstein
+++ Date Created: 22 Mar 1988
+++ Change History:
+++   11 Oct 1989   MB   ?
+++ Basic Operations: match
+++ Related Constructors: List
+++ Also See:
+++ AMS Classification:
+++ Keywords: mapping, list
+++ Description:
+++   \spadtype{ListToMap} allows mappings to be described by a pair of
+++   lists of equal lengths.  The image of an element \spad{x},
+++   which appears in position \spad{n} in the first list, is then
+++   the \spad{n}th element of the second list.  A default value or
+++   default function can be specified to be used when \spad{x}
+++   does not appear in the first list.  In the absence of defaults,
+++   an error will occur in that case.
+ListToMap(A:SetCategory, B:Type): Exports == Implementation where
+  LA  ==> List A
+  LB  ==> List B
+  AB  ==> (A -> B)
+
+  Exports ==> with
+    match: (LA, LB   ) -> AB
+      ++ match(la, lb) creates a map with no default source or target values
+      ++ defined by lists la and lb of equal length.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Error: if la and lb are not of equal length.
+      ++ Note: when this map is applied, an error occurs when
+      ++ applied to a value missing from la.
+    match: (LA, LB, A) -> B
+      ++ match(la, lb, a) creates a map
+      ++ defined by lists la and lb of equal length, where \spad{a} is used
+      ++ as the default source value if the given one is not in \spad{la}.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Error: if la and lb are not of equal length.
+    match: (LA, LB, B)    -> AB
+      ++ match(la, lb, b) creates a map
+      ++ defined by lists la and lb of equal length, where \spad{b} is used
+      ++ as the default target value if the given function argument is
+      ++ not in \spad{la}.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Error: if la and lb are not of equal length.
+    match: (LA, LB, A, B) -> B
+      ++ match(la, lb, a, b) creates a map
+      ++ defined by lists la and lb of equal length.
+      ++ and applies this map to a.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Argument b is the default target value if a is not in la.
+      ++ Error: if la and lb are not of equal length.
+    match: (LA, LB, AB)    -> AB
+      ++ match(la, lb, f) creates a map
+      ++ defined by lists la and lb of equal length.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Argument \spad{f} is used as the
+      ++ function to call when the given function argument is not in
+      ++ \spad{la}.
+      ++ The value returned is f applied to that argument.
+    match: (LA, LB, A, AB) -> B
+      ++ match(la, lb, a, f) creates a map
+      ++ defined by lists la and lb of equal length.
+      ++ and applies this map to a.
+      ++ The target of a source value \spad{x} in la is the
+      ++ value y with the same index lb.
+      ++ Argument \spad{f} is a default function to call if a is not in la.
+      ++ The value returned is then obtained by applying f to argument a.
+
+  Implementation ==> add
+    match(la, lb)             == match(la, lb, #1)
+    match(la:LA, lb:LB, a:A)  == lb.position(a, la)
+    match(la:LA, lb:LB, b:B)  == match(la, lb, #1, b)
+    match(la:LA, lb:LB, f:AB) == match(la, lb, #1, f)
+
+    match(la:LA, lb:LB, a:A, b:B) ==
+      (p := position(a, la)) < minIndex(la) => b
+      lb.p
+
+    match(la:LA, lb:LB, a:A, f:AB) ==
+      (p := position(a, la)) < minIndex(la) => f a
+      lb.p
+
+@
+\section{domain ALIST AssociationList}
+<<domain ALIST AssociationList>>=
+)abbrev domain ALIST AssociationList
+++ Author:
+++ Date Created:
+++ Change History:
+++ Basic Operations: empty, empty?, keys, \#, concat, first, rest,
+++   setrest!, search, setelt, remove!
+++ Related Constructors:
+++ Also See: List
+++ AMS Classification:
+++ Keywords: list, association list
+++ Description:
+++   \spadtype{AssociationList} implements association lists. These
+++   may be viewed as lists of pairs where the first part is a key
+++   and the second is the stored value. For example, the key might
+++   be a string with a persons employee identification number and
+++   the value might be a record with personnel data.
+
+AssociationList(Key:SetCategory, Entry:SetCategory):
+ AssociationListAggregate(Key, Entry) == add
+        Pair ==> Record(key:Key, entry:Entry)
+        Rep := Reference List Pair
+
+        dictionary()            == ref empty()
+        empty()                 == dictionary()
+        empty? t                == empty? deref t
+        entries(t:%):List(Pair) == deref t
+        parts(t:%):List(Pair)   == deref t
+        keys t                  == [k.key for k in deref t]
+        # t                     == # deref t
+        first(t:%):Pair         == first deref t
+        rest t                  == ref rest deref t
+        concat(p:Pair, t:%)     == ref concat(p, deref t)
+        setrest_!(a:%, b:%)     == ref setrest_!(deref a, deref b)
+        setfirst_!(a:%, p:Pair) == setfirst_!(deref a,p)
+        minIndex(a:%):Integer   == minIndex(deref a)
+        maxIndex(a:%):Integer   == maxIndex(deref a)
+
+        search(k, t) ==
+          for r in deref t repeat
+            k = r.key => return(r.entry)
+          "failed"
+
+        latex(a : %) : String ==
+          l : List Pair := entries a
+          s : String := "\left["
+          while not empty?(l) repeat
+            r : Pair := first l
+            l        := rest l
+            s := concat(s, concat(latex r.key, concat(" = ", latex r.entry)$String)$String)$String
+            if not empty?(l) then s := concat(s, ", ")$String
+          concat(s, " \right]")$String
+
+--      assoc(k, l) ==
+--        (r := find(#1.key=k, l)) case "failed" => "failed"
+--        r
+
+        assoc(k, t) ==
+          for r in deref t repeat
+            k = r.key => return r
+          "failed"
+
+        setelt(t:%, k:Key, e:Entry) ==
+          (r := assoc(k, t)) case Pair => (r::Pair).entry := e
+          setref(t, concat([k, e], deref t))
+          e
+
+        remove_!(k:Key, t:%) ==
+          empty?(l := deref t) => "failed"
+          k = first(l).key =>
+            setref(t, rest l)
+            first(l).entry
+          prev := l
+          curr := rest l
+          while not empty? curr and first(curr).key ^= k repeat
+            prev := curr
+            curr := rest curr
+          empty? curr => "failed"
+          setrest_!(prev, rest curr)
+          first(curr).entry
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+--    - Redistributions of source code must retain the above copyright
+--      notice, this list of conditions and the following disclaimer.
+--
+--    - Redistributions in binary form must reproduce the above copyright
+--      notice, this list of conditions and the following disclaimer in
+--      the documentation and/or other materials provided with the
+--      distribution.
+--
+--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--      names of its contributors may be used to endorse or promote products
+--      derived from this software without specific prior written permission.
+--
+--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+@
+<<*>>=
+<<license>>
+
+<<domain ILIST IndexedList>>
+<<domain LIST List>>
+<<package LIST2 ListFunctions2>>
+<<package LIST3 ListFunctions3>>
+<<package LIST2MAP ListToMap>>
+<<domain ALIST AssociationList>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}