0,0
рейтинг
1 марта 2012 в 06:12

Haskell — Дизайн

Говорят, каждый программист должен в своей жизни написать хотя бы один компилятор или придумать какой-нибудь язык программирования. Дизайн нового языка — дело непростое, ведь нужно продумать десятки параметров, которые, как кубики Lego, должны хорошо между собой сочетаться. Одно неудачное решение может перечеркнуть судьбу языка, когда он еще даже не вышел в свет. Сотни языков прозябают в забвении, подвинутые с подиума старшими братьями, но мир с упорством, достойным лучшего применения, рождает ежегодно два-три новых. Попадут ли они хотя бы в «группу альтернативного мировоззрения», или даже станут мэйнстримными, покажет время. К счастью, моему языку это не нужно, поскольку на нем нельзя программировать, — им можно только любоваться. Ибо это язык визуализации Haskell-кода, о дизайне которого пойдет речь в статье.





Haskell — замечательный язык. Он очень выразительный и емкий. Код получается на порядок компактнее кода на императивных языках (C++, Java, C#), несмотря на то, что в нем меньше синтаксических конструкций. Чистая функциональная природа Haskell и его дизайн способствуют тому, что код становится похож на математическую запись. Возьмем для примера показательный (но не лучший) вариант факториала:

fact n | n == 0 = 1
       | n >  0 = n * fact (n-1)


В этих двух строчках отлично узнается знакомая со школы рекуррентная формула факториала:



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

int fact(int n)
{
    if (== 0) return 1;
    return n * fact (- 1);
}


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

int fact(int n)
{
    int f = 1;
    for (int i = 2; i <= n; ++i)
        f *= i;
    return f;
}


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



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

При дизайне языка приходится думать над тем, как его потом расширять. Сделаешь неверно или неудобно, — и новым затеям не будет места без того, чтобы разрушить обратную совместимость. Истории такие примеры известны; не миновала сия чаша даже некоторые очень популярные языки (например, Python 3.0, который не совместим с ранними версиями). В значительной мере на расширяемость дизайна влияют совсем малые вещи, так сказать, синтаксис в малом. При удачных детальках весь язык строится как один большой и хорошо продуманный конструктор. Haskell из таких, а значит, язык визуализации тоже должен держать марку. И тут я даже не могу сделать скидку на то, что дизайн Haskell известен, — мне все равно приходится преодолевать эти трудности с самого начала. Хотя в некотором смысле мне, конечно же, проще.

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

-- | Collects actions for specified box side drawings.
-- | It should be used only in this module.
:: PreparedTextureObjects
    -> GLfVertex3 
    -> (BoxSide, QuadColorSpec)
    -> ([BoxSide], [IO()])
    -> ([BoxSide], [IO()])
f texRes boxDim (side, qColorSpec) (sList, ioList) = let
    boxIO = do  setQuadColorSpec texRes qColorSpec
                GL.renderPrimitive GL.Quads (boxSide boxDim side)
    in (side : sList, boxIO : ioList) 


Или для такого:

data QuadColorSpec = QuadTexture TextureName
                   | QuadPlainColor GLfColor4
                   | NoQuadColorSpec
    deriving (Show)
 
data ObjectTextureSpec = BoxTextureSpec
        { quadSideTexes  :: [(BoxSide, QuadColorSpec)]
        , defQuadSideTex :: QuadColorSpec
        } deriving (Show)
 
data CornerCoord = UR | DR | DL | UL 
    deriving (Show)


А пока у меня есть код факториала, с него и начинался язык визуализации:

fact n | n == 0 = 1
       | n /= 0 = fact (- 1) * n


Здесь мы видим несколько синтаксических конструкций:

название функции fact
Аргумент n
2 охранных выражения | n == 0
| n /= 0
2 тела функции = 1
= fact (n — 1) * n


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



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






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

isListElement  x xs = elem x xs   -- функциональная форма
isListElement’ x xs = x `elem` xs -- инфиксная форма


Операторы по умолчанию используются в инфиксной записи, но допустима и функциональная тоже:

add a b = a + b
add’ a b = (+) a b


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



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

add3 a b c = a + b + c
someF x y z = x >>= y >> z





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

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

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)


Выглядит выражение (да и работает тоже!) очень красиво. Попробуем построить эскиз для него, помня о том, что знак “двоеточие”, использованный дважды, записан в инфиксной форме, а zipWith — это функция, принимающая три аргумента: (+), fibs и (tail fibs). Проблема здесь появляется с плюсом в скобках. Знак передается в другую функцию как аргумент, — и для Haskell это нормальное и очень полезное явление, известное как “функция высшего порядка”. Дополнительно, у оператора + откушены оба его собственных аргумента, — и это уже называется сечением. Согласно нашим прошлым правилам, оператор + должен стать конечным аргументом с увеличенной коробкой. В принципе, это нормально:



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

ops = [(+), (*), (-)]
 
func x y op = x `op` y
 
result = map (func 2 3) ops


Здесь три функции: ops возвращает список операторов, func — производит над аргументами x и y действие, переданное как op, а внутри result это всё используется и что-то вычисляется. Если быть честным, при выполнении result вернет такой список: [5, 6, -1], и нетрудно проследить, как он получился. Функцией map функция (func 2 3) была применена ко всем операторам из списка ops. Нас в данном случае интересует, что (func 2 3) — это каррированая запись, у которой один аргумент остается вакантным. Операторы в скобках тоже каррированы (правильнее сказать — усечены), у них все уже украдено до нас… то есть, отобраны по два аргумента. В коде Haskell это никак не отражается, и странная запись вроде такой:

nullMap = map null


может ни о чем нам и не сказать, если не знать, что делают функции map и null, и если сигнатуры типов не указаны. Однако в визуализации мы могли бы чётко показать, что эти функции требуют еще какие-то аргументы. Достаточно постулировать, чтобы аргументы помещались в пазы функций, и количество пазов соответствовало арности. Вот результат для функций result и nullMap:




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

Важной конструкцией любого языка являются условные переходы. В Haskell оператор if тоже есть, и он таков, что оператор else обязательно должен ему сопутствовать. Не может быть выражения, у которого одна из альтернатив отсутствует, — в мире, где всё есть функция, результат должен возвращаться всегда. Ниже представлено вычисление факториала с if (мы, как и в прошлый раз, не задумываемся о том, что n может прийти отрицательный):

fact n = if n == 0 then 1 else fact (- 1) * n


Форматировать код здесь можно по-всякому. then и else не чувствительны к отступам и могут быть расположены на новой строке (только отсчитывая хотя бы один пробельный символ от функции fact):

fact n = if n == 0
      then 1
      else fact (- 1) * n


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




Давая волю фантазии, можно добиться некоторой интуитивности последнего варианта. Ведь что такое if? Это когда булевое выражение проверяется на истинность, то есть, на совпадение с True. На принципе совпадения построены конструкторы, паззлы и кое-что ещё: есть совпадение, — штырь подходит к пазу; нет совпадения, — ну, извините… Попробуем внести эту концепцию в эскиз:




Выглядит интересно и побуждает фантазировать дальше. Можно экспериментировать с положением, формой, размерами, но нужно не забывать о том, что if-then-else — это выражение, и оно будет использоваться внутри других выражений. То есть, раз уж мы ограничиваем себя в пространстве ради выразительности, то и условный оператор не должен выходить за некие эмпирические рамки.

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

fact n = case n == 0 of
    True  -> 1
    False -> fact (- 1) * n


Есть над чем подумать. В case-конструкции добавляется новая семантика: сопоставление с образцом. Тут я, признаться, еще не придумал достойного варианта. Но можно попробовать по аналогии с одним из последних эскизов if:



Смысл сопоставления с образцом в том, что на каждом из кубиков перед знаком "->" может быть достаточно большое выражение. Возможности огромны: здесь и расщепление списков, и сколь угодно глубокое сопоставление с алгебраическими типами данных, и даже — с подключенным расширением языка View Patterns — некий синтаксис, напоминающий функции. Я покажу лишь простой, достаточно типичный код, где используется pattern matching внутри case:

toHabrFormat (s, (ch:[])) = s ++ [ch]
toHabrFormat a@(s, b@(ch:inStr)) = let formatted = (foldr1 (<|>) formatters) a
                        in case formatted of
                            Just (res, [])     -> res
                            Just (res, (r:rs)) -> toHabrFormat (res ++ [r], rs)
                            Nothing            -> toHabrFormat (++ [ch], inStr)


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

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

fact n | n == 0 = 1
       | n /= 0 = fact (- 1) * n


Об охранных выражениях есть что сказать. Это обычные выражения, но возвращают они всегда булевое значение — True или False. Они служат некими фильтрами, как бы не пропуская выполнение в тело, если условие не истинно. Играя с этой концепцией, можно придумать что-то вроде пресловутого if. Оценим следующий вариант:



Коробка с равенством (”мост”) появилась из желания соединить охранные выражения и тело функции так же, как в коде. И это, кажется, интересная идея. Развиваясь, она переросла в нечто большее — в визуальное разделение частей (имя функции; охранные выражения; вычислительное выражение). Можно пойти дальше: поместить их на платформы, очертив тем самым пространство каждой из частей.



В коде охранное выражение начинается с символа ‘|’. Если бы его не было, код выглядел бы противоречиво:

fact n  n == 0 = 1
        n /= 0 = fact (- 1) * n


Компилятор бы не понимал, чем являются буквы и символы после слова fact. Вертикальная черта — необходимый элемент синтаксиса, и поэтому нам нужно его внести в визуализацию. Логично поставить что-нибудь слева от платформы с булевым выражением; это может быть, например, “стена”:



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



Гораздо лучше! Теперь визуализируем имя функции с аргументами. Опять же, здесь мы имеем дело с pattern matching, и, по-хорошему, его стоило бы совместить с арностью. Вырезы для аргументов мы уже научились делать, они пригодятся и здесь. Без сопоставления с образцом у нас был бы такой вариант:



Итак, построена основа графического языка, и мы теперь примерно представляем, как он должен выглядеть. Для ясной картины еще нужно разобраться с такими важными вещами, как алгебраические типы данных, списки, кортежи и сопоставление с образцом. Когда с ними будет покончено, скорее всего появятся идеи, что делать с декларациями типов, с do-конструкциями, генераторами списков, as-образцами, типами классов, воплощениями классов и прочими замечательными элементами Haskell-синтаксиса.

Начнем с алгебраических типов данных, списков и сопоставления с образцом. Выше в примере с case мы уже попробовали визуализировать АТД и pattern matching. Представим, что арность вместо вырезов обозначается выступами. Картинка с case, True и False тогда будет неверной, потому что у этих двух конструкторов арность равна нулю. Однако, арность Just равна 1, — и у него будет один выступ.



Списки создаются через инфиксный оператор ":" (который вообще-то является конструктором типа, — но это уже другая история [1]). Мы уже умеем его визуализировать. Возьмем более сложный случай, — когда есть и «неважные» элементы, и пустой список. Вот гипотетический код:

someFunc someList = case someList of
(x1:x2:_:xs) -> Just (x1, x2)
(x1:[])      -> Just (x1, x1)
[]           -> Nothing


Уже сами конструкции языка Haskell наглядно показывают свою суть. Неважный аргумент заменяется знаком подчеркивания, а пустой список — пустыми квадратными скобками. Учтем это при визуализации. Не видно в формализме кода только различий между аргументами x1, x2 и xs из первой альтернативы. Между тем, x1 и x2 — это отщепленные спереди элементы списка, а xs — это весь остальной возможно пустой список. Полезно было бы разницу как-то показать.




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



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



Красота, что и говорить. И уже кажется, что основные затраты здесь — на выдумывание дизайна, а визуализацию можно быстро состряпать в каком-нибудь графическом редакторе, но… В реальности всё несколько сложнее, потому что для визуализации нужна программа, а не статичная 3D-сцена. Именно такую программу я и создаю в проекте «GraphServer». Задача осложняется тем, что не для всех конструкций я придумал визуализацию; уже при написании этой статьи были сильно изменены или изобретены некоторые конструкции. Но даже то, что готово на данный момент, выглядит многообещающе.

Это кросс-статья. О создании сервера визуализации читайте в статье «Haskell — Эстетика».

P.S. Прошу прощения за не совсем качественные картинки. Habrastorage, похоже, с ними что-то делает.
[1] — Исправление в связи с данным комментарием: it-talk.org/post76900.html#p76900
Александр Гранин @graninas
карма
121,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (30)

  • +3
    Идея понравилась. Так можно находить огромные функции, выражения и уменьшать их. Ну, и красиво :)
    • +1
      Да. :) И, мне кажется, с помощью визуализации людей легче обучить некоторым особенностям языка (каррирование, арность).
  • +2
    Здравствуй, будущее. Прямо так и вижу, как программист, размахивая руками перед каким-нибудь кинектом, таскает подобные блоки, собирая их и составляя их в программы, а непосвященные замирают с открытыми ртами при виде такого таинства программирования.
    • +1
      Это было бы потрясающе. И, на самом деле, уже сейчас можно создать Proof of Concept, — технологии позволяют.
    • +3
      App Inventor гуглевый видели?
      • +1
        Посмотрел после того, как вы его назвали. Да! Тоже визуализация, тоже очень красивая. Поковырять его надо-с.
        • +2
          мечты о действительно визуальном программировании («программировании мышкой») витают давно. И в частных случаях эта задача решается, с разным успехом.

          У вас заход с другой стороны — при наличии программы отобразить. Но суть задачи общая — как визуальные образы использовать для каких конструкций — на мой взгляд есть смысл познакомиться с опытом «визуальных программистов», наверняка найдете интересные решения, или может быть даже просто подходы с другой стороны поможет :)
    • +2
      а непосвященные замирают с открытыми ртами при виде такого таинства программирования.

      Ага, щас. Точно так же будет подходить начальство и спрашивать «когда». А при знакомстве, узнав что ты программист все будут точно так же с покерфейсом говорить «понятно».
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Спасибо!

      Да, я с удовольствием читал, как вы учите свое дитя программированию. Удивительно, что он многое понимает. После этого ему в будущем, скорее всего, императивное программирование станет неудобным и вообще жутким.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          О, это хорошо, поздравляю с пополнением в семье!

          Хмм, для меня тоже лето — творческое время. Хочу дополнить Haskell Quest Tutorial несколькими главами, только это очень затратно по времени.
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              Ммм, ну это так… руководство по Haskell… Впрочем, не время для скромности. Вот: habrahabr.ru/blogs/Haskell/120590/
              • НЛО прилетело и опубликовало эту надпись здесь
  • –2
    «Я просто оставлю это здесь»

    • +3
      Это не совсем то же самое. Лисп, конечно, наше все, но он скушен для визуализации: там всего лишь одно или несколько AST-деревьев.
      • 0
        Это не скучность, это униформность. К тому же, программа остаётся выглядеть читаемой как и была. В тех же визуализациях придётся ещё думать как будет выглядеть код.
        • +2
          Безусловно, униморфность — это такое большое достоинство. Но оно же и недостаток. Все равно, что играть в тысячный клон Тетриса: суть кардинально не меняется, пространство для размышлений есть, но оно всегда одно и то же.

          Вам бы в мире «Эквилибриума» понравилось, да. :)
    • –2
      Херовый код, кстати: при значениях меньше нуля факториал не определён, а код этого не учитывает.
      • +1
        Цитата из статьи:

        > (мы, как и в прошлый раз, не задумываемся о том, что n может прийти отрицательный)
      • +1
        Упс, пардон, я думал, это вы про мой код…
      • +1
        Я вижу, что со мной не согласны, но всё же считаю неправильным всюду писать один и тот же некорректный код в качестве примера функциональщины. Зачем экономить одну строчку в ущерб корректности алгоритма?
        • 0
          Безусловно. В статьях о ФП и о самом языке я такого не допустил бы (да и не допустил, читайте Haskell Quest Tutorial). И в преподавании Хаскелля тоже этого не допускаю. А здесь как бы это не столь важно…
  • +2
    В sketchup очень просто включить сглаживание. Картинки будут куда приятнее. ОКНО Параметры OpenGL
  • +2
    Хочу посмотреть на визуализацию какой-нибудь охренительно сложной и ветвистой функции. Так чтоб мозг выносило и дух завораживало.
    • +1
      Я тоже хочу, но для этого сначала нужно дописать сервер хотя бы до половины. Присоединяйтесь, будем приближать будущее вместе. ;)
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Ой, спасибо!
  • НЛО прилетело и опубликовало эту надпись здесь

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