►C311/  H311/  A596/  B521 Fall 2024 – Programming Languages
▼Assignments
•10 Assignment 10:   Introduction to logic programming
    contents  ← prev  up  next → 

10 Assignment 10: Introduction to logic programming

"Success is the ability to go from one failure to another with no loss of enthusiasm."

——Winston Churchill

Preliminaries

This week we’ve begun our discussion of relational programming using miniKanren. Before you start the assignment, make sure you have mk.rkt and numbers.rkt from class notes.

(require "mk.rkt")
(require "numbers.rkt")

To further familiarize yourself with miniKanren, you should consult The Reasoned Schemer and the notes from class.

Assignment
Notes

You may find the following notes on transforming Racket programs to miniKanren to be useful. Keep in mind that these notes use old miniKanren syntax where conde means disj, and there’s an implicit conj when goals are written together within parentheses.

Part 1

Write the answers to the following miniKanren expressions. For each problem, explain how miniKanren arrived at the answer. You will be graded on the quality and completeness of your explanation; a full explanation will require several sentences.

Part 2

Here are the Racket procedures assoc, reverse, and stutter:

(define assoc
  (lambda (x ls)
    (match-let* ((`(,a . ,d) ls)
                 (`(,aa . ,da) a))
      (cond
        ((equal? aa x) a)
        ((not (equal? aa x)) (assoc x d))))))
(define reverse
  (lambda (ls)
    (cond
      ((equal? '() ls) '())
      (else
       (match-let* ((`(,a . ,d) ls)
                    (res (reverse d)))
         (append res `(,a)))))))
(define stutter
  (lambda (ls)
    (cond
      ((equal? '() ls) '())
      (else
        (match-let* ((`(,a . ,d) ls)
                     (res (stutter d)))
          `(,a ,a . ,res))))))

Take assoc, reverse, and stutter, and translate them into the equivalent miniKanren relations (assoco, reverseo, and stuttero) and put them at the end of your a10.rkt file. Your numbers.rkt file already contains an implementation of appendo.

The below tests are a guide. Your relations might not pass these tests, as implementing goals in a different order may cause the stream to return results in a different order. So it is possible that your code is correct though the tests fail. The output in the examples below show the results as a list which is different from what the current run and run* output. The output produced by run and run* in the current mk.rkt file is a complex nested structure which stores data related to the new features that have been added. Try to use run! and run*! in order to print the result in a well formatted manner.

Remember that you may need to rearrange some of the goals in your relations to ensure termination (and therefore to pass the tests). In general, recursive calls should come at the end of a sequence of goals, while explicit or implicit calls to == should come at the beginning.

Here are the tests.

> (require "a10.rkt")
> (run 1 q (stuttero q '(1 1 2 2 3 3)))
((1 2 3))
> (run* q (stuttero q '(1 1 2 2 3 3)))
((1 2 3))
> (run 1 q (fresh (a b c d) (== q `(,a ,b ,c ,d)) (stuttero a `(1 ,b ,c 2 3 ,d))))
(((1 2 3) 1 2 3))
> (run 1 q (fresh (a b c d) (== q `(,a ,b ,c ,d)) (stuttero `(,b 1) `(,c . ,d))))
((_0 _1 _1 (_1 1 1)))
> (run 1 q (fresh (e f g) (== q `(,e ,f ,g)) (stuttero `(,e . ,f) g)))
((_0 () (_0 _0)))
> (run 2 q (fresh (e f g) (== q `(,e ,f ,g)) (stuttero `(,e . ,f) g)))
((_0 () (_0 _0)) (_0 (_1) (_0 _0 _1 _1)))
> (run* q (assoco 'x '() q))
()
> (run* q (assoco 'x '((x . 5)) q))
((x . 5))
> (run* q (assoco 'x '((y . 6) (x . 5)) q))
((x . 5))
> (run* q (assoco 'x '((x . 6) (x . 5)) q))
((x . 6))
> (run* q (assoco 'x '((x . 5)) '(x . 5)))
(_0)
> (run* q (assoco 'x '((x . 6) (x . 5)) '(x . 6)))
(_0)
> (run* q (assoco 'x '((x . 6) (x . 5)) '(x . 5)))
()
> (run* q (assoco q '((x . 6) (x . 5)) '(x . 5)))
()
> (run* q (assoco 'x '((x . 6) . ,q) '(x . 6)))
(_0)
> (run 5 q (assoco 'x q '(x . 5)))
(((x . 5) . _0)
  ((_0 . _1) (x . 5) . _2)
  ((_0 . _1) (_2 . _3) (x . 5) . _4)
  ((_0 . _1) (_2 . _3) (_4 . _5) (x . 5) . _6)
  ((_0 . _1) (_2 . _3) (_4 . _5) (_6 . _7) (x . 5) . _8))
> (run 5 q (fresh (x y z)
                (assoco x y z)
                (== `(,x ,y ,z) q)))
((_0 ((_0 . _1) . _2) (_0 . _1))
  (_0 ((_1 . _2) (_0 . _3) . _4) (_0 . _3))
  (_0 ((_1 . _2) (_3 . _4) (_0 . _5) . _6) (_0 . _5))
  (_0 ((_1 . _2) (_3 . _4) (_5 . _6) (_0 . _7) . _8) (_0 . _7))
  (_0 ((_1 . _2) (_3 . _4) (_5 . _6) (_7 . _8) (_0 . _9) . _10) (_0 . _9)))
> (run* q (reverseo '() q))
(())
> (run* q (reverseo '(a) q))
((a))
> (run* q (reverseo '(a b c d) q))
((d c b a))
> (run* q (fresh (x) (reverseo `(a b ,x c d) q)))
((d c _0 b a))
> (run* x (reverseo `(a b ,x d) '(d c b a)))
(c)
> (run* x (reverseo `(a b c d) `(d . ,x)))
((c b a))
> (run* q (fresh (x) (reverseo `(a b c d) `(d    ,q . ,x))))
(c)
> (run 10 q (fresh (x y) (reverseo x y) (== `(,x ,y) q)))
((() ())
  ((_0) (_0))
  ((_0 _1) (_1 _0))
  ((_0 _1 _2) (_2 _1 _0))
  ((_0 _1 _2 _3) (_3 _2 _1 _0))
  ((_0 _1 _2 _3 _4) (_4 _3 _2 _1 _0))
  ((_0 _1 _2 _3 _4 _5) (_5 _4 _3 _2 _1 _0))
  ((_0 _1 _2 _3 _4 _5 _6) (_6 _5 _4 _3 _2 _1 _0))
  ((_0 _1 _2 _3 _4 _5 _6 _7) (_7 _6 _5 _4 _3 _2 _1 _0))
  ((_0 _1 _2 _3 _4 _5 _6 _7 _8) (_8 _7 _6 _5 _4 _3 _2 _1 _0)))
Brainteaser

Chapter 7 of The Reasoned Schemer Second Edition introduces a way to handle integers in relational programming. These are provided in the numbers suite.

Write lengtho, which associates its output with the length of a list as a binary number in reverse order (if you use the provided helpers, this is the normal representation of numbers).

Hint: You can find some functions like pluso, minuso and zeroo in numbers.rkt, make sure to figure out their arguments and what they do. Take a look at them. Once you have taken a look, you will realise that they work only on a least-significant-bit-first representation of binary numbers, as some of the example tests above highlight. Here are some tests:

> (require "a10.rkt")
> (run 1 q (lengtho '() q))
(())
> (run 1 q (lengtho '(a b) q))
((0 1))
> (run 1 q (lengtho '(a b c) q))
((1 1))
> (run 1 q (lengtho '(a b c d e f g) q))
((1 1 1))
> (run 1 q (lengtho q (build-num 0)))
(())
> (run 1 q (lengtho q (build-num 5)))
((0 1 2 3 4))
> (run 10 q (fresh (x y) (lengtho x y) (== `(,x ,y) q)))
((() ())
  ((0) (1))
  ((0 1) (0 1))
  ((0 1 2) (1 1))
  ((0 1 2 3) (0 0 1))
  ((0 1 2 3 4) (1 0 1))
  ((0 1 2 3 4 5) (0 1 1))
  ((0 1 2 3 4 5 6) (1 1 1))
  ((0 1 2 3 4 5 6 7) (0 0 0 1))
  ((0 1 2 3 4 5 6 7 8) (1 0 0 1)))
Just Dessert

Right now in our implementation of miniKanren, run returns the solution stream and a Relay struct. The Relay struct is used to fetch remaining solutions that run couldn’t return by passing Relay to run-next. This behavior is obscured in run! which doesn’t require us to pass a Relay every time to get results. run! uses a set! mutation to achieve its behavior. Now, try to implement run using a global continuation called next formed from Racket’s let/cc to return remaining requested results. One hint would be to start working on the definition of $take. If you can’t implement this, explain why it would be impossible to implement.

> (run 5 (q) (hot-dogs q))
(dog (hot . dog) (hot hot . dog) (hot hot hot . dog) (hot hot hot hot . dog))
> (next 5)
((hot hot hot hot hot . dog)
 (hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot hot . dog))
> (next 5)
((hot hot hot hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot hot hot hot hot hot . dog)
 (hot hot hot hot hot hot hot hot hot hot hot hot hot hot . dog))
    contents  ← prev  up  next →