Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 89
Текст из файла (страница 89)
С ее помощью можно следующим образом реализовать процедурудля поиска Пифагоровых троек, то есть троек чисел (i, j, k) между заданными границами, таких,что i ≤ j и i2 + j 2 = k2 :(define (a-pythagorean-triple-between low high)(let ((i (an-integer-between low high)))(let ((j (an-integer-between i high)))(let ((k (an-integer-between j high)))(require (= (+ (* i i) (* j j)) (* k k)))(list i j k)))))Упражнение 4.36.В упражнении 3.69 рассматривалась задача порождения потока всех Пифагоровых троек, без всякой верхней границы диапазона целых чисел, в котором надо искать.
Объясните, почему простаязамена an-integer-between на an-integer-startingfrom в процедуре из упражнения 4.35не является адекватным способом порождения произвольных Пифагоровых троек. Напишите процедуру, которая решает эту задачу. (Это значит, что Вам нужно написать процедуру, для котороймногократный запрос try-again в принципе способен породить все Пифагоровы тройки.)Упражнение 4.37.Бен Битобор утверждает, что следующий метод порождения Пифагоровых троек эффективнее, чемприведенный в упражнении 4.35.
Прав ли он? (Подсказка: найдите, сколько вариантов требуетсярассмотреть.)(define (a-pythagorean-triple-between low high)(let ((i (an-integer-between low high))(hsq (* high high)))(let ((j (an-integer-between i high)))(let ((ksq (+ (* i i) (* j j))))(require (>= hsq ksq))(let ((k (sqrt ksq)))(require (integer? k))(list i j k))))))4.3.2. Примеры недетерминистских программВ разделе 4.3.3 описывается реализация amb-интерпретатора. Однако для началамы приведем несколько примеров его использования. Преимущество недетерминистского4.3.
SCHEME с вариациями —недетерминистское вычисление387программирования состоит в том, что можно отвлечься от деталей процесса поиска, аследовательно, выражать программы на более высоком уровне абстракции.Логические загадкиСледующая задача (взятая из Dinesman 1968) — типичный представитель большогокласса простых логических загадок.Бейкер, Купер, Флетчер, Миллер и Смит живут на разных этажах пятиэтажного дома.
Бейкер живет не на верхнем этаже. Купер живет не на первомэтаже. Флетчер не живет ни на верхнем, ни на нижнем этаже. Миллер живет выше Купера. Смит живет не на соседнем с Флетчером этаже. Флетчерживет не на соседнем с Купером этаже. Кто где живет?Можно впрямую определить, кто на каком этаже живет, перечислив все возможностии наложив данные нам ограничения48.(define (multiple-dwelling)(let ((baker (amb 1 2 3 4 5))(cooper (amb 1 2 3 4 5))(fletcher (amb 1 2 3 4 5))(miller (amb 1 2 3 4 5))(smith (amb 1 2 3 4 5)))(require(distinct? (list baker cooper fletcher miller smith)))(require (not (= baker 5)))(require (not (= cooper 1)))(require (not (= fletcher 5)))(require (not (= fletcher 1)))(require (> miller cooper))(require (not (= (abs (- smith fletcher)) 1)))(require (not (= (abs (- fletcher cooper)) 1)))(list (list ’baker baker)(list ’cooper cooper)(list ’fletcher fletcher)(list ’miller miller)(list ’smith smith))))Выполнение выражения (multiple-dwelling) дает следующий результат:((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))48 Внашей программе используется следующая процедура, определяющая, все ли элементы списка отличныдруг от друга:(define (distinct? items)(cond ((null? items) true)((null? (cdr items)) true)((member (car items) (cdr items)) false)(else (distinct? (cdr items)))))Процедура member подобна memq, но на равенство проверяет с помощью equal?, а не eq?.Глава 4.
Метаязыковая абстракция388Эта простая процедура работает, но работает очень медленно. В упражнениях 4.39 и 4.40обсуждаются возможные улучшения.Упражнение 4.38.Измените процедуру multiple-dwelling, отказавшись от требования, что Смит и Флетчерживут не на соседних этажах. Сколько решений имеется у измененной загадки?Упражнение 4.39.Влияет ли порядок ограничений в процедуре multiple-dwelling на ответ? Влияет ли он навремя, необходимое для поиска ответа? Если Вы считаете, что он имеет значение, то покажите,как можно ускорить программу, переупорядочив ограничения.
Если Вы считаете, что порядокзначения не имеет, объясните, почему.Упражнение 4.40.Сколько возможных соответствий между людьми и этажами имеется в задаче о проживании, еслиучитывать требование, что все живут на разных этажах, и если его не учитывать? Крайне неэффективно порождать все возможные соответствия между людьми и этажами, а затем полагатьсяна то, что поиск с возвратом отсечет лишнее. Например, большая часть ограничений зависиттолько от одной или двух переменных, соответствующих людям, и их можно было бы проверятьраньше, чем этажи выбраны для всех действующих лиц.
Напишите и продемонстрируйте значительно более эффективную недетерминистскую процедуру, которая бы решала задачу, порождаятолько те варианты, которые еще не исключены благодаря предыдущим ограничениям. (Подсказка:потребуется набор вложенных выражений let.)Упражнение 4.41.Напишите процедуру для решения задачи о проживании на обычной Scheme.Упражнение 4.42.Решите задачу «Лгуньи» (из Phillips 1934):Пять школьниц писали экзаменационную работу. Им показалось, что их родителичересчур интересовались результатом, и поэтому они решили, что каждая девочкадолжна написать домой о результатах экзамена и при этом сделать одно верное иодно неверное утверждение. Вот соответствующие выдержки из их писем:Бетти: «Китти была на экзамене второй, а я только третьей».Этель: «Вам будет приятно узнать, что я написала лучше всех.
Второй была Джоан».Джоан: «Я была третьей, а бедная Этель последней».Китти: «Я оказалась второй. Мэри была только четвертой».Мэри: «Я была четвертой. Первое место заняла Бетти».В каком порядке на самом деле расположились отметки девочек?Упражнение 4.43.Решите с помощью amb-интерпретатора следующую задачу49 .49 Задача взята из книжки «Занимательные загадки», опубликованной в 60-е годы издательством ЛиттонИндастриз.
Книжка приписывает задачу газете «Кэнзас стейт энджинир».4.3. SCHEME с вариациями —недетерминистское вычисление389У отца Мэри Энн Мур есть яхта, и у каждого из четверых его друзей тоже. Этичетверо друзей — полковник Даунинг, мистер Холл, сэр Барнакл Худ и доктор Паркер. У каждого из них тоже есть по дочери, и каждый из них назвал свою яхту вчесть дочери одного из своих друзей. Яхта сэра Барнакла называется Габриэлла, яхтамистера Мура — Лорна, а у мистера Холла яхта Розалинда.
Мелисса, яхта полковника Даунинга, названа в честь дочери сэра Барнакла. Отец Габриэллы владеет яхтой,названной в честь дочери доктора Паркера. Кто отец Лорны?Попытайтесь написать программу так, чтобы она работала эффективно (см. упражнение 4.40).Кроме того, определите, сколько будет решений, если не указывается, что фамилия Мэри Энн —Мур.Упражнение 4.44.В упражнении 2.42 описывалась «задача о восьми ферзях», в которой требуется расставить нашахматной доске восемь ферзей так, чтобы ни один не бил другого. Напишите недетерминистскуюпрограмму для решения этой задачи.Синтаксический анализ естественного языкаПрограммы, которые должны принимать на входе естественный язык, обычно преждевсего пытаются провести синтаксический анализ (parsing) ввода, то есть сопоставитьвходному тексту какую-то грамматическую структуру.
Например, мы могли бы попытаться распознавать простые предложения, состоящие из артикля, за которым идет существительное, а вслед за ними глагол, например The cat eats («Кошка ест»). Чтобывыполнять такой анализ, нам нужно уметь определять части речи, к которым относятсяотдельные слова. Мы можем для начала составить несколько списков, которые задаютклассы слов50 :(define nouns ’(noun student professor cat class))(define verbs ’(verb studies lectures eats sleeps))(define articles ’(article the a))Нам также нужна грамматика (grammar), то есть набор правил, которые описывают,как элементы грамматической структуры составляются из меньших элементов. Простейшая грамматика может постановить, что предложение всегда состоит из двух частей —именной группы, за которой следует глагол, — и что именная группа состоит из артикляи имени существительного.
С такой грамматикой предложение The cat eats разбираетсятак:(sentence (noun-phrase (article the) (noun cat))(verb eats))Мы можем породить такой разбор при помощи простой программы, в которой длякаждого грамматического правила имеется своя процедура. Чтобы разобрать предложение, мы определяем две его составные части и возвращаем список из этих элементов,помеченный символом sentence:50 Здесь мы используем соглашение, что первый элемент списка обозначает часть речи, к которой относятсяостальные слова списка.390Глава 4.
Метаязыковая абстракция(define (parse-sentence)(list ’sentence(parse-noun-phrase)(parse-word verbs)))Подобным образом, разбор именной группы состоит в поиске артикля и существительного:(define (parse-noun-phrase)(list ’noun-phrase(parse-word articles)(parse-word nouns)))На самом нижнем уровне разбор сводится к многократной проверке, является лиследующее неразобранное слово элементом списка слов для данной части речи. Чтобыреализовать это, мы заводим глобальную переменную *unparsed*, содержащую ещенеразобранный ввод. Каждый раз, проверяя слово, мы требуем, чтобы *unparsed* небыла пустым списком и чтобы ее значение начиналось со слова из указанного списка.Если это так, мы убираем слово из *unparsed* и возвращаем его вместе с частью речи(которую можно найти в голове списка)51 .(define (parse-word word-list)(require (not (null? *unparsed*)))(require (memq (car *unparsed*) (cdr word-list)))(let ((found-word (car *unparsed*)))(set! *unparsed* (cdr *unparsed*))(list (car word-list) found-word)))Чтобы запустить разбор, нужно только присвоить переменной *unparsed* весь имеющийся ввод, попытаться проанализировать предложение и убедиться, что ничего неосталось в конце:(define *unparsed* ’())(define (parse input)(set! *unparsed* input)(let ((sent (parse-sentence)))(require (null? *unparsed*))sent))Теперь мы можем опробовать анализатор и убедиться, что он работает на нашемпростом примере:;;; Ввод Amb-Eval:(parse ’(the cat eats));;; Начало новой задачи;;; Значение Amb-Eval:(sentence (noun-phrase (article the) (noun cat)) (verb eats))51 Обратите внимание, что parse-word изменяет список необработанных слов при помощи set!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
