Tuesday, November 25, 2014

Reactive programming through explicit effects

Foreword

This paper is a pause from my spree about the ash shading language library I’m working on. I’m also working on a 3D engine, photon, in which I plan to use ash. The projects are then closely related ;).

The purpose of this paper is to discover a nice way of dealing with the reaction problem. There’re common and elegant solutions that address the problem, like FRP1, which is pretty elegant, but also very experimental. I wanted to explore on my own. This is what I come up with.

Side effect

As a programmer, you might already have come across side effects. You haven’t? Let’s have a look at these nasty things.

A side effect is a big word to describe an effect a function has that mutates something out of scope. For instance, you could picture a function modifying a global state, environment or any kind of “remote” value.

Another way to understand what a side effect is is to look at referential transparency. If you need assumptions to be able to say what a piece of code does, you might be in the presence of a side effect. For instance, look at this C++ snippet:

void update(int rx, int ry) {
  _x += rx;
  _y += ry;
}

Do you know what those lines do?

Yeah, sure! It’s a method in a class that updates _x and _y fields by applying them offsets rx and ry!

That could be. Let me add some more code to complete the example:

int _x = 0;
int _y = 0;

void update(int rx, int ry) {
  _x += rx;
  _y += ry;
}

int main() {
  update(2,1);
  return 0;
}

A class, you said? As you can see, we can’t say what that code does, because we have to look at all possible code lines that code might touch. It could be a class method, it could be a simple function, _x and _y could be int as well as they could be Foo objects with the operator+= overloaded. The list is long.

In that snippet, _x += rx and _y += ry are side effects, because they alter “something” elsewhere. That could be fine, but it’s not. The more you have side effects, the harder it is to debug, maintain, compose, understand and make your code base evolve. As a good programmer, you should care about side effect avoidance.

Purity

In pure functional languages like Haskell, we can’t do that kind of assignment, at least not directly. We would write this function:

update :: (Int,Int) -> (Int,Int) -> (Int,Int)
update (x,y) (rx,ry) = (x + rx,y + ry)

Because everything is immutable in Haskell, we are sure that (x,y) and (rx,ry) are constant. They can’t change. So we can say what that function does:

It takes a pair of int and apply them an offset!

Yeah, exactly. And it can’t be anything else. We don’t need assumptions, because such a function is transparent. That’s a great property you can rely on – do it, your compiler does ;)

However, we still need side effects

If Haskell rejected all side effects, we couldn’t have any programs. We would have theorems, properties and purity, but nothing on screen, no inputs, nothing actually computing. That would be a pity. But why? Well, we still need side effects. When you print something on screen, you actually want a side effect. There’s nowadays no other way to go. You pass a String to putStrLn for instance, and the function generates a side effect to put the String on screen. That’s a side effect because it’s out of scope of your program. You touch something elsewhere.

That’s the same thing for inputs, reading files, creating files and so on and so forth. Haskell uses a type to be able to deal with those cases: IO a. It’s a polymorphic type that can look at the real world. You can’t but IO a can.

We have IO a to explicitly deal with side effects, that’s cool. However, IO represents any kind of side effects. We’d like to be able to explicitly say “Hey, I can have that effect”.

Reaction: Part 1 – Explicit effects in imperative languages

Reacting to something requires activation. Do you know the observer design pattern? That is an interesting design pattern everyone should know. It’s very powerful since it enables you to run actions when an observed event is generated. You have to explicitly describe what actions and/or objects you want to observe. That is commonly done via two important things:

  • implementing an interface that exports the event handlers interface;
  • explicitly interleaving your observed code with calls to the abstract event handlers.

Let’s take an example, still in C++:

// this is the interface used to react to events
class FooObserver {
  FooObserver(void) {}
  virtual ~FooObserver() = 0;
  
  virtual void on_fire(Direction const &dir) = 0;
  virtual void on_set_a(int oldValue, int newValue) = 0;
  virtual void on_set_b(std::string const &oldValue, std::string const &newValue) = 0;
};

class Foo {
private:
  int _a;
  std::string _b;
  std::list<FooObserver&> _observers; // all observers that will react to events
  
public:
  Foo(void) : _a(0), _b("") {}
  ~Foo(void) {}
  
  void addObserver(FooObserver &observer) {
    _observers.push_back(observer);
  }
  
  void fire(Direction const &dir) {
    // use dir
    for (auto observer : _observers)
      observer.on_fire(dir); // notify all observers something has happenned
  }
  
  void setA(int a) {
    _a = a;
    for (auto observer : _observers)
      observer.on_set_a(_a, a); // notify all observers something has happenned
  }
  
  void setB(std::string const &b) {
    _b =  b;
    for (auto observer : _observers)
      observer_on_set_b(_b, b); // notify all observers something has happenned
  }
};

If we want to react to events emitted by an object of type Foo, we just have to create a new type that inherits from FooObserver, implement its abstract methods and register an object of our type so that the value can call it when it has to emit events. That’s pretty great, but it has a lot of side effects, and we’re gonna try to abstract that away.

Reaction: Part 2 – Explicit effects in Haskell

I’ve been wondering around for a while. There’re folks that advise to use FRP. It addresses the issue another way though – I won’t talk about FRP in this post, maybe later since it’s a very interesting concept. For my part, I wanted something like pipes. Being able to compose my functions along with having effects.

In photon, my 3D engine, I use explicit effects to implement reactions. That is done via a typeclass called Effect:

class (Monad m) => Effect e m where
  react :: e -> m ()

Pretty straight-forward eh? We call react e to react to an event of type e. Let’s have a look at a few examples.

react, examples – Part 1

Let’s start with a simple example:

-- This type represents all effects we want to observe.
data IntChanged
  = IntSucc
  | IntPred
  | IntConst Int
    deriving (Eq,Show)

-- This instance enables us to react in a State Int.
instance  Effect IntChanged (State Int) where
  react e = case e of
    IntSucc -> modify succ
    IntPred -> modify pred
    IntConst x -> put x

foo :: (Effect IntChanged m) => m String
foo = do
  react (IntConst 314)
  return "foo"

bar :: (Effect IntChanged m) => Float -> m Float
bar a = do
  when (sqrt a < 10) . replicateM_ 3 $ react IntSucc
  return (a + pi)

Let’s use that. I use explicit types because I’m in ghci:

flip runState 0 (foo :: State Int String)

("foo",314)

flip runState 0 (bar 0 :: State Int Float)

(0.0,3)

flip runState 0 (bar 10 :: State Int Float)

(3.1622777,3)

flip runState 0 (bar 99 :: State Int Float)

(9.949874,3)

flip runState 0 (bar 100 :: State Int Float)

(10.0,0)

flip runState 0 (bar 314 :: State Int Float)

(17.720045,0)

As you can see, we can have effects without IO. In that case, it was pretty simple. But since it’s abstract to any Monad, we could implement effects in IO, specific ones.

react, examples – Part 2

Let’s see an example in IO.

foo

set to 314

"foo"

bar 0

succ!

succ!

succ!

0.0

bar 10

succ!

succ!

succ!

3.1622777

bar 99

succ!

succ!

succ!

9.949874

bar 100

10.0

bar 314

17.720045

Because our foo and bar functions are polymorphic, we can use them with any types implementing the wished effects! That’s pretty great because it enables us to write our code in an abstract way, and interpret it with backends.

Extra – handles

Because all of this was firstly designed for my photon engine, I had to deal with an important question. Having effects is great, but how could we make an effect like:

“Draw the mesh with ID=486.”

Handles

I use handles to deal with that. I use a type to represent handles (H). Each object that can be managed (i.e. that can have a handle) can be wrapped up in Managed a. Basically:

type H = Int

data Managed a = Managed {
    handle :: H
  , managed :: a
  } deriving (Eq,Show)

Now, because we want to react to the fact that an object is being managed – or not managed anymore – we have to introduce special effects.

Effectful managing

Hence two new types: Manager m and EffectfulManage a s l.

Manager

A manager is a monad that can generate new handles to manage any kind of value and recycle managed values:

class (Monad m) => Manager m where
  manage :: a -> m (Managed a)
  drop   :: Managed a -> m ()

manage a will turn a into a managed version you can use for whatever you want. In theory, you shouldn’t have access to the constructor of Managed nor the handle field.

If a type implements both Monad and Manager, we can manage values and recycle them very easily:

import Prelude hiding ( drop )

foo :: (Manager m) => m ()
foo = do
  x <- manage 3
  y <- manage "hey!"
  drop x
  drop y

Notice: if you want to be able to use the drop function, you’ll have to hide Prelude’s drop.

EffectfulManage

However, we’d like to be able to react to the fact a value is now tracked by our monad, or recycled. That’s done through the following typeclass:

class EffectfulManage a s l | a -> s l where
  spawned :: Managed a -> s
  lost    :: Managed a -> l

EffectfulManage a s l provides an event s and an event l for a. If you’re not comfortable with functional dependencies, a -> s l means you can’t have two pairs of events for the same type.

Let’s take an example.

data IntSpawned = IntSpawned (Managed Int)
data IntLost = IntLost (Managed Int)

instance EffectfulManage Int IntSpawned IntLost where
  spawned = IntSpawned
  lost = IntLost

Pretty simple. Now, there’re two functions to react to such events:

spawn :: (Manager m,EffectfulManage a s l,Effect s m) => a -> m (Managed a)
lose :: (Manager m,EffectfulManage a s l,Effect l m) => Managed a -> m ()

spawn a manages the value a, returning its managed version, and as you can see in the type signature, have an effect of type s, which is the spawned effect. lost a takes a managed value, drops it, and emits the corresponding l event.

In our case, with our Int, we can specialize both the functions this way:

spawn :: (Manager m,EffectfulManage Int IntSpawned IntLost,Effect IntSpawned m) => Int -> m (Managed Int)
lost :: (Manager m,EffectfulManage Int IntSpawned IntLost,Effect IntLost m) => Managed Int -> m ()

Let’s write a simple example:

instance (Functor m,Monad m) => Manager (StateT [H] m) where
  manage x = fmap (flip Managed x) (gets head <* modify tail)
  drop (Managed h _) = modify $ (:) h

-- a possible backend...
instance Effect IntSpawned (StateT [H] IO) where
  react (IntSpawned (Managed h i)) = liftIO . putStrLn $ "int has spawned:" ++ show i

instance Effect IntLost (StateT [H] IO) where
  react (IntLost (Managed h i)) = liftIO . putStrLn $ "int lost :" ++ show i

In the end

This is being implemented in photon, and I think it’s a good start. I once wanted to use pipes, but a 3D engine is not a streaming problem: it’s a reactive problem. Maybe FRP could be more elegant, I don’t know – the H type is not the most elegant thing ever, but it works fine.

What do you think folks?


  1. Functional Reactive Programming

Monday, November 17, 2014

Abstracting Over Shader – Environment

In the previous episode…

This blog entry directly follows the one in which I introduced Ash, a shading language embedded in Haskell. Feel free to read it here before going on.

Controlling behavior

A shader is commonly a function. However, it’s a bit more than a simple function. If you’re a haskeller, you might already know the MonadReader typeclass or simply Reader (or its transformer version ReaderT). Well, a shader is kind of a function in a reader monad.

So… that implies a shader runs in… an environment?

Yeah, exactly! And you define that environment. The environment is guaranteed not to change between two invocations of a shader for the same render (e.g. between two vertices in the same render). This is interesting, because it enables you to use nice variables, such as time, screen resolution, matrices and whatever your imagination brings on ;)

The environment, however, can be changed between two renders, so that you can update the time value passed to the shader, the new resolution if the window resizes, the updated matrices since your camera’s moved, and so on and so forth.

Let’s see a few example in GLSL first.

Shader environment in GLSL

To control the environment of a shader in GLSL, we use uniform variables. Those are special, global variables and shared between all stages of a shader chain1.

Let’s see how to introduce a few uniforms in our shader:

uniform float time;       // time of the host application
uniform vec2 resolution;  // (w,h)
uniform vec2 iresolution; // (1 / w, 1 / h), really useful in a lot of cases ;)
uniform mat4 proj;        // projection matrix
uniform int seed;         // a seed for whatever purpose (perlin noise?)
uniform ivec2 gridSize;   // size of a perlin noise grid!

You got it. Nothing fancy. Those uniforms are shared between all stages so that we can use time in all our shaders, which is pretty cool. You use them as any kind of other variables.

Ok, let’s write an expression that takes a time, a bias value, and multiply them between each other:

uniform float time;
uniform float bias;

// this is not a valid shader, just the expression using it
time * bias;

Shader environment in HLSL

HLSL uses the term constant buffers to introduce the concept of environment. I don’t have any examples right now, sorry for the inconvenience.

Shader environment in Ash

In Ash, environment variables are not called uniforms nor constant buffers. They’re called… CPU variables. That might be weird at first, but let’s think of it. Those values are handled through your application, which lives CPU-side. The environment is like a bridge between the CPU world and the GPU one. A CPU variable refers to a constant value GPU-side, but varying CPU-side.

Create a CPU variable is pretty straight-forward. You have to use a function called cpu. That function is a monadic function working in the EDSL monad. I won’t describe that type since it’s still a work in progress, but it’s a monad for sure.

Note: If you’ve read the previous blog entry, you might have come across the Ash type, describing a HOAST. That type is no more a HOAST. The “new Ash” – the type describing the HOAST – is now Expr.

This is cpu:

cpu :: (CPU a) => Chain (Expr a)

CPU is a typeclass that enables a type to be injected in the environment of a shader chain. The instances are provided by Ash and you can’t make your own – do you really want to make instance CPU String, or instance (CPU a) => CPU (Maybe a)? Don’t think so ;)

Let’s implement the same time–bias example as the GLSL one:

foo :: Chain (Expr Float)
foo = liftA2 (*) cpu cpu

That example is ridiculous, since in normal code, you’d actually want to pass the CPU variables to nested expressions, in shaders. So you could do that:

foo :: Chain ()
foo = do
  time <- cpu
  bias <- cpu

  -- do whatever you want with time and bias
  return ()

You said Chain?

Chain is a new type I introduce in this paper. The idea came up from a discussion I had with Edward Kmett when I discovered that the EDSL needed a way to bind the CPU variables. I spotted two ways to go:

  • using a name, like String, passed to cpu; that would result in writing the name in every shader using it, so that’s not ideal;
  • introducing the environment and providing a monad instance so that we could bind the CPU variables and use them in shaders inside the monad.

The latter also provides a nice hidden feature. A chain of shaders might imply varying2 values. Those varying values have information attached. If you mistake them, that results in catastrophic situations. Using a higher monadic type to capture that information – along with the environment – is in my opinion pretty great because it can prevent you from going into the wall ;).

To sum up, Chain provides a clear way to describe the relation between shaders.

What’s next?

I’m still building and enhancing Ash. In the next post, I’ll try to detail the interface to build functions, but I still need to find how to represent them the best possible way.


  1. You can imagine a shader chain as an explicit composition of functions (i.e. shaders). For instance, a vertex shader followed by geometry shader, itself followed by a fragment shader.

  2. Varying values are values that travel between shaders. When a shader outputs a value, it can go to the input of another shader. That is call a varying value.

Friday, November 14, 2014

Abstracting shader – introducing the ash Haskell library

Foreword

Abstracting what?

Shaders are very common units in the world of graphics. Even though we’re used to using them for shading1 purposes, they’re not limited to that. Vulgarisation has ripped off the meaning up and down so much that nowadays, a shader might have nothing related to shading. If you’re already doing some graphics, you may know OpenGL and its compute shaders. They have nothing to do with shading.

You might also already know shader toy. That’s a great place to host cool and fancy OpenGL shaders2. You write your shaders in GLSL3 then a GLSL compiler is invoked, and your shader is running on the GPU.

The problem with source based shaders

So you write your shader as a source code in a host language, for instance in C/C++, Java, Haskell, whatever, and you end up with a shader running on GPU.

There’re two nasty issues with that way of doing though:

  • the shader is compiled at runtime, so if it contains error, you’ll know that after your application starts ;
  • you have to learn a new language for each target shader compilers.

They’re both serious issues I’m going to explain further.

Issue n°1: compiled at runtime

This is problematic for a good reason: a lot of shaders are application dependent. Shadertoy is a nice exception, just like modeling tools or material editors, but seriously, in most applications, end users are not asked the shaders to run with. In a game for instance, you write all the shaders while writing the game, and then release the whole package.

Yeah… What’s about additional content? Per-map shaders, or that kind of stuff?

Those shaders are like resources. That doesn’t imply using them as is though. We could use dynamic relocatable objects (.so or .dll) for instance.

What compile-time compilation gives you?

It gives you something hyper cool: host language features. If you have a strongly-typed language, you’ll benefit from that. And that’s a huge benefit you can’t get away from. If you’re writing an incorrectly typed shader, your application / library won’t compile, so that the application won’t react in weird way at run-time. That’s pretty badass.

Issue n°2: languages, languages…

This issue is not as important as the first one, but still. If you’re working on a project and you target several platforms (among ones using OpenGL, OpenGL ES, DirectX and a soft renderer), you’ll have to learn several shading languages as well (GLSL, HLSL4).

In order to solve that, there’re two ways to go:

  • a DSL5 ;
  • an EDSL6.

A DSL is appealing. You have a standalone language for writing shaders, and backends for a compiler/language. However, that sounds a bit overwhelming for such an aim.

An EDSL is pretty cool as well. Take a host language (we’ll be using Haskell) and provide structure and construction idioms borrowed from such a language to create a small embedded one. That is the solution I’m going to introduce.

Ash

Ash stands for Abstract Shader. It’s a Haskell package I’ve been working on for a few weeks now. The main idea is:

  • to provide a typesafe shading language compiled at compile-time;
  • to provide backends;
  • to provide a nice and friendly haskellish interface.

I guessed it’d be a good idea to share my thoughts about the whole concept, since I reckon several people will be interested in such a topic. However, keep in mind that Ash is still a big work in progress. I’m gonna use several blog entries to write down my thoughts, share it with you, possibly enhance Ash, and finally release a decent and powerful library.

If you’re curious, you can find Ash here.

Basics

Ash is a library that provides useful tools to build up shaders in Haskell. In Ash, a shader is commonly function. For instance, a vertex shader is a function that folds vertex components down to other ones – possibly maps, but it could add/remove components as well – and yields extra values for the next stages to work with.

You write a shader with the Ash EDSL then you pass it along to a backend compiler.

Here are two examples. In order for you to understand how Ash works, I’ll first write the GLSL (330 core) shader, then the Ash one.

First example: a simple vertex shader

Let’s write a vertex shader that takes a position and a color, and projects the vertex using a perspective matrix, a view matrix and the object matrix of the object currently being rendered and passes the color to the next stage:

#version 330 core

in vec3 pos;
in vec4 col;

out vec4 vcol;

uniform mat4 projViewModel;

void main() {
  vcol = col; 
  gl_Position = projViewModel * vec4(pos, 1.);
}

And now, the Ash one:

vertexShader :: Ash (M44 Float -> V3 Float :. V4 Float -> V4 Float :. V4 Float)
vertexShader = lam $ \proj -> lam $ \v ->
  let pos :. col = v
  in proj #* v3v4 pos 1 :. col

Ash is the type used to lift the shading expression up to Haskell. You use it to use the EDSL. It actually represents some kind of HOAST7.

Then, you can find M44, V3, V4 and (:.).

M44 is the type of 4x4 matrices. Since projection matrix, view matrix and model matrix are all 4x4 floating matrix, M44 Float makes sense.

V3 and V4 represents 3D and 4D vectors, respectively. V3 Int is three ints packed in a vector as well as V4 Float is four floats packed in a vector. You’ll also meet V2, which is… the 2D version.

(:.) is a type operator used to build tuples. You can see (:.) as a generalized (,) – the default Haskell pair type – but (:.) is more power full since it can flatten expressions:

a :. (b :. c) = a :. b :. c

The (:.) has a lot of uses in Ash. In our cases, a chain of (:.) represents a vertex’ components.

So our vertexShader value is just a function that takes a matrix and a vertex (two components) and outputs two values: the new position of the shader, and the color. Let’s see the body of the function.

lam $ \proj -> lam $ \v ->

This is a pretty weird expression, but I haven’t found – yet? – a better way to go. lam is a combinator used to introduce lambdas in the EDSL. This expression then introduces a lambda that takes two values: proj and v. You can read that as:

\proj v ->

Next:

let pos :. col = v

This is the tricky part. That let expression extracts the components out of the vertex and binds them to pos and col for later use.

in proj #* v3v4 pos 1 :. col

(#*) is a cool operator used to multiply a matrix by a vector, yielding a new vector.

(v3v4) is a shortcut used to to build a V4 using a V3 by providing the missing value – here, 1. You’ll find similar functions, like v2v3 and v2v4, to respectively build a V3 from a V2 by providing the missing value and build a V4 from a V2 by providing the two missing values.

We finally wrap the result in a tuple (:.), and we’re done.

Features

Ash embeds regular linear expressions (vectors, matrix), textures manipulation, tuples creation, let-bindings, lambda functions (they represent shader stages up to now), and a lot of other features.

Each feature is supposed to have an implementation in a given backend. For instance, in the GLSL backend, a lambda function is often turned into the well done main function. Its parameters are expanded to as in values, and control parameters are uniform variables.

Each backend is supposed to export a compile function – the name may varies though. However, each backend is free to compiles to whatever smart they think is. For instance, compiling an Ash shader to GLuint (shader stage) is not very smart since it would use IO and handles error a specific way we don’t want it to do. So the GLSL compiler is a function like glslCompile :: Ash … -> Either CompilationError String, and the String can be used as a regular GLSL source code string you’ll pass to whatever implementation of shader you’ve written.

What’s next?

I need to finish the implentation of the EDSL, and write the whole GLSL 330 compiler. If it’s a success, I’ll accept pull-requests for other famous compilers (other GLSL version compilers, HLSL, and so on and so forth).

Once that done, I’ll write a few other blog entries with example as a proof-of-concept :)


  1. Shading is the process in which primitives (sets of vertices) are turned into colors (i.e fragments, a.k.a. pixels or texels).

  2. Actually, they’re fragment shaders.

  3. OpenGL Shading Language.

  4. High Level Shading Language.

  5. Domain-Specific Language.

  6. Embedded Specific Language.

  7. High-Order Abstract Syntax tree; for the purpose of this paper, you don’t have to fully understand them to get your feet wet with Ash (which is cool, right? :) ).

Saturday, July 05, 2014

Lost in space

Lost in space

The following blog entry is a bunch of my own thoughts regarding a 3D engine I’m writting.

Foreword

It’s been a while now I’ve been trying to represent a 3D scene the proper way. I’ve found dozens of solutions, but still none of them is likely to be as proper nor accurate as I’d like to. The problem is actually quite simple: a 3D scene is composed of several objects. You can encounter two types of objects:

  • value-semantic object
  • entity-semantic object

A value object is an object you can think of by its value. For instance, money, color, position, a file configuration, and so on.
An entity object is an object you cannot think of by it its value. It’s a whole unique object. The simplest example is you. A human. Even if we find a way to make perfect clones, two perfect similar humans remain different. We also capture this concept in programming.

Now, what are 3D scene’s objects? Let’s select of few you could encounter in almost all engines:

  • a vertex
  • a mesh, which is a bunch of vertices with primitives construction information
  • a shader
  • a material, which holds a sharable shader
  • a model, which is a mesh associated to a material
  • a light
  • entities, that bind any value to space information (position, orientation and scale, for instance)

As you might guess, some objects in the above non-comprehensive list of scene objects are value-semantics, others are entity-semantic. A vertex is obviously a value. A mesh could be both depending on how you design your scene. In my way, it’s an entity. So is a shader, a material, a model and a light. Funny things, scene entities are values since they link an entity-semantics object to space information, which is value.

With all that said, how would you link objects between each other?

The simple way: identifiers

My first thought was a simple one: let’s introduce a higher-order type called ID:

newtype ID a = ID Int deriving (Eq,Ord,Show)

It’s a phantom type in order to know what we are refering to. ID :: Mesh refers to a Mesh. So, we can use our new identifiers type to add indirection in our types:

data Mesh = Mesh {-  -}
data Material = Material {-  -}
data Model = Model (ID Mesh) (ID Material)

That requires us to be able to generate names. I came up with a simple solution to do so:

class Identify a m where
  ident :: a -> m (ID a)
  reify :: ID a -> m a
  imod  :: ID a -> (a -> a) -> m ()

This typeclass is a bit like MonadState on steroids since it adds indirection. Then, given your own monad based on SatetT, you could do something like:

instance Identify Mesh MySceneMonad where
  ident = {-  -}
  reify = {-  -}
  imod  = {-  -}

instance Identify Material MySceneMonad where
  {-  -}

instance Identify Model MySceneMonad where
  {-  -}

foo :: MySceneMonad (ID Model)
foo = do
  msh <- ident $ Mesh {-  -}
  mat <- ident $ Material {-  -}
  ident $ Model msh mat

However, this suffers from some issues. First, the implementation of the ID supply is in your hand. If you do it wrong, everything will
just go… wrong. Furthermore, IDs are escapable. What would happen to if you escape an identifier and reify in another monad?

getID :: MySceneMonad (ID Mesh)
getID = ident $ Mesh {-  -}

foo = do
    mshid <- runMySceneMonad getID defaultState
    runMySceneMonad $ reify mshid -- oops!

The less simple way: AST

An AST would be great to represent our scene. We could find at the top objects which have the less dependencies, and at the bottom the
more dependent objects. Let’s try to write down the AST for a few objects only:

data E a
  = V a
  | Let (E a) (Scope () E a)
  | Lam (Scope () E a)
  | E a :@ E a
  | LitShader Shader
  | LitMesh Mesh
  | LitMaterial Material
  | LitModel Model
    deriving (Eq,Show)

Shader, Mesh, Material and Model would only care about core features. So you don’t find a Shader in the implementation of a Material
since the link is done through the AST. But in our case, how? We could use the Let constructor, let’s try out:

Let (LitShader shaderDef) (LitMaterial materialDef)

As you can see, that is stupid. The normal form of that expression discards the shader and turns into LitMaterial materialDef. I see here a
solution: we need a special branch in the AST to represent link. Let’s add that into our E expression type only for shaders:

WithShader :: E a -> E a -> E a

So we can do:

WithShader (LitShader shaderDef) (LitMaterial materialDef)

Notice we could even write:

WithShader (V "myShaderDef") {- any expression using that shader -}

Now I see another issue: the first expression is untyped. We could write this, it’d be perfectly valid:

WithShader (LitMaterial materialDef) (V "oshit")

And even V "myShaderDef is untyped. So we’re hitting ourselves in the foot with such an AST. We could, though, think it’s perfectly legit
and write a typechecker that would validate an AST for us, like:

typecheck :: E a -> Either ASTError (E a)

The harder way: AST via GADT

We don’t want typecheck, it’ll complicate the way we use an AST. So let’s turn E into a GADT.

data E :: * -> * -> * where
  V :: a -> E l a
  Let :: E l a -> Scope () (E l) a -> E q a
  Lam :: Scope () (E l) a -> E q a
  Apply :: E l a -> E q b -> E l a
  LitShader :: Shader -> E Shader a
  LitMesh :: Mesh -> E Mesh a
  LitMaterial :: Material -> E Material a
  LitModel :: Model -> E Model a

But now, go and try to make that a monad. You won’t be able to, since it’s not. Even less an applicative functor, so not foldable nor
traversable. I think that solution is the more complicated, the more obfuscated, and the more… solution, in the end!

The hope solution: typeclass

Typeclasses could save us all, since the interpreters could be the typeclass implementation. Let’s turn the GADT into a typeclass:

class AST expr where
  var :: a -> expr l a
  let_ :: expr l a -> a -> expr q a -> expr q a
  -- and so on and so forth

This is nice, I like that way of doing, even more than data, because we can let the compiler choose the best type for us (or force it).
An AST would be something like this:

ast :: (AST e) => e l a

But unfortunately, we have the same problem as GADT: writing a proper implementation will be… writing the same madness GADT…

So?

So… I still don’t know. I’m looking for alternatives. Up to know, I believe the ID solution is my shortest way to get things done. I’m open
to better solutions, because it might have plenty.

Tuesday, February 25, 2014

kwak – release 0.2.0.1

The Apocalypse

A few days ago, freenode – an IRC server – was injured by some people performing a DDoS. It was very messy and apocalypse day, but we all ended up quite okay. Except for one little guy: kwak, my IRC tellbot.

What happened

During a netsplit or a DDoS, you might be disconnected from the server. All IRC clients might implement something against that. As you may have already noticed, my tellbot is not really an IRC client (laughter). But it acts like it was one. You can /whois it, you’ll get something – nothing interesting though. Then during a netsplit or DDoS, the tellbot is disconnected, but doesn’t reconnect since I didn’t foresee it could happen.

The patch

Then I wrote a patch – it took me five minutes; Haskell <3. The patch introduces some fixes against disconnections. I also added an anti-kick behavior – kick the tellbot, it’ll come back! It was not mandatory, but it was something like ten words of code, so…

The patch is not deployed yet. I’ll do the change tonight if I have some spare time.

In the next release, 0.2.1.0, I’ll add a support for a minimalistic admin session through direct connection to the bot. It’ll be used to correctly shutdown the bot – useful when maintaining – and then backup all stories in order to resume them later.

Note: a bug was discovered by LLB. Using !tell in private always succeeds whereas it mustn’t. I’ll push another patch for that issue.

Friday, February 21, 2014

Logging flow activity

Foreword

Everyone needs to log things in a program. Have you already wondered what kind of logs you were dealing with? I don’t mean debug, warning or error logs. I mean semantic here.
Basically, I’ll put apart two concepts:
  • tracing an algorithm’s behavior
  • tracing a flow activity
Tracing an algorithm’s behavior is something we often do in Haskell with the Writer or WriterT monads. Those are very convenient because they allow the use of a monoid along with your computation. You can then compute things while mappending a monoidal value. Once the algorithm is done, you get a pair of values: the value from your computation, and the monoidal log. This is great when you want to launch something and analyze trace later.
This Writer stuff doesn’t fit flow activity. Why? Because tracing an algorithm’s behavior is what we could call deferred log handling whereas the later is on-the-fly log handling. There could be a lot of reasons for prefering on-the-fly over deferred:
  • if you’re planning to log in a function that may take long time to run (you’d like the logs as soon as possible, not in an hour)
  • if you’re planning to log a lot (you don’t want your application to poorly crash because your system runs out of memory due to the huge and nasty accumulating monoid memory print)
  • you have a reactive ecosystem to logs
  • and so on…
You still can do on-the-fly log handling with Writer. There are two functions called listen and listens that will grant you access to the monoidal value of a sub Writer. Then you can do something like that:
runWriterT $ do
(_,w) <- listen $ do
tell "Hello, this is dawg!"
return 314
liftIO (print w) -- print it out here
But all of this has a huge and important drawback: because the call to listen runs in Writer or WriterT, its monoid will be accumulated in its parent. So we can treat stuff on the fly, but we can’t purge logs. Imagine what happens if your application logs intensively and runs for a long time. Bam! :)

Tracing flow activity

We want to easily accumulate monoidal values. We also want to have a solution to access the monoid and do something with it – for instance print it out on screen or in the terminal. Finally we want to clear the monoid – the purge thing.

MonadJournal

Here MonadJournal comes. I’ve chosen the term journal because it’s straight-forward and a lot of applications call that that way (look at systemd’s journalctl program for instance). Let’s have a look:
class (Monoid w, Monad m) => MonadJournal w m | m -> w where
journal :: w -> m ()
history :: m w
clear :: m ()
And these useful functions:
sink :: (MonadJournal w m, MonadIO m) => (w -> IO ()) -> m ()
absorb :: (Monadjournal w m) => (a,w) -> m a
The MonadJournal typeclass defines three functions. journal, history and clear. The former is used to trace activity. It’s quite the same thing as tell, but in MonadJournal. history is used to retrieve the history of logs. The latter is used to clear the history.
sink is a log handler. It takes a function that takes the monoid – i.e. the logs history – and does something with it in IO, and purge the history. The simpliest thing you can do with logs is print them out! And this is quite ultra simple to do. If your monoid is also in the Show class, you can simply print them all with this:
sink print
absorb is to MonadJournal what writer is to MonadWriter. It takes a value with a monoid, absorbs the monoid, and pass the value around.

JournalT

The problem with that is that it’s a typeclass, not something directly usable. There’s no implementation of journal nor sink anywhere yet. That’s why a JournalT monad transformer was introduced. This is its type:
JournalT w m a
It’s then the monad transformer version of MonadJournal, just as WriterT is the monad transformer version of MonadWriter. It has a function to run it:
runJournalT :: JournalT w m a -> m (a,w)
Now we can write a complete example:
main :: IO ()
main = do
void . runJournalT $ do
-- here we are tracing IO flow activity
journal ["hello!"]
v <- maybe (return 0) absorb . runJournalT $ test
journal ["just read " ++ show v]
sink print
-- and here we are tracing Maybe flow activity, which is pure
test :: JournalT [String] Maybe Int
test = do
journal ["lol"]
return 314
See how it’s unified thank to the typeclass!

Conclusion

I’ve been wandering around logging in Haskell for a while now. I’ve been using Writer, WriterT, passing logging action (like a function foo :: (Errorable e, MonadIO m) => (e -> IO ()) -> a -> b -> … -> m ()) and so on. I came up with the MonadJournal solution recently while working on my 3D engine, and it’s quite nice. It’s already in hackage, so give it a try, and leave your feedback! :)
If you think some combinators are missing, please let me know! :)

Thursday, February 20, 2014

Regular imperative statements versus FPL abstractions

When having talks over the Internets about FPL (Functional Programming Language), it’s not uncommon reading people exposing the same perennial misconceptions. They’re actually several sides around such a topic:
  • the ones who think FP is a toy and have poor arguments
  • the ones who think FP is not that good and have poor arguments
  • the ones who think FP sucks and can’t say why (no argument at all)
  • the ones who think FP is a “way of thinking the software” and that it’s not language-related
  • the ones who’s gone beyond the stupid toy / research toy / masturbating toy / brainfuck-like language stuffs and are now interested and want to discover more
  • the ones who think FP is great
  • the ones who have no idea what the heck FP is
Something interesting: in most cases, a lot of guys never actually experienced FP seriously. I mean “use it in a software different than Fibonacci generation or other school cases”. I don’t want to start a debate about whether FP is the best or the worse way of programming. If you’re there it’s because you’re from the guys who’s overstepped the barrier of FP and you want to dig in. If you’re there, you now understand that “it’s slow”, “it’s ugly”, “it doesn’t fit production requirements and serious business” and so on were valid arguments some decades ago, but not anymore – some people would even say some of those points weren’t actually close to be valid at all.

In this thread, I put forward an analogy between regular imperative – C/C++, Java, C#, Perl and so on – statements and FPL abstractions. The requirements for you to understand this thread are quite low: basic statements (for, if, else if, else, switch, and so on).

Loops
Looping over a collection is natural for all programmers. It’s a very common situation and is used to break the controlflow of your application. Without them, you’d have a program acting like a math function. It would take input, do some stuff on it, then exit. Iterations enables you to go backward, repeat the same functions and instructions a certain times or even do some exotic and weird things.

That was just the a “programmer” simple way of defining what looping could be. For a mathematician, regarding functions, looping does really not make any sense. You can’t apply a function and rewind.

Consider this C++ snippet:

std::vector; a = { 1, 8, 2, 34, 314 };
int sum = 0;

for (auto it = std::begin(a), e = std::end(a); it != e; ++it);
  sum += *it;
This is a typical case of looping in C++ using an iterator, which could be considered as a raw pointer in that previous example.

Now, how would you do the same thing in FPL? One say “well let’s just write a recursive function sumArray that would sum all elements!”. This would work, but it’s not that way we think in FPL. Instead, we come up with abstractions.

Abstracting is the process of generalizing something true to one concept to several other ones along a certain, well fixed, axis of abstraction. For instance, you know how to sum integers. You can generalize integers sum along some axis. If you choose the type axis, you can generalize integers sum to numbers sum. If you choose the operation axis, you can generalize integers sum into integers binary operation. And so on.

“Looping”. Try to forget programming. Does it still have any meaning to you? One of the hardest things to deal with when trying to get into functional programming is to think like a human again – yeah you’re all filfthy machines! Try reasoning about that collection, and forget looping. Ok, let’s give it a go. I’d say “I want to do something for each elements”. That’s a great start! But this is very abstract. Let’s try something else. “Well, I want to construct a value while traversing a collection”. This is much better! “In this case, I just want to sum all elements in the collection, then I just want to build a value by summing it to each element of the collection”. Quite concise. In C++, what was that again? “I want to loop over a collection and alter a variable by summing.”.

In Haskell – but also in perhaps all other FPL – it’s very common to use the abstract concept of a fold to iterate over a collection, building a value along. The collection is now called a foldable type and the iteration a fold. Folding a value is just accumulating a value using a function on each element. The idea is quite simple:
  • you have a function a -> b -> b
  • you have a foldable value with several a inside of it
  • you have an initial value for b
  • folding is just applying the function to each of the elements, passing along the previous value of the accumulator to the current call
Folding is then a special kind of iteration in which you accumulate a value. Because of polymorphic type, Haskell can handle any types of accumulator when using a folding function. That means you can fold a list and generate any kind of data.

Let’s write the same example as above, but in Haskell:

let a    = [1,8,2,34,314]
result = foldl1 (+) a
That’s all. You might say “ahah, foldl1, it’s barly readable” but in fact, it is. We find fold in foldl1. Then, we find a l. What could it be? Well, it’s a directional fold from left to right. You could also find a r as in foldr1 for instance – it would be a directional fold from right to left. What’s the 1? As mentionned above, folding needs an initial value to be able to start. Imagine the sum, the initial value is 0. foldl1 just uses the first value of the foldable type as initial value for the accumulator – it has an impact of the type of the folding function, which is now a -> a -> a; if you don’t understand why, it’s not really a matter).

Then, foldl1 (+) is a function that sums all elements of a collection (a list, actually). It could be a first implementation of the sum function, that does the same thing.

Conditional execution
This is quite the same thing in FPL, but it’s a bit different as well. In typical imperative languages, conditionals are control statement. The single exception might be the ternary operator – not all languages have it. You know, that’s operator with ? and : keywords. Well, for Haskell, we only have that one. We don’t use the same keywords though, but instead, we have if and else.

Consider this C++ snippet:

string name;

std::cin << name;
if (name.empty()) {
  std::cout << "woh, empty name!" << std::endl;
} else if (name.size() < 4) {
  std::cout << "this is a short name you have" << std::endl;
} else {
  std::cout << "what a long name!" << std::endl;
}
This code is quite simple. You enter your name, and if it’s null, you’ll told it’s empty, if it’s less than four characters, you’ll be told it’s short and more than four characters you have a long name.

Now the same thing, but in Haskell:

name <- getLine
putStrLn $
  if null name
  then
    "woh, empty name!"
    else if length name < 4
    then
      "this is a short name you have"
    else
      "what a long name!"
You don’t have to insert as much newlines and indents I do, but I think it’s clearer that way. As you can see, the test is now done inside the value construction we’re passing to putStrLn, which takes a String and outputs it into your terminal. In Haskell, conditionals yields values. You could then write something like that:

a <- getLine
let r = if a == 0 then 314 else a
Haskell also has a lot of ways doing conditional execution. For instance, it has native support for partial function implementation depending on a predicate:

foo :: String -> IO ()
foo = putStrLn . go . length
  where
    go l
        | l == 0    = "woh, empty name!"
        | l < 4     = "this is a short name you have"
        | otherwise = "what a long name"
Those | are called guards in Haskell. We also have pattern-matching to implement a function differently depending on the “form” of its argument. For instance:

bar :: String -> String
bar []     = "empty string"
bar (x:[]) = "singleton string
bar _      = "long string"
I won’t go into complex details, but we also have monadic conditional function that enables us to do pretty things like:

testSomething :: IO ()
testSomething =
    runMaybeT $ do
      userInput <- lift getLine
      guard (length userInput /= 0)
      lift (putStrLn "ok!")
In that last snippet, if the user enters an empty string, the string “ok!” won’t be printed out.

As I already told you, abstractions are everywhere in FPL and especially in Haskell.

Error handling
One last example to give you an idea: exception handling. In C++, you have the keywords throw and catch and the type std::exception to inherits from. One big mistake a lot of folks do is thinking that error-prone code should be handled through exception. This is not really a good idea since exceptions are exceptional.

In Haskell, you can handle errors via dozens of ways. For instance, just like the testSomething function just above, you can use the Maybe type or use it as a monad. Even better, you can use its monadic transformer form, MaybeT, (what I did here), in order to extend your code with failable with no message errors code. Maybe express this concept: “maybe there’s nothing, maybe there’s just something”. And well, the Maybe type has two constructors. Try to guess what. Just, and Nothing. It can express a value that can be absent, ill, misformed, and so on.

For errors with message, we have a lovely type, monad and monad transformer with corresponding combinators: Either. It shows this: “I can have either this type or this one”. This is the theory about Either. Pratically, we don’t use it that way. We use this way: “it can has a right value, or a value that represents something wrong”. Two constructors for that type: Right, for a right value, and Left, for a wrong value.

If you just want to compute a value, and express a potential error with a String, you’re eligible to use an Either String a type! You could then do that:

testSomething :: IO ()
testSomething = do
    e <- runEitherT $ do
      userInput<- lift getLine
      when (length userInput == 0) . left $
        "oh god, error! empty string!"
      lift (putStrLn "ok!")
    either err skip e
stderr. Pretty straight-forward huh? :)

Conclusion
I could have written much more lines about comparison, but I think it’s quite enough for today. I’ll go into further details if you want.

The last thing to keep in mind is that all you can do in imperative languages can be achieved in FPL as well.

Kwak – the drama tellbot – was released in version 0.2.0.0!

I few days ago, I wrote a tellbot for my fellow French demosceners. It was designed to run on our public channel (#demofr on IRCNet). I wrote it Haskell and it took me something like only six hours to write it and release the version 0.1.0.0.

Only one hour after the first release was taking place a drama that’s split up the channel into smithereens. I won’t be going into any further details since everyone now knows what really happened in there. The important thing is that I fixed some issues – directly or indirectly related to that drama – and released another version.

Yesterday, I spent some time on changing the way the bot works. In the first place I designed it to be able to read your messages. If you want to leave a message to the user foo, you just had to type that in your favorite IRC client:

!tell foo I just wanted to tell you that […]

That message was delivered later when foo said something – no matter whether he’s already there, or joining, or whatever, he had to say something.

This behavior is quite convenient and I still think it’s a good thing. Some people have IRC autoconnect hooks when starting their machine so they can join their channels without any effort – I think it’s wrong but it’s another debate – but in fact they don’t read immediately messages nor hilights on IRC. So passing along messages when the recipient says something is a good idea. The drawback is about lurkers: if you’re lurking, and reading someone who’s using the !tell command to tell you something, if you don’t right answer back, and talk the day after that, you’ll be told the message anyway. This is normal to me, but might be quite annoying for some folks.

Then comes the 0.2.0.0 version of my tellbot. Now, the bot refuses to record your message if the recipient is already there, in the same room you and the bot are. It only enables you to leave a message to another folk if he’s not there. The message is delivered when the guy joins the channel.

You can find the source code here: