Created
April 4, 2012 15:21
-
-
Save cgrand/2302625 to your computer and use it in GitHub Desktop.
fair conjunction notes
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Streams were equipped with plus and bind, I removed bind and added join and narrow. | |
| I also added yield which returns the yielded substitution map for the stream (if any) | |
| and step which advances teh computation (was: calling the thunk). | |
| join, like plus, interleaves execution of its two streams. As soon as one yields, the | |
| yielded value is used to narrow the search space of the other stream. | |
| For any stream A, we have: | |
| A = (plus (yield A) (step A)) | |
| The interleaving formula behind join is: | |
| (join A B) = (plus (narrow B (yield A)) (join B (step A))) ; interleaving on the join term | |
| narrow is distributive over plus and join | |
| (narrow (join A B)) = (join (narrow A) (narrow B)) | |
| (narrow (plus A B)) = (plus (narrow A) (narrow B)) | |
| Implementation detail | |
| narrowed streams remember the substitutions map (the "min-yield") which was used to | |
| narrow them so whole streams can be pruned if one tries to narrow a stream with a | |
| substitution incompatible with its min-yield. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment