Готовый перевод Concepts, Techniques and Models of Computer Programming / Концепции, Техники и Модели Компьютерного Программирования: Предисловие

Шесть слепых мудрецов ощупали слона и начали обсуждать свои наблюдения. "Это замечательно" сказал первый, "слон похож на верёвку: тонкий и гибкий." "Нет, нет, не так" сказал второй, "слон похож на дерево: прочно стоит в земле." "Изумительно" сказал третий, "слон похож на стену." "Невероятно" сказал четвёртый, "слон - это труба заполненная водой." "Что это за странный зверь, который состоит из разных частей" сказал пятый. "Действительно странно" сказал шестой, "но в основе должна лежать некая гармония. Этот вопрос нужно исследовать подробнее."
- Свободная адаптация классической индийской сказки.

"Язык программирования подобен естественному, человеческому языку в том плане, что позволяет создавать определённые метафоры, образы и способы мышления."
- "Переворот в сознании: дети, компьютеры и плодотворные идеи" [141], Сеймур Пейперт (1980)

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

Мы сфокусировались на концепциях и техниках программирования, а также на их использовании, а не на языках программирования. Концепции представлены в терминах вычислительных моделей. Вычислительная модель - это формальная система, которая определяет как должны выполняться вычисления. Существует множество способов определения вычислительных моделей. Поскольку эта книга разрабатывалась с учётом на практику, то очень важно чтобы вычислительная модель приносила прямую пользу программисту. Далее мы будем определять её в терминах важных для программистов концепций: типы данных, операции и язык программирования. Термин вычислительная модель уточняет неточное понятие "парадигмы программирования". Во всей книге рассказывается о вычислительных моделях, а не парадигмах программирования. Иногда мы будем использовать фразу "модель программирования". Это относится к тому, что необходимо программисту: техники программирования и принципы проектирования стали возможны благодаря вычислительным моделям.

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

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

Как мы решаем какую концепцию следует добавить при переходе от одной модели к другой? Мы много раз коснёмся этого вопроса на протяжении этой книги. Главным критерием является принцип творческого расширения. Грубо говоря новая концепция добавляется тогда, когда программы становятся сложными из-за технических причин и тем самым отдаляются от решаемых задач. Добавление концепции к языку ядра позволяет сохранять простоту программы, при условии если концепция была выбрана верно. Более подробно это объясняется в Приложении D. Этот принцип лежит в прогрессии языков ядра, представленных в книге.

Приятная особенность в подходе языка ядра в том, что он даёт нам возможность использовать вместе различные модели в одной программе. Обычно это называется мультипарадигменным программированием. Это вполне естественно, поскольку означает просто использование нужной концепции для проблемы, вне зависимости от того, из какой вычислительной модели она появилась. Мультипарадигменное программирование - это старая идея. Например, архитекторы Lisp и Scheme давно придерживаются подобных взглядов. Однако, в этой книге мультипарадигменное программирование применяется более глубже и шире, чем было до сих пор.

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

Упомянутые языки

В этой книге мы упомянули много языков программирования и связали их конкретными вычислительными моделями. Например, Java и Smalltalk основаны на объектно-ориентированной модели. Haskell и Standard ML основаны на функциональной модели. Prolog и Mercury основаны на логической модели. Но не все интересные языки можно классифицировать подобным образом. Отметим некоторые языки имеющие свои особенности. Например, Lisp и Scheme пионеры во многих концепциях, представленных здесь. Erlang - это функциональный, по сути параллельный и поддерживающий отказоустойчивое распределённое программирование язык программирования.

Выделим четыре языка как представителей важных моделей вычислений: Erlang, Haskell, Java и Prolog. Мы идентифицируем вычислительные модели каждого языка в терминах единой системы этой книги. Если вы хотите получить более подробную информацию об этих языках, то обратитесь к соответствующей литературе. В связи с ограниченностью объёма книги мы не можем упомянуть здесь все интересные языки. Отсутствие упоминания в этой книге какого-либо языка ни в коем случае не может служить критерием оценки.

Цели книги

Обучение программированию

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

Что такое программирование?

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

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

И наука и технология

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

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

Больше чем ремесло

Несмотря на многие попытки введения научной базы, программированию почти всегда обучают как ремеслу. Обычно обучение велось в контексте одного (или нескольких) языков программирования (например, Java, дополненная Haskell, Scheme или Prolog). Исторические события происходящие при развитии какого-либо конкретно взятого языка тесно переплетаются с фундаментальными концепциями и их нельзя отделить друг от друга. Возникает путаница между инструментами и концепциями. Что более важно различные школы программирования основываются на различных видениях программирования, называемых "парадигмами": объектно-ориентированное, логическое, функциональное и т.д. Каждая школа обучает своей собственной науке. Программирование было потеряно как единая дисциплина.

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

В результате программы страдают от бедной архитектуры. Мы даём примеры на основе Java, но подобная проблема существует во всех языках в разной степени. Параллелизм в Java сложен для использования и дорог в плане вычислительных ресурсов. Из-за этих трудностей, программисты обученные на Java делают вывод что параллелизм - это фундаментально сложная и дорогостоящая концепция. Спецификации программ строятся вокруг сложностей, и часто в искажённом виде. Но эти трудности вообще не фундаментальны. Существуют формы параллелизма, которые являются очень полезными и лёгкими в программировании в виде последовательных программ (например, потоковое программирование, на примере Unix pipe). Кроме того, возможно реализовать нити, базовую единицу параллелизма, почти такие же дешёвые, как и вызов процедуры. Если программиста обучили параллелизму правильным способом, то он или она может определять что ему нужно и программировать в системах без ограничений на параллелизм (включая улучшенные версии Java).

Подход язык ядра

Практические языки программирования масштабируются до программ, состоящих из миллионов строк кода. Они предоставляют богатый набор абстракций и синтаксиса. Как мы можем отделить фундаментальные концепции языка, лежащие в основе их успеха, от исторических событий? Подход язык ядра показывает этот способ. Согласно этому подходу практические языки транслируются в язык ядра, который состоит из малого числа программно-значимых элементов. Богатый набор абстракций и синтаксиса зашифрован в этом малом языке ядра. Этот подход даёт и программисту и студенту возможность понять то, что выполняет язык. Язык ядра даёт простую формальную семантику, которая позволяет производить рассуждения о корректности программ и их сложности. Что в свою очередь даёт прочный фундамент для программистской интуиции и программных техниках строящихся поверх неё.

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

Упрощение сложного явления на более простые составные части - характерно для научного метода. Этот результативный подход используется во всех науках. С помощью такого подхода можно достичь глубокого понимания явлений, и этим достигается возможность предсказывать события. Например, с помощью науки мы можем проектировать любые мосты (сделанные из дерева, железа, других материалов или из их сочетаний) и предсказывать их поведение в терминах более простых концепций, таких как сила, энергия, напряжение, и других законов [62].

Сравнение с другими подходами

Сравним подход язык ядра с тремя другими способами преподавания прочного и широкого научного фундамента программирования:

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

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

Мультипарадигменные языки - это языки, вобравшие в себя несколько программных парадигм. Например, Scheme - это и функциональный и императивный ([38]) язык, а Leda имеет элементы функционального, объектно-ориентированного и логического ([27]) языка. Полезность мультипарадигменного языка зависит от того насколько в него интегрированы различные парадигмы.

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

Проектирование абстракций

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

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

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

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

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

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

Главные особенности

Педагогический подход

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

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

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

Как и Структура и Интерпретация Компьютерных Программ за авторством Абельсона, Сассмана и Сассмана (Structure and Interpretation of Computer Programs, by Abelson, Sussman, & Sussman) [1, 2], наша книга в основном использует подход основанный на вычислении. Концепции иллюстрируются с помощью программных фрагментов, которые можно запускать на сопутствующем программном пакете, Система Программирования Моцарт [129]. Программы конструируются в стиле строительных блоков, из которых составляются базовые концепции, позволяющие в свою очередь создавать более сложные концепции. Последние главы содержат немного логических рассуждений, использующихся для определения спецификаций и использование инвариантов для рассуждения о программах с состояниями.

Используемые формализмы

Книга использует единый формализм для представления всех вычислительных моделей и программ, а именно язык Oz и его вычислительная модель. Если более точно, вычислительные модели этой книги - это тщательно отобранное подмножество Oz. Почему мы выбрали Oz? Главная причина - это хорошая поддержка подхода языка ядра. Другая причина - это существование Системы Программирования Mozart.

Обзор вычислительных моделей

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

Больше - это не лучше (или хуже), - это по-другому

Все модели вычислений имеют свои места. И высказывание о том, что модели с большим числом концепций лучше или хуже - неправда. А всё потому, что новая концепция подобна обоюдоострому мечу. Добавление концепции в модель вычисления приводит к возникновению новых форм выражений, при этом некоторые программы упрощаются, но одновременно усложняются рассуждения о программах. Например, добавив явное состояние (изменяемые переменные) в функциональную модель мы можем выразить все вариации объектно-ориентированных техник программирования. Однако, рассуждения об объектно-ориентированных программах становятся более сложными по сравнению с рассуждениями о функциональных программах. Функциональное программирование - это вычисление значений с помощью математических функций. С течением времени ни функции, ни значения не изменяются. Явное состояние - это один из способов моделирования явлений, изменяющихся с течением времени: получается некий контейнер, содержимое которого может обновляться. Большая мощь этой концепции усложняет рассуждения о ней.

Важность совместного использования моделей

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

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

Важным принципом, красной нитью проходящим через всю книгу, является использование концепций, традиционно ассоциируемых с одной моделью, в других более общих моделях с целью получения более выраженного эффекта. Например, концепции лексической области видимости и высокоуровневого программирования, обычно ассоциируемые с функциональным программированием, полезны во всех моделях. Это явление хорошо известно в сообществе функциональных программистов. Функциональные языки уже давно расширяются с помощью явного состояния (например Scheme [38] и Standard ML [126, 192]) а в последнее время и с помощью параллелизма (например, Concurrent ML [158] и Concurrent Haskell [149, 147]).

Ограничения единственной модели

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

Объектно-ориентированные языки поощряют чрезмерное использование состояния и наследования. Объекты, по-умолчанию, обладают состоянием. И хотя такой подход кажется простым и интуитивно понятным, на самом деле программирование усложняется, например, возникают трудности с параллелизмом (смотрите Раздел 8.2). Шаблоны проектирования, которые определяют общую терминологию для определения хороших техник программирования, обычно описываются в терминах наследования [58]. Во многих случаях вполне достаточно использовать более простые высокоуровневые техники программирования (смотрите Раздел 7.4.7). К тому же наследованием часто злоупотребляют. Например, в объектно-ориентированных графических интерфейсах пользователя часто рекомендуется использовать наследования для расширения общих классов виджетов функциональностью, зависящей от приложения (например, компоненты Swing для Java). Это противоречит методу разделения проблемы на составные части.

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

Логические языки, такие как Prolog, поощряют чрезмерное использование синтаксиса дизъюнктов Хорна и запросов. Эти языки определяют все программы как коллекции дизъюнктов Хорна, напоминающие простые логические аксиомы в стиле "if-then". В результате многие алгоритмы оказываются обфусцированными, будучи написанными в таком стиле. К тому же всегда необходимо использовать запросы, даже если они не нужны (смотрите [196]).

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

Обучение по книге

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

Роль в учебной программе по информатике

Рассмотрим дисциплину программирования независимо от любой другой области информатики. По нашему опыту она естественным образом делится на три основные темы:

1. Концепции и техники.

2. Алгоритмы и структуры данных.

3. Архитектура программ и разработка программного обеспечения.

В этой книге дано подробное рассмотрение темы (1) и введение в (2) и (3). В каком порядке должны преподаваться темы? Между темами (1) и (3) существует сильная взаимная зависимость. Опыт показывает что разработка архитектуры программ должна преподаваться как можно раньше, таким образом студенты избегут приобретения плохих привычек. Однако это только одна часть целой истории, поскольку студенты должны знать о концепциях, для того, чтобы суметь выразить их архитектуры. Парнас использует подход, который начинается с темы (3) и применяет императивную вычислительную модель [143]. Поскольку эта книга использует много вычислительных моделей, то мы рекомендуем использовать её для параллельного обучения темам (1) и (3), постепенно вводя новые концепции и принципы проектирования. В программе информатики в Лувенском католическом университете (UCL), мы отводим восемь семестро-часов для каждой темы. Сюда входят лекции и лабораторные занятия. Все три темы вместе дают одну шестую полного учебного курса по информатике для дипломников и инженерных направлений обучения.

Есть ещё один момент, на который мы хотели бы обратить ваше внимание: обучение параллельному программированию. В традиционных учебных планах по информатике параллелизм преподаётся через расширение модели с состоянием, также как Глава 8 расширяет Главу 6. Такой подход по праву считается сложным и трудным для программирования. Существуют другие, более простые формы параллельного программирования. Декларативный параллелизм Главы 4 гораздо проще для программирования и часто может быть использован вместо параллелизма на состояниях (смотрите цитату, которой начинается Глава 4). Потоковому параллелизму, простой форме декларативного параллелизма, - обучают первокурсников в Массачусетском технологическом институте (MIT) и других учебных заведениях. Другой простой форме параллелизма - передаче сообщений между нитями - посвящена Глава 5. Мы полагаем что декларативный параллелизм и параллелизм на передаче сообщений являются частью стандартного учебного плана и должны преподаваться до параллелизма на состояниях.

Курсы

Мы использовали эту книгу в качестве учебного пособия для нескольких курсов начиная с второкурсников и заканчивая выпускниками [200, 199, 157]. В текущей форме эта книга не может быть использована в роли первого курса обучения программированию, но используемые подходы могут быть адаптированы для таких целей.2 Студенты уже должны обладать некоторым опытом программирования (например, практическое введение в программирование и знание простых структур данных, таких как последовательности, наборы, стеки, деревья и графы) и некоторой математической зрелостью (например, начальный курс анализа, дискретной математики или алгебры). Книга содержит много материала, по крайней мере четыре семестра-часов лекций и много лабораторных работ. Вот некоторые курсы в которых может применяться материал из этой книги:

2 Мы будем рады помочь любому кто решит провести такую адаптацию.

Курс по концепция и техникам программирования для студентов бакалавриата. В качестве вводного материала следует использовать Главу 1. Продолжение курса в Главах 2-8. В зависимости от глубины изучения материала, можно сделать акценты на алгоритмах (для обучения алгоритмам вместе с программированием), параллелизму (при желании можно не изучать) или формальным семантикам (для развития интуиции).

Курс по прикладным моделям программирования для студентов бакалавриата. Сюда входят: реляционное программирование (Глава 9), специфичные языки программирования (особенно Erlang, Haskell, Java и Prolog), программирование графического интерфейса пользователя (Глава 10), распределённое программирование (Глава 11) и программирование в ограничениях (Глава 12). Этот курс - это естественное продолжение предыдущего курса.

Курс по параллельному и распределённому программированию для студентов бакалавриата (Главы 4, 5, 8 и 11). Студенты уже должны обладать некоторым опытом в программировании. Курс можно начинать с некоторых частей Глав 2, 3, 6 и 7 для введения в декларативное программирование и программирование с состоянием.

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

На web сайте книги содержится больше информации о курсах, включая слайды и лабораторные задания для некоторых из них. На web сайте есть анимированный интерпретатор, выполненный Кристианом Шальтом (Christian Schulte), показывающий как выполняются языки ядра в семантике абстрактной машины. Книга может быть использована в качестве дополнения к другим курсам:

Часть курса о программировании в ограничениях для студентов бакалавриата (Главы 4, 9 и 12).

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

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

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

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

Программное обеспечение

Полезной особенностью книги является то, что все фрагменты программ можно запустить на программной платформе, Система Программирования Моцарт. Моцарт - это полнофункциональная система программирования промышленного уровня поставляемая с интерактивной, инкрементальной средой разработки и полным набором инструментов. Производится компиляция в эффективный платформно-независимый байткод, запускающийся на многих вариациях Unix, Windows и Mac OS X. Распределённые программы могут запускаться на всех вышеперечисленных системах. На web сайте Моцарт, http://www.mozart-oz.org, содержится наиболее полная информация, включающая в себя бинарные файлы доступные для скачивания, документацию, научные публикации, исходные коды и списки рассылки.

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

Система Моцарт - это результат долгой разработки Консорциума Моцарт, плод совместных неформальных исследований и разработок трёх лабораторий. Разработка началась с 1991 года. Система выпускается со всеми исходными кодами под лицензионным соглашением Open Source. Первый публичный релиз был выпущен в 1995 году. Первый публичный релиз с поддержкой дистрибутива был выпущен в 1999 году. Книга основана на идеальной реализации, наиболее близкой к Моцарт версии 1.3.0, выпущенной в 2003 году. Различия между идеальной реализацией и Моцартом перечислены на Web сайте книги.

История и благодарности

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

Нашим основным исследовательским инструментом и "тестовым полигоном" новых идей была система Моцарт, реализующая язык Oz. Главные архитекторы и разработчики (в алфавитном порядке): Пер Бранд (Per Brand), Торстен Брунклаус (Thorsten Brunklaus), Денис Дачер (Denys Duchier), Донатиен Гролю (Donatien Grolaux), Сеиф Хариди (Seif Haridi), Драгон Ховелка (Dragan Havelka), Мартин Хенз (Martin Henz), Эрик Клинтског (Erik Klintskog), Леиф Корнштадт (Leif Kornstaedt), Михаель Мейль (Michael Mehl), Мартин Мюллер (Martin Müller), Тобиас Мюллер (Tobias Müller), Анна Нейдеруд (Anna Neiderud), Константин Попов (Konstantin Popov), Ральф Шайдхаур (Ralf Scheidhauer), Кристиан Шульт (Christian Schulte), Герт Смолка (Gert Smolka), Питер Ван Рой (Peter Van Roy) и Йорг Вюрц (Jörg Würtz). Важный вклад внесли (в алфавитном порядке): Илиез Алоини (Iliès Alouini), Торстен Брунклаус (Thorsten Brunklaus), Рафаэль Коллет (Raphaёl Collet), Фрей Дрейхаммер (Frej Drejhammer), Самех Эль-Ансари (Sameh El-Ansary), Нилс Франсен (Nils Franzеn), Кевин Глинн (Kevin Glynn), Мартин Хомик (Martin Homik), Саймон Линдблом (Simon Lindblom), Бенджамин Лоренц (Benjamin Lorenz), Валентин Месарос (Valentin Mesaros) и Андреас Саймон (Andreas Simon).

Мы выражаем благодарность следующим исследователям и людям, косвенно оказавшим помощь при работе над книгой: Хассан Аит-Качи (Hassan A ̈ ıt-Kaci), Джо Армстронг (Joe Armstrong), Йоахим Дарчхольц (Joachim Durchholz), Андреас Франк (Andreas Franke), Клэр Гардент (Claire Gardent), Фредрик Холмгрен (Fredrik Holmgren), Сверкер Дженсон (Sverker Janson), Торбьёрн Ладжер (Torbj ̈rn Lager), Эли Милгром (Elie Milgrom), Йохан Монтелиус (Johan o Montelius), Аль-Метуолли Мостафа (Al-Metwally Mostafa), Йоахим Нирен (Joachim Niehren), Лак Онана (Luc Onana), Марк-Антоин Пиерент (Marc-Antoine Parent), Дэйв Парнас (Dave Parnas), Матиас Пайкер (Mathias Picker), Андреас Поделски (Andreas Podelski), Кристоф Понсард (Christophe Ponsard), Махмуд Рафи (Mahmoud Rafea), Юрис Реинфилдс (Juris Reinfelds), Томас Съёланд (Thomas Sj ̈land), Фред Спайссенс (Fred Spiessens), Джо Тёрнер (Joe Turner) и Джин Вандердонкт (Jean Vanderdonckt).

Мы выражаем отдельную благодарность людям, помогавшим нам при работе над материалом этой книги. Мы благодарим Рафаэля Коллета (Raphaёl Collet) за соавторство Главы 12 и 13 и его работу над практической частью LINF1251, курса, преподаваемого в Лувенском католическом университете (UCL). Мы благодарим Донатиена Гролю (Donatien Grolaux) за три обучающих примера Графического Интерфейса Пользователя (GUI) (использованные в Разделах 10.3.2 - 10.3.4). Мы благодарим Кевина Глинна (Kevin Glynn), написавшего введение в Haskell (Раздел 4.8). Мы благодарим Фрея Дрейхаммера (Frej Drejhammer), Самеха Эль-Ансари (Sameh El-Ansary) и Драгона Ховелка (Dragan Havelka) за работу над практической частью DatalogiII, курса, преподаваемого в Королевском Технологическом Институте (KTH). Мы благодарим Кристиана Шульта (Christian Schulte), ответственного за полное переосмысление и переработку следующей редакции DatalogiII и его комментарии по книге. Мы благодарим Али Одси (Ali Ghodsi), Йохана Монтелиуса (Johan o Montelius) и остальных трёх ассистентов за работу над практической частью этой редакции. Мы благодарим Луиса Куесада (Luis Quesada) и Кевина Глинна (Kevin Glynn) за работу над практической частью INGI2131, курса, преподаваемого в Лувенском католическом университете (UCL). Мы благодарим Бруно Картона (Bruno Carton), Рафаэля Коллета (Raphaёl Collet), Кевина Глинна (Kevin Glynn), Донатиена Гролю (Donatien Grolaux), Стефано Гуаланди (Stefano Gualandi), Валентина Месароса (Valentin Mesaros), Аль-Метуолли Мостафу (Al-Metwally Mostafa), Луиса Куесада (Luis Quesada) и Фреда Спайссенса (Fred Spiessens) за корректуру и тестирование примеров программ. И наконец мы благодарны членам Отдела Компьютерных Наук и Инженерии Лувенского католического университета (UCL), Шведского Института Компьютерных Наук и Отдела Микроэлектроники и Информационных Технологий Королевского Технологического Института (KTH). Приносим свои извинения всем, кого мы забыли упомянуть.

Как же нам удалось сохранить результат в простоте работая с такой большой командой разработчиков? Здесь нет никакого чуда, а есть результат чёткого видения цели и аккуратно спроектированной методологии на разработку и полировку которых ушло более десяти лет (итоги смотрите в [196]; кратко резюмируя можно сказать следующее: "архитектура бывает либо простой, либо неправильной"). Примерно в 1990 году некоторые из нас, обладающих сильными знаниями в построении систем и прочной теоретической базой, объединились и инициировали проект ACCLAIM спонсором которого выступил Европейский Союз (1991 - 1994). По некоторым причинам этот проект стал центральным. Среди многих других трудов значимыми вехами стали три работы: Сверкер Дженсон (Sverker Janson) и Сеиф Хариди (Seif Haridi) в 1991 [93] (множественные парадигмы в AKL), Герт Смолка (Gert Smolka) в 1995 [180] (построение абстракций в Oz) и Сеиф Хариди (Seif Haridi) и другие в 1998 [72] (надёжное открытое распределение в Oz). Первая публикация об Oz была опубликована в 1993 году и уже тогда содержала много важных идей [80]. После ACCLAIM две лаборатории продолжили совместную работу над идеями Oz: Programming Systems Lab - Лаборатория Программируемых Систем (DFKI, Universit ̈t des Saarlandes - Саарский Университет и Collaborative Research Center - Совместный Научно-Исследовательский Центр SFB 378) в Саарбрюкене, Германия и Intelligent Systems Laboratory - Лаборатория Интеллектуальных Систем (Swedish Institute of Computer Science - Шведский Институт Компьютерных Наук) в Стокгольме, Швеция.

Первоначально язык Oz был разработан Гертом Смолка (Gert Smolka) в Programming Systems Lab [79, 173, 179, 81, 180, 74, 172]. Хорошая архитектура языка и высокое качество его реализации были созданы во многом под руководством Герта Смолка (Gert Smolka) и высоким профессионализмом лаборатории в области построения систем. Среди разработчиков мы должны отметить Кристиана Шульта (Christian Schulte) и его роль в общей координации разработки, Дениса Дачера (Denys Duchier) за его активную поддержку пользователей и Пера Бранда (Per Brand) за его роль в координировании разработки реализации распределённости. В 1996 году Германские и Шведские лаборатории присоединились к Отделу Компьютерных Наук и Инженерии (Department of Computing Science and Engineering, Лувенского католического университета - UCL), в Лувен-ла-Нёв, Бельгия, когда первый автор переехал в Лувен-ла-Нёв. Вместе три лаборатории сформировали Консорциум Моцарт (Mozart Consortium) с нейтральным Web сайтом http://www.mozart-oz.org, таким образом проводимая работа не привязана к одному институту.

При создании книги использовался LaTeX 2e, flex, xfig, xv, vi/vim, emacs и Mozart. Изначально использовался компьютер Dell Latitude с Red Hat Linux и KDE, а затем Apple Macintosh PowerBook G4 с Mac OS X и X11. Первый автор благодарит Валлонский регион Бельгии за их щедрую поддержку во время работы над Oz/Mozart в Лувенском католическом университете в проекте PIRATES.

Что отсутствует

Есть две главные темы, отсутствующие в книге:

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

Специализированные техники программирования. Множество техник программирования слишком обширно для их охвата в рамках одной книги. В дополнение к общим техникам, описанным в этой книге, каждая предметная область какой-либо проблемы имеет свою особую технику. В этой книге охвачены не все техники; попытка охватить все техники приведёт к удвоению или к утроению размера. Для восполнения этого недостатка мы отошлём читателя к некоторым хорошим книгам, в которых рассматриваются предметные области некоторых проблем: техники искусственного интеллекта [160, 136], алгоритмов [41], объектно-ориентированных шаблонов программирования [58], мультиагентное программирование [205], базы данных [42] и численные методы [153].

Последние комментарии

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

Концепции, Техники и Модели Компьютерного Программирования
Отдел Компьютерных Наук и Инженерии
Лувенский католический университет
B-1348 Лувен-Ла-Нёв, Бельгия

И напоследок мы хотели бы выразить благодарность нашим семьям и друзьям за их поддержку и ободрение на протяжении более трёх лет создания книги. Сеиф Хариди (Seif Haridi) выражает особую благодарность своим родителям Али (Ali) и Амине (Amina) и своей семье Еве (Eeva), Ребекке (Rebecca) и Александру (Alexander). Питер Ван Рой (Peter Van Roy) выражает особую благодарность своим родителям Франсу (Frans) и Хендрике (Hendrika) и своей семье Мари-Терезе (Marie-Th´er`ese), Йохану (Johan) и Люсиль (Lucile).

Лувен-Ла-Нёв, Бельгия
Чиста, Швеция
Июнь 2003
Питер Ван Рой (Peter Van Roy)
Сеиф Хариди (Seif Haridi)

Запуск экземпляров программ

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

Систему Моцарт можно безвозмездно скачать с Web сайта Консорциума Моцарт http://www.mozart-oz.org. Существуют выпуски для различных версий Windows, Unix и Mac OS X.

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

Новые переменные в интерактивных примерах должны объявляться с помощью оператора declare. Примеры в Главе 1 показывают как производить это действие. Если вы забудете выполнить это действие, то в результате можете получить различные странные ошибки, в случае если уже существуют старые версии переменных. Начиная с Главы 2 и в последующих главах, оператор declare будет опускаться в тех случаях, когда очевидно присутствие новых переменных. В этом случае для запуска примеров нужно добавлять определение новой переменной.

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

Существует несколько различий между идеальной реализацией, применяемой в этой книге и системой Моцарт. Эти различия описаны на Web сайте книги.

Переведено на Нотабеноиде
http://notabenoid.org/book/49638/205197

Переводчики: Charlz_Klug, victor8632