Logic programming library development log

[bh]

@qw23

(or directions, actually)

Uh oh, am I being too controlling?

ALWAYS-TRUE: The general form of a rule is
(rule (conclusion) body)
analogous to
(define (function args...) body)
in Scheme.

How do you try using a rule to satisfy a query? There are two steps: (1) Unify the conclusion of the rule with the query. (2) If that succeeds (i.e., doesn't report FAILED), then qeval the body in the frame-stream it reports. This gives rise to a possibly-extended-or-shortened stream of possibly-extended frames.

But some rules have empty bodies, e.g.,
(rule (append () ?b ?b))
They could have made that a special case in APPLY-A-RULE this way (my added code in capital letters -- this is why symbols should be case-insensitive!):

(define (apply-a-rule rule query-pattern query-frame)
  (let ((clean-rule (rename-variables-in rule)))
    (let ((unify-result
	   (unify-match query-pattern
                        (conclusion clean-rule)
                        query-frame)))
      (if (eq? unify-result 'failed)
          the-empty-stream
          (IF (NULL? (RULE-BODY CLEAN-RULE))       ; no body?
                (SINGLETON-STREAM UNIFY-RESULT)    ; return unify result
                (qeval (rule-body clean-rule)
		               (singleton-stream unify-result)))))))

but instead they are avoiding having to make that test by being extra clever in the selector RULE-BODY:

(define (rule-body rule)
  (if (null? (cddr rule))
      '(always-true)
      (caddr rule)))

so that instead of seeing an empty body, APPLY-A-RULE sees (ALWAYS-TRUE).

The use of PUT here isn't about polymorphism; it's about recognizing special forms in the query language, which mostly means AND, OR, and NOT. But the PUT makes ALWAYS-TRUE also a special form, which means that instead of treating it as a query (remember, bodies are made of queries) and trying to match it against the database of assertions and rules, qeval will just call the Scheme procedure that's PUT into the table as the value associated with the key ALWAYS-TRUE. (The 'QEVAL as the second argument to PUT is just because back in Chapter 2 they defined PUT to use a 2D table, I think. Just take PUT on faith.)

So what happens when the evaluator finds a special form?

(define (qeval query frame-stream)
  (LET ((QPROC (GET (TYPE QUERY) 'QEVAL)))
    (IF QPROC
	    (QPROC (CONTENTS QUERY) FRAME-STREAM)
	    (simple-query query frame-stream))))

This is the code from the book; I haven't changed it. The capitalized part is what handles special forms. We look up the car of the query (that's what TYPE does) in the get/put table, and if we find it, call the procedure in the table value with two inputs: the special form with its keyword removed (CONTENTS is cdr) and the frame stream. They remove the keyword because in the usual case of AND, OR, or NOT, the contents part of the special form is a list of queries (AND query query ...) and so the handler can call itself recursively on the cdr of that list.

But in the case of ALWAYS-TRUE, the CONTENTS will be empty; there aren't any sub-queries to evaluate. So ALWAYS-TRUE has to be written to expect two arguments: an empty list of queries, which it ignores, and a frame stream, which it returns unchanged.

---

CONTENTS: Yes, your translation is okay, although PAIR? isn't the same as LIST?. It's making sure the EXPRESSION is a nonempty list. That's so that the query language won't accept (AND) etc.; those special forms require at least one sub-query (exactly one sub-query in the case of NOT). I guess also a perverse user could say (AND . FOO) to get a non-list CONTENTS.

---

I'm not saying you have to exactly copy the SICP code! Just that you should understand the SICP code and in particular how they use the idea of a stream of frames to make the whole thing functional.

[qw23]

Thanks for the explanation!

@bh

I'm not saying you have to exactly copy the SICP code! Just that you should understand the SICP code and in particular how they use the idea of a stream of frames to make the whole thing functional.

Yeah, that has been my interpretation, too. The SICP code from this section - and building on code from other sections - is kind of intimidating to me as a non-Schemer. I haven’t gotten around yet to analyzing how streams are to be integrated into my approach of the interpreter, but I will eventually . “Don’t hold your breath”

Well … perhaps you could help me out a bit more by telling if there are any ready-to-use Snap! equivalents of:

delay
force
stream-ref (would that be: item (n) of show stream?)
display-stream
cons-stream (= in front of stream ?)
the-empty-stream (= list() ??)
singleton-stream (= stream (x))
stream-flatmap (= sum (map over stream) ?)
interleave-delayed (why is it different from interleave, which in itself is supposed to handle streams?)
qeval
flatten-stream

Thx in advance!

BTW while studying SICP’s streams section I tried to implement the pairs function in Snap!, but something is not working well. If both streams are finite, show stream will raise an error if the number of elements to be shown is larger than the length of the stream of pairs:

This is the “project” (I simplified the test case as much as possible).
I’m pretty sure show stream is not causing the issue (while debugging I found it encounters a pair of two empties as item 1 of a Snap! record representing a stream), but I don’t know what is.
Solved it: the pairs function was devised for infinite streams only.

[callietastrophic]

I'm not saying you have to exactly copy the SICP code! Just that you should understand the SICP code and in particular how they use the idea of a stream of frames to make the whole thing functional.

Thanks not what I was trying to do either. I just wanted to get the framework functional so I could get in and examine the innards of snap and javascript in real time. Just a meta-circular evaluator in snap would be incredible. INCREDIBLE, let alone what I could add on top.

The problem is, the claim is that "Snap! is Scheme disguised as scratch" and it's not, because it has features that 1996's scheme will never have, and certain expectations that SICP asks for have been subtly changed and there is a barrier there, and it's not even there intentional, it's the side effect of the book being nearly 30 years old and the next version of the book written for a language that's powerful for all the wrong reasons.

[qw23]

Thinking aloud, I’m considering to add and, or and not blocks to Amalog (or whatever a logic programming library will be called in the end).

I don’t think it’s absolutely necessary though:

• and is the standard for a series of sub-goals within a rule’s body within the current version.
• the effect of or can be realized by adding extra clauses, e.g.:

(child, ?a, ?b) :- (father, ?b, ?a) or (mother, ?b, ?a)

… is logically equivalent to my current implementation’s:

(child, ?a, b?) :- (parent, ?b, ?a);
(parent, ?a, ?b) :- (father, ?a, ?b);
(parent, ?a, ?b) :- (mother, ?a, ?b)

• implementing not is also strictly unnecessary, since e.g. SICP’s example (§ 4.4.3, sub “problems with not”; my paraphrase):

… would be equivalent to:

[note]

However, I suspect and, or, and not are easier to use, and may even enable implementation optimizations.

note (to myself): the final argument (result) of a goal denoting a Snap! predicate test is actually superfluous, as a test can always be rewritten to be successful when true.

[bh]

@qw23

Well … perhaps you could help me out a bit more by telling if there are any ready-to-use Snap*!* equivalents of:

(delay x) is more or less (lambda () x) (so it's a special form, not an ordinary procedure). I say "more or less" because it's actually memoized, so when you force it for a second time it doesn't recompute the underlying expression. So

(let ((already-run? #f)
      (value #f))
  (lambda ()
    (if already-run?
        value
        (let ((result X))
          (set! value result)
          (set! already-run? #t)
          result))))

where the X is the unevaluated text of the input to DELAY. (If you wanted to implement this in Scheme, you'd write a macro. In Snap! you can just make it a block whose input is Any(unevaluated). We rule.)

(define (force promise) (promise))
This is the opposite of DELAY. Since PROMISE is a thunk (a procedure of no inputs), we can just call it; unlike DELAY, FORCE is an ordinary procedure.

stream-ref: Yes, you could implement it using SHOW-STREAM, but it's usually just defined in terms of STREAM-CAR and STREAM-CDR:

(define stream-ref index strm)
  (if (= index 0)   ; of course in Snap! it's one-origin
      (stream-car strm)
      (stream-ref (stream-cdr (- index 1) strm))))

display-stream is what we call SHOW STREAM, except that their version works only for finite streams, whereas we have an extra input saying the maximum number of items to display.

(cons-stream a b) is a macro for (cons a (delay b)). Again, in Snap! we can do it with an unevaluated input. CONS, for lists, is our IN FRONT OF.

I actually didn't use DELAY, though, because our IN FRONT OF doesn't allow a non-list in the second input. I'm too tired to change that tonight.

the-empty-stream can actually be any value that STREAM-NULL? can find unambiguously. We use the empty list, but it could be (LIST [THE EMPTY LIST]) too.

Jumping down a bit, because flattening is complicated, QEVAL is the central piece of what you're writing! It evaluates a query (a goal, which is basically just list-structured text) with respect to a stream of frames, reporting another stream of frames. So, no, neither Scheme nor Snap! provides this.

It's a stream of frames as input and as result because maybe you've already partly evaluated another query by applying a rule, which means (1) unify the query with the conclusion (the part before the :- ) of the rule, maybe generating some variable bindings, and (2) in the context of those bindings, evaluate the body of the rule (the part after the :- ), which may generate zero or more sets of additional bindings. Since the result of evaluating a query can be more than one set of bindings, we have to collect all the frames. In principle we could make an ordinary list of frames, but we use streams because (1) maybe there are infinitely many solutions, and we'd like the user to see some of them before we give up, and (2) even if the set of solutions isn't infinite, we want to get all the way to the end of one solution even though we write the code as if we're finding all the solutions in parallel.

This is the point about streams in general; the goal is to write programs that look like they use higher order functions:

but run as if they use iterative loops:

(Try them both with 1000000 as input if you don't see the efficiency difference.) Then try the stream version:

There's a lot more to say about the structure of QEVAL, but I don't want to write all of 3.5 here!

Okay, now to discuss flattening. FLATTEN (for lists) is

(define (flatten lists)
  (accumulate append '() lists))

i.e., one degree of flattening, not like , which flattens all the way down to atoms. (This is a confusion of nomenclature, and I wish we'd agreed with Scheme even though Jens is right that what we do is closer to what the name suggests in English.)

(define (flatmap func data)
   (flatten (map func data)))

is a frequently useful abbreviation, for situations in which FUNC returns a list, and we want to combine all the elements of all the lists.

Trivial example:

Less trivial example:

Note that there's an outer FLATMAP whose mapped function is a plain MAP.

Okay, now we move from lists to streams.

(define (stream-flatmap fn strm) 
   (flatten-stream (stream-map fn strm)))

is an ordinary procedure, not a special form. STREAM-MAP is of course just like MAP but using CONS-STREAM, STREAM-CAR, and STREAM-CDR instead of CONS, CAR, and CDR.

But FLATTEN-STREAM is tricky:

(define (flatten-stream strm)
  (if (stream-null? strm)
      the-empty-stream
      (interleave-delayed
       (stream-car strm)
       (DELAY (flatten-stream (stream-cdr strm))))))

Why can't we use plain old INTERLEAVE? If you look at the examples that use INTERLEAVE, it's always in the second input of a CONS-STREAM, e.g., just above ex. 3.66,

(define (pairs s t)
  (CONS-STREAM
   (list ...)
   (INTERLEAVE
    (stream-map ...)
    (pairs ...))))

As a result, the call to INTERLEAVE, including the evaluation of its inputs, is delayed. (And when it's forced, the recursive call to PAIRS again has its call to INTERLEAVE as the second input to CONS-STREAM and therefore delayed.) Note ex. 3.68, in which Louis Reasoner tries to use INTERLEAVE by itself, not inside a CONS-STREAM, and gets in trouble.

I think you could work around this by pulling out the first item of the first stream, to use as the first input to CONS-STREAM, and then juggling things around to put all the rest of the problem in the second input to CONS-STREAM, like this:

(define (flatten-stream strm)
  (cond ((stream-null? strm) the-empty-stream)
        ((stream-null? (stream-car strm))
         (flatten-stream (stream-cdr strm)))
        (else (CONS-STREAM
                (stream-car (stream-car strm))
                (INTERLEAVE
                  (flatten-stream (stream-cdr strm))
                  (stream-cdr (stream-car strm)))))))

There's an extra base case because I'm trying to extract the first item of the first stream, so I have to handle specially the situation in which the first stream doesn't have a first item.

But they chose a different solution, which doesn't require rearranging the inputs and kludgily pulling the first item out of the first stream. Instead, they explicitly DELAY the recursive call to FLATTEN-STREAM, and to compensate for that, they need a special version of INTERLEAVE, called INTERLEAVE-DELAYED, which FORCEs its second input.

I guess what they're thinking is that they'll need INTERLEAVE-DELAYED more than once. They could have made it a special form, like CONS-STREAM, but I think they thought it was too complicated not to have it shown as a procedure that students can read and understand. (Look at where they explain CONS-STREAM instead of defining it.)

Goodnight...

[qw23]

Thanks, bh, for moving posts on Streams library 2 to a separate topic.

[qw23]

So … flatmap is simply append input list: map (function) over (data) ?

And stream-flatmap is combine (map (function) over stream (s)) using (interleave streams) ?

(or variadic interleave input list: map (function) over stream)

[toontalk]

Have you thought about how to avoid duplicates in the stream of rational numbers? Recall that the concept of a countable set is that one can place the set in a one-to-one correspondence with the natural numbers. A stream with duplicates isn't a set.

[qw23]

@toontalk

A stream with duplicates isn't a set.

True. The above was just to see if I'm correctly interpreting SICP flatmap. To make it a set one may e.g. insert for example. Or check if GCD = 1 with every fraction calculated:

(using GCD from the APL library, plus the weird but convenient map over keep from map over stream block )

[sonic123cdmania]

@toontalk

A stream with duplicates isn't a set.

Uhhhh, if you were taking the rational numbers themselves, but taking, say, 1/2 and 2/4 and saying they are UNIQUE, even though they REPRESENT the same number, then it's still a set. In fact, Cantor's diagonal argument USES DUPLICATES(1/1, 2/1, 1/2, 1/3, 2/2, 3/1, ...)

[toontalk]

Maybe initially but Wikipedia claims "Fractions which can be simplified are left out:"

[sonic123cdmania]

@toontalk

claims

There's the kicker. CLAIMS. Doesn't mean that's true.

[toontalk]

But the definition of sets disallows duplicates - I'm not aware of any notion of countability for multisets.

[qw23]

Though an interesting discussion ...

My 2 cents

1. an element can only be in a set once;
2. e.g. 1/2 and 2/4 are different representations of the same number; so ...
3. depending on the perspective (form vs. value) they can either both be separate members of a set, or they must be considered the same member;
4. I lean towards considering the Rationals a set of values, but I fully understand the alternative perspective;
5. In the end, what counts (granted, a corny pun) is that either way the Rationals are countable; it doesn't matter by which index number each Rational is referred to.

... it's off-topic.

[sonic123cdmania]

@toontalk

I'm not aware of any notion of countability for multisets .

Ok, neither have I.

@qw23

Though an interesting discussion ...

My 2 cents

1. an element can only be in a set once;
2. e.g. 1/2 and 2/4 are different representations of the same number; so ...
3. depending on the perspective (form vs. value) they can either both be separate members of a set, or they must be considered the same member;
4. I lean towards considering the Rationals a set of values, but I fully understand the alternative perspective;
5. In the end, what counts (granted, a corny pun) is that either way the Rationals are countable; it doesn't matter which by index number each Rational is referred to.

... it's off-topic.

No it's not, and that's actually a good point.

[bh]

@qw23

I think you left something out here?

[qw23]

No mistake! You can actually do that:

Like you can also do:

[bh]

Ah, okay.

My life has been too hectic lately for me to have a solid chunk of time to look at the library, but I'll get there...

[qw23]

No problem as far as I’m concerned. One’s personal life, and health, should always be one’s top priorities.