Thursday, May 14, 2009

Effect masking vs. purity

I've been working for a while on an algorithm that involves two effects: mutation and backtracking. Implementation strategies for the two effects seem to have different economics. I'm working in the context of PLT Scheme, here, but I suspect my observations would be similar in other non-pure languages.

For backtracking, I could implement the algorithm in a pure way using two continuations or the list monad. Or I could just use the built-in exceptions and exception handlers of PLT Scheme. For mutation, the choice is between store-passing or the built-in mutation of Scheme.

I've tried abstracting these two effects out into a single monad for a completely pure implementation. There are downsides to this approach, though. For example, debuggers and stack traces are completely useless since most of the program control flow goes through unit, bind, and the myriad intermediate closures created by such a higher-order style of programming. Besides, an excessively higher-order style imposes real readability costs on a program. So for implementing backtracking, I find exceptions to be a more straightforward approach.

But as it turns out, the algorithm also needs to roll back mutations when it backtracks. So I simply can't use mutation. I think this is one of the things that make mutation so unwieldy--there's typically no corresponding "masking" operation for a destructive update. Exceptions have handlers, continuations (sometimes) have delimiters-- even some I/O features come with effect masks: for example, in PLT Scheme you can override the current-output-port with a string port and capture a program's output. All of these allow you to bound the effects a computation can have, to put a sort of dynamic safety net around it. Not so for set!, vector-set!, set-box!, or set-record-field!.

So for mutation, I'm sticking with explicit store-passing-- not in monadic style. That seems to be the reasonable middle ground for my purposes.


Alessandro Warth said...

Hey Dave,

What you're talking about here was pretty much exactly my motivation for "worlds". Did I ever tell you about that stuff? If you're interested, take a look at Chapter 4 of my dissertation. I'd love to chat with you about this stuff at some point...


Anonymous said...

It depends on the implementation of mutation. You can presumably build "masking" in, by e.g. firing a search with a copy of the current store, and discard the copy on backtrack. There's a bunch of stuff on doing this efficiently, in logic programming (dating back to CT Haynes in the 80s) and first-class stores (as duals to first-class continuations).


Andrew said...

I've had good results using the approach from "A Semi-Functional Implementation of a Higher-Order Logic Programming Language" by Conal Elliott and Frank Pfenning.

Anonymous said...

You can make rolling back state be extremely simple during backtracking by using a persistent datastructure. The only mutating state left then would be a stack which points to successive 'mutations' of the persistent structure.