[erlang-questions] Reassigning variables

[Richard O'Keefe]

On 18 Mar 2009, at 6:35 pm, Matthew Dempsky wrote:
>
> I'd prefer not to post the actual code that motivated this discussion,

Sigh.  I'm _sure_ this would be more use.
>
> but I will point out some code in OTP that uses numbered variables:
> the Erlang compiler.  It uses them quite significantly, with some
> functions
>
> matthew@REDACTED:~/src/otp_src_R12B-5/lib/compiler/src$ for x in `jot 11
> 0`; do echo -n "St$x: "; cat *.erl | grep -c
> "[^a-zA-Z0-9_]St$x[^0-9]"; done
> St0: 811
> St1: 612
> St2: 300
> St3: 120
> St4: 47
> St5: 29
> St6: 14
> St7: 10
> St8: 6
> St9: 2
> St10: 2
>
Great!  Numbers!  I love numbers!

The thing that strikes me here is that although numbered
variables are common, variables with *high* numbers are
rare.  Once you get past St0, it's very nearly an exponential
decay.

> I'm interested to know how you'd suggest rewriting v3_core:lc_tq/5
> using metaprogramming.

I never said anything about the Erlang compiler.
I said that *YOUR* problem sounded like a case for metaprogramming.
There's a big difference.

Let's look at that function and see what we find.

lc_tq(Line, E, [{generate,Lg,P,G}|Qs0], Mc, St0) ->
     {Gs,Qs1} =  splitwith(fun is_guard_test/1, Qs0),
     {Name,St1} = new_fun_name("lc", St0),
     {Head,St2} = new_var(St1),
     {Tname,St3} = new_var_name(St2),
     LA = lineno_anno(Line, St2),
     LAnno = #a{anno=LA},
     Tail = #c_var{anno=LA,name=Tname},
     {Arg,St4} = new_var(St3),
     {Nc,[],St5} = expr({call,Lg,{atom,Lg,Name},[{var,Lg,Tname}]}, St4),
     {Guardc,St6} = lc_guard_tests(Gs, St5),
     {Lc,Lps,St7} = lc_tq(Line, E, Qs1, Nc, St6),
     {Pc,St8} = list_gen_pattern(P, Line, St7),
     {Gc,Gps,St9} = safe(G, St8),
     Fc = function_clause([Arg], LA, {Name,1}),
     case {Guardc, Pc} of
         {[], #c_var{}} ->
             Cs0 = [#iclause{anno=LAnno,
                             pats=[#c_literal{anno=LA,val=[]}],guard=[],
                             body=[Mc]}];
         _ ->
             Cs0 = [#iclause{anno=#a{anno=[compiler_generated|LA]},
                             pats=[#c_cons{anno=LA,hd=Head,tl=Tail}],
                             guard=[],
                             body=[Nc]},
                    #iclause{anno=LAnno,
                             pats=[#c_literal{anno=LA,val=[]}],guard=[],
                             body=[Mc]}]
     end,
     Cs = case Pc of
              nomatch -> Cs0;
              _ ->
                  [#iclause{anno=LAnno,
                            pats=[#c_cons{anno=LA,hd=Pc,tl=Tail}],
                            guard=Guardc,
                            body=Lps ++ [Lc]}|Cs0]
          end,
     Fun = #ifun{anno=LAnno,id=[],vars=[Arg],clauses=Cs,fc=Fc},
     {#iletrec{anno=LAnno,defs=[{{Name,1},Fun}],
               body=Gps ++ [#iapply{anno=LAnno,
                                     
op=#c_fname{anno=LA,id=Name,arity=1},
                                    args=[Gc]}]},
      [],St9};

I'll look at just the first clause, that's more than enough.

The first thing I notice is that this is the kind of code that
makes me wonder whether I really like Erlang after all.  It
took a bit of head-scratching to figure out that the name
means something like "List Comprehension Translate Qualifier".

Now let's look at the first few state updates.

     {Name, St1} = new_fun_name("lc", St0),
     {Head, St2} = new_var(St1),
     {Tname,St3} = new_var_name(St2),
     {Arg,  St4} = new_var(St3),

-record(core, {
     vcount = 0,                        %Variable counter
     fcount = 0,                        %Function counter
     in_guard = false,                  %In guard or not.
     opts,                              %Options.
     es = [],                           %Errors.
     ws = [],                           %Warnings.
     file = [{file,""}]                 %File
}).

new_fun_name(Type, #core{fcount=C}=St) ->
     {list_to_atom(Type ++ "$^" ++ integer_to_list(C)),St#core{fcount=C 
+1}}.

new_var_name(#core{vcount=C}=St) ->
     {list_to_atom("cor" ++ integer_to_list(C)),St#core{vcount=C + 1}}.

new_var(St0) ->  % simplified
     {New,St} = new_var_name(St0),
     {#c_var{anno=[],name=New},St}.

I'm immediately struck by the fact that these three updates could
be done in any order.  We could imagine a "combo method"

     st_new(Ops, St) -> st_new(Ops, [], St).

     st_new([], R, St) -> {reverse(R),St};
     st_new([{fun_name,Type}|Ops], R, St0 = #core{fcount=C}) ->
	F = list_to_atom(Type ++ "$^" ++ integer_to_list(C)),
	St1 = St0#core{fcount = C+1},
	st_new(Ops, [F|R], St1);
     st_new([var|Ops], R, St0 = #core{vcount = C}) ->
	V = list_to_atom("core" ++ integer_to_list(C),
	I = #c_var{anno = [], name = V},
	St1 = St0#core{vcount = C+1},
	st_new(Ops, [I|R], St1);
     st_new([var_name|Ops], St0) ->
	V = list_to_atom("core" ++ integer_to_list(C),
	St1 = St0#core{vcount = C+1},
	st_new(Ops, [V|R], St1);
     ...

instead of all the little methods, and then
...
     {[Name,Head,TName,Arg],St4} =
	st_new([{fun_name,"lc"},var,var_name,var], St),

Not a big step, but
  - it makes clear which sequences of "operations" don't really
    need to be done in any particular sequence
  - it does save 3 of the state variables.

But that misses the point too.
What I'm really itching to do is to rewrite in Haskell
using a State monad:

-changer(core, [lc_tq/4, new_fun_name/0, new_var/0, new_var_name/0,
                 expr/2, lc_guard_tets/1, list_gen_pattern/2, safe/1
-reader( core, [lineno_anno/1]). 		

lc_tq(Line, E, [{generate,Lg,P,G}|Qs0], Mc) ->
     {Gs,Qs1} =  splitwith(fun is_guard_test/1, Qs0),
     Name = new_fun_name("lc"),
     Head = new_var(),
     Tname = new_var_name(),
     LA = lineno_anno(Line),
     LAnno = #a{anno=LA},
     Tail = #c_var{anno=LA,name=Tname},
     Arg = new_var(),
     {Nc,[]} = expr({call,Lg,{atom,Lg,Name},[{var,Lg,Tname}]}),
     Guardc = lc_guard_tests(Gs),
     {Lc,Lps} = lc_tq(Line, E, Qs1, Nc),
     {c = list_gen_pattern(P, Line),
     {Gc,Gps} = safe(G),
     Fc = function_clause([Arg], LA, {Name,1}),
     Cs0 = if Guardc == [], is_record(Pc, c_var) ->
              [#iclause{anno = LAnno,
                        pats = [#c_literal{anno=LA,val=[]}],
                        guard= [],
                        body = [Mc]}]
	   ; true ->
	     [#iclause{anno = #a{anno=[compiler_generated|LA]},
                        pats = [#c_cons{anno=LA,hd=Head,tl=Tail}],
                        guard= [],
                        body = [Nc]},
               #iclause{anno = LAnno,
                        pats = [#c_literal{anno=LA,val=[]}],
		       guard= [],
                        body = [Mc]}]
           end,
     Cs = if Pc == nomatch ->
             Cs0
           ; true ->
             [#iclause{anno = LAnno,
                       pats = [#c_cons{anno=LA,hd=Pc,tl=Tail}],
                       guard= Guardc,
                       body = Lps ++ [Lc]}|Cs0]
          end,
     Fun = #ifun{anno=LAnno,id=[],vars=[Arg],clauses=Cs,fc=Fc},
     {#iletrec{anno=LAnno,defs=[{{Name,1},Fun}],
               body=Gps ++ [#iapply{anno=LAnno,
                                     
op=#c_fname{anno=LA,id=Name,arity=1},
                                    args=[Gc]}]},
      []};

where a declaration like

-changer(Type, [...F/N...]).

means that a call P = F(E1,...,EN)
really stands for {P,S1} = F(E1,...,EN,S0)

and a declaration like

-reader(Type, [...F/N...]).

means that a call P = F(E1,...,EN)
really stands for P = F(E1,...,EN,S0)

with the Si being threaded through automatically.
This is just like, indeed in all important essentials, it _is_
the DCG rule to ordinary clause translation of Prolog.

Just as metaprogramming turns
	p(X, Y) --> q(X), r(Y).
into
	p(X, Y, S0, S) :- q(X, S0, S1), r(Y, S1, S)
in Prolog, so it could turn
	f(X) -> Y = g(X), h(X, Y)
into
	f(X, S0) -> {Y,S1} = g(X, S0), h(X, Y, S1)
in Erlang.

It's not _trivial_ (as I know to my cost), but it's not
rocket science either.

So, much to my surprise, the answer seems to be yes,
metaprogramming _would_ help this a lot.