"Understandability" is subjective. The meaning of the cKanren really jumps
out at me, the python program takes a lot more for me to think through.
There is nothing wrong with pruning the search space in this program. As
you said, doing so reduced the Python program execution time to 2ms!
Ambrose
On Sat, Nov 12, 2011 at 11:30 PM, Jules <julesjac...@gmail.com> wrote:
> 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 <dnolen.li...@gmail.com> 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 <julesjac...@gmail.com> 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 <julesjac...@gmail.com> 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 <tbaldri...@gmail.com> 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 clojure@googlegroups.com
> > > Note that posts from new members are moderated - please be patient with
> > > your first post.
> > > To unsubscribe from this group, send email to
> > > clojure+unsubscr...@googlegroups.com
> > > 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 clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> 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 clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
