![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Любой атом является символическим выражением.Содержание книги
Поиск на нашем сайте
Если А1 и А2 суть символические выражения, то (А1 A2)— это также символические выражения. Если S = (А,. (А2. (.... (Ап-1. AJ....))) — суть символическое выражение для некоторого п>0, то S — список тогда и только тогда, когда Аn =NIL. В соответствии с этим определением, если п=0, то S представляет собой пустой список, NIL. Такое определение допускает существование списка списков, а также списка атомов. Если S1 S2,..., Sn— символические выражения, то мы будем представлять список S1.(S2.(.... (Sn. NIL)....))) В виде (S1 S2.... Sn) Таким образом, (А. (В. NIL)) является списком. Он представляет список (А В), но (А. (В. С)) списком не является, поскольку (С=NIL)). Символическое выражение, которое не является ни атомом, ни списком, называется точечной парой. Если (А. В) — точечная пара, то А — это голова пары, а B — ее хвост. Точечные пары могут иметь произвольную сложность. Так, ((А. В). С) — тоже точечная пара, так же, как и ((А. В). (С. D)). Благодаря наличию соответствия между точечными парами и списками, понятия головы и хвоста определены и для списков. Поскольку список (А В) — это (А. (В. NIL)), то очевидно, что А — голова в списке (А В), а хвост — это (В), но не В. Хвостом списка (В) является NIL Структура LISP-программы Как использовать список в качестве базовой структуры данных, понятно. Сложнее представить себе, как можно организовать программу или выражение программы в виде списка. Например, список (+ X Y) представляет математическое выражение в форме (<функция> <1-й аргумент> <2-й аргумент>), которое обозначает сложение двух чисел. Такой метод обозначений (нотация) отличается от привычного нам обозначения функции п переменных в виде f(x1,... xn). Но возникает вопрос, как компилятор или интерпретатор отличает данные от программы, если и то и другое представлено списками. Необходимо иметь возможность определить значение такого выражения— например, значение выражения (+ X Y). Для этого нужно отыскать определение функции (в данном случае — функции +). В этом определении должна содержаться та последовательность элементарных операций, которую нужно применить к аргументам, чтобы определить значение функции. Нужно иметь средства сформировать определение функции и применить это определение к аргументам, т.е. к действительным, а не формальным параметрам. Механизм определения функции и приложения функции базируется на логической системе, названной лямбда-исчислением (см. [Church, 1941]). Лямбда-исчисление является скорее функциональным, чем исчислением отношений, и в этом состоит различие между ним и исчислением предикатов первого порядка. В функциональном исчислении первичным понятием является отношение "многие-к-одному", а не "многие-ко-многим". Так, отец — это функциональное отношение, а брат — более общее отношение, поскольку каждый человек может иметь только одного отца, а братьев может быть несколько. Ниже в этой главе мы более подробно остановимся на связях между языком LISP и лямбда-исчислением.
Нужно располагать средствами доступа к текущим значениям переменных (или формальных параметров), таких как X и Y. Вычисление каждого символического выражения выполняется в контексте формирования переменных. Нужно располагать средствами сохранения и восстановления этого контекста при вычислении значений сложных символических выражений, т.е. вычисления и комбинирования значений содержащихся в них подвыражений. При вычислении сложных символических выражений, когда необходимо вычислять значения его компонентов, которые являются сложными выражениями, нужно располагать средствами сохранять текущее выражение и промежуточные результаты. Необходимо также обладать средствами копирования символических выражений. Нужно уметь подавлять вычислительную обработку списков, которые не являются операторами программы, а структурами данных. Например, не нужно пытаться вычислять выражение, подобное следующему: ((1 2 3)(4 5 6)(7 8 9)) И пытаться отыскать определение функции (1 2 3). Для этого существует специальная форма выражения (QUOTE X) для любых X, которая возвращает X. Точно такое же действие выполняется и выражением (quote X). Современные версии LISP не чувствительны к регистру символов, хотя и возможно так сконфигурировать исполнительную систему, что она станет по-разному воспринимать символы верхнего и нижнего регистров. Функции, их вычисление и проблема цитирования в CLIPS Существуют два основных метода разрешения проблемы цитирования, т.е. предотвращения интерпретации данных как функций или выражений. Один метод заключается в том, чтобы в число системных функций ввести специальную функцию, которая рассматривается интерпретатором как указание не обрабатывать последующий список. Такой системной функцией в LISP является QUOTE. Другой метод состоит в том, чтобы по умолчанию подавлять механизм оценивания значения (вычисления) до тех пор, пока специальная синтаксическая конструкция его не запустит. В языке CLIPS использован именно такой метод.
Например, в CLIPS можно следующим образом определить функцию: (deffunction between(?lb?value?ub) (or (> lib?value) (>?value?ub)))) Эта функция определяет, попало ли заданное целочисленное значение в диапазон между указанными нижним и верхним пределами. Знак вопроса, предшествующий именам, говорит интерпретатору CLIPS, что выражения?lb,?value и?ub являются переменными и их не нужно оценивать. Общепринятым методом реализации функциональных языков типа LISP является использование четырехстековой машины, за которой закрепилось наименование SECD-машины. В четырех стеках машины отслеживаются промежуточные результаты, значения переменных, текущее выражение и копии текущего состояния процесса вычислений сложного выражения, которые нужны, чтобы восстановить состояние после завершения вычисления вложенного выражения (подвыражения). Не вдаваясь в подробности, отметим, что процесс оценивания символического выражения в такой машине — это не что иное, как реализация базовой операции приложения функции, как это определено в лямбда-исчислении (см., например, [Henderson, 1980], [Glaser et al., 1984]). Приложение функции и лямбда-исчисление Для того чтобы разобраться в связи между лямбда-исчислением и языком LISP, нужно постоянно держать в уме сформулированное Черчем отличие между денотацией (означиванием) и абстракцией. Так, выражение (X X) означивает конкретное число, которое зависит от значения X. Но то же число можно получить и при помощи функции square(X), которая является абстракцией, поскольку ее можно приложить к разным значениям X. Для того чтобы отличить означивание от абстракции, первое представляется в лямбда-исчислении в таком виде: (лх)(X х) Говорят, что лямбда-оператор, X, связан с переменной X, как квантор связывает отдельные переменные в исчислении предикатов. Тогда (ЛХ)(X X) может служить определением функции возведения в квадрат: square(X) = (лX)(X X) Теперь для применения функции возведения в квадрат к конкретному числу, скажем 3, мы должны каким-то образом подставить 3 вместо переменной X и оценить (X,Х), в результате чего получим 9. Когда определение функции применяется к аргументу 3, используется правило влияния, получившее наименование лямбда-преобразования. Доложим, что (лХ)М определяет любую лямбда-абстракцию, и пусть S(a, X, М) — результат подстановки X в М. Лямбда-преобразование. Заменим любую часть (lХ)М в формуле на s(a, x, М), причем ограниченные переменные в м отличны как от х, так и от свободных переменных а. Если мы полагаем, что ((ЛХ)М) а обозначает применение определения функции (ЛХ)М к аргументу а, то ((ЛХ)(Х Х))(3) = (3 3) = 9. Какое же все это имеет отношение к языку LISP? А вот какое. Определение функции возведения в квадрат в LISP выглядит примерно так: (defun SQUARE (X) (LAMBDA (X) (X X))). В различных диалектах языка допустимы вариации, но смысл остается тем же. В частности, в диалекте COMMON LISP используется сокращенная форма
(defun SQUARE (X) (X X)). В любом случае имя функции, в данном случае SQUARE, ассоциируется в определении с лямбда-выражением. Выражение (LAMBDA (X) (X X)) — это просто синтаксический вариант ((ЛХ) (X X)). Фактически, если определено SQUARE, в любом диалекте LISP имеем (SQUARE 3) = ((LAMBDA (X) (X X)) 3) = ((АХ)(Х Х))(3) = 9.
|
|||||||
Последнее изменение этой страницы: 2016-04-07; просмотров: 258; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.191.154.143 (0.011 с.) |