CS61A         Summer 2011         Homework 13

Topic: Lazy evaluator, Logic Programming

Reading: Abelson & Sussman, Section 4.2, 4.3

Abelson & Sussman, Section 4.4.1-4.4.3

A version of the lazy evaluator is online in the file

~cs61a/lib/lazy.scm

1. A&S  4.25, 4.26, 4.28, 4.30, 4.32, 4.33

We are not assigning section 4.4.4, which discusses the implementation of the

query system in detail.  Feel free to read it just for interest; besides

deepening your understanding of logic programming, it provides an example of

using streams in a large project.

2. A&S 4.56, 4.57, 4.58, 4.65

For all problems that involve writing queries or rules,

test your solutions. To run the query system and load in the sample data:

> (load "\~cs61a/lib/query.scm")

> (initialize-data-base microshaft-data-base)

> (query-driver-loop)

You're now in the query system's interpreter.  To add an assertion:

(assert! (foo bar))

To add a rule:

(assert! (rule (foo) (bar)))

Anything else is a query.

Extra for Experts:

1. The lecture notes for this week describe rules that allow inference

 of the reverse relation in one direction, i.e.,

;;; Query input:

(forward-reverse (a b c) ?what)

;;; Query results:

(FORWARD-REVERSE (A B C) (C B A))

;;; Query input:

(forward-reverse ?what (a b c))

;;; Query results:

INFINITE LOOP

or

;;; Query input:

(backward-reverse ?what (a b c))

;;; Query results:

(BACKWARD-REVERSE (C B A) (A B C))

;;; Query input:

(backward-reverse (a b c) ?what)

;;; Query results:

INFINITE LOOP

Define rules that allow inference of the reverse relation in

 both directions, to produce the following dialog:

;;; Query input:

(reverse ?what (a b c))

;;; Query results:

(REVERSE (C B A) (A B C))

;;; Query input:

(reverse (a b c) ?what)

;;; Query results:

(REVERSE (A B C) (C B A))

2. Exercise 4.31 in Abelson and Sussman.  This exercise doesn't require

great brilliance, but it's a lot of work and involves a lot of debugging

of details.  On the other hand, completing this exercise will teach you

a lot about the evaluator.

3. Fix the handle-infix procedure from project 4

to handle infix precedence for arithmetic operators properly.

That is, multiplications and divisions should be done before

additions and subtractions.  Comparison operators like =

come last of all.