4 ms·

Do you know of an example of another general backtracking DSL implemented in another language that is significantly easier or more concise?

• misja111 10y ago
  This is not what my comment is about. You wouldn't normally write a general backtracking DSL in an imperative language because a backtracking algorithm is trivial to write. Only when you are using a pure functional language it becomes non trivial to combine the results of the individual sub branches.
  • setra 10y ago
    Perhaps you misunderstand what this is doing? Or perhaps I misunderstand what you mean. If all you want is to take some kind of search function or backtracking system that generates a stream of results then combining the sub branches is trivial. If you represent a stream as a list and use something like Haskell that is lazy, then all you have to do is literally combine the streams. myStreamGenerator1 p1 ++ myStreamGenerator2 p2 if you want a different search strategy you can intersperse. concat . intersperse (mySG1 p1) (mySG2 p2) the cases being DFS and BFS
    • misja111 10y ago
      With backtracking you typically have some kind of pruning stragegy. That means keeping track of your best result so far and dont go into branches where it is clear that they can never beat your current winner anymore. So you cannot simply concatenate the results of the subbranches, each new branch needs to be aware of what has been found so far. That can quickly become ugly in pure FP, that's why people have been looking for solutions that do that in an elegant way, e.g. using Monads.
      • setra 10y ago
        Pruning can be implemented by just not computing a part of a stream based on some predicate. If you want some kind of global state of the current results then you just pass around the current calculated states. Pure FP has many simple solutions for passing around state.
  • mbrock 10y ago
    Would you care to show such a trivial example, and maybe we can see if it can be translated into Haskell?
  • marcosdumay 10y ago
    Your comment is about something that is not this article. This article is about a generic backtracking DSL. Not about writing a recursive function that fails some of the time.
• tannhaeuser 10y ago
  Prolog? Prolog uses backtracking as the principal control flow paradigm and allows user-defined languages/DSLs by defining tokens, their associativity and precedence in operator-precedence parsing, where tokens are character sequences that are either all graphic characters or all letters/digits. Example from the book Adventures in Prolog as returned by a cursory Google search: ? op(35, xfx, is_in) banana is_in room(kitchen).
• mpweiher 10y ago
  There's always the classic from 1988, which completely blew my mind when I came across it a couple of years later: "Building a backtracking facility in smalltalk without kernel support"[1] Languages like Snobol, Prolog, and Icon were designed with backtracking facilities from the outset and these facilities are deeply intertwined with the implementation. Retrofitting a backtracking facility in a language that wasn't designed for it has never been achieved. We report on an experiment to retrofit Smalltalk with a backtracking facility. The facility is provided through a small number of primitives written in the language (no modifications to the kernel were made). The ability to do this is a direct result of the power provided by the objectification of contexts. I'll leave the qualitative analysis of which is easier or more concise to others. [1] http://dl.acm.org/citation.cfm?doid=62084.62094&CFID=739328395&CFTOKEN=98039752 http://dl.acm.org/citation.cfm?doid=62084.62094&CFID=7393283...