Three Dollar Quill

Okay, yesterday I mentioned continuation passing style, and now I have some more time to try to explain it.

One way to think about continuations is, first, consider the "return" statement. There is some sense in which we can imagine "returning" to be calling a function that never returns. The function in question is "whatever the program does next", and is determined by the caller.

The next step is to go and write functions that actually work like that. For what I'm doing, I wrote functions that don't mutate their inputs, and take other functions like themselves as arguments, as well as utility functions that create such functions from constant values. These results of these functions then take a continuation as an argument and elaborate on it in various ways. This is very hard to talk about completely abstractly, so have some code snippets:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

local function k(const)
    return function(ret)
        return ret(const)
    end
end


local function binop(op)
    return function (left, right)
        return function(ret)
            return left(
                function(r_left)
                    return right(
                        function(r_right)
                            return ret(op(r_left, r_right))
                        end
                    )
                end
            )
        end
    end
end


local add = binop(function(left, right) return left + right end)
local sub = binop(function(left, right) return left - right end)
local mul = binop(function(left, right) return left * right end)
local div = binop(function(left, right) return left / right end)

local eq = binop(function(left, right) return left == right end)

Given an ordinary value, the function k returns a function that takes a continuation, and returns the result of applying that continuation to the value. Thus:

> cps = require "cps"
> cps_func = cps.k("Hello, World!")
> cps_func(print)
Hello, World!

The functions returned from binop do a bit more. Basically, given two functions that take a continuation, they apply op to the results of those functions and pass the result of that to the continuation. Furthermore, they're written to take advantage of Lua's tail-call optimizations, so the above logic is expressed in terms of "Given the input functions and the continuation, construct new continuations that can be passed to the input functions, in order to eventually pass the result to the original continuation".

I don't really have a solid motivation for implementing this stuff, as such. I guess it's just kind of mindbending that this stuff can work at all.

There's more code than the stuff above, but it basically just amounts to an "if" expression, and code using the above to implement factorial. The current implementation is based around using an accumulator, but I guess I could actually get rid of the accumulator-y stuff, since the tail-call optimizations are more baked into the libraries now.

Hm. I just tried, and now I'm realizing that the time performance of this code is... confusing. I think there might be performance cliffs or something. Needs actual profiling.

One thing I want to figure out here is how best to represent state.

I was going to start this paragraph with the word "basically", and deleted it because it would have been a lie. What I'm trying to figure out is how to add the idea of "this is the equivalent of a statement executing, and it will have an influence on the rest of the execution". Have functions that when passed a continuation, do "read from this storage" or "write to this storage". I think what those look like depend on the semantics I want to express with this stuff, which is kind of up in the air, and has no practical usage to constrain it, unfortunately. So, I guess I'll step away from this for now, maybe try documenting it some at some point.

Other stuff I've been doing... I've been trying out the tutorial for wxGlade, but the structure of the generated Python code bothers me enough (in a "if a human wrote this I wouldn't merge the PR" kind of way) that I've been sort of pondering writing my own generator based on the current one. That's probably not a good idea before I grasp the full usage of wxLocale, though. Because one thing that rubs me wrong is gettext. I haven't actually used gettext or Fluent, but the documentation for the former rubs me the wrong way, while the documentation for the latter doesn't. But, I'm at least intellectually aware that I can't just say "I'm going to use the shiny new thing!" without understanding the integration with the old thing. Maybe I end up not wanting to use wx, I don't know. There are alternatives.

Anyway, that's enough of that for now. I came up with a story idea that I want to try doing, so I'll work on that for a bit later.

And it's late, I'd better wrap up. Good night.