proposal: Add continuations #20

Closed Jookia opened this issue on 5 Jul - 1 comment

@Jookia Jookia commented on 5 Jul

Okay, this is a bit of a hefty topic so if you don't quite understand what this document says then I encourage a re-read.

Background

First, some background. Let's look at some code here:

Function DoorBouncer Do
  System Print StartText What is your age? EndText
  Set Age To System ReadNumber EndSet
  If Age LessThan 18
  Then System Print StartText Out of here! EndText
  Else System Print StartText Welcome aboard! EndText
  EndIf
  Return
EndFunction

You can see that we have a group of actions and things to do called 'DoorBouncer'. I'm sure you get the idea of what this code kind of is or does, but plainly put: It sets variables, calls things and makes decisions on what to do. Then it returns to the caller. This is about 90% of what every function in every programming language does.

Under the hood, we have a data structure called 'the stack' that handles keeping track of all this. Before we call a function we save what we're doing and where we are to the stack then run the function. When the function returns we restore what we were doing from the saved data. The groups of saved data are known as 'stack frames'.

If your stack gets too big it overflows and bad things happen, so in NewLang we have the 'Jump' statement that says 'don't bother returning to our code, just re-use our stack frame for your stuff'.

Problem 1: Error handling

This is all good, but it does have some limitations.

The first is that you always have to return to your caller. In many languages they have the idea of 'exceptions' which are basically just returns to somewhere deeper in the stack. For example, in psuedocode:

Function OpenFile Do
  Jump System OpenFile /etc/password
EndFunction
Function MyCode Do
  Set MyFile To OpenFile EndSet
  MyFile Write LotsOfData
  MyFile Close
EndFunction
Function MyHandler Do
  Try MyCode
  Except System Print StartText Uh oh error EndText
EndFunction

In this case we have 'MyCode' which does some things that could fail, and when it fails it will print "Uh oh error". In real code the error handler would probably do something useful, but in general the idea is that we put all the error handling in one place instead of copy and pasting it each time.

In order to do this we need two things:

  • The ability to return multiple places down the stack
  • Multiple return points

Problem 2: Random numbers

Let's say you're writing some code and it needs some random numbers. In most languages this is done using side effects, or mutation. For example, imagine this code:

Function MyDice Do
  Set Number To System GetRandomBetween 1 6 EndSet
  Return Number
EndFunction

Every time you call 'MyDice', the result is different. This is as expected, but sooner or later you'll find out this is a headache to manage:

  • You can't easily test your code in a controlled manner
  • There's no way to repeat the same rolls of dices for something like an online game

There's a few ways to solve this, but the way that makes the most sense to me is to support not just returning down the stack but calling down the stack. For example:

Function MyDice Do
  Set Number To GetRandomBetween Call 1 6 EndSet
  Return Number
EndFunction
Function MyRandomHandler Do
  SetFunction GetRandomBetween To Return 6 EndSet
  Try FunctionThatUsesMyDice
EndFunction

In this case FunctionThatUsesMyDice will call MyDice, which will call GetRandomBetween as created by MyRandomHandler. Then when GetRandomBetween returns it will resume in MyDice.

In order to do this we need three things:

  • The ability to call multiple places down the stack
  • The ability to return up the stack

You'll have trouble finding a programming language that supports this because with one stack you can't really do any other work than the current function. Calling down would create a frame ... Where? How?

Solution: Continuations?

I'm going to let you in on a little secret: Call and return are just jumps with extra arguments. Let me show you:

Function WriteHello Next Do
  System Print StartText Hello EndText
  Jump Next
EndFunction
Function WriteHelloWorld Next Do
  Jump WriteHello HERE
  Jump Next
EndFunction

When we call a function, we pass it a 'continuation', which is all the data and knowledge required to continue execution. In this case we have a variable named HERE that supposedly contains that information. When we return from a function we jump to the continuation to finish it. As a concrete example a continuation is a snapshot of the entire stack and the return address to continue execution.

I propose a new statement: Branch. Branch is the same as Jump, but it will pass a new continuation to the next function. Consider this code:

Function WriteHello Next Do
  System Print StartText Hello EndText
  Return
EndFunction
Function WriteHelloWorld Do
  Branch WriteHello
  System Print StartText world! EndText
  Return
EndFunction

This code branches to WriteHello, prints "Hello", then returns. This is just like a jump.
If we change the 'Return' in WriteHello to 'Jump Next', then it will also print "world!". This is just like a call.
The 'Branch' statement lets a function decide to act like a call or jump.

Branch example: Exceptions

Using Branch we can make some basic exceptions and do error handling. Our previous example would look like this:

Function OpenFile ErrorHandler Do
  Jump System OpenFile /etc/password ErrorHandler
EndFunction
Function MyCode ErrorHandler Do
  Set MyFile To OpenFile ErrorHandler EndSet
  MyFile Write LotsOfData ErrorHandler
  MyFile Close ErrorHandler
  Return
EndFunction
Function MyHandler Do
  Branch MyCode
  System Print StartText Uh oh error EndText
EndFunction

In this case we give the ErrorHandler to all functions that might error. They'll jump to the error handler when there's an error or MyCode will return, bypassing MyHandler's code

Branch example: Request/response

This one's a little more complicated:

Function WriteWord Giver Do
  System Print StartText The word is: EndText
  Set Word To Branch Giver EndSet
  System Print Word
EndFunction
Function Main Do
  Set Resume To Branch WriteWord EndSet
  Jump Resume StartText Hello EndText
  System Print StartText Oh dear! EndText
EndFunction

This is a very basic example of using multiple continuations. Here's how it works:

  • Main calls WriteWord with its continuation
  • WriteWord prints "The word is"
  • WriteWord calls main's continuation with its own continuation
  • Main jumps to WriteWord's continuation with the word "Hello"
  • WriteWord prints "Word" and returns on behalf of Main

At some point here there are two stacks in use: Main's stack and WriteWord's stack.

Concerns

Implementing this is a big decision and requires answers to the following:

  • How do we implement this efficiently? Copying the entire program's stack each time isn't a good idea
  • How do we handle resource cleanup if we dispose of a continuation?

Because everything is immutable, implementing algebraic effects or coroutines would require some form of mutation to ensure the continuation being called is up to date. I don't have a mechanism for that yet.

Other solutions considered

Continuation passing style with some kind of glue (like monads?) could work instead of continuations for error handling and other glue.

Would just having multiple stacks be easier to understand? Like threads or fork()? Then an exception handler would just be a supervisor.

Arrows and pipelines for composing complex systems seem too hard to understand.

Closing in favor of coroutines (#21)

@Jookia Jookia closed this issue 9 days ago
Labels

Priority
default
Milestone
No milestone
Assignee
No one
1 participant
@Jookia