core/combinators/combinators-docs.factor

   1 USING: arrays assocs combinators.private effects
   2 generic.standard help.markup help.syntax kernel quotations
   3 generalizations
   4 sequences sequences.private words ;
   5 IN: combinators
   6
   7 ARTICLE: "cleave-combinators" "Cleave combinators"
   8 "The cleave combinators apply multiple quotations to a single value or set of values."
   9 $nl
  10 "Two quotations:"
  11 { $subsections
  12     bi
  13     2bi
  14     3bi
  15 }
  16 "Three quotations:"
  17 { $subsections
  18     tri
  19     2tri
  20     3tri
  21 }
  22 "An array of quotations:"
  23 { $subsections
  24     cleave
  25     2cleave
  26     3cleave
  27     4cleave
  28 }
  29 "Cleave combinators provide a more readable alternative to repeated applications of the " { $link keep } " combinators. The following example using " { $link keep } ":"
  30 { $code
  31     "[ 1 + ] keep"
  32     "[ 1 - ] keep"
  33     "2 *"
  34 }
  35 "can be more clearly written using " { $link tri } ":"
  36 { $code
  37     "[ 1 + ]"
  38     "[ 1 - ]"
  39     "[ 2 * ] tri"
  40 } ;
  41
  42 ARTICLE: "spread-combinators" "Spread combinators"
  43 "The spread combinators apply multiple quotations to multiple values. The asterisk (" { $snippet "*" } ") suffixed to these words' names signifies that they are spread combinators."
  44 $nl
  45 "Two quotations:"
  46 { $subsections bi* 2bi* }
  47 "Three quotations:"
  48 { $subsections tri* 2tri* }
  49 "An array of quotations:"
  50 { $subsections spread }
  51 "Spread combinators provide a more readable alternative to repeated applications of the " { $link dip } " combinators. The following example using " { $link dip } ":"
  52 { $code
  53     "[ [ 1 + ] dip 1 - ] dip 2 *"
  54 }
  55 "can be more clearly written using " { $link tri* } ":"
  56 { $code
  57     "[ 1 + ] [ 1 - ] [ 2 * ] tri*"
  58 }
  59 "A generalization of the above combinators to any number of quotations can be found in " { $link "combinators" } "." ;
  60
  61 ARTICLE: "apply-combinators" "Apply combinators"
  62 "The apply combinators apply a single quotation to multiple values. The at sign (" { $snippet "@" } ") suffixed to these words' names signifies that they are apply combinators."
  63 { $subsections bi@ 2bi@ tri@ 2tri@ }
  64 "A pair of condition words built from " { $link bi@ } " to test two values:"
  65 { $subsections both? either? }
  66 "All of the apply combinators are equivalent to using the corresponding " { $link "spread-combinators" } " with the same quotation supplied for every value." ;
  67
  68 ARTICLE: "dip-keep-combinators" "Preserving combinators"
  69 "Sometimes it is necessary to temporarily hide values on the datastack. The " { $snippet "dip" } " combinators invoke the quotation at the top of the stack, hiding some number of values:"
  70 { $subsections dip 2dip 3dip 4dip }
  71 "The " { $snippet "keep" } " combinators invoke a quotation and restore some number of values to the top of the stack:"
  72 { $subsections keep 2keep 3keep } ;
  73
  74 ARTICLE: "curried-dataflow" "Curried dataflow combinators"
  75 "Curried cleave combinators:"
  76 { $subsections bi-curry tri-curry }
  77 "Curried spread combinators:"
  78 { $subsections bi-curry* tri-curry* }
  79 "Curried apply combinators:"
  80 { $subsections bi-curry@ tri-curry@ }
  81 { $see-also "dataflow-combinators" } ;
  82
  83 ARTICLE: "compositional-examples" "Examples of compositional combinator usage"
  84 "Consider printing the same message ten times:"
  85 { $code ": print-10 ( -- ) 10 [ \"Hello, world.\" print ] times ;" }
  86 "if we wanted to abstract out the message into a parameter, we could keep it on the stack between iterations:"
  87 { $code ": print-10 ( message -- ) 10 [ dup print ] times drop ;" }
  88 "However, keeping loop-invariant values on the stack doesn't always work out nicely. For example, a word to subtract a value from each element of a sequence:"
  89 { $code ": subtract-n ( seq n -- seq' ) swap [ over - ] map nip ;" }
  90 "Three shuffle words are required to pass the value around. Instead, the loop-invariant value can be partially applied to a quotation using " { $link curry } ", yielding a new quotation that is passed to " { $link map } ":"
  91 { $example
  92   "USING: sequences prettyprint ;"
  93   ": subtract-n ( seq n -- seq' ) [ - ] curry map ;"
  94   "{ 10 20 30 } 5 subtract-n ."
  95   "{ 5 15 25 }"
  96 }
  97 "Now consider the word that is dual to the one above; instead of subtracting " { $snippet "n" } " from each stack element, it subtracts each element from " { $snippet "n" } "."
  98 $nl
  99 "One way to write this is with a pair of " { $link swap } "s:"
 100 { $code ": n-subtract ( n seq -- seq' ) swap [ swap - ] curry map ;" }
 101 "Since this pattern comes up often, " { $link with } " encapsulates it:"
 102 { $example
 103   ": n-subtract ( n seq -- seq' ) [ - ] with map ;"
 104   "30 { 10 20 30 } n-subtract ."
 105   "{ 20 10 0 }"
 106 }
 107 { $see-also "fry.examples" } ;
 108
 109 ARTICLE: "compositional-combinators" "Compositional combinators"
 110 "Certain combinators transform quotations to produce a new quotation."
 111 { $subsections "compositional-examples" }
 112 "Fundamental operations:"
 113 { $subsections curry compose }
 114 "Derived operations:"
 115 { $subsections 2curry 3curry with prepose }
 116 "These operations run in constant time, and in many cases are optimized out altogether by the " { $link "compiler" } ". " { $link "fry" } " are an abstraction built on top of these operations, and code that uses this abstraction is often clearer than direct calls to the above words."
 117 $nl
 118 "Curried dataflow combinators can be used to build more complex dataflow by combining cleave, spread and apply patterns in various ways."
 119 { $subsections "curried-dataflow" }
 120 "Quotations also implement the sequence protocol, and can be manipulated with sequence words; see " { $link "quotations" } ". However, such runtime quotation manipulation will not be optimized by the optimizing compiler." ;
 121
 122 ARTICLE: "booleans" "Booleans"
 123 "In Factor, any object that is not " { $link f } " has a true value, and " { $link f } " has a false value. The " { $link t } " object is the canonical true value."
 124 { $subsections f t }
 125 "A union class of the above:"
 126 { $subsections boolean }
 127 "There are some logical operations on booleans:"
 128 { $subsections
 129     >boolean
 130     not
 131     and
 132     or
 133     xor
 134 }
 135 "Boolean values are most frequently used for " { $link "conditionals" } "."
 136 { $heading "The f object and f class" }
 137 "The " { $link f } " object is the unique instance of the " { $link f } " class; the two are distinct objects. The latter is also a parsing word which adds the " { $link f } " object to the parse tree at parse time. To refer to the class itself you must use " { $link POSTPONE: POSTPONE: } " or " { $link POSTPONE: \ } " to prevent the parsing word from executing."
 138 $nl
 139 "Here is the " { $link f } " object:"
 140 { $example "f ." "f" }
 141 "Here is the " { $link f } " class:"
 142 { $example "\\ f ." "POSTPONE: f" }
 143 "They are not equal:"
 144 { $example "f \\ f = ." "f" }
 145 "Here is an array containing the " { $link f } " object:"
 146 { $example "{ f } ." "{ f }" }
 147 "Here is an array containing the " { $link f } " class:"
 148 { $example "{ POSTPONE: f } ." "{ POSTPONE: f }" }
 149 "The " { $link f } " object is an instance of the " { $link f } " class:"
 150 { $example "USE: classes" "f class-of ." "POSTPONE: f" }
 151 "The " { $link f } " class is an instance of " { $link word } ":"
 152 { $example "USE: classes" "\\ f class-of ." "word" }
 153 "On the other hand, " { $link t } " is just a word, and there is no class which it is a unique instance of."
 154 { $example "t \\ t eq? ." "t" }
 155 "Many words which search collections confuse the case of no element being present with an element being found equal to " { $link f } ". If this distinction is important, there is usually an alternative word which can be used; for example, compare " { $link at } " with " { $link at* } "." ;
 156
 157 ARTICLE: "conditionals-boolean-equivalence" "Expressing conditionals with boolean logic"
 158 "Certain simple conditional forms can be expressed in a simpler manner using boolean logic."
 159 $nl
 160 "The following two lines are equivalent:"
 161 { $code "[ drop f ] unless" "swap and" }
 162 "The following two lines are equivalent:"
 163 { $code "[ ] [ ] ?if" "swap or" }
 164 "The following two lines are equivalent, where " { $snippet "L" } " is a literal:"
 165 { $code "[ L ] unless*" "L or" } ;
 166
 167 ARTICLE: "conditionals" "Conditional combinators"
 168 "The basic conditionals:"
 169 { $subsections if when unless }
 170 "Forms abstracting a common stack shuffle pattern:"
 171 { $subsections if* when* unless* }
 172 "Another form abstracting a common stack shuffle pattern:"
 173 { $subsections ?if }
 174 "Sometimes instead of branching, you just need to pick one of two values:"
 175 { $subsections ? }
 176 "Two combinators which abstract out nested chains of " { $link if } ":"
 177 { $subsections cond case }
 178 { $subsections "conditionals-boolean-equivalence" }
 179 { $see-also "booleans" "bitwise-arithmetic" both? either? } ;
 180
 181 ARTICLE: "dataflow-combinators" "Dataflow combinators"
 182 "Dataflow combinators express common dataflow patterns such as performing a operation while preserving its inputs, applying multiple operations to a single value, applying a set of operations to a set of values, or applying a single operation to multiple values."
 183 { $subsections
 184     "dip-keep-combinators"
 185     "cleave-combinators"
 186     "spread-combinators"
 187     "apply-combinators"
 188 }
 189 "More intricate dataflow can be constructed by composing " { $link "curried-dataflow" } "." ;
 190
 191 ARTICLE: "combinators-quot" "Quotation construction utilities"
 192 "Some words for creating quotations which can be useful for implementing method combinations and compiler transforms:"
 193 { $subsections cond>quot case>quot alist>quot } ;
 194
 195 ARTICLE: "call-unsafe" "Unsafe combinators"
 196 "Unsafe calls declare an effect statically without any runtime checking:"
 197 { $subsections call-effect-unsafe execute-effect-unsafe } ;
 198
 199 ARTICLE: "call" "Fundamental combinators"
 200 "The most basic combinators are those that take either a quotation or word, and invoke it immediately. There are two sets of these fundamental combinators. They differ in whether the compiler is expected to determine the stack effect of the expression at compile time or the stack effect is declared and verified at run time."
 201 $nl
 202 { $heading "Compile-time checked combinators" }
 203 "With these combinators, the compiler attempts to determine the stack effect of the expression at compile time, rejecting the program if the effect cannot be determined. See " { $link "inference-combinators" } "."
 204 { $subsections call execute }
 205 { $heading "Run-time checked combinators" }
 206 "With these combinators, the stack effect of the expression is checked at run time."
 207 { $subsections POSTPONE: call( POSTPONE: execute( }
 208 "Note that the opening parenthesis is actually part of the word name for " { $snippet "call(" } " and " { $snippet "execute(" } "; they are parsing words, and they read a stack effect until the corresponding closing parenthesis. The underlying words are a bit more verbose, but they can be given non-constant stack effects:"
 209 { $subsections call-effect execute-effect }
 210 { $heading "Unchecked combinators" }
 211 { $subsections "call-unsafe" }
 212 { $see-also "effects" "inference" } ;
 213
 214 ARTICLE: "combinators-connection" "Combinator Connections"
 215 "Factor provides several convenient implementations of combinators, specifically for simpler "
 216 "cases with few stack arguments. This page will document combinators that are "
 217 "similar in application, but may be different in effect."
 218 { $list
 219   { { $link map } " generalizes " { $link call } " over " { $link sequence } "s of objects." }
 220   { { $link napply } " generalizes " { $link bi@ } " and " { $link tri@ }
 221     " for a number of objects on the stack." }
 222   { { $link cleave } " generalizes " { $link bi } " and " { $link tri }
 223     " for equal numbers of quotations and objects on the stack." }
 224   { { $link spread } " generalizes " { $link  bi* } " and "  { $link tri* } " "
 225     "for performing a set of operations that ignore the top n values of the stack, keeping "
 226     "them as is." }
 227 }
 228 ;
 229
 230 ARTICLE: "combinators" "Combinators"
 231 "A central concept in Factor is that of a " { $emphasis "combinator" } ", which is a word taking code as input."
 232 { $subsections
 233     "call"
 234     "dataflow-combinators"
 235     "conditionals"
 236     "looping-combinators"
 237     "compositional-combinators"
 238     "combinators.short-circuit"
 239     "combinators.smart"
 240     "combinators-quot"
 241     "generalizations"
 242     "combinators-connection"
 243 }
 244 "More combinators are defined for working on data structures, such as " { $link "sequences-combinators" } " and " { $link "assocs-combinators" } "."
 245 { $see-also "quotations" } ;
 246
 247 ABOUT: "combinators"
 248
 249 HELP: call-effect
 250 { $values { "quot" quotation } { "effect" effect } }
 251 { $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." }
 252 { $examples
 253   "The following two lines are equivalent:"
 254   { $code
 255     "call( a b -- c )"
 256     "( a b -- c ) call-effect"
 257   }
 258 } ;
 259
 260 HELP: execute-effect
 261 { $values { "word" word } { "effect" effect } }
 262 { $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." }
 263 { $examples
 264   "The following two lines are equivalent:"
 265   { $code
 266     "execute( a b -- c )"
 267     "( a b -- c ) execute-effect"
 268   }
 269 } ;
 270
 271 HELP: execute-effect-unsafe
 272 { $values { "word" word } { "effect" effect } }
 273 { $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." }
 274 { $warning "If the word being executed has an incorrect stack effect, undefined behavior will result. User code should use " { $link POSTPONE: execute( } " instead." } ;
 275
 276 { call-effect call-effect-unsafe execute-effect execute-effect-unsafe } related-words
 277
 278 HELP: cleave
 279 { $values { "x" object } { "seq" "a sequence of quotations with stack effect " { $snippet "( x -- ... )" } } }
 280 { $description "Applies each quotation to the object in turn." }
 281 { $examples
 282     "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:"
 283     { $code
 284         "! Equivalent"
 285         "{ [ p ] [ q ] [ r ] [ s ] } cleave"
 286         "[ p ] keep [ q ] keep [ r ] keep s"
 287     }
 288 } ;
 289
 290 HELP: 2cleave
 291 { $values { "x" object } { "y" object }
 292           { "seq" "a sequence of quotations with stack effect " { $snippet "( x y -- ... )" } } }
 293 { $description "Applies each quotation to the two objects in turn." } ;
 294
 295 HELP: 3cleave
 296 { $values { "x" object } { "y" object } { "z" object }
 297           { "seq" "a sequence of quotations with stack effect " { $snippet "( x y z -- ... )" } } }
 298 { $description "Applies each quotation to the three objects in turn." } ;
 299
 300 { bi tri cleave } related-words
 301
 302 HELP: spread
 303 { $values { "objs..." "objects" } { "seq" "a sequence of quotations with stack effect " { $snippet "( x -- ... )" } } }
 304 { $description "Applies each quotation to the object in turn." }
 305 { $examples
 306     "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 a nested series of " { $link dip } "s:"
 307     { $code
 308         "! Equivalent"
 309         "{ [ p ] [ q ] [ r ] [ s ] } spread"
 310         "[ [ [ p ] dip q ] dip r ] dip s"
 311     }
 312 } ;
 313
 314 { bi* tri* spread } related-words
 315
 316 HELP: to-fixed-point
 317 { $values { "object" object } { "quot" { $quotation ( ... object(n) -- ... object(n+1) ) } } { "object(n)" object } }
 318 { $description "Applies the quotation repeatedly with " { $snippet "object" } " as the initial input until the output of the quotation equals the input." }
 319 { $examples
 320     { $example
 321         "USING: combinators kernel math prettyprint sequences ;"
 322         "IN: scratchpad"
 323         ": flatten ( sequence -- sequence' )"
 324         "    \"flatten\" over index"
 325         "    [ [ 1 + swap nth ] [ nip dup 2 + ] [ drop ] 2tri replace-slice ] when* ;"
 326         ""
 327         "{ \"flatten\" { 1 { 2 3 } \"flatten\" { 4 5 } { 6 } } } [ flatten ] to-fixed-point ."
 328         "{ 1 { 2 3 } 4 5 { 6 } }"
 329     }
 330 } ;
 331
 332 HELP: alist>quot
 333 { $values { "default" quotation } { "assoc" "a sequence of quotation pairs" } { "quot" "a new quotation" } }
 334 { $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." }
 335 { $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." } ;
 336
 337 HELP: cond
 338 { $values { "assoc" "a sequence of quotation pairs and an optional quotation" } }
 339 { $description
 340     "Calls the second quotation in the first pair whose first quotation yields a true value. A single quotation will always yield a true value."
 341     $nl
 342     "The following two phrases are equivalent:"
 343     { $code "{ { [ X ] [ Y ] } { [ Z ] [ T ] } } cond" }
 344     { $code "X [ Y ] [ Z [ T ] [ no-cond ] if ] if" }
 345 }
 346 { $errors "Throws a " { $link no-cond } " error if none of the test quotations yield a true value." }
 347 { $examples
 348     { $example
 349         "USING: combinators io kernel math ;"
 350         "0 {"
 351         "    { [ dup 0 > ] [ drop \"positive\" ] }"
 352         "    { [ dup 0 < ] [ drop \"negative\" ] }"
 353         "    [ drop \"zero\" ]"
 354         "} cond print"
 355         "zero"
 356     }
 357 } ;
 358
 359 HELP: no-cond
 360 { $description "Throws a " { $link no-cond } " error." }
 361 { $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." } ;
 362
 363 HELP: case
 364 { $values { "obj" object } { "assoc" "a sequence of object/quotation pairs, with an optional quotation at the end" } }
 365 { $description
 366     "Compares " { $snippet "obj" } " against the first element of every " { $link pair } ", evaluating the first element if it is a " { $link callable } ". If a pair matches, " { $snippet "obj" } " is removed from the stack and the second element of that pair (which must be a " { $link quotation } ") is " { $link call } "ed."
 367     $nl
 368     "If the last element of the " { $snippet assoc } " is a quotation, that quotation is the default case. The default case is called with the " { $snippet "obj" } " on the stack, if there is no other case matching " { $snippet obj } "."
 369     $nl
 370     "If all the cases have failed and there is no default case to execute, a " { $link no-case } " error is raised."
 371     $nl
 372     "The following two phrases are equivalent:"
 373     { $code "{ { X [ Y ] } { Z [ T ] } } case" }
 374     { $code "dup X = [ drop Y ] [ dup Z = [ drop T ] [ no-case ] if ] if" }
 375 }
 376 { $errors { $link no-case } " if the input matched none of the options and there was no trailing quotation." }
 377 { $examples
 378     { $example
 379         "USING: combinators io kernel ;"
 380         "IN: scratchpad"
 381         "SYMBOLS: yes no maybe ;"
 382         "maybe {"
 383         "    { yes [ ] } ! Do nothing"
 384         "    { no [ \"No way!\" throw ] }"
 385         "    { maybe [ \"Make up your mind!\" print ] }"
 386         "    [ drop \"Invalid input; try again.\" print ]"
 387         "} case"
 388         "Make up your mind!"
 389     }
 390 } ;
 391
 392 HELP: no-case
 393 { $description "Throws a " { $link no-case } " error." }
 394 { $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." } ;
 395
 396 HELP: deep-spread>quot
 397 { $values { "seq" sequence } { "quot" quotation } }
 398 { $description "Creates a new quotation from a sequence of quotations that applies each quotation to a stack element in turn." }
 399 { $see-also spread } ;
 400
 401 HELP: cond>quot
 402 { $values { "assoc" "a sequence of pairs of quotations" } { "quot" quotation } }
 403 { $description "Creates a quotation that when called, has the same effect as applying " { $link cond } " to " { $snippet "assoc" } "."
 404 $nl
 405 "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." }
 406 { $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." } ;
 407
 408 HELP: case>quot
 409 { $values { "default" quotation } { "assoc" "a sequence of pairs of quotations" } { "quot" quotation } }
 410 { $description "Creates a quotation that when called, has the same effect as applying " { $link case } " to " { $snippet "assoc" } "."
 411 $nl
 412 "This word uses three strategies:"
 413 { $list
 414     "If the assoc only has a few keys, a linear search is generated."
 415     { "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." }
 416     "Otherwise, an open-coded hashtable dispatch is generated."
 417 } } ;
 418
 419 HELP: distribute-buckets
 420 { $values { "alist" "an alist" } { "initial" object } { "quot" { $quotation ( obj -- assoc ) } } { "buckets" "a new array" } }
 421 { $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." }
 422 { $notes "This word is used in the implementation of " { $link hash-case-quot } " and " { $link standard-combination } "." } ;
 423
 424 HELP: dispatch
 425 { $values { "n" "a fixnum" } { "array" "an array of quotations" } }
 426 { $description "Calls the " { $snippet "n" } "th quotation in the array." }
 427 { $warning "This word 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." } ;