The time difference is largely due to using the product library
function instead of for comprehensions and the fact that the cKanren
version cheats by hardcoding part of the solution, and hardcoding an
extra constraint alldiff(a,b,c,d). The following code takes ~12ms with
PyPy on my computer:
def valid(a,b,c,d):
weights = set(w*a+x*b+y*c+z*d for w in [-1,0,1]
for x in [-1,0,1]
for y in [-1,0,1]
for z in [-1,0,1])
return weights >= set(range(1,41))
ws = [(a,b,c,d) for a in range(1,40)
for b in range(1,40) if a <= b
for c in range(1,40) if b <= c
for d in range(1,40) if c <= d
if a+b+c+d == 40 and valid(a,b,c,d)]
If you cheat with `for a in [1]` instead of `for a in range(1,40)` and
changing the <= to < (the same cheat as the alldiff), then the
execution time drops to 2ms.
Since we don't seem to be going to agree on the definition of
declarative, lets use another word: nice. Lets define niceness as
understandability and closeness to mathematical specification. I agree
that the matches definition is already nice: it handles the
constraints and symmetry breaking nicely (better than the Python
version if you ignore syntactic issues e.g. a+b+c+d=40 is more
convoluted). But the checko and subchecko leave a lot to be desired.
So my question is: can the cKanren version be improved so that it also
becomes nice?
Jules
On 12 nov, 07:16, David Nolen <[email protected]> wrote:
> Also note that even given all this generality over the Python code - the
> earlier Python implementation takes ~300ms and this implementation takes
>
> >900ms on my machine.
>
> Quite a bit slower than ~12ms. Inferring 40 takes even less time of course
> - ~8ms.
>
> But really the execution time is just icing on the declarative cake ;)
>
> David
>
>
>
>
>
>
>
> On Fri, Nov 11, 2011 at 8:09 PM, Jules <[email protected]> wrote:
> > Here is a new program. Perhaps you would consider this declarative:
>
> > def valid(a,b,c,d):
> > weights = set(w*a+x*b+y*c+z*d for (w,x,y,z) in
> > product([-1,0,1],repeat=4))
> > return weights >= set(range(1,41))
>
> > ws = [(a,b,c,d) for (a,b,c,d) in product(range(1,41),repeat=4)
> > if a <= b <= c <= d and a+b+c+d == 40 and
> > valid(a,b,c,d)]
>
> > On 12 nov, 01:48, Jules <[email protected]> wrote:
> > > Are we reading the same cKanren code? I'll give you that the matches
> > > definition is declarative, but then read checko and subchecko. They
> > > are all about (recursive) control flow. Where does the specification
> > > say anything remotely close to the checko and subchecko relations? In
> > > contrast to this, the Python set comprehensions have minimal control
> > > flow. Yeah, the standard Python implementation has a certain order of
> > > executing the comprehensions, but so does the cKanren implementation
> > > when executing the predicates. My Python program doesn't depend on
> > > this order: it just uses declarative descriptions of sets as set
> > > comprehensions.
>
> > > Just being written in cKanren doesn't make a program declarative. If
> > > you write a C interpreter in cKanren and then write your actual
> > > program in a literal string, that doesn't magically make the program
> > > declarative even though it is a cKanren program. Similarly, checko and
> > > subchecko don't describe the problem in a declarative way. Compare
> > > this with the Python valid() function: the set of possible weights you
> > > can make has to be a superset of {1..40}. Again, declarativeness is a
> > > property of programs, not languages. Some languages make writing
> > > declarative programs easier, of course. cKanren is supposed to be such
> > > a language, so it would be neat to see a more declarative cKanren
> > > program for this problem.
>
> > > Also, I don't see how "one stone should weigh 1lbs" is part of the
> > > specification. Now, it is true that the answer happens to have one
> > > stone equal to 1, but how is that part of or trivially follows from
> > > the specification? We might as well hard-code the whole solution.
>
> > > Jules
>
> > > On 12 nov, 00:49, Timothy Baldridge <[email protected]> wrote:
>
> > > > > My Python code is much more declarative than the given
> > > > > cKanren code in that regard. Just compare:
> >http://dosync.posterous.com/another-taste-of-ckanren
>
> > > > I don't think you understand what declarative programming is at its
> > > > core. Declarative programming
>
> > > > To borrow from the ever-present wikipedia:
> > > > "declarative programming is a programming paradigm that expresses the
> > > > logic of a computation without describing its control flow.[1] Many
> > > > languages applying this style attempt to minimize or eliminate side
> > > > effects by describing what the program should accomplish, rather than
> > > > describing how to go about accomplishing it.[2] This is in contrast
> > > > with imperative programming, which requires an explicitly provided
> > > > algorithm." (see: Declarative Programming)
>
> > > > This is where the cKanren code succeeds where the Python code fails.
> > > > The Python code is all algorithm, and no facts. While the cKanren code
> > > > is a direct implementation of the facts about the problem: one stone
> > > > must be 1lb all stones should equal 40lb, etc. The cKanren code leaves
> > > > the interpretation of these facts up to the logic engine, while the
> > > > Python code sets strict guidelines that the compiler must follow. If,
> > > > for instance, it was faster for a given computer to count down from
> > > > instead of counting up, the Python code would run much slower, by
> > > > defining the algorithm (by using range, and for loops), you're
> > > > restricting the interpreter to your view of how to solve the problem.
> > > > The cKanren compiler/interpreter/whatever is free to solve the problem
> > > > in any way it pleases, as long as the requirements (facts) are met.
> > > > The original problem states "find 4 numbers that equal 40 but a
> > > > combination of any of which can be 1 through 40" it says nothing of
> > > > range sequences, for loops, etc.
>
> > > > Timothy
>
> > --
> > You received this message because you are subscribed to the Google
> > Groups "Clojure" group.
> > To post to this group, send email to [email protected]
> > Note that posts from new members are moderated - please be patient with
> > your first post.
> > To unsubscribe from this group, send email to
> > [email protected]
> > For more options, visit this group at
> >http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
