chiark - git - mdw - fringe/blob - erlang-fringe.erl

   1 %%% -*-erlang-*-
   2 %%%
   3 %%% Erlang implementation of a `same-fringe' solver.
   4
   5 -module('erlang-fringe').
   6 -export([main/0, tree_fringe/1]).
   7
   8 %%%--------------------------------------------------------------------------
   9 %%% Iteration protocol.
  10
  11 %% An iterator is a process I which responds to the message {next, P} by
  12 %% sending to process P either {item, I, X} or {done, I}.  (The iterator's
  13 %% process id helps us work out which iterator we're getting a reply from.)
  14
  15 yield(X) ->
  16     %% Called from an iterator: yield the term X.
  17     receive
  18         {next, P} -> P ! {item, self(), X}
  19     end.
  20
  21 next(I) ->
  22     %% Fetch the next item from the iterator I, as a tuple {item, X}, or the
  23     %% symbol `done' if there's nothing left..
  24     I ! {next, self()},
  25     receive
  26         {item, I, X} -> {item, X};
  27         {done, I} -> done
  28     end.
  29
  30 iterator(M, F, A) ->
  31     %% Create and return an iterator process given a function F in module M,
  32     %% passing it the argument list A.
  33     spawn(fun () ->
  34               apply(M, F, A),
  35               receive
  36                   {next, P} -> P ! {done, self()}
  37               end
  38           end).
  39
  40 map_iterator(I, F) ->
  41     %% Apply F to each item returned from the iterator I.  Return the atom
  42     %% `done'.
  43     case next(I) of
  44         {item, X} ->
  45             apply(F, [X]),
  46             map_iterator(I, F);
  47         done ->
  48             done
  49     end.
  50
  51 iterators_equal(I, J) ->
  52     %% Answer whether the iterators I and J return the same elements, as
  53     %% decided by pattern-matching.
  54     X = next(I),
  55     Y = next(J),
  56     case {X, Y} of
  57         {done, done} -> true;
  58         {{item, Z}, {item, Z}} -> iterators_equal(I, J);
  59         _ -> false
  60     end.
  61
  62 %%%--------------------------------------------------------------------------
  63 %%% Node structure.
  64
  65 %% A tree is either the atom `nil' or a tuple {LEFT, DATUM, RIGHT} of the
  66 %% LEFT and RIGHT subtrees and the DATUM, which may be any term.
  67
  68 %% Iteration is easy.  We just use a separate process.
  69 tree_fringe({L, D, R}) ->
  70     tree_fringe(L),
  71     yield(D),
  72     tree_fringe(R);
  73 tree_fringe(nil) ->
  74     ignore.
  75
  76 %% Parse a tree from a textual description.  The syntax is simple:
  77 %%
  78 %%      tree ::= empty | `(' tree char tree `)'
  79 %%
  80 %% where the ambiguity is resolved by declaring that a `(' is a tree if we're
  81 %% expecting a tree.
  82 do_parse_tree([$( | S]) ->
  83     case do_parse_tree(S) of
  84         {L, [D | SS]} ->
  85             case do_parse_tree(SS) of
  86                 {R, [$) | SSS]} -> {{L, D, R}, SSS};
  87                 _ -> throw({simple_error, "missing )"})
  88             end;
  89         _ ->
  90             throw({simple_error, "no data"})
  91     end;
  92 do_parse_tree(S) ->
  93     {nil, S}.
  94
  95 parse_tree(S) ->
  96     case do_parse_tree(S) of
  97         {T, []} -> T;
  98         _ -> throw({simple_error, "trailing junk"})
  99     end.
 100
 101 %%%--------------------------------------------------------------------------
 102 %%% Main program.
 103
 104 main() ->
 105     try
 106         case init:get_plain_arguments() of
 107             [S] ->
 108                 T = parse_tree(S),
 109                 I = iterator('erlang-fringe', tree_fringe, [T]),
 110                 map_iterator(I, fun(X) -> io:put_chars([X]) end),
 111                 io:nl();
 112             [S, SS] ->
 113                 I = iterator('erlang-fringe', tree_fringe, [parse_tree(S)]),
 114                 J = iterator('erlang-fringe', tree_fringe, [parse_tree(SS)]),
 115                 case iterators_equal(I, J) of
 116                     true -> io:format("match~n");
 117                     _ -> io:format("no match~n")
 118                 end;
 119             _ ->
 120                 throw({simple_error, "bad args"})
 121         end
 122     catch
 123         {simple_error, M} ->
 124             io:format(standard_error, "erlang-fringe: ~s~n", [M]),
 125             init:stop(1)
 126     end,
 127     init:stop().
 128
 129 %%%----- That's all, folks --------------------------------------------------