Erlang is a language which is dynamic in many aspects.
One of the things that are resolved statically, however, is pattern matching; the decision trees used for branching in function clauses, case statements, and receive statements are constructed on compile time.
For instance, a set of patterns like
[X] when X==0 orelse X==100
[H|T]
[]
is translated by the Erlang compiler into the following decision tree:
is_nonempty_list(B)?
+-Y-> [H|T] = B
| is_nil(T)?
| +-Y-> H == 0?
| | +-Y-> case 1
| | | ^
| | | |
| | | Y
| | | |
| | +-N-> H == 100?
| | |
| | N
| | |
| | v
| +---------> case 2
|
+-N-> is_nil(B)?
+-Y-> case 3
+-N-> No match.
The Erlang compiler is quite good at constructing such decision trees, which is good, because it's critical to the performance of typical Erlang programs.
(Actually, if the compiler was poor at that job, “typical Erlang programs” would probably often look different, because developers would be more inclined to write their own decision trees. Compilers form developers, to some extent.)
If you want to construct a predicate dynamically, you can do that, using function composition or an interpreter function — that is for instance how the Eshell is implemented. For instance, the first pattern above can be described as
{is_pair,
{'or', {is_eq, 0}, {is_eq, 100}},
is_nil}
which can be interpreted by a predicate evaluator like:
eval(is_nil, []) -> true;
eval({is_pair, HP, TP}, [H|T]) -> eval(HP,H) andalso eval(TP,T);
eval({is_eq, V}, V) -> true;
eval({'or', P1,P2}, V) -> eval(P1,V) orelse eval(P2,V);
eval(P, V) when is_function(P,1) -> P(V);
eval(_, _) -> false.
However, you can't do a selective receive using such a predicate, because one of those statically-constructed decision trees is always used for selecting which message to extract from the inbox; and once it's taken out of the inbox it cannot be put back again. Only after a message is extracted from the inbox can more general code be applied to it.
When is this a problem?
Well, the Erlang shell is one example; here, dynamic selective receive will have to be faked: buffering is needed, and in fact the timeout mechanism of the Erlang receive construct is (last I checked, which is a few years ago) emulated only incompletely. I know that I filed a bug report about that issue, but I can't find it now.
Also, it's an issue that may sometimes arise when you're trying to combine two concerns in one process, and each of the concerns communicate with other processes; in such cases, it would sometimes be convenient to have parameterizable selective receive.
Solutions
For this problem, I've found a solution which looks promising.
The solution is sufficiently cheaty, however, that I should probably first mention a couple of more “in the spirit” solutions; all three solutions can be considered to be cheating, but at least I can offer different flavours of unrulyness.
Construct, dynamically, a module which implements a function which does the selective receive. Constructing and compiling modules dynamically is relatively easy in Erlang. Calling a function in a runtime-specified module is just everyday Erlang; it's Erlang primary kind of polymorhism.
You wouldn't want to do this module construction business for something that needs to be done a million times, but it's probably a good exercise.
Take as a parameter a predicate function which is to be used for selecting the message. Access the process's inbox through the backdoor:
process_info(self(), messages), and apply the predicate to each message in turn until an acceptable one is found (or the end of the list is reached, in which case you wait a bit and retry). Now you know exactly which message you want to extract, and that's straightforward to do (the decision tree for that is static).I can only recommend this approach if you don't care about performance or ugly hacks. Also, there's no really good way of handling the no-such-message-yet case, as far as I can see.
Take advantage of the fact that what is possible in Beam — the VM's instruction set — is a superset of what's possible in Erlang. In particular with respect to the receive construct. This is the solution that I will describe below.
The following module is a quite general solution which uses a matchspec as a predicate. It is written in Erlang assembly, because at this level this hack becomes possible:
%% File: dyn_sel_recv.S
{module, dyn_sel_recv}. %% version = 0
{exports, [{match_spec_receive,2}]}.
{labels, 5}.
{function,match_spec_receive,2,2}.
{label,1}.
{func_info,{atom,match_spec_magic},{atom,match_spec_receive},2}.
{label,2}.
{allocate,2,2}.
{move,{x,1},{y,0}}.
{move,{x,0},{y,1}}.
{label,3}.
{loop_rec,{f,5},{x,0}}.
%% x0 = Msg, y0 = Timeout, y1 = CMS
{test_heap,2,2}.
{put_list,{x,0},nil,{x,0}}.
%% x0 = [Msg]
{move,{y,1},{x,1}}.
%% x1 = CMS
{call_ext,2,{extfunc,ets,match_spec_run,2}}.
%% x0 = [] | [Res]
{test,is_nonempty_list,{f,4},[{x,0}]}.
{get_list,{x,0},{x,1},{x,2}}.
{move,{x,1},{x,0}}.
%% x0 = Res
remove_message.
{deallocate,2}.
return.
{label,4}.
{loop_rec_end,{f,3}}.
{label,5}.
{wait_timeout,{f,3},{y,0}}.
timeout.
{move,{atom,timeout},{x,0}}.
{deallocate,2}.
return.
To test it, we have this module:
%% File: dyn_recv_test.erl
-module(dyn_recv_test).
-include_lib(“stdlib/include/ms_transform.hrl”).
-export([test/0]).
test() ->
%% The pattern (and what it should result in):
MS = ets:fun2ms(fun({ping, X}) -> {pong,X} end),
%% Compile the pattern:
CMS = ets:match_spec_compile(MS),
%% Perform a selective receive based on the pattern:
dyn_sel_recv:match_spec_receive(CMS, 1000).
A sample interaction, with comment marked with "#" and "%":
# Compile the code:
$ erlc dyn_recv_test.erl dyn_sel_recv.S
# Then start an Erlang shell:
$ erl
Erlang R14B (erts-5.8.1) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]
Eshell V5.8.1 (abort with ^G)
1> dyn_recv_test:test(). % No appropriate messages - times out
timeout
% Fill the inbox with test data:
2> self() ! 'before'.
before
3> self() ! {ping, 144}.
{ping,144}
4> self() ! {ping, 1234}.
{ping,1234}
5> self() ! 'after'.
'after'
6> process_info(self(), messages). % There are four messages in the inbox now
{messages,[before,{ping,144},{ping,1234},'after']}
7> dyn_recv_test:test(). % Receive first ping message
{pong,144}
8> dyn_recv_test:test(). % Receive second ping message
{pong,1234}
9> dyn_recv_test:test(). % Times out again - no more ping messages
timeout
10> process_info(self(), messages). % Now, only the non-pings are left.
{messages,[before,'after']}
Discussion
Why restrict ourselves to matchspecs?
In principle you could instead construct a receive function which accepts a general predicate function, but that would be risky — while I'm reasonably confident that the matchspec hack works (no guarantees though!), I'm fairly certain that the Erlang VM would take offense if such a predicate were to e.g. do any receiving of its own, or throw exceptions.
Matchspecs, on the other hand, can do just that which is possible to do in a regular pattern matching construct in Erlang — in particular, no side effects are allowed.
And matchspecs can be preprocessed (“compiled”) into a form which is interpreted efficiently; yet their source form can be constructed with relative ease at runtime. Finally, matchspecs have the nice thing about them that even though they are represented as ordinary Erlang terms, and as such may be a somewhat hard to read (and write) if they are complex, there is a parse-tree transformation which makes it possible to write them just as ordinary Erlang patterns and conditions — this is demonstrated in the above.
Now, I haven't yet had the chance to use this hack in a real context, but here it is. If nothing else, I suppose it demonstrates that it is quite possible to allow matchspecs in Erlang's pattern-matching constructs — at least that there does not seem to be any VM-level reason against it. I think that might be an interesting language extension; then again, there are plenty of other language extension discussions, and this suggestion would probably not get high priority.
No comments:
Post a Comment