On Wed, 2006-09-06 at 22:47 -0400, Peter Tanski wrote:
> On Sep 6, 2006, at 9:01 PM, skaller wrote:
> Take the renowned GMP, for example: poke around
> a bit and eventually you will follow a function to a header file with
> one line of text "not implemented yet.") The bigger the system, the
> bigger the mess.
Yup. Parts are quite solid, and parts are experimental and
half complete. Often I implement something and have cases
like '
let algo ..
match .....
| NewFeature _ -> failwith "[algo] can't handle NewFeature yet"
I'm sure this is true in all compilers, including Ocaml and
GHC. One implements a general idea, with constraints.
There are two ways to fix this:
(a) refactor the code
(b) some user gripes something doesn't work as expected
EG Erick wanted:
int(3.4)
to work like it does in C++. In Felix we have in the library
int_of (3.4)
already. So I added this: when the system finds the syntax
typename expr
it translates the prior lookup failure into:
_ctor_<typename> expr // eg _ctor_int
This 'trick' is used already so that you can do:
struct X { x:int; y:int; };
val a:X = X(1,2);
only here the system generates the constructor: X can be used as a
a type OR as a function. The same trick is used so this works:
"Hello " 62 " person " person
No "+" is required to concatenate, the 62 converts to 'A'.
Normally
<string> expr
is an error. But before announcing the error, we check if
apply of (string * typeof expr)
exists, and use that function if it does. So things which
normally aren't applicative can be mapped to functions.
** We could do this for lists:
Empty[int] 1 2 3 4
could work using apply. In this kind of case, the syntactic
sugar introduced is introduced by the user, not the compiler.
The compiler just implements the deviant lookup.
In any case, Erick recently found the typename-to-constructor
lookup failed when the typename was found in an 'open'ed module.
And I immediately found, it also failed with a qualified name.
So I fixed both cases, making the system more complete.
The moral is that this was never a bug: the original implementation
was just restricted, but it was contrary to expectations, so I
extended the scope of the feature.
To my surprise it worked with polymorphic constructors. Previously
there was no test case for that.
Even reading the tutorial and regression tests .. you'd miss
some features. Even I can't remember everything I've implemented:
this is not a new project, I've been working more or less full
time on it for over 6 years.
There are no ocaml-like functors and no Haskell-like typeclasses.
I tried to implement both but failed. Typeclasses quite recently.
Why? Because *I* actually need them right now. In the library
code you'll find some 'macros' used to implement categories
for integers, and you'll also find some interscript code
for generating the modules Short, Int, Long etc.
I need typeclasses for this. Short, Int, Long are all the
same. I need:
typeclass Arith[t] =
{
fun add: t * t -> t = "$1+$2";
fun mul: t * t -> t = "$1*$2";
..
}
This is done with macros at the moment. The macros DO NOT WORK
in general because they don't support polymorphic types.
Furthmore, I need functors between these classes: signed
integers allow + - etc. Unsigned integers also allow
bitwise operations (signed integers do not).
In fact, the Haskell typeclasses are quite weak. I'm surprised
how bad they are. What we need in typeclasses is a set
of signatures and a SYSTEM OF GENERATION that can generate
the instances given some of them.
In other words, the signatures are theorems which can
be proved in terms of themselves, so given enough of
them as 'axioms' the others are defined automatically.
Haskell does provide 'default' but that is as weak as
the 'pure virtual' functions of C++ objects. The problem
is this doesn't support alternate choice of basis
(axiom set).
AFAIK there is actually a way to do this. A typeclass
is really a category. The 'laws' relating the methods
can therefore be stated equationally with the composition
operator, and the equations can be 'solved' using the
Knuth-Bendix procedure.
Of course we know in advance typeclasses are screwed
precisely because object orientation is screwed by
the covariance problem, and type classes really are
just classes lifted one 'kind' up.
So there's an open issue whether to bother with typeclasses
since they're wrong in the first place. In my latest attempt,
I generalised the notion to full modules, and reused the
module syntax:
module X[t,u] {
....
}
because modules already support inheritance, for example.
To use such a module you'd say, for example:
open X[int,float];
assuming the module was closed, and something like Ocaml functors
would be needed if it was open:
open X[int, float with
fun add[int,float]="$1+$2"
]
to fill in the 'virtual' methods -- and if it is too hard to get
around the structural typing requirement we'd probably have to use
an instantiation statement eg:
module XIF = X [int, float] with ...
like Ocaml functor instantiation or Haskell instance definition.
The *problem* was I couldn't get
open X[int, float]
to work, due to the internal representation of modules: the problem
being the quantifiers (type variables) in the module are bound
into the method signatures, and my attempts to get a 'view' object
working that instantiated them transparently collapsed.
The problem, technically, is that the stored functions are
generative. There is a symbol table entry for them. Lookup
often seeks the symbol table entry .. but with views every
entry would have to be specialised transparently on the fly.
Unfortunately .. that includes the reference to the method.
For example lookup f returns a list of integers, each
refering to some function named f. With an instantiation,
the list has to include substitutions for the type variables.
So to make it work I need a new term, and I have to replace
every use with it .. and that's a LOT of code to edit
for an experimental feature without even knowing if what
I'm doing is going to work .. i.e. without a theoretician
saying "YES, that is sound, do it".
> Well I can't argue about Haskell-speed but going head-on with OCaml
> is a high aspiration.
Felix trashes every other language translator INCLUDING C,
implementing Ackermann's function. Even I do not quite understand
how it can trash C, given it generates C .. but it does.
And I know of at least two more optimisations one of which
improves the polynomial performance (all the languages seem
to differ only in a linear factor .. due entirely to the
number of registers that get pushed on the stack each
recursion).
Taking on Ocaml shouldn't be that hard: Ocaml uses boxed types.
Felix doesn't. And, Felix is a whole program analyser, Ocaml isn't.
Frankly the ONLY languages out there with any hope of outperforming
Felix are
(a) MLton --> doesn't have 64 bit implementation yet
(b) Bigloo scheme --> whole program scheme compiler
If it doesn't do whole program analysis it has no chance.
In a closed form .. when it gets better .. Haskell SHOULD
kill everything. In theory purely functional should give
better optimisation opportunties. But at least at present,
GHC isn't very good .. it doesn't even rate on the
Ackermann test.
Of course at the moment .. the Felix garbage collector is slow
and has high overheads .. so on heap intensive work, Ocaml
will trash Felix. So will GHC.
> Just watch out for names like "union" that may create undue
> expectations. You know better than I do what to watch out for: C++
> had to worry about that when working from C.
Union is called union because it is a union. It's just that
it has built in discriminant and typesafe decoding of
the discriminant -- what every C programmer always wanted
in a union :)
You have to check the variant tag at run time: this is
crudely 'run time type checking'. The fact the Felix implementation
is fast is a nice bonus.
Remember Felix is an upgrade to C/C++ .. so we want to
preserve names of things so the syntax is familiar --
even if the semantics are different.
Surprisingly programmers are far more able to adapt to
semantic changes than syntactic ones. This is probably
because comprehension and reasoning are based on
prior subconscious visual pattern matching.
Change the symbols, the programmer can't reason at all,
they have to put all their effort into learning
Left Hand Drive when they're an Australian or Brit.
[I almost got killed in USA just crossing the road because
I didn't think .. I scanned the wrong direction for traffic,
thank you San Francisco drivers!]
You are right: union could be a bad choice, but the
purpose and meaning is the same as in C: unification
of heterogenous types into a single type.
> > You could .. there's also a reglex facility and a ready made
> > lexer in the library.
>
> Yes. It is very good.
Except it lacks substring extraction .. :)
> > There's ALSO a GLR parser but it's been
> > adandoned.
>
> ... and I just spent a little while reading through that stuff...
Hey, you misunderstand. The GLR parser is NOT abandoned.
It is 'flxdoc' which is abandoned: that is a tool which
typesets felix code, and thus need to parse Felix.
The tool is abandoned because I change the Ocamlyacc grammar
often and the tool uses a grammar *generated* from it.
But the user actions have to be hand written.. so every
time I change Ocamlyacc grammar I have to change the
flxdoc grammar too and it gets in the way of experimenting
with Felix.
> I was under the impression from a prior email that you had
> implemented the constructor-match.
I don't understand. Matching constructors is no problem.
The problem is that the type system -- the domain of discourse
for the implementation -- doesn't HAVE any constructors,
other than 0-ary ones like 'int', 'long' etc.
More precisely, there ARE some constructors:
+ * fix
do exist: sum, product, recursion are the only constructors
accepting arguments. The problem here is that these
constructors are NOT represented by 'named constructors',
and, + and * are not binary, they're n-ary.
That is, + and * are sum and product constructors represented
by Ocaml constructors .. not type system level constructors,
so they have no 'names' to substitute.
If you could write:
typeunion X[t,u] = Tuple of (t,u) | Sum (t,u)
then Tuple and Sum would be constructors. But you can't
write this. If you could it would be of kind isomorphic to
TYPE * TYPE + TYPE * TYPE
Note here * and + are KIND (category) operators NOT type
combinators.
> It might not be that hard for the general language--although you
> might run into trouble for the runtime system. The main thing to
> remember is that the language *must* carry types as real
> instantiations or it is not type-safe because once you get into more
> complex programs (i.e., databases, bootstrapping, named message
> senders and receivers, anything dynamic) you must be able to work
> with types at run-time.
Yes, but we cannot do that in Felix at the moment.
The RTTI is limited to use by the garbage collector.
> www.polyml.org/) and outrageously interactive systems like Epigram
Yeah, I've looked at Epigram. I like the description 'outageously'
for it :)
> These are just sources of ideas; using a type system based *not* on
> name-tables but on category theory Felix may take a fully numeric
> approach--but you might need a reasoner system to really handle it
> well; graph reduction for simplification may not be powerful enough.
We don't need to implement a fully powerful system: that is a
job for researchers. The real idea is to gather and integrate
research results to make a practical language. Most programmers
don't use higher level stuff that often. But that's no reason
to be stuck with crud decades out of date.
If Felix goes to far in the 'advanced language' thing it
would be forced to abandon C++ compatibility.
My contention is you can preserve C++ compat, whilst still
providing surprising powerful and general features from
a diverse range of research sources.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
