Упражнения

1. Программа CH07EX12.PRO подобна CH07EX11.PRO, но является более

сложной. Она использует тот же алгоритм для расстановки по алфавиту

любого стандартного в DOS текстового файла. Для одного из текстов

эта программа работала более чем в 5 раз быстрее, чем сортирующаяя

DOS программа SORT.EXE. Очевидно, что сортировка на основе дерева

более эффективна.

Замечание: В этом примере используются некоторые предикаты из систе-

мы файлов Турбо Пролога, чтобы дать Вам попробовать способ передачи

файлов. Чтобы передать со входа или на выход, нужно системе дать ин-

формацию о файле и, затем, использовать openread для чтения из файла

или openwrite для записи и него. Если файлы открыты, то ввод-вывод

между файлом и экраном можно начать применив writedevice, а между

открытым файлом и клавиатурой - readdevice предикаты. Детально эти

предикаты будут рассмотрены ниже, в Главе 12.

Загрузите и выполните программу CH07EX12.PRO. Когда она выведет

"File to read", введите имя существующего текстового файла. Програм-

ма, строка за строкой, расставит его в алфавитном порядке.

/* Программа CH07EX12.PRO */

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Быстрая сортирующая программа на основе дерева. *

* Читает сроки файла, сортирует их в алфавитном порядке и *

* записывает в другой файл *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

domains

treetype = tree(string, treetype, treetype) ; empty

file = infile, outfile * рассматривается в Главе 12

predicates

main

read_input(treetype)

read_input_aux(treetype, treetype)

insert(string, treetype, treetype)

write_output(treetype)

clauses

main:-

clearwindow, * Главная процедура,

* вызываемая предложением

write("Turbo Prolog Treesort"),

write("File to read: "),

readln(In),

openread(infile, In), * открыть заданный файла для

* чтения

write("File to write: "),

readln(Out),

openwrite(outfile, Out), * открыть заданный файл для

* записи

readdevice(infile), * передать все операции чтения

* в открытый файл

read_input(Tree),

writedevice(outfile), * передать все операции записи

* в открытый файл

write_output(Tree),

closefile(infile), * закрыть файл, открытый для

* чтения

closefile(outfile). * закрыть файл, открытый для

* записи

main :-

closefile(outfile), * Управление передается этому

writedevice(screen), * правилу, если в процедуре

write("Unable to perform sopt.\n"), * случаютя ошибки

write("Probable clause: can't open file.\n").

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* read_input(Tree) *

* Читает строки из текущего входного устройства до полу- *

* чения EOF, а затем организует из них бинарное поисковое *

* дерево. *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

read_input(Tree) :-

read_input_aux(empty, Tree).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* read_input_aux(Tree, NewTree) *

* Читает строки, вставляет их в NewTree и вызывает себя *

* рекурсивно до получения EOF. *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

read_input_aux(Tree, NewTree) :-

readln(S),

!,

insert(S, Tree, Tree1),

read_input_aux(Tree1, NewTree).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* Если первое предложение не удовлетворяется, то получен *

* EOF. Таким образом удовлетворяется второе предложение *

* без дальнейших действий *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

read_input_aux(Tree, Tree).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* insert(Element, Tree, NewTree) *

* вставляет элемент в дерево Tree и присваивает это *

* новому дереву NewTree *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

insert(NewItem, empty, tree(NewItem, empty, empty)) :- !.

insert(NewItem, tree(Element, Left, Right),

tree(Element, NewLeft, Right)) :-

NewItem < Element,

!,

insert(NewItem, Left, NewLeft).

insert(NewItem, tree(Element, Left, Right),

tree(Element, Left, NewRight)) :-

insert(NewItem, Right, NewRight).

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

* write_output(Tree) *

* выводит элементы дерева в алфавитном порядке. *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

write_output(empty). / * Ничего не делать */

write_output(tree(Item, Left, Right)) :-

write_output(Left),

write(Item), nl,

write_output(Right).

goal

main.

2. Используйте рекурсивную структуру данных для гипертекста. Гипер-

текст - это структура в которой каждая отдельная запись (статья)

состоит из нескольких строк текста и указателей на несколько других

записей. Каждая отдельная запись может соединяться с любой другой

записью. Например, чтобы можно было получить запись об Аврааме Лин-

кольне, как по указателю "Президент", так и по указателю "Гражданс-

кая война".

Для простоты, примените отдельные записи состоящие из одной строки и

пусть они имеют указатели только на одну другую запись.

Подсказка: Начните с

---------

domains

entrytype = empty() ; entry(string, entry)

Составьте объединенную структуру, в которой большинство записей име-

ют непустой второй аргумент.

3. А теперь, примените описание вашего гипертекста для записи пред-

ложений Пролога, т.е. примените предложения (а так же рекурсивные

структуры данных), которым удовлетворяли бы записи.

Обзор

Вот основные моменты, рассмотренные в этой главе:

1. В Прологе есть два способа повторить выполнение одного и того же

предложения: через поиск с возвратом и через рекурсию. В случае не-

успеха Пролог возвращается для поиска новой порции данных и повторя-

ет предложение до тех пор, пока они не закончатся. Рекурсия - это

процесс, когда предложение вызывает само себя.

2. Поиск с возвратом - это мощное и эффективное средство с точки

зрения памяти, но переменные обновляются после каждой итерации, поэ-

тому, их значения теряются. Рекурсия позволяет увеличить количество

переменных, но это не эффективно с точки зрения памяти.

3. С другой стороны, Турбо Пролог может выполнять хвостовые рекур-

сивные исключения, что снимает требования рекурсии по памяти. Чтобы

достичь в Турбо Прологе хвостового рекурсивного исключения, необхо-

димо, чтобы рекурсивный вызов был последним в разделе предложений,

вызываемых подцелью.