lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Tony Finch wrote:
> See also the Self papers. They were able to inline 95% of dynamic message sends (and Self programs are nothing but message sends) using static type inference. (Self also uses a lot of dynamic optimizations.)

A little while back I did a bunch of research into global type
inference, including the above paper (which is a good one, and worth
reading), and eventually came up with about 75-80% of a statically typed
duck typed language with polymorphism which used LLVM to compile into
real machine code. It would analyse the entire program to extract
interfaces based on what methods were called on what, and then produce
efficient code --- every method call was a single indirect subroutine
call instruction. It was producing really nice machine code at the end,
not far from C grade.

It eventually all fell apart, of course. Global type inference is Really
Hard, and nearly all research is based on functional languages, and most
of the algorithms I found don't map well onto procedural ones
(especially procedural ones which support null and polymorphism). The
biggest showstoppers involved polymorphism: trying to decide when to
instantiate a new instance of a method vs. trying to reuse an existing
instance, and how to handle polymorphic recursive method calls. My
half-baked inference engine was basically unable to handle these sensibly.

In fact, this approach wasn't as user friendly as one might think.
Because everything was statically typed, then this:

var i = "one";
i = 1; perfectly legal, because i's type may now be any interface which
contains the common subset of methods in strings and integers. Which is
to say, none. It wasn't until you actually tried to call a method on it
that your program broke.

And consider the consequences of statically typed polymorphism in this

var list = cons(1, cons(2, cons(3, cons(4, cons("foo", null)))));

For extra marks, you may also want to think about what happens when we
do this:

list = list.second();

In fact, what really killed this project was that the code got
excessively tangled and messy and eventually became too big and complex
for me to keep all the logic in my head. The compiler was implemented in
C++, which was not a good choice --- refactoring became horrifically
expensive after a while. I'm actually attempting to revisit the idea,
but with tweaks (explicitly named interfaces, but keeping the type

┌─── ───── ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup

Attachment: signature.asc
Description: OpenPGP digital signature