Lambda the Ultimate

Sorry about the lack of occurs check. I've been meaning to add it for some time, and I added a half-working version to the master branch just now. Hopefully this will resolve at least some infinite loops.

If you want to try writing something nicer in Eff, you could try Danvy & Filinski's optimised CPS transformation, which currently uses shift/reset. See: https://gist.github.com/orchid-hybrid/715f0b7eba3d902699fa

Are you concerned about performance? Or just that the average handler-implementer can't be trusted with a continuation? Or that even the wisest of handler-implementers shouldn't have to bother with continuations most of the time? Or something else?

Seems like Eff provides a primitive that you'd want to occasionally (often?) abstract over. You could imagine some simple macros that hide the continuation for typical return-once usages.

It seems to me that the continuation argument is superfluous in all use cases except where the continuation might be invoked multiple times (which is a pretty esoteric use case) and I'd like to know if this intuition is correct, or if there's something I'm missing.

Also, performance is an issue, too. Capturing and reinstating a continuation for each reference cell access is a bit too much.

You don't have to just concern yourself with how many times the continuation is called, but also *when* it is called. And what happens before or after it.

What about if you want to call the continuation zero times? For example when aborting a computation. Maybe even aborting conditionally (or, more accurately, resuming conditionally).

What about if you want to wrap computation around the continuation invocation? For example the pure emulation of ML's mutable refs discussed in the original Eff paper. The intermediate return value from the continuation is a function of the current state, which must be supplied by the handler.

As for performance: The same compilation techniques that GHC employees on monads in Haskell can be applied to effects in Eff. Because impurities are encoded as dataflow to, from and of continuations, you can basically just inline them away.

No, in the usual case, you call the continuation once because you need to resume it. If you leave out the call, the continuation is thrown away, just like in exception handlers. There is no implicit way of resuming the continuation.

If you want performance, you've come to the wrong place. Eff is currently in a prototype stage and though we are working on it, we are at least one PhD thesis away from efficient evaluation. So far, two optimisations seem plausible.

First, you could use resources, which are a generalisation of reference cells and capture the kind of effectful behaviour where an operation modifies some internal state and returns a value back to the continuation. In addition to reference cells, examples are I&O, pseudorandom number generators, various persistent data-structures, … Right now, Eff still traverses the whole handler stack to see that no handler captures the operation, and only then invokes the resource. However, it would be a simple fix to figure out that there will be no matching handler so you can invoke the resource immediately

A more complicated optimisation is to recognise handlers that end with a call to the continuation (similar to tail recursion), and in this case just run additional commands instead of pausing the continuation, running the additional commands, and then resuming the continuation.

As Matija said, we're still prototyping usage, but some people are already looking at optimisation! Steven Keuchel (in joint work with Tom Schrijvers) presented in this year's Implementation and Application of Functional Languages (IFL 2014) some first steps towards efficient implementations of effect handlers.