Hacker News new | past | comments | ask | show | jobs | submit login

reading the comments here is pretty painful. inasmuch as the call stack seems to be so central to people's perception of what computing is.

if you look at it from the assembly perspective, its just a jump thats been augmented with state (the closure) and additional parameters. i think trying to describe it as a snapshot, or multiple returns, is confusing since it describes them in terms of their stack behaviors.

the easiest way to think about them is to add an implicit argument to each function, which is the place to return to (jump to with the context, augmented with the return value). call it c. return x is c(x).

there is no longer any stack or implicit return target (above me). removing that common control flow assumption lets you make all sorts of different plumbing and get into an arbitrarily deep amount of trouble (the good kind and the bad kind).

call/cc has a pretty natural implementation in this model (heap allocated activation records)

but as someone else mentioned if you choose the simple continuation model, that makes a lot of choices for you in the runtime and the compiler. common complaint from compiler land is that it makes it difficult to reason about reordering later on. you also lean really heavily on the gc to clean up the frames that the stack was taking care of for you (see charlie on the mta)




At the assembly level, we are always working with continuation passing style. Normal calls are implemented by pushing their "return address" on the stack and then jumping to it after the procedure has finished. Formally, this is exactly a continuation.

However, all continuations here are linear (or rather affine - called at most once) and this allows you to allocate and free "closures" for your continuations with a stack discipline.


Formally, it is no such thing. Assembly language programs in the conventional style save registers into the stack, and that's also where they put arguments when there are too many to put into the arg registers.


> all continuations here are linear (or rather affine - called at most once)

Does the term 'linear' just not exist in this context, or does it have a different meaning?


Linear means called exactly once. Linearity requires proof that the value is definitely used, which is tricky. Affine types are more common in practice, even though people will call them linear.


How does this relate to linear(/affine) as in e.g. y = mx (+ b) ?


It was suggested on LtU that Girard explicitly addressed this connection, although it may still be somewhat rarefied; see the "Added in print" note at the bottom of logical p. 131 of http://www.sciencedirect.com/science/article/pii/01680072889... .


I wondered the same! It seems to have to do with Girard's idea that linear logic involves 'additive' and 'multiplicative' 'universes' (all words in quotes because I've only skimmed to try to get an idea—even the editors of TCS apparently found the paper unreferee-able). See logical p. 3 (physical p. 4) of http://iml.univ-mrs.fr/~girard/linear.pdf . (How exponentials fit into the picture I don't know.)

Then drdeca (https://news.ycombinator.com/item?id=14684219) 's explanation of why affine logic is so called seems plausible, but I haven't looked into it.


It's related to linear logic and affine logic, and both are kinda related to linear algebra I think.

With linear algebra, a function f is linear if, for any a,b, f(a+b)=f(a)+f(b)

Suppose there is a vending machine that sells soda for $1 each (doesn't have a menu, just dispenses the soda, for simplicity). If you put in $1, you get a soda. If you put in $1+$1, you get a soda + a soda.

The amount of soda you get is linear in the amount of money you put in.

This might not be a correct explanation of why it is called linear.

Also I don't really understand how the affine fits in this analogy, other than that "affine" is a somewhat weaker assumption than linear.

I hope someone can give a better answer than I did, because I thought I knew the answer, but when I tried to explain it, I found that I did not really know the answer.


> the easiest way to think about them is to add an implicit argument to each function, which is the place to return to (jump to with the context, augmented with the return value). call it c. return x is c(x). there is no longer any stack or implicit return target

That model doesn't help you when functions do not have an implicit argument and you cannot add one, and the run-time has a stack (which you like and want), and you want continuations anyway.

It certainly doesn't help if you're debugging something with continuations and they are not implemented that way; or only helps you so far.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: