diff options
Diffstat (limited to 'README.org')
| -rw-r--r-- | README.org | 829 |
1 files changed, 829 insertions, 0 deletions
diff --git a/README.org b/README.org new file mode 100644 index 0000000..fb6fc24 --- /dev/null +++ b/README.org @@ -0,0 +1,829 @@ +* GTWIWTG + +*Generators The Way I Want Them Generated* + +(Technically not generators, but iterators.) + +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 +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/). + +#+begin_src lisp + +(ql:quickload :gtwiwtg) +(use-package :gtwiwtg) + +#+end_src + +** First, Some Action + +Here are a few examples to show you what you can do. A more involved +example apears at the end of the document, following the tutorial. + +*** All The Primes + +#+begin_src lisp + +> (defun prime-p (n) + "Naive test for primes." + (loop + :for x :from 2 :upto (sqrt n) + :when (zerop (mod n x)) :do (return nil) + :finally (return t))) + +> (defun all-primes () + "Creates a generator that produces an infinite series of primes." + (filter! *'prime-p (range :from 2))) + +> (take 10 (all-primes)) ;; (2 3 5 7 11 13 17 19 23 29) + +#+end_src + +*** Fun With Fibonacci + +#+begin_src lisp + +> (defun fibs () + "Creates an infinite series of Fibonacci numbers." + (from-recurrence + (lambda (n-1 n-2) (+ n-1 n-2)) + 1 0)) + +;; First ten Fibonacci numbers +> (take 10 (fibs)) ;; (1 2 3 5 8 13 21 34 55 89) + +;; Just the 40th Fibonacci number, indexed from 0 +> (car (pick-out '(40) (fibs))) ;; 267914296 + +#+end_src + + +*** Cartesian Products + +#+begin_src lisp + +> (defun cartesian-product (list &rest lists) + "A generator for the Cartesian product of a some lists" + (if (null lists) + (map! 'list (seq list)) + (inflate! (lambda (elem) + (map! (lambda (tail) (cons elem tail)) + (apply 'cartesian-product lists))) + (seq list)))) + +> (collect (cartesian-product '(1 2 3) '(a b c) '("foo" "bar"))) +((1 A "foo") (1 A "bar") (1 B "foo") (1 B "bar") (1 C "foo") (1 C "bar") + (2 A "foo") (2 A "bar") (2 B "foo") (2 B "bar") (2 C "foo") (2 C "bar") + (3 A "foo") (3 A "bar") (3 B "foo") (3 B "bar") (3 C "foo") (3 C "bar")) + + +#+end_src + +*** Subsets + +#+begin_src lisp + +(defun powerset (list) + "Generate the set of all subsets of a given set." + (if (null list) (seq (list nil)) + (concat! (powerset (cdr list)) + (map! (lambda (sub) (cons (car list) sub)) + (powerset (cdr list)))))) + +> (collect (powerset '())) +(NIL) + +> (collect (powerset '(1))) +(NIL (1)) + +> (collect (powerset '(1 2))) +(NIL (2) (1) (1 2)) + +> (collect (powerset '(1 2 3))) +(NIL (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) + +> (collect (powerset '(1 2 3 4))) +(NIL (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) + (1 2 4) (1 2 3) (1 2 3 4)) + + +#+end_src + +Note: The above is just for demonstration purposes and is much slower +than a version you'd write without generators. Something like: + +#+begin_src lisp + +(defun powerset (xs) + (if (null xs) (list nil) + (let ((subsets (powerset (cdr xs)))) + (append subsets + (mapcar (lambda (subset) (cons (car xs) subset)) + subsets))))) +#+end_src + +The "vanilla CL" version is MUCH faster, but may not be possible if +you're generating powersets of very long lists. The trade off, as +usual, is between speed and memory. + +*** A Kind Of Grep + +#+begin_src lisp + +> (defun grepper (pattern file) + (filter! (lambda (idx-line) (search pattern (second idx-line))) + (zip! (range) (file-lines file)))) + + +> (for (idx line) (grepper "defun" "examples.lisp") + (format t "~4a: ~a~%" idx line)) + + +12 : (defun prime-p (n) +19 : (defun all-primes () +37 : (defun fibs () +52 : (defun fill-and-insert (idx elem vec buffer) +69 : (defun thread-through (elem vec) +86 : (defun perms (vec) +104 : ;; (defun perms (vec) +115 : (defun grepper (pattern file) + +#+end_src + +** Tutorial + +GTWIWTG is a tiny library for creating and using generators. + +If you have never heard of generators before, let me offer *a* +definition, but not *the* definition. + +For the purposes of this library, a generator is an object that can +produce a series of values, one value at a time. Generators are +sometimes convenient when you want to deal with series that are too +long to fit into memory. They also help when you want to generate +sequential data using recurrence relations, as in the Fibonacci +example above. + +*** Three Kinds Of Function + +In GTWIWTG, there are three kinds of functions. + +1. functions that *construct* generators +2. functions that *combine* generators +3. functions and macros that *consume* generators. + +*** The Breadwinning Constructors + +The two most common generator constructors are: + +- `(range &key (from 0) to (by 1) inclusive)` +- `(seq sequence)` + +Here are some examples using `range` and `seq` to make generators. + +#+begin_src lisp + + ;; all positive integers starting at 0 +> (range) + +#<GTWIWTG::GENERATOR! {1001A7DF63}> + + ;; positive integers from 0 to 9 +> (range :to 10) + +#<GTWIWTG::GENERATOR! {1001A90CA3}> + +;; positive integers from 0 to 10 +> (range :to 10 :inclusive t) + +#<GTWIWTG::GENERATOR! {1001A90CA3}> + +;; numbers between 4.0 and -15.7 incremented by -0.44 +> (range :from 4 :to -15.7 :by -0.44) + +#<GTWIWTG::GENERATOR! {1001B09D63}> + +;; the characters in the string "hello" +> (seq "hello") + +#<GTWIWTG::GENERATOR! {1001B93E63}> + +;; the symbols in the list +> (seq '(h e l l o)) + +#<GTWIWTG::GENERATOR! {1001BAB273}> + +;; the symbols in the vector +> (seq #('h 'e 'l 'l 'o)) + +#<GTWIWTG::GENERATOR! {1001BE4883}> + +#+end_src + +As you can see, generators are objects. Nothing is generated until you +consume a generator. As a quick, but greatly impoverished, example, +consider this: + +#+begin_src lisp + +;; get the first 4 numbers from the range starting at 20 +> (take 4 (range :from 20)) + +(20 21 22 23) + +#+end_src + +*** Other Constructors + +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. + +You can see some of these in action in the examples section at the top of this document. + +*** The Combination and Transformation Functions + +You can create more intersting and more specific generators by using a +few higher-order functions to combine and transform simple generators. + +These transformations are desirable because they can be performed +before any elements are produced. + +That is, if you think of a generator as a computation that produces a +series of values, then transformation functions allow you to +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. + +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.] + +Here are some simple examples of their use: + +#+begin_src lisp + +;; map cons over two generators +> (map! #'cons (times 3) + (range :from 8)) + +#<GTWIWTG::GENERATOR! {1001CB28D3}> + +;; consuming the above using collect +> (collect (map! #'cons (times 3) (range :from 8))) + +((0 . 8) (1 . 9) (2 . 10)) + +;; Notice that map! stops generating after 3 steps even though +;; (range :from 8) is an infinite generator. This is because (times 3) +;; only generates 3 values. + +;; get just the even values from a generator: +> (collect (filter! #'evenp (times 10))) + +(0 2 4 6 8) + +;; generate (times N) for each N in the range 1 to 4 +> (for x (inflate! #'times (range :from 1 :to 4 :inclusive t)) + (when (zerop x) (terpri)) + (princ x) (princ #\Space)) + +0 ; (times 1) +0 1 ; (times 2) +0 1 2 ; (times 3) +0 1 2 3 ; (times 4) + +#+end_src + +*** 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 + 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 `!`.) + +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 +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 +same generator to one such function at two argument positions, then +an error will be raised and new the generator will not be built. + +Internally, the library keeps track of whether or not generators have +been combined with others. Don't quote me on it, but I *think* that the +library will prevent you from making generators with surprising +(i.e. erroneous) behavior. + + +Here is an example to show you the illegal behavior: + +#+begin_src lisp + +> (let ((ten-times (times 10))) + (zip! ten-times ten-times)) + +; Evaluation aborted on #<SIMPLE-ERROR "~@<The assertion ~S failed~:[.~:; ~ + with ~:*~{~S = ~S~^, ~}.~]~:@>" {10046A61D3}>. + +#+end_src + +The gist is that we tried to zip a generator with itself. Such +behavior is not allowed. + +An ongoing goal is to make those errors nicer to look at so that you +can more easily pin-point where you goofed. + +*** The Fundamental Consumer + +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*) + +Every other consumer in `GTWIWTG` uses `for` under the hood. + +Here is how it looks when you use it: + +#+begin_src lisp + +> (for x (times 3) + (print x)) + +0 +1 +2 + +> (for (x y) (zip! (seq "hello") (range)) + (format t "~a -- ~a~%" x y) + (when (= 4 y) + (princ "world!") + (terpri)) + +h -- 0 +e -- 1 +l -- 2 +l -- 3 +o -- 4 +world! + +> (let* ((ten-times (times 10)) + (doubled (map! (lambda (x) (* 2 x)) ten-times)) + (incremented (map! #'1+ doubled)) + (indexed (zip! (range) incremented))) + (for (index number) indexed + (princ index) + (princ " -- ") + (princ number) + (terpri))) + +0 -- 1 +1 -- 3 +2 -- 5 +3 -- 7 +4 -- 9 +5 -- 11 +6 -- 13 +7 -- 15 +8 -- 17 +9 -- 19 + +#+end_src + +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. + +On each iteration, the variables in the binding form are bound to +successive values generated by the generator form. Notice that you do +not need to inline your generator form, you can build it up and pass +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]. + +*** Generators are Consumed at Most Once + +Even if you don't think you're "using up" the whole generator, a +generator can only be passed to a single consumer. Once that consumer +finishes, the generator is consumed. Here is an example: + +#+begin_src lisp + +>(let ((foo (seq "foobar"))) + (print (take 2 foo)) + (print (collect foo))) + +(#\f #\o) +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 +been consumed in its entirety. + +That is, even when the whole sequence was not actually generated, a +consuming form leaves its generator in an unusable state. This +approach has been taken in order to automatically close streams for +stream-backed generators - i.e. it has been done in the spirit of +letting you not have to think about how generators work. + +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 +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 +the old one left off. + +E.g. + +#+begin_src lisp + +> (defvar *resumable-evens* + (make-resumable! (filter! 'evenp (range :from 1)))) +*RESUMABLE-EVENS* + +> (take 10 *resumable-evens* ) +(2 4 6 8 10 12 14 16 18 20) + +> (setf *resumable-evens* (resume! *resumable-evens*)) +#<RESUMABLE-GENERATOR! {10049A7F63}> + +> (take 10 *resumable-evens*) +(22 24 26 28 30 32 34 36 38 40) + +#+end_src + +*** The Accumulating Consumer + +The next most common consuming form is `fold`, which lets you consume +values produced by a generator while accumulating some data along the +way. + +Here is how you would do a classic summing operation: + +#+begin_src lisp +> (fold (sum 0) (x (times 10)) + (+ sum x)) +45 +#+end_src + +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`. + +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)`. + +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)`. + +The `fold` form returns the final value of the accumulator. + +Here are some more folds: + +#+begin_src lisp + +;; some funky calculation + +> (fold (acc 0) + ((x y) (zip! (times 10) (range :by -1))) + (sqrt (+ acc (* x y)))) +#C(0.444279 8.986663) + +;; Example: building a data structure + +> (fold (plist nil) + ((key val) + (zip! (seq '(:name :occupation :hobbies)) + (seq '("buckaroo banzai" + "rocker" + ("neuroscience" "particle physics" "piloting fighter jets"))))) + (cons key (cons val plist))) + + (:HOBBIES ("neuroscience" "particle physics" "piloting fighter jets") + :OCCUPATION "rocker" :NAME "buckaroo banzai") + +#+end_src + + + +*** The Remaining Consumers + +All of the remaining consumers are regular functions that have been +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 + +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 +> (pick-out '(1 4) (seq "generators")) +(#\e #\r) + +;; you can do this in any order +> (pick-out '(4 1) (seq "generators")) +(#\r #\e) + +;; you can even repeat indices +> (pick-out '(4 1 1 4 2) (seq "generators")) +(#\r #\e #\e #\r #\n) +#+end_src + +*** Anaphoric Consumer Macros + +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: + +#+begin_src lisp + +> (use-package :gtwiwtg) ;; gets you the core package +> (use-package :gtwiwtg.anaphora) ;; gets you the two extra anaphoric consumers + +;; ordinary for +> (for x (times 3) (print x)) + +0 +1 +2 + +;; anaphoric for +> (afor (times 3) (print it)) ;; the variable IT is provided by AFOR +0 +1 +2 + +;; ordinary fold +> (fold (sum 0) (x (times 10)) (+ sum x)) +45 + +;; anaphoric fold +> (afold 0 (times 10) (+ acc it)) ;; variables IT and ACC are provided by AFOLD +45 +#+end_src + + + +*** Making New Generators + +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 + +Additionally, if your generator needs to perform cleanup after it is +consumed, you can implement the `:after` method combination for the method + +- `(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, +which is why they are not exported symbols. But if you want to make +your own generators you can. + +A silly example: + +#+begin_src lisp + +> (defclass countdown (gtwiwtg::generator!) + ((value :accessor countdown-value + :initarg :value + :initform 0))) + +> (defmethod gtwiwtg::next ((g countdown)) + (decf (countdown-value g))) + +> (defmethod gtwiwtg::has-next-p ((g countdown)) + (plusp (countdown-value g))) + +;; you might also want a constructor + +> (defun countdown (n) (make-instance 'countdown :value n)) + +;; now you can use it: + +> (for x (countdown 4) (print x)) + +3 +2 +1 +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 +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: + +#+end_srclisp + +> (with-generator (gen (seq "a1b2c3")) + (when (gtwiwtg::has-next-p gen) + (princ (gtwiwtg::next gen)) + (terpri))) +a + +#+end_src + +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 +ever *will* need it, but the library provides it just in case. + +** The Permutations Example + +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!`. + +#+begin_src lisp + +(defun perms (vec) + "Creates a generator that produces all of the permutations of the + vector VEC, one at a time." + (if (= 1 (length vec)) (seq (list vec)) + (let ((elem (elt vec 0)) + (subperms (perms (make-array (1- (length vec)) + :displaced-to vec ; share vec's memory + :displaced-index-offset 1 + :element-type (array-element-type vec))))) + (inflate! (lambda (subperm) (thread-through elem subperm)) + subperms)))) +#+end_src +The basic flow is: + +1. single out the first element of the vector +2. make a generator for permutations of the remainder of the vector +3. return a generator that "adds back" the singled out element at + 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 +"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 +we "add back" the singled out element. + +#+begin_src lisp +(defun thread-through (elem vec) + "Creates a generator that produces a series of N vectors of length + N, where N is one greater than the length of VEC. The vectors + produced by this generator have the same contents as VEC but have ELEM + inserted at each possible spot, N spots in all. + + Note: The generator reuses the memory that it returns on each step. If + you intend to collect the values of the generator, you should copy + them on each iteration." + + (let ((buffer (concatenate 'vector vec (list elem)))) ;; reusable buffer + (map! (lambda (idx) + (fill-and-insert idx elem vec buffer) + buffer) + (range :from 0 :to (length vec) :inclusive t)))) + +#+end_src + +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: + +#+begin_src lisp + +(defun fill-and-insert (idx elem vec buffer) + "A utilty function that modifies BUFFER. + +The length of BUFFER is assumed to be one greater than the length of +VEC. + +This function fills the first IDX fields of BUFFER with the first IDX +fields of VEC. It fills the field of BUFFER at IDX with ELEM. And it fills +the remaining fields of BUFFER with the remaining fields of VEC. +" + + (loop :for i :below (length buffer) + :when (= i idx) :do (setf (aref buffer idx) elem) + :when (< i idx) :do (setf (aref buffer i) + (aref vec i)) + :when (> i idx) :do (setf (aref buffer i) + (aref vec (1- i)))) ) + +#+end_src + + +And here's a quick demo of its use: + +#+begin_src lisp + +(for perm (perms "abcd") + (print (concatenate 'string perm))) + +"abcd" +"bacd" +"bcad" +"bcda" +"acbd" +"cabd" +"cbad" +"cbda" +"acdb" +"cadb" +"cdab" +"cdba" +"abdc" +"badc" +"bdac" +"bdca" +"adbc" +"dabc" +"dbac" +"dbca" +"adcb" +"dacb" +"dcab" +"dcba" + +#+end_src + +We could have generated all 121645100408832000 permutations of +"generators are cool", and, though it would have taken us an eternity +(a little more than 1000 years on a single core of my machine), the +memory consumption would stay at an even keel. + + + |