Функциональное программирование.

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

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

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

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

Функциональный подход породил целое семейство языков, родоначальником которых, как уже отмечалось, стал язык программирования LISP. Позднее, в 70-х годах, был разработан первоначальный вариант языка ML, который впоследствии развился, в частности, в SML, а также ряд других языков. Из них, пожалуй, самым «молодым» является созданный уже совсем недавно, в 90-х годах, язык Haskell.

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

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

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

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

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

Часто к ним относят нелинейную структуру программы и относительно невысокую эффективность реализации. Однако первый недостаток достаточно субъективен, а второй успешно преодолен современными реализациями, в частности, рядом последних трансляторов языка SML, включая и компилятор для среды Microsoft.NET.

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

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

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

(a, b) A? B,

таких, что если

(a, b1) f и (a, b2) f,

то

b1 = b2.

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

Для формализации понятия «функция» была построена математическая теория, известная под названием ламбда-исчисления. Более точно это исчисление следует именовать исчислением ламбда-конверсий.

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

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

Систематизируем эволюцию теорий, лежащих в основе современного подхода к ламбда-исчислению.

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

Ранние языки функционального программирования, которые берут свое начало от классического языка LISP (LISt Processing), были предназначены, для обработки списков, т.е. символьной информации. При этом основными типами были атомарный элемент и список из атомарных элементов, а основной акцент делался на анализе содержимого списка.

Развитием ранних языков программирования стали языки функционального программирования с сильной типизацией, характерным примером здесь является классический ML, и его прямой потомок SML. В языках с сильной типизацией каждая конструкция (или выражение) должна иметь тип.

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

Следующим шагом в развитии языков функционального программирования стала поддержка полиморфных функций, т.е. функций с параметрическими аргументами (аналогами математической функции с параметрами). В частности, полиморфизм поддерживается в языках SML, Miranda и Haskell.

На современном этапе развития возникли языки функционального программирования «нового поколения» со следующими расширенными возможностями: сопоставление с образцом (Scheme, SML, Miranda, Haskell), параметрический полиморфизм (SML) и так называемые «ленивые» (по мере необходимости) вычисления (Haskell, Miranda, SML).

Семейство языков функционального программирования довольно многочисленно. Об этом свидетельствует не столько значительный список языков, сколько тот факт, что многие языки дали начало целым направлениям в программировании. Напомним, что LISP дал начало целому семейству языков: Scheme, InterLisp, COMMON Lisp и др.

Не стал исключением и изучаемый нами язык программирования SML, который был создан в форме языка ML Р. Милнером (Robin Milner) в MIT (Massachusetts Institute of Technology) и первоначально предназначен для логических выводов, в частности, доказательства теорем. Язык отличается строгой типизацией, в нем отсутствует параметрический полиморфизм.

Развитием «классического» ML стали сразу три современных языка с практически одинаковыми возможностями (параметрический полиморфизм, сопоставление с образцом, «ленивые» вычисления). Это язык SML, разработанный в Великобритании и США, CaML, созданный группой французских ученых института INRIA, SML/NJ – диалект SML из New Jersey, а также российская разработка – mosml («московский» диалект ML).

Близость к математической формализации и изначальная функциональная ориентированность послужили причиной следующих преимуществ функционального подхода:

простота тестирования и верификации программного кода на основе возможности построения строгого математического доказательства корректности программ;

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

безопасная типизация: недопустимые операции с данными исключены;

динамическая типизация: возможно обнаружение ошибок типизации во время выполнения (отсутствие этого свойства в ранних языках функционального программирования может приводить к переполнению оперативной памяти компьютера);

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

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

безопасность программного кода, т.е. гарантия отсутствия переполнения памяти (в случае корректно написанной программы) и, соответственно, защиты от потенциальной неустойчивости работы системы посредством искусственного создания переполнения (такие языки программирования как «классический» C и C++ потенциально небезопасны);

статическая типизация: все ошибки несоответствия типов выявляются уже на стадии контроля соответствия типов в ходе трансляции (а не во время выполнения программы, как в LISP и Scheme);

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

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

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

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

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

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

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

интеграция различных языков функционального программирования (при этом максимально используются преимущества каждого из языков, в частности, Scheme предоставляет механизм сопоставления с образцом, а SML – возможность вычисления по мере необходимости);

интеграция различных подходов к программированию на основе межъязыковой инфраструктуры Common Language Infrastructure, или CLI (в частности, возможно использование C# для обеспечения преимуществ объектно-ориентированного подхода и SML – функционального, как в настоящем курсе);

общая унифицированная система типизации Common Type System, CTS (единообразное и безопасное управление типами данных в программе);

многоступенчатая, гибкая система обеспечения безопасности программного кода (в частности, на основе механизма сборок).

10. Модульное программирование: основные понятия.

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

Концепции модульного программирования. В основе модульного программирования лежат три основных концепции:

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

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

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

синтаксическая обособленность, т. е. выделение модуля в тексте синтаксическими элементами;

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

общность данных, т. е. наличие собственных данных, сохраняющихся при каждом обращении;

полнота определения, т. е. самостоятельность программной единицы.

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

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

потребность организационного расчленения крупных разработок;

возможность параллельного исполнения модулей (в контексте параллельного программирования).

Определения модуля и его примеры. Приведем несколько дополнительных определений модуля.

Модуль — это совокупность команд, к которым можно обратиться по имени.

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

Функциональная спецификация модуля должна включать:

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

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

Разновидности модулей. Существуют три основные разновидности модулей:

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

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

a)задачи в языке программирования Ada;

b)кластер в языке программирования CLU;

c)классы в языках программирования C++ и Java.

3) " Большие” (логические) модули, объединяющие набор " средних" или " маленьких" модулей. Примеры " больших" модулей в языках программирования:

a)модуль в языке программирования Modula-2;

b)пакеты в языках программирования Ada и Java.

Набор характеристик модуля предложен Майерсом [Майерс 1980]. Он состоит из следующих конструктивных характеристик:

1) размера модуля;

В модуле должно быть 7 (+/-2) конструкций (например, операторов для функций или функций для пакета). Это число берется на основе представлений психологов о среднем оперативном буфере памяти человека. Символьные образы в человеческом мозгу объединяются в " чанки" — наборы фактов и связей между ними, запоминаемые и извлекаемые как единое целое. В каждый момент времени человек может обрабатывать не более 7 чанков.

Модуль (функция) не должен превышать 60 строк. В результате его можно поместить на одну страницу распечатки или легко просмотреть на экране монитора.

2) прочности (связности) модуля;

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

Связность (прочность) модуля (cohesion) — мера независимости его частей. Чем выше связность модуля — тем лучше, тем больше связей по отношению к оставшейся части программы он упрятывает в себе. Можно выделить типы связности, приведенные ниже.

Функциональная связность. Модуль с функциональной связностью реализует одну какую-либо определенную функцию и не может быть разбит на 2 модуля с теми же типами связностей.

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

Информационная (коммуникативная) связность. Модуль с информационной связностью — это модуль, который выполняет несколько операций или функций над одной и той же структурой данных (информационным объектом), которая считается неизвестной вне этого модуля. Эта информационная связность применяется для реализации абстрактных типов данных.

Обратим внимание на то, что средства для задания информационно прочных модулей отсутствовали в ранних языках программирования (например, FORTRAN и даже в оригинальной версии языка Pascal). И только позже, в языке программирования Ada, появился пакет — средство задания информационно прочного модуля.

3) сцепления модуля с другими модулями;

Сцепление (coupling) — мера относительной независимости модуля от других модулей. Независимые модули могут быть модифицированы без переделки других модулей. Чем слабее сцепление модуля, тем лучше. Рассмотрим различные типы сцепления.

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

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

Сцепление по простым элементам данных.

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

4) рутинности (идемпотентность, независимость от предыдущих обращений) модуля.

Рутинность — это независимость модуля от предыдущих обращений к нему (от предыстории). Будем называть модуль рутинным, если результат его работы зависит только от количества переданных параметров (а не от количества обращений).

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

В большинстве случаев делаем модуль рутинным, т. е. независимым от предыдущих обращений.

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

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

11. Структурное программирование: основные понятия.

Структурное программирование (СП) возникло как вариант решения проблемы уменьшения СЛОЖНОСТИ разработки программного обеспечения.

В начале эры программирования работа программиста ничем не регламентировалась. Решаемые задачи не отличались размахом и масштабностью, использовались в основном машинно-ориентированные языки и близкие к ним язык типа Ассемблера, разрабатываемые программы редко достигали значительных размеров, не ставились жесткие ограничения на время их разработки.

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

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

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

Подход базируется на двух основных принципах:

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

· Использование структурного кодирования.

· Напомним, что данная методология является важнейшим развитием императивной методологии.

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

Методы и концепции, лежащие в основе структурного программирования. Их три

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

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

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

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

[Пратт Т., 1979] " Важным для программиста свойством синтаксиса является возможность отразить в структуре программы структуру лежащего в ее основе алгоритма. При использовании для построения программы метода, известного под названием структурное программирование, программа конструируется иерархически - сверху вниз (от главной программы к подпрограммам самого нижнего уровня), с употреблением на каждом уровне только ограниченного набора управляющих структур: простых последовательностей инструкций, циклов и некоторых видов условных разветвлений. При последовательном проведении этого метода структуру результирующих алгоритмов легко понимать, отлаживать и модифицировать. В идеале у нас должна появиться возможность перевести построенную таким образом схему программы прямо в соответствующие программные инструкции, отражающие структуру алгоритма."

Теорема о структурировании (Бёма-Джакопини (Boem-Jacopini)): Всякую правильную программу (т.е. программу с одним входом и одним выходом без зацикливаний и недостижимых веток) можно записать с использованием следующих логических структур - последовательность, выбора и повторение цикла

Следствие 1: Всякую программу можно привести к форме без оператора goto.

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

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

Структурное программирование- это не самоцель. Его основное назначение- это получение хорошей (" правильной") программы, однако даже в самой хорошей программе операторы перехода goto иногда нужны: например - выход из множества вложенных циклов.

Практически на всех языках, поддерживающих императивную методологию, можно разрабатывать программы и по данной методологии. В ряде языков введены специальные заменители оператора goto, позволяющие облегчить управление циклами (например, Break и Continue в языке C).

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