Continuations and Effects
- Delimitted Continuations
- Algebraic effects
Continuations are the work that was going to be done.
In a low level view, the contents of the stack, registers, and program counter are enough. Capturing all that is a pain, but it can be done. The system call
fork for example kind of copies all of that brute force.
Depending how you write an interpreter, the capturing the work to be done can be tricky. Very often we write interpreters using recursive function calls. We are borrowing the host language stack to hold work to be done. If you explicitly manage the interpreter stack, it becomes more clear how to talk about the continuation.
Relationship between monads and continuations
mother of all monads. Buyt also Filinkski paper. refiication and reflection - In a langue with effects like ocaml, we can reflect / reify the exceptions or mutation into their pure form that uses monad dsiciplaine. Converting native ocaml exception to Either exceptions https://www.reddit.com/r/haskell/comments/1cyajx/the_mother_of_all_monads_school_of_haskell/ some caustic yet intriguing discussion. The embedding is (x »=) like how cps embedding is (x $)?
https://gist.github.com/sjoerdvisscher/a56a286ccfabce40e424 This is interesting. Using cont monad in swift probably to deal with the lack of higher kinded types. Similar to rust problem
Contexts and Holes
Are continuations functions?
standard ml contiutation signature
type 'a cont val callcc : ('a cont -> 'a) -> 'a val throw : 'a cont -> 'a -> 'b val isolate : ('a -> unit) -> 'a cont type 'a control_cont val capture : ('a control_cont -> 'a) -> 'a val escape : 'a control_cont -> 'a -> 'b
throw is apply. The question is do we really want
(->) to be interchangeable. In a CPS implementation, the are
The stack as a closure
A closure is an value that contains a code pointer and captured data. To invoke a closure, you need to know some things about it’s layout, but not everything. It hides it’s implementation. Closures are objects in this sense.
Closures sometimes only store minimal amounts of environment, but in a naive implementation can store much more, maybe a copy of every variable in local scope for example instead of just the variables it closes over.
The conventional C stack has a return address and all the context of what has been going on. This really is a function pointer and environment. It is a closure. This closure however does not rely on the garbage collector to reclaim its memory, but so what?
Oleg delimcc an implemntation of delimitted continuations for the This uses exceptions (trap frames) as stack markers. In ocaml, at every try block puts handlers in the stack. These are marks It then copies the stack up to these points. mentions camlcallcc by xavier leroy https://xavierleroy.org/software.html It’s pretty small actually. Very interesting. It is copying the stack quite literally.
A delimitted continuation is a mapping between contexts… ? lwt fibers using delimcc
libmprompt A 64-bit C/C++ library that aims to implement robust and efficient multi-prompt delimited control.
Marks racket docs on conituation karks Compiler and runtik support for continuation marks The stack exists. You can put marks on it that could be searched for.
One shot continuationns can be called at most or exactly once. This is simpler and more efficient to implement and covers many (but not all) use cases
call with current continuation Relationship to double negation encoding
An argument against call-cc undelimited continuations are covalues rather than functions
What even are algebraic effects?
Kind of like resumable exceptions. Also kind of like yield-step (exactly like?).
Koka Generalized evidence passing for effect handlers: efficient compilation of effect handlers to C Implementing Algebraic Effects in C libhandler
Interaction trees. THe semantics of a program is a tree of call and response patterns. THe handler is a fold over the tree giving it semantics
High-Level Effect Handlers in C++
Either Err a piggy backs error handling on the regular return mechanisms. Every stack frame needs to be inspected to bubble error up. This is not how native ocaml exceptions are implemented and probably not how many systems do it.
CPS piggybacks other control flow on closure creation mechanisms.
Ocaml is getting an effect system See my ocaml notes for more.
- Efficient compilation of algebraic effect handlers
- effectfuljs. a javascrpt transpiler for effects very cool. multi prompt delim conitautiona too?
- https://www.stephendiehl.com/posts/exotic03.html effect systems are off to the side, but do they help explain lifetimes? https://news.ycombinator.com/item?id=25178437 interesting commments. Oleg talk. Frank language
- divergence as an effect. But also is memory usage an effect
- ocaml algebraic effects. https://github.com/ocaml-multicore/effects-examples https://www.youtube.com/watch?v=z8SI7WBtlcA&feature=emb_title&ab_channel=JaneStreet https://ocamlverse.github.io/content/future_ocaml.html#typed-algebraic-effects https://github.com/ocamllabs/ocaml-effects-tutorial
- There was an andrej bauer video https://www.youtube.com/watch?v=atYp386EGo8&ab_channel=OPLSS What’s Algebraic About Algebraic Effects and Handlers?
- Sandy Maguire and polysemy
- resumable exceptions.
- Related the the python yield stuff.
- Daan Leijen paper https://www.microsoft.com/en-us/research/wp-content/uploads/2016/08/algeff-tr-2016-v2.pdf comes up
- Koka, Eff, F*, Link, Helium
- Daan Leijen Asynchrony with Algerbaic Effects
- Plotkin papers
- Alexis King effects for less https://www.youtube.com/watch?v=0jI-AlWEwYI&ab_channel=Z%C3%BCrichFriendsofHaskell
- https://github.com/ghc-proposals/ghc-proposals/pull/313 delimitted continuation primops ghc proposal. Lots of interestnig discussion
- Pretnar 2015 An Introduction to Algebraic Effects and Handlers Invited tutorial pap https://www.eff-lang.org/handlers-tutorial.pdf
- https://cs.ru.nl/~dfrumin/notes/delim.html delimitted contiunuations
- Eff directly in ocaml Kiselyov Sivaramakrishnan
- algerbaic effects for the rest of us async functions and generators have a different “color”. effects remove the need for this how? common lisp condition system is related? Is another example of resumable exceptions.
Rebvisting coroutines http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.398.9600&rep=rep1&type=pdf Yield - mainstream delimitted continuations. slides http://parametricity.net/dropbox/yield-slides.subc.pdf
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.399.1021&rep=rep1&type=pdf Lazy v Yield - kiselyov sabry peytonjones Inremental linear pretty printing
io.py https://gist.github.com/alexknvl/e15ea9762a58935b28f2 https://github.com/alexknvl/ai-meetup/blob/master/19-09-26-ppl1/ppl-meetup.ipynb probablistic programming https://twitter.com/ezyang/status/1300278419188580353?s=20
https://pypi.org/project/effect/#:~:text=Effect%20is%20a%20library%20for,It%20supports%203.6%20and%20above. effect - as python library
takafumi asrakaki using julia yieldto for a “callcc” https://julialang.zulipchat.com/#narrow/stream/137791-general/topic/call.2Fcc.20for.20Julia.3F.20%28or.20how.20to.20use.20.60yieldto.60%29/near/218188425
https://news.ycombinator.com/item?id=24257488 Anatomy of Lisp. Lisp in small pieces.
Lambda prolog book is drectly talking about semantics in terms of sequents
https://github.com/nornagon/jonesforth/blob/master/jonesforth.S Jones forth tutorail assembly
https://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf The essence of compiling with continuations. Pushing A normal form.