Commit | Line | Data |
---|---|---|
18b71d38 MW |
1 | %%% -*-erlang-*- |
2 | %%% | |
3 | %%% Erlang implementation of a `same-fringe' solver. | |
4 | ||
3f23c90e | 5 | -module('erlang-fringe'). |
18b71d38 MW |
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), | |
3f23c90e | 109 | I = iterator('erlang-fringe', tree_fringe, [T]), |
18b71d38 MW |
110 | map_iterator(I, fun(X) -> io:put_chars([X]) end), |
111 | io:nl(); | |
112 | [S, SS] -> | |
3f23c90e MW |
113 | I = iterator('erlang-fringe', tree_fringe, [parse_tree(S)]), |
114 | J = iterator('erlang-fringe', tree_fringe, [parse_tree(SS)]), | |
18b71d38 MW |
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} -> | |
3f23c90e | 124 | io:format(standard_error, "erlang-fringe: ~s~n", [M]), |
18b71d38 MW |
125 | init:stop(1) |
126 | end, | |
127 | init:stop(). | |
128 | ||
129 | %%%----- That's all, folks -------------------------------------------------- |