Prolog

[Jay McCarthy]

I just did the Prolog assignment again to jog my memory.

Here's the time to beat:

* 40 minutes with 4 typos
* 98 lines (+ 79 for the tests from the site)

The most complicated stuff is

* logic variable support code (13 lines)
* =find-some algorithm (15 lines)
* == (23 lines)

Everything else fits on 1 80 column line (but takes up more lines
because of whitespace and beautious formatting.)

So, I was a little bit off with 60 lines, but it's close to what I
said. I would say that the code that is long is the easiest to come up
with, but each of the single line guys is where the soul searching
comes in.

Jay

--
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93

[Aaron Leonard]

I looked at it yesterday and I am just a little lost as to where to start. Is it best to just go in order (as in first define logic-variable and prolog-value, then implement =succeed, =fail, (_), etc)?

And will tomorrow's lecture of domain-specific languages help us with this lab?

[Jay McCarthy]

On Thu, Nov 29, 2012 at 12:38 PM, Aaron Leonard
<aaronjoh...@gmail.com> wrote:
> I looked at it yesterday and I am just a little lost as to where to start.
> Is it best to just go in order (as in first define logic-variable and
> prolog-value, then implement =succeed, =fail, (_), etc)?

I suggest doing =succeed, =fail, =or2, =and2, a function form of
=find-some, =or, =and, _, =var, the macro form of =find-some,
=find-all, then ==

> And will tomorrow's lecture of domain-specific languages help us with this
> lab?

Not really.

When you write the macros (=var, =or, =and, and =find-*) you will use
stuff that we talk about during the first 10 minutes of chapter 36. I
would be extremely surprised if someone was ready for this before we
talked about it in class.

But then we will quickly go far beyond any macro machinery you need
for the assignment.

Jay

>
> On Thursday, November 29, 2012 12:26:21 PM UTC-7, Jay McCarthy wrote:
>>
>> I just did the Prolog assignment again to jog my memory.
>>
>> Here's the time to beat:
>>
>> * 40 minutes with 4 typos
>> * 98 lines (+ 79 for the tests from the site)
>>
>> The most complicated stuff is
>>
>> * logic variable support code (13 lines)
>> * =find-some algorithm (15 lines)
>> * == (23 lines)
>>
>> Everything else fits on 1 80 column line (but takes up more lines
>> because of whitespace and beautious formatting.)
>>
>> So, I was a little bit off with 60 lines, but it's close to what I
>> said. I would say that the code that is long is the easiest to come up
>> with, but each of the single line guys is where the soul searching
>> comes in.
>>
>> Jay
>>
>> --
>> Jay McCarthy <j...@cs.byu.edu>
>> Assistant Professor / Brigham Young University
>> http://faculty.cs.byu.edu/~jay
>>
>> "The glory of God is Intelligence" - D&C 93
>

> --

[Royce Holmes]

Just to double check, is this the correct syntax for a function that takes in a continuation in Racket?

(define (somefun)

  (lambda (fk)

    ...

  )

)

On Thursday, November 29, 2012 12:26:21 PM UTC-7, Jay McCarthy wrote:

[Jay McCarthy]

Which function are you asking about? One takes no arguments and one takes an argument named "fk" which I presume is intended to be a continuation. 

Sent from my iPhone

--
 
 

[Royce Holmes]

I just want to know what the correct Racket syntax would be for a prolog-expression.  do I just do 

(define (expr fk)

...

)

i.e. are continuations treated like any other thing we pass into a function?

[Jay McCarthy]

The argument to any function, no matter what kind of thing it is, is
always written the same.

(lambda (x) ...)

is a function that takes a continuation, a zebra, a list of numbers, a
procedure, etc.

Jay

> --

[Jeff Andersen]

That moment when you spend half an hour debugging your =or macro before realizing you were using (or ...) in your test case the whole time...

[Brian Kingery]

Jay,

I'm kind of sad that we won't have a review day for Prolog. When judgment day is over can we have your code or something?

[Jeff Andersen]

Or maybe even a screencast so we can bask in your brilliance as you go.

On Dec 4, 2012, at 5:29 PM, Brian Kingery <brian....@gmail.com> wrote:

> Jay,
>
> I'm kind of sad that we won't have a review day for Prolog. When judgment day is over can we have your code or something?
>

> --
>
>

[Trent Burke]

Haha, I would second that.  After so many hours... it'll be like being set free.

--

[Logan Stromberg]

I've been stumped for hours and I still have no idea even how and2 is supposed to work.

I'm starting with the trivial implementation of
(define (=and2 expr1 expr2)
  (λ (fcont) (expr1 fcont)))

which just reduces the expression to its own left side, making it correct 50% of the time.
I'm trying to add the right side logic while focusing on this test case:

(=and2 (=or2 =succeed =succeed) (=or2 =succeed =succeed)) will succeed exactly four times.

My dumb answer was to do (begin (expr1 fcont) (expr2 fcont)) to tack on the rhs.
The problem is, evaluating the lhs will return a success continuation of its intermediate state that should be
used when you want to find future successes within the body of that expression. Evaluating the rhs will give you a different success continuation likewise. So as I understand it, when the two subexpressions of And succeed, what you need to return is a new success continuation that will effectively resume evaluation of the two subexpressions where they left off, using their individual success continuations. I imagine some fancy continuation passing is needed to do this. I am not that fancy yet, and instead have this dysfunctional function
(define (=and2 expr1 expr2)
  (λ (fcont) (let [(cont1 (expr1 fcont))] ;Test the lhs
               (if (procedure? cont1)
                 (let [(cont2 (expr2 fcont))] ;Test the rhs
                   (if (procedure? cont2)
                     (=succeed (=and2 cont1 cont2)) ;Return an aggregate success continuation
                     (fcont falsum)) ;Fail if expr2 failed
                   )
                 (fcont falsum)) ;Fail if expr1 failed
               )
    )
  )

I believe you were halfway through explaining this and then got cut off at 4:00 so I never figured it out. Also I am way overthinking this aren't I, the real solution is like 2 lines of code I know it is

-Logan

[Jay McCarthy]

I'll do that

[Jay McCarthy]

Please don't send emails like this to the mailing list.

[Jay McCarthy]

I got this email today from a student who has given up. It would be
useful for you all to see the answer. Read the email (and the attached
image) before reading the response.

Answer:

Your inability to read and understand the assignment is not
necessarily a problem with the assignment. It is not even a compelling
argument given the number of students who have understood the parts
you comment on without any advice from me.

In your commentary on =fail, for instance, you have a long winded
explanation of failure and claim that "I had to infer it all from the
sentence \"Never succeeds\"" However, your sentence is almost
identical (modulo confusing verbiage) to the paragraph that starts "A
failure-continuation? is ...". In particular you divide up the
definition of failure into two cases, backtracking and total failure.
This is the exact same definition in the cited paragraph on the
assignment page. Regurgitating (poorly) a sentence from the assignment
is not an "inference" that you made from one sentence.

Second, to help you see the error of your ways, let's just look at the
types involved in =fail.

The assignment says:

=fail : prolog-expression?

prolog-expression? : failure-continuation? -> success-continuation?

failure-continuation? : anything -> doesn't return, but FAILS [recall
that continuations don't return, a basic fact from October]

success-continuations : anything -> doesn't return, but TRIES AGAIN

Based solely on this information, you can trivially expand the type of =fail:

=fail : failure-continuation? -> success-continuation?

=fail : (anything -> doesn't return, but FAILS) -> success-continuation?

Now, if =fail "never succeeds" than by basic understanding of English,
that means it "Always and immediately fails". So, you have a function,
that takes one argument, that causes failure, and you want to fail.
Hmm, how could you possibility implement this?

Just to show you how absurd your argument is, let's just change all
the names and you'll see how trivial it is.
......

A printing expression is a function that takes a printing function and
returns a reading function.

A printing function is a function that takes an argument (that it
ignores) and prints something.

A reading function is a function that takes an argument (that it
ignores) and reads something.

=prints is a printing expression that never reads anything, and thus
always prints something.

Expressed as types:

PE : PF -> RF
PF : Any -> Prints
RF : Any -> Reads
=prints : PE

Thus

=prints : (PF -> RF)
=prints : (Any -> Prints) -> RF

=prints should print.

Simply by looking at the types alone, there is only one possible
implementation of =prints:

(define (=prints pf) (pf "anything"))

There's no other way to get a "Prints", so it must be this way.

=succeed, =and2, and =or2 can be written almost completely by looking
the types alone. The majority of errors that I see in my office when
people ask questions are people ignoring the types.

Jay


---------- Forwarded message ----------
From: A student
Date: Wed, Dec 5, 2012 at 4:18 PM
Subject: Re: Prolog
To: Jay McCarthy <jay.mc...@gmail.com>


I've given up on this assignment. It's just completely broken me after
spending 12 hours just trying to figure out what "fail" means,
continuation-wise
And then doing the same for "success", "or", "and", and so forth. It's
getting old.

I'm kind of angry as you can tell so I probably shouldn't be writing
an email now, wait for it to cool off, etc, etc. but whatever.

You say that the everything for the assignment that we need to know is
"right there". Yes, it's right there, in the sense that everything we
want to know about Kolob is right there in the facsimiles of Abraham.

I've had a hard time expressing exactly in words why the assignment
descriptions are so infuriatingly vague and ambiguous, leaving us to
either spend hours trying to decipher them, or else going to the
oracle (you) to try and understand them (Hence, the party in your
office right now). I figure the best way to approach this would be
constructive criticism, so I'll give an example suggestion to try and
elucidate what I mean. Actually I'll just attach it as an image since
I don't know how html works. Maybe I'm just not seeing your principle
of "letting the students learn to figure things out on their own",
because most of the time I don't feel like I'm learning anything new
when I'm trying to decipher what you mean in these descriptions.

I guess I do have one other dumb suggestion, which would be to rewrite
this assignment to use the (amb) function and a global fail stack, but
then I know that would cause issues with recursion (overwriting a
single mutable stack) and universe of discourse issues (amb would
require a list of all possible values, already precalculated). So
that's shot down. I guess my point is, I understand that
implementation naturally, but I still have no idea what Prolog is
supposed to do. I was never able to grasp the big picture.

Regrettably yours
- The student


On Tue, Dec 4, 2012 at 9:25 PM, Jay McCarthy <jay.mc...@gmail.com> wrote:
>
> Your =or2 is mostly right, but you can't discover the (small) error
> until you do find-some
>
> Sent from my iPhone
>
> On 2012/12/04, at 21:20, Logan Stromberg <loganst...@gmail.com> wrote:
>
> > Can you at least tell me if this is right? I don't want to go back to
> > the drawing board but better sooner than later
> >
> > ;This value is returned if a fail has occurred
> > ;Should be (void)
> >
> > (define fail-value "FAIL")
> >
> > ;Define the falsum value to mark the "end" of an undelimited
> > continuation. This function is the final failure continuation in all
> > evaluation paths, and its invocation indicates that there is no possible
> > solution to the expression.
> >
> > (define falsum (λ (x) fail-value))
> >
> > ;A failure means it shifts control to the fail continuation by invoking it.
> >
> > (define úil (λ (fcont) (fcont 'an-ignored-value)))
> >
> > ;A succeed means that it returns a function, which, when invoked, will
> > try again (by failing). The function it calls when it tries again is the
> > failure continuation that was passed in when this....success
> > ...occurred....OH WHAT THE
> > ;The "success" is indicated by the fact that this function exists and it
> > is not void. This function stores the continuation which, when invoked,
> > will resume computation after the point the success occurred.
> > ;Probably. Don't think falsum should go here but then what else could?
> >
> > (define =succeed (λ (fcont) (λ (an-ignored-value) (fcont falsum))))
> >
> > ;INVOKING FAIL ON FALSUM RETURNS FAIL VALUE
> > ;This means "we have failed and there is nowhere else to go"
> >
> > (test (úil falsum) fail-value)
> >
> > ;INVOKING SUCCEED GIVES A FUNCTION WHICH WILL THEN FAIL
> >
> > (test (procedure? (=succeed falsum)) #t)
> > (test ((=succeed falsum) falsum) fail-value)
> >
> > ;Use CPS to evaluate the lhs and rhs of an OR in sequence.
> > (define (=or2 expr1 expr2)
> > (λ (fcont) (expr1 (λ (an-ignored-value) (expr2 fcont))))
> > )
> >
> > -Logan