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

Оптимизация вычислений и абстрактные машины

Разбить на страницы
Показывать лекцию целиком

Проиллюстрируем особенности реализации наиболее существенных стратегий вычислений на примере КАМ.

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

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

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

Перечислим наиболее существенные (с учетом целей и задач нашего курса) из этих недостатков.

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

Другим существенным недостатком КАМ является отсутствие поддержки рекурсивных вычислений, которое, как мы увидим впоследствии, устраняется посредством модификации среды вычислений.

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

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

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

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

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

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

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

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

Заменим "встроенные" в систему команд категориальной абстрактной машины одноместные функции на двухместные.

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

$$+<x,y> = \varepsilon o<\varepsilon o<'+,x>,y>.$$

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

$$\varepsilon o<\Lambda (x)oy,z> = xo<y,z>,$$

которое находится в полном соответствии с правилами редукции, принятыми в формальной системе категориальной комбинаторной логики, на основе которой построена КАМ.

Продолжим обсуждение перехода к многоместным операциям в языке программирования категориальной абстрактной машины. Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний   КАМ дополнительными инструкциями, которые, по аналогии с основными командами КАМ, представим в форме таблицы 12.1.

Дополнительные инструкции пространства состояний КАМ
Старое состояние КАМ Новое состояние КАМ
Терм Код Стек Терм Код Стек
true if abc sm S a c m
false if abc sm S b c m
(a,b) add c S {a+b} C S
(a,b) eq c S true/false C S

Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций сравнения if, проверки условия eq, а также сложения add. Проиллюстрируем практическую эффективность программного кода усовершенствованной категориальной абстрактной машины следующим примером. Рассмотрим программу категориальной абстрактной машины, вычисляющую сумму целых чисел 2 и 3 в "классической" версии "языка программирования" КАМ:

push cur (push push cdr swap quote 2 cons app swap push cur (cdr) swap quote 3 cons app cons app) swap quote + cons app.

"Запрограммируем" ту же задачу в усовершенствованной версии КАМ:

push quote 2 swap quote 3 cons add.

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

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

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

Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний   КАМ дополнительными инструкциями, которые, по аналогии с основными командами абстрактной машины, представим в форме таблицы 12.2.

Дополнительные инструкции КАМ для реализации рекурсивных вычислений
Старое состояние КАМ Новое состояние КАМ
Терм Код Стек Терм Код Стек
T dum c sm $Y C S
[a:b] wind c (t$Y)S (t.[a:b]) C S

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

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

При вычислении с вызовом по значению (call-by-value) все выражения должны быть означены до вычисления операции аппликации.

При вычислении с вызовом по имени (call-by-name) до вычисления операции аппликации необходима подстановка термов вместо всех вхождений формальных параметров перед означиванием. Именно эта стратегия лежит в основе "ленивых" (lazy), "отложенных" (delayed) или "замороженных" (frozen) вычислений, которые принципиально необходимы для обработки потенциально бесконечных структур данных.

Наконец, при вычислении с вызовом по необходимости (call-by-need) ранее вычисленные значения аргументов сохраняются в памяти компьютера только в том случае, если необходимо их повторное использование.

Чтобы устранить сложности с поддержкой категориальной абстрактной машиной   "ленивых" вычислений, пересмотрим цикл работы   КАМ, расширив пространство состояний дополнительными инструкциями для "замораживания" (freeze) и "размораживания" (unfreeze), которые представим в форме таблицы 12.3.

Дополнительные инструкции КАМ для реализации "ленивых" вычислений
Старое состояние КАМ Новое состояние КАМ
Терм Код Стек Терм Код Стек
s {freeze c}.C1 S C.s C1 S
C.s unfreeze.C S s C S
s unfreeze.C S s C S

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

Заметим, что возможность "ленивого" связывания переменных с их значениями в языках функционального программирования вытекает из формулировки теорем Черча-Россера.

Поскольку доказательство теорем Черча-Россера выходит за рамки настоящего курса, ограничимся приведением формулировок теорем как таковых.

Теорема Черча-Россера

Пусть E1 и E2 суть ламбда-выражения, причем справедливо соотношение: E1 = E2.

Тогда существует ламбда-выражение E такое, что выполнены следующие условия: во-первых, E1 = E, и, во-вторых, E2 = E.

Заметим, что символ "=" в формулировке теоремы понимается в смысле отношения конвертируемости.

Теорема Черча-Россера (1)

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

Теорема Черча-Россера (2)

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

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

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

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

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

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

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

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

Во-первых, необходимо отметить, что в рамках рассматриваемой инструментально-технологической платформы Microsoft .NET используется виртуальная машина с универсальным высокоуровневым ассемблером (известным под названием Microsoft Intermediate Language, или, сокращенно, MSIL), принципиально подобная КАМ. Абстрактная машина. NET транслирует исходный текст на языке программирования в код MSIL, который в значительной степени подобен КАМ -коду.

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

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

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

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

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

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

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

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

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

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

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

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

В связи с этим в ходе дальнейшего исследования планируется систематическое изучение следующих вопросов:

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

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

    Для более подробного самостоятельного ознакомления с тематикой лекции рекомендуется следующий список источников: [24, 31, 32, 49, 51, 62, 76, 78].

    Страницы:

    Проиллюстрируем особенности реализации наиболее существенных стратегий вычислений на примере КАМ.

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

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

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

    Перечислим наиболее существенные (с учетом целей и задач нашего курса) из этих недостатков.

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

    Другим существенным недостатком КАМ является отсутствие поддержки рекурсивных вычислений, которое, как мы увидим впоследствии, устраняется посредством модификации среды вычислений.

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

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

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

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

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

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

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

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

    Заменим "встроенные" в систему команд категориальной абстрактной машины одноместные функции на двухместные.

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

    $$+<x,y> = \varepsilon o<\varepsilon o<'+,x>,y>.$$

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

    $$\varepsilon o<\Lambda (x)oy,z> = xo<y,z>,$$

    которое находится в полном соответствии с правилами редукции, принятыми в формальной системе категориальной комбинаторной логики, на основе которой построена КАМ.

    Продолжим обсуждение перехода к многоместным операциям в языке программирования категориальной абстрактной машины. Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний   КАМ дополнительными инструкциями, которые, по аналогии с основными командами КАМ, представим в форме таблицы 12.1.

    Дополнительные инструкции пространства состояний КАМ
    Старое состояние КАМ Новое состояние КАМ
    Терм Код Стек Терм Код Стек
    true if abc sm S a c m
    false if abc sm S b c m
    (a,b) add c S {a+b} C S
    (a,b) eq c S true/false C S

    Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций сравнения if, проверки условия eq, а также сложения add. Проиллюстрируем практическую эффективность программного кода усовершенствованной категориальной абстрактной машины следующим примером. Рассмотрим программу категориальной абстрактной машины, вычисляющую сумму целых чисел 2 и 3 в "классической" версии "языка программирования" КАМ:

    push cur (push push cdr swap quote 2 cons app swap push cur (cdr) swap quote 3 cons app cons app) swap quote + cons app.

    "Запрограммируем" ту же задачу в усовершенствованной версии КАМ:

    push quote 2 swap quote 3 cons add.

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

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

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

    Пересмотрим цикл работы (схему смены состояний) категориальной абстрактной машины, расширив пространство состояний   КАМ дополнительными инструкциями, которые, по аналогии с основными командами абстрактной машины, представим в форме таблицы 12.2.

    Дополнительные инструкции КАМ для реализации рекурсивных вычислений
    Старое состояние КАМ Новое состояние КАМ
    Терм Код Стек Терм Код Стек
    T dum c sm $Y C S
    [a:b] wind c (t$Y)S (t.[a:b]) C S

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

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

    При вычислении с вызовом по значению (call-by-value) все выражения должны быть означены до вычисления операции аппликации.

    При вычислении с вызовом по имени (call-by-name) до вычисления операции аппликации необходима подстановка термов вместо всех вхождений формальных параметров перед означиванием. Именно эта стратегия лежит в основе "ленивых" (lazy), "отложенных" (delayed) или "замороженных" (frozen) вычислений, которые принципиально необходимы для обработки потенциально бесконечных структур данных.

    Наконец, при вычислении с вызовом по необходимости (call-by-need) ранее вычисленные значения аргументов сохраняются в памяти компьютера только в том случае, если необходимо их повторное использование.

    Чтобы устранить сложности с поддержкой категориальной абстрактной машиной   "ленивых" вычислений, пересмотрим цикл работы   КАМ, расширив пространство состояний дополнительными инструкциями для "замораживания" (freeze) и "размораживания" (unfreeze), которые представим в форме таблицы 12.3.

    Дополнительные инструкции КАМ для реализации "ленивых" вычислений
    Старое состояние КАМ Новое состояние КАМ
    Терм Код Стек Терм Код Стек
    s {freeze c}.C1 S C.s C1 S
    C.s unfreeze.C S s C S
    s unfreeze.C S s C S

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

    Заметим, что возможность "ленивого" связывания переменных с их значениями в языках функционального программирования вытекает из формулировки теорем Черча-Россера.

    Поскольку доказательство теорем Черча-Россера выходит за рамки настоящего курса, ограничимся приведением формулировок теорем как таковых.

    Теорема Черча-Россера

    Пусть E1 и E2 суть ламбда-выражения, причем справедливо соотношение: E1 = E2.

    Тогда существует ламбда-выражение E такое, что выполнены следующие условия: во-первых, E1 = E, и, во-вторых, E2 = E.

    Заметим, что символ "=" в формулировке теоремы понимается в смысле отношения конвертируемости.

    Теорема Черча-Россера (1)

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

    Теорема Черча-Россера (2)

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

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

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

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

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

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

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

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

    Во-первых, необходимо отметить, что в рамках рассматриваемой инструментально-технологической платформы Microsoft .NET используется виртуальная машина с универсальным высокоуровневым ассемблером (известным под названием Microsoft Intermediate Language, или, сокращенно, MSIL), принципиально подобная КАМ. Абстрактная машина. NET транслирует исходный текст на языке программирования в код MSIL, который в значительной степени подобен КАМ -коду.

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

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

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

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

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

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

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

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

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

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

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

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

    В связи с этим в ходе дальнейшего исследования планируется систематическое изучение следующих вопросов:

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

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

    Для более подробного самостоятельного ознакомления с тематикой лекции рекомендуется следующий список источников: [24, 31, 32, 49, 51, 62, 76, 78].

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^