Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ
Посмотреть оригинал

Функциональное и логическое программирование

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

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

Языки функционального программирования.

Среди языков функционального программирования наиболее известен язык Lisp, реализующий «чистую» идею функционального программирования и отличающийся наиболее простым синтаксисом из всех языков функционального программирования [21]. По определению, Lisp является языком обработки списков.

Списки как единственный составной тип данных в Lisp не типизированы и представляются текстуально с помощью .9-выражений, которые являются либо атомами (простейшими последовательностями цифр или символов), либо последовательностью других 5-выражений, разделенных пробелами и заключенных в скобки.

Функции в Lisp строятся из 5-выражений и имеют единообразную префиксную форму записи. Для задания произвольного отображения используются ^-определения функций. Запуск и применение функции осуществляется с помощью X-вызова функции с конкретными значениями аргументов. Вычисление Х-вызова производится как Х-преобразование, в процессе которого сначала вызываются значения фактических параметров, которые связываются с соответствующими формальными параметрами, а затем вычисляется тело Х-выражения, т.е. функция, после чего полученное значение возвращается в качестве значения Х-вызова.

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

_ (DEFUN SUM (LAMBDA (X Y) (+ X Y) ) ) ; определение

; функции SUM с ; X-выражением внутри

SUM ; имя функции

_(SUN '2 '3) ; Х-вызов функции

5 ; результат вычислений

Техника программирования на Lisp основана на композиции Х-вызовов и повторных вычислениях через рекурсии. Разветвление вычислений осуществляется с помощью механизма обработки аргументов условного предложения.

Композиция является основным способом определения функции с помощью других функций при написании функциональной программы. Композиция Х-вызовов позволяет делать вложенные вызовы в сложных функциях.

Например, следующий вызов содержит вложенный Х-вызов (символ ‘ помечает константу):

_( (LAMBDA(Y) (LAMBDA(X) ) (LIST Y X))

' INTERNAL 'EXTERNAL)

(EXTERNAL INTERNAL))

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

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

При построении рекурсий используется механизм условных предложений, который определяет ветвление программы, окончание и продолжение вычислений. Условные предложения могут строиться, например, на функции COND с аргументами в виде последовательности пар «предикат — результат, ему соответствующий».

В качестве примера простой рекурсии определим функцию вычисления суммы чисел от 1 до N:

_(DEFUN SUM_1_N (N) (COND((=N 1) 1)

(Т (SUM (SUM_1_N (-N 1))N N)))

Здесь Tявляется специальным атомом true («истина»).

Условное предложение из тела этой функции содержит две ветви: ветвь с условием окончания и ветвь с рекурсией, с помощью которой находится сумма чисел от 1 до N.

Для работы со списками в Lisp используются примитивные функции: CAR и CDR, выделяющие голову и хвост списка (разбор выражений); CONS, выполняющая композицию списков; АТОМ, проверяющая, является ли аргумент атомом (т.е. неделимым элементом). Последняя функция возвращает Т (true), если аргумент атом, или F(false) — в ином случае. При работе со списком констант, чтобы константа не оказалась именем функции, применимой к списку аргументов, используется функция QUOTE, которая возвращает свой аргумент без изменения, не интерпретируя его как вычислимое выражение.

Следующие примеры показывают использование перечисленных примитивов:

  • (CAR (QUOTE (123))) ; результат 1
  • (CDR (QUOTE (1 2 3))) ; результат (2, 3)
  • (CONS (QUOTE A) (QUOTE (В C))) ; результат (А В C)
  • (ATOM (QUOTE 1)) ; результат T
  • (ATOM (QUOTE (1 2))) ; результат F

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

о.-, (3-, р- и 8-преобразования Я-исчисления. Для интерпретации выражений Lisp-программы используются функции EVAL и APPLY. Функция EVAL вычисляет значение аргумента, преобразуя его к нормальной форме, a APPLY вычисляет значения применения функции с помощью преобразования этого применения к нормальной форме.

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы