| 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 -------------------------------------------------- |