Шпора (Шпоры к первому коллоквиуму), страница 8

Факультативный параметр with задает список свойствзаписываемого утверждения (он имеет такую же структуру, что и список свойств идентификатора,но связан с утверждением в целом). Факультативный параметр rec указывает, какие теоремыследует вызвать при записи данного утверждения (некоторые теоремы могут вызываться в этотмомент автоматически). Факультативный параметр else содержит рекомендации по поводу того,что следует делать, если записать указанное утверждение в базу данных не удалось (например,потому, что такое утверждение в базе данных уже хранится).Пример: пусть переменная X имеет значение green[assert (box A) (with col .X) (else)]- параметр rec в этом примере опущенПри выполнении этого обращения к функции assert происходит следующее:1) в базу данных записывается утверждение (box A) - имеется ящик A,2) с ним связывается список свойств (col green)- его цвет – зеленый,3) если утверждение записать не удалось, то (в соответствии с конкретным видомпоследнего параметра – else – вырабатывается неуспех.Поиск[search pat test?] – основная функция для поиска в базе данных утверждений по образцу pat.Параметр test (факультативный) позволяет задать требования, предъявляемые к списку свойствутверждения.Функция search ставит развилку; ищет утверждение, соответствующее образцу; проверяет егосписок свойств (если он не удовлетворяет требованиям параметра test, ищется другоеутверждение соответствующее образцу).

Если подходящее (соответствует образцу, удовлетворяеттребованиям test, параметр test не задан) утверждение найдено, оно является результатомобращения к search; развилка не уничтожается, следовательно, если в динамике до этогообращения к search «доберется» неуспех, начнется поиск новых утверждений, соответствующихpat. Если найти утверждение, соответствующее pat и удовлетворяющее test, не удалось, развилкаотменяется и вырабатывается неуспех.Пример: пусть после выполнения обращения к assert из предыдущего примера мы задаем:[search (box [ ]) (test col [non red])]Результат поиска – утверждение (box A).Поиск утверждений можно вести поэтапно – находить утверждения, «частично соответствующие»образцу (функция candidates, обращение к которой имеет вид [candidates pat type?]), а затемболее детально анализировать полученный «список кандидатов». Можно искать только одноподходящее утверждение (функция search1).Вычеркивание[erase pat test?] – функция для удаления из базы данных утверждений, соответствующих образцуpat и удовлетворяющих требованиям параметра test (если он задан).Пример: стереть утверждение (box A) со списком свойств (col green) можно так:[erase (box [ ]) (test col [non red])]Плэнерская база данных, отображающая состояние проблемной среды:(room R1)(room R2)(conn R1 R2 D)(door D)(box A) – (col green)(box B) – (col red)R1R2ROBBY(at ROBBY R1)(at A R2)(at B R2)ABDВ этой ситуации можно выполнять операции поиска:[search (at ROBBY R1)] → T[search (at ROBBY R2)] → ( )[search (at ROBBY *X)] → T, X:= R1[find all (Y) .Y [search (room *Y)]] → (R1 R2)Режим возвратовВ язык Плэнер встроен т.н.

режим возвратов, который упрощает реализацию различныхпоисковых алгоритмов, использующих перебор вариантов. Суть этого режима в следующем. Влюбом месте программы может быть установлена т.н. развилка, от которой возможно нескольковариантов продолжения работы программы. Выбирается один из вариантов, и программапродолжает свою работу.

Если затем окажется, что этот вариант неуспешен, вырабатывается т.н.неуспех, по которому программа автоматически «откатывается» к последней (по времени)развилке. При этом отменяются все изменения (в значениях переменных и т.п.), произведенныена неуспешном пути, и в этой развилке выбирается следующий вариант, после чего программаснова «идет вперед».

Если в развилке уже не оказалось нерассмотренных альтернатив, то неуспехвозвращает программу к предыдущей развилке.В каких местах программы ставить развилки и с какими альтернативами, считать ливыбранный путь вычисления неуспешным и когда вырабатывать неуспех – за все это отвечаетавтор программы. Встроенный же режим возвратов обеспечивает запоминание мест развилок ито, какие альтернативы в них еще не рассматривались, обеспечивает возврат программы понеуспеху к последней развилке и отмену ранее произведенных изменений в значенияхпеременных.Ниже перечислены некоторые из встроенных функций языка Плэнер, позволяющихреализовать режим возвратов.[among e]Значением аргумента должен быть список.

Если этот список пуст, функция вырабатывает неуспех,который автоматически возвращает программу к предыдущей ее развилке. Иначе функциязапоминает развилку, альтернативами которой является то, что функция в качестве своегозначения может выдать любой элемент из этого списка. Вначале функция выдает как своезначение первый элемент списка, завершает на этом работу, и программа продолжает своивычисления. Но если позже в программе возникнет неуспех, который вернет ее к даннойразвилке, то функция возобновит свою работу и теперь как свое значение выдаст второй элементсписка, после чего программа снова «идет вперед». И так далее, пока в списке остаютсянерассмотренные элементы. После выдачи в качестве своего значения последнего элементасписка, функция уничтожает свою развилку и потому последующий неуспех уже не будет здесьостановлен.[alt e1 e2 … en]Функция ставит развилку, i-я альтернатива которой – вычисление формы ei. Если вычислитьзначение удалось, функция заканчивает работу со значением Ei.

Перед вычислением en развилкауничтожается.[fail]Эта функция вырабатывает неуспех, по которому программа автоматически возвращается кпоследней (по времени) развилке. (Если развилок нет, то вычисление всего выражения самоговерхнего уровня программы считается окончившимся неуспешно.)[pset v e]Это аналог функции set, т.е. переменной, имя которой является значением аргумента v,присваивается новое значение – значение аргумента e. Однако, если присваивание,осуществленное функцией set, отменяется при неуспехе, то действие функции pset при неуспехене будет отменено.

Функция pset (и ей подобные) применяется, когда надо сохранитьинформацию, полученную на неуспешном пути вычисления программы, для последующих путей.Для управления режимом возвратов помимо использования процедур, результаты которыхне отменяются при неуспехе, в Плэнере есть и другие средства:- уничтожение развилок и/или обратных операторов,- использование именованных развилок.Пример плэнер-программы, решающей переборную задачу на основе бэктрекинга:Пусть задан список L положительных целых чисел. Нужно подобрать набор чисел из L (они могутповторяться), сумма которых равна заданному числу N.[define sum (lambda (L N) [prog ( K (M ( )) (S 0))A[set K [among .L]] [set M ( .K !.M)] [set s [+ .K .S]][cond ([eq .S .N] .M]([lt .S .N] [go A])(T [fail])] ])]Трассировка выполнения программы при L = (6 3 2 1) и N = 5:Вход: K – без значения, M = ( ), S = 0[among (6 3 2 1)] → 6[among (6 3 2 1)] → 3[set K 6]обр.оператор [unassign K][set K 3][set M (6)]обр.оператор [set M ( )][set M (3)][set S 6]обр.оператор [set S 0][set S 3]S > 5 → неуспехS < 5 → переход по метке A и новый вызовamong: [among (6 3 2 1)] → 6[among (6 3 2 1)] → 3[among (6 3 2 1)] → 2неуспехнеуспехS = 5, выход со значением M.Отметим, что развилки в первом и втором обращениях к функции among остаются.

Если вописанное обращение к функции sum откуда-то извне «придет» неуспех, вычисление можетвозобновиться (при этом будут выбираться не исследованные ранее альтернативы). Например:[prog (X) [set X [sum (6 3 2 1) 5]] [cond ([neq [length .X 3]] [fail])] .X] → (1 1 3).Напечатать (поочередно) все решения рассматриваемой задачи можно с помощью такойконструкции:[prog ( ) [alt ( ) [return T]][print [sum (6 3 2 1) 5]] [fail]]А собрать все решения (в списке Y) и затем выдать этот результат на печать можно так:[prog (X (Y ( )) ) [alt ( ) [return .Y]][set X [sum (6 3 2 1) 5]][pset Y (!.Y .X)] [fail]]ТеоремыТеорема Плэнера – процедура, вызываемая по образцу.В языке существуют три типа теорем:• «целевые» (типа conseq),• «при записи» (типа antec),• «при вычеркивании» (типа erasing).Целевые теоремы используются при планировании решения задач.Если плэнерская база данных может рассматриваться как модель проблемной ситуации, то наборцелевых теорем – как набор средств решения соответствующей задачи.

Отобранный иупорядоченный набор теорем может трактоваться как план решения: отдельная теорема из этогонабора описывает некоторое элементарное действие (перемещение робота из одной точки вдругую, применение некоторой формулы интегрирования и т.п.). Примечательно, что мы можемне знать имена теорем, перебираемых в ходе планирования решения задачи и/или попавших вокончательный вариант плана решения. Автоматически выбираются такие теоремы, которыеприводят к достижению цели, описываемой в образце этой теоремы.

Вызов теорем происходит всочетании с режимом возвратов; распространение неуспеха может влиять на процесспланирования решения.Все теоремы – любого из трех указанных типов – пользователь должен определять сам(встроенных теорем в языке нет).Пример определения целевой теоремы:[define TRAN-R (conseq (x y)(at R *y)[search1 (AT R *x)][erase (AT R .x)][assert (AT R .y)] )]Эта теорема (с именем TRAN-R) описывает перемещение робота (R) из точки x в точку y. Теоремаможет быть вызвана по образцу – (at R *y) – в ситуации, когда ставится цель «робот R долженпопасть в некоторую точку проблемной среды», скажем в точку G (такая целевая ситуацияописывается выражением (at R G), которое соответствует образцу теоремы). Добиться этогоможно, применив данную теорему (выполнив соответствующее ей действие в предметном мире)или, возможно, какие-то другие теоремы из числа описанных в программе.Тело этой теоремы предписывает:- найти точку, в которой находится R,- вычеркнуть из базы данных утверждение о том, что R находится в этой точке,- записать в базу данных утверждение о новом местонахождении R.Вызов целевых теорем осуществляется с помощью функции achive (или goal):[achive pat rec?]- pat – образец, rec? – факультативная рекомендация;[goal pat test? rec?] - pat – образец, test? – факультативный набор требований к списку свойствутверждения, rec? – факультативная рекомендация;Функция goal перед тем, как начать вызов теорем, проверяет, не представлена ли целеваяситуация в базе данных в виде утверждения (это означает, что цель на самом деле достигнута,никакого вызова теорем, никакого планирования решения не нужно).Факультативный параметр rec (рекомендации) позволяет влиять на процесс перебора теорем,отдавать приоритет некоторым теоремам, учитывать их «стоимость» и т.п.