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

 

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

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

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

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

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

 

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

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

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

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

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

1. Найти для доказательства цели первое предложение, значение которого унифицируется с целью.

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

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

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

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

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

Заключение.

 

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

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

Список литературы

 

1. И. Братко «Программирование на языке Пролог для искусственного интеллекта». М: Мир 1990г.

2. «Язык Пролог в пятом поколении ЭВМ». Сборник статей под редакцией Ильинского. М: Мир 1988г.

3. Клоксин, Меллиш «Программирование на языке Пролог». М: Мир 1987г.

4. Дж. Стобо «Язык программирования Пролог». М: Радио и связь 1993г.

5. Э. Хювёнен, Й. Сеппянен «Мир Лиспа» в 2-х томах. М: Мир 1990г.

6. Хоггер «Введение в логическое программирование». М: Мир 1988г.

7. Л. Стерлинг, Э. Шапиро «Искусство программирования на языке Пролог». М: Мир 1990г.

 

 

[1] ESP – язык логического программирования. К особенностям этого языка, отличающим его от Пролога можно отнести;

· модульность,

· макросредства,

· глобальные данные.