Traversing graphs

[Vladimir Sekissov]

Good day,

vlad_dumitrescu> What I want to do is process the grammar in different ways: for example, 
vlad_dumitrescu> simplifying it or eliminating unreferenced productions. Most of the times, 
vlad_dumitrescu> it's easy to traverse everything, but there are some special cases, where I 
vlad_dumitrescu> have to propagate production attributes "upwards".

vlad_dumitrescu> I think I didn't see those before because I was locked on 
vlad_dumitrescu> finding a completely functional solution. It should be possible and now it 
vlad_dumitrescu> has become an intellectual chalenge.

May be it could be easier with continuation-passing style because you
don't know every time at upper level would you have some productions to
propagate later or not. Something like this(in pseudocode):

traverse_node({Node, Content}, UpperCont) ->
  PartResult = make_what_I_can_at_this_moment(Node),
  CurrentCont =
    fun (V) ->
        compute_node(V, UpperCont, PartResult)
    end,
  traverse_content(Content, CurrentCont, []).
  
traverse_content([], NodeCont, Acc) ->
  NodeCont({nomore, lists:reverse(Acc)});
traverse_content([TreeNode|Rest], NodeCont, Acc) ->
  Cont = fun (V) ->
             compute_content_node(V, NodeCont, Rest, Acc)
         end,
  traverse_node(TreeNode, Cont).

%% node traversing finished
compute_content_node({nomore, Result}, UpperCont, Rest, Acc) ->
       %% continue with rest of nodes
       traverse_content(Rest, UpperCont, [Result|Acc]);
%% it is the intermediate result, feed it to upper level and return
%% new continuation to the current
compute_content_node(Other, UpperCont, Rest, Acc) ->
  NxtUpperCont = UpperCont(Other),
  fun (V) ->
      compute_content_node(V, NxtUpperCont, Rest, Acc)
  end.

compute_node(V, UpperCont, PartResult) ->
  case V of
    %% lower level finished, we too
    {nomore, Result} ->
      finish_computation(Result, PartResult),
      UpperCont({nomore, finish_computation(Result, PartResult)});
    %% do intermidiate computation, return next continuation
    ForMe ->
      NxtResult = part_computation(ForMe, PartResult),
      fun (NxtV) ->
          compute_node(NxtV, UpperCont, NxtResult)
      end;
    %% propogate information to upper level, return next continuation
    ForYou ->
      NxtUpperCont = UpperCont(ForYou),
      fun (NxtV) ->
          compute_node(NxtV, NxtUpperCont, PartResult)
      end
  end.

Best Regards,
Vladimir Sekissov