diff options
| -rw-r--r-- | README.org | 164 |
1 files changed, 82 insertions, 82 deletions
@@ -7,12 +7,12 @@ The GTWIWTG library is meant to be small, explorable, and understandable. The source code is meant to be legible and straightforward. -Every symbol exported from the `GTWIWTG` package has a useful +Every symbol exported from the =GTWIWTG= package has a useful docstring. Many docstrings include examples of use. ** Installation -The `gtwiwtg` system is available from [quicklisp](https://www.quicklisp.org/beta/) and [ultralisp](https://ultralisp.org/). +The =gtwiwtg= system is available from [quicklisp](https://www.quicklisp.org/beta/) and [ultralisp](https://ultralisp.org/). #+begin_src lisp @@ -182,10 +182,10 @@ In GTWIWTG, there are three kinds of functions. The two most common generator constructors are: -- `(range &key (from 0) to (by 1) inclusive)` -- `(seq sequence)` +- =(range &key (from 0) to (by 1) inclusive)= +- =(seq sequence)= -Here are some examples using `range` and `seq` to make generators. +Here are some examples using =range= and =seq= to make generators. #+begin_src lisp @@ -243,17 +243,17 @@ consider this: Here is a brief listing of the other generator constructors in GTWIWTG: -- `(times n)` is shorthand for `(range :to n)` -- `(repeater &rest args)` repeats its arguments in order, looping forever. -- `(noise &optional (arg 1.0))` an infinite sequence of random numbers -- `(from-thunk thunk)` an infinite sequence of calls to `(funcall thunk)` -- `(from-thunk-until thunk &optional until clean-up)` like `from-thunk`, but stops when `(funcall until)` is non nil. Runs the thunk `clean-up` when done. -- `(from-thunk-times thunk n)` like `from-thunk` but stops after `n` times. -- `(from-recurrence fn n-1 &rest n-m)` generate using a recurrence relation -- `(from-input-stream stream reader)` turn a stream into a generator -- `(file-lines file)` a file-backed generator. Produces lines from that file (strings) -- `(file-chars file)` a file-backed generator. Produces characters from that file. -- `(file-bytes file)` a file-backed generator. Produces bytes from that file. +- =(times n)= is shorthand for =(range :to n)= +- =(repeater &rest args)= repeats its arguments in order, looping forever. +- =(noise &optional (arg 1.0))= an infinite sequence of random numbers +- =(from-thunk thunk)= an infinite sequence of calls to =(funcall thunk)= +- =(from-thunk-until thunk &optional until clean-up)= like =from-thunk=, but stops when =(funcall until)= is non nil. Runs the thunk =clean-up= when done. +- =(from-thunk-times thunk n)= like =from-thunk= but stops after =n= times. +- =(from-recurrence fn n-1 &rest n-m)= generate using a recurrence relation +- =(from-input-stream stream reader)= turn a stream into a generator +- =(file-lines file)= a file-backed generator. Produces lines from that file (strings) +- =(file-chars file)= a file-backed generator. Produces characters from that file. +- =(file-bytes file)= a file-backed generator. Produces bytes from that file. You can see some of these in action in the examples section at the top of this document. @@ -271,14 +271,14 @@ incrementally "build up" a desired computation before it is run. The three core transformation functions are: -- `(map! fn gen &rest gens)` makes a new generator by mapping `fn` over other generators -- `(filter! pred gen)` makes a new generator by discarding values that dont satisfy `pred` -- `(inflate! fn gen)` The function `fn` should make new generators using the values produced by the generator `gen`. The `inflate!` function combines all those "intermediate" generators into a single generator. +- =(map! fn gen &rest gens)= makes a new generator by mapping =fn= over other generators +- =(filter! pred gen)= makes a new generator by discarding values that dont satisfy =pred= +- =(inflate! fn gen)= The function =fn= should make new generators using the values produced by the generator =gen=. The =inflate!= function combines all those "intermediate" generators into a single generator. -Admittedly, the behavior of `inflate!` is difficult to grok by reading a description. +Admittedly, the behavior of =inflate!= is difficult to grok by reading a description. Once you begin to use it, however, it becomes indispensible. -[NB: `inflate!` is really a *kind of* monadic bind operator in disguise.] +[NB: =inflate!= is really a *kind of* monadic bind operator in disguise.] Here are some simple examples of their use: @@ -318,32 +318,32 @@ Here are some simple examples of their use: *** The Other Combinations and Transformations -- `(zip! gen1 &rest gens)` is shorthand for `(map! #'list gen1 gen2 ...)` -- `(indexed! gen)` is shorthand for `(zip! (range) gen)` -- `(concat! gen &rest gens)` concatenates generators -- `(skip! n gen)` produces a generator by skipping the first `n` values in `gen` -- `(skip-while! pred gen)` produces a generator by skipping elements of `gen` while `pred` is `t` -- `(merge! comp gen1 gen2 &rest gens)` emulates the behavior of `merge` but for generators -- `(truncate! n gen)` produces at most `n` of the values produced by `gen` -- `(inject! fn gen)` shorthand for `(map! (lambda (x) (funcall fn x) x) gen)` -- `(intersperse! gen1 gen2 &rest gens)` returns a generator that +- =(zip! gen1 &rest gens)= is shorthand for =(map! #'list gen1 gen2 ...)= +- =(indexed! gen)= is shorthand for =(zip! (range) gen)= +- =(concat! gen &rest gens)= concatenates generators +- =(skip! n gen)= produces a generator by skipping the first =n= values in =gen= +- =(skip-while! pred gen)= produces a generator by skipping elements of =gen= while =pred= is =t= +- =(merge! comp gen1 gen2 &rest gens)= emulates the behavior of =merge= but for generators +- =(truncate! n gen)= produces at most =n= of the values produced by =gen= +- =(inject! fn gen)= shorthand for =(map! (lambda (x) (funcall fn x) x) gen)= +- =(intersperse! gen1 gen2 &rest gens)= returns a generator that intermingles the values of its argument generators, in the order they appear in the argument list. *** A Word Of Warning! -(Or, there's a reason those forms all end in `!`.) +(Or, there's a reason those forms all end in =!=.) You must be cautious when incrementally building up generators. The reason for caution is that generators cannot be "combined twice". If -you are storing intermediate generators in a `let` binding, for +you are storing intermediate generators in a =let= binding, for example, you may be tempted to pass those bound variables into generator combination functions more than once. If you do, an error will be signalled. _The general rule_ is: if you pass a generator to more than one -combining function (those whose names end in `!`), or if you pass the +combining function (those whose names end in =!=), or if you pass the same generator to one such function at two argument positions, then an error will be raised and new the generator will not be built. @@ -377,9 +377,9 @@ Finally! Once you have built up your generators using *constructors* and *combinations*, you want to actually use them for something. This is where *consumers* come in. -There is one fundamental consumer, a macro, called `for`. (*Triumphant Horns Play*) +There is one fundamental consumer, a macro, called =for=. (*Triumphant Horns Play*) -Every other consumer in `GTWIWTG` uses `for` under the hood. +Every other consumer in =GTWIWTG= uses =for= under the hood. Here is how it looks when you use it: @@ -428,12 +428,12 @@ world! #+end_src -As you can see `for` has 3 basic parts: a *binding form*, a *generator +As you can see =for= has 3 basic parts: a *binding form*, a *generator form*, and a *body*. -The binding form is either a variable, like `x` above, or is a form -suitable for use in the binding form of a `DESTRUCTURING-BIND`, like -`(x y)` above. +The binding form is either a variable, like =x= above, or is a form +suitable for use in the binding form of a =DESTRUCTURING-BIND=, like +=(x y)= above. On each iteration, the variables in the binding form are bound to successive values generated by the generator form. Notice that you do @@ -442,8 +442,8 @@ it in as in the third example above. Finally, the body is evaluated for each iteration. -[Aside: `for` used to be called `iter`, but I didn't want to step on -the toes of `series` and `iterate` users :P]. +[Aside: =for= used to be called =iter=, but I didn't want to step on +the toes of =series= and =iterate= users :P]. *** Generators are Consumed at Most Once @@ -463,7 +463,7 @@ NIL #+end_src Even though you only *seemed* to use the first two members of the -generator `foo`, the `take` form will mark the generator as having +generator =foo=, the =take= form will mark the generator as having been consumed in its entirety. That is, even when the whole sequence was not actually generated, a @@ -477,10 +477,10 @@ You need only remember the rule: Generators Are Consumed At Most Once. *** But Resumable Generators are Possible An exception to the above comes in the form of *resumable* generators. -To make a resumable generator call `(make-resumable! <gen>)` on a +To make a resumable generator call =(make-resumable! <gen>)= on a generator. Once you have passed a resumable generator to a consuming form you can still get some values out of it by passing it to -`resume!`, which will create a brand new generator that picks up where +=resume!=, which will create a brand new generator that picks up where the old one left off. E.g. @@ -504,7 +504,7 @@ E.g. *** The Accumulating Consumer -The next most common consuming form is `fold`, which lets you consume +The next most common consuming form is =fold=, which lets you consume values produced by a generator while accumulating some data along the way. @@ -516,20 +516,20 @@ Here is how you would do a classic summing operation: 45 #+end_src -The syntax is `(fold (acc init) (iter-var gen) update)`. +The syntax is =(fold (acc init) (iter-var gen) update)=. First, you declare and initialize an accumulator variable. In the -above that is the form `(sum 0)`, which declares a variable called -`sum` initialized to `0`. +above that is the form =(sum 0)=, which declares a variable called +=sum= initialized to =0=. Next comes your iteration variable and generator form. These have the -same syntax as `for`. So in the above we bind a variable `x` to each -successive value generated by `(times 10)`. +same syntax as =for=. So in the above we bind a variable =x= to each +successive value generated by =(times 10)=. Finally, you write a *single update form* whose value becomes bound to your -accumulator variable. In the above example `sum` is set to `(+ sum x)`. +accumulator variable. In the above example =sum= is set to =(+ sum x)=. -The `fold` form returns the final value of the accumulator. +The =fold= form returns the final value of the accumulator. Here are some more folds: @@ -562,19 +562,19 @@ Here are some more folds: *** The Remaining Consumers All of the remaining consumers are regular functions that have been -built using `for` and `fold`. They are: +built using =for= and =fold=. They are: -- `(collect gen)` collects the values of `gen` into a list -- `(take n gen)` collects the first `n` values of `gen` into a list -- `(pick-out indices gen)` see example below -- `(size gen)` consumes a generator, returning the number of values it produced -- `(maximum gen)` returns the maximum among the values in gen (subject to change) -- `(minimum gen)` see maximum -- `(average gen)` returns the average of the values produced by gen -- `(argmax fn gen)` returns a pair `(val . x)` where `val` is the value of `gen` for which `(funcal fn val)` is maximal. `x` is `(funcall fn val)` -- `(argmin fn gen)` see argmax +- =(collect gen)= collects the values of =gen= into a list +- =(take n gen)= collects the first =n= values of =gen= into a list +- =(pick-out indices gen)= see example below +- =(size gen)= consumes a generator, returning the number of values it produced +- =(maximum gen)= returns the maximum among the values in gen (subject to change) +- =(minimum gen)= see maximum +- =(average gen)= returns the average of the values produced by gen +- =(argmax fn gen)= returns a pair =(val . x)= where =val= is the value of =gen= for which =(funcal fn val)= is maximal. =x= is =(funcall fn val)= +- =(argmin fn gen)= see argmax -The `pick-out` consumer is interesting enough to see a quick example of: +The =pick-out= consumer is interesting enough to see a quick example of: #+begin_src lisp ;; pick out characters and index 1 and index 4 @@ -592,9 +592,9 @@ The `pick-out` consumer is interesting enough to see a quick example of: *** Anaphoric Consumer Macros -If you would like to use `for` and `fold` macros with a little less +If you would like to use =for= and =fold= macros with a little less visual noise (but sacrificing some of their flexibility), you can use -the `gtwiwtg.anaphora` package. Here's an example: +the =gtwiwtg.anaphora= package. Here's an example: #+begin_src lisp @@ -627,16 +627,16 @@ the `gtwiwtg.anaphora` package. Here's an example: *** Making New Generators -Generators are subclasses of `gtwiwtg::generator!` that have at least +Generators are subclasses of =gtwiwtg::generator!= that have at least two methods specialized on them: -- `(gtwiwtg::next gen)` : advances the generator and gets its next value -- `(gtwiwtg::has-next-p gen)` : checks whether or not the generator has a next value +- =(gtwiwtg::next gen)= : advances the generator and gets its next value +- =(gtwiwtg::has-next-p gen)= : checks whether or not the generator has a next value Additionally, if your generator needs to perform cleanup after it is -consumed, you can implement the `:after` method combination for the method +consumed, you can implement the =:after= method combination for the method -- `(gtwiwtg::stop gen)` : is called by consumers to mark the generator +- =(gtwiwtg::stop gen)= : is called by consumers to mark the generator as stopped. None of the above are meant to be called by users of the library, @@ -672,18 +672,18 @@ A silly example: 0 #+end_src -You can see that `next` ASSUMES that there is a next value. This is -one of the reasons you are not ment to call `next` manually. The -`for` consumer automatically checks that there is a next value before +You can see that =next= ASSUMES that there is a next value. This is +one of the reasons you are not ment to call =next= manually. The +=for= consumer automatically checks that there is a next value before trying to get it. *** The Naughty Consumer Now that the mysteries that make generators go have been explained in -the previous section, you may be tempted to manually call `next` and -`has-next-p` on your generators. If you must do this, you should use -the `with-generator` macro: +the previous section, you may be tempted to manually call =next= and +=has-next-p= on your generators. If you must do this, you should use +the =with-generator= macro: #+end_srclisp @@ -695,7 +695,7 @@ a #+end_src -The `with-generator` form will ensure that the generator is properly +The =with-generator= form will ensure that the generator is properly closed. It could be useful with generators backed by input streams that need a custom logic, or perhaps in some case where you need to interleave operations between multiple generators. I'm not sure if you @@ -705,7 +705,7 @@ ever *will* need it, but the library provides it just in case. One final example to show you what you can do. Here is a function that generates all of the permutations of a sequence passed to it, one at a -time. It is a good example of the usefulness of `inflate!`. +time. It is a good example of the usefulness of =inflate!=. #+begin_src lisp @@ -729,15 +729,15 @@ The basic flow is: each possible spot in each permutation. The interesting bit about this is that we recursively compute -permutation generators for the subvectors of `vec` in a classic -divide-and-conquer way, and then use `inflate!` to combine those +permutation generators for the subvectors of =vec= in a classic +divide-and-conquer way, and then use =inflate!= to combine those "generated sub-generators" into a single generator, which we return. The above code is made significantly noisier by the use of displaced arrays. Displaced arrays let us share memory with the original vector. For each "sub permutation", we create a new generator using a -generator constructor called `thread-through`. This is the part where +generator constructor called =thread-through=. This is the part where we "add back" the singled out element. #+begin_src lisp @@ -759,7 +759,7 @@ we "add back" the singled out element. #+end_src -And this function uses a utility function called `fill-and-insert` +And this function uses a utility function called =fill-and-insert= that just fills a buffer, which I pulled out into its own function for clarity: |