Robert on anything

What are BIF's?

2009-10-24T16:13:00.002+01:00

There has always been much confusion about what a BIF really is, how they relate to the Erlang language. An example of this was a discussion earlier this year when someone wanted to have some more functions in lists coded in C and so become part of Erlang. Saying that they are functions coded in C just tell us how they are implemented not what they *are*.

The source of this confusion is very old and exists in the earliest documentation, where a BIF was described as function "which could not be written in Erlang or written in C for efficiency". They were in some sense implicitly part of Erlang and considered to be in the module 'erlang'. Some could be used without specifying the module but there was no clear reason why some needed the module and others did
not.

A first proper attempt to define what a BIF is came when Jonas Barklund and I wrote the Erlang specification. There we proposed that a BIF was part of the Erlang language that did not have a special syntax but looked like a normal function call. Spawn, link and trapexit are just as much part of Erlang as ! and receive even though they use normal function syntax and semantics. We also decided that it was irrelevant in what language the function was written, what was important was the function itself. This is analogous to processes where the semantics are what is important. I think this definition is correct but calling them BIFs was wrong.

Our BIF proposals were put on ice together with the Erlang specification.

The problem still remains and has not become better - there is still much confusion as to what a BIF is, if being coded in C has anything to do with it, and if being coded in C means that the functions automatically becomes part of the language. BEAM and the compiler also handle BIFs in many different ways which does not always help.

Currently BIF is used to describe at least three different things:

- Functions which are part of Erlang, spawn and link are examples of this.

- Functions which are not part of Erlang but which are part of a basic runtime system, the trace BIFs are an example of this.

- Functions which have been coded in C for efficiency, for example lists:reverse.
(Some might not agree with separating the first two)

Moving the module 'erlang' from kernel to erts is a step in the right direction. As is putting the new unicode BIFs (?) in a separate module, because they are not part of the language just a library where some functions are coded in C.

OK, so why worry about it? Does it really matter? I think it does (or else I wouldn't be writing this mail) for the following reasons:

- We need a proper language specification and this would be a part of it. Some day I plan to resurrect the old Erlang spec and get it up to date and we have to start somewhere.

- It would clarify what is part of the language and what is not. This would put various discussions about adding things to the implementation/language in their proper context. So coding a function in lists in C would just become an implementation detail where the issue would be whether it is worth the extra effort to do this, and not misplaced discussions about adding to the language.

- I think it would allow you to do more with the FFI than is proposed today and still be consistent with the language.

- And it would help people realise and understand what is what - unclarity and confusion are never good.

Backtracking in Erlang, part 2 - passing data

2009-04-09T02:16:00.006+01:00

In the first part I showed how we could program backtracking in a generic way in Erlang. While Erlang does not directly support it, it is relatively easy to do. In this part we will look at some ways of handling data within this context. The basic problem is how to get data out of a function as in this context functions never return.

For a specific application this may not be a problem as either each function always explcitly knows what the contunation is, or a it is possible to have a local convention of how to pass arguments. For an example of this see the Erlog parser in the file erlog_parse.erl where each continuation function has two arguments, the remaining tokens and the term parsed so far. This works well for this specific case.

This is not possible in the general case or when writing generic functions. Seeing we cannot return values we will adopt the method used in logic languages like prolog (or C) of "returning" values through the function arguments. For example the following "function" fubar/2 (written in a logic style) which takes input in the argument X and "returns" data through the argument Y:


fubar(X, Y) :- foo(X, M, N), bar(M, O), baz(N, O, Y).

Each of the functions foo/3, bar/2 and baz/3 behave in a similar way but they have varying numbers of input and output arguments.

I will show one way how this can done. We will define a variables structure which contains the bindings of variables. It has the following interface:


new_vars() -> Vars.
new_var(Vars) -> {Var,Vars}.
bind_var(Var, Value, Vars) -> Vars.
get_var(Var, Vars) -> Value.

A requirement on the Vars structure is that all variable bindings are undone on backtracking. Note that we are not really defining logical variables here or implementing unification, we are just creating variables and binding them. There is no default value for a variable, trying to get the value of an unbound variable will generate an error.

We will adopt the convention that all continuation functions have one argument and they will be called with the current Vars structure. We will also adopt the convention that each normal function will have its arguments in the following order: first come normal Erlang arguments, then the Vars structure, then the arguments which use the Vars structure with the input arguments first followed by the output arguments, and finally the continuation. Using Vars and this convention we could translate fubar/2 into the following Erlang function:


fubar(Vars0, X, Y, Next) ->
    %% Create the new variables in fubar.
    {M,Vars1} = new_var(Vars0),
    {N,Vars2} = new_var(Vars1),
    {O,Vars3} = new_var(Vars2),
    Next2 = fun (Vars) -> baz(Vars, N, O, Y, Next) end,
    Next1 = fun (Vars) -> bar(Vars, M, O, Next2) end,
    foo(Vars, X, M, N, Next1).

Here we have assumed that fubar is part of a larger application which has created the Vars structure. The continuation function is called with the current Vars. So for example the (trivial) function bar/2 which has M as input and binds O for output could be written:


bar(Vars0, M, O, Next) ->
    Mval = get_var(M, Vars),
    Oval = do_stuff(Mval),
    Vars1 = bind_var(O, Oval, Vars),
    Next(Vars1).

Choice points are now introduced by:


cp([fun (Vs) -> do_stuff_a(Vs, Next) end,
   fun (Vs) -> do_stuff_b(Vs, Next) end,
   fun (Vs) -> do_stuff_c(Vs, Next) end,
   ...], Vars).

The code for cp/2, is still simple:


cp(Vars, [G|Gs]) ->
   case G(Vars) of
       {succeed,Value} -> {succeed,Value};
       fail -> cp(Vars, Gs)
   end;
cp(_, []) -> fail.

We see here that if the Vars structure does not use side effects then we will automatically undo all bindings on backtrackíng.

I will give a simple definition of the Vars structure and its interface. It uses dicts to store the variable bindings.


-record(vars, {vc,dict}).

new_vars() -> #vars{vc=0,dict=dict:new()}.

new_var(#vars{vc=Vc,dict=Dict}=Vars) ->
   {{var,Vc},Vars#vars{vc=Vc+1}}.

bind_var({var,Var}, Value, #vars{dict=Dict}=Vars) ->
   Vars#vars{dict=dict:store(Var, Value, Dict)}.

get_var({var,Var}, #vars{dict=Dict}) ->
   dict:fetch(Var, Dict).

That's it, we're done. Again a lot of explanation for quite a simple concept and very little code.

In the next installment I will give an example of how this can be used and some problems with the current implementation.

Backtracking in Erlang, part 1 - control

2009-03-18T01:47:00.010Z

Sometimes you need to be able to do search algorithms which can step back and try other alternate ways of finding a solution, "backtracking". Generally this is difficult to do in functional languages like Erlang (most other languages too for that matter). A classic example of this type of problem is parsing ambiguous grammars.

Prolog syntax is like that, in some cases you need almost indefinite look-ahead before you can decide how input is to be parsed. When I implemented Erlog (a prolog in and for Erlang) I decided to do the parser in Erlang so that it could run stand-alone and so I ran straight into this problem.

Here is *a* solution to the problem. It is in two parts, the first describing the control structures and the second (more difficult) describing handling of data. There may also be a third part discussing some problems with the solution to control, if anyone is still interested.

The main problem we have to overcome is that normally when you choose a path you "commit" to it and can't go back and try an alternate path. For example in:


case get_a_value() of
    Choice1 -> ... ;
    Choice2 -> ... ;
    ...
end

once you have chosen a path, say Choice1, there is no (simple) way to go back try Choice2 if you later decide that Choice1 was wrong. We can't backtrack.

Another problem is that if we have:


a() -> foo(), bar(), baz().

and once we have completed foo() then even if it gave an answer which later was shown to be wrong there is no way to step back into it, backtrack, and let it give a new answer.

In this first section we will (almost) completely ignore arguments and return values.

When looking at control we will (almost) completely ignore arguments and returning values. We will use the convention that functions return either '{succeed,Value}' when they succeed or 'fail' when they can't find a solution.

The trick is to ensure that functions only return at all when they fail, otherwise they just continue by explicitly calling the next thing which should be done. We will do this by using a Continue Passing Style (CPS) where each function will have an argument which is the next function call to continue. (CPS is not new and is generally known) So functions will usually look like this:


a(Next) ->
    do_stuff(),
    OurNext = fun () -> even_more_stuff(Next) end,
    more_stuff(OurNext).

We will use the convention that when a function fails and cannot go on it will return 'fail'. When *the* solution has been found then the final test will return {succeed,Value}. So the top level function will look something like:


top_call() ->
    Succeed = fun () -> {succeed,yes} end,        %We have succeeded
    find_solution(Succeed).

So now our program will keep going forwards until it finally calls the Succeed fun when it all returns back to the initial caller.

The next problem is to introduce 'choice points' where we can choose one path but still allow the code to backtrack and make another choice. This is the done in the function cp/1 where the argument is a list functions which are separate paths to choose from:


cp([fun () -> do_stuff_a(Next) end,
    fun () -> do_stuff_b(Next) end,
    fun () -> do_stuff_c(Next) end,
    ...]).

Cp/1 will try the functions in order, if one succeeds then the choice point will succeed and return the same succeed value, if it fails then the next function in the list will be tried, until no more exist when the choice point will fail: The code for cp is simple:


cp([G|Gs]) ->
    case G() of
        {succeed,Value} -> {succeed,Value};
        fail -> cp(Gs)
    end;
cp([]) -> fail.

That's it, we're done. A lot of explanation for very little code.

A slight variation is to not chain the continuation together as shown here but to have Next as a list of functions to call. Instead of directly calling Next you call next/1 with argument Next, next(Next), where next/1 is defined as:


next([N|Ns]) -> N(Ns).

There is no functional difference it just make writing some code a bit easier. For example the function defined above:


a() -> foo(), bar(), baz().

would look like this in the normal way:


a(Next) ->
    Next1 = fun () -> baz(Next) end,
    Next2 = fun () -> bar(Next1) end,
    foo(Next2).

while using the list variant it would look like:


a(Next) ->
    foo([fun (Ns) -> bar(Ns) end,
         fun (Ns) -> baz(Ns) end | Next]).

which can be easier to read, especially if there many calls in the continuation.

After I introduce handling data in the next installment I can give a proper example.

The Erlang Rationale - The problem with ‘if’

2008-11-28T21:18:00.002Z

Sigh. If was added as an almost “on the spur of the moment” hack. We knew how to compile guards and thought it might be useful in the case where you don’t have a value to match against. As Erlang has pattern matching we found that a “pure” if is used less than in many other languages, we never used it much ourselves and therefore didn’t really worry much about it. This is not really that strange as in many languages if is used in way which resembles very trivial pattern matching. For example in C:

if ((x = get_some_value()) != 0) {
do stuff with x
else {
do some other stuff
}

Also I don’t really have a problem using case when I want to do a conditional, but then again I am so used to it I don't think about it.

There have been repeated suggestions and discussions of either extending if to allow user defined boolean functions or adding a new construct. The problem with extending if is that the tests would no longer be guard tests and would handle differently for exceptions. A guard test silently just fails while a normal expression generates an error, which would make the change incompatible. We actually made cond a reserved word but never got around to adding it to the language.

The Erlang Rationale - Characters and strings

2008-11-08T22:23:00.002Z

This is one non-terminating discussion we had.

There have been many suggestions whether to have a proper type character data type or to leave them as integers. While adding a new type would not have been difficult we could not quite agree as to whether we should do it. If so which encoding should we use, stay with ASCII or go to ISO-8859-1 (Latin1) or UNICODE? If we changed to UNICODE should we also allow that in atoms as well? In the end we decided not to add a character type but make sure we could handle Latin1 in the libraries. As our primary application area was not handling text we felt that this was sufficient.

Very early on we decided that strings were lists. This was partly environment as many of the languages we were using, such as Prolog, use lists and partly practical as lists are a very powerful data type.

Using a general data type like lists and having characters is seldom as problem as you usually know what if you are processing a list which is a string or if it is something else. It is only within generic functions like printing or the shell where you can have problems with such a general data type.

The Erlang Rationale

2008-11-03T21:33:00.003Z

A while back I released the Erlang Rationale which is an attempt to explain why things look like they do in Erlang and our thinking behind many of the properties and features of the language. There is also some descriptions of part of the system which today seem to lack description, for example the i/o system and groups. The Rationale mainly deals with the core parts of the language and the older parts of the libraries and not OTP.

It can be found on trapexit.org here

The rationale is not finished and I am adding to it and expanding/improving what is already there. When there has been a significant enough change I will release a new version. However, someone suggested I could release new bits as they come and get comments and suggestions. This seems like a good idea and i will try it.

Gogol på Roma Teatern

2008-07-06T23:24:00.002+01:00

Igår var vi på Roma Teatern på Gotland och såg på Revisorn av Gogol. Det var en riktigt bra uppsättning och väl värt att se. Jag kan rekomendera att ni går och ser den om ni är på Gotland under sommaren.

Det enda tråkiga var att få reda på hur lite bidrag Roma teatern får jämfört med t.ex. riktsteatrar och olika "fria" teatergrupper. Tydligen att göra bra uppsättningar år efter år som folk uppskattar är inte något som prioriteras av stat och kommun.

"Optimerad laddning"

2008-03-19T01:34:00.003Z

Jag har en Sony Ericsson K610i som för det mesta tycks fungera bra (fast ibland tror jag att den stänger av sig själv). Det som förundrar mig är att när man laddar den så säger den "Optimerad laddning". Då undrar jag förstås om den även klarar av "Ooptimerad laddning" och vad i så fall är skillnaden. Eller är det bara någon marketroid som har en tänkt lite mer än vad han/hon borde?

Virding's First Rule of Programming

2008-01-11T02:02:00.000Z

After reading the blogs about how good Erlang's concurrency model is and how we just just made a super implementation of it in XXX I have been led to formulate Virding's First Rule of Programming:

Any sufficiently complicated concurrent program in another language contains an ad hoc informally-specified bug-ridden slow implementation of half of Erlang.

With all respect to Greenspun.

Att installera Windows XP på en Dell XPS M1330

2007-09-30T13:56:00.000+01:00

I veckan fick jag en ny dator. Det är en Dell XPS M1330, en trevlig liten dator med god prestanda och ett bra grafikkort för att vara så liten. Enda verkliga nackdelen med den är att den endast leveras med Windows Vista.

Av någon mystiskt anledning leveras den bara med Vista eftersom Dell anser att det är en dator för privatpersoner och dessa skall använda Vista. Nu skall jag ha den till jobbet där vi kör XP och jag f.ö. inte är intresserad av att använda Vista. Definitivt inte innan ett par service packs och troligen inte efter det heller.

Då var problemet att få XP att fungera på den och att få rätta drivers till den. Dell supportar inte XP men det finns några drivers och applikationer på deras support sida. Efter lite sökning så hittade jag denna fantastiska tråd på dellcommunity som "tells it all":

http://www.dellcommunity.com/supportforums/board/message?board.id=insp_general&thread.id=253132

Jag har bara två kommentarer till vad som sägs där:

1. Jag behövde inte ladda ner något extra för att få ljudkortet att fungera, bara drivers
2. Jag hittade en bättre (och nyare) driver för grafikkortet genom:

http://www.laptopvideo2go.com/forum/index.php?showtopic=8128
http://www.laptopvideo2go.com/forum/index.php?showtopic=13742

Med den info som fanns här kunde jag ladda nre drivers från NVIDIA's hemsida och mycket enkellt få det att fungera. Jag använder v162.18 nu.

På det hela gick det mycket smärtfritt och var bara att ladda ner och installera allt.

New Erlang book

2007-05-22T00:40:00.000+01:00

There is a new Erlang book coming out soon, Programming Erlang: Software for a Concurrent World by Joe Armstrong, which is very good and a great improvement over the old book. Apart from a very understandable description of the language it all also describes some of the more generally useful libraries, and gives real-world examples of how to use them. As I already know the language it is the second part of the book which I find most helpful.

In all the book is well worth reading.

Dåliga förlorare

2007-05-13T22:20:00.000+01:00

Efter att ha lyssnat en del på ESC i går kväll så tycker jag att kommentatorerna visade tecken på att vara extremt dåliga förlorare. Bara för att vi inte vann var allting kasst, östländerna bara kompisröstade och det hela var en stor skandal. Detsamma gäller många av de inlägg man läser i tidningarna idag.

Den som ger sig in i leken får leken tåla, och det gör vi visst inte.