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

большие по объему хранилища данных (базы знаний) и средства эффективной работы с ними;10. символьные (в основном) данные;11. модели, отражающие состояние проблемной среды;12. переборные алгоритмы;13. алгоритмы поиска по образцу;14. гибкие структуры управления.-средства для работы со списками (лисповская часть, используется для работы сосписками)плэнерская база данных (используется для моделирования ситуаций проблемной среды)встроенный режим возвратов (реализует один из основных методов перебора – бэктрекинг)аппарат работы с образцами (используется для анализа структуры списков)аппарат теорем (используется при планировании решения)Основные составляющие языка Плэнер:-позволяют достаточно эффективно (и быстро) реализовать соответствующие возможности.Три типа процедур языка Плэнер:- функции;- сопоставители (для работы с образцами);- теоремы (процедуры, вызываемые по образцу).Обращение к функции:Примеры конструкций и процедур Плэнера:[ELEM -2 (A B C D)] → CВыдать второй (2), считая с конца списка (знак "минус" при 2), элемент списка (A B C D).Сопоставление образца с выражением:[IS (*X ПРИШЕЛ !*Y) (САША ПРИШЕЛ ИЗ МАГАЗИНА)] → TСопоставление успешно, то есть образец (*X ПРИШЕЛ !*Y) соответствует выражению (САШАПРИШЕЛ ИЗ МАГАЗИНА).

Побочный эффект: переменная X получает значение САША, апеременная Y получает значение (ИЗ МАГАЗИНА)Утверждение плэнерской базы данных:(BOX A (3 7)) - ящик с названием А находится на плоском квадратном поле с пронумерованнымиклетками в третьей строке (по горизонтали) и в седьмом столбце (по вертикали).Запись утверждения в плэнерскую базу данных:[ASSERT (BOX A) (WITH COL RED)] – в базу данных записывается утверждение (BOX A), тоесть "А является ящиком"; записывается также, что "цвет" (COL) этого ящика "красный" (RED).Поиск утверждения в плэнерской базе данных:[SEARCH (BOX [ ]) (TEST COL [NON GREEN])] – в базе данных ищется утверждение онекотором ящике, цвет которого не (NON) зеленый (GREEN); возможный ответ (результат поиска)– (BOX A).Определение плэнерской теоремы:[DEFINE ОСВОБОДИЛИ (ERASING (X)(=ЗАНЯТ= *X)[ASSERT (=СВОБОДЕН= .X)])]Если из базы данных вычеркивается утверждение о том, что "поверхность некоторого кубика Xзанята" (если так, то на него нельзя поставить другой кубик), то автоматически будет вызвана ивыполнена эта теорема.

Она запишет в базу данных утверждение: "поверхность этого кубика Xосвободилась" (теперь на него можно поставить другой кубик).Перейдем к более детальному рассмотрению основных составляющих Плэнера.Основные объекты языка, средства для работы со спискамиВыражения:• атомарные:- обращения к переменным- атомы: идентификаторы, числа, строки• списковые:- L-списки (списки в круглых скобках: ( и ) )- P-списки (списки в квадратных скобках: [ и ] )- S-списки (списки в «уголках»: < и > )Ограничители: <пробел>, ( , ) , [ , ] , < , >; цифры; буквы; специальные литеры + , - , . , * , : , ! .Префиксы: . , * , : - простое обращение к переменным; !.

, !* , !: - сегментное обращение кпеременным.Простые формы:- атомы (значением атома является сам этот атом),- обращения к переменным с префиксом . ,- обращения к константам с префиксом : ,- L-списки (значением L-списка является список из значений его элементов),- P-списки (обращения к процедурам).Сегментные формы:- обращения к переменным с префиксом !. ,- обращения к константам с префиксом !: ,- S-списки (сегментные обращения к процедурам).В языке Плэнер, как и в Лиспе, программа и обрабатываемые ею данные строятся извыражений, к которым относятся: атомы, обращения к переменным, состоящие из префикса иимени переменной (например, .X) и списки всех трех видов. Некоторые выражения (формы)можно вычислять, получая в результате значения (ими являются выражения).

Программа наПлэнере представляет собой последовательность форм, ее выполнение заключается в вычисленииэтих форм.В языке имеется много встроенных (стандартных) функций.Определение новых функцийДля определения новой функции следует обратиться к встроенной функции define:[define f dexp]Вычисление функции define в качестве побочного эффекта приводит к появлению в программеновой функции с именем f и т.н. определяющим выражением dexp, которое должно иметь вид(lambda (v1 v2 … vn) e)(n≥0)где vi - формальные параметры новой функции, а e - форма, зависящая от vi.При последующем обращении к этой новой функции[f a1 a2 … an]сначала вычисляются аргументы (фактические параметры) ai, затем вводятся локальныепеременные vi, которым присваиваются значения соответствующих аргументов ai, и далеевычисляется форма e при этих значениях переменных vi, после чего эти переменныеуничтожаются.

Значение данной формы становится значением функции f при аргументах ai.Операции над списками[elem n l]Значением аргумента n должно быть ненулевое целое число (обозначим его N), а значениемвторого аргумента - список (L) с любыми скобками. Значением функции является N-й от началаэлемент списка L, если N>0, или |N|-й от конца элемент этого списка, если N<0. В случае, когда вкачестве n явно указано число, имя функции в обращении можно опустить; например, [1 .X] - этосокращение от [elem 1 .X], т.е. выделяется первый от начала элемент списка, являющегозначением переменной X.[rest n l]Значением аргумента n должно быть ненулевое целое число (N), а значением второго аргумента список (L) с любыми скобками.

Значением функции является результат отбрасывания N первыхэлементов списка L, если N>0, или |N|-й последних его элементов, если N<0.[head n l]В такой же ситуации значением функции является список из N первых элементов списка L, еслиN>0, или |N|-й последних его элементов, если N<0.Пример: [rest 2 [head 5 (1 2 3 4 5 6) ] ] → (3 4 5)Если требуется вычислить список в круглых скобках(e1 e2 … en)(n≥0)т.е. если он рассматривается как форма, то все его элементы должны быть формами. Значениемтакого списка является список (с круглыми скобками) из значений его элементов. Например, еслипеременная X имеет значение (a b), то значением списка (.X c [-1 .X]) является список ((a b) c b).В таких списках можно использовать сегментные формы (сегментные обращения кпеременным и сегментные обращения к процедурам, <elem 5 .X>). Сегментная формавычисляется как обычная (простая) форма, но затем у ее значения, если это список,отбрасываются внешние скобки, и полученная таким образом последовательность элементовпоставляется вместо сегментной формы.

Например, если переменная X имеет значение (a (b c)),то:(5 .X ( )) → (5 (a (b c)) ( )), (5 !.X ( )) → (5 a (b c) ( )), (!.X !.X) → (a (b c) a (b c)).Если переменная X имеет значение (1 2), а переменная Y – значение (3 4):(.X !.Y) → ((1 2) 3 4)– на Лиспе эти действия задаются так: (cons X Y)(!.X !.Y) → (1 2 3 4)– на Лиспе эти действия задаются так: (append X Y)Арифметические функции[+ n1 n2 … nk](k≥2)Значениями аргументов должны быть числа. Результат вычисления функции – их сумма.[- n1 n2]Значениями обоих аргументов должны быть числа. Значение функции – их разность.[max n1 n2 … nk](k≥2)Значениями аргументов должны быть числа.

Результат вычисления функции – их максимум.(k≥2)[min n1 n2 … nk]Значениями аргументов должны быть числа. Результат вычисления функции – их минимум.ПредикатыПредикатом называется форма, значение которой рассматривается как логическое значение«истина» или «ложь».

При этом в Плэнере «ложью» считается пустой список ( ), а «истиной» –любое другое выражение (чаще всего в роли «истины» выступает атом T).[num e]Эта функция-предикат проверяет, является ли числом значение ее аргумента. Если да, то значениефункции равно T («истина»), иначе – ( ) («ложь»).[empty e]Функция проверяет, является ли значение ее аргумента пустым списком (с любыми скобками).Если да, то значение функции равно T, иначе – ( ).[eq e1 e2]Функция сравнивает значения своих аргументов.

Если они равны, то значение функции – T , иначе– ( ).[neq e1 e2]Аналог, но значения аргументов сравниваются на «не равно».[memb e l]Значением функции является номер первого вхождения формы E в список L.[gt n1 n2], [ge n1 n2], [lt n1 n2] – сравнение, соответственно, на «больше», «больше илиравно» и «меньше».Предикаты, проверяющие состояние переменныхВ Плэнере переменные (формальные параметры процедур или локальные переменныеблоков) могут находиться в одном из трех состояний:1) переменная не описана (в некоторой функции встретилась нелокальная переменная, котораяне описана в динамически объемлющих процедурах/блоках),2) переменная описана, но не имеет значения,3) переменная описана и имеет некоторое значение.Для анализа таких ситуаций используются предикаты: [bound v] и [hasval v].Первый из этих предикатов проверяет, является ли значение его параметра описанной (вдинамически объемлющих процедурах/блоках) переменной.

Если да, возвращается значение T,иначе – ( ).Значением аргумента предиката hasval должно быть имя переменной, существующей в данныймомент. Функция проверяет, имеет ли сейчас эта переменная какое-либо значение или нет. Еслиимеет, то функция возвращает результат T, а иначе - результат ( ).Функции для работы со списками свойств идентификаторов«условноевыражение»Идентификаторы (и некоторые другие объекты) Плэнера могут иметь т.н. списки свойств –списки пар: свойство-значение.