Лабы_ЭкспСист / Лабораторная №5
.docЛабораторная работа №5.
Консольные приложения.
Цель работы: Научиться создавать консольные приложения Visual Prolog. Освоить отсечения предикатов и основы работы со списками.
Задание: Написать два консольных приложения, для вычисления факториала и для вычисления длины списка.
Порядок выполнения:
1. Ознакомится с понятием отсечения.
2. Реализовать проект по вычислению факториала.
3. Получить основные сведения о списках.
4. Реализовать программу вычисления длины списка.
6.1. Отсечение
Если вы хотите, чтобы система ни делала откат, ни пыталась найти другое предложение после нахождения решение, вы ставите восклицательный знак в хвосте предложения Хорна. После того, как система найдет восклицательный знак, она прерывает поиск новых решений. Восклицательный знак называется cut – отсечение.
Проиллюстрируем использование отсечений на предикате, который находит факториал числа. Математики определяют факториал как:
factorial(0)→1
factorial(n)→n×factorial(n-1)
Используя хорновские предложения, это определение становится следующим:
fact(N, 1) :- N<1, !.
fact(N, N*F1) :- fact(N-1, F1).
Отсечение предотвращает попытку Пролога применить второе предложение для N=0. Другими словами, если вы поставите запрос
fact(0, F)?
программа успешно использует первое предложение для N=0, и ответит, что F=1. Без отсечения она могла бы подумать, что второе предложение определения
fact(N, 1) :- N<1, !.
fact(N, N*F1) :- fact(N-1, F1).
тоже даст решение. Тогда, она попробовала бы использовать его, и сбилась бы. Отсечение обеспечивает, что факториал – функция и отображает каждое значение из домена в одно и только одно значение множества образа. Чтобы реализовать функцию факториала, следуйте следующим указаниям:
1.Создание нового проекта. Выберите пункт Project/New и заполните диалоговое окно Project Settings так:
General
Project Name: facfun
UI Strategy: console
Обратите внимание, что мы собираемся использовать консольную стратегию, не GUI.
2. Сборка. Выберите пункт Build/Build из панели задач, чтобы внести прототип класса facfun в дерево проекта. Отредактируйте facfun.pro, как показано ниже.
implement facfun
open core, console
class predicates
fact : (integer, integer) procedure (i,o).
clauses
classInfo(“facfun”, “1.0”).
fact(N, 1) :- N<1, !.
fact(N, N*F1) :- fact(N-1, F1).
run() :- console::init(), fact(read(), F), write(F), nl.
end implement facfun
goal mainExe::run(facfun::run).
Снова откомпилируйте программу, и запустите её, используя команду Run in Window (не Execute). Напишите число в приглашении к вводу, и вы получите его факториал.
5.2. Списки
Список это упорядоченная последовательность элементов, где упорядоченная означает, что порядок имеет значение. В Прологе список помещается между квадратными скобками, и подразумевается имеющим голову (head) и хвост (tail):
|
Список |
Тип |
Голова |
Хвост |
|
[3, 4, 5, 6, 7] |
Integer* |
3 |
[4, 5, 6, 7] |
|
[“wo3”, “ni3”, “ta1”] |
String* |
“wo3” |
[“ni3”, “ta1”] |
|
[4] |
Integer* |
4 |
[] |
|
[3.4, 5.6, 2.3] |
Real* |
3.4 |
[5.6, 2.3] |
Вы можете соотнести шаблон переменных со списком. Например, если вы соотнесете шаблон
[X|Xs]
со списком [3.4, 5.6, 2.3], вы получите X=3.4 и Xs=[5.6, 2.3], то есть, X соответствует голове списка и Xs соответствует хвосту. Конечно же, вы можете использовать другие две переменные вместо X и Xs в шаблоне [X|Xs]. Так, [A|B], [Head|Tail], [First|Rest] – эквивалентные шаблоны.
Шаблон [X|Xs] соответствует только списку с как минимум одним элементом. Вот шаблон, который соответствует только спискам с как минимум двумя элементами:ок X
|
Шаблон |
Список |
Х1, Х2 |
Хs |
|
[X1, X2|Xs] |
[3, 5, 2, 7] |
X1=3, X2=5 |
[2, 7] |
|
[X1, X2|Xs] |
[2, 7] |
X1=2, X2=7 |
[] |
|
[X1, X2|Xs] |
[7] |
Не соответствуют |
|
|
[X1, X2|Xs] |
[] |
Не соответствуют |
|
Пусть avg будет маленьким проектом, вычисляющим длину списка действительных чисел. Как и в случае facfun, убедитесь, что avg – консольное приложение.
General
Project Name: avg
UI Strategy: console
Откомпилируйте проект, чтобы вставить класс avg в дерево проекта. Затем, отредактируйте avg.pro, как показано ниже. Запустите, используя Run in Window, как и ранее.
%File: avg.pro
implement avg
open core, console
domains
rList= real*.
class predicates
len:(rList, real) procedure (i, o).
clauses
classInfo("avg", "1.0").
len([], 0) :- !.
len([_X|Xs], 1.0+S) :- len(Xs, S).
run():-
console::init(),
List= read(),
len(List, A),
write(A), nl.
end implement avg
goal
mainExe::run(avg::run).
Давайте изучим концепции, стоящие за этой маленькой программой. Первое, что вы сделали, это создали домен:
domains
rList=real*.
Затем, вы определил предикат len/2, который получает список через первый аргумент, и выводит его длину через второй аргумент. Наконец, вы определили предикат run(), чтобы протестировать программу:
run() :-
console::init(), %Инициализировали консоль
List=read(), %Прочитали List с консоли
len(List, A), %Нашли длину списка
write(A), nl. %Вывели длину на экран
Объявление домена удобно, если вы имеете дело с составными алгебраическими типами данных. Тем не менее, это не требуется для таких простых структур, как список действительных чисел.
Ниже вы найдёте ту же программу без объявления домена.
%File: avg.pro
implement avg
open core, console
class predicates
len:(real*, real) procedure (i, o).
clauses
classInfo("avg", "1.0").
len([], 0) :- !.
len([_X|Xs], 1.0+S) :- len(Xs, S).
run():- console::init(),
L= read(),
len(L, A),
write(A), nl.
end implement avg
goal
mainExe::run(avg::run).
Эта программа имеет недостаток: len/2 можно использовать только для подсчёта длины списка действительных чисел. Было бы неплохо, если бы len/2 мог принимать любой тип списка. Это должно быть возможным, если подставлять переменную типа для real*. Однако, до того, как проверять, действительно ли эта схема работает, необходимо придумать способ извещать L=read() что будет конечным типом вводимого списка, и передать эту информацию в len/2. Visual Prolog имеет предикат, который создаёт переменную любого заданного типа. Ниже вы узнаете, как его использовать.
%File: avg.pro
implement avg
open core, console
class predicates
len:(Element*, real) procedure (i, o).
clauses
classInfo("avg", "1.0").
len([], 0) :- !.
len([_X|Xs], 1.0+S) :- len(Xs, S).
run():- console::init(),
hasdomain(real_list, L), L= read(),
len(L, A), write(A), nl.
end implement avg
goal mainExe::run(avg::run).
Следующий шаг – добавить предикаты sum/2 к avg.pro:
class predicates
sum:(rList, real) procedure (i, o).
clauses
sum([], 0) :- !.
sum([X|Xs], S+X) :- sum(Xs, S).
Давайте посмотрим, что произойдёт, если вызвать sum([3.4, 5.6, 2.3], S).
1. sum([3.4, 5.6, 2.3], S[5.6, 2.3]+X), где S[5.6, 2.3]+X=S[3.4, 5.6, 2.3],
соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), с X=3.4, Xs=[5.6, 2.3], дает sum([3.4, 5.6, 2.3], S[5.6, 2.3]+3.4) :- sum([5.6, 2.3], S[5.6, 2.3])
2. sum([5.6, 2.3], S[2.3]+X), где S[2.3]+X=S[5.6, 2.3],
соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), с X=5.6, Xs=[2.3], дает sum([5.6, 2.3], S[2.3]+5.6) :- sum([2.3], S[2.3])
3.sum([2.3], S[]+X), где S[]+X=S[2.3], соответствует предложению sum([X|Xs], S+X) :- sum(Xs, S), с X=2.3, Xs=[], дает sum([2.3], S[]+2.3) :- sum([], S[])
4.sum([], S[]), соответствует предложению sum([], 0.0) :- !, дает S[]=0.
После достижения низа рекурсии, компьютер должен откатиться к началу подсчетов. Что еще хуже, он должен хранить каждый X, который он найдет по пути, чтобы произвести сложение S+X во время отката. Традиционный путь предотвращения отката – использование накопителей. Вот определение, которое использует накопитель для суммирования элементов списка:
add([], A, A).
add([X|Xs], A, S) :- add(Xs, X+A, S).
Давайте посмотрим, как компьютер подсчитывает эту вторую версию суммирования списка.
1. add([3.4, 5.6, 2.3], 0.0, S)
соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S)
дает add([5.6, 2.3], 0+3.4, S)
2. add([5.6, 2.3], 0.0+3.4, S)
соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S)
дает add([2.3], 0+3.4+5.6, S)
3. add([2.3], 0.0+3.4+5.6, S)
соответствует предложению add([X|Xs], A, S) :- add(Xs, X+A, S)
дает add([], 0+3.4+5.6+2.3, S)
что соответствует предложению add([], A, A), возвращая S=11.3.
Вы можете использовать add/3 для вычисления среднего значения списка чисел.
len([], 0) :- !.
len([_X|Xs], 1.0+S) :- len(Xs, S).
add([], A, A) :- !.
add([X|Xs], A, S) :- add(Xs, X+A, S).
sum(Xs, S) :- add(Xs, 0.0, S).
avg(Xs, A/L) :- sum(Xs, A), len(Xs, L).
Описанная выше программа проходит через список дважды, один раз, чтобы подсчитать сумму, и другой, чтобы подсчитать длину. Используя два накопителя, вы можете вычислять длину и сумму вместе.
%File: avg.pro
implement avg
open core, console
class predicates
avg:(real*, real, real, real) procedure (i, i, i, o).
clauses
classInfo("avg", "1.0").
avg([], S, L, S/L).
avg([X|Xs], S, L, A) :-
avg( Xs,
X+S, %добавить X к накопителю суммы
L+1.0, %увеличить на единицу накопитель длины
A).
run():- console::init(),
hasdomain(rList, List), List= read(),
avg(List, 0, 0, A),
write(A), nl.
end implement avg
goal
mainExe::run(avg::run).
Вышеприведенный листинг показывает программу для вычисления среднего значения списка действительных чисел. Используется два накопителя, один для суммы, и другой для количества элементов.