SICP Exercise 4.49

April 30, 2010

SICP Exercise 4.49

(define (parse-word word-list)
  (list (car word-list) (an-element-of (cdr word-list))))

; the results
the student studies
the student studies for the student
the student studies for the student for the student
the student studies for the student for the student for the student
......

SICP Exercise 4.48

April 30, 2010

SICP Exercise 4.48

(define adjectives '(adjective nice tall diligent small white))

(define (parse-simple-noun-phrase)
  (define (parse-adjective-noun)
    (amb (parse-word nouns)
         (list 'adjective-noun
               (parse-word adjectives)
               (parse-adjective-noun))))
  (list 'simple-noun-phrase
        (parse-word articles)
        (parse-adjective-noun)))

;;; Amb-Eval input:
(parse '(the tall professor lectures))

;;; Starting a new problem 
;;; Amb-Eval value:
(sentence 
 (simple-noun-phrase 
  (article the) 
  (adjective-noun (adjective tall) (noun professor))) 
 (verb lectures))

;;; Amb-Eval input:
try-again

;;; There are no more values of
(parse (quote (the tall professor lectures)))

;;; Amb-Eval input:
(parse '(the nice tall professor lectures))

;;; Starting a new problem 
;;; Amb-Eval value:
(sentence 
 (simple-noun-phrase 
  (article the) 
  (adjective-noun (adjective nice) 
                  (adjective-noun (adjective tall) 
                                  (noun professor)))) 
 (verb lectures))

;;; Amb-Eval input:
try-again

;;; There are no more values of
(parse (quote (the nice tall professor lectures)))

;;; Amb-Eval input:
(parse '(the nice tall professor lectures 
             to the diligent student in the small class 
             with the white cat))
; It works.  Output omitted

SICP Exercise 4.47

April 29, 2010

SICP Exercise 4.47

It does not work correctly even for the most simple sentences such as “the professor lectures”. For the above sentence, the parser can produce the correct result when it runs for the first time. But if one runs try-again, it will be stuck in an infinite loop because the evaluation of (parse-prepositional-phrase) always fails. The failure will cause the evaluation of (list 'verb-phrase (parse-verb-phrase) (parse-prepositional-phrase)), which in turn will cause the the evaluation of (parse-prepositional-phrase) again. Moreover, if the sentence contains a misspelled word, the parser will be stuck too.

Changing the order of expressions in the amb would make things even worse. It would fail for the above simple sentence even in the first round.


SICP Exercise 4.46

April 29, 2010

SICP Exercise 4.46

The procedure (parse-sentence) contains (list 'sentence (parse-noun-phrase) (parse-verb-phrase)). The evaluator will evaluate (parse-verb-phrase) first, if it evaluates the arguments of list from right to left. This will fail because a sentence starts with a noun phrase, not a verb phrase.


SICP Exercise 4.45

April 29, 2010

SICP Exercise 4.45

The cat has three possibilities: with the professor, the student, or the class. Either the professor or the student is in the class. So there are 6 possibilities. However, if the cat is with the student, the word “class” must belong to the student because it is between the words “student” and “cat”. Thus there are 5 ways to parse the sentence.

  1. With the cat, the professor lectures in the class. This means

    • The cat is with the professor.
    • The professor is in the class.
  2. The professor lectures in the class that has the cat. This means

    • The cat is with the class.
    • The professor is in the class.
  3. With the cat, the professor lectures to student who is in the class. This means

    • The cat is with the professor.
    • The student is in the class.
  4. The professor lectures to the student in the class who has the cat. This means

    • The cat is with the student.
    • The student is in the class.
  5. The professor lectures to student who is in the class that has the cat. This means

    • The cat is with the class.
    • The student is in the class.

SICP Exercise 4.44

April 28, 2010

SICP Exercise 4.44

(define (safe? positions)
  (define (two-queens-safe? q1 q2)
    (let ((row1 (car q1))
          (col1 (cadr q1))
          (row2 (car q2))
          (col2 (cadr q2)))
      (and (not (= row1 row2))
           (not (= (- col2 col1)
                   (abs (- row2 row1)))))))
  (let ((new-queen (list (last positions) (length positions))))
    (define (check col positions)
      (cond ((null? (cdr positions)) true)
            ((two-queens-safe? (list (car positions) col) 
                               new-queen)
             (check (+ col 1) (cdr positions)))
            (else false)))
    (check 1 positions)))

(define (eight-queens)
  (let ((q1 (amb 1 2 3 4 5 6 7 8)))
    (let ((q2 (amb 1 2 3 4 5 6 7 8)))
      (require (safe? (list q1 q2)))
      (let ((q3 (amb 1 2 3 4 5 6 7 8)))
        (require (safe? (list q1 q2 q3)))
        (let ((q4 (amb 1 2 3 4 5 6 7 8)))
          (require (safe? (list q1 q2 q3 q4)))
          (let ((q5 (amb 1 2 3 4 5 6 7 8)))
            (require (safe? (list q1 q2 q3 q4 q5)))
            (let ((q6 (amb 1 2 3 4 5 6 7 8)))
              (require (safe? (list q1 q2 q3 q4 q5 q6)))
              (let ((q7 (amb 1 2 3 4 5 6 7 8)))
                (require 
                 (safe? (list q1 q2 q3 q4 q5 q6 q7)))
                (let ((q8 (amb 1 2 3 4 5 6 7 8)))
                  (let ((queens (list q1 q2 q3 q4 q5 q6 q7 q8)))
                    (require (safe? queens))
                    queens))))))))))

SICP Exercise 4.43

April 28, 2010

SICP Exercise 4.43

(define (yacht-puzzle)
; father = (last-name daughter yacht)
  (define (last-name f) (car f))
  (define (daughter f) (cadr f))
  (define (yacht f) (caddr f))
  (define (different? f) (not (eq? (daughter f) (yacht f))))
  (define (father-of d fathers)
    (if (eq? d (daughter (car fathers)))
        (car fathers)
        (father-of d (cdr fathers))))
  (let ((Downing (list 'Downing
                       (amb 'Gabrielle 'Lorna 'Mary 'Rosalind)
                       'Melissa))
        (Hall (list 'Hall
                    (amb 'Gabrielle 'Lorna 'Mary 'Melissa)
                    'Rosalind))
        (Hood (list 'Hood 'Melissa 'Gabrielle))
        (Moore (list 'Moore 'Mary 'Lorna))
        (Parker (list 'Parker
                      (amb 'Gabrielle 'Lorna 'Mary 'Melissa 
                           'Rosalind)
                      (amb 'Gabrielle 'Lorna 'Mary 'Melissa 
                           'Rosalind))))
    (require (different? Parker))
    (let ((fathers (list Downing Hall Hood Moore Parker)))
      (define (map proc a)
        (if (null? a)
            '()
            (cons (proc (car a)) (map proc (cdr a)))))
      (let ((daughters (map daughter fathers)))
        (require (distinct? daughters))
        (let ((yachts (map yacht fathers)))
          (require (distinct? yachts))
          (require (eq? (daughter Parker) 
                        (yacht (father-of 'Gabrielle fathers))))
          fathers)))))

Lorna is a daughter of Downing.

; father  daught    yacht
((downing lorna     melissa) 
 (hall    gabrielle rosalind) 
 (hood    melissa   gabrielle) 
 (moore   mary      lorna) 
 (parker  rosalind  mary))

The following code does not assume Mary’s last name is Moore.

(define (yacht-puzzle-2)
  ......
        (Moore (list 'Moore
                     (amb 'Gabrielle 'Mary 'Melissa 'Rosalind)
                     'Lorna))
  ......
)

There are two solutions. The first is the same as before. The second is,

; father  daught   yacht
((downing rosalind  melissa) 
 (hall    mary      rosalind) 
 (hood    melissa   gabrielle) 
 (moore   gabrielle lorna) 
 (parker  lorna     mary)))

Follow

Get every new post delivered to your Inbox.