core/combinators/combinators-docs.factor

   1 USING: arrays help.markup help.syntax strings sbufs vectors
   2 kernel quotations generic generic.standard classes
   3 math assocs sequences sequences.private combinators.private
   4 effects words ;
   5 IN: combinators
   6
   7 ARTICLE: "combinators-quot" "Quotation construction utilities"
   8 "Some words for creating quotations which can be useful for implementing method combinations and compiler transforms:"
   9 { $subsection cond>quot }
  10 { $subsection case>quot }
  11 { $subsection alist>quot } ;
  12
  13 ARTICLE: "call" "Calling code with known stack effects"
  14 "Arbitrary quotations and words can be called from code accepted by the optimizing compiler. This is done by specifying the stack effect of the quotation literally. It is checked at runtime that the stack effect is accurate."
  15 $nl
  16 "Quotations:"
  17 { $subsection POSTPONE: call( }
  18 { $subsection call-effect }
  19 "Words:"
  20 { $subsection POSTPONE: execute( }
  21 { $subsection execute-effect }
  22 "Unsafe calls:"
  23 { $subsection call-effect-unsafe }
  24 { $subsection execute-effect-unsafe } ;
  25
  26 ARTICLE: "combinators" "Additional combinators"
  27 "The " { $vocab-link "combinators" } " vocabulary provides a few useful combinators."
  28 $nl
  29 "Generalization of " { $link bi } " and " { $link tri } ":"
  30 { $subsection cleave }
  31 "Generalization of " { $link 2bi } " and " { $link 2tri } ":"
  32 { $subsection 2cleave }
  33 "Generalization of " { $link 3bi } " and " { $link 3tri }  ":"
  34 { $subsection 3cleave }
  35 "Generalization of " { $link bi* } " and " { $link tri* } ":"
  36 { $subsection spread }
  37 "Two combinators which abstract out nested chains of " { $link if } ":"
  38 { $subsection cond }
  39 { $subsection case }
  40 "The " { $vocab-link "combinators" } " also provides some less frequently-used features."
  41 $nl
  42 "A combinator which can help with implementing methods on " { $link hashcode* } ":"
  43 { $subsection recursive-hashcode }
  44 { $subsection "call" }
  45 { $subsection "combinators-quot" }
  46 { $see-also "quotations" "dataflow" } ;
  47
  48 ABOUT: "combinators"
  49
  50 HELP: call-effect
  51 { $values { "quot" quotation } { "effect" effect } }
  52 { $description "Given a quotation and a stack effect, calls the quotation, asserting at runtime that it has the given stack effect. This is a macro which expands given a literal effect parameter, and an arbitrary quotation which is not required at compile time." } ;
  53
  54 HELP: execute-effect
  55 { $values { "word" word } { "effect" effect } }
  56 { $description "Given a word and a stack effect, executes the word, asserting at runtime that it has the given stack effect. This is a macro which expands given a literal effect parameter, and an arbitrary word which is not required at compile time." } ;
  57
  58 HELP: execute-effect-unsafe
  59 { $values { "word" word } { "effect" effect } }
  60 { $description "Given a word and a stack effect, executes the word, blindly declaring at runtime that it has the given stack effect. This is a macro which expands given a literal effect parameter, and an arbitrary word which is not required at compile time." }
  61 { $warning "If the word being executed has an incorrect stack effect, undefined behavior will result. User code should use " { $link POSTPONE: execute( } " instead." } ;
  62
  63 { call-effect call-effect-unsafe execute-effect execute-effect-unsafe } related-words
  64
  65 HELP: cleave
  66 { $values { "x" object } { "seq" "a sequence of quotations with stack effect " { $snippet "( x -- ... )" } } }
  67 { $description "Applies each quotation to the object in turn." }
  68 { $examples
  69     "The " { $link bi } " combinator takes one value and two quotations; the " { $link tri } " combinator takes one value and three quotations. The " { $link cleave } " combinator takes one value and any number of quotations, and is essentially equivalent to a chain of " { $link keep } " forms:"
  70     { $code
  71         "! Equivalent"
  72         "{ [ p ] [ q ] [ r ] [ s ] } cleave"
  73         "[ p ] keep [ q ] keep [ r ] keep s"
  74     }
  75 } ;
  76
  77 HELP: 2cleave
  78 { $values { "x" object } { "y" object }
  79           { "seq" "a sequence of quotations with stack effect " { $snippet "( x y -- ... )" } } }
  80 { $description "Applies each quotation to the two objects in turn." } ;
  81
  82 HELP: 3cleave
  83 { $values { "x" object } { "y" object } { "z" object }
  84           { "seq" "a sequence of quotations with stack effect " { $snippet "( x y z -- ... )" } } }
  85 { $description "Applies each quotation to the three objects in turn." } ;
  86
  87 { bi tri cleave } related-words
  88
  89 HELP: spread
  90 { $values { "objs..." "objects" } { "seq" "a sequence of quotations with stack effect " { $snippet "( x -- ... )" } } }
  91 { $description "Applies each quotation to the object in turn." }
  92 { $examples
  93     "The " { $link bi* } " combinator takes two values and two quotations; the " { $link tri* } " combinator takes three values and three quotations. The " { $link spread } " combinator takes " { $snippet "n" } " values and " { $snippet "n" } " quotations, where " { $snippet "n" } " is the length of the input sequence, and is essentially equivalent to series of retain stack manipulations:"
  94     { $code
  95         "! Equivalent"
  96         "{ [ p ] [ q ] [ r ] [ s ] } spread"
  97         "[ [ [ p ] dip q ] dip r ] dip s"
  98     }
  99 } ;
 100
 101 { bi* tri* spread } related-words
 102
 103 HELP: alist>quot
 104 { $values { "default" "a quotation" } { "assoc" "a sequence of quotation pairs" } { "quot" "a new quotation" } }
 105 { $description "Constructs a quotation which calls the first quotation in each pair of " { $snippet "assoc" } " until one of them outputs a true value, and then calls the second quotation in the corresponding pair. Quotations are called in reverse order, and if no quotation outputs a true value then " { $snippet "default" } " is called." }
 106 { $notes "This word is used to implement compile-time behavior for " { $link cond } ", and it is also used by the generic word system. Note that unlike " { $link cond } ", the constructed quotation performs the tests starting from the end and not the beginning." } ;
 107
 108 HELP: cond
 109 { $values { "assoc" "a sequence of quotation pairs and an optional quotation" } }
 110 { $description
 111     "Calls the second quotation in the first pair whose first quotation yields a true value. A single quotation will always yield a true value."
 112     $nl
 113     "The following two phrases are equivalent:"
 114     { $code "{ { [ X ] [ Y ] } { [ Z ] [ T ] } } cond" }
 115     { $code "X [ Y ] [ Z [ T ] [ no-cond ] if ] if" }
 116 }
 117 { $errors "Throws a " { $link no-cond } " error if none of the test quotations yield a true value." }
 118 { $examples
 119     { $code
 120         "{"
 121         "    { [ dup 0 > ] [ \"positive\" ] }"
 122         "    { [ dup 0 < ] [ \"negative\" ] }"
 123         "    [ \"zero\" ]"
 124         "} cond"
 125     }
 126 } ;
 127
 128 HELP: no-cond
 129 { $description "Throws a " { $link no-cond } " error." }
 130 { $error-description "Thrown by " { $link cond } " if none of the test quotations yield a true value. Some uses of " { $link cond } " include a default case where the test quotation is " { $snippet "[ t ]" } "; such a " { $link cond } " form will never throw this error." } ;
 131
 132 HELP: case
 133 { $values { "obj" object } { "assoc" "a sequence of object/word,quotation pairs, with an optional quotation at the end" } }
 134 { $description
 135     "Compares " { $snippet "obj" } " against the first element of every pair, first evaluating the first element if it is a word. If some pair matches, removes " { $snippet "obj" } " from the stack and calls the second element of that pair, which must be a quotation."
 136     $nl
 137     "If there is no case matching " { $snippet "obj" } ", the default case is taken. If the last element of " { $snippet "cases" } " is a quotation, the quotation is called with " { $snippet "obj" } " on the stack. Otherwise, a " { $link no-cond } " error is rasied."
 138     $nl
 139     "The following two phrases are equivalent:"
 140     { $code "{ { X [ Y ] } { Z [ T ] } } case" }
 141     { $code "dup X = [ drop Y ] [ dup Z = [ drop T ] [ no-case ] if ] if" }
 142 }
 143 { $examples
 144     { $code
 145         "SYMBOL: yes  SYMBOL: no  SYMBOL: maybe"
 146         "maybe {"
 147         "    { yes [ ] } ! Do nothing"
 148         "    { no [ \"No way!\" throw ] }"
 149         "    { maybe [ \"Make up your mind!\" print ] }"
 150         "    [ \"Invalid input; try again.\" print ]"
 151         "} case"
 152     }
 153 } ;
 154
 155 HELP: no-case
 156 { $description "Throws a " { $link no-case } " error." }
 157 { $error-description "Thrown by " { $link case } " if the object at the top of the stack does not match any case, and no default case is given." } ;
 158
 159 HELP: recursive-hashcode
 160 { $values { "n" integer } { "obj" object } { "quot" { $quotation "( n obj -- code )" } } { "code" integer } }
 161 { $description "A combinator used to implement methods for the " { $link hashcode* } " generic word. If " { $snippet "n" } " is less than or equal to zero, outputs 0, otherwise calls the quotation." } ;
 162
 163 HELP: cond>quot
 164 { $values { "assoc" "a sequence of pairs of quotations" } { "quot" quotation } }
 165 { $description  "Creates a quotation that when called, has the same effect as applying " { $link cond } " to " { $snippet "assoc" } "."
 166 $nl
 167 "the generated quotation is more efficient than the naive implementation of " { $link cond } ", though, since it expands into a series of conditionals, and no iteration through " { $snippet "assoc" } " has to be performed." }
 168 { $notes "This word is used behind the scenes to compile " { $link cond } " forms efficiently; it can also be called directly,  which is useful for meta-programming." } ;
 169
 170 HELP: case>quot
 171 { $values { "assoc" "a sequence of pairs of quotations" } { "default" quotation } { "quot" quotation } }
 172 { $description "Creates a quotation that when called, has the same effect as applying " { $link case } " to " { $snippet "assoc" } "."
 173 $nl
 174 "This word uses three strategies:"
 175 { $list
 176     "If the assoc only has a few keys, a linear search is generated."
 177     { "If the assoc has a large number of keys which form a contiguous range of integers, a direct dispatch is generated using the " { $link dispatch } " word together with a bounds check." }
 178     "Otherwise, an open-coded hashtable dispatch is generated."
 179 } } ;
 180
 181 HELP: distribute-buckets
 182 { $values { "alist" "an alist" } { "initial" object } { "quot" { $quotation "( obj -- assoc )" } } { "buckets" "a new array" } }
 183 { $description "Sorts the entries of " { $snippet "assoc" } " into buckets, using the quotation to yield a set of keys for each entry. The hashcode of each key is computed, and the entry is placed in all corresponding buckets. Each bucket is initially cloned from " { $snippet "initial" } "; this should either be an empty vector or a one-element vector containing a pair." }
 184 { $notes "This word is used in the implemention of " { $link hash-case-quot } " and " { $link standard-combination } "." } ;
 185
 186 HELP: dispatch ( n array -- )
 187 { $values { "n" "a fixnum" } { "array" "an array of quotations" } }
 188 { $description "Calls the " { $snippet "n" } "th quotation in the array." }
 189 { $warning "This word is in the " { $vocab-link "kernel.private" } " vocabulary because it is an implementation detail used by the generic word system to accelerate method dispatch. It does not perform type or bounds checks, and user code should not need to call it directly." } ;