WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 6 | 7 || 9 |

GO-форма, используемая для указания перехода (GO A) указывает, что программа продолжается оператором, помеченным атомом A, причем это A может быть и из более внешнего prog.

Условные выражения в качестве операторов программы обладают полезными особенностями. Если ни один из предикатов не истинен, то программа продолжается оператором, следующим за условным выражением.

RETURN - нормальное завершение программы. Аргумент return вычисляется, что и является значением программы. Никакие последующие операторы не вычисляются.

Если программа прошла все свои операторы, не встретив Return, она завершается со значением NIL.

Prog-форма может быть рекурсивной.

Пример: Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивной Prog-формы.

Лисп Паскаль (DEFUN rev (x) function rev (x: list) :List (prog (y z) var y, z: list;

begin A (COND ((null x)(return y))) A: if null (x) Then rev := y;

(setq z (CDR x)) z := cdr (x);

(COND ((ATOM z)(goto B))) if atom (z) then goto B;

(setq z (rev z)) z := rev (z);

B (setq y (CONS z y)) B: y := cons (z, y);

(setq x (CDR x)) x := cdr (x);

(goto A) goto A )) end;

Функция rev обращает все уровни списка, так что rev от (A ((B C) D)) даст ((D (C B))A).

Для того, чтобы форма prog была полностью законна, необходима возможность дополнять ассоциативный список рабочими переменными. Кроме того операторы этой формы требуют специального расширения языка - в него включаются формы go, set и return, не известные вне prog. (Формы Go, Set, Return возникли как операторы лишь на верхнем уровне PROG или внутри COND, находящегося на верхнем уровне PROG. Но в современных версиях Лиспа их можно встретить и в других позициях.) Атомы, выполняющие роль меток, работают как указатели помеченного блока.

Кроме того произошло уточнение механизма условных выражений, - отсутствие истинного предиката не препятствует формированию значения cond-оператора, т.к. все операторы игнорируют выработанное значение. Это позволяет считать, что значением является Nil.

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

В принципе SET и SETQ могут быть реализованы с помощью a-списка примерно также как и доступ к значению аргумента, только с копированием связей, расположенных ранее изменяемой переменной (см. функцию assign из параграфа 4). Более эффективная реализация, на основе списков свойств, будет описана ниже.

(DEFUN set (x y) (assign x y Alist)) Обратите внимание, что введенное таким образом присваивание работает разнообразнее, чем традиционное присваивание: допущена вычисляемость левой части присваивания, т.е.

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

Пример:

(setq x 'y) (set x 'NEW) (print x) (print y) Напечатается Y и NEW.

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

Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры.

Согласно стандарту Common Lisp глобальные значения переменных и определения функций хранятся в фиксированных полях структуры атома. Они доступны с помощью специальных функций symbol-function и symbol-value соответственно. Список произвольных свойств можно получить функцией symbol-plist. Функция remprop в Clisp удаляет лишь первое вхождение заданного свойства. Новое свойство можно ввести формой вида:

(setf (get Индикатор ) Свойство) Числа представляются в Лиспе как специальный тип атома. Атом такого типа состоит из указателя с тэгом, специфицирующим слово как число, тип числа (целые, дробные, вещественные), и адрес собственно числа, код которого может быть произвольной длины. В отличие от обычного атома одинаковые числа не совмещаются при хранении Структура списков и памяти До этого момента списки рассматривались на уровне текстового ввода-вывода. В настоящем разделе рассматривается кодовое представление списков внутри машины и механизм сборки мусора, обеспечивающий повторное использование памяти.

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

Теперь можно дать правило представления С-выражений в машине. Представление атомов будет пояснено ниже.



Преимущества структур списков для хранения С-выражений в памяти:

1) Размер и даже число выражений, с которыми программа будет иметь дело, можно не предсказывать. Кроме того, трудно организовать для размещения выражений блоки памяти фиксированной длины.

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

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

Для примера рассмотрим типичную двухуровневую структуру (A (B C)).

Она может быть построена из A, B и C с помощью (cons ‘A (cons (cons ‘B (cons ‘C NIL)) NIL)) или, используя функцию list, можно то же самое записать как (list ‘A (list ‘B ‘C)) Если дан список x из трех атомов x = (A B C), то аргументы A, B и C, используемые в предыдущем построении, можно найти как A = (car x) B = (cadr x) C = (caddr x) Исходную структуру из такого списка можно получить функцией grp, строящей (X (Y Z)) из списка вида (X Y Z).

(grp x) = (list (car x) (list (cadr x) (caddr x))) Здесь grp применяется к списку X в предположении, что он заданного вида.

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

В частности, элементарный Лисп не имеет возможности модифицировать структуру списка.

Единственная базисная функция, влияющая на структуру списка - это cons, а она не изменяет существующие списки, а создает все новые и новые. Функции, описанные в чистом Лиспе, такие как subst, в действительности не модифицируют свои аргументы, но делают модифицированную копию оригинала.

Элементарный Лисп работает как расширяемая система, в которой информация как бы никогда не пропадает. Set внутри Prog лишь формально смягчает это свойство, сохраняя ассоциативный список и моделируя присваивания теми же CONS.

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

(rplaca x y) заменяет адресную часть x на y. Ее значение - x, но x, отличное от того, что было раньше. На языке значений rplaca можно описать равенством (rplaca x y) = (cons y (cdr x)) Но действие совершенно различно: никакие cons не вызываются и новые слова не создаются.

(rplacd x y) заменяет декремент x на y.

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

Такие функции используются при реализации списков свойств атома и ряда эффективных, но небезопасных, функций Clisp-а, таких как nconc, mapc и т.п.

Для примера вернемся к функции grp. Это преобразующая список функция, которая преобразует копию своего аргумента, реорганизуя подструктуру A B C в структуру из тех же атомов:

A B C Вышеприведнное определение функции делает это созданием новой структуры и использует для этого четыре cons. Из-за того, что в оригинале только три слова, по крайней мере один cons необходим, а grp можно переписать с помощью rplaca и rplacd.

Изменение состоит в следующем:

A B C B Пусть новое машинное слово строится как (cons (cadr x) (cddr x)). Тогда указатель на него заготавливает форма:

(rplaca (cdr x) (cons (cadr x) (cddr x))) Другое изменение состоит из удаления указателя из второго слова на третье. Оно делается как (rplaca (cdr x) NIL).

Новое опреление функции pgrp можно определить как соотношение:

(pgrp x) = (rplacd (rplaca (cdr x) (cons (cadr x) (cddr )x))) NIL) Функция pgrp используется в сущности ради ее действия. Ее значением, неиспользуемым, является подструктура ((B C)). Поэтому необходимо, чтобы pgrp выполнялось, а ее значение игнорировалось.

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

Выводы:

- При реализации языка программирования происходит его расширение с целью - повышения практичности программирования.

- Стандартные, операторно-процедурные построения моделируются с помощью функций.

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

- Деструктивные операции могут дать большую эффективность вычислений ценой надежности программирования.

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

10. Парадигмы программирования Средства и методы программирования на Лиспе образуют два слоя. Глубинный слой - локальное программирование, нацеленное на определение:





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

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

- прототипы и макеты программ, - интеграция разных стилей и методов программирования, - экспериментальное программирование, - проверка новых идей и подходов к организации информационных систем.

Стиль разработки программ на Лиспе, получивший название "функциональное программирование" (ФП), воспринят многими языками программирования с общей логикой уточнения решаемых задач и обобщения решений на основе выбранных специально базовых конструкций:

1) Базовые конструкции определяются как строгие функции.

2) При необходимости выполняются преобразования программ, (компиляция, оптимизация и т.п.) для улучшения эксплуатационных характеристик, связанных с процессами исполнения программ.

3) Важный критерий качества ФП - полнота системы функций и универсальность определений для синтаксически управляемой обработки данных функциями высоких порядков (компилятор и т.п.), что существенно повышает надежность программирования.

4) Разработка ИС средствами ФП успешно выполняет роль прототипа для реализации другими, более привычными, средствами.

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

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

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

3) Изучено расширение функционального языка, достаточное для стандартного программирования, естественного для привычных задач.

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

Понятийно-функциональный потенциал языка Lisp 1.5 в значительной мере унаследован стандартом Common Lisp, но не все идеи получили достойное развитие. Возможно это дело будущего - для нового поколения системных программистов, но это уже другая история.

По мере накопления опыта реализации Лиспа и других языков сформированы обширные библиотеки функций, весьма эффективно поддерживающих обработку основных структур данных - списков, векторов, множеств, хэш-таблиц, а также строк, файлов, директорий, гипертекстов, изображений. Существенно повысилась результативность системных решений в области работы с памятью, компиляцией, манипулирования пакетами функций и классами объектов. Все это доступно в современных системах, таких как GNU Clisp, Python, CMUCL и др., основная проблема при изучении которых – слишком много всего, разбегаются глаза, трудно выбрать первоочередное. Все это превращает любой диалект Лиспа в практичный инструментарий, обладающий интересными перспективами.

Результативность идей Лиспа подтверждена самой историей развития его диалектов и родственных ему языков программирования. (Pure Lisp, Lisp 1.5, Lisp 2, Interlisp, CommonLisp, MicroLisp, MuLisp, Sail, Hope, Miranda, Scheem, ML, GNU Clisp, CLOS, Emacs, Elisp, xLisp, Vlisp, AutoLisp, Haskell, Python, CMUCL). Стандарт Common Lisp в сравнении с Лиспом от МакКарти имеет ряд отличий, несколько влияющих на программотехнику. GNU Clisp, xLisp, CMUCL соответствуют стандарту Common Lisp.

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

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

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

Базис Лиспа идеально лаконичен - атомы и простые структуры данных –девять функций и функционалов - обычные функции, которые анализируют, строят и разбирают любые структурные значения (atom, eq, cons, car, cdr,), и специальные функционалы, которые управляют обработкой структур, представляющих вычисляемые выражения (quote, cond, lambda, eval).

Pages:     | 1 |   ...   | 6 | 7 || 9 |










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

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