Рекурсивные функции и структуры данных

Система программирования может быть задана как правило интерпретации или компиляции программ.

Определение 1.6

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

Определение 1.7

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

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

Определение 1.8

Определение 1.9

Типы данных в Лиспе включены в представление значений. Поэтому при вычислении они всегда известны и могут быть проверены в любой момент.

Определение 1.10

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

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

Термины "Ассоциативный список", "Атом", "Сборка мусора", "Свойства атома", "Список", "Символьные выражения", "S-выражения", "Форма", "Функциональное программирование" еще будут пояснены по ходу курса.

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

{1 –1 =  0 ;  ( n +1 )  -1 = n  } ,

не поддавшейся А.Чёрчу и решенной С.Клини лишь в 1932 году:

Пример 1.1Запись с помощью алгоритмической нотации школьного курса информатики

{ F (x, y, z) = если (x = 1) то 0 иначе 
                       если  ((y +1) = x) то z  иначе F (x, y +1, z +1) ;
n –1  = F (n, 0, 0) }

алг F ( цел  x, y, z) арг x, y, z 
       нач 
            если  (x = 1)
                 то знач := 0
                 инес (y +1) /= x
           то знач := F (x, y +1, z +1)
       кон

алг N-1 (цел N) арг N нач  знач := F (N, 0, 0)  кон

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

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

Лисп появился как язык символьной обработки информации. К середине семидесятых годов на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, экспериментального программирования, лингвистики, химии, биологии, медицины и инженерного проектирования. На Лиспе реализована система AutoCAD - автоматизация инженерных расчетов, дизайна и комплектации изделий из доступных элементов, и Emacs – весьма популярный текстовый редактор в мире UNIX/Linux.

Приверженцы Лиспа ценят его за элегантность, гибкость, а, главное, за способность к точному представлению программистских идей и удобство отладки. Методы программирования на Лиспе потребовали от авторов Лиспа большого числа нетрадиционных решений и соглашений, основа которых предложена и опробована Дж. Мак-Карти с его коллегами и учениками в определении этого языка (Lisp - list processing) и в первых реализациях Lisp 1.0 и Lisp 1.5. Наиболее общие из них признаны как принципы функционального программирования:

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

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

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

Наследие Лиспа в информатике достойно отдельного изложения. Существуют и активно применяются более трехсот диалектов Лиспа и родственных ему языков (Interlisp, muLisp, Clisp, Scheme, Ml, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и т.д.) По современным меркам реализации Лиспа компактны и непритязательны к оборудованию. Существуют свободно распространяемые версии, занимающие менее Мегабайта, пригодные к применению на любом процессоре.

В этом курсе мы сконцентрируемся на ключевой идее Лиспа - сведении понятия "программа" к взаимодействию разных категорий функций, а также на основах и методах функционального программирования. Подробно познакомимся с базисом Лиспа, проанализируем конструктивность методов программирования на Лиспе, изучим построение Лисп-системы и узнаем ее архитектурные особенности, рассмотрим методы эффективного и прикладного программирования в функциональном стиле. С математическими основами Лиспа можно ознакомиться подробнее на страницах журнала "Компьютерные инструменты в образовании", N 2-5 за 2002 год.

Выводы:

Вопросы: