sicp-ex-4.62



<< Previous exercise (4.61) | Index | Next exercise (4.63) >>


meteorgan

  
  
 rule: 
 (assert! (rule (last-pair (?x) (?x)))) 
 (assert! (rule (last-pair (?u . ?v) (?x)) 
                (last-pair ?v (?x)))) 
  
 ;;; Query input: 
 (last-pair (3) ?x) 
  
 ;;; Query output: 
 (last-pair (3) (3)) 
 ;;; Query input: 
 (last-pair (1 2 3) ?x) 
  
 ;;; Query output: 
 (last-pair (1 2 3) (3)) 
 ;;; Query input: 
 (last-pair (2 ?x) (3)) 
  
 ;;; Query output: 
 (last-pair (2 3) (3)) 
  
 there is no answer for (last-pair ?x (3)) 

codybartfast

After reversing the two parts of the rule it does return results for the last query.


Last-Pair Rule (parts reversed):
================================

  (rule (last-pair (?u . ?v) (?x))
        (last-pair ?v (?x)))

  (rule (last-pair (?x) (?x)))

Results (Rules Reversed):
=========================

    ;;; Query input:
    (last-pair (3) ?x)

    ;;; Query results:
    (last-pair (3) (3))


    ;;; Query input:
    (last-pair (1 2 3) ?x)

    ;;; Query results:
    (last-pair (1 2 3) (3))


    ;;; Query input:
    (last-pair (2 ?x) (3))

    ;;; Query results:
    (last-pair (2 3) (3))


    ;;; Query input:
    (last-pair ?x (3))

    ;;; Query results:
    (last-pair (3) (3))
    (last-pair (?u-20 3) (3))
    (last-pair (?u-20 ?u-22 3) (3))
    (last-pair (?u-20 ?u-22 ?u-24 3) (3))
    (last-pair (?u-20 ?u-22 ?u-24 ?u-26 3) (3))
    (last-pair (?u-20 ?u-22 ?u-24 ?u-26 ?u-28 3) (3))
    (last-pair (?u-20 ?u-22 ?u-24 ?u-26 ?u-28 ?u-30 3) (3))
    (last-pair (?u-20 ?u-22 ?u-24 ?u-26 ?u-28 ?u-30 ?u-32 3) (3))

This is using the implementation from Section 4.4.4. (I won't pretend to know exactly what's going on but it seems that rule parts are evaluated in the reverse order to how they are defined, and with the original order the iterative part of the rule is repeatedly evaluated first.)

Amazing discovery! In fact the two rules are both evaluated alternatively and the second rule has to be evaluated first in order to generate this infinite stream result.