(* Copyright (C) 1989, Digital Equipment Corporation *) (* All rights reserved. *) (* See the file COPYRIGHT for a full description. *) (* Last modified on Mon Aug 5 23:18:30 1991 by kalsow *) (* modified on Thu Mar 29 07:39:26 1990 by muller *) (* modified on Thu Sep 14 12:08:00 1989 by ellis *) (* modified on Fri Jun 3 13:58:32 1988 by glassman *) INTERFACE List; (***************************************************************************** Data types and operations for Lisp-like lists This interface provides Lisp-like lists and their most useful operations. Why lists? The list has proven to be an extremely flexible data structure with many powerful operations and acceptable efficiency for many, many applications. Sequences, sets, tables, and other sorts of mappings can all be implemented easily with lists, often with more than enough efficiency for the particular application. See the end of the interface for a detailed introduction. See Sx.def for general operations on symbolic expressions, including reading and printing of lists. See List1.def for extensions to this interface. Index: linked lists; sequences *****************************************************************************) TYPE T = REF Pair; Pair = RECORD first: REFANY; tail: T; END; CompareProc = PROCEDURE (arg, item1, item2: REFANY): [-1..1]; (* The type of client-supplied comparison functions. *) MapProc = PROCEDURE (arg, element: REFANY): REFANY RAISES ANY; (* The type of procedures for mapping over lists. *) WalkProc = PROCEDURE (arg, element: REFANY) RAISES ANY; (* The type of procedures for walking over lists. *) PROCEDURE New (first: REFANY; tail: T ): T RAISES {}; (* Constructs a new list cell (Lisp CONS). *) PROCEDURE List1( x1: REFANY ): T RAISES {}; PROCEDURE List2( x1, x2: REFANY ): T RAISES {}; PROCEDURE List3( x1, x2, x3: REFANY ): T RAISES {}; PROCEDURE List4( x1, x2, x3, x4: REFANY ): T RAISES {}; PROCEDURE List5( x1, x2, x3, x4, x5: REFANY ): T RAISES {}; PROCEDURE List6( x1, x2, x3, x4, x5, x6: REFANY ): T RAISES {}; PROCEDURE List7( x1, x2, x3, x4, x5, x6, x7: REFANY ): T RAISES {}; PROCEDURE List8( x1, x2, x3, x4, x5, x6, x7, x8: REFANY ): T RAISES {}; PROCEDURE List9( x1, x2, x3, x4, x5, x6, x7, x8, x9: REFANY ): T RAISES {}; (* Constructors for convenience: List1( x1 ) = New( x1, NIL ) List2( x1, x2 ) = New( x1, New( x2, NIL ) ) ... *) PROCEDURE Push( VAR(*inOut*) l: T; x: REFANY ) RAISES {}; (* Pushes a new element onto the front of "l", and sets "l" to be the new list. Equivalent to: l := New( x, l ); *) PROCEDURE Pop( VAR(*inOut*) l: T ): REFANY RAISES {}; (* Removes one element from the front of "l", and sets "l" to the new list. Equivalent to: result := l^.first l := l^.tail; *) PROCEDURE Length( l: T ): CARDINAL RAISES {}; (* Returns the length of a list. *) PROCEDURE Tail( l: T ): T RAISES {}; PROCEDURE First( l: T ): REFANY RAISES {}; PROCEDURE Second( l: T ): REFANY RAISES {}; PROCEDURE Third( l: T ): REFANY RAISES {}; PROCEDURE Fourth( l: T ): REFANY RAISES {}; PROCEDURE Fifth( l: T ): REFANY RAISES {}; PROCEDURE Sixth( l: T ): REFANY RAISES {}; (* Procedural accessors of list elements. They're included for completeness and because the operators "^" and "." cannot be applied to general expressions. *) PROCEDURE Nth( l: T; n: INTEGER ): REFANY RAISES {}; (* The nth element of a list; n=0 gets the first element. Undefined if n < 0 or n >= Length( l ). *) PROCEDURE SetNth( l: T; n: CARDINAL; x: REFANY ) RAISES {}; (* Destructively changes the nth element of a list to be x. Undefined if n < 0 or n >= Length( l ). *) PROCEDURE NthTail( l: T; n: INTEGER ): T RAISES {}; (* The result of applying Tail to l n times. Undefined if n < 0 or n >= Length( l ). *) PROCEDURE SetNthTail( l: T; n: CARDINAL; x: T ) RAISES {}; (* Destructively changes the nth tail of a list to be x. Undefined if n < 1 or n >= Length( l ). *) PROCEDURE Last( l: T ): REFANY RAISES {}; (* The last element of l, equivalent to Nth( l, Length( l ) - 1 ). *) PROCEDURE LastTail( l: T ): T RAISES {}; (* The last tail of l, equivalent to NthTail( l, Length( l ) - 1 ). *) PROCEDURE FirstN( l: T; n: INTEGER ): T RAISES {}; (* A new list consisting of the first n elements of l. Undefined if n < 0 or n > Length( l ). *) PROCEDURE Equal( x1: REFANY; x2: REFANY ): BOOLEAN RAISES {}; PROCEDURE EqualQ( x1: REFANY; x2: REFANY ): BOOLEAN RAISES {}; (* Compares two objects for equality. Equal is isomorphic structure comparison in which two lists are equal if their elements are Equal. More precisely, Equal( x1, x2 ) is true iff one of the following is true: x1 = x2 (pointer equality). x1 and x2 are lists of the same length with Equal elements. x1 and x2 are vectors of the same length with Equal elements. x1 and x2 are texts with the exact same characters. x1 and x2 are Ref.Integers and x1^ = x2^. x1 and x2 are Ref.Chars and x1^ = x2^. x1 and x2 are Ref.Booleans and x1^ = x2^. x1 and x2 are Ref.LongReals and x1^ = x2^. x1 is a Ref.Integer and x2 is a Ref.LongReal and LONGFLOAT( x1^ ) = x2^ (or vice versa). EqualQ is pointer equality (Lisp EQ or Modula-2 "="). It is included for consistency and application; normally "=" should be used instead. *) PROCEDURE Compare( arg: REFANY; x1: REFANY; x2: REFANY ): [-1..1]; (* Compares x1 and x2. If x1 and x2 have the same type and are one of the following symbolic expression types: Ref.Integer, Ref.Char, Ref.Boolean, Ref.LongReal, SxSymbol.T, SxModule.T, Text.T, List.T, Ref.Vector then the result is the comparison of x1 and x2. For symbols and modules, the result is the comparison of their full print names. Lists and vectors are compared lexicographically, recursively comparing their elements: (a b c e) < (a b d) (a b c) < (a b c d) [a (45 1) b] < [a (45 2)] NIL comes before anything else. If x1 is a Ref.Integer and x2 a Ref.LongReal (or vice versa), the integer is first converted to a long real and then compared. Otherwise, if x1 and x2 don't have the same type, the result is +1 (this meshes well with Table). The closure "arg" is for use when Compare is passed to procedures such as Sort. *) PROCEDURE CompareQ( arg: REFANY; x1: REFANY; x2: REFANY ): [-1..1]; (* Returns 0 if x1 = x2, +1 otherwise. *) PROCEDURE Member( l: T; x: REFANY ): BOOLEAN RAISES {}; PROCEDURE MemberQ( l: T; x: REFANY ): BOOLEAN RAISES {}; (* Returns true if for some y at the top level of list l, y = x; returns false otherwise. Member tests equality using Equal and MemberQ uses EqualQ. *) PROCEDURE Assoc( l: T; x: REFANY ): T RAISES {}; PROCEDURE AssocQ( l: T; x: REFANY ): T RAISES {}; (* The list l is an association list: a possibly-empty list whose top-level elements are varying-length non-empty lists of the form: (key val1 val2 ... valn) n >= 0. Returns the first such list for which key = x. Assoc tests equality using Equal, and AssocQ uses EqualQ. Returns NIL if no such tuple is found. See also List1.AssocPutD. *) PROCEDURE Append( l1: T; l2: T ): T RAISES {}; PROCEDURE AppendD( l1: T; l2: T ): T RAISES {}; (* Appends two lists together, returning the new list. AppendD doesn't create any new list cells, but it destroys its first argument. *) PROCEDURE Append1( l1: T; x: REFANY ): T RAISES {}; PROCEDURE Append1D( l1: T; x: REFANY ): T RAISES {}; (* Appends an element onto the end of a list, returning the new list. *) PROCEDURE Copy( l: T ): T RAISES {}; PROCEDURE CopyRecursively( l: T ): T RAISES {}; (* Copy returns a copy of a list, where only the top level of the list is copied (the elements are not copied). CopyRecursively recursively copies all the list structure of l. *) PROCEDURE Reverse( l: T ): T RAISES {}; PROCEDURE ReverseD( l: T ): T RAISES {}; (* Reverses a list. *) PROCEDURE Sort( l: T; c: CompareProc := NIL; arg: REFANY := NIL ): T RAISES {}; PROCEDURE SortD( l: T; c: CompareProc := NIL; arg: REFANY := NIL ): T RAISES {}; (* Sorts a list in ascending order; if the CompareProc is NIL, then Compare is used by default. The implementation is time- and cons-efficient but is not stable. *) PROCEDURE FromVector(v: REF ARRAY OF REFANY): T RAISES {}; (* Returns a list of the elements in vector v. *) PROCEDURE ToVector( l: T ): REF ARRAY OF REFANY RAISES {}; (* Returns a new vector containing the elements of list l. *) PROCEDURE Map( l: T; p: MapProc; arg: REFANY := NIL ): T RAISES ANY; (* Applies p to each of the elements of l, returning a list of the results returned by p. The only exceptions raised are those possibly raised by p. *) PROCEDURE Walk( l: T; p: WalkProc; arg: REFANY := NIL ) RAISES ANY; (* Applies p to each of the elements of l in turn. The only exceptions raised are those possibly raised by p. *) PROCEDURE Hash( arg: REFANY; x: REFANY ): INTEGER; (* Returns an integer suitable for use by hashing functions, computed from the contents of "x" such that Hash( x ) = Hash( y ) if Equal( x, y ). Hash is typically used in conjunction with Equal or Compare. Because Hash recursively examines the contents of lists and vectors, it might not be very fast. The closure "arg" is for use when Hash is passed to procedures such as Table.New. *) PROCEDURE HashQ( arg: REFANY; x: REFANY ): INTEGER; (* Returns an integer suitable for use by hashing functions, such that Hash( x ) = Hash( y ) if x = y (but not necessarily if Equal( x, y )). Currently: Hash( x ) = LOOPHOLE( x, INTEGER ); HashQ is much faster than Hash because it does not recursively examine the contents of "x". HashQ is typically used in conjunction with EqualQ (=) or CompareQ. *) (****************************************************************************** Sets Implemented As Lists The following procedures provide set operations, where a "set" is implemented as a possibly-empty list of elements with no duplicates. The binary operations generally take time O( |l1| * |l2| ), where |l1| and |l2| are the lengths of the arguments. Thus these procedures are only appropriate either where the lists are small (tens of items or fewer) or where efficiency doesn't matter much. As a convenience, arguments may contain duplicates, but the result would be the same as if there were no duplicates. Except where noted, the elements of results have the same ordering as in the arguments. For example, Union( l1, l2 ) = NoDuplicates( Append( l1, l2 ) ) (but Union is a little more efficient). Though not neccessary for a formal definition of unordered set, this ordering guarantee has turned out to be very useful in practice, especially where an object doubles both as an ordered sequence and as a set. See Member above. ******************************************************************************) PROCEDURE NoDuplicates( l: T ): T RAISES {}; PROCEDURE NoDuplicatesQ( l: T ): T RAISES {}; (* Returns l with all the duplicate elements removed. *) PROCEDURE Union( l1: T; l2: T ): T RAISES {}; PROCEDURE UnionQ( l1: T; l2: T ): T RAISES {}; (* Returns the union of l1 and l2. *) PROCEDURE Union1( l: T; x: REFANY ): T RAISES {}; PROCEDURE Union1Q( l: T; x: REFANY ): T RAISES {}; (* Returns the union of l with the singleton set {x}. Efficiency wart: Union1/Q/F doesn't preserve order -- if x is added, it is added at the front. Use Union( l, List1( x ) ) if you want order preserved. *) PROCEDURE Intersection( l1: T; l2: T ): T RAISES {}; PROCEDURE IntersectionQ( l1: T; l2: T ): T RAISES {}; (* Returns the intersection of l1 and l2. *) PROCEDURE Difference( l1: T; l2: T ): T RAISES {}; PROCEDURE DifferenceQ( l1: T; l2: T ): T RAISES {}; (* Returns all elements in l1 that are not contained in l2. *) PROCEDURE Delete( l: T; x: REFANY ): T RAISES {}; PROCEDURE DeleteQ( l: T; x: REFANY ): T RAISES {}; (* Returns all the elements of l that are not Equal/= to x. *) PROCEDURE Subset( l1: T; l2: T ): BOOLEAN RAISES {}; PROCEDURE SubsetQ( l1: T; l2: T ): BOOLEAN RAISES {}; (* Returns true iff l2 is a subset of l1. *) PROCEDURE ParWalk (l: T; p: WalkProc; arg: REFANY := NIL ) RAISES ANY; (*| Same as Walk, except each p is forked. This procedure does not return until all p's have been joined. *) PROCEDURE AssocPutD( l: T; key: REFANY; valueTail: T ): T RAISES {}; PROCEDURE AssocQPutD( l: T; key: REFANY; valueTail: T ): T RAISES {}; (*| The list l has the same form as in Assoc, a possibly empty list whose elements are tuples of the form: (key val1 val2 ... valn) n >= 0 AssocPut finds the first such tuple whose key is Equal to "key", and destructively replaces the tail of the tuple with "valueTail". E.g. if "valueTail" has the form (val1' ... valm') m > = 0 then the tuple is mutated to be: (key val1' ... valm') and "l" is returned. If there is no tuple containing "key", then a new tuple is added to the front of l and the new list returned. AssocQPutD uses EqualQ instead of Equal. "valueTail" is never modified. *) END List. (****************************************************************************** Details of this Interface Why use lists? An oft-overlooked property of Lisp lists is that they partially make up for the lack of more powerful polymorphism of the sort found in Smalltalk and similar languages. One data structure, List, can be manipulated first as a sequence, then as a set, then as a table, using a small number of primitives. The opportunities for reusability of packages increase dramatically if a single data structure is used to represent sequences, tables, sets. I've included the most common list operations that I've found useful in "systems"-type applications, though I'm sure many useful ones are missing. See the symbolic expression package "sx" (Sx.def) for reading and printing general symbolic expressions (which include lists and symbols). Because Modula-2 doesn't provide inline procedures yet (if ever), the normal method for accessing the front of a list "l" is: l^.first (Lisp CAR) l^.tail (Lisp CDR) Thus, unlike many Lisps, the first and tail of NIL are undefined. Also unlike Lisp, the tail of a list must always be of type List. That is, in Lisp terms, all lists are "proper". This avoids the necessity for NARROWing when enumerating the elements of a list. In addition to Lists, some of the procedures in this interface also recognize the symbolic expression ref types: Ref.Integer, Ref.Char, Ref.Boolean, Ref.LongReal, Text.T, SxSymbol.T, SxModule.T, and Rev.Vector. For example, Equal knows how to compare objects of these types. Destruction: Operations are normally non-destructive (they don't affect their arguments). Destructive operations are suffixed with a "D", e.g. ReverseD reverses a list destructively, modifying the list cells of the argument. Destructive operations are more efficient because they reuse the list cells of the arguments instead of allocating new ones, but they are also dangerous for precisely the same reason. Comparisons: Operations invoking comparison normally use Equal (isomorphic structure comparison of lists, texts, integers, etc.). Operations using EqualQ (pointer equality, Lisp EQ, Modula-2 "=") are suffixed with "Q" and are generally faster because they avoid calling Equal for each comparison. For example, Member tests for list membership using Equal, MemberQ using EqualQ. Order of arguments: I've tried for consistent ordering, using the object-style now in fashion in Modula-2+ T, Scheme, etc. This ordering often differs from more traditional Lisps. Exceptions: Generally, no exceptions are raised by this interface, except System.Fail. Specifically, dereferencing of NIL by operations not expecting NIL will be a common cause of Fail. Walk and Map are two exceptions to this rule. ******************************************************************************)