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

    Имеющиеся средства и системы программирования не навязывают и не поддерживают, какую либо специфическую методику разработки программ. Однако, как и в других символьных языках программирования, наиболее естественной стратегией разработки программ является стратегия быстрой смены прототипов. При такой стратегии на каждой стадии разработки имеется лучше работающий прототип программы. Разработка происходит путём переделки или расширения прототипа. Другой подход к разработке программ, иногда комбинируемый с первым, состоит в “нисходящем анализе и восходящей реализации”. Хотя проектирование системы следует проводить нисходящим способом, основываясь на  анализе цели, реализацию системы лучше всего строить “снизу вверх”. В процессе восходящего программирования каждый написанный фрагмент программы может быть немедленно отлажен. Глобальные проектные решения, такие, как представление, могут быть проверены на небольших сегментах системы, которые будут приведены  в порядок и очищены от ошибок на начальной стадии программирования. Кроме того, эксперименты с одной подсистемой могут привести к изменению проектных решений, относящихся к другим подсистемам.

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

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

1.5. Другие языки логического  программирования.

 

    Пролог  не единственный язык логического программирования. Кроме него существует ряд других языков, не получивших такого широкого признания в кругах программистов. Рассмотрим два таких языка.

1.5.1 Язык логического  программирования KL0.

 

    KL0 (от англ. “kernel-language version 0” – ядро-язык версии 0) – язык, в основу которого положено расширение языка логического программирования Пролог. Среди особенностей, новых в KL0 по отношению к Прологу, можно выделить:

• более гибкую структуру управления.
• многопроцессовость
• операции с побочным эффектом
• машинно-ориентированные операции.

    К наиболее существенным механизмам Пролога, не поддерживаемым в KL0, относятся:

• средства управления базой данных
• средства управления таблицей имён.

    Так как KL0 мало, чем отличается от Пролога, ограничимся лишь рассмотрением типов данных.

1.5.2 Типы данных KL0.

 

    Рассмотрим  в общих чертах некоторые базовые  типы данных языка. К ним относятся  символы, целые и действительные числа, строки и др.

    Символы в основном предназначены для  представления символьных атомов Пролога  и, как правило, никак не связаны  ни со строками символов, используемыми  для текстуального представления  программ, ни с определениями предикатов, в которых символы задают имена предикатов. Такие атрибуты при необходимости могут быть приписаны символам средствами ESP¹ . KL0 более прост и не поддерживает подобных механизмов. В этом отношении он только обеспечивает структуры данных прямого доступа и стандартную функцию хеширования для доступа к определениям атрибутов в хеш-таблице. Символы в KL0 можно проверять только на идентичность.

    Целые и действительные числа введены  для эффективного выполнения арифметических операций. Арифметические операции в  KL0 не обладают свойством двойственности: сложение и вычитание, здесь различные предикаты. Аппаратно поддерживаются только числа фиксированной длины, определяемой разрядной сеткой. Целые числа произвольной длины (bignums), действительные числа произвольной точности и, возможно, рациональные числа могут быть реализованы с помощью обработчика исключений. Исключение возбуждается, если операндами встроенных арифметических предикатов (машинных инструкций в традиционном смысле) являются, например, нечисловые данные. Обработчик исключения может проверить аргументы и, если они соответствуют ожидаемым, выполнить предписанные операции; в противном случае вызывается обработчик ошибок. После обработки исключения дальнейшее выполнение программы может быть возобновлено.

    Строки  представляются одномерными массивами небольших положительных целых. Размер элементов массива зависит от диапазона значений элементов строки и может изменяться от одной строки к другой. Для представления битовых массивов, используемых для хранения образов графических изображений в памяти, введены строки с однобитовыми элементами. Для представления символов в коде ASCII используются строки с размером элемента 8 бит.

1.5.3. Язык программирования ShapeUp.

 

    ShapeUp - ещё один язык логического программирования, в основу которого положен Пролог, расширенный средствами сопоставления строк.

    В ShapeUp образцы строк рассматриваются так же, как и термы Пролога, и их сопоставление возложено на процесс унификацию. Таким образом, программы на ShapeUp значительно проще, чем аналогичные программы на Прологе, их легче писать и понимать. Сокращается значительно и размер программ.

    Прологу присущи недетерминированность  и сопоставление с образцом. Эти  свойства очень полезны для разработки систем обработки информационных знаний. К таким системам можно отнести системы понимания естественного языка и другие системы интеллектуальной обработки текстов. Для подобных приложений очень важна операция сопоставления строк. Однако механизм сопоставления с образцом в таком виде, как он существует в Прологе, недостаточен для сопоставления строк. Причина заключена в “терм-терм” механизме сопоставления. ShapeUp – попытка разработать более практический, свободный от присущего Прологу недостатка инструмент программирования. Характерной чертой ShapeUp, отличающей его от традиционных Пролог-систем, является выполняемая при унификации функция сопоставления строк. В ShapeUp включено несколько операторов сопоставления строк. Язык позволяет конструировать образцы строк, представляемые как термы Пролога. Образцы могут унифицироваться  с различными строковыми объектами: расширена унификация для выполнения сопоставления строк. В результате ShapeUp-программы проще и имеют более прозрачную семантику, их легче писать.

    Список  языков логического программирования можно продолжать ещё долго. Кроме перечисленных выше, к языкам логического программирования относятся также: Дейталог, LogLisp и множество других. Но хотелось бы ещё остановиться на таком языке, как Лисп (от англ. Lisp – list processing – обработка списков).

Глава 2. Lisp – язык функционального программирования.

 

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

2.1. Лисп в истории программирования.

 

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

    Лисп, ни в каком смысле не является младенцем в программировании. Скорее, он старик среди языков программирования. Лисп был разработан в 50-х годах и является вслед за Фортраном старейшим ещё используемым языком программирования. Но в отличие, от Фортрана будущее Лиспа ещё впереди.

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

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

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

 

    Лисповские  функции, как и написанные на традиционных языках программы, обрабатывают данные в порядке, задаваемом описанием  алгоритма, несмотря на то, что эту  последовательность можно в Лиспе  отобразить весьма гибкими и общими формами. Такие языки назовём процедурными.

    В процедурных языках и формализмах  программирование сводиться к разработке алгоритма, выполняющего действия. В  логических языках алгоритмы в таком  смысле не используются. Если функциональные и операторные языки описывают, каким образом решается некоторая задача, то в логических языках для её решения достаточно точного логического описания. Языки, в которых решение задачи получают из описания структуры и условий задачи, называют декларативными.

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

    При необходимости добиться от Лиспа  возможности логического программирования необходимо запрограммировать алгоритм доказательства.

    Построим  такой алгоритм доказательства. Для  этого доказываемый в настоящий  момент предикат-теорему назовём  целью. Цель можно доказать следующим  алгоритмом:

1. Найти для доказательства цели первое предложение, значение которого унифицируется с целью.
2. Если предложение с таким заключением не найдено, то доказательство не удалось. Если предложение найдено и его тело пусто, то цель доказана. Если у предложения не пустое тело, то надо доказать его предикаты в качестве новых целей рекурсивно слева направо.
3. Если алгоритм зашёл в тупик, т.е. доказательство не удалось, то надо вернуться (backtrack) в предыдущее место, где можно выбрать другую цель (если такая имеется) и продолжить доказательство.

    Подбор  связей переменных основан на методе проб и ошибок и на поиске. Доказываемый в настоящий момент предикат пытаются унифицировать первым возможным способом. Если решение окажется неверным, т.е. некоторый предикат позже не удастся унифицировать, то происходит возврат к предыдущей унификации, выбирается следующая из ещё имеющихся возможностей, и делается попытка унифицировать оставшиеся предикаты другим способом.

    Реализовав  описанный алгоритм на Лиспе можно  добиться возможности логического  программирования на этом языке.