Serendip

Web Studio

問題4.49

各語のリストを amb で選び出して作る。
p253 の脚注にあるように、実行結果が "再帰の一つに「落ち込み」" 止ってしまっている。
問題4.50の特殊形式 ramb でこの問題は解決できるらしい。

(define (require p)
  (if (not p) (amb)))

(define nouns (list 'noun (amb 'student 'professor 'cat 'class)))
(define verbs (list 'verb (amb 'studies 'lectures 'eats 'sleeps)))
(define articles (list 'article (amb 'the 'a)))
(define prepositions (list 'prep (amb 'for 'to 'in 'by 'with)))

(define (parse-prepositional-phrase)
  (list 'prep-phrase
        (parse-word prepositions)
        (parse-noun-phrase)))

(define (parse-sentense)
  (list 'sentense
        (parse-noun-phrase)
        (parse-verb-phrase)))

(define (parse-verb-phrase)
  (define (maybe-extend verb-phrase)
    (amb verb-phrase
         (maybe-extend (list 'verb-phrase
                             verb-phrase
                             (parse-prepositional-phrase)))))
  (maybe-extend (parse-word verbs)))

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

(define (parse-noun-phrase)
  (define (maybe-extend noun-phrase)
    (amb noun-phrase
         (maybe-extend (list 'noun-phrase
                             noun-phrase
                             (parse-prepositional-phrase)))))
  (maybe-extend (parse-simple-noun-phrase)))

(define (parse-word word-list)
  (require (not (null? (cdr word-list))))
  (list (car word-list) (car (cdr word-list))))

実行結果

;;; Amb-Eval input:
(parse-sentense)

;;; Starting a new problem 
;;; Amb-Eval value:
(sentense (simple-noun-phrase (article the) (noun student)) (verb studies))

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(sentense (simple-noun-phrase (article the) (noun student)) (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))))

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(sentense (simple-noun-phrase (article the) (noun student)) (verb-phrase (verb-phrase (verb studies) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))) (prep-phrase (prep for) (simple-noun-phrase (article the) (noun student)))))

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る