Hope the attachment is readable ..
FELIX2, design changes
----------------------
1. Elimination of lvalues.
--------------------------
In the old Felix we had this problem: to implement, say,
++x;
in C, we would do some crud like:
fun incr: &int -> int = "++*(int*)(void*)$1.offset";
because a pointer was a
struct ref_t { void *base; ptrdiff_t offset; };
The problem is that the call has to be written:
++(&x);
OR the compiler translates for us, but either weay we have a C++
constructor for a ref_t like
ref_t (0,&x)
which is promptly deconstructed by the user
C++ code. There's no way to optimise this, because the user code is
invisible to the compiler. To fix this, lvalues were introduced:
fun incr: lvalue[int] -> int = "$1++";
which allows us to write
++x;
however the problem is that *Felix* functions cannot accept lvalues, only C++
primitives allow them.
Today, Felix has a new garbage collector which uses Judy arrays, which are
digital
trees (tries) which allow a raw C pointer to be used for pointers. So now, Felix
and C pointers are the same thing, and there is no "construct a ref then
deconstruct it"
rubbish needed to implement the original lvalue free model --
"everything is pass by value"
Basically this means you must write:
fun incr: &int -> int = "*$1++";
and call like:
(&x)++
which works the same way for primitives and Felix functions now: both get passed
a pointer. The C code leads to
(*&x)++
which is theoretically non-optimal, however any good C++ compiler will optimise
this to just
x++
Similarly instead of
x = y;
you'd have to write
&x <- y;
which is short for
assign(&x, y)
and reduces to
*&x = y;
and thence via the C++ compiler optimisations to
x = y;
We can then *reintroduce* the transformation:
x = y; ---> &x <- y; ---> assign(&x, y)
as a syntax extension, emulating lvalues.
Now we must note that to check
&x
is correct we STILL need a notion of lvalues. However operator & is not
a function, but an intrinsic operator, and thus there is no impact on the
type system. To repeat:
"Lvalues can be removed from the type system"
This is the key point, because lvalue types are NOT proper combinators.
in other words, "lvalue[t]" need not be a type, for example
lvalue[lvalue[int]]
is not a valid type. "lvalue" only works on a value type.
The combinatorial nature of type operators is an essential property,
it is not just a matter of complexity, it just isn't *possible* to have
polymorphism in the presence of non-combinatorial operators.. this is also
why "void" is usually left out of type systems, since
fst (int, void) --> int
is wrong. The point is type variables are abstract types, and thus prevent
any analysis.. the formula above can only be made to work by
fst (v1 , v2) -> if v2 = void then void else v1
which makes most reductions impossible.
2. Void
------
In Felix, "void" isn't really
a type but it IS allowed to be used as one, so some faulty types can
be calculated .. however they will usually lead to errors at code
generation time. The notation
t -> void
for a procedure is carried through into function combinators,
but then analysis routines must check for a void to detect a
procedure. This is wrong and should be fixed: if we disallow
void as a type we can STILL use function combinators with a void
return value for procedure types, and then check, the point is to
disallow void elsewhere.
Note that I disagree with theoreticians that void isn't a valid type.
In a categorical type system, unit and void are quite legitimate.
The problem is similar to lvalues in that many polymorphic formulas,
that is, one with abstract types in them, will not work simply: as noted
above there is a correct formula for "fst" but you cannot use unification
to perform reductions because the result is a conditional.
So in a *structural* type system, void can't be allowed as a type.
it CAN be used as an argumentless combinator tho! In other words,
when we see a type variable (abstract type) we have to agree it can
never be replaced by void.
Note that even unit has problems:
fst (unit, int) --> ??
It isn't well defined in the categorical type system due to the
isomorphism
1 * int === int
Felix currently uses some special code in some places to eliminate
units .. typically the back end code generators, where it is banned
outright because it creates inefficient code -- since unit has only
one value, the value is known and never needs to be passed. Since
Felix has an extensional type system, this is possible. With an
intensional system (as in Ocaml) unit has to be passed to polymorphc
routines.
--
john skaller
[EMAIL PROTECTED]
-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
