Erlang: behavior, parameterized and extends module

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

Behavior

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

В качестве примера можно привеси gen_server. Но из-за объёмности, лучше взять более локальную задачу - генератор последовательностей.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

-module(sequence). -export([behaviour_info/1          , start/1          , get/1         ]). behaviour_info(callbacks) -> % returned list with all needed callbacks     [{calc,1},      {from,0}]; behaviour_info(_Other) ->     undefined. start(Module) ->     Pid = spawn(fun() -> loop(Module:from(), Module) end),     register(Module, Pid). get(Module) ->     Module ! {get, self()},     receive X -> X end. loop(X, Module) ->     receive         {get, Pid} -> Y = Module:calc(X),                       Pid ! Y,                       loop(Y, Module)     end.

Приведённый выше код является behavior модулем и он не может быть использован сам по себе, и должен работать в связке с другим модулем. Функция behavior_info/1 должна возвращать список требуемых callback функций. Это позволит при компиляции сборки проверить, были ли определены все необходимые функции. Вот пример модуля, который определяет необходимые callback функции для генерации списка натуральных чисел (будем считать ноль не натуральным числом) и интерфейс для работы с ним.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

-module(natural). -behaviour(sequence). % export API -export([start/0         , next/0]). % export callbacks -export([from/0          , calc/1]). % API start() ->     sequence:start(?MODULE). next() ->     sequence:get(?MODULE). % Callbacks from() -> 0. calc(X) -> X + 1.

Parameterized module

Параметризованными модулями являются модуль, которые должен быть связан со значением перед использованием. Одним из вариантов его применение – симуляция ООП. Пример такого использования можно найти в исходном коде MochiWeb (src/mochiweb_request.erl).

Заголовок подобного модуля должен иметь следующий вид:

6	-module(mochiweb_request, [Socket, Method, RawPath, Version, Headers]).

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

Эффективный метод создаётся следующим образом:

Mod = mochiweb_request:new(Socket,

                           Method,

                           Uri,

                           Version,

                           mochiweb_headers:make(Headers))

В качестве результата в Mod будет сохранён следующий кортеж: {mochiweb_request, Socket, Method, Uri, Version, Headers}, а вызовы методов должны осуществляться следующим образом:

Mod:get(body_length)

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

Extends module

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

1 2 3 4 5 6 7 8

-module(global_sequence). -extends(sequence). -export([start/1]). start(Module) ->     {ok, Pid} = spawn(fun() -> Module:loop(Module:from()) end),     global:register_name(Module, Pid).

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

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

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

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

В данном посте будет рассказано про понятие типа данных. Про различные подходы к работе с ними. Описаны некоторые плюсы и минусы тех или иных реализаций. (ответ на вопрос, что лучше, можно спросить на 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).