Follow-up on effect masking and backtracking

A follow-up on yesterday's post about backtracking with state: an anonymous commenter reminded me that persistent data structures are a useful and lightweight (compared to e.g. first-class stores) approach. In fact, probably my favorite paper from ESOP 2008 was Conchon and Filliâtre's Semi-Persistent Data Structures, which was addressing exactly this problem. Rather than introducing an entirely transactional semantics for the language, it's just a data structure with a transactional interface.

Representing failure

I'm working on an algorithm that uses backtracking implemented with exceptions and handlers (rather than, say, explicit continuations). I just noticed that, for debugging, it's nice to represent the failure exceptions as records that contain not just the data about the operation that failed but also an optional list of other failure exceptions. In the disjunction cases, I can save the intermediate failures and, if they all fail, include them in the resulting failure record. This provides me with a nice data structure representing the control flow of the failed search tree. It only required modifying about 3 lines of code and the resulting data structure is easier to analyze than a manual debugging sequence. (I hate working with debuggers, even good ones.)