Today World News Online

Importance of Survival Skills

What is a continuation?


What is a continuation? By the end of this episode, we will have gone
over this concept. You will understand it. You will see why you’re likely already using
continuations, even if you don’t know it yet, and what you can do with continuations. Hello, my name is Eric Normand, and I help
people thrive with Functional Programming. Continuations became important in scheme. They were used as part of the compiler as
a…continuations were used as a compiler implementation technique. We will go over a little bit how that’s done. What is a continuation? That is the main part of this episode. Continuations have to do with how functions
are called and then returned. Imagine a typical scenario — you have Function
A which does some work, calls Function B, and then does some more work with the return
value from B. When Function A calls B, what actually has to happen? You’re passing control to another function,
you’re going to push onto the stack a new stack frame and record in that stack frame
where to return to. After you do a jump, a go-to, to run that
function, where does the return statement take you back? You have to write that down as a pointer,
just write it down. You also have to write down all the arguments
into the stack. Then, when you jump to the Function B, it
knows where to look up the arguments and then it also knows where to return when it’s done. That’s how the function calls work and the
stack works. Notice we pushed this pointer onto the stack
along with the arguments, but what if we made it an argument? What if we made that pointer an argument,
instead of something to check when you are about to return? Instead of a pointer, what if we made it into
a function that you could call? Basically, you do x equals b, and then you
have some more code. You’re saving the return value of b. I said b, and I did parentheses with my fingers. It’s x equals call b, so b(). You have the return value of b stored in x. After b returns, it’s going to get saved to
x, and then you’re going to do some more stuff. What if you made a function that was just
that, some more stuff? Also, assigns that stuff to x, the return
value to x. This is a function you’ve packaged up. Instead of a pointer to jump there, you just
make it into a function. You pass that to b. Now, b, instead of calling return, could just
call the function that’s an argument. In Scheme, it’s called k. It’s the continuation. Just imagine you add an argument to your function
b. It’s called k. Then at the end of the function, when it’s
done, it calls k. That does the continuation of what a was doing. Now, typically, when you return, you’re returning
a value. That value is useful. To get that value that’s returned from b,
you make it an argument to k. k is a function of one argument, and b will just call that
with whatever value it would have returned. Now, imagine you did this with every function. Every function, you added an argument called
k — that was the continuation — and it was one argument. Instead of having a return statement, you
just called k. Of course, because it’s a return statement,
it’s the last thing your function will ever do before it’s over. That means that it’s always in tail position. We talked about that in a previous episode. There’s a tail call removal, where, if you’re
in tail position, meaning it’s the last call, the last call of a function call of the function
— a function that’s made out of other function calls — The last function call before you
return, that’s called the tail position. Because you’ve threaded this k through every
function call — this is a different k each time — you’ve turned your program inside-out
and nested it to the right, instead of going straight down, every function call is in tail
position. Which means that every function call can be
optimized into a go-to, and you never have to return. You don’t have to return, because there’s
no return statements used anymore. They’re just always calling k, the next thing,
the next thing, and the next thing. You don’t need a stack anymore, because the
stack’s main job is to keep track of where to go back, how to return. You’re not returning, so you don’t need a
stack. You need one frame to store the current arguments. You just thread that k through there, and
you have this style of programming is called continuation passing style. Now, this is not a pleasant style to write
code in, but your compiler can turn your straight-line, imperative, “Do this, do this, do this, call
that,” nested function calls, you can do all that. Turn that into continuation passing style,
and then it has this really nice property, that you don’t need a stack. It has other properties. For instance, because it’s a function, and
functions are first-class, you can save it somewhere. Just know about that. We’ll talk about it in a second. I don’t know if this rings a bell to you,
but if you’re a JavaScript programmer, you’re often calling a function that has a callback. That callback is going to get called with
the result of that asynchronous function. If you do Ajax, the response to your Ajax
request is going to get passed to a function sometime in the future. What typically happens is you have, “This
Ajax needs this callback, and then that callback makes another Ajax request, and so it has
another callback. That one makes another one, and it has another
callback…” You have this deeply-nested callback chain. That is just continuation passing style. It’s one of the reasons why I say that JavaScript
is one of the best things to happen to functional programming in a long time. People are doing continuation passing style
without even knowing it. They just picked it up, because they had to. This thing that was this arcane, functional
programming style idea from compiler theory is now a thing [laughs] that people are writing
their code in. They know it’s not very ergonomic. It forces you to break up your program to
the right, so you’re deeply nested. It’s hard to coordinate things. It’d be much better to write it straight up
and down, but they’re learning it. They understand its limitations. They understand how to sequence things by
calling the next continuation, the next continuation. Just as an aside, the new stuff in JavaScript
called async/await. I say new, relatively new. It lets you write straight-line code, but
you put await in there in front of something that would be asynchronous, and it just waits. It looks like it waits. Really, internally, the compiler is turning
that into a continuation passing style, or in the JavaScript world, called a callback
chain style. I don’t know what they call it. It’s callbacks in JavaScript. It looks straight up and down, straight line,
like, “I can do this. Then I do this step, then I do this step,
and I wait for this step. Then I do this step. I wait for this step.” Putting those awaits in there, it’ll get turned
into continuation passing style. It’s an ergonomics issue. It doesn’t really add any functionality, but
it’s a really nice bit of ergonomics. All right, back to the main thing. What are these useful for? Oh, that’s what I said in the beginning, like
why you might be using them already. If you’re doing JavaScript, you’re already
doing continuations. What are these useful for? Notice, we’ve gotten rid of the stack. That’s nice. We don’t have this problem of stack overflow
anymore. The Scheme folks, the people who invented
Scheme, published a lot of papers about how the function call, before Scheme, was actually
a very heavyweight thing. You wouldn’t want little, bitty functions,
because it would eat into your performance. You’d make big functions, with 20, 30 lines
of code in them. You do a whole bunch of stuff in them. Then, just for convenience, for programmer
convenience, you’d have another function you would call that would do this common routine. You wouldn’t treat them like, they were too
heavyweight to say, “I’m just naming this one operation with a new name, and I’ll wrap
it in a new function.” It was too heavyweight for that. What they showed was that function calls are
very lightweight. That, especially if you do this continuation
passing style, you can make it just like go-to. You don’t even need to return anymore. You’re just passing a few arguments on the
stack, the same stack frame you had before, and you’re doing a jump. You don’t even have to remember where you
were, although you do. It’s part of the Clojure of the continuation,
if you’re curious. Because it’s a function, that was function
was built in a certain environment. It has certain state. Anyway, it just showed that function calls
could be super, super efficient, just about as efficient as a go-to. You could use them wherever you wanted, and
they were a good compiler technique. What can you do with them, besides make nice
compilers? One thing is, just like in the JavaScript
world when you have callbacks, is you can add asynchrony in there. I could, instead of calling k, my function
could put k on a queue to be called later. That’s what JavaScript does. It’s not done directly. There’s some other, like the networking engine,
if you’re doing Ajax. The Ajax happens, and it gets put on a queue
when it’s done as an event. There’s an event loop. There’s a lot of machinery there. In essence, what you’re doing is you’re putting
the continuation onto the queue. Because things are round robin, and they’re
taking turns, you’re able to share a processor between multiple timelines, even though there’s
only really one thread. These are often called co-routines. Another thing that you can do with continuations
is the same kind of stuff you might do with stack manipulation in function calls. For instance, you could implement exceptions. You could have exception handling, where the
continuation is wrapped in something that will do a finally or do a catch on an exception
being thrown. Then it’s going to continue after the try-catch
block was finished. Anything that you would do, typically think
would require a language-level implementation, if you’ve got access to those continuations,
you can do a lot of stuff. That’s how Scheme manages to do so much language-level
stuff, but in the language itself. All right, so, let’s recap. Continuations are a way of representing the
rest of the calculation. After I return from this function, what else
do I need to do? They are wrapped up in a function, and the
argument is the return value of the thing that you’re calling. There’s a style called continuation passing
style, where you replace all return values with calls to the continuation, to the next
continuation. If you do this, you don’t need a stack. The stack is implicit in those function calls. You can also use continuations as a means
of inserting some indirection. Instead of actually calling the continuation,
you could put the continuation onto a queue. You could hand it to something that monitors
it or something, makes sure it succeeds, it completes correctly. Maybe it’ll retry it, something like that. Anything you can do with a function, boom,
now, you’ve got that continuation as a function. You can implement exception handling, things
like that. All right, so, if you found this episode useful,
you can find all the past episodes at lispcast.com/podcast. There, you’ll find audio, video, and text
versions of all of the past episodes. You’ll also find links to subscribe to the
podcast, and also find me on social media. Social being the keyword. I’ve got email, Twitter, LinkedIn. I love to get into discussions with people,
so please reach out. This has been my thought on functional programming. My name is Eric Normand. Thank you for listening, and rock on.

Leave a Reply

Your email address will not be published. Required fields are marked *

Proudly powered by WordPress