klisp

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

combiners.texi (7031B)


      1 @c -*-texinfo-*-
      2 @setfilename ../src/combiners
      3 
      4 @node Combiners, Continuations, Environments, Top
      5 @comment  node-name,  next,  previous,  up
      6 
      7 @chapter Combiners
      8 @cindex combiners
      9 @cindex applicatives
     10 @cindex operatives
     11 
     12   There are two types of combiners in Kernel, operative and
     13 applicative. Both types are encapsulated. All combiners are immutable.
     14 Two applicatives are @code{eq?} iff their underlying combiners are
     15 @code{eq?}.  However, @code{eq?}-ness of operatives is only
     16 constrained by the general rules for @code{eq?}, which leave
     17 considerable leeway for variation between implementations.  klisp only
     18 considers @code{eq?} those operatives constructed by the same call to
     19 a constructor (e.g. @code{$vau}).  Two combiners are @code{equal?}
     20 iff they are @code{eq?}.
     21 @c TODO add xref for eq? and equal?
     22 
     23 @deffn Applicative operative? (operative? . objects)
     24   The primitive type predicate for type operative. @code{operative?}
     25 returns true iff all the objects in @code{objects} are of type
     26 operative.
     27 @end deffn
     28 
     29 @deffn Applicative applicative? (applicative? . objects) 
     30   The primitive type predicate for type applicative.
     31 @code{applicative?} returns true iff all the objects in
     32 @code{objects} are of type applicative.
     33 @end deffn
     34 
     35 @deffn Operative $vau ($vau <formals> <eformal> . <objects>)
     36 @c TODO add xref to formal parameter tree
     37 @code{<formals>} should be a formal parameter tree; @code{<eformal>}
     38 should be either a symbol or @code{#ignore}.  If @code{<formals>} does
     39 not have the correct form for a formal parameter tree, or if
     40 @code{<eformal>} is a symbol that also occurs in @code{<formals>}, an
     41 error is signaled.
     42 
     43   A @code{vau} expression evaluates to an operative; an operative
     44 created in this way is said to be compound. The environment in which
     45 the @code{vau} expression was evaluated is remembered as part of the compound
     46 operative, called the compound operative’s static environment.
     47 @code{<formals>} and @code{<objects>} are copied as by
     48 @code{copy-es-immutable} and the copies are stored as part of the
     49 operative being constructed.  This avoids problem if these structures
     50 are later mutated.
     51 
     52 @c TODO add xref to eval or apply as example
     53 When the compound operative created by @code{$vau} is later called
     54 with an object and an environment, here called respectively the
     55 operand tree and the dynamic environment, the following happens:
     56 
     57 @enumerate
     58 @item
     59 A new, initially empty environment is created, with the static
     60 environment as its parent. This will be called the local environment.
     61 
     62 @item
     63 A stored copy of the formal parameter tree formals is matched in the
     64 local environment to the operand tree, locally binding the symbols of
     65 @c TODO add xref to matching
     66 formals to the corresponding parts of the operand tree.  eformal is
     67 matched to the dynamic environment; that is, if eformal is a symbol
     68 then that symbol is bound in the local environment to the dynamic
     69 environment.
     70 
     71 @item
     72 @c TODO add xref to tail context.
     73 A stored copy of the expressions is evaluated sequentially from left
     74 to right, with the last (if any) evaluated as a tail context, or if
     75 the list of expressions is empty, the result is inert.
     76 @end enumerate
     77 
     78   NOTE: Because compound operatives are not a distinct type in Kernel,
     79 they are covered by the encapsulation of type operative.  In
     80 particular, an implementation of Kernel cannot provide a feature that
     81 supports extracting the static environment of any given compound
     82 operative, nor that supports determining whether or not a given
     83 operative is compound.
     84 @end deffn
     85 
     86 
     87 @deffn Applicative wrap (wrap combiner)
     88   The @code{wrap} applicative returns an applicative whose underlying
     89 combiner is @code{combiner}.
     90 @end deffn
     91 
     92 @deffn Applicative unwrap (unwrap applicative)
     93   The @code{unwrap} applicative returns the underlying combiner of
     94 @code{applicative}.
     95 @end deffn
     96 
     97 @deffn Operative $lambda ($lambda <formals> . <objects>)
     98   @code{<formals>} should be a formal parameter tree.
     99 
    100   The @code{$lambda} operative is defined by the following equivalence:
    101 @example
    102 ($lambda formals . objects) @equiv{} 
    103   (wrap ($vau formals #ignore . objects))
    104 @end example
    105 @end deffn
    106 
    107 @deffn Applicative apply (apply applicative object [environment])
    108   Applicative @code{apply} combines the underlying combiner of
    109 @code{applicative} with @code{object} in a tail context with dynamic
    110 environment @code{environment} (if the long form is used) or in an
    111 empty environment (if the short form is used).
    112 
    113 The following equivalences hold:
    114 @example
    115 (apply applicative object environment) @equiv{}
    116   (eval (cons (unwrap applicative) object) environment) 
    117 
    118 (apply applicative object) @equiv{}
    119   (apply applicative object (make-environment))
    120 @end example
    121 @end deffn
    122 
    123 @deffn Applicative map (map applicative . lists)
    124   @code{lists} must be a nonempty list of lists; if there are two or
    125 @c TODO add xref to length
    126 more, they must all have the same length. If @code{lists} is empty, or
    127 if all of its elements are not lists of the same length, an error is
    128 signaled.
    129   
    130   The @code{map} applicative applies @code{applicative} element-wise
    131 to the elements of the lists in @code{lists} (i.e., applies it to a
    132 list of the first elements of the @code{lists}, to a list of the
    133 second elements of the @code{lists}, etc.), using the dynamic
    134 environment from which @code{map} was called, and returns a list of
    135 the results, in order. The applications may be performed in any order,
    136 as long as their results occur in the resultant list in the order of
    137 their arguments in the original @code{lists}.  If @code{lists} is a
    138 cyclic list, each argument list to which @code{applicative} is applied
    139 is structurally isomorphic to @code{lists}.  If any of the elements of
    140 @code{lists} is a cyclic list, they all must be, or they wouldn’t all
    141 have the same length.  Let @code{a1...an} be their acyclic prefix
    142 lengths, and @code{c1...cn} be their cycle lengths.  The acyclic
    143 prefix length @code{a} of the resultant list will be the maximum of
    144 the @code{ak}, while the cycle length @code{c} of the resultant list
    145 will be the least common multiple of the @code{ck}.  In the
    146 construction of the result, applicative is called exactly @code{a + c}
    147 times.
    148 @c TODO comp/xref for-each
    149 @end deffn
    150 
    151 @deffn Applicative string-map (string-map applicative . strings)
    152 @deffnx Applicative vector-map (vector-map applicative . vectors)
    153 @deffnx Applicative bytevector-map (bytevector-map applicative . bytevectors)
    154 @code{strings}, @code{vectors}, or @code{bytevectors} should be
    155 non-empty lists of the corresponding type and all elements should be
    156 of the same length.
    157 
    158 These applicatives behave as @code{map} except that the list of
    159 elements passed to @code{applicative} are the n-th chars, objects, or
    160 uint8s of the strings, vectors or bytevectors passed as arguments.
    161 
    162 SOURCE NOTE: These are taken from r7rs.
    163 @end deffn
    164 
    165 @deffn Applicative combiner? (combiner? . objects)
    166   The primitive type predicate for type combiner. @code{combiner?}
    167 returns true iff all the objects in @code{objects} are of type
    168 combiner (i.e. applicative or operative).
    169 @end deffn
    170