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