5 ms·

I'll have a crack at some suggestions, as a Clojure user (nice work on core.logic!) with some Haskell familiarity. For logic programming: you might find Contro

• oggy 14y ago
  Kiselyov et al have an interesting paper on logic programming in Haskell [1]. They introduce a backtracking monad transformer with fair disjunctions, and negation-as-failure and pruning operations. And the implementation is based on continuation, so it's more efficient than reification-based approaches such as e.g. Apfelmus's operational monad [2] [1]: http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.... [2]: http://apfelmus.nfshost.com/articles/operational-monad.html http://apfelmus.nfshost.com/articles/operational-monad.html
  • saosebastiao 14y ago
    Is that Basque-Icelandic pidgin?
    • oggy 14y ago
      Heh, fair point. I guess it can read like that. I'll expand. Monad transformer = thing that can transform a monad into another one with additional primitive operations. Monads are more or less the Haskell way of achieving something akin to overloading the semicolon in imperative languages. In imperative languages the meaning of the semicolon is baked into the language. It seems natural and stupid to think about what it means, normally it's just "do this, changing the program state by assigning some values to some variables, then do this with this new state" but if you think harder, it can also mean "do this and skip the rest of the loop" (if the first statement is a break) or "do this and then skip a bunch of levels up the call stack until you find an appropriate handler, unwinding the stack in the process" (if it's a throw). Haskell doesn't have any of this baked in, but in a way allows you to define the semantics of the semicolon yourself. So monad transformers then allow you to build up more complicated semicolon semantics by combining simpler ones (and getting the full set of their primitive operations, such as assignment, break or throw statements in the previous examples). Logic programming, in its simplest form, is concerned with deducing "goal" facts of the form C(X), from a bunch of rules of the form "A(X) and B(X) and ... imply C(X)" and other facts of the form "A(X)". One way you can do this is look for all the rules with your goal fact as their conclusion, then look how you can derive their premises, and so on. Which essentially boils down to a backtracking search. So what Kiselyov et al did was to implement some primitive operations and overload the semicolon in a way which makes it easy to perform a backtracking search. Or more precisely, since it's a monad transformer, they figured out a way to add these primitives to any set of existing ones (such as assignment primitives for instance). Their implementation also provides some interesting backtracking operations which can be tricky to implement (the aforementioned fair disjunctions, negation as failure and pruning). And it is efficient since it's based on continuations (which are just functions of a certain format), as compared to other approaches which first have to represent the target program as data ("reify" it), then define an interpreter for that data and finally run the interpreter. Better?
      • saosebastiao 14y ago
        Almost. One of my frustrations with learning Haskell is that everybody assumes that I am coming from a imperative programming background. I've toyed Python a wee bit, but I've really only ever used functional languages (Scheme, R, Clojure) and have only ever programmed in a functional style. Needless to say, I have no clue what the semi-colon is supposed to do in imperative languages. As I have been told many times, knowing functional programming lets you start at 2nd base with Haskell...but no further. Thanks for the attempt. I'll try again after I'm done with RWH.
        • flyinRyan 14y ago
          I also find it amusing that Haskellers always tell you "semicolon" when you normally won't ever see one in any code. What they're talking about is statements. If you have a completely pure functional language, no function should ever have more than one expression. If the function had two expressions that would mean one of them did something and the result was thrown away. But if you don't have side effects, why would you have an expression that does something and then throws the result away? In Haskell any function can only have one expression. So if you need to do several steps (i.e. you need side effects) you have to use do notation. Do notation is syntactic sugar for turning what appear to be several statements into one statement. If you use the "curly brackets" way of coding then you would separate these statements with semicolons (tada!), but most code is white space significant so they just use one line per statement. So what do does is takes the code you wrote in the lines and determines how to combine it. If you're using do then you're using a monad of some kind (a container, basically). Given the container and the contained, you can do two kinds of operations: "side effect kinds" that appear to do a statement and ignore the result (these actually work with the container) and expressions. The interesting thing about this kind of code is you don't keep track of the container. Sometimes you don't see any trace of it at all except in the type signature. There will be functions that talk to the container but they don't appear to take the container as a parameter (which is good since you don't have a handle to it anyway). Behind the scenes do is setting up the code in such a way that the container is actually passed to each of your expressions so your "side effects" aren't side effects at all, they're modifications to the invisible (to you) container. And each line is fused together by using one of two functions the container defines. So this is where the power comes in. How the container chooses to put these lines together depends on what the container actually is. An exception container, for example, might provide a special function (called, say, "throw") that will call each expression (functions by the time the container seems them) unless one of them calls its special "throw" function at which point it doesn't execute any further expressions and instead returns the exception it was passed. I don't know if that makes things better or worse. :)
• flyinRyan 14y ago
  > (Can't quite put my finger on why). Lazy evaluation. Much of what you use Lisp macros for is to control when/if arguments get evaluated. Haskell just works this way so you don't need macros for it.
  • zeckalpha 14y ago
    Another way to think about it is that every Haskell function is a macro.