klisp

an open source interpreter for the Kernel Programming Language.
git clone http://git.hanabi.in/repos/klisp.git
Log | Files | Refs | README

pairs_lists.texi (20495B)


      1 @c -*-texinfo-*-
      2 @setfilename ../src/pairs_lists
      3 
      4 @node Pairs and lists, Environments, Control, Top
      5 @comment  node-name,  next,  previous,  up
      6 
      7 @chapter Pairs and lists
      8 @cindex pairs
      9 @cindex nil
     10 @cindex empty list
     11 @cindex lists
     12 
     13 A pair is an object that refers to two other objects, called its car
     14 and cdr.  The Kernel data type pair is encapsulated.
     15 
     16   The null data type consists of a single immutable value, called nil
     17 or the empty list and having external representation @code{()}, with
     18 or without whitespace between the parentheses. It is immutable, and
     19 the null type is encapsulated.
     20 
     21   If @code{a} and @code{d} are external representations of
     22 respectively the car and cdr of a pair @code{p}, then @code{(a . d)}
     23 is an external representation of @code{p}. If the cdr of @code{p} is
     24 nil, then @code{(a)} is also an external representation of
     25 @code{p}. If the cdr of @code{p} is a pair @code{p2}, and @code{(r)}
     26 is an external representation of @code{p2}, then @code{(a r)} is an
     27 external representation of @code{p}.
     28 @c add xref for write
     29   When a pair is output (as by write), an external representation with
     30 the fewest parentheses is used; in the case of a finite list, only one
     31 set of parentheses is required beyond those used in representing the
     32 elements of the list. For example, an object with external
     33 representation @code{(1 . (2 . (3 . ())))} would be output using,
     34 modulo whitespace, external representation @code{(1 2 3)}.
     35 
     36 @deffn Applicative pair? (pair? . objects)
     37   The primitive type predicate for type pair.  @code{pair?} returns
     38 true iff all the objects in @code{objects} are of type pair.
     39 @end deffn
     40 
     41 @deffn Applicative null? (null? . objects)
     42   The primitive type predicate for type null.  @code{null?} returns
     43 true iff all the objects in @code{objects} are of type null.
     44 @end deffn
     45 
     46 @deffn Applicative immutable-pair? (immutable-pair? objects)
     47 @deffnx Applicative mutable-pair? (mutable-pair? objects)
     48 The primitive type predicates for types immutable pair and mutable
     49 pair.  These return true iff all the objects in @code{objects} are of
     50 type immutable pair or mutable pair respectively.
     51 
     52 SOURCE NOTE: these aren't provided in the Kernel report, but added for
     53 convenience.  These can be implemented in standard kernel by using guards.
     54 @end deffn
     55 
     56 @deffn Applicative cons (cons object1 object2)
     57   A new mutable pair object is constructed and returned, whose car and
     58 cdr referents are respectively @code{object1} and @code{object2}.  No
     59 two objects returned by different calls to cons are @code{eq?} to each
     60 other.
     61 @end deffn
     62 
     63 @deffn Applicative set-car! (set-car! pair object)
     64 @deffnx Applicative set-cdr! (set-cdr! pair object)
     65   @code{pair} should be a mutable pair.
     66   
     67   These applicatives set the referent of, respectively, the car
     68 reference or the cdr reference of @code{pair} to @code{object}.  The
     69 result of the expression is inert.
     70 @end deffn
     71 
     72 @deffn Applicative copy-es-immutable! (copy-es-immutable object)
     73   The short description of this applicative is that it returns an object
     74 @code{equal?} to @code{object} with an immutable evaluation structure. The
     75 ``-es-'' in the name is short for ``evaluation structure''.  
     76 
     77 @c TODO move the evaluation structure description to the intro
     78   The evaluation structure of an object @code{o} is defined to be the
     79 set of all pairs that can be reached by following chains of references
     80 from @code{o} without ever passing through a non-pair object. The
     81 evaluation structure of a non-pair object is empty.  
     82 
     83   If @code{object} is not a pair, the applicative returns @code{object}.
     84 Otherwise (if @code{object} is a pair), the applicative returns an
     85 immutable pair whose car and cdr would be suitable results for
     86 @code{(copy-es-immutable (car object))} and @code{(copy-es-immutable
     87 (cdr object))}, respectively.  Further, the evaluation structure of
     88 @c TODO add xref for isomorphic (and add isomorphic to the intro)
     89 the returned value is isomorphic to that of @code{object} at the time
     90 of copying, with corresponding non-pair referents being @code{eq?}.
     91 
     92   NOTE: In Kernel it's undefined whether immutable pairs are copied or
     93 left ``as is'' in the result.  klisp doesn't copy immutable pairs, but
     94 that behaviour should not be depended upon.
     95 @end deffn
     96 
     97 @deffn Applicative list (list . objects)
     98 The @code{list} applicative returns @code{objects}.
     99 
    100   The underlying operative of @code{list} returns its undifferentiated
    101 operand tree, regardless of whether that tree is or is not a list.  
    102 @end deffn
    103 
    104 @deffn Applicative list* (list* . objects)
    105 @code{objects} should be a finite nonempty list of arguments.
    106 
    107   The following equivalences hold: 
    108 @example
    109 (list* arg1) @equiv{} arg1 
    110 (list* arg1 arg2 . args) @equiv{} (cons arg1 (list* arg2 . args))
    111 @end example
    112 @end deffn
    113 
    114 @deffn Applicative car (car pair)
    115 @deffnx Applicative cdr (cdr pair)
    116 These applicatives return, respectively, the car and cdr of @code{pair}.
    117 @end deffn
    118 @deffn Applicative caar (caar pair)
    119 @deffnx Applicative cadr (cadr pair)
    120 @deffnx Applicative cdar (cdar pair)
    121 @deffnx Applicative cddr (cddr pair)
    122 @deffnx Applicative caaar (caaar pair)
    123 @deffnx Applicative caadr (caadr pair)
    124 @deffnx Applicative cadar (cadar pair)
    125 @deffnx Applicative caddr (caddr pair)
    126 @deffnx Applicative cdaar (cdaar pair)
    127 @deffnx Applicative cdadr (cdadr pair)
    128 @deffnx Applicative cddar (cddar pair)
    129 @deffnx Applicative cdddr (cdddr pair)
    130 @deffnx Applicative caaaar (caaaar pair)
    131 @deffnx Applicative caaadr (caaadr pair)
    132 @deffnx Applicative caadar (caadar pair)
    133 @deffnx Applicative caaddr (caaddr pair)
    134 @deffnx Applicative cadaar (cadaar pair)
    135 @deffnx Applicative cadadr (cadadr pair)
    136 @deffnx Applicative caddar (caddar pair)
    137 @deffnx Applicative cadddr (cadddr pair)
    138 @deffnx Applicative cdaaar (cdaaar pair)
    139 @deffnx Applicative cdaadr (cdaadr pair)
    140 @deffnx Applicative cdadar (cdadar pair)
    141 @deffnx Applicative cdaddr (cdaddr pair)
    142 @deffnx Applicative cddaar (cddaar pair)
    143 @deffnx Applicative cddadr (cddadr pair)
    144 @deffnx Applicative cdddar (cdddar pair)
    145 @deffnx Applicative cddddr (cddddr pair)
    146 
    147 @c TODO add note about pronunciation
    148 These applicatives are compositions of @code{car} and @code{cdr}, with
    149 the ``a’s'' and ``d’s'' in the same order as they would appear if all
    150 the individual ``car’s'' and ``cdr’s'' were written out in prefix
    151 order.  Arbitrary compositions up to four deep are provided. There are
    152 twenty-eight of these applicatives in all.
    153 @end deffn
    154 
    155 @deffn Applicative make-list (make-list length [fill])
    156   @code{length} shoulde be an exact non-negative integer.
    157 
    158   Applicative @code{make-list} creates a new mutable acyclic list of
    159 length @code{length}, with all pairs having @code{fill} in their
    160 cars.  If no value is provided for @code{fill}, @code{#inert} is used.
    161 
    162 SOURCE NOTE: this is taken from r7rs.
    163 @end deffn
    164 
    165 @deffn Applicative list-copy (list-copy list)
    166 Applicative @code{list-copy} creates a new mutable copy of
    167 @code{list}.  That is, the returned list has the same list metrics as
    168 @code{list} and the cars in the returned list are initially @code{eq?}
    169 to the corresponding cars in @code{list}.
    170 
    171 SOURCE NOTE: this is taken from r7rs.
    172 @end deffn
    173 
    174 @deffn Applicative reverse (reverse list)
    175 @code{list} should be an acyclic list.
    176 
    177 Applicative @code{reverse} makes a mutable copy of list but with the
    178 reverse order.  That is, the returned list has the same number of
    179 pairs as @code{list} and the cars in the returned list are initially
    180 @code{eq?} to the corresponding cars in @code{list} but starting from
    181 the end and going backwards.
    182 
    183 SOURCE NOTE: this is taken from r7rs.
    184 @end deffn
    185 
    186 @deffn Applicative get-list-metrics (get-list-metrics object)
    187 @c TODO move definition of improper list to intro, xref data structure
    188   By definition, an improper list is a data structure whose objects
    189 are its start together with all objects reachable from the start by
    190 following the cdr references of pairs, and whose internal references
    191 are just the cdr references of its pairs.  Every object, of whatever
    192 type, is the start of an improper list.  If the start is not a pair,
    193 the improper list consists of just that object.  The acyclic prefix
    194 length of an improper list @code{L} is the number of pairs of @code{L}
    195 that a naive traversal of @code{L} would visit only once. The cycle
    196 length of @code{L} is the number of pairs of @code{L} that a naive
    197 traversal would visit repeatedly. Two improper lists are structurally
    198 @c TODO add xref to isomorphic
    199 isomorphic iff they have the same acyclic prefix length and cycle
    200 length and, if they are terminated by non-pair objects rather than by
    201 cycles, the non-pair objects have the same type.  Applicative
    202 @code{get-list-metrics} constructs and returns a list of exact
    203 integers of the form @code{(p n a c)}, where @code{p}, @code{n},
    204 @code{a}, and @code{c} are, respectively, the number of pairs in, the
    205 number of nil objects in, the acyclic prefix length of, and the cycle
    206 length of, the improper list starting with @code{object}. @code{n} is
    207 either @code{0} or @code{1}, @code{a + c = p}, and @code{n} and
    208 @code{c} cannot both be non-zero. If @code{c = 0}, the improper list
    209 is acyclic; if @code{n = 1}, the improper list is a finite list; if
    210 @code{n = c = 0}, the improper list is not a list; if @code{a = c =
    211 0}, @code{object} is not a pair.
    212 @end deffn
    213 
    214 @deffn Applicative list-tail (list-tail object k)
    215 @code{object} must be the start of an improper list containing at
    216 least @code{k} pairs.
    217 
    218   The @code{list-tail} applicative follows @code{k} cdr references
    219 starting from @code{object}.
    220 
    221 The following equivalences hold:
    222 @example
    223 (list-tail object 0) @equiv{} object
    224 (list-tail object (+ k 1)) @equiv{} (list-tail (cdr object) k)
    225 @end example
    226 @end deffn
    227 
    228 @deffn Applicative encycle! (encycle! object k1 k2)
    229   The improper list starting at @code{object} must contain at least
    230 @code{k1 + k2} pairs.
    231 
    232   If @code{k2 = 0}, the applicative does nothing. If @code{k2 > 0},
    233 the applicative mutates the improper list starting at @code{object} to
    234 have acyclic prefix length @code{k1} and cycle length @code{k2}, by
    235 setting the cdr of the @code{(k1+k2)}th pair in the list to refer to
    236 the @code{(k1 + 1)}th pair in the list.  The result returned by
    237 @code{encycle!} is inert.
    238 @end deffn
    239 
    240 @deffn Applicative map (map applicative . lists)
    241   @code{lists} must be a nonempty list of lists; if there are two or
    242 @c TODO add xref to length
    243 more, they must all have the same length. 
    244 
    245   The map applicative applies @code{applicative} element-wise to the
    246 elements of the lists in lists (i.e., applies it to a list of the
    247 first elements of the lists, to a list of the second elements of the
    248 lists, etc.), using the dynamic environment from which map was called,
    249 and returns a list of the results, in order. The applications may be
    250 performed in any order, as long as their results occur in the
    251 resultant list in the order of their arguments in the original lists.
    252 If @code{lists} is a cyclic list, each argument list to which
    253 @c TODO xref to ismorphic
    254 @code{applicative} is applied is structurally isomorphic to @code{lists}.  If
    255 any of the elements of @code{lists} is a cyclic list, they all must
    256 be, or they wouldn’t all have the same length.  Let @code{a1...an} be
    257 their acyclic prefix lengths, and @code{c1...cn} be their cycle
    258 lengths.  The acyclic prefix length @code{a} of the resultant list
    259 will be the maximum of the @code{ak}, while the cycle length @code{c}
    260 of the resultant list will be the least common multiple of the
    261 @code{ck}.  In the construction of the result, @code{applicative} is
    262 called exactly @code{a + c} times.
    263 @end deffn
    264 
    265 @deffn Applicative length (length object)
    266 @c TODO xref improper-list
    267   Applicative @code{length} returns the (exact) improper-list length
    268 of @code{object}.  That is, it returns the number of consecutive cdr
    269 references that can be followed starting from @code{object}.  If
    270 @code{object} is not a pair, it returns zero; if @code{object} is a
    271 cyclic list, it returns positive infinity.
    272 @end deffn
    273 
    274 @deffn Applicative list-ref (list-ref object k)
    275   The @code{list-ref} applicative returns the @code{car} of the object
    276 obtained by following @code{k} cdr references starting from
    277 @code{object}.
    278 
    279 NOTE: In the current report, object is required to be a list. In
    280 klisp, for now, we prefer the behaviour presented here, as it is more
    281 in line with the applicative @code{list-tail}.  That is, we define
    282 @code{list-ref} by the following equivalence:
    283 @example
    284 (list-ref object k) @equiv{} (car (list-tail object k))
    285 @end example
    286 @end deffn
    287 
    288 @deffn Applicative append (append . lists)
    289   Here, all the elements of @code{lists} except the last element (if
    290 any) must be acyclic lists.  The @code{append} applicative returns a
    291 freshly allocated list of the elements of all the specified
    292 @code{lists}, in order, except that if there is a last specified
    293 element of @code{lists}, it is not copied, but is simply referenced by
    294 the cdr of the preceding pair (if any) in the resultant list.  If
    295 @code{lists} is cyclic, the cycle of the result list consists of just
    296 the elements of the lists specified in the cycle in @code{lists}. In
    297 this case, the acyclic prefix length of the result is the sum of the
    298 lengths of the lists specified in the acyclic prefix of @code{lists},
    299 and the cycle length of the result is the sum of the lengths of the
    300 lists specified in the cycle of @code{lists}.
    301 
    302 The following equivalences hold:
    303 @example
    304 (append) @equiv{} () 
    305 (append h) @equiv{} h
    306 (append () h . t) @equiv{} (append h . t) 
    307 (append (cons a b) h . t) @equiv{} (cons a (append b h . t))
    308 @end example
    309 @c TODO add xref/comp to append
    310 @end deffn
    311 
    312 @deffn Applicative list-neighbors (list-neighbors list)
    313   The @code{list-neighbors} applicative constructs and returns a list
    314 of all the consecutive sublists of @code{list} of length 2, in order.
    315 If @code{list} is nil, the result is nil.  If @code{list} is non-nil,
    316 the length of the result is one less than the length of
    317 @code{list}. If @code{list} is cyclic, the result is structurally
    318 isomorphic to it (i.e., has the same acyclic prefix length and cycle
    319 length).
    320 @c TODO add xref to isomorphic
    321 
    322   For example:
    323 @example
    324 (list-neighbors (list 1 2 3 4)) @result{} ((1 2) (2 3) (3 4))
    325 @end example
    326 @end deffn
    327 
    328 @deffn Applicative filter (filter applicative list)
    329   Applicative @code{filter} passes each of the elements of @code{list}
    330 as an argument to @code{applicative}, one at a time in no particular
    331 order, using a fresh empty environment for each call.  The result of
    332 each call to @code{applicative} must be boolean, otherwise an error is
    333 signaled.  @code{filter} constructs and returns a list of all elements
    334 of @code{list} on which @code{applicative} returned true, in the same
    335 order as in @code{list}.  @code{applicative} is called exactly as many
    336 times as there are pairs in @code{list}.  The resultant list has a
    337 cycle containing exactly those elements accepted by @code{applicative}
    338 that were in the cycle of @code{list}; if there were no such elements,
    339 the result is acyclic.
    340 @end deffn
    341 
    342 @deffn Applicative assoc (assoc object pairs [eq-pred?])
    343   Applicative @code{assoc} returns the first element of @code{pairs}
    344 whose car is @code{eq-pred?} to @code{object}.  If there is no such
    345 element in @code{pairs}, nil is returned.  If @code{eq-pred?} is not
    346 supplied it defaults to @code{equal?}.
    347 @c TODO add xref/comp to assq
    348 @c TODO add xref to equal?
    349 SOURCE NOTE: the optional eq-pred? argument is from r7rs.
    350 @end deffn
    351 
    352 @deffn Applicative member? (member? object list [eq-pred?])
    353   Applicative @code{member?} is a predicate that returns true iff some
    354 element of @code{list} is @code{eq-pred?} to @code{object}.  If
    355 @code{eq-pred?} is not supplied, it defaults to @code{equal?}.
    356 @c TODO add xref/comp to memq
    357 @c TODO add xref to equal?
    358 SOURCE NOTE: the optional eq-pred? argument is from r7rs.
    359 @end deffn
    360 
    361 @deffn Applicative finite-list? (finite-list? . objects)
    362   This is the type predicate for type finite-list.
    363 @code{finite-list?}  returns true iff all the objects in
    364 @code{objects} are acyclic lists.
    365 @end deffn
    366 
    367 @deffn Applicative countable-list? (countable-list? . objects)
    368 This is the type predicate for type list.  @code{countable-list?}
    369 returns true iff all the objects in @code{objects} are lists.
    370 @end deffn
    371 
    372 @deffn Applicative reduce (reduce list binary identity [precycle incycle postcycle]) 
    373   @code{binary} should be an applicative. If the short form is used,
    374 @code{list} should be an acyclic. If the long form is used,
    375 @code{precycle}, @code{incycle}, and @code{postcycle} should be
    376 applicatives.
    377 
    378   If @code{list} is empty, applicative @code{reduce} returns
    379 @code{identity}.  If @code{list} is nonempty but acyclic, applicative
    380 @code{reduce} uses binary operation @code{binary} to merge all the
    381 elements of @code{list} into a single object, using any associative
    382 grouping of the elements. That is, the sequence of objects initially
    383 found in @code{list} is repeatedly decremented in length by applying
    384 @code{binary} to a list of any two consecutive objects, replacing
    385 those two objects with the result at the point in the sequence where
    386 they occurred; and when the sequence contains only one object, that
    387 object is returned.  If @code{list} is cyclic, the long form must be
    388 used.  The elements of the cycle are passed, one at a time (but just
    389 once for each position in the cycle), as arguments to unary
    390 applicative @code{precycle}; the finite, cyclic sequence of results
    391 from @code{precycle} is reduced using binary applicative
    392 @code{incycle}; and the result from reducing the cycle is passed as an
    393 argument to unary applicative @code{postcycle}. Binary operation
    394 @code{binary} is used to reduce the sequence consisting of the
    395 elements of the acyclic prefix of @code{list} followed by the result
    396 returned by @code{postcycle}. The only constraint on the order of
    397 calls to the applicatives is that each call must be made before its
    398 result is needed (thus, parts of the reduction of the acyclic prefix
    399 may occur before the contribution from the cycle has been completed).
    400 
    401   Each call to @code{binary}, @code{precycle}, @code{incycle}, or
    402 @code{postcycle} uses the dynamic environment of the call to
    403 @code{reduce}.  
    404   
    405   If @code{list} is acyclic with length @code{n >= 1},
    406 @code{binary} is called @code{n - 1} times.  If @code{list} is cyclic
    407 with acyclic prefix length @code{a} and cycle length @code{c},
    408 @code{binary} is called @code{a} times; @code{precycle}, @code{c}
    409 times; @code{incycle}, @code{c - 1} times; and @code{postcycle}, once.
    410 @end deffn
    411 
    412 @deffn Applicative append! (append! . lists)
    413   @code{lists} must be a nonempty list; its first element must be an
    414 acyclic nonempty list, and all of its elements except the last element
    415 (if any) must be acyclic lists. 
    416 
    417   The @code{append!} applicative sets the cdr of the last pair in each
    418 nonempty list argument to refer to the next non-nil argument, except
    419 that if there is a last non-nil argument, it isn’t mutated.  It is an
    420 error for any two of the list arguments to have the same last pair.
    421 The result returned by this applicative is inert.  
    422 
    423   The following equivalences hold:
    424 @example
    425 (append! v) @equiv{} #inert 
    426 (append! u v . w) @equiv{} ($sequence (append! u v) (append! u . w))
    427 @end example
    428 @end deffn
    429 
    430 @deffn Applicative copy-es (copy-es object)
    431   Briefly, applicative @code{copy-es} returns an object initially
    432 @code{equal?} to @code{object} with a freshly constructed evaluation
    433 @c TODO add xref to evaluation structure
    434 structure made up of mutable pairs.  If @code{object} is not a pair,
    435 the applicative returns @code{object}.  If @code{object} is a pair,
    436 the applicative returns a freshly constructed pair whose car and cdr
    437 would be suitable results for @code{(copy-es (car object))} and
    438 @code{(copy-es (cdr object))}, respectively.  Further, the evaluation
    439 @c TODO add xref to isomorphic
    440 structure of the returned value is structurally isomorphic to that of
    441 @code{object} at the time of copying, with corresponding non-pair
    442 referents being @code{eq?}.
    443 @c TODO add xref/comp to copy-es-immutable and the reverse too!
    444 @c TODO add xref to eq?/equal?
    445 @end deffn
    446 
    447 @deffn Applicative assq (assq object pairs)
    448   Applicative @code{assq} returns the first element of @code{pairs}
    449 whose car is @code{eq?} to @code{object}.  If there is no such element
    450 in @code{pairs}, nil is returned.  
    451 @c TODO add xref/comp to assoc
    452 @c TODO add xref to eq?
    453 @end deffn
    454 
    455 @deffn Applicative memq? (memq? object list) 
    456   Applicative @code{memq?} is a predicate that returns true iff some
    457 element of @code{list} is @code{eq?} to @code{object}.
    458 @c TODO add xref/comp to member?
    459 @c TODO add xref to eq?
    460 @end deffn