Archive for the ‘Concepts & theory’ Category

OO -> Actors (?)

November 15, 2008

Since the web has been established, networking and concurrency became central in most applications, like parrallelization is going to be with the multicore technology. However, OO seems not to be that well suited for either of both.

Why is OO not good for parrallelization?

Let’s say you have:
a := f()
b := g()
c := a + b
Simply put: how can you know if you can run f() and g() parrallely? You cannot tell directly. You have to know if f() or g(), and all resulting function calls, might at some moment modify a variable that the other uses or modify as well. In the latter case, parrallelization would lead to unpredictability and thus cannot be performed. Moreover, analyzing such dependencies is extremely difficult and breaks the principle of encapsulation.

And is OO good for networked applications?

Yes and no …At first sight it looks like yes but after some time it turns out it is not ideal. One issue is concurrency. When two requests come in at the time, it should be taken care that something being used by one is not modified by someone else at the same time. This leads to hard to investigate bugs and increased complexity due to synchronization. Another issue is that objects are not that well suited to model transactions.

Ok, so what now? Do you have anything better?

Object Orientation, combining data and methods acting upon them, is “today’s paradigm”. Now everything are objects, everyone “thinks” in terms of objects and OOP is “the way to go”. …But we should keep in mind it’s by all means not the sole way! And perhaps there are even better ways.

Two of the (compatible) models seeing some resurgence are the ones of functional programming and the actor model. I’ll skip the first one and directly go on speaking a little about the actor model.

What is an actor?

At first sight, both may look similar. However, they have profound differences. Conceptually, objects are just “dead” data with methods. On the opposite, actors are “alive” indepedent processes with transactional memory.

An actor is basically like a server. It receives and sends messages, and can also start/stop other agents. By  “transactional state”, we mean that state is associated to a “conversation”; not to the actor itself, as opposed to objects having a global shared state. As a consequence actors are free of concurrency issues.

So?

So transactions with asynchronous messages are naturally expressed and we have no more concurrency issues!

What can we model with actors?

Everything that follows the client/server architecture: I/O, networking, the X window system… 
In fact, anything interacting with the environment can nicely be modelled with actors, as well as intelligent agents, jobs running in parrallel, etc.

And this is even more natural! Indeed, when reading a file, a DB or whatrever: why sitting there and waiting for the answer? When these are seen as asynchronous requests, computation can go on until the response arrives.

…Sounds nice. Is there anything further?

Yes, this goes wonderfully hand in hand with functional programming. …But more on this later.

Advertisements

Data structures in functional programming …big issues (?!)

November 1, 2008

Welcome to this short presentation where I show something simple turning out to have dramatic consequences. Data and relationships between them plays a vital role in any paradigm …let’s have a closer look of how these can be manipulated in a functional paradigm where data is immutable.

Let us start with something simple. Imagine we want to have a tree which could be navigable. That is, having a tree node, you could access both its children and its parent.

Ok, no problem, let us just define some data type like this for instance:

data Tree a = Tree
{
parent :: Maybe (Tree a),
content :: a,
children :: Forest a
}

This way, one would build data trees like this:

root = Tree
{
parent = Nothing,
content = “root”,
children = [child]
}

child = Tree
{
parent = Just root,
content = “child”,
children = []
}

So far so good you might think …Well, not really, here we already have two issues:

1. Changing a node == reconstruct the whole tree

Assume some operation takes a tree as input and outputs the same tree among with a single node was modified, added or deleted.
In any of these 3 cases, the consequences are the same:
– if node A has been modified/added/deleted, its children and parent has to be replaced with ones having updated references to A
– the same happens for their own children and parents
– …
– the whole tree becomes a replica of the original one

2. Coherence is not enforced

Nothing prevents you from creating bullshit where children do not reference their proper parents and vice-versa. Moreover, creating helper functions cannot really help since they cannot act locally. Indeed, because of issue 1, the whole tree must be built at once, it cannot be assembled of small pieces.

…And the tree was just an example. This applies to ANY navigable data structure!!!
When anything is modified, everything linked to it has to be replicated!
I guess there is no need to draw a picture when there is lots of data and (bidirectional) relationships between them.

One way around would be to use dictionaries to store the relationships like:
parent_child = [(root, chA), (root, chB), …]
And use the latter one for all operations. But this is both very inconvinient and inefficient.

Another way would be to use monads and mutable state …which boils down to simulating the imperative object-oriented paradigm (in a much uglier and complex manner).

…I’m curious of what you think about this, because the fact that something as simple as a tree involves such dramatic consequences looks pretty catastrophic to me.

About mixing imperative and functional…

June 20, 2008

Making a custom programming language is a tricky thing… Here come a few issues of the constructs as I thought them.

It was initially planned to use both funtional and imperative programming by providing two constructs, one for true equality and another for affectation. Moreover, this sounded like to provide nice ways to interact. With variables for data and equalitites used to give a formatted view of these. …Sounds weird? Ok, here is a small example:


declare width, height
surface = width * height
do
width := 2
height := 3
print surface # prints 6
width := 4
height := 7
print surface # prints 28

In the previous example, we declare the surface to be equal to the width times the height. It has the same effect than making a function out of area but is simply more expressive.

However …it goes with its issues as well. For example, the lack of references initially planned encounters some issues. In java, affectation of “primitive” elements are done by copy while affectation of “compound” elements (i.e. objects) are done by reference. However, I wanted to avoid the distinction between what is “primitive” and what not. While on the same time avoiding pointers.

In leo, equality is “referential equality”. Thus, when we write:

a = b

The identifier ‘a’ becomes equal to ‘b’, not to it’s content. We do not even evaluate ‘b’ at this moment. On the opposite, an affectation like this:

a := b

takes the content of b at this moment in time and copies the content into a. …The thousand question point is now: does it copy “in depth” the object or does it merely copy a handle to the content of ‘b’?

Let us take a few examples to illustrate this. Suppose we have a group of people, let’s say the pupils of a class with each one having a best friend. If we do:

alice.bestFriend := zoe
bob.bestFriend := zoe

Then we copy the content of zoe into both variable …here we would whish that both zoes are the same even if they are modified afterwards. Thus a referencial copy. What about:

a := 1
b := 1

In this case, there is nothing to do on the ones. Referencial copy has no sense, just copy that value. …But what if the integer would be 60 pages long? And what about this:

date = 07/05/2008
a := date

The issue doesn’t change …is it arbitrarily copied by reference or by value?
…In any case, the issue is the arbitrary frontier between what is primitive and what not, as well as how to decide to make the affectation by copying references or values.

The adopted solution is to always store a pointer in ‘a’! …even in the case of “a := 1”, ‘a’ will point to an anonymous “node” containing itself the value 1.

Thus the internal representation for:

a = b
b := 2

is:

a –> b –> anon_int : 2

So each number would be represented by a small little data object …nice 🙂
Notice also that = makes them always point to symbols while := always point to data objects.

By the way, == would:
first compare references, if they are same then reply true
else, compare the types and content.

Let us go over to another issue with a more practical example. Assume we have some graph and want to modify some properties of the node having the highest score based on some computation. There should be a function that returns the node having the highest score so that we can modify it accordingly.


graphA = ...
getBestNode = function (graph) -> (node)

do
graphB := graphA

nodeA := gestBestNode(graphA)
nodeB := gestBestNode(graphB)

nodeA.property := … # error!
nodeB.property := … # ok

In the last line …it means that we do not operate on the same data structure than graphA.
In this case, the nodeWe cannot do that!!! …it has no sense …graph cannot be equal to something that we modify afterwards
The greatest argument of functional programming is that it is stateless and deterministic. In the above case, it makes no sense anymore. Indeed, we retrieve an element of a graph to modify it afterwards. …so does this still fit in functional programming? …barely. I am no theorist anyway. The other issue is:

let us be firends…

alice.friend := zoe
bob.friend := zoe

what if

zoe = buildZoe()

Then zoe is either not modifiable or zoe is a copy.