Advanced Methods in Programming Languages (201-2-4411-01)
HW Assignment 3 - Fall 1996 - Michael Elhadad

Streams - Prolog Interpreters

Problems for Sun 8/12

Notes on running and using Prolog can be found in the Logic Programming course home page.

interleave-stream

(interleave-stream stream1 stream2)
The procedure must return one stream that returns alternatively one element of stream1 and then one element of stream2. For example: 
> (define (integers n) (make-stream n (lambda () (integers (+ n 1)))))
> (define (filter-stream pred? s) 
     (cond ((stream-null? s) the-null-stream)
           ((pred? (stream-car s))
            (make-stream (stream-car s)
                         (lambda () (stream-filter pred? (stream-cdr s)))))
           (else (stream-filter pred? (stream-cdr s)))))
> (define (display-head s n) 
     (if (> n 0) 
        (let ((head (stream-car s)))
          (display head) (display " ")
          (display-head s (- n 1)))))
> (display-head (interleave-stream (filter-stream even? (integers 0))
                                   (filter-stream (lambda () (>= n 10)) 
                                                  (integers 0)))
                6)
0 10 2 11 4 12

merge-stream

(merge-stream stream1 stream2) The procedure combines two ordered streams into one ordered stream eliminating repetitions. Use this procedure to generate in an efficient way, in ascending order and with no repetitions, all positive integers with no prime factors other than 2, 3 and 5. If you call this stream S, note that S is defined by the following facts:
  1. S begins with 1
  2. The elements of (scale-stream 2 S) are also elements of S
  3. The elements of (scale-stream 3 S) are also elements of S
  4. The elements of (scale-stream 5 S) are also elements of S
  5. These are all the elements of S
where (scale-stream n S) is a procedure which returns the stream of elements n*i for each i generated by S.

syntax-expand

(syntax-expand syntax-tree) where syntax-tree is a parsed expression for the following BNF: 
<exp>         ::= <varref>                  varref (var)
               |  <number>                  lit (datum)
               |  (if <exp> <exp> <exp>)    if (test-exp then-exp else-exp)
               |  (proc ({<var>}*) <exp>)   proc (formals body)
               |  (<exp> {<exp>}*)          app (rator rands)
               |  (:= <var> <exp>)          varassign (var exp)
               |  (begin {<exp>}+)          begin (exps)
               |  (let <decls> <exp>)       let (decls body)
               |  (letrec <decls> <exp>)    letrec (decls body)
<decls> ::= ({<decl>}*)
<decl>  ::= (<var> <exp>)                   decl (var exp)
This is a Lisp form of the syntax of the language studied in the text book. syntax-expand must return a new syntax tree, with every let and letrec records replaced by a semantically equivalent app record.

Partial Evaluation (Prolog)

Write a transformer which reads a file foo.pl containing a Prolog program P and writes a file foo_bu.pl containing a program P' which computes the minimal model of P.

P' contains a top level predicate model/0. A call ?- model initiates a computation of the minimal model of P which is to be written on the file foo_mm.pl.

The program you have to write should mimic the behavior of the simple interpreter for bottom-up evaluation given in class

Note that the bottom-up evaluation is finite only in case the minimal model of the program is finite.

see files , dynamic predicates.

Semi Naive Evaluation (Prolog)

One problem with the (naive) bottom-up evaluation technique we have seen in the lecture is that each iteration of the evaluation recomputes everything that was computed in the previous iteration.

For example. If there is a clause 

    h :- a,b,c.
in the program and in one iteration we already proved fact(a), fact(b) and fact(c). then in every subsequent iteration we will prove fact(h) (which will be computed but not added to the database of facts because it is already there.

A semi naive evaluation works as follows. Each fact is associated with the number of the iteration in which it was derived. When solving a clause we make sure that at least one of the facts matched with the atoms in the body is a new fact --- otherwise for sure we have already computed this head in a previous iteration.

In this exercise you are required to implement a meta-interpreter for semi-naive evaluation of logic programs.

Your program must contain a top-level predicate sn_bu/0.

see dynamic predicates.

Last modified Nov 18th, 1996 Michael Elhadad