воскресенье, 19 августа 2007 г.

Что необходимо знать, прежде чем спорить о системах типов


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

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

Классификация систем типов

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

Сильная и слабая типизация

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

В связи с этим, я согласен с такими основными определениями сильной и слабой типизации, по крайней мере, в общем случае:
  • Сильная типизация: система типов, которая мне нравится, и я чувствую себя комфортно, используя ее.
  • Слабая типизация: система типов, которая доставляет мне беспокойство, и, используя ее, я чувствую себя несколько неуверенно.
А как быть, когда выражения используются в более ограниченном смысле? Сильная типизация, в зависимости от автора и контекста разговора может означать «статическая» или “чистая” обе описаны ниже.

Статическая и динамическая типизация

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

Статическая система типов - это механизм, с помощью которого компилятор анализирует исходный код и присваивает синтаксическим единицам метки (так называемые "типы"), а затем используют их для того, чтобы что-то сделать вывод о поведении программы. Динамическая система типов представляет собой механизм, на основании которого компилятор генерирует код для отслеживания вида данных (иначе «типа») используемого в программе. Использование одного и то же термина "тип" в каждой из этих двух систем, конечно, не совсем совпадающее, но, несмотря на это, так будет лучше понять его исторический или обобщенный смысл. Огромную путаницу вызывают попытки определить «тип», как понятие, означающее одно и то же для обеих систем. Его нет. Наилучшим способом решения данной проблемы является осознание некоторых фактов:
  • Значительную часть времени программисты пытаются решить ту же проблему, используя и статическую, и динамическую типизацию.
  • Тем не менее, статическая типизация не ограничена проблемами, которые решены в динамической типизации.
  • Динамическая типизация не ограничена проблемами, которые можно решить, используя статическую типизацию.
  • По своей сути эти две системы - не одно и то же в принципе
Исследование второго из этих четырех простых фактов популярное занятие в некоторых кругах. Совсем недавно я прочитал этот набор заметок и натолкнулся на запутанный комментарий «система типов определила зацикливание». Забавно, что с теоретической точки зрения, решение задач зацикливания – это одно их простейших возможных вещей, которые вы можете сделать со статической типизацией! Легко-типизированное (simply-typed) лямбда-исчисление, на котором в принципе основаны все остальные системы типов, доказывает, что программа завершаема за конечный промежуток времени. Действительно, более интересным является вопрос, как можно расширить систему типов, способную описать незавершаемую программу! Несмотря на это, нахождения зацикливаний не является классом задач, которые, по мнению большинства людей, относятся к системам типов. Данный вопрос недоказуем в динамической типизации (это называется проблемой останова (halting problem), вы, вероятно, слышали об этом). Но нет ничего специального для статической типизации. Почему? Потому что она совершенно непохожая на динамическую типизацию.

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

Другие Виды

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

  • Чистая типизация. Чистая система типов, это такая, которая обеспечивает определенные виды гарантий. Это четко определенная концепция, относящаяся к статической типизации, которая имеет доказательства и все необходимые навороты. Многие современные системы являются чистыми. Но более старые языки, такие как C часто не являются чистыми системами; системы типов таких языков спроектированы только для предоставления некоторых предостережений в общем случае. Данное понятие можно применить и к динамическим системам, но точное определение там может быть изменчивым в зависимости от их употребления.
  • Явная/неявная типизация. Когда используются эти определения, они определяют меру, согласно которой компилятор выводит статические типы частей программы. Все языки программирования имеют определенный уровень выводимости типов. У некоторых он больше, чем у других. ML и Haskell используют неявную типизацию из-за чего объявление типов не требуется (или почти не требуется, в зависимости от языка и используемых расширений). Java и Ada используют явную типизацию и требуют объявление типа операндов. Все из вышеперечисленных языков (к примеру, по сравнению с C и C++) имеют сильную статическую типизацию.
  • Лямбда-исчисление. Разнообразные вариации между статическими системами типов обобщены в абстракцию, называемую «лямбда-исчислением». Ее определение выходит за пределы данной статьи, но по существу, она определяет - поддерживает ли система типов некоторые особенности: параметризированные типы, зависимые типы, или операторы типов. Обратитесь сюда за дополнительной информацией.
  • Структурная/Номинальная типизация. Этот вид типизации в основном используется применительно статической типизации с подтипами. В структурной типизации допущение о типе осуществляется всякий раз, когда это действительно возможно. К примеру, запись с полями X, Y, и Z может автоматически приводиться к одному из подтипов полей X и Y. В номинальной типизации нет таких допущений, пока оно не будет где-нибудь объявлено.
  • Утиная типизация. Этот термин стал популярным недавно. Он базируется на динамическом аналоге структурной типизации и означает, что прежде чем делать допущение о том, является ли корректным тип некоторого объекта, используемого в процессе, система выполнения просто проверяет, поддерживает ли этот объект все операции допустимые для него. Данные операции могут иметь различную реализацию, для разных типов.

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

Заблуждения о статической и динамической типизации

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

Заблуждение: Статическая типизация подразумевает объявление типа

Наиболее очевидным фактом относительно систем типов Java, C, C++, Pascal, и многих других распространенных «промышленных» языков является не то, что они статически типизированные, а то, что они явно типизированные. Другими словами, они требуют объявления типов. (В мире менее явно типизированных языков, где такие объявления опциональны, они часто иначе называются языками с аннотацией типов. Вы также можете найти использование мной этого термина.) Это опять заставляет некоторых людей нервничать, и программисты по этой причине часто отказываются от использования статически типизированных языков.

Это не имеет ничего общего со статической типизацией. Первые статически типизированные языки были явно типизированными по необходимости. Однако алгоритмы вывода типов – техника определения типов переменных, по их использованию в исходном коде – существовали давно. Язык ML, который использует их сегодня, является одним из числа старейших. Haskell, замечательно использующий данный подход, недавно отметил свое пятнадцатилетие. Даже C# принимает подобную идею, что вызовет много удивления (и несомненно вызовет массу недовольств относительно его «слаботипизированности» - см. определение выше). Если кому-то не нравится определение типов, то они более состоятельны в описании, отличном от явной типизации.

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

Заблуждение: Динамически типизированные языки являются слабо типизированными.

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

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

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

В порядке комментария и конечно для продолжения дискуссии: нет возможности сделать исчерпывающее блочное тестирование на Haskell, как бы его можно было сделать на Ruby или Smalltalk. Это попросту пустая трата времени. Интересно отметить, что разработка через тестирование (Test-Driven Delevopment) исходит от людей, предпочитающих динамически типизированные языки.

Заблуждение: Статическая типизация подразумевает использование подхода «дизайн наперёд» (BDUF) или водопадную методику.

Некоторые статически типизированные языки спроектированы с учетом идеи так называемого хорошего процесса разработки. То есть они часто требуют или всячески способствуют необходимости детального описания интерфейса в одном месте, и только после этого можно писать исходный код. Это становится затруднительным, в случае, когда требуется разрабатывать изменяемый код или когда необходимо исследовать некоторую идею. Это иного означает, что для изменения функциональности требуется делать изменения в различных местах. Наихудшая форма подобного явления и того что мне известно (хотя отчасти это сделано скорее не про идеологическим, а прагматическим соображениям) это заголовочные файлы C и С++. У Pascal есть подобная проблема, требующая объявления всех переменных в отдельной группе в заголовке файла. Хотя и некоторые другие языки также навязывают подобное разделение, многие избавлены от такой необходимости.

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

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

Подобное заблуждение находит отражение в различных выражениях: «Мне нравится заниматься исследованием в программировании» - это популярная фраза. То есть, взяв во внимание существующие мнения, будто статически типизированные языки обязывают сначала написать весь код, и поэтому они не так хороши для проведения своего рода экспериментов и изучения их результатов. Основные инструменты для исследования программирования имеют в своем распоряжении интерактивную среду REPL (read-eval-print loop), которые в основном являются интерпретаторами и принимают строку выражения, обрабатывают ее, и выводят результат операции. Подобные инструменты достаточно полезны, и они существуют для многих языков, как статических, так и динамических. Их нет для Java, C, или C++, и в связи с этим появился неприятный миф, что они могут быть только у динамических языков. Динамически типизированные языки, возможно, обладают некоторыми преимуществами в этой области (бесспорно, ряд преимуществ у них разумеется, есть), но это в первую очередь определяется наличием подобных инструментов для конкретного языка а не спецификой системы типов.

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

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

Можно обсуждать причины таких заблуждений, и при этом иметь в данном вопросе веские аргументы. К примеру, одна причина заключается в том, что средний уровень программистов, знакомых с Ruby выше программистов, которые знакомы с Java. Еще причиной может быть то, что C++ и Java имеют относительно бедную систему типов. Еще одна причина – это тестирование. Как упоминалось выше, блочное тестирование пришло с динамических языков. Оно имеет некоторые недостатки, по сравнению с гарантиями, предоставляемыми статическими типами, но также имеет и ряд преимуществ; системы статических типов не могут обеспечить проверку многих свойств исходного кода, которые доступные в блочном тестировании. Игнорируя этот факт, общаясь с кем-нибудь, кто действительно знаком с Ruby, вы также можете оказаться проигнорированными.

Заблуждение: Статическая типизация предполагает больший объем кода.

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

Это заявление может выглядеть удивительным, но так оно и есть. Типы несут информацию, и эта информация может использоваться в дальнейшем, предотвращая необходимость дублирования кода. Это нельзя показать на простых примерах, но действительно изумительное решение существует в стандартной библиотеке Haskell в модуле Data.Map. Этот модуль реализует сбалансированное бинарное дерево поиска и содержит функцию, подобную этой:

lookup :: (Monad m, Ord k) => k -> Map k a -> m a

Это магическая функция. Она позволяет находить нечто в Map и получать результат. Достаточно просто, но здесь есть ньюанс, что делать, когда результата нет? Как правило, результатом выполнения функции в таком случае может быть специальное значение “nothing” (пусто), или прерывание текущего вычисления и инициирование обработчика ошибок, или же завершение выполнения всей программы. Функция, описанная выше делает все из перечисленного! Ниже представлен код, описывающий сравнение результата со специальным значением “nothing”:

case (lookup bobBarker employees) of
Nothing -> hire bobBarker
Just salary -> pay bobBarker salary


Как Haskell определяет, что вариант возвращения Nothing для дальнейших действий для меня более предпочтителен генерации прочих видов ошибки, когда запрашиваемое значение отсутствует? Это происходит по причине того, что я указал сравнение результата со значением Nothing! Если бы я не написал такого непосредственного кода по обработке подобной ситуации, но описал бы вместо этого где-то обработку всех трех вариантов обработки ошибок на предмет отсутствия необходимого значения, мне пришлось бы последовательно реализовывать семь или восемь дополнительных проверок и использовать в вычислениях результат без наличия проверок на значение Nothing. Это исчерпывающее решение возможных вариантов обработки подобной ситуации является серьезной полемикой «исключение или возвращаемое значение» при возникновении ошибки во многих других языках. Но она не имеет однозначного ответа, как лучше поступать. Возвращаемые значение – это хорошо, когда вы сразу проверяете его, исключения хороши, когда вы их обрабатываете на верхних уровнях выполнения программы. Данный же код, просто делает так, как вам удобно обрабатывать подобную ситуацию.

Детали данного примера специфичны для Haskell, но подобные примеры могут быть сконструированы во многих статически типизированных языках. Нет оснований полагать, что код на ML или Haskell более длинный, чем эквивалент на Python или Ruby. Следует запомнить это, прежде чем заявлять, что статически типизированные языки требуют большего объема кода. Это неочевидно, и у меня по этому поводу большие сомнения.

Преимущества статической типизации.

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

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

Производительность

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

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

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

Документирование

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

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

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

Инструменты и анализ

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

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

«Любой дурак может написать код, который понятен компьютеру. Хороший же программист пишет код, который понятен человеку.»

Я не согласен с Мартином, но у нас с ним различный смысл слова понимание. Понимание компьютером кода шаг за шагом – это несложно. Способность компьютера проанализировать код и решить более сложные вопросы, чем просто построчное понимание им кода, это совершенно другое, и это очень сложно.

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

Корректность

В конечно счете, оправданием статической типизации является возврат к написанию корректного кода. Корректность, естественно, это когда программа делает то, «что вы хотите».

Это действительно трудноразрешимая проблема, если разрешимая вообще. У теории вычисления есть подобные наработки, называемые Теоремой Райса (Rice's Theorem), которая гласит следующее: «Если взять произвольную программу, написанную на языке программирования общего назначения, то невозможно написать для нее компьютерную программу, позволяющую определить выходные данные этой программы». Если я буду обучать студентов программированию и дам им задание написать «Hello World», я не смогу воспользоваться другой программой для определения правильно ли работает написанное студентом решение. Найдутся некоторые программы, для которых ответ прост; если программа никогда не использует операции ввода/вывода, то значит ответ отрицательный. Если программа состоит из одного выражения печатающего результат, также несложно определить – решено задание или нет. Однако, могут быть и более сложные программы для которых определить корректность результата невозможно. Несущественный, но важный технический момент: нельзя запустить программу и дождаться, пока она выполнится, так как программа может не завершиться вовсе! Это справедливо для любого высказывания о программе, включая такие интересные, как «это программа имеет завершение?» или «эта программа нарушает мои правила безопасности?»

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

  • Тестирование: устанавливает верхние границы корректности
  • Доказательство: устанавливает нижние границы корректности

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

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

А что с динамической типизацией?

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

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

Динамические языки для определения корректности используют тестирование. Напомню, что тестирование делает возможным только лишь определение верхних границ корректности. Дейкстра сказал об этом наилучшим образом: “Тестирование программы может использоваться для определения наличия ошибок, но не для проверки на их отсутствие”. Полагаю, что если кто-либо не сможет определить наличие ошибок, то вполне вероятно, что их нет. Если кто то не сможет доказать наличия лучшей верхней границы корректности, то вероятно действительно корректность такой программы 100%. Естественно, не стоит забывать о возможной корреляции этой позиции.

Что такое тип?

Это хорошая идея, сделать шаг назад и задаться фундаментальным вопросом: что такое тип? Я уже упомянул, что с моей точки зрения есть два ответа. Один для статической типизации, а другой - для динамической. Я рассмотрю вопрос для статических типов.

Рискованно отвечать на этот вопрос слишком быстро. Это опасно потому, что мы рискуем не учесть какую-либо сущность, как тип, и пропустить природу ее типа, потому что мы никогда не рассматривали его в подобной роли. Поэтому определение типа, в конечном счете, я постараюсь привести максимально широко.

Проблемы с общими определениями

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

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

Давайте посмотрим на другие вещи, которые мы часто хотим знать: помещает ли наше веб-проложение данные клиента в SQL-запросы перед их отправклой? Если это то, что мы хотим знать, то почему бы не назвать это типом. Данная статья Тома Мортела построена как раз на таком подходе, и использует систему типов Haskell. Таким образом, это выглядит, как обоснованное определение “типа”: что-то, о чем мы хотим знать.

Система типов

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

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

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

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

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

Пример к данному определению выглядит примерно так. Получено выражение 5 + 3 механизм проверки типов (type checker) может взять первый операнд ‘5’ и прийти к выводу, что результатом операции будет целое число. Также он может взять второй операнд ‘3’ и опять таки прийти к такому же выводу. Также он может взять оператор ‘+’ и сделать заключение, что данный оператор применим для двух целых чисел, и результат его выполнения так же целое число. Так доказывается отсутствие определенного поведения программы (таких, как добавление целого числа к строке) вызовом базовых элементов синтаксиса программы.

Примеры необычных систем типов

Выше были довольно скучные примеры, больше походившие на ловушки: размышления о типе, имеющее такое же значение как в случае динамической типизации. Ниже представлено несколько более интересных проблем, решаемых с помощью статической типизации.
  • http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Использование типов для гарантии корректности вида данных получаемых из реляционной базы данных. Используя систему типов, компилятор не в состоянии понять, как работать с концепциями подобных функциональных зависимостей и нормальных форм и осуществляет статическое доказательство уровней нормализации.
  • http://www.cs.bu.edu/~hwxi/academic/papers/pldi98.pdf Использование расширения для системы типов ML, с целью доказательства, что массивы никогда не получат доступ за пределами своих границ. Это необычно тяжелая проблема для решения ее с помощью языков, у которых нет подобной реализации на уровне системы типов.
  • http://www.cis.upenn.edu/~stevez/papers/LZ06a.pdf Замечательная статья. Данный пример использует систему типов Haskell для возможности определения политики безопасности программы Haskell и доказывая после этого что программа должным образом реализует эту безопасность. Если программист делает ошибку безопасности, компилятор скорее выразит свое недовольство, чем сделает возможным потенциальную ошибку безопасности в системе.
  • http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Только в целях размышлений о системах типов, решение простой проблемы, немного кода на Haskell использующего систему типов для доказательства двух основных теорем о простом типизированном лямбда-исчислении, ветви теории вычислений.

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

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

Истинное значение типа

И все же, что такое тип? Единственно верное определение: тип это метка, используемая системой типов для доказательства некоторых свойств поведения программы. Если механизм проверки типов в состоянии назначить типы для всей программы - он получит доказательство корректности программы; иначе он потерпит неудачу и укажет на причину этого. Это и есть определение, но он не говорит нам ничего фундаментально важного. Некоторые дальнейшие исследования приводит нас к пониманию фундаментальных ньюансов, связанных с использованием механизма проверки статических типов.

Если вы были внимательны, то несколько разделов назад могли обратить внимание на теорему Райса, которая гласит, что мы не можем определить выходных данных программы. Статически типизированные системы доказывают всего лишь корректность написанного кода, и получается, что если смотреть на них через призму теоремы Райса, то получается, что с помощью таких систем мы не можем осуществить автоматизированное доказательство интересующих нас моментов. Если бы это было так, то тогда это был бы приличный камень в огород статически типизированных систем. Но, конечно же, это не так, хотя и не так уж далеко от истины. Теорема Райса утверждает, что мы не можем определить ничего. Это не говорит, что мы не можем ничего доказать. Это важное различие!

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

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

Развитие дискуссии

Последний параграф резюмирует интересные части дискуссий между статической и динамической типизацией. Поле боя ограничены восемью вопросами, по четыре с каждой стороны:
  1. Для каких интересующих нас моментов мы можем использовать статическую систему типов?
  2. Насколько близко мы можем подойти в таких системах типов к недостижимому идеалу, никогда не отвергающему корректную программу?
  3. Насколько просто это может быть сделано для программы на языке с подобной статически типизированной системой?
  4. Каковы затраты, связанные со случайным отклонением корректной компьютерной программы?
  5. Для каких интересующих нас моментов мы можем реализовать набор тестов с помощью динамической типизации?
  6. Насколько близко мы можем подойти в таких наборах тестов к недостижимому идеалу, никогда не принимающему неисправную программу?
  7. Насколько просто это может быть сделано для того, что бы написать и выполнить набор тестов для программы?
  8. Каковы затраты связанные со случайным принятием некорректной компьютерной программы?

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

вторник, 22 мая 2007 г.

Эффективные коллекции

Несколько дней назад у меня появилась необходимость максимально эффективного доступа к элементам, которые хранятся в объекте-хранилище. Все элементы имеют одного предка, определяющего их общие признаки и идентифицирующий каждый элемент уникальным целочисленным идентификатором. Каждый тип элементов хранится в отдельной коллекции. Для хранения элементов в объекте-хранилище я использовал обобщенную коллекцию List, по одной на каждый тип. Мне был необходим метод, позволявший получать элементы из хранилища по типу и идентификатору. Этот метод не должен быть обобщенным, так как должен вызывается через делегат из метода, который имеет только лишь Type запрашиваемого элемента. Таким образом, эффективность применения List сводилась на нет, процесс получения элемента работал очень медленно. На одном из форумов RSDN мне подсказали решение основанное на KeyedCollection. Оно оказалось настолько эффективным для моей задачи, что я был просто поражен. Результаты сравнения решений с использованием List и KeyedCollection, которые приведены здесь, показывают превосходство второго способа более чем в 500 раз. Думаю, это больше чем хорошая мотивация, что бы присмотреться к данному решению. Кстати, в процессе тестирования я помимо этих двух вариантов добавил вариант с использованием ArrayList, для того что бы показать что использование List ничем не отличается по эффективности от использования необобщенной коллекции. Итак, приступим к описанию всех решений.

Иерархия элементов для тестирования эффективности:


public class base1
{
public int i;
public base1(int iq) { i = iq; }
};

public class der1 : base1
{
public string s1;
public der1(int iq, string s) : base(iq) { s1 = s; }
};

public class der2 : base1
{
public string s2;
public der2(int iq, string s) : base(iq) { s2 = s; }
};

Абстрактный класс, описывающий произвольный объект-хранилище для хранения элементов и выполнения требуемых для данной задачи операций:


public abstract class BaseRep
{
// инициализация репозитория
public abstract void Init(Type[] ar);

// добавление элемента
public abstract void Add<T>(T item) where T : base1;

// выборка элемента
public abstract base1 GetCollectionItem(Type collectionType,
int input);

// используется для вывода названия типа
// репозитория в процессе выполнения теста
public string GetName() { return this.GetType().Name; }
}

Реализация объекта-хранилища с использованием KeyedCollection:


// интерфейс для быстрого доступа к элементам хранилища
public interface IIndexable<TKey, TItem>
{
TItem this[TKey key] { get; }
}

// реализация коллекции, используемой для хранения элементов
public class myCollection<T> : KeyedCollection<int, T>,
IIndexable<int, base1> where T : base1
{
// переопределение абстрактного метода KeyedCollection
protected override int GetKeyForItem(T item)
{
return item.i;
}

// реализация метода интерфейса
base1 IIndexable<int, base1>.this[int key]
{
get
{
base1 value = null;
if (Contains(key))
value = this[key];
return value;
}
}
}

// реализация объекта-хранилища
public class keyedRep : BaseRep
{
private Dictionary<Type, IIndexable<int, base1>> array =
new Dictionary<Type, IIndexable<int, base1>>();

public override void Init(Type[] ar)
{
foreach (Type type in ar)
{
Type genType = typeof(myCollection<>).MakeGenericType(type);
array.Add(type, (IIndexable<int,
base1>)Activator.CreateInstance(genType));
}
}

public override void Add<T>(T item)
{
((myCollection<T>)array[typeof(T)]).Add(item);
}

public override base1 GetCollectionItem(Type collectionType,
int input)
{
return array[collectionType][input];
}
};

Более простая реализация объекта-хранилища с использованием List:


public class listRep : BaseRep
{
Dictionary<Type, object> array = new Dictionary<Type, object>();

public override void Init(Type[] ar)
{
foreach (Type type in ar)
{
Type genType = typeof(List<>).MakeGenericType(new Type[] { type });
array.Add(type, Activator.CreateInstance(genType));
}
}

public override void Add<T>(T item)
{
((List<T>)array[typeof(T)]).Add(item);
}

public override base1 GetCollectionItem(Type collectionType, int input)
{
if (array.ContainsKey(collectionType))
{
IEnumerable collection = (IEnumerable)array[collectionType];
foreach (base1 item in collection)
{
if (item.i == input)
return item;
}
}
return null;
}
}

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


public class arrayListRep : BaseRep
{
Dictionary<Type, ArrayList> array = new Dictionary<Type, ArrayList>();

public override void Init(Type[] ar)
{
foreach (Type type in ar)
{
array.Add(type, (ArrayList)Activator.CreateInstance(typeof(ArrayList)));
}
}

public override void Add<T>(T item)
{
((ArrayList)array[typeof(T)]).Add(item);
}

public override base1 GetCollectionItem(Type collectionType, int input)
{
if (array.ContainsKey(collectionType))
{
ArrayList collection = array[collectionType];
foreach (base1 item in collection)
{
if (item.i == input)
return item;
}
}
return null;
}
}

И наконец, метод осуществляющий тестирование всех трех вариантов:


private static void Test()
{
// количество элементов каждого типа и количество итераций при выборке
int iterCount = 10000;

// типы элементов, которые мы будем использовать
Type[] types = new Type[] { typeof(der1), typeof(der2) };

// формируем списки каждого типа элементов,
// которые позже будем использовать при добавлении в репозиторий
List<der1> d1 = new List<der1>();
List<der2> d2 = new List<der2>();
for (int i = 0; i < iterCount; i++)
{
d1.Add(new der1(i, "test"));
d2.Add(new der2(i, "test"));
}

// эмуляция произвольного доступа, определяем индексы элементов
// которые будем получать в процессе выборки
//(выборка должна быть одинаковая для всех, что бы никому не было обидно;))
List<int> accessInd = new List<int>();
Random rnd = new Random();
for (int i = 0; i < iterCount; i++)
{
accessInd.Add(rnd.Next(iterCount - 1));
}

//формируем список репозиториев для тестирования
BaseRep[] reps = { new listRep(), new arrayListRep(), new keyedRep() };

//
Stopwatch sw = new Stopwatch();

// для каждого репозитория проводим добавление и выборку
// с подсчетом затраченного времени на каждую операцию
foreach (BaseRep rep in reps)
{
// инициализация
rep.Init(types);

sw.Start();

// заполнение
for (int i = 0; i < iterCount; i++)
{
rep.Add(d1[i]);
rep.Add(d2[i]);
}
sw.Stop();

// результаты
System.Console.WriteLine("{0} adding: {1} ticks or {2} ms",
rep.GetName(), sw.ElapsedTicks, sw.ElapsedMilliseconds);
sw.Reset();

sw.Start();

// выборка
for (int i = 0; i < accessInd.Count; i++)
{
// попеременно запрашиваем элементы различных типов
base1 b = rep.GetCollectionItem(types[i % 2], accessInd[i]);
}
sw.Stop();

// результаты
System.Console.WriteLine("{0} reading: {1} ticks or {2} ms",
rep.GetName(), sw.ElapsedTicks, sw.ElapsedMilliseconds);
sw.Reset();

System.Console.WriteLine(Environment.NewLine);
}
}

Таким образом, вот какие я получил результаты на своем компьютере:

Результаты (MSVS2k5, Release, WinXP, Athlon64 3000+):

listRep adding: 25441 ticks or 7 ms
listRep reading: 8778434 ticks or 2452 ms


arrayListRep adding: 24542 ticks or 6 ms
arrayListRep reading: 9088774 ticks or 2539 ms


keyedRep adding: 68186 ticks or 19 ms
keyedRep reading: 19248 ticks or 5 ms


Решения с List и ArrayList показили себя практически одинаково малоэффективно.
Однако, добавление в такие коллекции осуществляется в 3 раза быстрее, чем в случае с KeyedCollection. Оно и понятно — в линейных коллекциях добавление не требует каких-либо чрезмерных усилий и дополнительных затрат.
А вот резульаты произвольной выборки — это что-то... 5 мс против ~2500 мс, то есть практически в 500 раз KeyedCollection работает эффективней.
В виду того на практике в большинстве случаев выборка или получение элементов из хранилища используется гораздо чаще, чем операция добавления (удаления, изменения), то фактом более медленного добавления в принципе можно пренебречь. Таким образом, если у Вас возникнет ситуация похожая на ту, которая опианная здесь, Вы уже знаете что делать

суббота, 12 мая 2007 г.

Введение в функциональные языки программирования

Большинство языков программирования, повсеместно используемых для разработки программного обеспечения, использует императивную парадигму программирования. Это значит, что процесс программирования представляет собой перечень инструкций или команд, которые изменяют состояние программы. Императивный подход имеет много общего с естественными языками, поэтому он достаточно понятен для понимания, и языки программирования базирующиеся на нем легче поддаются изучению.
В противовес императивной парадигме как правило противопоставляют декларативный подход. Суть подхода состоит в том, что программа представляет собой не набор команд, а описание действий, которое не предполагает такой строгой последовательности и ориентировано прежде всего на описание желаемого результата. Такой подход существенно проще и прозрачнее формализуется математическими средствами и, как следствие требует для понимания гораздо более высокую математическую подготовку. Одним из путей развития декларативной парадигмы стал функциональный подход к программированию.
Функциональный подход базируется на стиле программирования, при использовании которого в программах описывается способ решения поставленной задачи посредством вычисления значений функций с одним или несколькими аргументами, которые также можно рассматривать как функции. Любая функция представляет собой конструкцию языка, которая описывает правила преобразования своего аргумента в результат. Функцию, принимающую в качестве аргументов другие функции или возвращающую другую функцию в качестве результата, часто называют функцией высшего порядка. С теоретической точки зрения любая функция при функциональном подходе является функцией высшего порядка.
Благодаря тому что выражения в функциональном программировании очень схожи с выражениями в естественной математике, программы написанные на функциональных языках в большинстве случаев короче и нагляднее, чем те же самые программы на традиционных императивных языках. Кроме того, данная особенность достигается еще и посредством того, что функциональные языки являются более абстрактными по отношению к особенностям вычислительной техники, и для решения задачи используют подходы максимально приближенные к математическим вычислениям. Функциональные программы не содержат операторов присваивания, а переменные, получив однажды значение, никогда не изменяются. Именно по этой причине все операции с памятью выполняются автоматически.
Как правило каждому выражению (константа, переменная, функция) функционального языка поставлен в соответствие тот или иной тип. Такая система типизации в языках функционального программирования называется системой сильной типизации, а сам язык - языком с сильной типизацией. При этом многие функциональные языки имеют механизм выводимости типов (type inference), который позволяет определять типы констант, выражений и функций из контекста. То есть, если не задан тип переменной, входящей в состав выражения, то он может быть автоматически выведен на основании типов других переменных, которые входят в состав данного выражения. По этой причине типы используемых функций в некоторых случаях можно не указывать. Механизм выводимости типов не является исключительной особенностью функциональных языков, он так же существует и в некоторых современных императивных языках, однако впервые подобная возможность была реализована именно в функциональных языках.
В чистом функциональном программировании оператор присваивания отсутствует, а используемые переменные, являются просто псевдонимами для выражений. Именно по этой причине они не могут быть изменены или уничтожены. Благодаря этой особенности все функции свободны от побочных эффектов. Кроме того независимость и произвольный порядок выполнения функций делает функциональный подход удобным для параллельных вычислений.
Еще одной особенностью чистых функциональных языков является наличие механизма отложенного вычисления. В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Такой поход иначе известен как «ленивые» вычисления, и у некоторых функциональных языков присутствует даже специальное ключевое слово lazy, которое описывает выражение, вычисляемое по необходимости. Следует отметить что механизм отложенного вычисления реализован не во всех функциональных языках.
Программы реализованные с помощью функциональных языков как правило работают медленнее чем аналоги, использующие императивный подход, однако они могут решать более абстрактные задачи с меньшими трудозатратами и являются весьма эффективными при реализации символьной обработки и анализе текстов. Помимо этого функциональный подход дает возможность прозрачного моделирования текста программ математическими средствами поэтому он активно используется в академических целях.
Впервые функциональный подход подход был воплощен в языке LISP. Основной задачей данного языка является символьная обработка данных. В своей основе LISP - это язык списков. Все в LISP, от данных до кода приложения, является списком. Хотя LISP не является строго функциональным языком, так как существующие в нем императивные свойства лишают его права так называться в строгом смысле слова, многие идиомы и функциональные возможности LISP имеют сильный функциональный привкус. Этот язык дал развитие большому количеству различных диалектов, наиболее распространенными из которых являются Common Lisp и Scheme, которые очень активно используются в наши дни.
Дальнейшим развитием функционального программирования стало появление семейства языков ML (Meta Language). Этот язык был задуман как инструмент для научных и образовательных учреждений, предназначенный для построения формальных доказательств в системе логики для вычислимых функций. Однако возможность практического применения языка для промышленных целей, к примеру для символьных вычислений спровоцировало пересмотр его концепции, что явилось причиной появления различных диалектов, таких как Standard ML, CaML Light и Objective CaML. К сожалению данное семейство также не является чисто функциональным.
Первым чистым функциональным языком стал язык SASL (сокр. от St. Andrews Static Language) в далеком 1972 году, который позже перерос в KRC (Kent Recursive Calculator). В свою очередь KRC дал развитие новому языку – Miranda, который используется и в наше время. Язык Miranda разрабатывался в качестве стандартного функционального языка. Сейчас он преподаётся во многих университетах, и так же как и ML и LISP оказал большое влияние на развитие функционального подхода.
В наше время к чистым функциональным языкам программирования, которые получили развитие и используются не только в академических целях можно отнести Haskell и Clean. Haskell является наиболее распространённым чисто функциональным языком программирования. Последний стандарт языка, по праву стал стандартом функционального программирования — Haskell-98. Язык Clean намного меньше распространен, чем Haskell, однако его синтаксис несильно отличается от синтаксиса Haskell. Главное отличие этих языков заключается в способе вычислений выражений.
Помимо всего этого функциональный подход получил огромное развитие в мультипарадигменных языках, сочетающих в себе различные подходы, и языках не являющихся чисто функциональными. Так к примеру Erlang - язык сочетает в себе функциональную сущность и понятие процессов. Идеологие данного языка является выражение "всё есть процесс" Он активно используется для разработок разного рода распределённых систем. Язык Scala сочетает возможности функционального и объектно ориентированного программирования, и имеет реализацию для платформы JVM. Nemerle является высокоуровневым компилируемым языком программирования для .NET и использует функциональный, объектно-ориентированный и императивный подходы. Python – язык, который по сути является объектно-ориентированным, использует помимо всего особенности и других парадигм, в том числе и функциональную. Python используется в различных качествах: как основной язык реализации, для создания расширений, для интеграции приложений. Подобно ему, существует большое количество различных языков, использующих в той или иной мере функциональный подход.
Функциональный подход это не альтернатива императивному. Это просто другой взгляд на теорию программирования, со своей культурой, теорией и спецификой, который обладает как преимуществами так и недостатками, присущими ему. Поэтому нет смысла сравнивать эти подходы или противопоставлять, гораздо лучше их совместить во благо разрабатываемых всеми нами программных проектов;)

Литература, использованная при написании статьи:

Функциональное программирование для всех
Курс введение в теорию программирования. Функциональный подход
Курс основы функционального программирования
Основы функционального программирования
Лекции по функциональному программированию
Декларативное программирование
Сильные стороны функционального программирования
Описание языка Haskell
Мягкое введение в Haskell. Часть 1
Форумы RSDN
Википедия

четверг, 29 марта 2007 г.

Быть программистом

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

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

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

Быть программистом, это... нужно быть им;)

воскресенье, 18 февраля 2007 г.

Как не стать Оленеводом Крайнего Севера

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

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

Понедельник. Вы пасете оленей.
Вторник. Вы пасете оленей.
Среда. Вы пасете оленей.
Четверг. Вы пасете оленей.
Пятница. Вы пасете оленей.
Суббота. Думали выходной, да? Хрен!!! Вы пасете оленей.
Воскресенье. Hу вы уже поняли, что вы делаете, да? Правильно. Пасете оленей.
У вас один выходной в год - это день, когда приезжают геологи, и вы обмениваете
оленей на водку.
В чуме вас ждут: страшная жена, семеро голодных детей, паленая водка от
геологов, и соленая оленина на ужин.
Вы моетесь дважды в течении всей жизни: при рождении, и после смерти.
Вы никогда не видели горячую воду.
Hастоящим лакомством для вас являются ягоды и коренья, собранные вашими детьми.
Если вы плохо пасете оленей, вы умрете от голода.

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

И прекратите, наконец, заниматься херней. Hачните работать.


«Есть желание поработать? Собирается команда для разработки проекта связанного с Интернет-пейджингом на С++. Предложение вообще супер, соглашайся, знакомый подсуетил информацию».

В июне 2003 года я закончил четвертый курс и уже видел себя, свободного и счастливого, купающегося во всех прелестях последних студенческих летних каникул. Но этот телефонный звонок перечеркнул все мои беззаботные планы относительно наступившего лета.
Ну кончено я не мог не согласиться на такое предложение, а это значило, что отныне летних каникул у меня больше не будет. По правде говоря, я был чрезвычайно рад такому повороту событий. Конечно, намного лучше потратить свободное время на что-то полезное, чем все лето предаваться неизвестно чему. Таким образом, я был привлечен, к моему первому такого масштаба проекту.
В команду были привлечены еще четверо моих друзей, с которыми мы вместе учились на одном потоке. Руководить нашей молодой командой взялись два менеджера-координатора. Таким образом, была снята квартира под наш офис, временно, до закупки корпоративных, перевезены туда наши компьютеры и работа над проектом началась.
Заказчик, молодой уважаемый англичанин, с которым мы общались только через интернет, хотел получить многофункциональную систему обмена мгновенными сообщениями, поддерживающую протоколы ICQ, AIM, IRC, MSN, Yahoo!. Должна была быть реализация многоаккаунтной работы клиента, поддержка шифрования передаваемых данных, возможность проведения аудио и видео конференций. Программа должна была обладать приятным многоязычным интерфейсом, поддерживающий скины. «Хочу Trillian, только лучше», - шутили менеджеры словами заказчика.
Между нами пятью были распределены протоколы для реализации. Мне достался легендарный ICQ. Практически все лето ушло на исследование каждым из нас своего протокола и реализации демонстрационного приложения, реализующего его базовые возможности. Менеджеры занимались организационными вопросами и формулированием требований к разрабатываемому проекту, точнее его первой альфа-версии.
С сентября мы приступили к совмещению своих наработок и созданию первой альфы. В связи с этим, каждому, помимо своего протокола, пришлось заниматься еще и задачами направленными на реализацию компонентов основной системы. А к тому же, летние каникулы закончились и опять началась учеба в университете. Однако, к счастью, на пятом курсе нет необходимости учебе уделять столько времени, сколько, скажем, на первом, и поэтому мы практически все время находились в офисе, посещая университет несколько раз в неделю, которых было достаточно для того, что бы избежать неприятных последствий нашего невнимания к учебному процессу.
Все условия занятости на проекте нас устраивали, мы были полны оптимизма и решимости. Все наши разговоры как на офисе, так и вне его всегда сводились только к проекту. Нам это было очень интересно. Думаю каждый из нас был уверен, что мы напишем что-то лучшее чем Trillian, по крайней мере с нашей точки зрения. Таким образом, к ноябрю проект дорос до статуса «Альфа» и увидел, что мир есть и за пределами нашего офиса;).
Но повышение статуса проекта до «Альфа», помимо всего прочего означало еще и то, что начиналось время дедлайнов (dead-line). Это значит, что где-то раз в две-три недели в пятницу нам приходилось засиживаться в офисе до полуночи и тщетно избавляться от неожиданно появившихся ошибок, о существовании которых ранее никто и представить не мог. Иногда все заканчивалось хорошо, и очередная версия отправлялась заказчику в срок. Однако бывали и такие случаи, когда сроки срывались и в понедельник имели место длительные дискуссии наших менеджеров с заказчиком о причинах срыва. Так или иначе проект рос и развивался.
Однако, как правило, любой длительный проект рано или поздно сталкивается с различными проблемами, корректное решение которых является единственным условием успешности проекта и определяется уровнем квалификации людей, занимающихся его управлением.
В нашем проекте подобных проблем также не удалось избежать. Основной проблемой, как мне кажется сейчас была неопределенность заказчика. То есть как бы работа над проектом ведется, средства на его поддержание вкладываются. Но остается главный вопрос – для чего все это? Как извлечь прибыль из проекта, как добиться его окупаемости? Вообще что нужно получить в результате. Ответов на эти вопросы у него не было. К проекту были привлечены люди на стороне заказчика координирующие развитие проекта и занимающихся его промоушеном. Было решено также применить более жесткие меры по контролю деятельности разработчиков (то есть нас) и оплаты их труда. Была введена система MBO, регулирующая сумму заработной платы на основании продуктивности работы каждого сотрудника и качества его рабочего дня. Если раньше мы все получали одинаковую сумму, то теперь появились существенные различия. И если кто-то получал больше, то это совсем не означало, что этот человек сделал больше и лучше чем тот, кто получил меньше. Ведь здесь помимо самой продуктивности сотрудников появился субъективный фактор, который определялся отношениями внутри нашего коллектива, а в особенности отношениями с нашими менеджерами.
По большому счету, введение системы было логичным этапом в развитии проекта такого масштаба. Она позволила бы простимулировать деятельность разработчиков, и исключила бы ситуации когда разработчик делая в несколько раз больше, чем другой получал бы столько же. Она положила бы начало формированию какого-то локального бюджета коллектива, который в дальнейшем мог бы уменьшить нашу финансовую зависимость от заказчика. Но на практике это нововведение стало началом конца проекта. Обычная человеческая алчность взяла верх.
Те из нас, кто стал получать меньше совершенно справедливо по их мнению затаили на менеджеров обиду и приняли решение что если получают меньше, то и работать должны меньше. Поползли мнения, что недоплаченные суммы попадают в карман наших непосредственных начальников и что те таким образом наживаются за наш счет. Подобные волнения сильно пошатнули моральное состояние нашей команды. И с этих пор все стало только ухудшаться. Отдельные люди практически перестали работать вовсе, отсиживая «попо»-часы и довольствуясь тем что осталось от заработанного после вполне справедливых вычетов. Остальные «обиженные» продолжали работать в том же ритме что и прежде, однако отношение к менеджерам очень сильно изменилось в худшую сторону.
В итоге все эти неприятности привели к необходимости проведения всеобщего совещания. Оно состоялось в марте в виде онлайн-конференции, в которой принимали участие мы, разработчики, наши менеждеры, и наш английский заказчик. Получив такую возможность непосредственного общения с заказчиком, мы, как вариант решения конфликта быстро убедили его в необходимости увеличения оплаты нашего труда. Таким образом, итогом конференции стал тот факт, уровень нашей заработной платы увеличился вдвое.
Но теперь очень обиженными стали наши менеджеры. Они посчитали, что мы, как все еще студенты, не должны получать таких больших сумм, и что это крайне неправильно. В результате штрафы по системе MBO увеличились еще больше, и некоторые из нас стали получать едва больше, чем до конференции, несмотря на то что нормативно заработная плата увеличилась вдвое. Теперь конфликт внутри нашего коллектива приобретал глобальный характер. Участились общения нас с заказчиком, относительно иррациональных действий менеджеров, и их некорректности ведения дел в команде.
То настроение, переполненное амбициями и оптимизмом, которое было ранее бесследно исчезло. По мере приближения релиза версии 1.0 негативные эмоции все больше преобладали в команде. Вместе с тем приближалось время нашего диплома в университете, а это значит, что на проект оставалось уделять еще меньше времени. Были недовольны мы, были недовольны наши менеджеры, был недоволен заказчик. Все катилось вниз по наклонной, с каждым днем все больше и больше.
Апогеем всех этих событий стала майская чистка нашего коллектива. Было уволено двое сотрудников нашей команды: разработчик, занимавшийся протоколом Yahoo! и наш тим-лидер (team-leader), душа всего коллектива и генератор оптимизма и бодрости нашей команды разработчиков, который занимался протоколом AIM. Если первая вакансия была в кратчайшие сроки ликвидирована, то увольнение тим-лидера, который к слову собственно и позвонил мне тем далеким летом, предложив заняться проектом, едва ли можно было назвать хорошим решением. Вот при таком упадочном настроении внутри команды в июле был отправлен на «золото» релиз версии 1.0.
К тому времени у продукта был полноценный сайт, огромный многоязычный форум, и большое количество посетителей и пользователей нашей программы. Ссылки на продукт стали появляться на различных софтверных порталах. О программе заговорили.
Но настроение в нашем коллективе были просто ниже плинтуса. Без тим-лидера не было того позитива в нашей работе и простить его увольнение нашим менеждерам мы не могли.
Мы проработали над проектом год, а значит настало время заслуженных отпусков. Ключевой разработчик занимавшийся разработкой ядра программы и протокола IRC с отпуска так и не вернулся. Он пошел работать в другое место. А в конце лета с проекта ушел и я, сославшись на то, что необходимо отрабатывать распределение (может кто-то еще в курсе что это такое:)). На наше место пришли новые разработчики, со своими амбициями и настроением. Но проект спасти было уже нельзя. В январе следующего года моя бывшая команда нашла силы выпустить версию 1.5. Позже , почти через полгода появилась 2.0 но все было тщетно. Проект уже был мертв. Позже не стало и сайта. Все было кончено – конкурента у триллиана больше не стало.
Теперь я иногда нахожу на софтверных порталах последнюю версию, ее до сих пор качают и используют, иногда даже хвалят, но у пользователей нет возможности обратиться к разработчикам, указать о наличии какой-то ошибки, поделиться впечатлениями или загрузить обновление программы.
Проекта больше нет, остались только воспоминания.

суббота, 20 января 2007 г.

Как я стал программистом.

В 1999 году я поступил в Белорусский государственный университет информатики и радиоэлектроники в Минске на факультет компьютерных сетей и систем, сокращенно – КсиС. Правда для бесплатного обучения у меня не хватило баллов на вступительных экзаменах, но студентом я все же стал, платником. Таким образом половина мечты стать программистом и связать свою жизнь ИТ сбылись.
До этого, знания в области программирования у меня практически отсутствовали. Я имел общее представление о том, что такое переменная, что с ней можно сделать, но не более того. К примеру тогда я понятия не имел, как эти знания применимы для создания полноценной программы, вроде тех, которыми я пользовался в то время на компьютере.
Однако неплохие на то время знания математики, достаточно развитое логическое мышление вселяло в меня оптимизм и уверенность в том что я стану высококлассным программистов, потом хакером, и наконец гуру:). Теперь мне кажется, что все так думают до какого то времени. Потом, с возрастом, это как правило проходит. Ну не у всех конечно, только у тех кто так и не стал хакером или гуру и отказался от этой мечты:))
Учеба была чрезвычайно тяжелой. Было очень много предметов, никак не связанных с моей специальностью, к которым преподаватели предъявляли такие же требования, как и к специализированным предметам, может даже и больше. Помимо этого у меня на то время был достаточно большой пробел в знаниях о программировании, и для его закрытия требовалось чрезвычайно много времени. С первого курса мы начали изучать Си. Хорошо помню, как по вечерам часто оставался в библиотеке и разбирался с книгой по Си. Насколько я помню называлась она «Приглашение в Си», была в мягкой обложке бирюзового цвета.
Времени для изучения всех дисциплин катастрофически не хватало, и поэтому меня, признаюсь, иногда посещали мысли бросить учебу, потому что было очень тяжело. Однако несмотря ни на что, я, как любят говорить про студентов, "грыз гранит науки" и продвигался дальше, получая все новые и новые знания.
Постепенно начал как-то замечать что уже не являюсь таким дилетантом, каким был прежде. «Приглашение к Си» было «изгрызено» от корки до корки, и на ее место пришел Г. Шилд, со своим «Borland C++». Я уже неплохо разбирался в переменных, операциях над ними, функциях, структурах. И потихоньку начинал знакомится с принципом объектно-ориентированного программирования. Но несмотря ни на что, уровень моих знаний оставался достаточно низким. Однако это только сподвигало меня на дальнейшую изнурительную учебу и укрепляла мою уверенность относительно того что я точно стану гуру:)
Практически в процессе всего обучения мы использовали DOS, однако меня это не угнетало: серьезные, как я считал в то время, таблицы из ASCII-символов делало интерфейс моей программы профессиональным и очень серьезным. Я был почти счастлив, еще на шаг приблизившись к моей мечте о лаврах и непревзойденности.
Позже к С++ добавился Ассемблер. Нас учили в DOS работать с периферийными устройствами, заставляли писать программы на Ассемблере с графическим интерфейсом (ASCII-таблицы). Изучая Ассемблер, я все больше понимал С++, его гибкость и мощь.
Позже мы добрались до WIN32 API. Это было действительно потрясением. Теперь я видел, что для того что бы писать программы под Windows, знаний С++ совсем недостаточно. Необходимо было использовать огромные структуры, непонятные типы данных, такие как HINSTANCE или UINT, вызывать странные и неизвестные функции, типа CreateWindow. До этого все было уже интуитивно понятно относительно типов С++, таких как int или char*. Новые особенности написания программ внушали недоверие и опаску.
Однако и этот этап был пройден. Я уже без труда писал огромные блоки switch в оконной процедуре, и считал что могу многое. Позже я научился эффективно разделять этот код в отдельные методы, что привносило хорошую читаемость моего исходного кода и делало оконную процедуру не такой монолитной как было раньше.
Однако писать большие серьезные программы, используя только Win32 API было очень затруднительно и неудобно. Исправление или дополнение функциональности требовало огромных усилий, так как для каждого обработчика сообщения, для каждого окна был свой метод, своя оконная процедура. И изменяя исходный код в одном месте, требовалось анализировать как он повлияет на все остальное и делать дополнительно соответствующую доработку в другом месте. Пришло время знакомится с MFC.
Первое затруднение вызвало непонимание: где WinMain? Есть много классов, много файлов. Для каждого окна свой отдельный клас, удобный, после блока switch, механизм обработки сообщений. Однако мне все равно было непонятно – где точка входа в программу? Я не понимал. Я не понимал, и поэтому продолжал разбираться.
Позже я привык и смирился, что явного WinMain нету, и продолжал исследовать особенности MFC и получая все новые и новые знания. Меня очень порадовал тот факт, что для написания программ для Windows, не обязательно использовать чистый Win32 API.
Я был счастлив, что MFC позволяет писать такой удобный и понятный код. Я уже мог экспериментировать с графическим интерфейсом программы, делая его более приятным, ,без труда применяя различные особенности элементов управления и украшая интерфейс различными иконками и красочными картинками. Практиковал использование многопоточности в своих программах, работу с сетевыми интерфейсами.
Чуть позже приобрел книгу по Java, которая тогда еще не была так распространена как сейчас, и ее изучение представляло достаточно большой интерес в студенческих кругах. Поскольку в программе университета изучение Java не предполагалось, я приступил к самостоятельному изучению. Я занимался уже на четвертом курсе и был почти счастлив.
Но все тогда только начиналось.