Costas-Tyros_rus_MS

кPaintResponder’у формы map.frm.

%Файл draw.cl class draw

open core predicates

drawThem:(windowGDI). end class draw

%Файл draw.pro implement draw

open core, vpiDomains, vpi

class facts

city:(string Name, pnt Position). conn:(pnt, pnt).

class predicates connections:(windowGDI). drawCities:(windowGDI).

clauses

city("Salt Lake", pnt(30, 40)). city("Logan", pnt(100, 120)). city("Provo", pnt(100, 160)).

conn(pnt(30, 40) , pnt(100, 120)). conn(pnt(100, 120), pnt(100, 160)).

drawCities(W) : city(N, P),

P= pnt(X1, Y1),

X2= X1+10, Y2= Y1+10, W:drawEllipse(rct(X1, Y1, X2, Y2)), W:drawText(pnt(X1, Y1), N), fail.

drawCities(_Win). connections(W) : conn(P1, P2),

W:drawLine(P1, P2), fail. connections(_W).

drawThem(Win) : connections(Win), drawCities(Win).

end implement draw

Рисунок 5.6 Класс draw.

41

5.11.Примеры

В этой главе присутствуют три примера: mapDataBase рисует положение трёх главных городов штата Юта, когда нажимается соответствующая городу кнопка; drawMap рисует карту направлений дорог Юты; drawMapObj является GDI версией drawMap.

5.12. Представления о логике: Смысл предложений Хорна.

Предложения Хорна имеют вид

H :­ T1, T2, T3…

Значение этого предложения следующее:

Если T1 И T2 И T3 истинны, то H тоже истинно.

Ранее вы видели, что это утверждение эквивалентно

H является истинным или конъюнкция T1 И T2 И T3 не является истинной.

Последняя интерпретация проливает свет на значение символа, изображающего «шею» пред ложения, в котором точка с запятой заменяет связующее «если», а знак минус заменяет логическое отрицание. Тогда, утверждение

H :­T

означает: или H истинно, или не T. Чтобы закончить наше изучение связок, используемых в Про логе, я напомню, что запятая заменяет И, точка с запятой заменяет ИЛИ, а знак > заменяет if…then –

ЕСЛИ…ТО.

42

Глава 6: Консольные приложения

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

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).

тоже даст решение. Тогда, она попробовала бы использовать его, и сбилась бы. Отсечение обес печивает, что факториал является функцией и отображает каждое значение из домена в одно и толь ко одно значение множества образа. Чтобы реализовать функцию факториала, следуйте следующим указаниям:

•Создание нового проекта. Выберите пункт Project/New и заполните диалоговое окно

Project Settings так:

General

Project Name: facfun

UI Strategy: console

Обратите внимание, что мы собираемся использовать консольную стратегию, не GUI.

•Постройка. Выберите пункт Build/Build из панели задач, чтобы внести прототип класса facfun в дерево проекта. Отредактируйте facfun.pro, как показано ниже.

%Файл main.pro

implement main

43

class predicates

fact : (integer N, integer Res) procedure (i,o). clauses

classInfo(“facfun”, “1.0”).

fact(N, 1) : N<1, !. fact(N, N*F) : fact(N 1, F).

run() : console::init(), fact(read(), F), stdio::write(F), stdio::nl. end implement main

goal mainExe::run(main::run).

Снова постройте программу, и запустите её, используя команду Run in Window. Напишите число в

приглашении к вводу, и вы получите его факториал. NB: Чтобы протестировать консольную програм му, используйте Run in Window, не Execute.

6.2.Списки

Есть книга о языке Lisp, в которой говорится: список есть упорядоченная последовательность элементов, где упорядоченная означает, что порядок имеет значение. В Прологе список помещается между квадратными скобками, и подразумевается имеющим голову (head) и хвост (tail):

Вы можете соотнести шаблон переменных со списком. Например, если вы соотнесете шаблон

[X|Xs]

со списком [3.4, 5.6, 2.3], вы получите X=3.4 и Xs=[5.6, 2.3], то есть, X соответствует голове списка и Xs соответствует хвосту. Конечно же, вы можете использовать другую пару переменных вместо X и Xs в шаблоне [X|Xs]. Так, [A|B], [X|L], [Head|Tail], [First|Rest] и [P|Q] – эквивалентные шаблоны. Вот ещё несколько примеров соответствий для шаблона [X|Xs]:

Как вы можете видеть, шаблон [X|Xs] соответствует только списку как минимум с одним элемен том. Вот шаблон, который соответствует только спискам как минимум с двумя элементами:

44

Пусть avg будет маленьким проектом, вычисляющим длину списка действительных чисел. Как и в случае facfun, убедитесь, что avg – консольное приложение.

General

Project Name: avg

UI Strategy: console

Откомпилируйте проект, чтобы вставить класс avg в дерево проекта. Затем, отредактируйте avg.pro, как показано ниже. Запустите, используя Run in Window, как и ранее.

% Файл main.pro implement main

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 main goal

mainExe::run(main::run).

Давайте рассмотрим концепции, стоящие за этой маленькой программой. Первое, что вы сдела ли, это создали домен:

domains rList=real*.

Затем, вы определил предикат len/2, который через первый аргумент получает список, и через второй аргумент выводит его длину. Наконец, вы определили предикат run(), чтобы протестировать программу:

Объявление домена удобно, если вы имеете дело с составными алгебраическими типами дан ных. Тем не менее, это не требуется для таких простых структур, как список действительных чисел. Ниже вы найдёте ту же программу без объявления домена.

% Файл main.pro implement main

open core, console

45

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(),

List= read(), len(List, A), write(A), nl.

end implement main goal

mainExe::run(main::run).

Эта программа имеет недостаток: len/2 можно использовать только для подсчёта длины списка действительных чисел. Было бы неплохо, если бы len/2 мог принимать любой тип списка. Это будет возможно, если подставлять переменную типа вместо real*. Однако, до того, как проверять, дейст вительно ли эта схема работает, необходимо придумать способ извещать L=read() что будет конеч ным типом вводимого списка, и передать эту информацию в len/2. К счастью, есть предикат, кото рый создаёт переменную любого заданного типа. Ниже вы узнаете, как его использовать.

implement main /* в файле main.pro */ 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 main

goal mainExe::run(main::run).

Следующий шаг – добавить предложения sum/2 к main.pro:

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)

соответствует предложению 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[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[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 во время от

46

ката. Традиционный путь предотвращения отката – использование накопителей. Вот определение, которое использует накопитель для суммирования элементов списка:

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).

Описанная выше программа проходит через список дважды: один раз, чтобы подсчитать сумму, и другой, чтобы подсчитать длину. Используя два накопителя, вы можете вычислять длину и сумму одновременно.

% Файл main.pro implement main

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) :

run(): console::init(), List= read(), avg(List, 0, 0, A), write(A), nl.

end implement main

47

implement main open core

domains

pp2 = (real Argument1, real Argument2) > real ReturnType.

clauses

classInfo("main", "hi_order").

class predicates sum:pp2. prod:pp2.

red:(pp2, real*, real, real) procedure (i, i, i, o).

clauses

sum(X, Y)= Z : Z=X+Y. prod(X, Y)= Z : Z=X*Y.

red(_P, [], A, A) : !.

red(P, [X|Xs], A, Ans) : red(P, Xs, P(X, A), Ans).

run(): console::init(), red(prod, [1,2,3,4,5], 1, X), stdio::write(X), stdio::nl, succeed().

end implement main

goal mainExe::run(main::run).

Рисунок 6.1. Сокращение в Прологе

•«Молния» (ZIP) Это устройство, используемое в сплошной застежке для одежды, изобретенной канадским инженером Гидеоном Сандбэком (Gideon Sundback). Это устройство сводит с ума, ко гда не работает, и является причиной такого количества инцидентов с мальчишками, что врачам и медсёстрам потребовалось специальное обучение, чтобы разбираться с этими устройствами.

class predicates

dotproduct:(real*, real*, real) procedure (i, i, o). clauses

dotproduct([], _, 0) : !. dotproduct(_, [], 0) : !.

dotproduct([X|Xs], [Y|Ys], X*Y+R) : dotproduct(Xs, Ys, R).

49

Пример показывает применение этой схемы с последующим шагом редукции для вычисления скалярного произведения двух списков. В выражении X*Y+R умножение используется для закрытия одного зажима застежки.

Мы можем захватить эту схему в предикате более высокого порядка точно так же, как захватили схему редукции. На самом деле, мы можем закрывать каждый зажим застёжки с помощью функций того же рода, что мы использовали для осуществления редукции. На рис. 6.2 вы можете найти (не очень эффективную) реализацию zip в Прологе. Я добавил этот листинг, потому что не один человек написал мне, запрашивая полный разбор этой важной темы; я считаю, что не могу предоставить пол ный разбор, так как это выйдет за пределы этой книги; в конце концов, моя цель заключается в том, чтобы избегать чрезмерно крутых кривых обучения для начинающих; в то же время, примеров на рис. 6.1 и 6.2 должно быть достаточно для того, чтобы показать, как писать предикаты высших поряд ков в Visual Prolog. Люди, которые хотят изучить возможности логики и функций высших порядков, могут обратиться к книгам таких авторов, как [Wadler & Bird] или статьям [John Hughes].

Предикат zip имеет два аргумента. Первый аргумент является двухместной функцией; в листинге 6.2 я предоставляю две из таких функций, но вы можете определить ещё. Второй и третий аргументы содержат списки, которые должны быть застёгнуты1 друг с другом. Четвёртый аргумент содержит результат операции. Определение zip/4 простое:

zip(_P, [], _, []) : !. zip(_P, _, [], []) : !.

zip(P, [X|Xs], [Y|Ys], [Z|As]) : Z= P(X, Y), zip(P, Xs, Ys, As).

Если какой либо из входных списков опустеет, первое или второе предложение остановит рекур сию, произведя пустой список как результат; иначе, третье предложение сцепит головы двух входных списков и продолжит обработку их оставшихся частей. Мне хочется верить, что этого достаточно для начала.

6.4.Операции состроками.

Ниже вы найдете несколько примеров операций со строками. Этих примеров должно быть дос таточно, чтобы показать вам, как разбираться с подобными структурами данных. Вы можете найти больше операций, используя справочную систему Visual Prolog.

implement main

open core, string class predicates

tokenize:(string, string_list) procedure (i, o). clauses

classInfo("main", "string_example").

tokenize(S, [T|Ts]) :

frontToken(S, T, R), !, tokenize(R, Ts). tokenize(_, []).

run(): console::init(),

L= ["it ", "was ", "in ", "the ", "bleak ", "December!"], S= concatList(L), UCase= toUpperCase(S),

RR= string::concat("case: ", Ucase),

R1= string::concat("It is ", "upper ", RR), stdio::write(R1), stdio::nl, tokenize(R1, Us),

1 Автор имеет в виду метод, которым застёгивается та самая застёжка «молния» две гребёнки металлических зубчиков, которые специальным устройством – т. н. «собачкой» соединяются вместе (что и заключает в себе смысл реальной застёжки).

50