lördag, oktober 24, 2009

What are BIF's?

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.

torsdag, april 09, 2009

Backtracking in Erlang, part 2 - passing data

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.

onsdag, mars 18, 2009

Backtracking in Erlang, part 1 - control

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.