Fork me on GitHub
#off-topic
<
2017-07-27
>
qqq12:07:30

Why does other schemes / lisps believe that continuations are a good idea?

qqq12:07:50

I've yet to come across a single explaination of how continuations are useful and/or how they make code more clear.

qqq12:07:17

Then, when continuations are mixed together with set! .... code gets really confusing.

alandipert16:07:50

i think in imperative code it's important to be able to "exit early" in the middle of iteration

alandipert16:07:44

but various ways of doing that aren't "expression level"

alandipert16:07:11

ie the call to return in a function doesn't itself evaluate. it's context-sensitive, as it needs to be called inside a function. and so it's a kind of special form

alandipert16:07:44

and so i think part of the appeal of continuation is, it's a way to somewhat align the idea of exiting early with the idea of functional programming

alandipert16:07:22

since return in the context of continuations isn't a special form, it's "just a function"

qqq16:07:35

yeah, upon more reading, the common uses for it are: * early return * implement error handling / exception system * backtracking during search

qqq16:07:05

so I guess in a scheme world this makes sense since "continuation" is a "primitive" that lets you do thihngs that otherwise are "language level constructs"

alandipert16:07:17

i think their utility is also an effect of the collection model in most lisps

alandipert16:07:52

like, in clj we don't feel we need them for early return, because we don't really make open loops in clj. we do lazy seq stuff

qqq16:07:55

what is the 'collection model' ? I have never heard of this phrase

alandipert16:07:13

a term i invented :-) just the style of collection a language advocates, how to represent n things

qqq16:07:14

oh, as in list, vector, maps

qqq16:07:41

"reduced" / loop-recur is pobably closest to early return in clj

alandipert16:07:12

reduced, definitely. i would say loop/recur is closer to tail calls, which are also most useful when you have mutable collections

qqq16:07:30

loop-recur, without an recur, is an early exit 🙂

alandipert16:07:33

or when you want to build a result without building anything intermediate

alandipert16:07:14

but you can't i.e pass a function an argument that's a function, and inside this passed function, there's a recur... since the binding is lexical

qqq16:07:27

you're right

qqq16:07:57

I don't know if this was your original intention, but you've now convinced me continuations are a good thing.

alandipert16:07:20

i'm not so sure they're good as unavoidable

alandipert16:07:29

same as exceptions

alandipert16:07:39

https://gist.github.com/alandipert/9415252 btw, might interest you. experiment of mine from awhile ago

qqq16:07:43

I'm really starting to wish for a racket-jvm and racket-js (this continuation question came from reading racket docs)

alandipert16:07:23

kawa is a really nice jvm scheme, if you haven't seen it

qqq16:07:49

it's racket in particular, with it's DSLs, that I want 🙂

noisesmith17:07:02

Another way of looking at continuations is if you wanted to implement the primitive of “if” on a semantic level rather than a parsing / special form level. It fills some of the roles that a macro would take on (the non syntax related ones)

qqq17:07:23

so I'm looking at porting racket to clojure, and it seems like tye two hardest things are continuations and tail call recursion

qqq17:07:34

err, tail call optimization

noisesmith17:07:58

I have a hunch these things are related pretty strongly

noisesmith17:07:48

self call can automatically turned into recur in tail position of course, generalized tail call optimization can be transformed into usage of trampoline

noisesmith17:07:59

you just need to turn f into a function that returns f

noisesmith17:07:05

and adjust all calls accordingly

noisesmith17:07:19

oh, returns f, which returns a result or g

noisesmith17:07:37

(I wonderi f that’s at all intelligible)

qqq17:07:53

still thinking

noisesmith17:07:41

so you could do a full program transform where every f is turned into a function returning a boxed value or a function to trampoline to

noisesmith17:07:06

then you get generalized tail call jumps

qqq17:07:12

are you saying: assuming we have TCO, continuations can all be resolved by code rewriting ?

noisesmith17:07:05

I’m saying, assuming TCO is impossible in the general case on the JVM (which is the case because of method size limits and the semantics of the JVM goto op) the only way to replace it is turning everything into a trampolined function

noisesmith17:07:20

you replace duplicate the behavior but don’t get the full optimization

qqq17:07:34

okay, I believe the "trampoline as solution to TCO" statement

noisesmith17:07:20

it does duplicate the behavior of not growing the stack, but it isn’t as optimized sadly

qqq17:07:21

I actually do miss TCO, there's a number of algorithms that are easy to write recursively but less elegant as loop-recur

qqq17:07:33

but then I am processing an arbitraryly long list, so I have to loop-recur

noisesmith17:07:55

if they can’t be done with loop recur they can’t be tail call optimized

noisesmith17:07:24

the reason we need recur is not because self calls can’t be automatically optimized, it’s the bugs caused by coders assuming their calls are tail calls when they are not

qqq17:07:24

i believe TCO also works across different functions

qqq17:07:36

whereas loop recur forces it all into one block

noisesmith17:07:39

oh, sorry, I thought you meant self calls, yes I understand

noisesmith17:07:45

and trampoline does help with that usage

noisesmith17:07:59

letfn + trampoline is a nice combo btw

noisesmith17:07:15

since the letfn binding rules let every function refer to every other function to trampoline

noisesmith17:07:32

in fact without trampoline I’d probably never need letfn

qqq17:07:39

how does other languages, like haskell get away with fast tco? iirc they allocate thunks on teh heap, and gc the useless ones, yet somehow manage to make it fast

noisesmith17:07:41

well, they can goto in a general way

noisesmith17:07:52

while jvm can only goto within one method body

noisesmith17:07:18

(and jvm method bodies have limited size)

noisesmith17:07:33

so it can see that a mutual recursion can be jumps between the two lambdas

noisesmith17:07:43

(without stack allocation that is)

noisesmith17:07:50

@qqq you are probably familiar that the standard calling convention from eg. C is that you put your args and space for locals on the stack, then do a jump to the new code with a pointer to where you came from

noisesmith17:07:56

that’s how a function call usually works

qqq17:07:07

yes, I'm familiar with C calling conventions

noisesmith17:07:22

@qqq a TCO says “hey, we never need to come back, so we can throw away all the stack the previous function used right now, and reuse the return pointer”

noisesmith17:07:37

and haskell is able to actually do that on a stack level

noisesmith17:07:42

the jvm intentionally lacks that power

qqq17:07:21

wait, I thought haskell was all spineless tagged -something, where it's all thunks instead of stack

noisesmith17:07:44

OK - I’m describing the general principle, I guess I misunderstand haskell’s internals though

noisesmith17:07:10

it still needs a call stack, and the reusing instead of allocating stack still applies, right?

noisesmith17:07:16

even if it never stack allocates for data

qqq17:07:35

I don't know.

qqq17:07:47

I thought it was lazy thunks on the heap for everything.

qqq17:07:53

But key phrase: I don't know.

qqq17:07:05

because in most languages, when you call a function, you do it strictly

qqq17:07:11

so you push it on the call stack, and wait for it to return

qqq17:07:31

haskell is lazy, so when you 'call a function' in haskell, it just creates a thunk somewhere on the heap, doesn't eval it, returns immediately

qqq17:07:47

and when you try to deref the thunk, it evals it to weak head normal form

qqq17:07:04

and that's everything I know about haskell's execution model

tbaldridge18:07:44

@qqq Haskell is a continuation passing language. Every function takes as an argument the continuation to call into next

tbaldridge18:07:12

that's part of it also being lazy. With proper support from a compiler (e.g. LLVM) true TCO isn't hard. A tailcall is basically: 1) move all your arguments into registers/parts of the stack 2) pop all your locals/args off the stack, 3) push all your new args to the stack, 4) call the new function

tbaldridge18:07:31

Really that's it, TCO is simply saying "remove my stack frame and call X with Y

tbaldridge18:07:19

BTW, some languages like Erjang do full program transformation to get light weight threads/processes on the JVM

qqq18:07:21

in practice, what does this mean if I'm trying to run a language with continuations, like racket, on clojure ?

qqq18:07:28

s/continuations/continuations+tco

tbaldridge18:07:13

on any language that doesn't natively support stack manipulation or TCO, it means you have to go to trampolines, which will be slow

qqq18:07:36

why is haskell not slow?

tbaldridge18:07:37

On some platforms (like chicken scheme which is in C) there's other tricks you can do.

tbaldridge18:07:53

Because it implements all this at the machine code layer, and doesn't have to fight a virtual machine.

tbaldridge18:07:57

TCO in assembly isn't really hard at all, it's just some VM security models restrict your ability to hand set the stack pointer, or to define your own calling conventions.

noisesmith18:07:18

@tbaldridge glad you can describe this stuff more lucidly than I, thanks

tbaldridge18:07:49

Notice how call and ret (http://www.cs.virginia.edu/~evans/cs216/guides/x86.html) on x86 use the stack to store the "return to this place" pointer, and the function pointer. The register SP points to the current head of the stack. That means you can do some really wacky stuff, like change the ret pointer after you've called into a function, or completely change the SP to some other value to jump to a different stack.

tbaldridge18:07:22

setjmp/longjmp have been used for years to implement call/cc like behavior in C. And that's all they really do: save the registers to the stack, then change the SP to point somewhere else: https://en.wikipedia.org/wiki/Setjmp.h

tbaldridge18:07:14

But yeah, none of that exists on the JVM. Or .NET, or Python...

chrisbroome18:07:55

that's awesome info

qqq19:07:32

@tbaldridge : does this imply it is basically impossible to get fast continuations/tco in any scheme that runs on the jvm ?

luxbock19:07:43

Quasar / Pulsar add delimited continuations for the JVM (or fibers / green threads, afaik they are one and the same), by instrumenting the bytecode

tbaldridge19:07:41

@qqq pretty much, you have to define "fast" though

tbaldridge19:07:52

Fast as Java? Fast as Clojure, no I don't think it's possible.

tbaldridge19:07:08

Faster than CPython or some interpreted language, perhaps.

tbaldridge19:07:37

@qqq but to be honest with you continuations and TCO isn't all roses either. I agree with Guido's take on TCO in Python. It actually makes code harder to reason about as whole portions of your stack trace are missing.

tbaldridge19:07:26

So it can be really hard to figure out "how did I get to here from where I started". That's even worse with continuations because you may have jumped into some sort of stack without any information about where I came from.

tbaldridge19:07:48

So while I see TCO and continuations as powerful tools, they do make the code more complex.