О начале массивов и списков...

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

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


my $day_epoch = timelocal(0, 0, 0, 31, 3, 2011);
Day '31' out of range 1..30 at - line 2


The value for the day of the month is the actual day (ie 1..31), while the month is the number of months since January (0..11). This is consistent with the values returned from "localtime()" and "gmtime()".


$mday is the day of the month, and $mon is the month itself, in the range 0..11 with 0 indicating January and 11 indicating December.  This makes it easy to get a month name from a list:


Как видно, на первый взгляд, совершенно дурное решение нумеровать дни от 1 до 31, а месяцы с 0 до 11, становится вполне логичным и оправданным в контексте нумерации массивов с 0. Напрашиваются странные выводы...

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

Литуратурная аппаратура на VHDL

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

Сперва о инструментарии, который мною использовался. Это была реализация системы литературного программирования noweb, которая не привязана ни к какому языку программирования (что оказалось крайне приятным, так как VHDL специально никто ничего подобного не делал). В качестве редактора использовался emacs + noweb.el. Текстовая часть кода оформлялась в LaTeX (тут была альтернатива в качестве html). В принципе, эти инструменты позволили с комфортом работать над задачей, после некоторой привычки. К сожалению, noweb.el является достаточно кривой реализацией, с некоторым количеством неприятных моментов (часто слетает подсветка синтаксиса).

Русская вики даёт следующее определение для литературного программирования:

Литературное (английский термин намеренно двусмысленный), или грамотное программирование (англ. Literate Programming) — концепция, методология программирования и документирования. Термин и саму концепцию разработал Дональд Кнут в 1981 году при разработке системы компьютерной вёрстки TeX.

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

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

<<фича такая-то>>=

Код этой фичи, абсолютно выдранный из контекста.

@

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

<<имя_файла>>=

Заголовок такой-то
<<контескт такой-то фичи>>

<<фича такая-то>>

<<фича такая-то>>

<<фича такая-то>>

Ещё какой-то код, необходимый тут.

@

Теперь, мы можем двумя простыми командами получить как статью, в которой довольно неплохо описано, что делает программа (noweave -delay programm.nw > text.tex) и собственно сам код программы (notangle -Rимя_файла programm.nwп > имя_файла). Так как вы нормальный человек, а следовательно не достаточно внимательны, команда для кода скорее всего любезно скажет вам, какие аспекты программы вы забыли, и вы будете вынуждены, добавить пару абзацев текста.

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

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

Преимущества:

- Вы пишите код к той форме и в том порядке, в котором вы думаете. Соответственно он намного проще проверяется, намного проще восстанавливается в голове, так как в нём все его детали всегда явно присутствуют и вводятся последовательно.

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

Недостатки:

- Не понятно как это можно применять для динамических языков, таких как Smalltalk и Lisp.

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

- Не совсем понятно, как такой стиль может применяться в коллективе, так как все думают по разному.

- (самый существенный, также его отмечает Кнут) Мало уметь программировать, надо уметь и писать. 

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

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

http://dl.dropbox.com/u/1619524/src/literate_lab1.zip.

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

Системы типизации языков программрования

Доброго времени суток.

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

В данном посте будет рассказано про понятие типа данных. Про различные подходы к работе с ними. Описаны некоторые плюсы и минусы тех или иных реализаций. (ответ на вопрос, что лучше, можно спросить на linux.org.ru)

"Покажите мне код, не показывая своих структур данных и я по-прежнему буду пребывать в заблуждении. Покажите мне свои структуры данных и, как правило, ваш код мне не понадобиться; и так все будет понятно". (с) Эрик Реймонд

Введение

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

И вот тут, явно или не явно начинает появляться типизация. Мы можем выделить тип объектов, которые могут пролезть в оконный проём. Назовём множество всех объектов, которые проходят в оконный проём множеством W. W = {w | w \in Q; P(w)}, где P(x) - предикат, который позволяет однозначно определить относится ли к данному типу данных объект или нет. В данном случае он звучит так "проходит ли объект в оконный проём".

Определения

Википедия даёт следующие определения типов данных:

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

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

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

Википедия даёт такое определение для пространства:

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

Данное определение вполне подходит для данной работы.

Одномерные типы данных.

Давайте рассмотрим некоторые типы данных языка C с данной позиции:

• int - конечное одномерное пространство, точки которого являются целыми числами.
• double - конечное одномерное пространство, точки которого являются натуральными числами.
• void[] - бесконечное одномерное пространство, которое состоит из всех возможных массивов элементов произвольного типа данных. 
• int[] - бесконечное одномерное пространство, для которого справедливо утверждение: int[] \subset void[].

(Массив является одномерным пространством, так как размерность массива никоим образом не влияет, на свойства, коими обладает массив, так же как строка остаётся строкой не зависимо от её длинны)

Необходимо более внимательно рассмотреть массивы. (важно забыть о указателях, адресной арифметике и всём связанным с тем, как это работает, нам важен именно уровень семантики языка) Тип void[] и int[]. Символы "[]" - указывают на то, что это массив. Слова void и int - на тип элементов, которые хранятся в данном массиве. Из этого можно выбелить два базовых свойства для типов данных:

1. Пространства могут пересекаться между собой и, зачастую, иметь иерархическую структуру. int[] \subset void[]
2. Есть типы данных, параметризуемые другими типами данных. Важно понимать (также как и с размерностью массива), тип данных в массиве никоим образом не влияет на свойства самого массива. Влияние типа данных элементов в массиве играет роль только тогда, когда они извлечены из массива.

Полиморфизм

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

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

В функциональных языках полиморфизм реализуется при помощи обобщённых функций, их отличие от простых функций заключается в том, что во время применения обобщённой функции к объекту, из реализованных методов формируется эффективный метод. В объектной системе Common Lisp Object System, это происходит динамически, причём эффективный метод создаётся путём комбинирования множества методов в 1. В языке Haskell используется статическая типизация, в связи с чем введено понятие класс типов данных. Классом является интерфейс, для которого могут быть декларированы типы данных (а следовательно определены и все необходимые функции). Классы типов выстраиваются в иерархии, к примеру класс сравнимых типов данных наследуется от класса с функция для проверки на равенство.

В объектных и объектно-ориентированных языка иной подход к реализации ad hoc полиморфизма. Проще его рассмотреть на примере объектных языков. У нас есть набор всех допустимых объектов. Из него выделяется некоторое подмножество, наделённое необходимыми нам свойствами. Далее этот механизм повторяется (в случае, если есть множественное наследование, подмножество может быть выделено из нескольких классов).Таким образом, все свойства определённые для изначального множества объектов определены и для дочерних (могут быть переопределены). Так же как и в некоторых функциональных языках, в объектных и объектно-ориентированных языках существует некоторый аналог классов типов данных. К примеру: примеси в C++, интерфейсы в Java и traits в smalltalk.

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

Составные типы данных.

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

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

Аналогичную операцию мы можем произвести над двумя любыми множествами, к примеру: {1,2} x {a,b} = {(1,a), (1,b), (2,a) (2,b)}.  Прямое или декартово произведение. Результатом перемножения 2-ух множеств является множество 2-ух мерных кортежей.

Кортеж - упорядоченная последовательность разнородных данных фиксированной длинны.

Легко заметить, что кортеж является аналогом структур данных. А пространства кортежей - являются таблицами (все записи в таблице - отмеченные точки в пространстве). В частности в языке Erlang (в виду динамической типизации) записи реализуются именно через кортежи, а тип записи определяется первым элементом в кортеже. (для точки это будет выглядеть примерно так: ('point', int(), int()) = {'point'} x int() x int())

Алгебраические типы данных.

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

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

\union { (x, i) | x \in A_i }

Что это означает намного проще понять на наглядном примере, и классикой в данном случае является дерево, но пример с типом Maybe языка Haskell намного забавнее и проще. Назначение типа данных: контейнер для данных, который имеет состояние "пустой". На языке C (для целочисленных данных) это имеет следующий вид:

struct Maybe {
  int value;
  enum {
    JUST,
    NOTHING
  } status;

}

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

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

data Maybe a = Just a | Nothing

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

Более подробно алгебраических типах данных можно прочесть здесь: Роман Душкин - Алгебраические типы данных.

First-class object

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

Для языка Smalltalk это объекты. Причём к объектам относятся классы, исполняемые блоки и даже константы True и False являются полноправными объектами.

В Lisp это атомы, простые типы данных, списки и функции.

Подходы к реализации

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

• Динамическая типизация (типы данных определяются в runtime).
• Статическая типизация (типы данных определяются на этапе компиляции).

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

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

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

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

Послесловие

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

Принято делить типы данных на простые и сложные (составные).

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

• Простой тип - тип данных, объекты (переменные или постоянные) которого не имеют доступной программисту внутренней структуры.
• Сложный (составной) тип — тип данных, объекты (переменные или постоянные) которого имеют внутреннюю структуру, доступную программисту.

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