klisp

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

commit 39ac8f8ce0ce5f77ba9ba20b4ab4df5201fa75ad
parent 5a41ccb081715f8e13cc7b0dac52a5eb3416d90f
Author: Andres Navarro <canavarro82@gmail.com>
Date:   Tue, 31 May 2011 18:42:19 -0300

Some more content on pairs and lists for the manual.

Diffstat:
Mmanual/html/A-Sample-Applicative-Description.html | 3++-
Mmanual/html/Index.html | 40+++++++++++++++++++++++++++++++++++++++-
Mmanual/klisp.info | 330+++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------
Mmanual/src/Makefile | 6++++--
Mmanual/src/intro.texi | 3++-
Mmanual/src/pairs_lists.texi | 201++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------
6 files changed, 448 insertions(+), 135 deletions(-)

diff --git a/manual/html/A-Sample-Applicative-Description.html b/manual/html/A-Sample-Applicative-Description.html @@ -61,7 +61,8 @@ then adds all the rest of the arguments to the result. <var>integer</var>, <var>integer1</var> or <var>continuation</var>) is expected to be of that type. A plural of a type (such as <var>numbers</var>) often means a list of objects of that type. Parameters named <var>object</var> may be of any -type. +type. Additionally parameters named <var>k</var>, or <var>kn</var> (for any +value of <var>n</var>), should be exact, non-negative integers. <!-- TODO add xref types of objects --> (XXX Types of Lisp Object XXX, for a list of Kernel object types.) Parameters with other sorts of names are diff --git a/manual/html/Index.html b/manual/html/Index.html @@ -40,17 +40,48 @@ Up:&nbsp;<a rel="up" accesskey="u" href="index.html#Top">Top</a> <li><a href="Control.html#index-g_t_0024if-28"><code>$if</code></a>: <a href="Control.html#Control">Control</a></li> <li><a href="Booleans.html#index-g_t_0024or_003f-18"><code>$or?</code></a>: <a href="Booleans.html#Booleans">Booleans</a></li> <li><a href="Control.html#index-g_t_0024sequence-29"><code>$sequence</code></a>: <a href="Control.html#Control">Control</a></li> -<li><a href="Pairs-and-lists.html#index-g_t_0028-42"><code>(</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Booleans.html#index-and_003f-15"><code>and?</code></a>: <a href="Booleans.html#Booleans">Booleans</a></li> +<li><a href="Pairs-and-lists.html#index-append-80"><code>append</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="A-Sample-Applicative-Description.html#index-applicative-descriptions-8">applicative descriptions</a>: <a href="A-Sample-Applicative-Description.html#A-Sample-Applicative-Description">A Sample Applicative Description</a></li> <li><a href="Booleans.html#index-boolean_003f-13"><code>boolean?</code></a>: <a href="Booleans.html#Booleans">Booleans</a></li> <li><a href="Booleans.html#index-booleans-12">booleans</a>: <a href="Booleans.html#Booleans">Booleans</a></li> +<li><a href="Pairs-and-lists.html#index-caaaar-58"><code>caaaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caaadr-59"><code>caaadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caaar-50"><code>caaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caadar-60"><code>caadar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caaddr-61"><code>caaddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caadr-51"><code>caadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caar-46"><code>caar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cadaar-62"><code>cadaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cadadr-63"><code>cadadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cadar-52"><code>cadar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caddar-64"><code>caddar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cadddr-65"><code>cadddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-caddr-53"><code>caddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cadr-47"><code>cadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-car-44"><code>car</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdaaar-66"><code>cdaaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdaadr-67"><code>cdaadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdaar-54"><code>cdaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdadar-68"><code>cdadar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdaddr-69"><code>cdaddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdadr-55"><code>cdadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdar-48"><code>cdar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cddaar-70"><code>cddaar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cddadr-71"><code>cddadr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cddar-56"><code>cddar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdddar-72"><code>cdddar</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cddddr-73"><code>cddddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdddr-57"><code>cdddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cddr-49"><code>cddr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-cdr-45"><code>cdr</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Pairs-and-lists.html#index-cons-38"><code>cons</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Control.html#index-control-26">control</a>: <a href="Control.html#Control">Control</a></li> <li><a href="Pairs-and-lists.html#index-copy_002des_002dimmutable_0021-41"><code>copy-es-immutable!</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Format-of-Descriptions.html#index-description-format-7">description format</a>: <a href="Format-of-Descriptions.html#Format-of-Descriptions">Format of Descriptions</a></li> <li><a href="Evaluation-Notation.html#index-documentation-notation-4">documentation notation</a>: <a href="Evaluation-Notation.html#Evaluation-Notation">Evaluation Notation</a></li> <li><a href="Pairs-and-lists.html#index-empty-list-34">empty list</a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-encycle_0021-76"><code>encycle!</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Equivalence.html#index-eq_003f-20"><code>eq?</code></a>: <a href="Equivalence.html#Equivalence">Equivalence</a></li> <li><a href="Equivalence.html#index-equal_003f-21"><code>equal?</code></a>: <a href="Equivalence.html#Equivalence">Equivalence</a></li> <li><a href="Equivalence.html#index-equivalence-19">equivalence</a>: <a href="Equivalence.html#Equivalence">Equivalence</a></li> @@ -59,9 +90,16 @@ Up:&nbsp;<a rel="up" accesskey="u" href="index.html#Top">Top</a> <li><a href="Some-Terms.html#index-fonts-2">fonts</a>: <a href="Some-Terms.html#Some-Terms">Some Terms</a></li> <li><a href="A-Sample-Applicative-Description.html#index-foo-11"><code>foo</code></a>: <a href="A-Sample-Applicative-Description.html#A-Sample-Applicative-Description">A Sample Applicative Description</a></li> <li><a href="Control.html#index-for_002deach-31"><code>for-each</code></a>: <a href="Control.html#Control">Control</a></li> +<li><a href="Pairs-and-lists.html#index-get_002dlist_002dmetrics-74"><code>get-list-metrics</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Control.html#index-inert_003f-27"><code>inert?</code></a>: <a href="Control.html#Control">Control</a></li> <li><a href="Kernel-History.html#index-Kernel-history-1">Kernel history</a>: <a href="Kernel-History.html#Kernel-History">Kernel History</a></li> +<li><a href="Pairs-and-lists.html#index-length-78"><code>length</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-list-42"><code>list</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-list_002a-43"><code>list*</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-list_002dref-79"><code>list-ref</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-list_002dtail-75"><code>list-tail</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Pairs-and-lists.html#index-lists-35">lists</a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> +<li><a href="Pairs-and-lists.html#index-map-77"><code>map</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Pairs-and-lists.html#index-nil-33">nil</a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> <li><a href="Booleans.html#index-not_003f-14"><code>not?</code></a>: <a href="Booleans.html#Booleans">Booleans</a></li> <li><a href="Pairs-and-lists.html#index-null_003f-37"><code>null?</code></a>: <a href="Pairs-and-lists.html#Pairs-and-lists">Pairs and lists</a></li> diff --git a/manual/klisp.info b/manual/klisp.info @@ -325,11 +325,13 @@ arguments are also used in the body of the description. Any parameter whose name contains the name of a type (e.g., INTEGER, INTEGER1 or CONTINUATION) is expected to be of that type. A plural of a type (such as NUMBERS) often means a list of objects of that type. -Parameters named OBJECT may be of any type. (XXX Types of Lisp Object -XXX, for a list of Kernel object types.) Parameters with other sorts -of names are discussed specifically in the description of the combiner. -In some sections, features common to parameters of several combiners are -described at the beginning. +Parameters named OBJECT may be of any type. Additionally parameters +named K, or KN (for any value of N), should be exact, non-negative +integers. (XXX Types of Lisp Object XXX, for a list of Kernel object +types.) Parameters with other sorts of names are discussed +specifically in the description of the combiner. In some sections, +features common to parameters of several combiners are described at the +beginning. Operative descriptions have the same format, but the word `Applicative' is replaced by `Operative', and `Argument' is replaced @@ -574,60 +576,166 @@ output using, modulo whitespace, external representation `(1 2 3)'. returned value is isomorphic to that of `object' at the time of copying, with corresponding non-pair referents being `eq?'. - In Kernel it's undefined whether immutable pairs are copied or - left "as is" in the result. klisp doesn't copy immutable pairs, - but that behaviour should not be depended upon. + NOTE: In Kernel it's undefined whether immutable pairs are copied + or left "as is" in the result. klisp doesn't copy immutable + pairs, but that behaviour should not be depended upon. - -- list: (list . objects) + -- Applicative: list (list . objects) The `list' applicative returns `objects'. The underlying operative of `list' returns its undifferentiated operand tree, regardless of whether that tree is or is not a list. - -- list*: (list* . objects) - `objects' should be a finite nonempty list of arguments. The - following equivalences hold: + -- Applicative: list* (list* . objects) + `objects' should be a finite nonempty list of arguments. + + The following equivalences hold: (list* arg1) == arg1 (list* arg1 arg2 . args) == (cons arg1 (list* arg2 . args)) - -- car: (car pair) - -- cdr: (cdr pair) + -- Applicative: car (car pair) + -- Applicative: cdr (cdr pair) These applicatives return, respectively, the car and cdr of `pair'. - -- caar: (caar pair) - -- cadr: (cadr pair) - -- cdar: (cdar pair) - -- cddr: (cddr pair) - -- caaar: (caaar pair) - -- caadr: (caadr pair) - -- cadar: (cadar pair) - -- caddr: (caddr pair) - -- cdaar: (cdaar pair) - -- cdadr: (cdadr pair) - -- cddar: (cddar pair) - -- cdddr: (cdddr pair) - -- caaaar: (caaaar pair) - -- caaadr: (caaadr pair) - -- caadar: (caadar pair) - -- caaddr: (caaddr pair) - -- cadaar: (cadaar pair) - -- cadadr: (cadadr pair) - -- caddar: (caddar pair) - -- cadddr: (cadddr pair) - -- cdaaar: (cdaaar pair) - -- cdaadr: (cdaadr pair) - -- cdadar: (cdadar pair) - -- cdaddr: (cdaddr pair) - -- cddaar: (cddaar pair) - -- cddadr: (cddadr pair) - -- cdddar: (cdddar pair) - -- cddddr: (cddddr pair) + -- Applicative: caar (caar pair) + -- Applicative: cadr (cadr pair) + -- Applicative: cdar (cdar pair) + -- Applicative: cddr (cddr pair) + -- Applicative: caaar (caaar pair) + -- Applicative: caadr (caadr pair) + -- Applicative: cadar (cadar pair) + -- Applicative: caddr (caddr pair) + -- Applicative: cdaar (cdaar pair) + -- Applicative: cdadr (cdadr pair) + -- Applicative: cddar (cddar pair) + -- Applicative: cdddr (cdddr pair) + -- Applicative: caaaar (caaaar pair) + -- Applicative: caaadr (caaadr pair) + -- Applicative: caadar (caadar pair) + -- Applicative: caaddr (caaddr pair) + -- Applicative: cadaar (cadaar pair) + -- Applicative: cadadr (cadadr pair) + -- Applicative: caddar (caddar pair) + -- Applicative: cadddr (cadddr pair) + -- Applicative: cdaaar (cdaaar pair) + -- Applicative: cdaadr (cdaadr pair) + -- Applicative: cdadar (cdadar pair) + -- Applicative: cdaddr (cdaddr pair) + -- Applicative: cddaar (cddaar pair) + -- Applicative: cddadr (cddadr pair) + -- Applicative: cdddar (cdddar pair) + -- Applicative: cddddr (cddddr pair) These applicatives are compositions of `car' and `cdr', with the "a’s" and "d’s" in the same order as they would appear if all the - individual "car"’s and "cdr"’s were written out in prefix order. + individual "car’s" and "cdr’s" were written out in prefix order. Arbitrary compositions up to four deep are provided. There are twenty-eight of these applicatives in all. + -- Applicative: get-list-metrics (get-list-metrics object) + By definition, an improper list is a data structure whose objects + are its start together with all objects reachable from the start by + following the cdr references of pairs, and whose internal + references are just the cdr references of its pairs. Every + object, of whatever type, is the start of an improper list. If + the start is not a pair, the improper list consists of just that + object. The acyclic prefix length of an improper list `L' is the + number of pairs of `L' that a naive traversal of `L' would visit + only once. The cycle length of `L' is the number of pairs of `L' + that a naive traversal would visit repeatedly. Two improper lists + are structurally isomorphic iff they have the same acyclic prefix + length and cycle length and, if they are terminated by non-pair + objects rather than by cycles, the non-pair objects have the same + type. Applicative `get-list-metrics' constructs and returns a + list of exact integers of the form `(p n a c)', where `p', `n', + `a', and `c' are, respectively, the number of pairs in, the number + of nil objects in, the acyclic prefix length of, and the cycle + length of, the improper list starting with `object'. `n' is either + `0' or `1', `a + c = p', and `n' and `c' cannot both be non-zero. + If `c = 0', the improper list is acyclic; if `n = 1', the improper + list is a finite list; if `n = c = 0', the improper list is not a + list; if `a = c = 0', `object' is not a pair. + + -- Applicative: list-tail (list-tail object k) + `object' must be the start of an improper list containing at least + `k' pairs. + + The `list-tail' applicative follows `k' cdr references starting + from `object'. + + The following equivalences hold: + (list-tail object 0) == object + (list-tail object (+ k 1)) == (list-tail (cdr object) k) + + -- Applicative: encycle! (encycle! object k1 k2) + The improper list starting at `object' must contain at least `k1 + + k2' pairs. + + If `k2 = 0', the applicative does nothing. If `k2 > 0', the + applicative mutates the improper list starting at `object' to have + acyclic prefix length `k1' and cycle length `k2', by setting the + cdr of the `(k1+k2)'th pair in the list to refer to the `(k1 + + 1)'th pair in the list. The result returned by `encycle!' is + inert. + + -- Applicative: map (map applicative . lists) + `lists' must be a nonempty list of lists; if there are two or + more, they must all have the same length. + + The map applicative applies `applicative' element-wise to the + elements of the lists in lists (i.e., applies it to a list of the + first elements of the lists, to a list of the second elements of + the lists, etc.), using the dynamic environment from which map was + called, and returns a list of the results, in order. The + applications may be performed in any order, as long as their + results occur in the resultant list in the order of their + arguments in the original lists. If `lists' is a cyclic list, + each argument list to which `applicative' is applied is + structurally isomorphic to `lists'. If any of the elements of + `lists' is a cyclic list, they all must be, or they wouldn’t all + have the same length. Let `a1...an' be their acyclic prefix + lengths, and `c1...cn' be their cycle lengths. The acyclic prefix + length `a' of the resultant list will be the maximum of the `ak', + while the cycle length `c' of the resultant list will be the least + common multiple of the `ck'. In the construction of the result, + `applicative' is called exactly `a + c' times. + + -- Applicative: length (length object) + Applicative `length' returns the (exact) improper-list length of + `object'. That is, it returns the number of consecutive cdr + references that can be followed starting from `object'. If + `object' is not a pair, it returns zero; if `object' is a cyclic + list, it returns positive infinity. + + -- Applicative: list-ref (list-ref object k) + The `list-ref' applicative returns the `car' of the object + obtained by following `k' cdr references starting from `object'. + + NOTE: In the current report, object is required to be a list. In + klisp, for now, we prefer the behaviour presented here, as it is + more in line with the applicative `list-tail'. That is, we define + `list-ref' by the following equivalence: + (list-ref object k) == (car (list-tail object k)) + + -- Applicative: append (append . lists) + Here, all the elements of `lists' except the last element (if any) + must be acyclic lists. The `append' applicative returns a freshly + allocated list of the elements of all the specified `lists', in + order, except that if there is a last specified element of + `lists', it is not copied, but is simply referenced by the cdr of + the preceding pair (if any) in the resultant list. If `lists' is + cyclic, the cycle of the result list consists of just the elements + of the lists specified in the cycle in `lists'. In this case, the + acyclic prefix length of the result is the sum of the lengths of + the lists specified in the acyclic prefix of `lists', and the + cycle length of the result is the sum of the lengths of the lists + specified in the cycle of `lists'. + + The following equivalences hold: + (append) == () + (append h) == h + (append () h . t) == (append h . t) + (append (cons a b) h . t) == (cons a (append b h . t)) +  File: klisp.info, Node: Index, Next: (dir), Prev: Pairs and lists, Up: Top @@ -637,53 +745,91 @@ Index * Menu: -* $and?: Booleans. (line 28) -* $cond: Control. (line 32) -* $if: Control. (line 15) -* $or?: Booleans. (line 41) -* $sequence: Control. (line 23) -* (: Pairs and lists. (line 72) -* and?: Booleans. (line 20) +* $and?: Booleans. (line 28) +* $cond: Control. (line 32) +* $if: Control. (line 15) +* $or?: Booleans. (line 41) +* $sequence: Control. (line 23) +* and?: Booleans. (line 20) +* append: Pairs and lists. (line 208) * applicative descriptions: A Sample Applicative Description. - (line 6) -* boolean?: Booleans. (line 12) -* booleans: Booleans. (line 6) -* cons: Pairs and lists. (line 35) -* control: Control. (line 6) -* copy-es-immutable!: Pairs and lists. (line 49) + (line 6) +* boolean?: Booleans. (line 12) +* booleans: Booleans. (line 6) +* caaaar: Pairs and lists. (line 101) +* caaadr: Pairs and lists. (line 102) +* caaar: Pairs and lists. (line 93) +* caadar: Pairs and lists. (line 103) +* caaddr: Pairs and lists. (line 104) +* caadr: Pairs and lists. (line 94) +* caar: Pairs and lists. (line 89) +* cadaar: Pairs and lists. (line 105) +* cadadr: Pairs and lists. (line 106) +* cadar: Pairs and lists. (line 95) +* caddar: Pairs and lists. (line 107) +* cadddr: Pairs and lists. (line 108) +* caddr: Pairs and lists. (line 96) +* cadr: Pairs and lists. (line 90) +* car: Pairs and lists. (line 85) +* cdaaar: Pairs and lists. (line 109) +* cdaadr: Pairs and lists. (line 110) +* cdaar: Pairs and lists. (line 97) +* cdadar: Pairs and lists. (line 111) +* cdaddr: Pairs and lists. (line 112) +* cdadr: Pairs and lists. (line 98) +* cdar: Pairs and lists. (line 91) +* cddaar: Pairs and lists. (line 113) +* cddadr: Pairs and lists. (line 114) +* cddar: Pairs and lists. (line 99) +* cdddar: Pairs and lists. (line 115) +* cddddr: Pairs and lists. (line 116) +* cdddr: Pairs and lists. (line 100) +* cddr: Pairs and lists. (line 92) +* cdr: Pairs and lists. (line 86) +* cons: Pairs and lists. (line 35) +* control: Control. (line 6) +* copy-es-immutable!: Pairs and lists. (line 49) * description format: Format of Descriptions. - (line 6) -* documentation notation: Evaluation Notation. (line 6) -* empty list: Pairs and lists. (line 6) -* eq?: Equivalence. (line 12) -* equal?: Equivalence. (line 16) -* equivalence: Equivalence. (line 6) -* error message notation: Error Messages. (line 6) -* evaluation notation: Evaluation Notation. (line 6) -* fonts: Some Terms. (line 13) + (line 6) +* documentation notation: Evaluation Notation. (line 6) +* empty list: Pairs and lists. (line 6) +* encycle!: Pairs and lists. (line 158) +* eq?: Equivalence. (line 12) +* equal?: Equivalence. (line 16) +* equivalence: Equivalence. (line 6) +* error message notation: Error Messages. (line 6) +* evaluation notation: Evaluation Notation. (line 6) +* fonts: Some Terms. (line 13) * foo: A Sample Applicative Description. - (line 15) -* for-each: Control. (line 42) -* inert?: Control. (line 11) -* Kernel history: Kernel History. (line 6) -* lists: Pairs and lists. (line 6) -* nil: Pairs and lists. (line 6) -* not?: Booleans. (line 16) -* null?: Pairs and lists. (line 31) + (line 15) +* for-each: Control. (line 42) +* get-list-metrics: Pairs and lists. (line 123) +* inert?: Control. (line 11) +* Kernel history: Kernel History. (line 6) +* length: Pairs and lists. (line 191) +* list: Pairs and lists. (line 72) +* list*: Pairs and lists. (line 78) +* list-ref: Pairs and lists. (line 198) +* list-tail: Pairs and lists. (line 147) +* lists: Pairs and lists. (line 6) +* map: Pairs and lists. (line 169) +* nil: Pairs and lists. (line 6) +* not?: Booleans. (line 16) +* null?: Pairs and lists. (line 31) * object descriptions: A Sample Applicative Description. - (line 6) + (line 6) * operative descriptions: A Sample Applicative Description. - (line 6) -* or?: Booleans. (line 24) -* pair?: Pairs and lists. (line 27) -* pairs: Pairs and lists. (line 6) -* printing notation: Printing Notation. (line 6) -* set-car!: Pairs and lists. (line 41) -* set-cdr!: Pairs and lists. (line 42) -* string->symbol: Symbols. (line 20) -* symbol->string: Symbols. (line 16) -* symbol?: Symbols. (line 12) -* symbols: Symbols. (line 6) + (line 6) +* or?: Booleans. (line 24) +* pair?: Pairs and lists. (line 27) +* pairs: Pairs and lists. (line 6) +* printing notation: Printing Notation. (line 6) +* set-car!: Pairs and lists. (line 41) +* set-cdr!: Pairs and lists. (line 42) +* string->symbol: Symbols. (line 20) +* symbol->string: Symbols. (line 16) +* symbol?: Symbols. (line 12) +* symbols: Symbols. (line 6)  @@ -700,12 +846,12 @@ Node: Printing Notation10297 Node: Error Messages10773 Node: Format of Descriptions11421 Node: A Sample Applicative Description11985 -Node: Acknowledgements13645 -Node: Booleans14031 -Node: Equivalence16573 -Node: Symbols17366 -Node: Control18731 -Node: Pairs and lists21048 -Node: Index25996 +Node: Acknowledgements13748 +Node: Booleans14134 +Node: Equivalence16676 +Node: Symbols17469 +Node: Control18834 +Node: Pairs and lists21151 +Node: Index32148  End Tag Table diff --git a/manual/src/Makefile b/manual/src/Makefile @@ -1,8 +1,10 @@ # Makefile for the klisp manual # some of this is from the elisp manual -srcs = klisp.texi intro.texi \ - index.texi booleans.texi equivalence.texi symbols.texi +srcs = klisp.texi index.texi \ + intro.texi \ + booleans.texi equivalence.texi symbols.texi \ + control.texi pairs_lists.texi #TODO add dvi/pdf output #TODO check what happens with xrefs diff --git a/manual/src/intro.texi b/manual/src/intro.texi @@ -309,7 +309,8 @@ More generally, @var{integer}, @var{integer1} or @var{continuation}) is expected to be of that type. A plural of a type (such as @var{numbers}) often means a list of objects of that type. Parameters named @var{object} may be of any -type. +type. Additionally parameters named @var{k}, or @var{kn} (for any +value of @var{n}), should be exact, non-negative integers. @c TODO add xref types of objects (XXX Types of Lisp Object XXX, for a list of Kernel object types.) Parameters with other sorts of names are diff --git a/manual/src/pairs_lists.texi b/manual/src/pairs_lists.texi @@ -79,63 +79,64 @@ immutable pair whose car and cdr would be suitable results for the returned value is isomorphic to that of @code{object} at the time of copying, with corresponding non-pair referents being @code{eq?}. - In Kernel it's undefined whether immutable pairs are copied or left ``as -is'' in the result. klisp doesn't copy immutable pairs, but that -behaviour should not be depended upon. + NOTE: In Kernel it's undefined whether immutable pairs are copied or +left ``as is'' in the result. klisp doesn't copy immutable pairs, but +that behaviour should not be depended upon. @end deffn -@deffn list (list . objects) +@deffn Applicative list (list . objects) The @code{list} applicative returns @code{objects}. The underlying operative of @code{list} returns its undifferentiated operand tree, regardless of whether that tree is or is not a list. @end deffn -@deffn list* (list* . objects) -@code{objects} should be a finite nonempty list of arguments. The -following equivalences hold: +@deffn Applicative list* (list* . objects) +@code{objects} should be a finite nonempty list of arguments. + + The following equivalences hold: @example (list* arg1) @equiv{} arg1 (list* arg1 arg2 . args) @equiv{} (cons arg1 (list* arg2 . args)) @end example @end deffn -@deffn car (car pair) -@deffnx cdr (cdr pair) +@deffn Applicative car (car pair) +@deffnx Applicative cdr (cdr pair) These applicatives return, respectively, the car and cdr of @code{pair}. @end deffn @c 2 levels -@deffn caar (caar pair) -@deffnx cadr (cadr pair) -@deffnx cdar (cdar pair) -@deffnx cddr (cddr pair) +@deffn Applicative caar (caar pair) +@deffnx Applicative cadr (cadr pair) +@deffnx Applicative cdar (cdar pair) +@deffnx Applicative cddr (cddr pair) @c 3 levels -@deffnx caaar (caaar pair) -@deffnx caadr (caadr pair) -@deffnx cadar (cadar pair) -@deffnx caddr (caddr pair) -@deffnx cdaar (cdaar pair) -@deffnx cdadr (cdadr pair) -@deffnx cddar (cddar pair) -@deffnx cdddr (cdddr pair) +@deffnx Applicative caaar (caaar pair) +@deffnx Applicative caadr (caadr pair) +@deffnx Applicative cadar (cadar pair) +@deffnx Applicative caddr (caddr pair) +@deffnx Applicative cdaar (cdaar pair) +@deffnx Applicative cdadr (cdadr pair) +@deffnx Applicative cddar (cddar pair) +@deffnx Applicative cdddr (cdddr pair) @c 3 levels -@deffnx caaaar (caaaar pair) -@deffnx caaadr (caaadr pair) -@deffnx caadar (caadar pair) -@deffnx caaddr (caaddr pair) -@deffnx cadaar (cadaar pair) -@deffnx cadadr (cadadr pair) -@deffnx caddar (caddar pair) -@deffnx cadddr (cadddr pair) - -@deffnx cdaaar (cdaaar pair) -@deffnx cdaadr (cdaadr pair) -@deffnx cdadar (cdadar pair) -@deffnx cdaddr (cdaddr pair) -@deffnx cddaar (cddaar pair) -@deffnx cddadr (cddadr pair) -@deffnx cdddar (cdddar pair) -@deffnx cddddr (cddddr pair) +@deffnx Applicative caaaar (caaaar pair) +@deffnx Applicative caaadr (caaadr pair) +@deffnx Applicative caadar (caadar pair) +@deffnx Applicative caaddr (caaddr pair) +@deffnx Applicative cadaar (cadaar pair) +@deffnx Applicative cadadr (cadadr pair) +@deffnx Applicative caddar (caddar pair) +@deffnx Applicative cadddr (cadddr pair) + +@deffnx Applicative cdaaar (cdaaar pair) +@deffnx Applicative cdaadr (cdaadr pair) +@deffnx Applicative cdadar (cdadar pair) +@deffnx Applicative cdaddr (cdaddr pair) +@deffnx Applicative cddaar (cddaar pair) +@deffnx Applicative cddadr (cddadr pair) +@deffnx Applicative cdddar (cdddar pair) +@deffnx Applicative cddddr (cddddr pair) @c TODO add note about pronunciation These applicatives are compositions of @code{car} and @code{cdr}, with @@ -145,3 +146,127 @@ order. Arbitrary compositions up to four deep are provided. There are twenty-eight of these applicatives in all. @end deffn +@deffn Applicative get-list-metrics (get-list-metrics object) +@c TODO move definition of improper list to intro, xref data structure + By definition, an improper list is a data structure whose objects +are its start together with all objects reachable from the start by +following the cdr references of pairs, and whose internal references +are just the cdr references of its pairs. Every object, of whatever +type, is the start of an improper list. If the start is not a pair, +the improper list consists of just that object. The acyclic prefix +length of an improper list @code{L} is the number of pairs of @code{L} +that a naive traversal of @code{L} would visit only once. The cycle +length of @code{L} is the number of pairs of @code{L} that a naive +traversal would visit repeatedly. Two improper lists are structurally +@c TODO add xref to isomorphic +isomorphic iff they have the same acyclic prefix length and cycle +length and, if they are terminated by non-pair objects rather than by +cycles, the non-pair objects have the same type. Applicative +@code{get-list-metrics} constructs and returns a list of exact +integers of the form @code{(p n a c)}, where @code{p}, @code{n}, +@code{a}, and @code{c} are, respectively, the number of pairs in, the +number of nil objects in, the acyclic prefix length of, and the cycle +length of, the improper list starting with @code{object}. @code{n} is +either @code{0} or @code{1}, @code{a + c = p}, and @code{n} and +@code{c} cannot both be non-zero. If @code{c = 0}, the improper list +is acyclic; if @code{n = 1}, the improper list is a finite list; if +@code{n = c = 0}, the improper list is not a list; if @code{a = c = +0}, @code{object} is not a pair. +@end deffn + +@deffn Applicative list-tail (list-tail object k) +@code{object} must be the start of an improper list containing at +least @code{k} pairs. + + The @code{list-tail} applicative follows @code{k} cdr references +starting from @code{object}. + +The following equivalences hold: +@example +(list-tail object 0) @equiv{} object +(list-tail object (+ k 1)) @equiv{} (list-tail (cdr object) k) +@end example +@end deffn + +@deffn Applicative encycle! (encycle! object k1 k2) + The improper list starting at @code{object} must contain at least +@code{k1 + k2} pairs. + + If @code{k2 = 0}, the applicative does nothing. If @code{k2 > 0}, +the applicative mutates the improper list starting at @code{object} to +have acyclic prefix length @code{k1} and cycle length @code{k2}, by +setting the cdr of the @code{(k1+k2)}th pair in the list to refer to +the @code{(k1 + 1)}th pair in the list. The result returned by +@code{encycle!} is inert. +@end deffn + +@deffn Applicative map (map applicative . lists) + @code{lists} must be a nonempty list of lists; if there are two or +@c TODO add xref to length +more, they must all have the same length. + + The map applicative applies @code{applicative} element-wise to the +elements of the lists in lists (i.e., applies it to a list of the +first elements of the lists, to a list of the second elements of the +lists, etc.), using the dynamic environment from which map was called, +and returns a list of the results, in order. The applications may be +performed in any order, as long as their results occur in the +resultant list in the order of their arguments in the original lists. +If @code{lists} is a cyclic list, each argument list to which +@c TODO xref to ismorphic +@code{applicative} is applied is structurally isomorphic to @code{lists}. If +any of the elements of @code{lists} is a cyclic list, they all must +be, or they wouldn’t all have the same length. Let @code{a1...an} be +their acyclic prefix lengths, and @code{c1...cn} be their cycle +lengths. The acyclic prefix length @code{a} of the resultant list +will be the maximum of the @code{ak}, while the cycle length @code{c} +of the resultant list will be the least common multiple of the +@code{ck}. In the construction of the result, @code{applicative} is +called exactly @code{a + c} times. +@end deffn + +@deffn Applicative length (length object) +@c TODO xref improper-list + Applicative @code{length} returns the (exact) improper-list length +of @code{object}. That is, it returns the number of consecutive cdr +references that can be followed starting from @code{object}. If +@code{object} is not a pair, it returns zero; if @code{object} is a +cyclic list, it returns positive infinity. +@end deffn + +@deffn Applicative list-ref (list-ref object k) + The @code{list-ref} applicative returns the @code{car} of the object +obtained by following @code{k} cdr references starting from +@code{object}. + +NOTE: In the current report, object is required to be a list. In +klisp, for now, we prefer the behaviour presented here, as it is more +in line with the applicative @code{list-tail}. That is, we define +@code{list-ref} by the following equivalence: +@example +(list-ref object k) @equiv{} (car (list-tail object k)) +@end example +@end deffn + +@deffn Applicative append (append . lists) + Here, all the elements of @code{lists} except the last element (if +any) must be acyclic lists. The @code{append} applicative returns a +freshly allocated list of the elements of all the specified +@code{lists}, in order, except that if there is a last specified +element of @code{lists}, it is not copied, but is simply referenced by +the cdr of the preceding pair (if any) in the resultant list. If +@code{lists} is cyclic, the cycle of the result list consists of just +the elements of the lists specified in the cycle in @code{lists}. In +this case, the acyclic prefix length of the result is the sum of the +lengths of the lists specified in the acyclic prefix of @code{lists}, +and the cycle length of the result is the sum of the lengths of the +lists specified in the cycle of @code{lists}. + +The following equivalences hold: +@example +(append) @equiv{} () +(append h) @equiv{} h +(append () h . t) @equiv{} (append h . t) +(append (cons a b) h . t) @equiv{} (cons a (append b h . t)) +@end example +@end deffn