lang-specification.pandoc

<div style="float:left;width:100%;">
<a href='http://lambdacube3d.com'>
<img src='/lambdacube-logo.svg' width="14%" style="float:left;margin: 0 3% 4% 0"/>
</a>

LambdaCube 3D
=============
<a href='http://lambdacube3d.com'>lambdacube3d.com</a>
</div>

Language Specification
======================

LambdaCube 3D is specified as [Haskell98](https://www.haskell.org/onlinereport/) plus various language extensions.

Haskell98 language features
---------------------------

-   algebraic data types (ADTs)
-   special syntax for tuples and lists
-   `case`, `let`, `if` statements
-   lambda expressions
-   list comprehensions
-   operators, operator fixity declarations
-   pattern matching; wildcard patterns
-   function alternatives
-   value definitions (pattern = expression)
-   where-blocks
-   simple recursion
-   type synonyms

Work in progress:

-   type classes
-   module imports and export lists
-   type signatures
-   dot-dot expressions

TODO:

-   mutual recursion
-   irrefutable patterns
-   at-patterns
-   type class defaulting
-   type instance deriving
-   newtype declarations
-   do syntax

There are some diversions from Haskell98. Our plan is to keep this list very short.

-   Different `Prelude`: look at the [API documentation](api-documentation).



Extentions to Haskell98
-----------------------

These extensions are automatically enabled.

### Known extensions

-   [`NoMonomorphismRestriction`](https://ghc.haskell.org/trac/haskell-prime/wiki/NoMonomorphismRestriction)
-   [`NoNPlusKPatterns`](https://ghc.haskell.org/trac/haskell-prime/wiki/NoNPlusKPatterns)
-   [`TypeApplication`](https://ghc.haskell.org/trac/ghc/wiki/TypeApplication)
-   [`KindSignatures`](https://downloads.haskell.org/~ghc/7.6.3/docs/html/users_guide/kind-polymorphism.html)
-   [`EmptyDataDecls`](https://ghc.haskell.org/trac/haskell-prime/wiki/EmptyDataDecls)
-   [`PolyKinds` & `DataKinds`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/kind-polymorphism-and-promotion.html)
-   [`RankNTypes`](https://ghc.haskell.org/trac/haskell-prime/wiki/RankNTypes)
-   `NoImplicitPrelude` language pragma

Work in progress:

-   [`GADTs`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/data-type-extensions.html#gadt) (includes [`ExistentialQuantification`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/data-type-extensions.html#existential-quantification))
-   [`TypeFamilies`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/type-families.html)
-   [`PartialTypeSignatures`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/partial-type-signatures.html)
-   [`ScopedTypeVariables`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/other-type-extensions.html#scoped-type-variables)
-   [`PatternGuards`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#pattern-guards)
-   [`ViewPatterns`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#view-patterns)
-   [`PatternSynonyms`](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/syntax-extns.html#pattern-synonyms)

Planned:

-   [Typed holes](https://wiki.haskell.org/GHC/Typed_holes)
-   [`LambdaCase`](https://ghc.haskell.org/trac/haskell-prime/wiki/LambdaCase)
-   `TupleSections`

### Custom extensions

-   [Tuples as heterogeneous lists](#heterogeneous-lists)
-   [Row polymorphism](#row-polymorphism)
-   [Swizzling](#swizzling)
-   `ImplicitParams`


### Homogeneous and heterogeneous lists

#### Homogeneous lists

`List` has the standard definition:

~~~~~ {.haskell}
data List a
    = Nil
    | Cons a (List a)
~~~~~

Lists has special syntax like in Haskell:

desugared form (in expr. ctx)       type context                            expression/pattern context
---------------------------         -------------                           ------------------------
`'List`                             `[]`                                    `'[]`
`'List` a                           `[`a`]`                                 `'[`a`]`
`Nil`                               `'[]`                                   `[]`
`Cons` a `Nil`                      `'[`a`]`                                `[`a`]`
`Cons` a b                          `'(`a`:`b`)` **or** `(`a`:`b`)`         `(`a`:`b`)`
`Cons` a `(Cons` b `Nil)`           `'[`a`,`b`]` **or** `[`a`,`b`]`         `[`a`,`b`]`
`Cons` a `(Cons` b `(Cons` c `Nil))``'[`a`,`b`,`c`]` **or** `[`a`,`b`,`c`]` `[`a`,`b`,`c`]`
...                                 ...                                     ...

Examples with sytactic sugar:

~~~~~ {.haskell}
    []                  ::  [Int]
    []                  ::  [Bool]
    [True]              ::  [Bool]
    [True, False]       ::  [Bool]
    [1, 23, 4]          ::  [Int]
    [[1], [], [23, 4]]  ::  [[Int]]
~~~~~



#### Heterogeneous lists

Heterogeneous lists has special syntax like tuples in Haskell.  
The only difference is that LambdaCube 3D has special syntax for one element tuples: `((` *element* `))`.

Examples with syntactic sugar:

~~~~~ {.haskell}
    ()                      ::  ()
    ((True))                ::  ((Bool))
    (3, True)               ::  (Int, Bool)
    [(3, True), (4, False)] ::  [(Int, Bool)]
    (((3)), [True, False])  ::  (((Int)), [Bool])
~~~~~

Details:

The `HList` data type is defined as a GADT:

~~~~~ {.haskell}
data HList :: [Type] -> Type where
    HNil :: HList 'Nil
    HCons :: x -> HList xs -> HList ('Cons x xs)
~~~~~

Some of the previous examples without syntactic sugar:

~~~~~ {.haskell}
    HNil                      ::  HList 'Nil
    HCons True HNil           ::  HList ('Cons Bool 'Nil)
    HCons 3 (HCons True HNil) ::  HList ('Cons Int ('Cons Bool 'Nil)
~~~~~

General rules for desugaring:

desugared form (in expression ctx)  type context                    expression/pattern context
---------------------------         -------------                   ------------------------
`'HList Nil`                        `()`                            `'()`
`'HList (Cons` a `Nil)`             `((`a`))`                       `'((`a`))`
`'HList (Cons` a `(Cons` b `Nil)`   `(`a`,`b`)`                     `'(`a`,`b`)`
...                                 ...                             ...
`HNil`                              `'()`                           `()`
`HCons` a `HNil`                    `'((`a`))`                      `((`a`))`
`HCons` a `(HCons` b `HNil)`        `'(`a`,`b`)`                    `(`a`,`b`)`
...                                 ...                             ...



Row polymorphism
================

A.k.a. structural records.  
Row polymorphism is implemented following [Edward Kmett's presentation on Ermine](http://ekmett.github.io/presentations/Functional%20Reporting.pdf).

~~~~~~~~ {.haskell}
v1 = {x: 1.0, y: 2.0, z: 3.0}
v2 = {x: 1.0, y: 2.0, z: 3.0, a: 4.0}

f v = v.x + v.y

r = f v1 + f v2    -- this is valid
~~~~~~~~


Swizzling
=========

[Swizzling](http://en.wikipedia.org/wiki/Swizzling_%28computer_graphics%29) means rearranging the elements of a vector.[^swizzling]

~~~~~~~~ {.haskell}
(V3 1.0 2.0 3.0)%xxzy   ==   V4 1.0 1.0 3.0 2.0
~~~~~~~~

The letters `x`, `y`, `z` and `w` refers to the 1st, 2nd, 3rd and 4th element of a record, respectively.  
It is also possible to use the letters `r`, `g`, `b` and `a` instead of `x`, `y`, `z` and `w`.

<!--

Compositional typing
====================

Compositional typing improves error messages.  
Compositional typing can be seen as a language extension if we suppose that a language description provide information about
ill-typed programs too.

Compositional typing does unification in a bottom-up order:
during typing of expressions it unifies the calculated typings of subexpression.
Doing so, compositional typing avoids the left-to-right (or right-to-left) bias caused by
a substitution state carried by type inference algorithms used today.

As an example, consider the following code (example copied from Gergő Érdi's thesis):

~~~~~~~~ {.haskell}
test x = (toUpper x, not x)
~~~~~~~~

Gergő Érdi made a short survey on the error messages given some Haskell compilers:

-   GHC 6.12: The subexpression toUpper x is processed first.

        Couldn’t match expected type ‘Bool’
        against inferred type ‘Char’
        In the first argument of ‘not’, namely ‘x’
        In the expression: not x
        In the expression: (toUpper x, not x)

-   Hugs 98 seems to process application in the reversed order:

        ERROR "test.hs":1 - Type error in application
        *** Expression     : toUpper x
        *** Term           : x
        *** Type           : Bool
        *** Does not match : Char

-   Helium 1.6 gives the same result as GHC above.

        (1,29): Type error in application
        expression     : not x
        function       : not
        type           : Bool -> Bool
        1st argument   : x
        type           : Char
        does not match : Bool

-   Gergő Érdi's prototype of compositional typing gives the following error message:

        input/test.hs:1:8-25:
        (toUpper x, not x)
        Cannot unify ‘Char’ with ‘Bool’ when unifying ‘x’:
              toUpper x    not x
              Char         Bool
        x ::  Char         Bool


Link to Gergő Érdi's master thesis: [Compositional Type Checking for Hindley-Milner Type Systems with Ad-hoc Polymorphism](http://gergo.erdi.hu/projects/tandoori/Tandoori-Compositional-Typeclass.pdf)

//-->