Haskell — Эстетика

    Я придумываю особенную игру в жанре космического симулятора. Согласно одной из ключевых концепций, в игре будет встроенный язык программирования, с помощью которого можно разрабатывать и улучшать алгоритмы взаимодействия игровых элементов. Дизайн такого языка — дело непростое, учитывая его «натуральность», а не «текстовость». То есть, конструкции языка выражены в виде разных графических объектов. Рисуя эскизы его конструкций, я неожиданно для себя отвлекся и вместо языка для игры стал придумывать язык для визуализации Haskell-кода. Получалось так интересно, что я не мог оставить эскизы просто бумажными рисунками. В январе 2012 года я начал писать сервер визуализации, и вот что получилось…





    Чтобы визуализировать что-либо, нужно сначала разобрать это на значимые единицы, а затем сопоставить им графические элементы. В случае с кодом такими единицами будут синтаксические элементы языка, стало быть, на первом шаге нам нужно разобрать код на абстрактное синтаксическое дерево (AST). Компилятор GHC умеет это делать лучше всего, и к нему даже есть биндинги, которые тем и занимаются. Scion — библиотека, позволяющая анализировать код через GHC API. Scion используется, например, в EclipseFP для подсветки синтаксиса и анализа ошибок «на лету». И он был бы хорош, если бы не его сложность, которая на ранних этапах разработки была ни к чему. Писать вручную синтаксический анализатор не хотелось. Любопытно, что нашелся еще один способ, простой и в то же время достаточный: библиотека Language.Haskell.

    Модуль Language.Haskell.Parser — это синтаксический анализатор чистого, без расширений, Haskell’98 кода (ну, почти без расширений). «Продвинутые» программы им не распарсишь, но в начале и самого Haskell’98 хватит за глаза. В качестве подопытного кролика я взял код вычисления факториала:

    fact' n | n == 0 = 1
            | otherwise = fact' (n-1) * n


    Парсинг и анализ с помощью библиотеки делается элементарно, вот пример простой программы:

    import Language.Haskell.Parser
     
    main = do
        s <- readFile "Fact.hs"
        let parsed = parseModule s
        putStrLn . show $ parsed


    Функция parseModule имеет следующий тип:

    parseModule :: String -> ParseResult HsModule


    где первым аргументом идет Haskell-код, а возвращается значение типа HsModule. Чтобы работать с типом HsModule, нужно подключить модуль Language.Haskell.Syntax. Его структура типов полностью описывает подмножество Haskell’98 в виде AST:

    ParseOk
        (HsModule 
            (SrcLoc {srcFilename = "<unknown>", srcLine = 3, srcColumn = 1}) 
            (Module "Main") 
            (Just [HsEVar (UnQual (HsIdent "main"))]) 
            [] 
            [HsFunBind 
                [HsMatch 
                    (SrcLoc {srcFilename = "<unknown>", srcLine = 3, srcColumn = 1}) 
                    (HsIdent "fact'") 
                    [HsPVar (HsIdent "n")] 
                    (HsGuardedRhss 
                        [HsGuardedRhs 
                            (SrcLoc {srcFilename = "<unknown>", srcLine = 3, srcColumn = 9}) 
                            (HsInfixApp 
                                (HsVar (UnQual (HsIdent "n"))) 
                                (HsQVarOp (UnQual (HsSymbol "=="))) 
                                (HsLit (HsInt 0))) 
                            (HsLit (HsInt 1))
                        , HsGuardedRhs 
                            (SrcLoc {srcFilename = "<unknown>", srcLine = 4, srcColumn = 9}) 
                            (HsVar (UnQual (HsIdent "otherwise"))) 
                            (HsInfixApp 
                                (HsApp 
                                    (HsVar (UnQual (HsIdent "fact'"))) 
                                    (HsParen
                                        (HsInfixApp 
                                            (HsVar (UnQual (HsIdent "n"))) 
                                            (HsQVarOp (UnQual (HsSymbol "-"))) 
                                            (HsLit (HsInt 1))))) 
                                (HsQVarOp (UnQual (HsSymbol "*"))) 
                                (HsVar (UnQual (HsIdent "n"))))]) []]])


    В проекте GraphServer я разделил AST-дерево на составляющие, чтобы с ним было удобнее работать:

    t1 = HsInfixApp (HsVar    (UnQual (HsIdent "n")))
                    (HsQVarOp (UnQual (HsSymbol "-")))
                    (HsLit    (HsInt 1))
     
    t2 = HsApp (HsVar (UnQual (HsIdent "fact'")))
               (HsParen t1)
     
    t3 = HsInfixApp t2
                    (HsQVarOp (UnQual (HsSymbol "*")))
                    (HsVar    (UnQual (HsIdent "n")))
     
    t4 = HsGuardedRhs (SrcLoc {srcFilename = "<unknown>", srcLine = 4, srcColumn = 9})
                      (HsVar (UnQual (HsIdent "otherwise")))
                      t3
    ...


    Когда сервер будет работать в обычном режиме, на него можно будет отправить строку Haskell-кода, которая сервером парсится на AST и затем визуализируется. Сейчас же, в активной фазе разработки, сервер работает вхолостую. Я просто выбираю ту или иную «t-функцию» и запускаю весь процесс визуализации; но под кажущейся простотой скрываются разнообразные механизмы и алгоритмы, результат которых вы можете увидеть на картинке:



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

    | n == 0 = 1
    | otherwise = fact' (n-1) * n



    Я хотел, чтобы графический язык отражал смысл синтаксических конструкций. Охранные выражения работают как «фильтры выполнения». Покажем интуитивность рамки мысленным экспериментом. Представим, что ход выполнения — это такой кубик, который может пройти через рамку к телу функции, а может и не пройти, — в зависимости от своих размеров («логического условия»). Стрелки на картинке выше показывают ход выполнения. Что забавно, рамка, если глядеть на сцену спереди, превращается в ту самую вертикальную черту, которую мы видим в коде.


    Я пытался придумать, как будет выглядеть список, создаваемый оператором: внутри сопоставления с образцом, и пришел пока к варианту на картинках. Первая соответствует выражению (x1:x2:xs), вторая — выражению (x1:_:[]). Вместо «неважного» элемента изображена плоская платформа, а пустой список — он и есть пустой. Условный оператор if и case-конструкция тоже в некоторой степени интуитивны. На бумаге у меня есть и другие черновые эскизы, но значительную часть Haskell-синтаксиса еще нужно разработать. Это касается и деклараций типов, и do-конструкции с ее особенностями, и паттерн-матчинга, и прочих важных вещей. А потом созданные эскизы нужно воплотить в коде…



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

    I. Преобразование элемента AST в элемент StructureObject
    II. Сопоставление элементу StructureObject графического примитива
    III. Объединение и позиционирование StructureObject относительно друг друга
    IV. Компиляция графических примитивов в элементы сцены
    V. Отрисовка (рендеринг) сцены

    Прежде чем мы перейдем к реализации, рассмотрим модули, на которые разбит код сервера.

    GraphServer (Main) — главный модуль программы. Содержит функцию main, логику сервера; в нем же происходит инициализация OpenGL, создание окна и первичные настройки. Там же лежит главный цикл программы, и в нем крутится функция draw из модуля Draw.Draw.

    Common — общие данные и алгоритмы.
    Common.Constants — общие константы, настройки, фиксированные данные.
    Common.GLTypes — типы OpenGL (векторы, вершины и прочее), а также другие определения.
    Common.TestData — «t-функции», дополнительные данные для тестирования механизмов.
    Common.Units — функции по работе с единицами пространства, с OpenGL-векторами и вершинами.

    Structure — типы данных и алгоритмы по компиляции AST-дерева в StructureObject-дерево.
    Structure.Constants — константы и настройки, связанные с этапами I, II, III.
    Structure.StructureObject — описание центрального типа данных StructureObject.
    Structure.GraphObject — описание типа GraphObject и функции, создающие объект этого типа.
    Structure.Dimensions — работа с размерностями графических объектов.
    Structure.SOConstruct — создание StructureObject. Соответствует этапам I, II.
    Structure.SOConnect — соединение нескольких StructureObject. Соответствует этапу III.
    Structure.GOCompile — компиляция графических примитивов (GraphObject) в реальные объекты сцены. Соответствует этапу IV.
    Structure.HsSyntaxTools — вспомогательные функции для работы с AST.
    Structure.Texture — вспомогательные типы данных и функции для работы с текстурами.

    Draw — функции, отвечающие за рендеринг сцены.
    Draw.Draw — содержит функцию draw, в которой происходит компиляция и рендеринг сцены.
    Draw.GLInit — вспомогательные функции, предназначенные, как следует из названия, для инициализации OpenGL.
    Draw.Render — содержит функцию render. Соответствует этапу V.
    Draw.TextureInit — вспомогательные функции для создания текстур.

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

    ThirdParty — сторонние утилиты и программы.
    ThirdParty.Frag — код из программы Frag. Загрузка TGA-файлов, создание текстур.
    ThirdParty.GLUtil — дополнительные утилиты по работе с OpenGL.
    ThirdParty.ImageFormats — загрузка TGA-файлов.



    Я тестирую и обкатываю алгоритмы в упомянутой выше функции draw:

    draw :: DrawFunction
    draw GLResources texRes n = do
        putStr $ "Current n = " ++ show n
        GL.clear [GL.ColorBuffer, GL.DepthBuffer]
        GL.loadIdentity
        GL.rotate 10 (vector3 0 1 0)
        GL.rotate 20 (vector3 1 0 0)
        GL.translate (vector3 (-5) (-10) (-30))
     
        -- Конструируем иерархию из StructureObject
        let c = constructFramedGRhss (OcsGuardedRhss t6)
     
        -- Компилируем элементы сцены из графических примитивов
        -- и рисуем сцену
        render texRes c
        putStrLn "Ok."




    Функции constructFramedGRhss и render делают всю работу, и на выходе мы получаем картинки, что представлены в начале статьи. Функция constructFramedGRhss (и ее аналоги) из модуля Structure.SOConstruct реализует этапы I — III. У нее такой тип:

    constructFramedGRhss :: ObjectConstructSpec -> StructureObject


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

    -- Модуль Structure.StructureObject
    data ObjectConstructSpec
                    = OcsApp HsExp
                    | OcsExpArgument   HsExp
                    | OcsExpFuncName   HsExp StructureObject
                    | OcsInfixOperator HsQOp
                    | OcsGuardedRhs    HsGuardedRhs
                    | OcsFoundationExp StructureObject
                    | OcsGuardedRhss   HsRhs
                    | OcsArrowBridge
                    | OcsEqualSignBridge
                    | OcsMatch HsMatch


    Тип данных StructureObject должен быть достаточно общим, чтобы описать любую возможную иерархическую структуру.

    -- Модуль Structure.StructureObject
    data StructureObject = StructureObject
            { soObjectSpec       :: ObjectSpec
            , soGeometry         :: Geometry
            , soGraphObjectSpec  :: GraphObjectSpec
            , soStructureObjects :: StructureObjects
            } deriving (Show)
     
    type StructureObjects = [StructureObject]


    Как видно, поле soStructureObjects содержит список дочерних объектов. Фактически, иерархия AST преобразуется в иерархию StructureObject с накоплением необходимой для рендеринга информации: положение, размеры, графический примитив, текстуры. Дерево строится, начиная с самых нижних уровней, поскольку только так можно определить, где в пространстве должен быть расположен элемент вышележащего уровня. Данная схема налагает ограничение, что нельзя объектам StructureObject сразу же присвоить абсолютные координаты в пространстве сцены: двигаясь от дочерних объектов вверх, мы даже не можем представить, где окажется родительский элемент. Таким образом, все объекты StructureObject могут быть позиционированы только относительно своего родительского объекта; то есть, у каждого StructureObject есть свое смещение по осям OX, OY и OZ относительно нулевой точки родителя. Выглядит это так:



    На схеме условно изображены два StructureObject: белые панели соответствуют пространству родительского объекта, кирпичные панели — пространству дочернего. Сами по себе StructureObject’ы не отображаются на сцене, но считаются контейнерами для графических объектов (на схеме — синего цвета). Графические объекты позиционируются относительно нулевой точки содержащего их StructureObject. Габариты (размеры) StructureObject являются общими габаритами всех подструктур и нужны для расчетов в родительском элементе. Поле soGeometry имеет тип Geometry. Оно содержит общие смещение и габариты, заданные трехмерным вектором:

    -- Модуль Common.GLTypes
    type Geometry     = (Translation, Dimension)
    type GLfVector3   = GL.Vector3 GL.GLfloat
    type Translation  = GLfVector3
    type Dimension    = GLfVector3


    Аналогичные данные, а также графический объект содержит поле soGraphObjectSpec следующего типа:

    type GraphObjectSpec = (Translation, Dimension, GraphObject)


    Код создания StructureObject обширен и разбит на два модуля. Синтаксические элементы, простые и сложные, преобразуются в объекты StructureObject в модуле Structure.SOConstruct. Первоначально смещение Translation в поле soGeometry приравнивается к нулевому вектору. Мы просто не можем знать, как только что созданный StructureObject расположен относительно родителя, а родитель еще даже не существует, да и не обязательно появится в будущем. Смещение пересматривается позже, в том коде, который создает себе дочерний объект; либо оно просто остается нулевым, — тогда именно этот объект будет ориентиром для своих подобъектов. В коде ниже — создание трех простых объектов («переменная», «платформа», «мост») и одного сложного (инфиксный оператор с аргументами):

    -- Конструируется объект для выражения-переменной:
    constructExp (OcsExpArgument (HsVar var)) = let
        varText      = makeName . getHsQualName $ var
        rawDim       = GL.Vector3 (hsNameLength varText) 2 2
        dim          = derivedDimensions (FuncDimensions variableBoxDims) rawDim
        graphObjSpec = variableBox varText dim
        in StructureObject OsArgument (nullVector3, dim) graphObjSpec []
     
    -- Конструируется "платформа":
    constructFoundation :: ObjectConstructSpec -> StructureObject
    constructFoundation (OcsFoundationExp expSo) = let
        expSoDim     = geometryDim . soGeometry $ expSo
        dim          = derivedDimensions FoundationDimensions expSoDim
        graphObjSpec = foundationBox dim
        in StructureObject OsFoundation (nullVector3, dim) graphObjSpec []
     
    -- Конструируется "мост":
    constructBridge :: ObjectConstructSpec -> StructureObject
    constructBridge ocsBridgeType = let
        dim          = vector3 2 0.25 2
        (graphObjSpec, bType) = case ocsBridgeType of
                        OcsArrowBridge     -> (arrowBridgeBox     dim, OsArrowBridge)
                        OcsEqualSignBridge -> (equalSignBridgeBox dim, OsEqualSignBridge)
        in StructureObject bType (nullVector3, dim) graphObjSpec []
     
    -- Конструируется сложный объект - инфиксный оператор с аргументами:
    constructExp (OcsExpArgument (HsInfixApp exp1 qOp exp2)) = let
        exp1So = constructExp (OcsExpArgument   exp1)
        qOpSo  = constructQOp (OcsInfixOperator qOp)
        exp2So = constructExp (OcsExpArgument   exp2)
        in connectStructureObjects OsInfixApp [exp1So, qOpSo, exp2So]


    Создавая сложный объект, мы должны как-то расположить его дочерние объекты. Понятно, что для разных синтаксических единиц будут разные положения. Нам нужно расчитать и присвоить объектам смещение относительно нуля. Родитель, являясь вновь созданным объектом, будет смещен на ноль (то есть, не смещен вообще), так как мы пока не знаем, насколько сдвигать и относительно чего это делать. Смещения расчитывает функция connectStructureObjects из модуля Structure.SOConnect. В нее передаются вид синтаксической единицы и список подобъектов, созданных ранее. Для каждого случая в функции connectStructureObjects есть свои варианты расчетов.

    connectStructureObjects :: ObjectSpec -> StructureObjects -> StructureObject
     
    -- Соединяются инфиксный оператор и два выражения:
    connectStructureObjects OsInfixApp (exp1So : opSo : exp2So : []) = let
        exp1SoDim@(GL.Vector3 e1dl e1dh e1dw) = geometryDim . soGeometry $ exp1So
        exp2SoDim                             = geometryDim . soGeometry $ exp2So
        opSoDim  @(GL.Vector3 opdl opdh opdw) = geometryDim . soGeometry $ opSo
        exp1Trans    = nullVector3               -- Выражение 1 начинается в нуле родителя
        opTrans      = vector3  e1dl         0 0 -- Оператор сдвинут по OX на длину выражения 1 (находится рядом с ним)
        exp2Trans    = vector3 (e1dl + opdl) 0 0 -- Выражение 2 сдвинуто по OY на длину выражения 1 и длину оператора
        generalDim   = generalizedDimension [ (exp1Trans, exp1SoDim) -- Общие габариты родителя
                                            , (exp2Trans, exp2SoDim)
                                            , (opTrans, opSoDim)]
        newOpGoSpec  = (opTrans, opSoDim, graphObjectFromSpec . soGraphObjectSpec $ opSo)
        newExp1So    = exp1So {soGeometry = (exp1Trans, exp1SoDim)}
        newExp2So    = exp2So {soGeometry = (exp2Trans, exp2SoDim)}
        in StructureObject OsInfixApp (nullVector3, generalDim) newOpGoSpec [newExp1So, newExp2So]


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

    -- Модуль Structure.Dimensions
    generalizedDimension :: Geometries -> Dimension
    generalizedDimension (g:gs) = toDimension (foldr f g gs)
      where
        f ((GL.Vector3 dx1 dy1 dz1), (GL.Vector3 ax1 ay1 az1))
          ((GL.Vector3 dx2 dy2 dz2), (GL.Vector3 ax2 ay2 az2)) =
                 (vector3 (min dx1 dx2) (min dy1 dy2) (min dz1 dz2),
                  vector3 (max (dx1 + ax1) (dx2 + ax2))
                          (max (dy1 + ay1) (dy2 + ay2))
                          (max (dz1 + az1) (dz2 + az2)))
        toDimension ((GL.Vector3 x1 y1 z1), (GL.Vector3 x2 y2 z2)) =
            vector3 (abs (x2 - x1)) (abs (y2 - y1)) (abs (z2 - z1))



    Несмотря на громоздкость функций в модулях Structure.SOConstruct и Structure.SOConnect, я пока не придумал ничего лучше. Вероятно, есть какое-то декларативное решение, но вряд ли кода будет меньше. Существуют и особые случаи, которые трудно вписать в единую декларативную схему; так, согласно дизайну языка, функция выглядит как коробка в один юнит в высоту, а на ней располагаются ее аргументы. Отсюда следует, что для вычисления длины коробки нужно учитывать количество аргументов, их размеры и расстояние между ними. Выражение в графическом языке выглядит в виде пирамиды, а это значит, что, возникают дополнительные расчеты, связанные с выступами каждого нижележащего слоя. Обобщая данную задачу, я создал «механизм наследованных размеров», в котором ключевую роль играет derivedDimensions из модуля Structure.Dimensions. Она принимает исходные размеры элемента, размеры нужных дочерних элементов и алгоритм наследования, выраженный в виде функции высшего порядка, а возвращает новые, «наследованные» размеры. Ниже приведен упрощенный код из функции constructExp пред-пред-предыдущего листинга:

    let
        rawDim = GL.Vector3 1 2 2
        dim    = derivedDimensions (FuncDimensions variableBoxDims) rawDim
    ...


    Здесь rawDim — исходный размер коробки для переменной, а dim — новые, «унаследованные» размеры. Конструктор данных FuncDimensions принадлежит специальному типу данных DerivedDimensions:

    -- Модуль Structure.Dimensions
    data DerivedDimensions = FuncDimensions (GLfVector3 -> GLfVector3)
                           | FoundationDimensions


    Функция derivedDimensions и функции высшего порядка определяются следующим образом:

    -- Модуль Structure.Dimensions
    derivedDimensions :: DerivedDimensions -> GLfVector3 -> GLfVector3
    derivedDimensions (FuncDimensions f) dim = f dim
    derivedDimensions  FoundationDimensions (GL.Vector3 l h w) = vector3 (+ 2) 0.25 (+ 2)
     
    -- Functions to place into DerivedDimensions
    -- | Calculates function box dimensions according to it's argument dims
    funcBoxDerivedDims :: GLfVector3 -> GLfVector3 -> GLfVector3
    funcBoxDerivedDims (GL.Vector3 opl oph opw) (GL.Vector3 fBoxl fBoxh fBoxw) =
        (GL.Vector3 (f opl fBoxh) fBoxh (max opw fBoxw))
      where
        f  op box | op >= box       = op + 1
                  | (box - op) <  1 = op + 1
                  | (box - op) >= 1 = box 
     
    -- | Calculates dims for variable box
    variableBoxDims :: GLfVector3 -> GLfVector3
    variableBoxDims (GL.Vector3 varl varh varw) =
        (GL.Vector3 (if varl < 2 then 2 else varl) varh varw)



    Как видно, для конструктора FoundationDimensions в функции derivedDimensions задан простейший алгоритм, при котором исходные размеры просто изменяются на определенную величину. Длина и ширина увеличиваются на 2, а высота становится 0.25. Более сложные случаи реализовываются с помощью funcBoxDerivedDims и variableBoxDims. Например, dim из того упрощенного кода станет равным GL.Vector3 2 2 2, потому что вычисление сведется к вызову variableBoxDims (GL.Vector3 1 2 2). При надобности можно написать и другие аналогичные функции. Для еще большей интуитивности графического языка я планирую в будущем добавить арность функций. Она будет выглядеть как пазы на коробке; пустые пазы соответствуют каррингу или сечению. Конечно, одного только механизма наследованных размеров будет мало, ведь для определения арности нужен более продвинутый анализ кода, чем простое разложение на синтаксис. Но это уже другая история…

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

    -- Модуль Structure.GraphObjec
    data GraphObject = NoGraphObject
                     | PrimitiveBox GLfVertex3 TextureName
                     | TexturedBox  GLfVertex3 ObjectTextureSpec
                     | GraphObjects [GraphObjectSpec]
      deriving (Show)


    Легко заметить, что у объекта StructureObject может быть как много графических объектов (конструктор GraphObjects), так и не быть их вообще (конструктор NoGraphObject). И это понятно: в дереве AST, отображенном выше, для значения HsGuardedRhss нечего сопоставить графического. Это, скорее, будет контейнер для других объектов, а именно, для правых частей функции, содержащих охранные выражения (Rhss — «right hand sides»). В то же время «реальные» графические объекты пока представлены всего двумя элементами: примитивной коробкой PrimitiveBox и продвинутой коробкой TexturedBox. У обоих коробок есть значение типа GLfVertex3 — это просто размеры, по которым на этапе IV будут созданы текстурированные грани, шесть штук. У примитивной коробки текстура одна, а для TexturedBox возможно задать отдельную текстуру каждой грани. Тип ObjectTextureSpec устроен так:

    -- Модуль Structure.Texture
    data ObjectTextureSpec = BoxTextureSpec
            { quadSideTexes  :: [(BoxSide, QuadColorSpec)]
            , defQuadSideTex :: QuadColorSpec
            } deriving (Show)
     
    data QuadColorSpec = QuadTexture TextureName
                       | QuadPlainColor GLfColor4
                       | NoQuadColorSpec
        deriving (Show)
     
    -- Тип BoxSide описан в модуле Common.GLTypes.
    -- Легко догадаться, что он из себя представляет:
    data BoxSide = SideTop
                 | SideBottom
                 | SideLeft
                 | SideRight
                 | SideRear
                 | SideFront
        deriving (Show, Eq)


    Хотите, чтобы на верхней грани была стрелка, а все остальные были текстурированы по умолчанию? Нет проблем!

    let texes      = [(SideTop, QuadTexture arrowTex)]
        defaultTex = QuadTexture yellowBaseTex
        boxTexSpec = BoxTextureSpec texes defaultTex


    Или только две грани с текстурами, а остальные — каким-нибудь цветом? И это можно.

    let texes      = [ (SideFront, QuadTexture arrowTex)
                     , (SideRear,  QuadTexture arrowTex)]
        defaultTex = QuadPlainColor (color3 1 0 0)
        boxTexSpec = BoxTextureSpec texes defaultTex


    Элементы типа GraphObject строятся с помощью мнемонических функций во время создания StructureObject. Сейчас в модуле Structure.GraphObject имеются следующие функции: primitiveBox, variableBox, functionBox, foundationBox, arrowBridgeBox, equalSignBridgeBox, bridgeBox и guardFrame. Для примера приведу лишь несколько функций:

    -- Модуль Structure.GraphObject
    primitiveBox trans dim@(GL.Vector3 l h w) texName = (trans,       dim, PrimitiveBox (vertex3 l h w) texName)
    variableBox _      dim@(GL.Vector3 l h w)         = (nullVector3, dim, PrimitiveBox (vertex3 l h w) helloTex)
     
    arrowBridgeBox     dim = bridgeBox dim arrowTex
    equalSignBridgeBox dim = bridgeBox dim equalSignTex
     
    bridgeBox dim@(GL.Vector3 l h w) texName =
        (nullVector3, dim, TexturedBox (vertex3 l h w) boxTexSpec)
      where
          boxTexSpec = BoxTextureSpec texes defTex
          texes      = [(SideTop, QuadTexture texName)]
          defTex     = QuadTexture yellowBaseTex




    Отдельно стоит рассказать о системе рендеринга. На данный момент я компилирую графические примитивы в объекты сцены и сразу же их рисую. Это происходит в функции render, которая в составе функции draw вечно крутится в цикле программы. Конечно, такой код неэффективен, ведь при компиляции одного и того же StructureObject-дерева получается одна и та же сцена с объектами, и можно было бы ее подготовить загодя. Никаких препятствий тут нет, к тому же рендеринг и компиляция легко разделяются, если возвращать список действий [IO()], а не выполнять на месте, как это сделано сейчас:

    -- Модуль Draw.Render
    render texRes (StructureObject _ (soTrans, _) goSpec objects) = do
        GL.translate soTrans                   -- устанавливаем относительное смещение
        mapM_ (render texRes) objects          -- рекурсивно спускаемся по дереву
        sequence_ $ compileGraphObjectSpec texRes goSpec -- компилируем примитивы и выполняем OpenGL-вызовы
        GL.translate . negateVector3 $ soTrans -- убираем относительное смещение


    Алгоритм рендеринга рекурсивен. Спускаясь по дереву от коренного StructureObject, мы выставляем все новые и новые смещения для дочерних элементов, а при возврате на предыдущий уровень эти смещения убираем. Функция compileGraphObjectSpec компилирует объект GraphObject в объект сцены. Функция sequence_ выполняет список действий [IO()]. У графических объектов тоже есть относительное смещение, поэтому делаем аналогиные переносы координат:

    -- Модуль Structure.GOCompile
    compileGraphObjectSpec texRes (goTrans, _, go) = let
        forwardTrans  = GL.translate goTrans
        compiled      = compileGraphObject texRes go
        backwardTrans = GL.translate . negateVector3 $ goTrans
        in (forwardTrans : compiled) ++ [backwardTrans]


    Вообще, код в модуле Structure.GOCompile весьма интересен применяемыми техниками (например, свертки и list comprehensions). Конечно, такой код труднее понять, но мне чудится в нем какая-то внутренняя красота и завершенность, ценная сама по себе:

    -- | 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) 
     
    -- | Compiles GraphObject into action list structure, which is ready-to-eval. ([IO ()])
    compileGraphObject :: PreparedTextureObjects -> GraphObject -> [IO()]
     
    compileGraphObject _ NoGraphObject = []
     
    compileGraphObject texRes (GraphObjects gObjectSpecs) =
        concatMap (compileGraphObjectSpec texRes) gObjectSpecs
     
    compileGraphObject texRes (PrimitiveBox boxDim texName) =
        [do GL.color colorWhite
            GL.textureBinding GL.Texture2D GL.$= lookup texName texRes
            GL.renderPrimitive GL.Quads (allBoxSides boxDim)]
     
    compileGraphObject texRes (TexturedBox boxDim boxTexSpec) = let
        (BoxTextureSpec sideTexes defTex) = boxTexSpec
        (textedSides, textedSideDrawList) = foldr (f texRes boxDim) ([], []) sideTexes
        untextedSides                     = [| s <- boxSideList, s `notElem` textedSides]
        untextedQColor                    = setQuadColorSpec texRes defTex
        untextedSidesDraw                 = GL.renderPrimitive GL.Quads (boxSides boxDim untextedSides)
        in untextedQColor : untextedSidesDraw : textedSideDrawList


    Коробки состоят из граней, а грани заливаются цветом или текстурой. В OpenGL какую-либо фигуру можно рисовать повершинно; в нашем случае это будут вершины четырехугольника. Вершины расчитываются из длины, высоты и ширины, содержащихся в dim, причем нулевая точка соответствует углу коробки слева-внизу-сзади (просто потому, что оси в системе координат OpenGL так направлены: OX — вправо, OY — вверх, OZ — на нас). Грани создаются в модуле Misc.BoxSide с помощью функций из библиотеки HOpenGL.

    boxSide :: GLfVertex3 -> BoxSide -> IO ()
     
    boxSide (GL.Vertex3 x y z) SideTop = do
                GL.texCoord texCoordDR >> GL.vertex (vertex3 x y z)
                GL.texCoord texCoordUR >> GL.vertex (vertex3 x y 0)
                GL.texCoord texCoordUL >> GL.vertex (vertex3 0 y 0)
                GL.texCoord texCoordDL >> GL.vertex (vertex3 0 y z)
     
    boxSide (GL.Vertex3 x y z) SideFront = do
                GL.texCoord texCoordUR >> GL.vertex (vertex3 x y z)
                GL.texCoord texCoordUL >> GL.vertex (vertex3 0 y z)
                GL.texCoord texCoordDL >> GL.vertex (vertex3 0 0 z)
                GL.texCoord texCoordDR >> GL.vertex (vertex3 x 0 z)
     
    -- ... и так далее для всех 6 граней.
     
    boxSideList = [SideTop, SideBottom, SideLeft, SideRight, SideRear, SideFront]
    boxSides    boxDim = mapM_ (boxSide boxDim)
    allBoxSides boxDim = boxSides boxDim boxSideList



    Что ж, мы довольно поверхностно проследили общую структуру программы GraphServer. Я не стану описывать, как устроена серверная часть программы, как загружаются картинки из файлов, как из картинок создаются текстуры, как используются сторонние утилиты. Работы еще очень много, сервер визуализации готов процентов на 10. Работа осложняется тем, что далеко не для всех элементов языка Haskell готовы эскизы. Есть трудности и с визуализацией, что очень хорошо заметно на скриншотах; все-таки, отладочные текстуры далеки от идеала. Хотелось бы нормировать растяжение текстур по объекту, украсить, создать что-то более гармоничное, поработать над дизайном. Еще нужны шрифты и рисование строк; в будущем добавится анализ функций на арность, а это очередной рефакторинг, другие подходы, иные методы. И опять потребуются тонкие техники, хитрые алгоритмы, умные структуры данных, которые сами по себе разработать ой как нелегко… Проект масштабный, глубокий и приносящий эстетическое удовольствие. Я приглашаю всех желающих присоединиться к нему: это и практика в Haskell, и опыт в проектировании больших программ, и знания в графике, и изучение алгоритмов. Но прежде всего, это искусство и творчество, — то, что делает нашу жизнь прекраснее.

    Код открыт и расположен на GitHub: github.com/graninas/GraphServer

    Это кросс-статья. О дизайне графического языка читайте статью «Haskell — Дизайн».

    P.S. Просьба к читателям: если вам интересно вступить в проект, обращайтесь ко мне в личку, в аську или на почту. Почта на Гугле, ник такой же, как на Хабре. Если можете, пропиарьте статью среди других любителей Haskell, или среди тех, кто бы хотел его изучить, присоединившись к проекту. Для коллективной разработки понадобятся некоторые адаптации проекта и инструментов. Обещаю подойти к делу профессионально.
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 38
    • 0
      А чем обусловлен выбор Haskell для написания, собственно, визуализатора? Почему не какой-нибудь промышленный язык?
      • +3
        В последнее время я все больше и больше нахожу Haskell удобным для почти любого типа задач. Если бы визуализацию писал на другом языке, у меня бы спрашивали, почему не на Haskell. На самом деле, писать и отлаживать легко. Нелегко только продумать логику. Рефакторинг в Haskell — дело местами даже приятное, чего не скажешь о том же С++. Статическая типизация помогает в этом: если где-то изменил тип выражения, компилятор скажет, какой участок кода нужно подогнать. Исправляешь, — и всё начинает работать ожидаемым образом.
        • +6
          А можно узнать критерии, по которым вы относите Haskell к «непромышленным» языкам?
          • +2
            Чтобы его можно было визуализировать самим собой?
          • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              > Коллега, а что если образцы и охранные выражения визуализировать как фильтры в стенах?
              Почему бы и нет. Надо только помнить, что булевое охранное выражение может быть сколь угодно большим, и для «сути охраны» должно быть достаточно места. Это же касается и сопоставления с образцом. Есть ли у вас возможность набросать эскиз?

              Генераторы списков можно разобрать на части:

              [(x, y) | x < — xs, y < — ys, x `elem` someList, not. empty $ y]

              Шаблон возвращаемого значения(x, y)
              Обязательный символ|
              Источники значенийx < — xs, y < — ys
              Охранные выраженияx `elem` someList, not. empty $ y


              Шаблон визуализируется как обычное выражение. Затем можно поставить вместо вертикальной черты, например, рамку или два столба. Источники значений и охранные выражения — это вертикальные конструкции, идущие подряд. Источники — это выражение наверху (xs), затем натуральная (не текст, а блоки) стрелка вниз, а внизу — блок целевого значения (x). Охранные выражения почти также, только вместо стрелки — горизонтально расположенная рамка с дыркой. Как приду домой, набросаю концепт.
              • НЛО прилетело и опубликовало эту надпись здесь
                • +1
                  Ну, сахарок-то он, конечно, сахарок… А сам do, в свою очередь, сахарок для оператора >>= и лямбд… И при визуализации мы могли бы свести все это к одному и тому же виду. Однако было бы полезно все-таки для генераторов создать индивидуальный дизайн. Конечно, некоторые конструкции будут совпадать, — на то и эквивалентность этих конструкций дана. Но если рассахаривать генератор списков, люди, сравнивая код и визуализацию, будут недоумевать. Впрочем, тут есть над чем поразмыслить.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • +1
                      Про три измерения вы верно заметили. Для эффективного использования пространства нужно придумать хорошие конструкции, что у меня как-то не выходило. Тут еще появляется проблемка: растущие вверх и вширь блоки закрывают другую часть сцены. Приходится пока балансировать.
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • +1
                          Идея замечательная! Про гиперссылки я и не думал.

                          Хммм, а что если сделать не только гипессылки на нужную функцию, но и на визуализированную документацию?
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • +1
                              Пока не знаю, надо бы выяснить…
                • +2
                  Визуализация штука сложная, конечно.
                  Функция — это преобразователь из одного типа данных в другой, и тогда значения одного типа должны выглядеть одинаково (но разные типы — по-разному).
                  А guard — это фильтр значений, т.е. пропускает определённые значения и не пропускает другие, тогда его форма должна зависеть от самого значения.

                  Ну, например.
                  length — тоннель с треугольным входом и квадратным выходом. Входит любой длины треугольная призма, выходит параллепипед. Причём в поперечной оси отражается тип (треугольник — список, квадрат — число) а в продольной — значение.
                  length xs == 0 — guard, который сначала пропускает значение вперёд через length, меняя его тип, а затем поперёк через тоннель, способный пропустить только 0.

                  Список, правда, продвинутый пример, так как он полиморфный.

                  Интересно было бы подумать, не пригодится ли при визуализации математическая запись типов:
                  list(A) = 1 + A * list(A)
                  bool = 2
                  nat = 1 + nat

                  В общем, полезного я мало сказал, но может хоть идей на размышление подкинул.
                  • +2
                    Мысли интересные и правильные, наталкивают на другие мысли.

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

                    data StructureObject = StructureObject
                            { soObjectSpec       :: ObjectSpec
                            , soGeometry         :: Geometry
                            , soGraphObjectSpec  :: GraphObjectSpec
                            , soStructureObjects :: StructureObjects
                            } deriving (Show)

                    ?

                    А вот для декларации типов туннели, может, и подойдут. В любом случае, надо рисовать эскизы сначала. :)
                    • +2
                      Именованный тип от кортежа ничем структурно не отличается, т.е. в данном случае достаточно взять 4 фигурки подтипов и соединить их как удобнее.

                      Вообще говоря если брать мат.запись, то имеются кортеж (product) (A x B), т.е. оба значения, и coproduct (A + B), т.е. одно из значений (Either). Для типов с фиксированным кол-вом значений используют число. Т.е. например Bool — это 2.

                      Пример:
                      Список — голова или хвост, содержащий элемент и список
                      list(A) = 1 + A x list(A)

                      Maybe:
                      maybe(A) = 1 + A

                      Изобразить кортеж, в общем-то, несложно. А вот по поводу coproduct и аналогов Bool надо думать.
                      • +2
                        Может, набросаете по-быстрому пару эскизов?
                        • 0
                          Прямо сейчас времени нет, могу попробовать на выходных набросать.
                        • НЛО прилетело и опубликовало эту надпись здесь
                  • +1
                    Вот, набросал я таки эскиз генераторов:

                    image
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +1
                        Рамка? Охранное выражение. Но тут спорный момент, я долго над ним размышлял.

                        Сбоку — это где?
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • +2
                            Поддержу предложение подумать о возможном смещении отображения от прямого повторения синтаксиса к отображению смысла.
                            Предложу вариант:
                            _X_Y_ [ тут охранное выражение ] X<-XS, Y<-YS
                            • +2
                              Охранное выражение похоже на фильтр. Его можно отобразить в виде «коробки», которая будет иметь квадратное отверстие со стороны x<-xs, т.е. на входе, а сто стороны выхода будет иметь фигурное отверстие. Получится что-то, вроде «из всех xs пролезут только подходящие».
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • +2
                                  Тоже думал над вертикальном расположении «исходников», но охрана может не только X охранять, но и Y вместе с ним. Правда, такую комплексную охрану можно уже после объединяющей скобки поставить.
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                  • +2
                                                    xs           ys
                                                      |             |
                                                     V           V
                                    _x_y_ <- [ x "==" y ]
                                    

                                    (Тут у меня что-то типа стрелок сверху вниз, надеюсь, понятно будет)
                                    • +1
                                      image
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                  • +1
                                    Вот так?

                                    image
                                    • НЛО прилетело и опубликовало эту надпись здесь
                          • +2
                            Если пространство, в котором располагаются объекты, изначально координатное, то скорее всего оно станет сильно разреженным по мере отрисовки кода, а если ему наложить структуру, в самом простом случае задать ячейки для размещения, то оно станет более компактным, а если структуру пространства менять в зависимости от родителя, то компактность еще повысится. Но здесь дерево собирается с нижних уровней, и в связи с этим
                            задать ограничения с верхний уровней для нижних не представляется возможным. Просто возможно возникнут в связи с этим неудобства, например я захотел бы вписать сцену в другой графический проект, с заранее известными ограничениями и на размер и на компактность.
                            p.s.
                            «Как мы знаем, процесс, при котором один язык преобразовывается в другой, называется компиляцией» — мне кажется больше подходит термин «трансляция»
                            • +1
                              Вряд ли возможно строить дерево сверху вниз. Я рисовал и обычные деревья — AVL — там тоже если не знать, сколько места нужно листьям, верхушку не нарисуешь. Для AVL-дерева можно построить формулу, которая будет расчитывать место для любого уровня, поскольку это фукнкция от количества элементов и от номера уровня. Для кода такую формулу не выведешь. Как понять, не будет ли мало пространства 100x100x100 клеток? Если только продвинутым анализом каким-нибудь…
                              • +2
                                Во первых, дочерние элементы в процессе их размещения могут заглянуть к родителю и спросить его: «в чем ты мне предлагаешь отрисоваться (какую ты задаешь структуру пространства)?» вопрос будет не сколько ты мне конкретно предлагаешь места, а относительное место в этом пространстве, во вторых, а кто не использует несколько проходов по дереву для оптимизации построения деревьев в пространстве, если во главу угла ставится компактность. Я думаю этим не стоит брезговать сильно.
                                • +1
                                  Может быть и так, но я не уверен. К тому же для компактизации нужно язык продумать еще сильнее, а может быть даже изменить совсем: чтобы элементы и выразительны были, и могли бы разместиться с оптимальной плотностью.

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