1. Функциональное программирование. Основы Лиспа
| Вид материала | Документы |
- Рабочая программа по курсу "Функциональное программирование" Специальность, 144.38kb.
- Федеральное агентство по образованию, 124.95kb.
- В. А. Давыденко программирование и основы алгоритмизации лабораторный практикум, 1951.1kb.
- Петербургский Гуманитарный Университет Профсоюзов (СПбгуп), с-петербург учебный курс, 20.72kb.
- Программа дисциплины Математическое программирование Семестры, 10.84kb.
- Методические указания и задания к курсовому проекту по дисциплине «Функциональное, 73.42kb.
- Программа дисциплины Функциональное программирование и интеллектуальные системы для, 148.26kb.
- Методические рекомендации для студентов по изучению курса «Функциональное программирование», 49.76kb.
- Рабочая программа по дисциплине "Функциональное и логическое программирование, 152.21kb.
- Программа элективного курса «Алгоритмизация и программирование», 95.38kb.
Общее представление о языке Лисп
Лисп появился как язык символьной обработки информации. К середине семидесятых годов на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, экспериментального программирования, лингвистики, химии, биологии, медицины и инженерного проектирования. На Лиспе реализована система 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 и т.д.) По современным меркам реализации Лиспа компактны и непритязательны к оборудованию. Существуют свободно распространяемые версии, занимающие менее Мегабайта, пригодные к применению на любом процессоре.