WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |

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

Особый интерес представляет тип констант, которые всегда означают себя – Nil и T, примеры таких констант. Такие константы как T, Nil и другие самоопределимые константы (числа, строки) не могут использоваться в качестве переменных. Числа и строки не имеют списка свойств.

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

На практике связывание в ассоциативном списке для функций используется редко. Удобнее связывать название с определением другим способом - размещением определения функции в списке свойств атома, символизирующего ее название. Выполняет это псевдо-функция DEFUN, описанная в начале этого параграфа. Когда APPLY интерпретирует функцию, представленную атомом, она исследует р-список до исследования текущего состояния асписка.

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

Некоторые функции вместо определений с помощью S-выражений закодированы как замкнутые машинные подпрограммы. Такая функция будет иметь особый индикатор в списке свойств с указателем, который позволяет интерпретатору связаться с подпрограммой.

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

1) Подпрограмма закодирована внутри Лисп-системы.

2) Функция кодируется пользователем вручную на языке типа ассемблера.

3) Функция сначала определяется с помощью S-выражения, затем транслируется компилятором. Компилированные функции могут выполняться гораздо быстрее, чем интерпретироваться.

Обычно EVAL вычисляет аргументы функций до применения к ним функций с помощью APPLY. Таким образом, если EVAL задано (CONS X Y), то сначала вычисляются X и Y, а потом работает CONS над полученными значениями. Но если EVAL задано (QOUTE X), то X не будет вычисляться. QUOTE - специальная форма, которая препятствует вычислению своих аргументов.

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

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

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

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

Специальная функция FUNCTION обеспечивает доступ к функциональному объекту, а функция FUNCALL обеспечивает применение функции к произвольному числу ее аргументов.

(funcall f a1 a2... ) = (apply f (list a1 a2...)) Разрастание числа функций, манипулирующих функциями, связано с реализационным различием структурного представления данных и представляемых ими функций.

Программы для Лисп-интерпретатора.

Цель этой части - помочь на первых шагах избежать некоторых общих ошибок.

Пример 1.

(CAR '(A B)) = (CAR (QUOTE(A B))) Функция: CAR Аргументы: ((A B)) Значение есть A. Заметим, что интерпретатор ожидает список аргументов. Единственным аргументом для CAR является (A B). Добавочная пара скобок возникает т.к. APPLY подается список аргументов.

Можно написать (LAMBDA(X)(CAR X)) вместо просто CAR. Это корректно, но не является необходимым.

Пример 2.

(CONS 'A '(B. C)) Функция: CONS Аргументы: (A (B. C)) Результат (A. (B. C)) программа печати выведет как (A B. C) Пример 3.

(CONS '(CAR (QUOTE (A. B))) '(CDR (QUOTE (C. D))) ) Функция: CONS Аргументы:

((CAR (QUOTE (A. B))) (CDR (QUOTE (C. D)))) Значением такого вычисления будет ((CAR (QUOTE (A. B))). (CDR (QUOTE (C. D)))) Скорее всего это отнюдь не то, что ожидал новичок. Он рассчитывал вместо (CAR (QUOTE (A. B)) получить A и ожидал (A. D) в качестве итогового значения CONS. Кроме очевидного стирания апострофов:

(CONS (CAR (QUOTE (A. B))) (CDR (QUOTE (C. D))) ) ниже приведены еще три правильных способа записи нужной формы. Первый состоит в том, что CAR и CDR части функции задаются с помощью LAMBDA в определении функции. Второй - в переносе CONS в аргументы и вычислении их с помощью EVAL при пустом а-списке. Третий - в принудительном выполнении константных действий в представлении аргументов, ((LAMBDA (X Y) (CONS (CAR X) (CDR Y))) '(A. B) '(C. D)) Функция:

(LAMBDA (X Y) (CONS (CAR X) (CDR Y))) Аргументы:

((A. B)(C. D)) (EVAL '(CONS (CAR (QUOTE (A. B))) (CDR (QUOTE (C. D)))) Nil) Функция: EVAL Аргументы:

((CONS (CAR (QUOTE (A. B))) (CDR (QUOTE (C. D)))) Nil) Значением того и другого является (A. D) ((LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) '(CAR (QUOTE (A. B))) '(CDR (QUOTE (C. D))) ) Функция:



(LAMBDA (X Y) (CONS (EVAL X) (EVAL Y))) Аргументы:

((CAR (QUOTE (A. B))) (CDR (QUOTE (C. D)))) Решения этого примера показывают, что грань между функциями и данными достаточно условна - одни и те же вычисления можно осуществить при разном распределении промежуточных вычислений внутри выражения, передвигая эту грань.

Выводы:

- Чтобы выполнить вычисление на реальном Лисп-интерпретаторе необходимо уточнить ряд правил по оформлению текста Лисп-программы.

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

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

- Некоторые функции системы необходимо реализовывать в виде машинных подпрограмм.

Они образуют ядро системы.

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

8. Управление процессами Теперь рассмотрим более тонкие методы повышения эффективности и результативности вычислений:

• замедленные вычисления • рецепты вычисления Замедленные вычисления (lazy evaluation) Интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам, не всегда гарантирует получение результата. Ради полноты вычислений, гибкости программ и результативности процессов такое представление можно расширить и ввести категорию специальных функций, которые "сами знают", когда и что из их аргументов следует вычислить. Примеры таких функций - специальные функции QUOTE и COND, которые могут анализировать и варьировать условия, при которых вычисление необходимо. Такие функции манипулируют данными, представляющими выражения, и явно определяют в программах позиции обращения к интерпретатору.

Источником неэффективности стандартных “прямолинейных” вычислений может быть целостность больших сложных данных, избыточное вычисление бесполезных выражений, синхронизация формально независимых действий. Такую неэффективность можно смягчить простыми методами замедленных вычислений (lazy evaluation). Необходимо лишь вести учет дополнительных условий для их фактического выполнения, таких как востребованность результата вычислений. Такие соображения по обработке параметров функций называют “вызов по необходимости”.

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

Пример: Построение ряда целых от M до N с последующим их суммированием. Обычная формула:

(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) ) Введем специальные операции || - приостановка вычислений и @ - возобновление ранее отложенных вычислений. Приостановка сводится к запоминанию символьного представления программы, которая временно не вычисляется, но можно вернуться к ее вычислению с помощью операции возобновления. Отложенная программа преобразуется в так называемый рецепт вычисления, который можно хранить как данное и выполнять в любой момент.

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

Избежать целостного представления большого и возможно бесконечного ряда чисел можно небольшим изменением формулы, отложив вычисление второго аргумента CONS “до лучших времен” – когда его значение действительно понадобится более внешней функции:

(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M ( || (ряд_цел (1+ M) N)))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( @ ( сумма (cdr X))))) )) Можно исключить повторное вычисление совпадающих рецептов. Для этого во внутренне представление рецепта вводится флаг, имеющий значение T - истина для уже выполненных рецептов, Nil - ложь для невыполненных.

Таким образом рецепт имеет вид (Nil e AL ) или ( T X ), где X = (eval e AL ) для произвольного e, в зависимости от того, понадобилось ли уже значение рецепта или еще не было в нем необходимости.

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

(defun цел (M) (cons M ( || (цел (1+ M) )))) Можно из таким образом организованного списка выбирать нужное количество элементов, например, первые K элементов можно получить по формуле:

(defun первые (K Int) (cond ((= Int Nil) Nil) ((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) )) Формально эффект таких приостанавливаемых и возобновляемых вычислений получается следующей реализацией операций || и @:

||e = > (lambda () e ) @e = > (e ), что при интерпретации дает связывание функционального аргумента с ассоциативным списком для операции || - приостановка и вызов функции EVAL для операции @ - возобновление вычислений.





Обычно в языках программирования различают вызовы по значению, по имени, по ссылке.

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

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

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

Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизации кода программ (умножение на 0, разность или частное от деления совпадающих форм и т.п.) Отложенные действия - естественный механизм программирования асинхронных и параллельных процессов.

Выводы:

- Замедленные вычисления могут быть результативнее обычных.

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

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

9.Традиционное (стандартное) программирование - Императивное программирование - Списки свойств атома - Структуры данных и памяти - Деструктивные операции - Свободная память и мусорщик Форма “Prog” и циклы Противопоставление функционального и императивного (операторно-процедурного) стилей программирования порой напоминает свифтовские бои остроконечников с тупоконечниками. Впрочем, переписать функциональную программу в императивную проще, чем наоборот.

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

Рассмотрим предложенный МакКарти пример, показывающий возможности prog-формы при императивном стиле определения функции Length. Эта функция сканирует список и вычисляет число элементов на верхнем уровне списка. Значение функции Length - целое число. Алгоритм можно описать следующими словами:

"Это функция одного аргумента L.

Она реализуется программой с двумя рабочими переменными z и v.

Записать число 0 в v.

Записать аргумент L в z.

A: Если z содержит NIL, то программа выполнена и значением является то, что сейчас записано в v.

Записать в z cdr от того, что сейчас в z.

Записать в v на единицу больше того, что сейчас записано в v.

Перейти к A" Эту программу можно записать в виде Паскаль-программы с несколькими подходящими типами данных и функциями. Строкам вышеописанной программы соответствуют строки определения функции LENGTH, в предположении, что существует библиотека Лиспфункций на Паскале:

function LENGTH (L: list) : integer;

var Z: list;

V: integer;

begin V := 0;

Z := l;

A: if null (Z) then LENGTH := V;

Z := cdr (Z);

V := V+1;

goto A;

end;

Переписывая в виде С-выражения, получаем программу:

(defun LENGTH (lambda (L) (prog (Z V) (setq V 0) (setq Z L) A (cond ((null Z)(return V))) (setq Z (cdr Z)) (setq V (+ 1 V)) (go A) ))) )) ;;=======================ТЕСТЫ============= (LENGTH '(A B C D)) (LENGTH ‘((X. Y) A CAR (N B) (X Y Z))) Последние две строки содержат тесты. Их значения 4 и 5 соответственно.

Форма Prog имеет структуру, подобную определениям функций и процедур в Паскале:

(PROG, список рабочих переменных, последовательность операторов и атомов... ) Атом в последовательности выполняет роль метки, локализующей оператор, расположенный вслед за ним. В вышеприведенном примере метка A локализует оператор, начинающийся с "COND".

Первый список после символа PROG называется списком рабочих переменных. При отсутствии таковых должно быть написано NIL или (). С рабочими переменными обращаются примерно как со связанными переменными, но они не могут быть связаны ни с какими значениями через lambda. Значение каждой рабочей переменной есть NIL, до тех пор, пока ей не будет присвоено что-нибудь другое.

Для присваивания переменной применяется форма SET. Чтобы присвоить переменной pi значение 3.14 пишется:

(SET (QUOTE PI)3.14) SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому (SETQ PI 3.14) запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменять значения любых переменных из ассоциативного списка более внешних функций.

Значением SET и SETQ является значение их второго аргумента.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.