Information
ИНТУИТ:
Программирование
:The basics of functional programming
: Information
Created: 18.03.2004 | Level: specialist | Access: paid
В курсе изложены основы функционального программирования и методы его применения при решении сложных задач на стыке искусственного интеллекта и системного программирования.
Студенты познакомятся с основами символьной обработки информации, слабо отраженными в отечественной литературе, а также с эффективными методами преобразования информации, реализация которых требует многоуровневого обобщения и абстрагирования, что наиболее естественно выражается в терминах функционального программирования. Функциональное программирование зарекомендовало себя как гибкая методика с практически неограниченными возможностями информационного моделирования, способствующего решению задач исследовательского и технического характера, актуальность которых резко возрастает. Традиционные средства слишком нацелены на кодирование битов-байтов, тогда как основная работа переместилась на более крупные формирования, такие как системы файлов, маршрутизация, многоканальный обмен, многопроцессорные комплексы, многоуровневые протоколы и т.п. Переход к результативной обработке столь сложно устроенных данных требует более глубокого абстрагирования, что может быть изучено прототипированием в функциональном стиле.Техника функционального программирования иллюстрируется на языке Лисп, послужившем основой широкого спектра исследований и прикладных разработок, оказавших существенное влияние на расширение и распространение компьютерных и информационных технологий, по существу являющихся ключевыми для анализа и формирования многих сфер деятельности. Изучение языка Лисп является важной составляющей образования в области информатики еще и по той причине, что в настоящее время происходит рост популярности скриптовых, интерпретируемых языков, для понимания которых знакомство с Лиспом и функциональным программированием весьма полезно. Лисп также представляет собой ключ и базовую модель для изучения основных задач системного программирования и искусственного интеллекта. Именно определение Лиспа и раскрутку системы программирования на его основе следует рассматривать как первый полномасштабный эксперимент в области применения функционального программирования для решения весьма сложной задачи: организации инструментальной поддержки для исследования и разработки нового класса задач информационной обработки с высоким уровнем новизны.При отладке примеров использован GNU Clisp.Курс предназначен для студентов, интересующихся перспективами информационных технологий и предпочитающих понимать задачи, с которыми приходится сталкиваться в разных областях применения информационных систем.
Goal: Дать представление о возможностях функционального подхода к задачам информатики, особенно на ранних стадиях постановки новых задач, а также при разработке и совершенствовании наукоемкого и интеллектуального ПО, включая решение задач искусственного интеллекта и компьютерной лингвистики.
Prerequisites: Желательно иметь представление о теории алгоритмов и рекурсивных функций.
План занятий
| Lesson | Title << | Date |
|---|---|---|
| - | ||
Lecture 154 minutes | Основные идеи
В этой лекции дается общее представление о функциональном программировании и сфере его применения, включая анализ основных понятий и принципов и их иллюстрацию на материале истории языка Лисп, его диалектов, наследников и реализаций. Рассматривается роль функциональных программ в жизненном цикле программного обеспечения и эволюции информационных технологий, а также перспективы функционального подхода к совершенствованию информационных систем.
Contents | - |
Тест 124 minutes | - | |
Lecture 21 hour 20 minutes | Элементарный Лисп
Изучается ключевой метод функционального программирования — выбор семантического базиса для класса решаемых задач на примере организации информационной обработки символьными выражениями в языке Лисп. Вводятся базовые понятия, достаточные для символьного представления программ. Формализм рекурсивных функций и простые алгоритмы символьной обработки привлечены для обоснования и демонстрации функционального подхода к представлению программ. Анализируются требования к полноте и эффективности их обработки. В качестве исторической иллюстрации полномасштабного применения функционального программирования для решения достаточно сложной задачи используется символика языка Лисп, выбранная при организации символьной обработки для решения задач искусственного интеллекта.
Contents | - |
Тест 227 minutes | - | |
Lecture 31 hour 4 minutes | Универсальная функция
Изучается техника использования параметров и функций при организации обычных вычислений как альтернатива стандартной программотехнике, основанной на изменениях состояний памяти. Рассматриваются методы управления эффективностью и порядком вычислений, организованных как применение функций к заданным аргументам. Оценивается сложность формирования результата в зависимости от параметризации форм, задающих вычисления. Строится простейшее определение универсальной функции, задающей границы вычисления представленных списками определенных форм над С-выражениями.
Contents | - |
Тест 327 minutes | - | |
Lecture 454 minutes | Отображения и функционалы
Программирование отображений и использование функционалов демонстрируется как метод резкого повышения производительности программирования и эффективности отладки программ. Изучается механизм безымянных определений. Рассматриваются разные схемы отображений аргументов и формирования результатов на основе отображающих функций над компонентами структур данных и определения различных функциональных схем переработки данных.
Contents | - |
Тест 427 minutes | - | |
Lecture 545 minutes | Имена, определения и контексты
Рассматриваются основные методы расширения функциональных систем с помощью иерархии разнородных контекстов определений. Изучаются приемы достижения удобочитаемости функциональных программ при определении сложных функций и анализируются особенности типовых схем связывания имен переменных с их значениями, принятых в системах программирования. Знакомство с методом неподвижных точек в системах рекурсивных определений логически завершает схему выбора решений по взаимодействию имен с определениями.
Contents | - |
Тест 527 minutes | - | |
Lecture 656 minutes | Свойства атомов и категории функций
Методы расширения функциональных построений применены для моделирования привычного операторно-процедурного стиля программирования и техники работы с глобальными определениями. Демонстрируется еще один важный метод — обобщение базовой схемы обработки символьных выражений и представленных с их помощью функциональных форм на основе списков свойств атомов. В результате можно собирать и специализировать функционально полное определение гибкого и расширяемого интерпретатора для языка программирования на примере Лиспа, написанном на Лиспе. Акцент на возможности варьирования семантики функций и пополнения семантического базиса с целью автоматизации выполненных построений в процессе исследования границ класса решаемых задач и конкретизации методов их решения.
Contents | - |
Тест 627 minutes | - | |
Lecture 733 minutes | Детализация базовых функций
Рассматривается функциональный подход к низкоуровневому программированию на уровне ассемблера, использованный при реализации Лисп. Изучается понятие абстрактной машины (secd) для определения операционной семантики языка функционального программирования по Венской методике, а именно для отображения абстрактного синтаксиса языка на язык абстрактной машины. Анализируется процедура включения средств уровня ассемблера в высокоуровневую обстановку языка Лисп, опробованных при раскрутке Лисп-системы.
Contents | - |
Тест 727 minutes | - | |
Lecture 840 minutes | Компиляция функциональных программ
В данной лекции изучаются требования к компиляции функциональных программ и строится определение компилятора.
Для Лиспа такое определение написано на Лиспе, как и определение интерпретатора. Рассматриваются Венская методика определения
языков программирования, а именно отображение абстрактного синтаксиса языка на
язык абстрактной машины, и приемы оптимизационного программирования. Разложение программы на функции с разным уровнем
отладки является отправной точкой при выборе оптимизационных решений. Компиляция программ рассматривается как один из
методов оптимизации процессов, осуществляемый как символьное преобразование — трансляция с исходного языка высокого
уровня на язык низкого уровня, допускающий оптимизирующую кодогенерацию.
Contents | - |
Тест 827 minutes | - | |
Lecture 936 minutes | Реализационные решения
Приведены принципы реализации, описаны структуры данных, удобные для динамической обработки информации. Проиллюстрированы методы "сборки мусора" и других реализационных механизмов функциональных языков программирования, давших экспериментальное обоснование современным решениям в области языковых новинок по организации вычислений, ставших практичными на современном оборудовании, которое обладает достаточно высокими эксплуатационными характеристиками. Рассмотрена последовательность комплектации ядра системы программирования, технические детали организации ее рабочего цикла и функциональные средства оперативного мониторинга фактического состава системы.
Contents | - |
Тест 927 minutes | - | |
Lecture 1046 minutes | От ФП к ООП
Анализируется содержательное родство между функциональным (ФП) и объектно-ориентированным (ООП) программированием. Рассмотрены основные принципы ОО-программирования и проанализированы схемы их реализации в рамках функционального программирования на базе ряда структур данных на примере простой модели ОО-языка, встраиваемого в Лисп. Отмечены особенности системы CLOS, поддерживающей ООП на GNU Clsip. Реализация методов обработки объектов заданного класса сводится к отдельной категории функций, вызов которых управляется анализом принадлежности аргумента классу.
Contents | - |
Тест 1027 minutes | - | |
Lecture 1127 minutes | Варианты, последовательности, множества
Описаны приемы организации недетерминированных вычислений в рамках функционального стиля программирования. Реализация программ с возвратами, перебор вариантов, откат влекут за собой расширение семантического базиса механизмами обработки прерываний. Анализируется соответствие точности решения задач и уровня их изученности. Исследуются связь диагностической интерпретации и средств логического программирования. Обработка множеств, последовательностей и хэш-таблиц дает материал для простых примеров.
Contents | - |
Тест 1127 minutes | - | |
Lecture 1232 minutes | Управление процессами
Рассматривается эффективное обобщение процесса информационной обработки, вытекающее из возможности отложенных действий (lazy evaluation), органически присущей функциональному программированию благодаря унификации представления данных и программ. Анализируются резервы производительности обобщенных процессов и методы динамической оптимизации вычислений, приводящие к смешанным и параллельным вычислениям.
Contents | - |
Тест 1227 minutes | - | |
Lecture 1338 minutes | Функции высших порядков
Рассматривается аппарат функций высших порядков при организации высококвалифицированных процессов информационной обработки, использующей формализацию и спецификацию данных, таких как синтаксический анализ, кодогенерация, конструирование интерпретаторов и компиляторов по формальному определению реализуемого языка — так называемые синтаксически управлямые методы информационной обработки.
Contents | - |
Тест 1327 minutes | - | |
Lecture 1416 minutes | Макеты программ и тесты
Техника функционального программирования иллюстрируется примерами поддержки полного жизненного цикла программ с помощью быстрого прототипирования и спецификации программ. В этом плане существенна возможность введения частично определенных функций, варьируемых и уточняемых определений, а также специализация интерпретатора программ с целью учета уровня достоверности решений. Рассматриваются примеры построения прототипов системы, опережающего детальную разработку алгоритмов и отладку программ. Основой является процесс уточнения информации о решаемой задаче, продемонстрированный на отдельных примерах и схемах с привлечением частичных функций на доступных типах данных с доведением до полных функций, приспособленных к обработке произвольных данных.
Contents | - |
Тест 1427 minutes | - | |
Lecture 1547 minutes | Парадигмы программирования
В данной лекции подводится итог изучению основ ФП и особенностей его применения. Анализируются наиболее очевидные закономерности применения языков программирования, отражающие расширение класса решаемых задач, прогресс элементной базы и рост квалификации программистов. Рассматриваются ключевые моменты развития парадигм программирования и анализируются закономерности в процессе реализационного освоения новых областей обработки информации. Приведен небольшой обзор парадигм программирования. Для желающих поэкспериментировать дана справка о реализационных особенностях GNU Clisp [6, 7].
Contents | - |
Тест 1527 minutes | - | |
5 hours | - |