Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
7.1. Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:
?- упростить(1 + 1 + а, E).
E = а + 2
?- упростить(1 + a + 4 + 2 + b + с, E).
E = а + b + с + 7
?- упростить(3 + x + x, E).
E = 2*x + 3
7.2. Определите процедуру
добавить(Элемент, Список)
для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, — атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда
Список = [а, b, с | Хвост]
где Хвост — переменная. Цель
добавить(d, Список)
вызовет конкретизацию
Xвoст = [d | НовыйХвост] и
Список = [а, b, с, d | НовыйХвост]
Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.
7.2. Создание и декомпозиция термов: =.., functor, arg, name
Имеются три встроенные предиката для декомпозиции и синтеза термов: functor, arg и =... Рассмотрим сначала отношение =.., которое записывается как инфиксный оператор. Цель
Терм =.. L
истинна, если L — список, начинающийся с главного функтора терма Терм, вслед за которым идут его аргументы. Вот примеры:
?- f(а, b) =.. L.
L = [f, а, b]
?- T =.. [прямоугольник, 3, 5].
T = прямоугольник(3, 5)
?- Z =.. [p, X, f(X,Y) ].
Z = p(X, f(X,Y))
Зачем может понадобиться разбирать терм на составляющие компоненты — функтор и его аргументы? Зачем создавать новый терм из заданного функтора и аргументов? Следующий пример показывает, что это действительно нужно.
Рассмотрим программу, которая манипулирует геометрическими фигурами. Фигуры — это квадраты, прямоугольники, треугольники, окружности в т.д. В программе их можно представлять в виде термов, функтор которых указывает на тип фигуры, а аргументы задают ее размеры:
квадрат(Сторона)
треугольник(Сторона1, Сторона2, Сторона3)
окружность(R)
Одной из операций над такими фигурами может быть увеличение. Его можно реализовать в виде трехаргументного отношения
увел(Фиг, Коэффициент, Фиг1)
где Фиг и Фиг1 — геометрические фигуры одного типа (с одним в тем же функтором), причем параметры Фиг1 равны параметрам Фиг, умноженным на Коэффициент. Для простоты будем считать, что все параметры Фиг, а также Коэффициент уже известны, т.е. конкретизированы числами. Один из способов программирования отношения увел таков:
увел(квадрат(A), F, квадрат(А1)):-
A1 is F*A
увел(окружность(R), F, окружность(R1)):-
R1 is F*R1
увел(прямоугольник(А, В), F, прямоугольник(А1, В1)):-
A1 is F*A, B1 is F*B.
Такая программа будет работать, однако она будет выглядеть довольно неуклюже при большом количестве различных типов фигур. Мы будем вынуждены заранее предвидеть все возможные типы, которые могут когда-либо встретиться. Придется заготовить по предложению на каждый тип, хотя во всех этих предложениях по существу говорится одно и то же: возьми параметры исходной фигуры, умножь их на коэффициент и создай фигуру того же типа с этими новыми параметрами.
Ниже приводится программа, в которой делается попытка (неудачная) справиться для начала хотя бы со всеми однопараметрическими фигурами при помощи одного предложения:
увел(Тип(Пар), F, Тип(Пар1)):-
Пар1 is F*Пар.
Однако в Прологе подобные конструкции, как правило, запрещены, поскольку функтор должен быть атомом, и, следовательно, переменная Тип синтаксически не будет воспринята как функтор. Правильный метод — воспользоваться предикатом '=..'. Тогда процедура увел будет иметь обобщенную формулировку, пригодную для фигур любых типов:
увел(Фиг, F, Фиг1):-
Фиг =.. [Тип | Параметры],
умножспис(Параметры, F, Параметры1),
Фиг1 =.. [Тип | Параметры)].
умножспис([], _, []).
умножспис([X | L], F, [X1 | L1]):-
X1 is F*X, умножспис(L, F, L1).
Наш следующий пример использования предиката '=..' связан с обработкой символьных выражений (формул), где часто приходится подставлять вместо некоторого подвыражения другое выражение. Мы определим отношение
подставить(Подтерм, Терм, Подтерм1, Терм1)
следующим образом: если все вхождения Подтерм'а в Терм заменить на Подтерм1, то получится Терм1. Например:
?- подставить(sin(x), 2*sin(x)*f(sin(x)), t, F).
F = 2*t*f(t)
Под "вхождением" Подтерм'а в Терм мы будем понимать такой элемент Терм'а, который сопоставим с Подтерм'ом. Вхождения будем искать сверху вниз. Поэтому цель
?- подставить(а+b, f(а, А+В), v, F).
даст результат
F = f(а, v)
А = а
В = b
а не
F = f(a, v + v)
А = а + b
В = а + b
При определении отношения подставить нам нужно рассмотреть несколько случаев и для каждого принять свое решение:
если Подтерм = Терм, то Терм1 = Подтерм1;
иначе если Терм — "атомарный" (не структура),
то Терм1 = Терм (подставлять нечего),
иначе подстановку нужно выполнить над аргументами Tерм'a.
Эти правила можно превратить в программу, показанную на рис. 7.3.
Термы, полученные при помощи предиката '=..', разумеется, можно использовать и в качестве целей. Это дает возможность программе в процессе вычислений самой порождать и вычислять цели, структура которых не обязательно была известна заранее в момент написания программы. Последовательность целей, иллюстрирующая этот прием, могла бы выглядеть примерно так:
получить(Функтор),
вычислить(Списарг),
Цель =.. [Функтор | Списарг],
Цель
Здесь получить и вычислить — некоторые определенные пользователем процедуры, предназначенные для вычисления компонент цели. После этого цель порождается предикатом '=..', а затем активизируется при помощи простого указания ее имени Цель.
% Отношение
%
% подставить(Подтерм, Терм, Подтерм1, Терм1)
%
% состоит в следующем: если все вхождения Подтерм'а в Терм
% заменить на Подтерм1, то получится Терм1.
% Случай 1: Заменить весь терм
подставить(Терм, Терм, Терм1, Терм1):-!.
% Случай 2: нечего подставлять
подставить(_, Терм, _, Терм):-
atomic(Терм),!.
% Случай 3: Проделать подстановку в аргументах
подставить(Под, Терм, Под1, Терм1):-
Терм =.. [F | Арги],
% Выделить аргументы
подспис(Под, Арги, Под1, Арги1),
% Выполнить над ними подстановку
Терм1 =.. [F | Арги1].
подспис(Под, [Терм | Термы], Под1, [Терм1 | Термы1]):-
подставить(Под, Терм, Под1, Терм1),
подспис(Под, Термы, Под1, Термы1).
Рис. 7.3. Процедура подстановки в терм вместо одного из его подтермов некоторого другого подтерма.
Некоторые реализации Пролога могут содержать требование, чтобы все цели, появляющиеся в программе, по своей синтаксической форме были либо атомами, либо структурами с атомом в качестве главного функтора. Поэтому переменная, вне зависимости от ее текущей конкретизации, может по своей синтаксической форме не подойти в качестве цели. Эту трудность можно обойти при помощи еще одного встроенного предиката call (вызов), чьим аргументом является цель, подлежащая вычислению. В соответствий с этим предыдущий пример должен быть переписан так:
...
Цель = [Функтор | Списарг],
саll(Цель)
Иногда нужно извлечь из терма только его главный функтор или один из аргументов. В этом случае можно, конечно, воспользоваться отношением '=..'. Но более аккуратным и практичным, а также и более эффективным способом будет применение одной из двух новых встроенных процедур: functor и аrg. Вот их смысл: цель
functor(Терм, F, N)
истинна, если F — главный функтор Tepм'a, а N — арность F. Цель
arg(N, Терм, А)
истинна, если А — N-й аргумент в Терм'е, в предположении, что нумерация аргументов идет слева направо и начинается с 1. Примеры для иллюстрации:
?- functor(t(f(x), X, t), Фун, Арность).
Фун = t
Арность = 3
?- аrg(2, f(X, t(a), t(b)), Y).
Y = t(a)
?- functor(D, дата, 3),
arg(1, D, 29),
arg(2, D, июнь),
arg(3, D, 1982).
D = дата(29, июнь, 1982)
Последний пример иллюстрирует особый случай применения предиката functor. Цель functor(D, дата, 3) создает "обобщенный" терм с главным функтором дата и тремя аргументами. Этот терм обобщенный, так как все три его аргумента — не конкретизированные переменные, чья имена генерируются пролог-системой. Например:
D = дата(_5, _6, _7)
Затем эти три переменные конкретизируются при помощи трех целей аrg.
К рассматриваемому множеству встроенных предикатов относится также и введенный в гл. 6 предикат name, предназначенный для синтеза и декомпозиция атомов. Для полноты изложения мы здесь напомним его смысл. Цель
name(A, L)
истинна, если L — список кодов (в кодировке ASCII) символов, входящих в состав атома А.
Дата публикования: 2015-10-09; Прочитано: 219 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!