16.8. Упражнения

1. Какой тип у карризованной функции min_c?

fun min_c х у = if x < у then x else у

2. Выведите типы sumtree и mintree.

3. Опишите словами определение general_insert_element.

4. Напишите функцию для конкатенации списков, а затем покажите, как ту же самую функцию можно определить с помощью accumulate.

5. Напишите функцию, которая берет список деревьев и возвращает спи­сок минимальных значений в каждом дереве.

6. Выведите типы compare_lists и tree_to_list.

7. Что делает следующая программа? Какой тип у функции?

fun filter f[] = []

| filter f h ::t = h:: (filter f t), if f h = true

| filter f h :: t = filter f t, otherwise

8. Стандартное отклонение последовательности чисел (х\, . .. , х„) опреде­ляется как квадратный корень из среднего значения квадратов чисел ми­нус квадрат среднего значения. Напишите программу на языке ML, ко­торая вычисляет стандартное отклонение списка чисел. Подсказка: ис­пользуйте тар и accumulate.

9. Напишите программу на языке ML для поиска совершенных чисел; п > 2 — совершенное число, если множители я (не включая п) в сумме дают п. Например, 1 +2 + 4 + 7+ 14 = 28.В общих чертах программа будет вы­глядеть как:

fun isperfect n =

let fun addfactors...

in addfactors(n div 2) = n end;

9. Сравните исключения в языке ML с исключениями в языках Ada, C++ и Eiffel.

Глава 17

Логическое программирование

Логическое программирование основано на том наблюдении, что формулы математической логики можно интерпретировать как спецификацию вычис­ления. Стиль программирования при этом становится скорее декларативным, чем процедурным. Мы не выдаем команды, сообщающие компьютеру, что де­лать; вместо этого мы описываем связь между входными и выходными данны­ми и предоставляем компьютеру «догадаться», как получить из входа выход. В пределах, в которых этого удается достичь, логическое программирование обеспечивает значительно более высокий уровень абстракции с соответству­ющим преимуществом чрезвычайной краткости программ.

Есть две основные абстракции, которые характеризуют логическое про­граммирование. Суть первой состоит в том, что от таких управляющих опера­торов, как хорошо известные for и if, мы отказываемся полностью. Вместо них «компилятор» предоставляет чрезвычайно мощный механизм управления, который единообразно применяется ко всей программе. Механизм основан на понятии доказательства в математической логике: программа рассматривает­ся не как пошаговый алгоритм, а как набор логических формул, которые предполагаются истинными (аксиомы), а вычисление — как попытка дока­зать формулу на основе аксиом программы.

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

После того как мы обсудим «чистое» логическое программирование, мы опишем компромиссы, введенные в языке Prolog, первом и все еще очень популярном языке логического программирования, используемом на прак­тике.

В то время как проделать вручную вышеупомянутое вычисление довольно утомительно, для компьютера это всего лишь случай без конца повторяющейся задачи, с которой он превосходно справляется. Для выполнения логической программы набор логических формул (программа) и формула-цель, например:

"wor" =>"Hello world"?

предлагаются программной системе, которая названа машиной вывода, потому что она из одних формул выводит другие, являющиеся их следствием, пока проблема не будет решена. Метод логического вывода проверяет, можно ли доказать целевую формулу, исходя из аксиом, т.е. формул программы, кото­рые приняты за истинные. Ответом может быть и «да», и «нет», что в логиче­ском программировании называется «успехом» или «неуспехом». «Неуспех» мог быть получен из-за того, что цель не следует из программы, например, "wro" не является подстрокой "Hello world", или из-за неправильности про­граммы, например, если мы пропустили одну из формул программы. Возмо­жен и третий вариант, когда поиск машины вывода будет продолжаться без выбора того или иного ответа, и, так же как это может случиться с while-циклом в языке С, никогда не завершится.

Основные понятия логического программирования:

• Программа является декларативной и состоит исключительно из формул математической логики.

• Каждый набор формул для того же самого предиката (такого как «с») ин­терпретируется как процедура (возможно, рекурсивная).

• Конкретное вычисление определяется предложенной целью, т.е. форму­лой, о которой нужно выяснить, является ли она следствием программы.

• Компилятор является машиной вывода, которая по мере возможности ищет доказательство цели из программы.

Таким образом, каждую логическую программу можно прочитать двояко: как набор формул и как спецификацию вычисления. В некотором смысле, ло­гическая программа — это минимальная программа. В разработке программ­ного обеспечения вас обучают точно определять смысл программы перед по­пыткой ее реализовать, и для точной спецификации используется формаль­ная нотация, обычно некоторая форма математической логики. Если специ­фикация является программой, то делать больше нечего, и тысячи програм­мистов можно заменить горсткой логиков. Причина того, что логическое про­граммирование нетривиально, состоит в том, что чистая логика недостаточно эффективна для практического программирования, и поэтому есть этап, ко­торый должен быть пройден от научной теоретической логики до ее инженер­ных приложений в программировании.

В логическом программировании нет никаких «операторов присваива­ния», потому что управляющая структура единообразна для всех программ и состоит из поиска доказательства формулы. Поиск решений проблемы, ко­нечно, не нов; новым является предположение, что поиск решений вычисли­тельных проблем возможен в рамках общей схемы логических доказательств. Логика стала логическим программированием, когда было обнаружено, что, ограничивая структуру формул и способы, которыми делается поиск доказа­тельств, можно сохранить простоту логических утверждений и тем не менее искать решения проблем эффективным способом. Перед объяснением как это делается, мы должны обсудить, как обрабатываются данные в логическом программировании.