I'll just clarify, the "matches" function body jumps out at me. "checko"
doesn't, but it's role in the problem is still clear, even if its
implementation is not. I think that's still an important trait.
Can checko be improved? I'm not sure. What does subchecko do, David?
Ambrose
On Sun, Nov 13, 2011 at 11:37 AM, Ambrose Bonnaire-Sergeant <
abonnaireserge...@gmail.com> wrote:
> "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
