4 ms·
somehow I have no issues understanding call/cc, but shift reset has never clicked for me.
by gpderetta 5y ago
somehow I have no issues understanding call/cc, but shift reset has never clicked for me.
- oshiar53-0 5y agoYou can basically think of call/cc as subroutine + return/throw (break out of control structures), and delimited continuations as yield + next/send in Python. Of course this explanation is heavily simplified.
- ilammy 5y agoYou sound a bit like those people, “git is just directed acyclic graph of objects, it’s all that simple”.
- jasomill 5y ago“A monad is a monoid in the category of endofunctors, what's the problem?” http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html http://james-iry.blogspot.com/2009/05/brief-incomplete-and-m...
- wbl 5y agoThe difference is that that formulation is exactly correct whereas the other ones are not.
- kazinator 5y agoIs git necessarily acyclic? Or is it just that nobody has bothered to contrive a git repo with cycles? It seems possible in principle: via a kind of quining, a git commit can be created whose parent hash is its own. It involves a bit of a tough search.
- anyfoo 5y agoIt’s very likely specified as an acyclic graph (because, without checking, I see no reason why it would not be). So if you made a cyclic graph it would be wrong. It’s possible, likely even, that a lot of git’s implementation and associated tools don’t check for that, because it’s very hard[1] to achieve, but that just means stuff would break in more non-obvious ways. [1] Constructing a cyclic git graph means finding a hash collision, and git uses SHA1 which is known to have weaknesses. With another hash algorithm it might be “practically impossible” instead of “very hard”.
- oshiar53-0 5y agoYou can use the "grafting" feature to emulate rewriting commit parents (but not true rewrite--as in the object itself is not actually modified and some tools do not respect it), so maybe give it a shot
- oshiar53-0 5y agoI know it's oversimplified, but as a poor man's explanation I couldn't really think of a better way to articulate it at the moment
- convolvatron 5y agoI think this is really interesting. I'm in the same boat. and its easy to dismiss the delimited people as being deluded. but a lot of highly developed people think shift/reset is _alot_ easier to work with. I can understand the basic case...but its totally unclear for me how to compose them. this is kind of a fundamental issue about language development...apparently we can get used to all sorts of terrible ideas - which makes evaluating them quite difficult.
- the-smug-one 5y agoThe reduction rules copied from Racket's docs: (reset val) => val (reset E[(shift k expr)]) => (reset ((lambda (k) expr) (lambda (v) (reset E[v])))) ; where E has no reset E is the current-continuation of the expression, and the comment is an invariant to be held. And I think call/cc is this: E[(call/cc k expr)] => ((lambda (k) expr) (lambda (v) E[v])) So imagine a stack like this: g h call/cc my-fun this captures the whole stack. And now imagine: g reset h shift my-fun this only captures h (see how it moves the E in the reduction rules and wraps it in reset). So if I try to store k from shift and call it at a later time it won't reach g, but doing the same with call/cc it would reach g.
- gpderetta 5y agoThanks I think I did get that much, but your example still helps a bit. Some questions: - how does (both formally and from an implementation point of view) does shift find the corresponding reset? Does it relies on some sort of dynamic scoping or does the reset need to be lexically visible from the shift call? It doesn't help that in all the examples shift and resets are always called in the same expression (with shift in a lambda). - Related to the above, how does typing work? Is the captured delimited continuation typed (i.e. does it take parameters of a specific type and returns typed values), and if so, does the typing of shift and reset need to match (racket is dynamically typed so this is not an issue there of course). I have no formal language background, I just implement coroutines and (one shot) continuations for fun (in C++), so the key to my understanding is from an implementation point of view. edit: from a comment elsethread it seems that I should look into effect systems.
- the-smug-one 5y agoAlgebraic effect system = Statically typed delimited continuations, as your edit shows :-). It's dynamically scoped, which is the same as the lexical scope in the untyped lambda calculus. But yes, that is really annoying. Example from Racket REPL: > (require racket/control) > (define f (lambda () (shift k (k 5)))) > (reset (f)) 5
- thealig 5y ago
- dleslie 5y agoI understand it as: shift captures a continuation scope, and reset defines a scope in which a captured continuation can be released.