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

Размещено на http://www.allbest.ru/

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

Лекция 1. Вступительная лекция

Обзор истории развития научных направлений, сформировавших теоретическое основание курса.

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

Еще в 1924 г. М. Шейнфинкель (Moses Schonfinkel) разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление ламбда-исчисления - математической формализации, поддерживающей языки функционального программирования (т.е. программирования в терминах функций).

Затем в 1934 г. А. Черч (Alonso Church) предложил собственно исчисление ламбда-конверсий (или ламбда-исчисление) и применил его для исследования теории множеств. Вклад ученого был фундаментальным, так что теория до сих пор называется ламбда-исчислением и часто именуется в литературе ламбда-исчислением Черча.

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

В 60-х годах Х. Барендрегтом (H. Barendregt) были детально описаны синтаксис (т.е. форма конструкций) и семантика (т.е. значение конструкций) ламбда-исчисления.

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

В 60-х годах Дж. Бэкусом (John Backus) были созданы основы формализации синтаксиса языков программирования посредством специального математического языка. Позднее П. Науром (Peter Naur) этот язык (а с точки зрения целевого языка программирования - метаязык) был доработан, в результате чего возникла математическая нотация, известная и сегодня под названием "форм Бэкуса-Наура", или, сокращенно, БНФ.

Данная нотация была специально разработана с целью формализации синтаксиса языка программирования (в то время это был весьма популярный, прежде всего в математической среде, язык программирования ALGOL 60 с ясным, но довольно пространным синтаксисом). БНФ и сегодня являются теоретически адекватным и практически применимым средством формализации синтаксиса языков программирования.

В 90-х годах синтаксис современного языка программирования SML был сформулирован Р. Милнером (Robin Milner). В работах, описывающих синтаксис SML, и по сей день широко используются формы Бэкуса-Наура.

Что касается теоретических основ семантики вычислений, то в конце 60-х годов Д. Скотт (Dana S. Scott) предложил применить для формализации семантики математических теорий так называемые домены (пока будем неформально понимать их как особый вид множеств). При этом на основе доменов Д. Скоттом был предложен так называемый денотационный подход к семантике. Такой подход предполагает анализ синтаксически корректных конструкций языка (или, иначе, денотатов) с точки зрения возможности вычисления их значений посредством специализированных функций.

Далее, в 70-х годах, М. Гордон (Michael J.C. Gordon) исследовал аппарат денотационной семантики применительно к языкам функционального программирования и сделал вывод об адекватности и практической эффективности использования этого подхода для решения поставленной задачи.

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

Одним из практических результатов исследований в этом направлении стала разработка П. Лендином (Peter J. Landin) семантики модели языка программирования в форме абстрактной машины (т.е. модели компьютера), использовавшей понятие состояния.

Альтернативный подход к формализации семантики (который был осуществлен в рамках исследования так называемой операционной семантики языков программирования) привел к созданию Ч. Хоаром (Charles A.R. Hoare) аксиоматического метода, моделирующего отношения и причинно-следственные связи, возникающие между операторами языка программирования.

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

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

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

В 60-х годах Р. Хиндли (Roger Hindley) исследовал типизацию в комбинаторной логике. При этом основной проблемой было моделирование языков функционального программирования со строгой типизацией, к каковым, в частности, относится изучаемый в рамках курса язык SML. Р. Хиндли разработал выводимость типов (type inference), т.е. возможность неявно определять тип выражения, исходя из типов выражений, которые его окружают. Именно эта возможность широко используется в современных языках программирования, таких как SML и Haskell.

Кроме того, Р. Хиндли изучил полиморфные системы типов, т.е. такие системы типов, в которых допустимы параметризованные функции или функции, имеющие переменный тип.

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

Наконец, на рубеже 80-х и 90-х годов, рядом исследователей - У. Куком (William R. Cook), П. Кэннингом (Peter S. Canning), У.Хиллом (Walter L. Hill) и другими - была изучена концепция полиморфизма в приложении к объектно-ориентированному программированию (в частности, к языку C++) и выявлена возможность моделирования полиморфизма на основе ламбда-исчисления.

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

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

Принципиальная реализуемость рекурсии средствами математической теории была доказана С. Клини (S.C. Kleene) еще в 30-х годах. При этом фундаментом рассуждений служило ламбда-исчисление.

В 50-х годах появилась комбинаторная логика Х. Карри - более приближенная к практике программирования формальная система с возможностью моделирования рекурсии.

Вскоре, в 60-х годах, Джоном Маккарти (John McCarthy) в ходе создания языка функционального программирования LISP, была исследована практическая применимость рекурсивных вычислений для символьной обработки и доказана возможность реализации рекурсии в программировании.

Абстрактная машина как формальная модель вычислительной системы является весьма важным объектом исследования в рамках настоящего курса.

Еще в 30-х годах А. Тьюрингом (Alan Mathison Turing) и Э. Постом (Emil Leon Post) независимо друг от друга были созданы эквивалентные по возможностям, но практически весьма сложные в реализации формализации, известные как абстрактные машины и получившие названия по именам своих авторов.

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

В 60-х годах Д. Тернер (David Turner) предложил применять комбинаторы в качестве низкоуровневого кода для трансляторов языков функционального программирования, т.е. предвосхитил появление абстрактных машин, использующих в качестве инструкций комбинаторы.

Также в 60-х годах П. Лендин создал первую практически реализуемую абстрактную машину на основе расширенного ламбда-исчисления. Машина, получившая название SECD, формализовала вычисления на языке программирования ISWIM (If you See What I Mean), который впоследствии стал прообразом языка функционального программирования ML. Основным понятием для SECD-машины является понятие состояния.

Уже в 70-е годы группой ученых института INRIA (Франция), ведущую роль в работе которой сыграл Пьер Кюрьен (P.-L. Curien), была создана еще одна абстрактная машина, основанная на смене состояний и получившая название категориальной абстрактной машины (КАМ). Теория категорий в форме категориальной комбинаторной логики, которая является теоретическим фундаментом для КАМ, по сути, представляет собой вариант ламбда-исчисления. С помощью КАМ был реализован еще один современный диалект ML, получивший название CaML (по имени машины).

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

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

Исследования различных стратегий передачи параметров при обращении к функциям языков программирования (в частности, вызова функций по имени и по значению) были проведены Г. Плоткиным (G.D. Plotkin) на основе развития формализации SECD-машины П. Лендина. Полученные результаты легли в основу стратегии моделирования вычислений в ранних версиях языка функционального программирования ML.

В 70-х годах К. Уодсворт (Christopher P. Wadsworth) предложил механизм редукции графов для моделирования так называемых "ленивых" (т.е. выполняемых исключительно по мере необходимости) вычислений с помощью фундаментальной формальной теории-исчисления ламбда-конверсий.

Несколько позже Д. Тернером был представлен аналогичный механизм для "ленивых" вычислений в более приближенной к практике программирования формальной системе, а именно, в терминах выражений комбинаторной логики.

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

Примерно в тот же период Р. Хьюсом (R.J.M. Hughes) была разработана формальная система суперкомбинаторов (усовершенствованная комбинаторная логика Х. Карри), позволяющая моделировать методы реализации языков программирования с возможностью оптимизации вычислений.

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

В 50-х годах Х. Хассе (Helmut Hasse, 1898-1979) предложил использовать особого рода диаграммы для графической интерпретации отношения частичного порядка. Заметим, что позднее диаграммы, открытые ученым, стали называться диаграммами Хассе. И по сей день диаграммы Хассе являются наиболее широко распространенной графической формализацией механизма наследования.

Затем в 1976 году Н.Руссопулос (N.D. Roussopulos) впервые применил фреймовую нотацию для моделирования отношений между объектами тех или иных предметных областей. Кроме того, ученым было введено так называемое ISA-отношение частичного порядка, которое адекватно моделирует понятие наследования. Заметим, что обозначение ISA, которое возникло от английских слов " is a ", означающих " является одним из ", хорошо иллюстрирует суть понятия наследования на естественном языке.

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

Затем, в 1988-90 годах Л. Карделли (Luca Cardelli), У. Куком и другими учеными была исследована семантика наследования. При этом был построен вариант денотационной семантики, который, как оказалось, адекватно формализовал не только единичное, но и множественное наследование.

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

В конце 60-х годов Д. Скоттом была предложена теория вычислений - модель, основанная на понятии домена (которое можно неформально определить как особый вид множеств). Эта модель принципиально применима для формализации объектов и их взаимодействия.

В 80-х годах Д. Скоттом и М. Фурманом (Michael P. Fourman) был исследован механизм определенных дескрипций для формализации определений. В ходе изложения мы будем неоднократно использовать эту лаконичную и интуитивно прозрачную нотацию для математически строгой сокращенной записи определений объектов, типов и классов.

Позднее, в 90-е годы, В. Вольфенгагеном (Vyatcheslav E. Wolfengagen) была создана так называемая двухуровневая схема концептуализации, основанная на двукратном применении постулата свертывания (до известной степени аналогичного операции ламбда-абстракции). Модель позволяет полно и непротиворечиво описывать объекты предметных областей с учетом их рассмотрения как в динамике, так и в статике. При этом двухуровневая схема концептуализации позволяет моделировать как объекты предметной области, так и объекты языков программирования. Другим преимуществом модели является возможность ее использования применительно как к объектам данных, так и к объектам метаданных (метаданные можно неформально понимать как данные о данных).

Лекция 2. Классификация языков программирования

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

Проведем классификацию языков и подходов к программированию.

Первые языки программирования возникли относительно недавно. Различные исследователи указывают в качестве времени их создания 20-е, 30-е и даже 40-е годы XX столетия. Нашей задачей является не установление самого раннего языка, а поиск закономерностей в их развитии.

Как и следовало ожидать, первые языки программирования, как и первые ЭВМ, были довольно примитивны и ориентированы на численные расчеты. Это были и чисто теоретические научные расчеты (прежде всего, математические и физические), и прикладные задачи, в частности, в области военного дела.

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

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

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

Следующее десятилетие ознаменовалось появлением языков программирования так называемого "высокого уровня", по сравнению с ранее рассмотренными предшественниками, соответственно именуемыми низкоуровневыми языками.

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

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

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

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

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

Одним из таких примеров является язык Fortran, реализующий вычислительные алгоритмы. Другой пример - язык APL, трансформировавшийся в BPL и затем в C. Основные конструкции последнего остаются неизменными вот уже несколько десятилетий и присутствуют в языке C#, который нам предстоит изучить.

Примеры других языков программирования: ALGOL, COBOL, Pascal, Basic.

В 60-х годах возникает новый подход к программированию, который до сих пор успешно конкурирует с императивным, а именно, декларативный подход.

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

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

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

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

В частности, язык SML, который мы будем изучать в рамках данного курса, был разработан как средство доказательства теорем.

Различные диалекты языка LISP (в частности, Interlisp, Common Lisp, Scheme), возникли потому, что ядро и идеология этого языка оказались весьма эффективными при реализации символьной обработки (анализе текстов).

Другие характерные примеры декларативных языков программирования: SML, Haskell, Prolog.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нелинейность структуры программы является особенностью декларативного подхода и, строго говоря, представляет собой оригинальную особенность, а не объективный недостаток.

В качестве примеров языков логического программирования можно привести Prolog (название возникло от слов PROgramming in LOGic) и Mercury.

Важным шагом на пути к совершенствованию языков программирования стало появление объектно-ориентированного подхода к программированию (ООП) и соответствующего класса языков.

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

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

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

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

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

Объекты, классы и методы могут быть полиморфными, что делает реализованное программное обеспечение более гибким и универсальным.

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

Пожалуй, наиболее известным примером объектно-ориентированного языка программирования является язык C++, развившийся из императивного языка С. Его прямым потомком и логическим продолжением является язык С#. Другие примеры объектно-ориентированных языков программирования: Visual Basic, Eiffel, Oberon.

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

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

Основные достоинства языков данного класса унаследованы от объектно-ориентированных языков программирования. Это интуитивная ясность описаний, близость к предметной области, высокая степень абстракции, хорошая переносимость.

Широкие возможности повторного использования кода также унаследованы сценарными языками от объектно-ориентированных предков.

Существенным преимуществом языков сценариев является их совместимость с передовыми инструментальными средствами автоматизированного проектирования и быстрой реализации программного обеспечения, или так называемыми CASE- (Computer-Aided Software Engineering) и RAD- (Rapid Application Development) средствами.

Одним из наиболее передовых инструментальных комплексов, предназначенных для быстрой разработки приложений, является Microsoft Visual Studio NET; его возможности мы будем изучать в рамках данного курса.

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

Характерные примеры сценарных языков программирования: VBScript, PowerScript, LotusScript, JavaScript.

Еще один весьма важный класс языков программирования - языки поддержки параллельных вычислений.

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

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

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

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

Примерами языков программирования с поддержкой параллельных вычислений могут служить Ada, Modula-2 и Oz.

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

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

Подводя итоги, кратко перечислим рассмотренные в данной лекции подходы к программированию:

· ранние неструктурные подходы;

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

· функциональный подход;

· логический подход;

· объектно-ориентированный подход;

· смешанный подход (некоторые подходы можно комбинировать);

· компонентно-ориентированный (программный проект рассматривается как множество компонент, такой подход принят, в частности, в NET);

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

Лекция 3. Концепция и возможности подхода NET

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

Попытаемся найти ответ на вопрос: что такое NET? Несмотря на популярность термина, однозначно ответить непросто, прежде всего по той причине, что ответ представляется многоаспектным.

Итак, можно сказать, что NET - это подход к проектированию и реализации программного обеспечения, включающий, по меньшей мере, четыре компонента:

1. идеология проектирования и реализации программного обеспечения;

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

3. унифицированная, интегрированная технологическая платформа для программирования;

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

Остановимся подробнее на каждом из этих аспектов.

Прежде всего, постараемся объяснить идеологию подхода Microsoft NET.

Самой корпорацией-разработчиком сформулированы приблизительно следующие важнейшие аспекты видения (vision) идеологии NET:

1. легкость развертывания приложений в глобальной среде Internet;

2. экономичная разработка программного обеспечения;

3. "бесшовная", гибкая интеграция программных продуктов и аппаратных ресурсов;

4. предоставление программного обеспечения как сервиса;

5. новый уровень безопасности и удобства использования.

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

Рассмотрим подробнее, как идеология NET претворяется в практические вопросы проектирования программного обеспечения.

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

Существенным преимуществом является и возможность практической реализации принципа "всякая сущность представляет собой объект гетерогенной программной среды". Во многом это стало реализуемым благодаря усовершенствованной, обобщенной системе типизации Common Type System, или CTS, которая будет подробнее рассмотрена в одной из следующих лекций.

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

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

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

Говоря о NET как о технологической платформе, нельзя не отметить тот факт, что она обеспечивает одновременную поддержку проектирования и реализации программного обеспечения с использованием различных языков программирования. При этом поддерживаются десятки языков программирования, начиная от самых первых (в частности, COBOL и FORTRAN) и заканчивая современными (например, C# и Visual Basic). Ранние языки программирования до сих пор активно используются, в частности, для обеспечения совместимости с ранее созданными приложениями (скажем, COBOL весьма широко применялся для создания прикладных программ, поддерживающих финансовую деятельность).

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

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

Немаловажно отметить и то обстоятельство, что новая технология NET не только востребована мировой общественностью, но и официально признана, что отражено в соответствующих стандартах ECMA (European Computer Manufacturers Association).

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

Прежде всего, необходимо отметить поддержку многоязыковой среды разработки приложений CLR (Common Language Runtime). Эта возможность появилась благодаря универсальному межъязыковому интерфейсу Common Language Infrastructure, или CLI, который поддерживает разработку программных компонент на различных языках программирования.

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

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

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

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

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

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

Еще одним важным аспектом комплексного обеспечения безопасности в NET является обязательная проверка промежуточного кода (IL - Intermediate Language) на корректность типизации, осуществляемая в рамках реализованной стратегии расширенного контроля соответствия типов.

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

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

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

Продолжим обсуждение поддержки жизненного цикла программного обеспечения в рамках подхода NET.

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

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

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

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

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

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

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

При этом наиболее существенными задачами, решение которых необходимо обеспечить, являются следующие:

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

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

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

В этой связи в концепции NET сформулирована и решена задача адаптации изначально аморфной и практически не структурированной Internet-среды для достижения возможности интеграции приложений. Основные направления решения этой задачи следующие:

· унификация информационной инфраструктуры;

· достижение необходимого уровня интероперабельности прикладного программного обеспечения;

· достижение необходимого уровня масштабируемости прикладного программного обеспечения.

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

Задача поддержки интероперабельности прикладного программного обеспечения в рамках концепции NET решается с помощью универсальной высокоуровневой языковой среды Common Language Infrastructure (CLI), которая характеризуется следующими возможностями.

Прежде всего, осуществляется поддержка разнообразных языков программирования, а, следовательно, и различных подходов к программированию, в частности, функционального (например, на основе SML, Scheme, Haskell), объектно-ориентированного (например, на основе С++) и компонентного (например, на основе С#).

Кроме того, интегрированное использование языков программирования осуществляется совместно с единой системой типов (Common Type System, CTS), включающей общую иерархию для примитивных типов, типов-значений и ссылочных типов.

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

Наконец, универсальная высокоуровневая языковая среда Common Language Infrastructure обеспечивает межъязыковую отладку.

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

В отношении технологий NET теоретические достижения и технологические инновации подтверждаются мнением европейской ассоциации по стандартам ECMA (European Computer Manufacturers Association).

Так, язык программирования C# и среда Common Language Infrastructure (CLI) ратифицированы организацией ECMA в качестве международного стандарта. Кроме того, несколько независимых разработчиков программного обеспечения осуществляют проекты в соответствии со спецификациями ECMA (в частности, реализация NET под управлением операционной системы Linux).

Ведущие производители аппаратного и программного обеспечения рассчитывают на NET как на стратегический путь совместного с Microsoft развития. В частности, в 2001 году подписано соглашение о сотрудничестве между Microsoft, Intel и Hewlett-Packard.

Вопреки распространенному мнению, Microsoft не настаивает на непременном условии единственности операционной системы Windows для поддержки NET. Корпорация планирует совместную разработку программного проекта NET под управлением операционных систем FreeBSD и Windows.

Более подробную информацию о стандартизации технологий и программного обеспечения семейства NET можно получить по адресу: http://msdn.microsoft.com/net/ecma/.

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

Во-первых, разработчики отмечают достаточно высокие требования к аппаратному обеспечению (в частности, объем оперативной памяти должен быть не менее 256 Мбайт, свободный объем жесткого диска для работы с Microsoft Visual Studio NET - не менее 10 Гбайт).

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

Поддержка теоретически интересных и практически полезных языков программирования реализована лишь отчасти (скажем, компилятор для языка программирования SML для Visual Studio NET находится в процессе реализации). Поскольку многие компиляторы для языков программирования предоставляюется сторонними по отношению к Microsoft компаниями-разработчиками или некоммерческими учреждениями, результаты их деятельности поддаются контролю и доработке с ограничениями.

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

Подведем итоги лекции.

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

Несомненное качественное превосходство над существующими средствами автоматизированного проектирования и быстрой реализации прикладного программного обеспечения (в частности, Inprise Delphi и JBuilder, Oracle Developer, Microsoft Visual Studio и др.) достигается за счет следующих основных факторов:

· интероперабельность и межъязыковое взаимодействие;

· многоуровневая, гибкая и надежная политика безопасности;

· интеграция с технологией web-сервисов;

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

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

Лекция 4. Функциональный подход к программированию

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

Классификация подходов к программированию была построена нами в ходе лекции 1.

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

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

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

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

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

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