Sorry to revive an old thread, but I
just came across this paper in my list future papers to read and
it seems quite relevant. I believe Keean was arguing for inferring
arity based on call sites, but there was some confusion about what
this means IIRC. Here's a paper that describes such an arity
analysis:
Higher order combinators in functional programming
languages
can lead to code that would be considerably more
efficient if some functions’ definitions were eta-expanded, but
the existing analyses are not always precise enough to allow
that. In particular, this has prevented the implementation of
foldl via foldr, which would allow foldl to take part in list
fusion.
Call Arity is an analysis that eta-expands functions based
on their uses, instead of their definitions, and is very precise
in the presence of recursion. Its inclusion in GHC now allows
foldl-based combinators to take part in list fusion.
http://www.joachim-breitner.de/publications/CallArity-TFP.pdf
Sandro
On 04/04/2015 4:40 AM, Keean Schupke wrote:
Here's a slightly modified version of the
arity-inference algorithm, with the distinction that we now have
a kind "fn" with possible values "call" and "arg", to make the
interpretation of arrow types a bit clearer: Everything else is
as before.
expr(P, var(X), cons(def(X, T), nil), T).
expr(P, nat(X1), nil, nat) :-
nat(X).
expr(P, bool(X), nil, bool) :-
bool(X).
expr(P, pair(X, Y), C3, prod(A, B)) :-
expr(pair, X, C1, A),
expr(pair, Y, C2, B),
append(C1, C2, C3).
expr(app, app(Fun, Arg), Cxt, B) :-
expr(app, Fun, C1, arrow(fn(M), A, B)),
expr(app, Arg, C2, A),
append(C1, C2, Cxt).
expr(P, app(Fun, Arg), Cxt, B) :-
dif(P, app),
expr(app, Fun, C1, arrow(fn(call), A, B)),
expr(app, Arg, C2, A),
append(C1, C2, Cxt).
expr(P, lam(V1, lam(V2, Body)), Cxt, arrow(fn(arg), A,
B)) :-
expr(lam, lam(V2, Body), C1, B),
split(V1, C1, Def, Cxt),
unifyall(Def, A).
expr(P, lam(Var, Body), Cxt, arrow(fn(call), A, B)) :-
dif(Body, lam(X, Y)),
expr(lam, Body, C1, B),
split(Var, C1, Def, Cxt),
unifyall(Def, A).
expr(P, let(Var, Body, Rhs), Cxt, T2) :-
expr(let, Body, C1, T1),
expr(let, Rhs, C2, T2),
split(Var, C2, Def, C3),
unifyeach(Def, pair(C1, T1), C4),
append(C3, C4, Cxt).
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
|
