Точно Не проект 2 / Не books / Источник_1

ГЛАВА 5

ЯЗЫК ЛИСП

Вэтой и следующей главе рассматриваются две важные парадигмы программирования, используемые при построении СИИ, – функциональное

илогическое программирование. Функциональное программирование реализуется средствами языка Лисп, а логическое – языка Пролог. Важная характеристика этих языков – ориентация не на числовую обработку, а на обработку символов. Поэтому структуры данных, поддерживаемые этими языками, не ограничиваются массивами. Списки – основная структура данных, реализованная как в языке Лисп, так и в языке Пролог.

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

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

5.1.Общая характеристика языка

Язык Лисп был разработан в конце 50-х годов Дж. Маккарти. Название языка Лисп происходит от английских слов LISt Processing – обработка списков. Существовавшие в то время языки программирования были плохо приспособлены для решения задач ИИ, так как предназначались для обработки числовой информации. Цель, поставленная Маккарти, состояла в том, чтобы создать язык, ориентированный, прежде всего, на символьную обработку, а не на числовые вычисления, а также реализовать модель вычислений, основанную на теории рекурсивных функций А. Черча [26].

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

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

Говоря о Лиспе, нельзя не отметить другую его характеристику. Лисп

– это язык функционального программирования. Функции являются основным инструментом для манипуляций со списками. В состав Лиспа входит большое число разнообразных функций обработки списков. Это позволяет относительно легко писать и отлаживать сложные программы.

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

Сразу после появления первой версии языка начались работы по его совершенствованию. В 1961 г. была разработана новая версия языка под названием Lisp 1.5, которая претендовала на роль квазистандарта в период

с1961 по 1965 г. К началу 70-х годов появляются два новых диалекта языка Лисп – MacLisp и InterLisp. В диалекте MacLisp были введены функции

спеременным числом аргументов и возможности работы с макросами. В диалекте InterLisp появились итерационные циклы, которые позже вошли во многие другие диалекты языка. Необходимо отметить, что к этому времени уже существовало значительное число различных диалектов языка Лисп, и встал вопрос о его стандартизации. Первые усилия по стандартизации языка были предприняты в 1965 г., когда на основе Lisp 1.5 был разработан язык Standard Lisp. Это был первый диалект языка Лисп, реализованный на различных программно-аппаратных платформах. Существенное влияние на развитие языка Лисп оказало появление во второй половине 70- х годов диалекта Scheme и технологии объективно-ориентированного программирования в языках Smalltalk и KRL. В диалекте Scheme было расширено понятия области действия переменных и введено понятие лексического замыкания. К началу 80-х годов вновь остро стал вопрос о стандартизации языка. В 1981 г. агентство DARPA при Министерстве обороны США инициировало работы по разработке нового стандарта языка. В ре-

Важное понятие языка Лисп – символы. Символы обозначают объекты, которыми манипулирует программа, и в этом смысле соответствуют именам переменных алгоритмических языков программирования. Однако символы в языке Лисп имеют и другие атрибуты, о которых будет сказано позже. Поэтому не следует их отождествлять с именами переменных алгоритмических языков программирования. Символы образуются из знаков алфавита по правилу:

символ::= буква | символ буква | символ спецзнак | символ цифра | цифра буква | цифра спецзнак | цифра символ | спецзнак символ

Примеры символов: А1, %1А, col13. В Лиспе не различаются прописные и строчные буквы. Поэтому символы, составленные из строчных букв, совпадают с соответствующими символами, составленными из прописных букв. Символы могут иметь значения. Для приписывания символам значений используются специальные формы. Изначально символы значений не имеют.

Наряду с символами, в Лиспе используются и числа. Лисп поддерживает работу с целыми, рациональными и вещественными числами:

число::=целое число | рациональное число | вещественное число

Числа записывают с помощью цифр и букв и, в отличие от символов, обозначают самих себя. Примеры чисел: 537, 2/3, 2.0Е-3.

Символы и числа представляют простейшие объекты языка Лисп, поэтому их называют атомами. Атом определяется с помощью следующей формулы:

атом::=символ | число | ()

Пара скобок ( ) в языке Лисп имеет двойное значение. С одной стороны, она обозначает пустой список, а с другой – логическое значение ложь. Иными словами, в Лиспе ложь представляется пустым списком. Все остальные значения интерпретируется как истина. Для обозначения логического значения истина (true) в Лиспе используется символ Т. Ложь или пустой список также обозначаются символом NIL. Символы Т и NIL имеют фиксированное значение, и их нельзя использовать в качестве имен других лисповских объектов.

Из атомов можно построить основную структуру данных языка Лисп

– s-выражение, которое определяется с помощью следующей рекурсивной формулы:

s-выражение ::= атом | (s-выражение . s-выражение )

Например, s-выражения (A .(B .(C .(D . NIL)))) и ((A . B) . ((C . D) . NIL)) – списки. Элементы первого списка – это атомы A, B, C, D, элементы второго списка – это точечные пары (A . B) и (C . D) (рисунок 5.3).

Рисунок 5.2 – Диаграмма точечной пары ((A . B ) . (C . D))

В Лиспе принято также изображать список в виде последовательности элементов, отделяемых пробелом и заключенных в круглые скобки: (А В С D), ((А . В) . (С . D)). В этом случае список представляет собой упорядоченную последовательность, элементами которой являются как атомы, так и списки. Списки, записанные в такой форме, весьма удобны для представления различных моделей знаний. Вспомните, например, фреймовые модели. Список, заданный в виде последовательности элементов, всегда можно представить в точечной записи. Например, следующие записи эквиваленты:

(А В С D) ↔ (A . (B . (C . (D . NIL))))

а)

б)

Рисунок 5.3 – Диаграммы списков (А. (В . (С . (D . NIL)))) (a) и

((А . В) . ((С . D) . NIL)) (б)

По умолчанию исходные s-выражения вводятся с клавиатуры. На втором шаге выполняется интерпретация s-выражения с помощью функции ЕVAL, которая является вызовом интерпретатора. На третьем шаге функция PRINT осуществляет вывод значения s-выражения. По умолчанию вычисленные значения выводятся на дисплей. Затем цикл READ-EVAL- PRINT повторяется для другого s-выражения и т.д.

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

(fn a1 a2 … an),

где fn – имя вызываемой функции; а1, а2 … аn – аргументы функции, которые задаются вычисляемыми s- выражениями.

Например, если требуется вычислить сумму чисел 5 и 3, то с клавиатуры вводится следующее s-выражение (+ 5 3). Результат интерпретации показан на рисунке 5.5. Здесь знак “+” соответствует имени функции, выполняющей сложение.

Рисунок 5.5 – Пример интерпретации

В общем случае формы могут быть заданы константами, перемен-

ными, списками. Константы соответствуют самоопределяемым формам,

которые представляют самих себя и имеют фиксированные значения (числа, символы T и NIL, строки и др.). Переменные в Лиспе обозначаются символами. При вычислении такой формы возвращается значение символа. Форма, заданная в виде списочной структуры, может представлять: вызов функции, рассмотренный выше, вызовы специальных форм, макровызовы. Специальные формы позволяют выполнять действия, недостижимые с помощью обычных функций, например, присваивать значения переменным, осуществлять условные вычисления. К таким формам относят: SETQ, QUOTE, IF и др. Макровызовы внешне соответствуют вызову функции, но отличаются по способу вычисления. Они вычисляются в два этапа: сначала из аргументов макроса строится форма, а затем она вычисляется. Подробнее макросы будут рассмотрены позже.

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

Для сравнения скалярных чисел в Лиспе используются функции, имена которых задаются знаками отношений ( =, | = (не равно), <, >, <=, >= ). Эти функции могут иметь произвольное количество аргументов. В этом случае проверяется выполнение соответствующего отношения для всех аргументов. Если отношение выполняется, то функция возвращает в качестве результата значение Т, иначе – NIL. Например,

(> 5 4 3 2 1) Т

В Лиспе имеется большой набор иррациональных и трансцендентных функций: EXP, EXPT, LOG, SQRT, SIN, COS, TAN, ASIN, ACOS, ATAN

и др. Аргументы тригонометрических функций задаются в радианах. Ниже приведены примеры вызовов некоторых из указанных функций:

Функции TRUNCATE, ROUND, FLOAT выполняют преобразование чисел из одного формата в другой. Функция TRUNCATE возвращает два значения – целую и дробную часть числа:

(truncate - 1.7) - 1 - 0.7

Функция ROUND выполняет округление числа и также возвращает в качестве результата два значения – ближайшее целое и разность между исходным значением и найденным ближайшим целым:

(round 5.7) 6 - 0.3

Функция FLOAT преобразует целое число в число с плавающей точ-

кой.