effective

KO | EN

gitlite — search

#hacktoberfest #react #ai #go #golang #android #rust #deep-learning #linux #docker #java #windows #awesome-list #ios

(★ 16)

Messing around with delimited continuations, fibers, and algebraic effects

effective Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# A Simple Virtual Machine with Effects

Each thread of execution in this VM is called a `Fiber`. A Fiber is unique, can be sent between threads, but can not be copied. It has:

- A local stack
- Some bytecode
- A program counter

Which is pretty neat.

An *effect* is basically a dynamically-scoped function. *System injection* is leveraging effects so that the host runtime can interact with the VM.

# A simple example
Here's the stack of an example fiber running a program—the `[X]` denote stack frames

```
[A] 1 2 [B] 3 4
```

Let's say we want to print `4` using system injection. First thing we do is execute the `print` effect. This checks the frames `[A]` and `[B]` for handlers. Not surprisingly, there are none.

For this reason, `4` is popped off the stack and wrapped up with the name of the effect; the `Fiber` itself then returns this wrapped `print|4` effect. This is then handled by the runtime, and the `Fiber` is then resumed by passing in a value. Let's say printing returns zero:

```
[A] 1 2 [B] 3 4 -- initial stack
[A] 1 2 [B] 3   -- system injection
[A] 1 2 [B] 3 0 -- new stack
```

# Introducing handlers
Beautiful. Now, let's say that we are back to the original stack, and want to print again. This time, however, `[A]` has registered an effect *handler*. We've denoted the fact that `[A]` now has a handler with a `*`:

```
[A*] 1 2 [B] 3 4
```

Wow! A handler is just a function that takes a value, and ultimately either returns another value or resumes with a value.

Let's start with the easier of the two cases, that the effect just resumes:

```
[A*]:
    print = v -> resume (v + 1)
```

Let's walk through the call to print again, with this new definition of `print` in place:

```
[A*] 1 2 [B] 3 4
```

Let's say we want to print `4` using effect handling. First thing we do is execute the `print` effect. This checks the frames `[A*]` and `[B]` for handlers. This time, we find a `print` handler on frame `[A*]`.

For this reason, `4` is popped off the stack. We then create a *new* fiber, and initialize it with the print handler function:

```
[A*] 1 2 [B] 3 4 -- initial stack

[A*] 1 2 [B] 3 -- not active
[C] 4          -- active handler stack
```

We then run this function:

```
[A*] 1 2 [B] 3 -- not active
[C] 5          -- active after `(v + 1)`
```

And then invoke `resume`. When `resume` is invoked, we pop `5` off the stack, destroy the handling stack, push `5` on to the original stack, and resume execution:

```
[A*] 1 2 [B] 3 -- not active
[C]            -- resume 5

[A*] 1 2 [B] 3 5 -- active
```

Resume mirrors the path of a system injection, only the system that is handling the code is not the parent system.

# Something a bit more complex
This is the trivial case; let us now discuss the more complex case, when `resume` is not invoked and a value is returned instead.

Here's the original stack, yet again:

```
[A*] 1 2 [B] 3 4
```

And the handler is now:

```
[A*]:
    print = v -> (v - 1)
```

Note that the handler does not resume and instead returns the value minus one. With this new handler in mind, let's simulate the system:

Let's say we want to print `4` using effect handling. First thing we do is execute the `print` effect. This checks the frames `[A*]` and `[B]` for handlers. This time, we find a `print` handler on frame `[A*]`.

For this reason, `4` is popped off the stack. We then create a *new* fiber, and, like before, initialize it with the print handler function:

```
[A*] 1 2 [B] 3 4 -- initial stack

[A*] 1 2 [B] 3 -- not active
[C] 4          -- active handler stack

[A*] 1 2 [B] 3 -- not active
[C] 3          -- active after (v - 1)
```

No surprises so far; we now execute the return instruction, like this were a normal function:

```
[A*] 1 2 [B] 3 -- not active
3              -- returned
```

Returning just replaces the topmost stack frame with the value to be returned. This is true in all cases.

So now, the question becomes, what happens next?

When an effect is called, we keep track of the stack frame that caused the effect to be raised. so, for instance:

```
[A*] 1 2 [B] 3
[C:A*] 3
```

The stack frame `[C]` was created because of an effect defined in `[A*]`, hence: `[C:A*]`.

When we return, we check whether the stack frame was created because of an effect. because `[C]` was obviously created because of an effect, instead of returning from `[C]`, we instead return from `[A*]`:

```
[A*] 1 2 [B] 3 -- first stack
[C:A*] 3       -- before return

3              -- first stack after return
```

Alright, so the clever among you may have noticed something: The second stack for handling the effect runs once, then is destroyed; the stack below it is never modified.

For this reason, the combination of effects and handlers, with the resume operation, create delimited continuations, which can be used to implement control flow.

# Fibers

effective

effective Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

effective

effective Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README