On 11/01/2010 06:19 PM, Richard O'Keefe wrote:
On 2/11/2010, at 1:27 PM, Gregory Crosswhite wrote:
Hey everyone,
This is a little off-topic, but I just ran into a problem which might benefit
from being attacked by a logic language,
Why not describe the problem?
My goal is to exhaustively search through a space in order to categorize
all of the elements in that space. This space is combinatorial, so I am
looking for a good domain specific language for letting me break up the
space into a bunch of generators which can be combined combinatorically
to generate the list of elements in the space. What makes the
generators non-trivial is that I am choosing them carefully in order to
eliminate many symmetries of the problem that effectively result in
equivalent/redundant elements of the search space, and a consequence of
this is that some generators depend on the results of other generators.
The combinatorics of the problem are such that there are about a billion
elements in the space if I try tackling a small version of my problem,
and a trillion if I try tackling a slightly larger version of my problem.
(More background: The elements in this space are choices of quantum
measurement operators which are used to implement a quantum
error-correcting code, and I am interested in knowing if the code is
"good" or not. My goal is to systematically search through all codes
with a small (<= 5-6) number of qubits in order to be able to classify
all of the possible of error-correcting codes one can implement using
that many qubits.)
It is worth mentioning that the function I am applying to these elements
to compute the desired properties is very fast. I have had benchmarks
showing the ability for this function to scan through up to ~ 500,000
elements a second (It helps that it is written in C++ :-) ).
Actually, the more that I think about my problem the more that I'm
thinking I should just stick with the List monad. This gives me a way
to create generators that can rely on the results of other generators
and put them all together using the List monad, taking advantage of
Haskell's laziness to iterate in O(1) space. Which does raise the
question: when is it better to use a logic programming language instead
of the list monad?
so I've been looking for a good one to try out --- and hopefully one that has a
very efficient implementation since I want to iterate through billions and
possibly trillions of nondeterministically generated solutions.
I think about the practical success of Model Checking, and wonder whether it
might be better NOT to iterate through so many.
What exactly do you mean by Model Checking?
Anyway, there might be more clever ways to eliminate possibilities from
my space (other than the ones I have already) but the advantage of
having a computer search all of it is that it can scan through all of
the millions and even billions of possibilities in a stupid brute-force
fashion in less time than it takes for me to come up with a clever way
to analyze the space using theoretical analysis. :-)
I've also been looking at Prolog but I am having trouble seeing whether I can
process N non-deterministic solutions in O(1) space (rather than first
generating a O(N) size list),
The point of backtracking search is that you need only space for the current
candidate solution, not for all solutions visited so far. So much so that the
Iterative Deepening family of search algorithms cheerfully *revisit* graph nodes
in order to save time over all.
Yes, exactly, but my point is that in Prolog I am having trouble
figuring out if there is a way to iterate over all of the solutions
generated non-deterministically in O(1) space because all of the library
functions which run an accumulator over a generated set of results seem
to operate by first generating the full list and then accumulating over
it which takes O(n) space, which is wasteful since as you point out it
should only take O(1) space to do this. However, it is also possible
that I misunderstand the semantics of how Prolog works and so things
which look like O(n) to me are actually O(1) --- similar to laziness in
Haskell.
and I checked out Mercury but the documentation for it is a bit sparse.
Packl
The Mercury documentation I downloaded in March comes to 773 pages.
faq.pdf 6 pages
library.pdf 470 pages
reference_manual.pdf 150 pages
transition_guide.pdf 10 pages (Mercury for Prolog programmers)
user_guide.pdf 137 pages
Packing the tutorial into a single HTML file gives another 19 pages.
Ralph Beckett's tutorial adds another 53 pages of PDF.
So that's 845 pages all up. "sparse"?
"a bit sparse"?
Yes, because although there is a tutorial with the trivial stuff, and a
references for people who already know what they are doing, there is not
much intermediate-level documentation for someone who understands the
basic ideas behind the language and is trying to figure out how to do
more advanced things in it.
For example, there is a garbage collector in the system which you can
turn on and off with command-line options, but there is nothing in the
documentation that tells you what the actual effect of this is, which is
very strange --- I mean, it seems to me like a garbage collector isn't
something that you could just switch off without having other
consequences, but there is nothing in the documentation to tell me what
these might be. (Having said that, I found an academic paper or two
which suggest that a run-time garbage collector isn't needed because
Mercury does *compile-time* garbage collection, which is *awesome* if
that is indeed what is going on! :-) )
Also, while there is a lot of library documentation, there is no
high-level organization to it so it can be tricky to figure out where
you should be looking for a given bit of functionality. Also, the size
is misleading; in particular, the size of library.pdf is inflated
because it basically just a collection of header files with brief
descriptions of what the functions do, and part of the reason why it is
so large is because for every line of documentation there are many lines
of declarations because in Mercury there has to be a separate
declaration for each mode of operation.
Cheers,
Greg
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
