Monday, July 6, 2020

Watch Me Learn Haskell

I use some good software written in Haskell (Xmonad, Pandoc, ...) and, keen for a new adventure, I delved into it.

The community provides great help for newcomers:

Mind-setting

To mum you can say: Make me a cake, please. To your sister you may need to say: Open the lowest drawer. Take the deep bowl. ...

Programming can be easy and it can be hard. A computer does know very little by itself. So it is hard to tell it what to do. The hard side is to organize, what you need to say to the computer.

The words and the way to organize things can vary between programming languages.

Variable vs Type

Variable comes from "vary", which is the Latin-rooted word for change.

Why a value changes does not matter for the concept of variable,

along (no causality) or due to (causality) space or time or color or whatever
by itself (no causality) or by choosing or selection (causality)

Variable is synonymous to alternatives or choice.

I walk. I run. Both have the "I". This makes "walk" and "run" the values of this variable.

So variable arises due to a common context in which

values exclude each other
values can be selected individually
values can be distinguished

Each of these mean the same. But lets settle with 1, with exclude (exclusive), to characterize (the values of) a variable.

What is a variable in one context is a value in another.

There is a history of various wording with similar to same meaning. variable-value is same as or similar to

a-the
level of indirection
set-element (set theory)
type-term (type theory)

The modelling in mathematics/software involves many levels of indirection. variable-value is a general concept that links the layers.

Type is the aspect that maps the real variable to the representation variable in a computer. Type as the implementation. Type refers to the

amount of memory used for a variable and
the encoding of the values of the variable

The choice of type is restricted by

the requirements of the real variable and
the types offered by the specific computer (language)

In Haskell you can specify the type separately, also later. If you omit it, Haskell will normally make a choice for you.

:{
v::Double
v = 1
:}
v

When you program you map a real variable hierarchy to a type hierarchy.

In C-like languages the type describes a memory area (plus methods in OOP). A variable is an instance of such a type, i.e. a memory location with a specific address. Assignment is placing a value (a bit combination) to the memory area. The name identifies the typed memory area, the variable. This is static typing.
In Python or R, the name identifies a value. The name is a variable in the sense that it can address different values of whatever type. The type associated with a name can change during run time. Assignment is basically naming. This is also called dynamic typing. If there are typing problems, this is only found during runtime (duck typing).

Functional languages are also statically or dynamically typed. Haskell is statically typed, Scheme and Clojure are dynamically typed.

Variable vs Function

Values normally are not random, but occur due to values of other variables. Value occurrences are a function of values from other variables.

Variable-value thus becomes function-(function application). function application is the selection of the value. This is the smallest building block of computing. Computing consists of (execution of) functions, i.e. the mapping from variable to variable.

All values of variables do occur (are exhaustive). The function f is all the couples f={(v,w)|vin V land win W land text{unique}(w)}.

In Haskell this is:

import Data.Char
:{
f 1 = 11
f 2 = 22
f x | x >= 10 = digitToInt (head (show x))
:}
f 23
f 2
f 0 -- Exception: ... : Non-exhaustive patterns in function f

Variables are more fundamental than functions, because you need to have choice first. The function maps this choice, the independent variable(s), to the target variable.

The function does not completely define the target variable, if not surjective. If not surjective the target variable might arise from more functions. The target variable would thus motivate a variable of functions towards it.

The function loses information, if not injective. Then, a common target value links source values, i.e. it produces a topological structure in the source variable.

There are also relations between variables that are not functions, i.e. that are not unique in either direction. Functional description can be restored by introducing new structure variables whose values combine original values according relation.

This produces complexity applicable only for specific contexts and does not have the generality needed in programming. Programming is about choosing, about the values.

Category theory avoids the complexity by not looking at internals: A well defined object gets mapped to another object or itself (id) by a morphism. Morphisms need to be composable associatively (a path uniquely defines the target object).

I use variable instead of set to emphasizing that the important quantity is the exclusive choice the variable allows (the value).

In Haskell the choice is done by a data construction. There can be more data constructors for one type. This allows to use different data layout within one type, while still being statically type checked (ADT).

The object in Category theory could be the value or the variable. The former is a dynamic variable (immutable), the latter is static variable (mutable). The Haskell types are static, but the variables are dynamic.

In Haskell the = is a mapping rather than an assignment. Every application generates a new variable. Every generated value is associated with new memory allocation. To avoid that in critical code, Haskell also has mutable types.

Function composition

Haskell allows to compose functions without mentioning the arguments. This is called pointfree style, as values in mathematics are often called points. No argument values means no points. Ironically the usual composition operator is the point (.).

-- pointfree
sc = sum . sequence [(**2) . sin, (**2) . cos]
sc 2 -- 1.0
-- in this case better:
sc x = (sin x)**2 + (cos x)**2

pointfree is only shorter, if the return value is forwarded to the next function. For other situations there are other function compositions. Functions composing other function are called higher order functions or combinators.

In Haskell a lot of effort goes into the design of function compositions (Monad, Kleisli, Arrow, ...) to allow the elegant pointfree style.

The fundamental building block of computing is function application (selection), but immediately next in importance is how to compose them in a widely applicable way.

Wide application means good abstraction. Abstraction is compression. Compression means coping with less resources, less space, less time, less code, less energy. So effort is well spent, if it allows describing something in a more compressed way.

Functional Programming

Programming is based on mathematics, which is older than computers. We encounter variable-value, functions, etc. in all languages, but especially functional languages like Haskell push you to think mathematically. Code reuse demands abstraction. A good programmer needs to think abstractly, mathematically.

Many languages assume and work on an outside world. This outside world gives instructions their meaning. The "open the lowest drawer" example assumes a kitchen, which can be changed. One can open a drawer, etc ...

A purely functional style describes everything as functions. A function maps input to output without changing the input. In our example, a kitchen would be input and a kitchen with an open drawer would be output.

An output becomes a new input to another function. This function composition produces a time sequence, a natural thread of execution. If there were more cooks (more threads), they would all develop their own kitchens. No coordination needed, which makes things a lot easier. (In Haskell the kitchen would be a Monad.)

A programming style is a way to organize things. Languages can be used for more styles, but their syntax and libraries favor a specific style. A style that is shared in a community is called a paradigm.

Most people are first introduced to languages that favor an imperative style.

Functions in non-functional languages change memory. They have side effects. Some languages call functions more appropriately "procedure" or "subroutine".
Functions in functional programming languages don't change anything. They only map values to other values. They are mathematical functions.

The functional style passes functions around, instead of data.

Haskell tries hard to make you think purely functionally.

Syntax

BNF-syntax of Haskell: BNF

Syntax described by template Haskell: TH

Typing

A simple function type (signature) is:

fun:: Int -> Double

Unlike in C or Java this is a function without side effects, which makes it easier to test.

Not only types, but also variables of types (kind) are possible:

fun:: a -> b

:kind (->)
(->) :: * -> * -> *

-> accepts all type (* = all types). -> maps from two kinds (input) to a third kind (output). -> has other usages as well.

Application is done via a space: fun some_value. There are different types of applications:

application of function
application of constructor
application of constraint

A constructor constructs a type. It is like a function signature without implementation, that can be applied to actual argument values, though. Since it cannot map the actual arguments, it just holds them. Therefore it is like a record in DB jargon, or a struct in C.

The implementation for the signature fun:: a -> b would be fun pat = rhs.

pat could be just a letter, e.g. x, which is a variable for any actual argument value during application.
Or pat could be a constrained pattern to address contained variables like x:xs or AConstructor x.

The rhs is the last entry in the function type definition. The expression for rhs depends only on the lhs arguments (e.g. on x). Within the code of rhs further functions with variables can be declared.

Via this containment of functions, context is built.

If the rhs introduces new variables, the application of a function is the application of context.

Currying: fun application is like walking along a path between variables. A (partial) walk on the path (a section), i.e. partial application, produces a function, that walks the rest of the path.

flip or infix notation allows to curry also on the second argument.

Many functions in Haskell are of higher orders. Higher order functions combine (compose) functions to new functions (combinators) without the need to mention the variables.

In:

( . ) :: (b -> c) -> (a -> b) -> a -> c

( . ) has two lhs arguments
(b -> c) and (a -> b) match functions

When applying ( . ) you don't need to mention the variables of type a, b, ....

In:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

f is constrained to the Applicative class.
The constraint between :: and => is called Context.
The actual f must be a data type that is instance of Applicative and cannot be a single function.
f with space is a pattern for an application. Here it is a constructor application for the type implementing Applicative.
f (a -> b) is the pattern for the first argument to extract f, a, b.
f a is the pattern for the second argument.
The last argument f b is the type of the return value.

In:

(<$>) :: Functor f => (a -> b) -> f a -> f b

(<$>) has two lhs arguments
(a -> b) is the pattern for the first argument: a function.
f a is a constructor pattern for the second argument: a data type.
f stands for a class (= variable of types = kind)
Functor is a class.
Functor f constrains f to types with the Functor class

The implementation of (<$>) would construct a value using an actual f constructor.

[] is a type, which implements both, Applicative and Functor.

Usage:

[ (*3), (*6) ] <*> [3]
((*) <$> [ 3, 6]) <*> [3]
-- -> [9,18]

In Haskell a lot of typing is done via function signatures:

functions :: signature
class is more signatures (interface)
a data or newtype type can be made instance of more classes

:{
data ABType = ABType
class AClass a where
  afun:: a -> a
class BClass b where
  bfun:: b -> b
instance AClass ABType where
  afun = id
instance BClass ABType where
  bfun = id
fun:: ABType -> Int
fun ab = 1 -- just to make the compiler happy
:}

id is the Haskell function for identity
Type and class names must start with capital letter.

ABType is a type constrained to two classes:

fun:: ABType -> Int

is equivalent to:

fun:: (AClass ab, BClass ab) => ab -> Int  -- Int is a type

Actually using (AClass a, BClass b) => would need the FlexibleContexts extension.

Int is a type that is constraint to these (type) classes:

:info Int
type Int :: *
data Int = GHC.Types.I# GHC.Prim.Int#
        -- Defined in ‘GHC.Types’
instance Eq Int -- Defined in ‘GHC.Classes’
instance Ord Int -- Defined in ‘GHC.Classes’
instance Enum Int -- Defined in ‘GHC.Enum’
instance Num Int -- Defined in ‘GHC.Num’
instance Real Int -- Defined in ‘GHC.Real’
instance Show Int -- Defined in ‘GHC.Show’
instance Read Int -- Defined in ‘GHC.Read’
instance Bounded Int -- Defined in ‘GHC.Enum’
instance Integral Int -- Defined in ‘GHC.Real’

Keywords

The top level declarations, ordered by importance, are:

<gendecl> | <fundecl> | data | instance | class | module | newtype | type | default

gendecl: Function signature (fun ::) or fixity.
fundecl: Functions use no keyword (read from left to right)
data, type, newtype are data related (read from right to left)
class, instance are type related
module, default are organizational

Keyword meaning:

module .. where is used to specify what is exported by a file, then where and the details follow
default(Int) or used in extensions, like DefaultSignatures
data atype = rhs introduces a type name that on the right hand side has possibly more constructor names
newtype Key = Int similar to data, but only one constructor allowed, which is seen by the compiler, but not in runtime
type Key = Int creates a type synonym for the user, which is not seen by the compiler
class <Aclass> <params> where is a container of function signatures
instance <Aclass> <atype> where declares an implementation of a class for a type. Implementation can be done automatically using deriving.

Data

data can have named values (enum):

data Move = Walk | Run
let move = Walk

speed Walk = 5
speed Run = 10

:t speed
-- -> speed :: Num p => Move -> p

Constructors Walk, Run map to a type (Move). Literals have a type. Haskell can infer the function signature.

Note the difference between type (data,newtype,type) and constraint (class,instance):

type (Move here) is directly used in the signature
p is constrained to class Num, which is more general, than using type Int or Double.

Constructors can be parametrized:

data Person = Person String Int deriving (Show)
let guy = Person "Buddy" 44

The parameters (fields) can be named, but actually it is naming the accessor function.

data Person = Person { nickname :: String, age :: Int} deriving (Show)
let guy1 = Person "Buddy" 44
let guy2 = Person { nickname = "Jo", age = 33}
nickname guy2
-- -> "Jo"
guy2 { age = age guy2 + 1}
-- -> Person {nickname = "Jo", age = 34}

data with one constructor and more fields is called a record.

data Shape location size = Rectangle location size | Circle location size deriving Show
:t Rectangle
-- -> Rectangle :: location -> size -> Shape location size
data Size = Small | Medium | Large deriving Show
data Location = Inside | Outside deriving Show
let ri = Rectangle Inside
:t ri
-- -> ri :: size -> Shape Location size
let ris = ri Small
:t ris

You cannot do Shape Inside Small, because ambiguous.

Different data constructors (rhs) are grouped by the common type constructor (lhs). This is called algebraic data type (ADT).

data can use recursion.

Code

An example

data Speed = Slow | Fast
data Move s = Walk s | Run s

:{
speed:: Num a => Move Speed -> a
speed (Walk Slow) = 5
speed (Walk Fast) = 10
speed (Run Slow) = 11
speed (Run Fast) = 15
:}

speed (Run Fast)
-- -> 15

:t speed
-- -> speed :: Num a => Move Speed -> a

lhs

Function: One or more declarations that map from the left-hand-side (lhs) to the right-hand-side (rhs).

' can be part of a function name. Combinations of !#$%&*+./<=>?@\^-~| and Unicode symbols can be used as function symbols (fop).

Every lhs = rhs has its own namespace. So never consider the argument naming when comparing two (related) declarations, because it just confuses you, if you see the same name for unrelated things.

lhs can be infix:

pat `fun` pat = rhs
pat fop pat = rhs

Or prefix:

fun pat = rhs
(fop) pat = rhs

lhs can contain guards (|). There can be a where at the end of the guards:

-- in ghci :{:} is needed
:{
aad a|a<0  = a-1
aad a|a>0  = a+1
aad a|otherwise = a
:}
-- equivalent to
:{
aad a|a<0  = a-1
     |a>0  = a+1
     |otherwise = a
:}
aad (-1) -- use () with negative numbers
-- -> -2
aad 1
-- -> 2
aad 0
-- -> 0

lhs can contain patterns with sub-patterns (pat). Patterns are built of:

_
(Constructor _) -- brackets is a good idea!
n@(Constructor _) -- rhs uses n
[a]
(x:xs)
!pat -- match now, not lazily
~pat -- always match (irrefutable), if you know it to succeed

n, a, x, xs are arbitrary names that can be used in the rhs. Constructor refers to an actual constructor. _ is anything.

Patterns are evaluated lazily by default. Lazy can mean a lot of memory consumption. It evaluates until the first constructor is found and then needs to remember the arguments (thunks) before trying other evaluation paths. Using ! avoids that.

rhs

The rhs declaration is an expression (exp) with helper declarations either before:

fun pat = let ... in exp

or after:

fun pat = exp where
  ...

The helper declarations can be in layout style:

... where
  recl1
  ...
  declN

where {decl1;...;declN}

where can also be used in class and instance declarations.

exp is application of functions

fun a b or a `fun` b or (fop) a b or a fop b. To name functions with symbols (fop) is normal in Haskell.
fun $ pat avoids brackets by reducing fixity to 0 (see :info $)
fun $! pat evaluates pat before applying fun

Fixity of an operation is set with infixl|infixr|infix <fixity> <fop>.

:{
fsum (x:xs) y = fsum xs $! (x+y) -- same as: (x+y) `seq` fsum xs
fsum [] y = y
:}
fsum [1..100] 0

These can use patterns on the left side:

= is a mapping
<- names values from a generator
-> replaces = in local scopes (e.g lambda \x -> x*x)

Some other operators:

== and /= mean equal or not equal
\ introduces a lambda function (function without name)
: prepend element in a list (1:[2])
| is a guard, used in declarations and list comprehensions
.. generates a sequence of values based on a partial sequence
. module.sub-module or, with spaces, composes functions

let s = [x*x | x <- [1, 3 .. 9]]
s !! 2
-- -> 25
zip [1 ..] s
-- -> [(1,1),(2,9),(3,25),(4,49),(5,81)] 
take 3 $ [0,5 .. ]
-- -> [0,5,10]
cycle [3,6 .. ] !! 4
-- -> 15
iterate (1+) 2 !! 3
-- -> 5

Further, code can contain:

if exp then exp else exp

case exp of {alternatives}

do {statements}

Only if-then-else has expressions.
case alternatives are maps that use -> instead of =.
statements use <-, if at all, and can use = only in an optional where.

do is syntactic sugar for a Monad binding operator (>>=), which forwards output of the function in the previous line to the input of the function in the next line, to allow imperative style fragments. It is not imperative, though, but function composition. Function composition is Haskell's way of a sequence, intermitted with let or where for cases in which not the full output is needed as input. Monad is detailed further down.

Class

class contains function types and possibly default implementations. Class is short of type class, in the sense that more types are instances of a class.

An instance provides implementations of the functions of a class for a specific data type. Instances for one class can be scattered across many modules. import xyz() imports only the instances.

class A1 a where f:: a -> a
class A2 a where g:: a -> a
data D = D Int
data E = E Int
instance A1 D where f (D n) = D (n+1)
instance A2 E where g (E n) = E (n+2)

:{
ff:: A1 a => a -> a
ff u = u
:}

dd = let d = D 3 in ff d
dd = let e = E 3 in ff e -- error: No instance of (A1 E)

If we make E an instance of A1, there is no error:

instance A1 E where f n = n
dd = let e = E 3 in ff e

When a module imports a class, its functions become public.

The function is constrained to the class, in which the function was declared.

Prelude>   :info (<*>)
type Applicative :: (* -> *) -> Constraint
class Functor f => Applicative f where
  ...
  (<*>) :: f (a -> b) -> f a -> f b
  ...
        -- Defined in ‘GHC.Base’
infixl 4 <*>
Prelude>   :info (<$>)
(<$>) :: Functor f => (a -> b) -> f a -> f b
        -- Defined in ‘Data.Functor’
infixl 4 <$>

Starting from ghc/libraries/base/Prelude.hs one can follow included modules. ghc/libraries/base/GHC/Base.hs declares:

Semigroup, Monoid, Functor, Applicative, Monad, Alternative, MonadPlus

Here some example usages for Prelude classes:

:info Semigroup
[1,2] <> [4,5]
-- -> [1,2,4,5]
:info Monoid
[1,2,3] <> []
-- -> [1,2,3]
:info Functor
(+10) <$> [1,2,3] -- or fmap
-- -> [11,12,13]
:info Applicative
(+) <$> [1,2] <*> [3,4] -- same infixl 4
-- -> [4,5,5,6]
1 <$ [1,2,3]
-- -> [1,1,1]
liftA2 (+) (Just 1) (Just 2)
-- -> Just 3
(+) <$> Just 1 <*> Just 2
-- -> Just 3

Since functions are passed around in Haskell, type classes have functions that accept functions as arguments and apply them to the data. This result in classes (Functor, Applicative, Monad, ...) that you don't see among the interfaces of data oriented languages.

The full usage intention behind a class cannot be read from the function signature. Additional laws (see Typeclassopedia) can be the basis for further thinking to grasp the intended generality.

(<>) :: Semigroup a => a -> a -> a is binary. That we stay within the same type (a) (closedness) makes sure that the associative law stays. The associativity law (a <> b) <> c == a <> (b <> c) allows to infer

that the time sequence does not matter (one could calculate chunks of a chain in any order or in parallel) and
that consequently the space sequence fully identifies the result

A law like this is quite general, but still reduces all possible cases quite a bit, and thus has information.

Monoid adds the empty. A neutral element allows usage of the concept where there is nothing fitting to it. The neutral 0 allowed the transition from roman numerals, where the quantity grouping had to be named, to position coded numbers, where you place a 0 in a position, if the value of the position is not there.

(<$>) :: Functor f => (a -> b) -> f a -> f b

injects a function a -> b (first argument)
into a constructed/derived type (second argument)

<$> is also called fmap (functor map). A functor maps one category into another. This is also called lifting (liftA, liftA2, ...).

(<*>) :: Applicative f => f (a -> b) -> f a -> f b assumes a lifted function, which is then applied in the new category.

<$> lifts the arguments and applies the function.
pure just lifts, without looking at the arguments.
<*> only applies.

So Applicative splits a Functor's fmap into two parts.

import GHC.Base
( (*) <$> [2, 3] ) <*> [6,7]
liftA2 (*) [2,3] [6,7]
-- all -> [12,14,18,21]
fmap (*10) [6,7]
liftA (*10) [6,7]
pure (*10) <*> [6,7]
-- all -> [60, 70]
pure (*10) *> [6,7]
[6,7] <* pure (*10)
-- all -> [6, 7]

import Control.Applicative
:{
digit :: Int -> String -> Maybe Int
digit _ []                     = Nothing
digit i (c:_) | i > 9 || i < 0 = Nothing
              | otherwise      = if [c] == show i then Just i else Nothing
:}
digit 0 "01"
-- -> Just 3
digit 1 "01"
-- -> Nothing
binChar s = digit 0 s <|> digit 1 s
binChar "01"
-- -> Just 0
binChar "10"
-- -> Just 1

Alternative adds the idea of Monoid to the Functor-Applicative line, with <|> instead of <> (Typeclassopedia). It also implements some and many. They are only useful for types where the constructor calls a function that processes input: a parser.

some stops when the first empty is constructed, and
many continues recursive application of the constructor beyond empty

Monad

A monad constructs and forwards context.

In a functional programming language context is built via the parameters of contained functions.

import Control.Monad
:info Monad

(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a

In:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

m is a constructor of a type that is instance of the Monad class
m a is NOT a constructor application but a pattern matching to extract m and a
a -> m b is a pattern against a function with target m b. Let's call it k.
>>= needs to map to what k maps to, i.e. apply k a. The implementation from Maybe: (Just x) >>= k = k x

In a do

a <- exp [args]; nextexp stands for exp >>= (\a -> nextexp)
exp [args] constructs a value that would be pattern matched using m a
>>= composes a <- exp [args] with the next expression
>> composes exp; nextexp

return :: Monad m => a -> m a

return is basically the same as m, but since m can be any constructor it is good that we can refer to it generally with this one name.

`->` is a Monad

-> constructs a type via lambda encapsulation (currying).

instance Monad ((->) r) where
    f >>= k = \ r -> k (f r) r

f is the application so far (a lambda)
k is the next ->
k is applied to what was before (f r) and what comes after (r)

IO is a Monad:

do {putStr "Hi"; putStrLn " there!"; }
putStr "Hi" >> putStrLn " there"
readLn >>= print

`[]` is a Monad

You can use this to do SQL like queries.

sel prop vals = do {val <- vals; return (prop val);} -- @val <- vals@ needed
data Name = Name { firstName ::String , lastName :: String } deriving Show
children = [ Name "Audre" "Lorde", Name "Leslie" "Silko", Name "Jo" "Silko"]
sel firstName children
-- -> ["Audre","Leslie","Jo"]
import Control.Monad -- for guard
wh test vals = do {val <- vals; guard (test val); return val; }
wh (\s->'A'==(head s)) (sel firstName children)
data Family = Family { name ::String } deriving Show
families = [ Family "Lorde", Family "Silko" ]
jn d1 d2 p1 p2 = [ (d,e) | d<-d1, e<-d2, p1 d == p2 e]
jn families children name lastName
sel (firstName.snd) (wh (((==) "Silko").name.fst) (jn families children name lastName))
q s j w = s (w j)
q (sel (firstName.snd)) (jn families children name lastName) (wh (((==) "Silko").name.fst))

`State` is a Monad

import Control.Monad.State
runState (do { put 5; return 'X' }) 1
-- -> ('X',5)
evalState (gets (+1)) 1

`Maybe` is a Monad

import Data.Maybe
catMaybes [Just 3, Nothing, Just 9]
-- -> [3,9]

:{
printLengthPrint :: Int -> Maybe Double
printLengthPrint = \w -> Just (show w)    -- :: Int -> Maybe String
               >>= \x -> Just (length x)  -- :: String -> Maybe Int
               >>= \y -> Just (2.0 ^^ y)  -- :: Int -> Maybe Double
:}
printLengthPrint 32
-- -> Just 4.0
:{
f :: Int -> Maybe String
f = Just . show
g :: String -> Maybe Int
g = Just . length
h :: Int -> Maybe Double
h = Just . (2.0 ^^)
:}
import Control.Monad
plp1 = h <=< g <=< f
plp1 32
plp2 = f >=> g >=> h
plp2 32

Monad transformer

A Monad transformer constructs a Monad from other monads.

The monad transformer library (mtl) is part of the ghc.

Extensions

The Haskell standard gets updated only every 10 years. Development in between can get activated via extensions.

{-# <EXTENSION>, ... #-}
-- or GHCi:
:set -X<EXTENSION>

Here some common ones from the GHC extension list:

OverloadedStrings: When using Data.Text instead of String
FlexibleInstances: nested types in head of instance
FlexibleContexts: class context of kind class (Cls1 a, Cls2 a) => ...
AllowAmbiguousTypes: let call decide and not ambiguity checker
ViewPatterns: include function result in pattern match
PaternSynonym: e.g. pattern NoBlending = #{const SDL_BLENDMODE_NONE} :: CInt
RecordWildCards: f (ARec{..}) = e1 ... instead of f (ARec e1 ...) = e1 ...
NamedFieldPuns: when matching against less fields: f (ARec{ex}) = ex instead of f (Arec{ex=ex}) = ex
DeriveFunctor: deriving Functor derives functor instance
TypeApplications: specify type when called, e.g. show (read @Int "5")
BangPatterns: f (!x,y) strict (not lazy) in x but not in y
MultiParamTypeClasses implies FunctionalDependencies: class C a b ...| a b -> c
LambdaCase: \case { p1 -> e1; ...; pN -> eN } for \p -> case p of {...
BlockArguments: when (x>0) do ... instead of when (x>0) (do ...)
MonadComprehensions: [ x+y | x <- [1..10], y <- [1..x], then take 2 ] (comprehension for all monads)
RebindableSyntax: bind to whatever in scope and not to Prelude
TransformListComp: in list comprehension then f [by|using field] (f=sortWith|group|..)
GADTs: constructors as parametrized constrained type functions
TypeFamilies: type function within class to let instance compute the type
TemplateHaskell: compile-time macros to generate Haskell code

24 GHC Extensions gives alternative examples to some extensions.

Haskell has no Sequence, Loop, OOP

Object-oriented programming (OOP) gives different data a common interface to be passed to functions. In Haskell, interfaces are called (type) classes and they give different data a common way to inject (e.g. liftM) and compose functions on it (e.g. >>=).

Haskell is about composing functions:

sequences are replaced with function compositions
loops are replaced with recursive function compositions
if-then-else and case could be functions

Compared to OOP in Haskell:

type class is what interface is in OOP.

class can also have function implementations (default implementations).
data or newtype is the object type called class in OOP.
- They can have more constructors and recursive constructors
- They can have fields that are
  - other data types (corresponds to OOP inheritance)
  - functions (runtime polymorphism in OOP)
An instance constrains a data type to a class.

Note the shift of meaning of class and instance respect to OOP:

OOP: interface - class - constructor to memory
Haskell: class - instance, data - constructor to memory

Pattern matching is a way to associate code to data without an instance declaration.

There is the Lens library to allows access fields in OOP style (needs an install: cabal install --lib microlens-platform).

Generic programming in called parametrized polymorphism in Haskell, as it is done via parametrizing types and classes

parametrized data (ADT), extended through GADTs
parametrized class, extended through MultiParamTypeClasses

GHC.Generics allows to derive instance methods for user classes based on a generic implementation, similar to .. deriving (Eq,Ord,Show) for built-in classes.

Extensions:

DeriveGeneric: deriving Generic generates instance Generic <usertype> ...
DefaultSignatures: change signature of class default implementations
DeriveAnyClass: allows deriving (<UserClass>)

Then there is template meta-programming with TemplateHaskell, to create Haskell code on the fly, like a C macro.

Epilogue

To program functionally, in data and code, express yourself with

pattern matching functions
recursion
currying
pointless

It is a path with problems, too, and their solutions, an evolutionary branch of programming.

Thursday, October 24, 2019

plan do test

Inform

Tradition

rstdoc uses documents like

(risk) analysis (ra)
system requirements (sr)
detailed design (dd)
test plan (tp)

Similar documents based on the waterfall requirement-design-implementation-verification are quite common.

But many alternative, more agile methods have surfaced, for a reason.

Evolution

A general approach starts from the evolutionary mutation-selection. Considering encapsulations, this leads to

plan
do
test

until fit.

Development goes in cycles of varying size:

all of them are pdt
the waterfall requirement-design-implementation-verification is a pdt cycle of pdt cycles.
usage is the ultimate test and brings maintenance cycles
system alternatives eventually end the life cycle with deprecation, obsolescence and death/extinction

pdt is general, including the horizontal waterfall, but following cohesion, vertical cycles, i.e. by topic, are preferred. pdt is agile.

Plan

Encapsulation: pdtevolution

Creation (of a variable) and selection (of a value) in evolution corresponds to trial-and-error.

All systems evolving, do so by trial and error.
Every algorithm is trial-and-error. Good algorithms have less trials.

To save energy evolution produces

encapsulations

Information flow is energy. Within encapsulations information flow is more efficient, which makes encapsulations more economic.

An encapsulation has input-processing-output. Information flow between encapsulations (input, output) is minimal:

the interface is minimal

There are two orthogonal encapsulation lattices (topologies).

Unit is used for the physical topology.
- Departments and ultimately the developer are organizational or processing units. They are physical units.
- Reality and mind are different physical units.
- Different organizations are different physical units.
Node is used for the content topology.

We concentrate on the content topology.

Development: pdtevolution

With shorter and less roman wording, evolution consists of make-test steps.

creation-selection = make-test

When we consider physical units, we have e.g.

make-test in mind: plan
make-test in reality: do

Compared to trial-error, trial=plan,do. plan,do emphasizes the two units and the interface between them (,).

The mind needs to have a good map of reality,

to create a plan that fits
to minimize the interaction between these two physical units

The map of reality evolves with reality. So there needs to be feedback. The feedback is called test here.

Compared to trial-error: error=feedback=test Test is more neutral than error. It is an obvious evolutionary step of the map, to sync up with reality.

The syncing needs to happen often, if the reality changes often. The same for seldom.

Content: pdtevolution

Development is mapped to development documentation

to organize thoughts
to communicate with others
to decrease the dependence of a project from processing units.
to stay consistent over time despite
- swap of processing units
- memory loss of processing units

Note, that there is also system documentation, which is not considered here.

In the content topology, plan-do-test are all documentation texts, i.e. words that link to concepts, that are either up or down:

up: more general (less variables)
down: more concrete (more variables)

Content items are elementary nodes. They are grouped to content files or directories. All of them are content nodes.

The test is the environment of the do and gets constructed in parallel or before the do to check the do against the plan.

plan = uplinks
do = downlinks
test = uplinks

plan-test forms a brace around the do.

Code is regarded as documentation using a programming language. There is no need to duplicate that with a human language.

Human language descriptions have
- plan: uplinks to the human context in which the system is to be integrated
- do: downlink to what needs to be done to make the system useful
- test: uplink to verify that what was done is well integrated
Computer language descriptions (code) has its own pdt's with possibly many further layers
- plan: uplink to the do of the human description arguing for a specific do on this node
- do: downlink, e.g. via an interface, to more detailed implementation
- test: uplink to the do of the human description using the do of this node, e.g. this interface

Content nodes are grouped

vertically (more abstraction layers into one document)
horizontally (by topic)

For a software project vertical groupings are

pdt documents
the code (possibly in more pdt groupings)

Cycle: pdtevolution

plan,do,test is a development cycle.

Cycle instead of loop emphasizes that plan,do,test needs to repeat in time.

To link the content nodes between processing units, an additional

inform is a minimal non-technical document

Development in regular expressions is (inform plan do test )* or

p'=(pdt)*
d'=(pdt)*
t'=(pdt)*

i - inform, initiate, inception, abstract, purpose
p - plan, motivate, analyze, model, drive, optimize, qualify, why
d - do, specify, describe, interface, commit
t - test, verify, validate, inspect, review

If only one organizational unit is involved,

the i is dropped. This is the case for more detailed nodes done by one developer: (pdt)*.

For mere information between organizational units

the pdt is dropped

Method: pdttradition

Development follows the content links:

vertical links are coherent, while
horizontally we might just have a listing of unrelated parts

It is natural to have a development, where every cycle deals with the full vertical stack, unless the vertical links are costly.

Change of physical unit is costly. It is a change of physical unit, e.g.

when something is physically executed
when another developer or organization is involved

If switching physical unit is done just once, the processing unit ensures success, by simulating using its map of reality

construct the map
test the map
use the map

Using the map consists of

pdt cycles where each
encompasses most of the vertical abstraction stack.

Traditional methods derive from the link cost.

For software development by one or a few developers links are cheap. Agile methods are preferred.
You build a house using the waterfall method.
For Software, if the organizational responsibilities do not reflect the content structure, e.g. interface design by a separate organization, then waterfall is better than agile.

Despite the name in waterfall each layer is stabilized separately, i.e. horizontal development.

Processing: pdtevolution

Ideally there is one developer per pdt cycle.

A developer (initial processing unit) creates a topology on the content in a maximum cohesion - minimal coupling way.

This can be mapped to further processing units (organizations or developers). The resulting sacrifice in efficiency can be minimized, if their interactions are

minimal, but
still in place to operate the plan-do-test cycles

The map between content nodes and processing units should stabilize quickly and be kept stable to reduce

information flow between old and new processing units

memory loss (as documentation is never perfect)

loss of methodical consistency

reorganization of communication channels

Organizational changes are more costly than content changes.

UID: pdtevolution

Easy addressability reduces repeated formulation and thus effort.

pdt permeates down to the most detailed content, which is an atomic variable.

Detailed content items are split into 3 separate items (pdt) if there is an m-n relation between each two.

All content nodes have a UID to make them addressable. Instead of repeating, one makes a link with the UID (DRY).

The UID can be considered as a DSL word for the project domain. It is like an identifiers (IDs) in a programming language.

Infrastructure: pdtevolution

New structure builds on existing longer-living infrastructure.

Processing units need infrastructure (e.g. office, tools, communication channels, methods, pay, ...)
Content needs infrastructure (processing units, format, repo, ...)

The content for the development

of one system
is in one repo

Why:

content encapsulation by maximum cohesion
organizational communication
scope for UID

A distributed VCS is used.

Why: organizationally and technically

more independent
less coordination needed

The repo is accessible to all physical units linked by the system (developers, users).

Why: The Repo

is the communication hub
is an easily findable, single point of information on the system
avoids construction of separate communication channels
avoids repeated interactions on costly link, especially between users and developers.

Continuity: pdtinfrastructure

Continuity is very important. Every living species on earth is

the tip of more than 3 billion years of continuous development
an information channel through 3 billion years of changing environments

The end of a system does not mean the end of its parts. What is part is just a question of perspective. But in general, for a system to get versatile (advanced), one needs to keep up the continuity of development.

Continuity asks for a stable infrastructure.

Do

Repo: pdtinfrastructure pdtencapsulation pdtcontent pdtuid

git is used as VCS, because it is distributed and popular.

A git branch must not contain old and new versions in parallel. Git is for versioning.

Cooperation is done over the internet via a central git repository. All branches are pushed to the central repo.

Github/Gitlab/Butbucket/SourceForge support issues.

Issues are for feedback from the users.
pdt documents are used for development cycles that need more planning.

Project forking dissipates effort. Repo maintainers need to react timely

on issues or
on pull requests

to prevent project forking.

Repo forking is part of normal development. Those without write access to the central repo,

work on their own forks and
contribute pull requests

The source tree tries to stay flat. Example entries:

pdt: for pdt enhancements cycle, each in an AAA subdir
doc: system documentation for API, libraries, GUI,...; tutorials
c: platform neutral code in in C or C++
python: python bindings
test: test scripts

The build tree is outside of the repo tree.

Development Documentation: pdtcontent

rstdoc is used to a have

all information as hyperlinked text
documentation as python code (.stpl)
support of many graphic DSLs
convertibility to many other formats

Documentation as code allows to

generate documentation from different sources (code, system documentation, development documentation)
reuse or generate boilerplate text
create graphics in line with text

pdt cycle documentation:

The repo has a top level folder for pdt's (optionally named pdt)
Every cycle gets an AAA folder below pdt, e.g. 011. Usage of base36, .i.e 0-9A-Z, keeps the UID short.
A normal cycle has 4 documents below AAA:
- i.rest.stpl
- p.rest.stpl
- d.rest.stpl
- t.rest.stpl
Informational entries have only an i document (pdttype).

Project-relevant content is in paragraphs with a project-wide unique ID:

.. _`xAAABB`:

with A,B base36 and x∈{i,p,d,t}.

See the sample project generated with rstdoc --ipdt tmpipdt.

A document looks like this:

.. _`i001`:

%globals().update(include('pdt.rst.tpl'
%,Title="Development Process"
%,Type="inform"
%))

.. _`i001header`:
%__i001_('header')

.. _`i001keywords`:
%__i001('key words')

Item content.

__i001() numbers the BB part. Reference to items between RST documents is done with |i001keywords|. Reference targets are not generated to allow rstdoc to create .tags that point to the .rest.stpl instead of the .rest.

i.rest.stpl contains

pdt fields (pdtfields)
a short non-technical introduction to the context (problem, goal, purpose).

A is a base36 letter (0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ)

pdt fields:

The necessary fields are

PDT - The AAA pdt number
Contact - instead of author, as the authors are documented via git
Status - see pdtstatus
Type - see pdttype
Created - as a hint to how old the pdt is.

pdt status:

drafting - work in progress
draft - initial state until discussed and/or implemented and tested
final - consistent with the rest of the repo or agreed upon
replaced - for a conflicting change a new pdt replaces a final one
deferred - possibly because other things are prioritized
rejected - after a discussion the majority decided not go that way
withdrawn - the one who proposed the pdt changed his mind

pdt type:

pdt - Enhancement to the project
inform - Informs about processes or workflows, or anything not having a pdt cycle

The inform type does not have a development phase. There can be just one file. After discussion it goes to final or another status.

Workflow: pdtprocessing pdtmethod

First add an pdt/AAA directory to the develop branch, directly if with write access, else via pull request.
Let peers and yourself review and change the pdt content in their local forks.
Make pull requests until pdt status is final in the develop branch of the central repo.
Add an AAA feature branch.
Do development until stable.
Merge develop into AAA regularly to stay up-to-date, and specifically before declaring that AAA is ready.
When AAA is ready, the AAA branch is first merged to the develop branch.
When develop is stable, i.e. tests pass, the develop branch is merged to the master branch.

Active pdt's are those where

pdt/AAA exists in the develop branch and
an AAA git branch exist

Done cycles have their branch deleted. Whether merged or not, the pdt/AAA folder stays.

Non-dependent cycles can run in parallel.

Plan: pdtcontent pdtcycle

plan items considers the current state:

input from above
experience
examples
simulations (separate pdt's)

plan items create alternatives by

abstraction (analysis) and
combination (synthesis)
analogy

plan items motivate choice (why).

plan items are testable.

Alternatives are (stepwise) reduced to 1 choice, which is specified as do item.

(why choice test)* = (plan do test)* = (pdt)*

The ultimate evolutionary why is to save energy, i.e. one invests energy to save energy.

Why's:

more useful (more global energy minimum)
less effort, less cost, with same utility
improve development efficiency itself
in the middle of a context: produce consistency

These generic guidelines still keep many choices open. Among them

how to group p, d and t items to minimize effort
how to integrate products from other organizational units (qualification)

Do: pdtcontent pdtcycle

Normally for every do item there is a linked plan. do items don't need a separate plan item, if a why

can be stated very shortly and
is local to the do item

do items are a commitment to do things as specified.

do items only specify based on (information from) plan items.

do items are as general as the constraints from the plan items allow

do items are interface that crystalizes from the plan items

do items are testable

Test: pdtcontent pdtcycle

The test is the link back up.

test items check against plan items
test items are planned together with plan items
test items are executed after the do items

Tests in lower layers are not specified.

Verification is a synonym of testing, the process of executing tests. Validations of a product from another organizational unit are the subset of tests dealing with that product.

Test-Driven Development: Tests form the evolutionary environment for a solution. One best thinks of test items when formulating plan items. This way the do items already have a environment to test against.

To make the expensive do more likely a success, one better tests early, in

mind (thinking) or via
via (software) experiments/simulations

As tests finalize a cycle, they are also responsible for consistency. Test items link to plan and do items, and state that their consistency has been checked.

Traceability: With separate files for inform, plan, do and test, the content items get marked as such. This can be used to automatically check that test items are linked to plan and do items.

The ultimate test is the usefulness,

which leads to applications in the real world,
which provides new test cases,
leading to further improvements

A system is not bug-free, unless proven so by tests. Due to the complexity tests will

most likely never cover everything

See

test coverage

A system is still usable even if not bug-free. Most applications of a system use only a limited amount of functionality. Broad adoption increases usage coverage.

To reach a stable, i.e. usable, state, reserve at least as much time for stabilization as for "development", because every development step has more test steps.

With

testing accompanies all development steps and can be considered part of development.

Test

This document is informative.

I reused the inform-plan-do-test structuring to separate

abstract motivation (plan) and
more concrete guidelines (do) and
because it fits to the topic

The test is given by the application of these guidelines. It should produce feedback and adaptations in this document.