On Sep 7, 2006, at 7:20 AM, skaller wrote:
> 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
Ah. I understand now.
> 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.
>
>> 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.
>
> 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.
Although having a type-checking system at runtime *may* require
runtime system support, you might implement it statically in the
final program but the simplification process and code generation
would become very complex. Take PROLOG as an example: it is a
relatively primitive system that essentially uses table lookups to
handle "types." Not what you want. More advanced code generation--
here ML is a good example but I might also refer you to output from
HAskell Regular Patterns (HARP, at http://www.cs.chalmers.se/
~d00nibro/harp/index.html) for a graphic example--involves
implementing pattern matches as lambda expressions. Some of the most
recent research I am aware of is "Boxy types: type inference for
higher-rank types and impredicativity," at http://
research.microsoft.com/Users/simonpj/papers/boxy/ . Mark P. Jones's
Publications page also has some good material on typing and type
classes, notably "Typing Haskell in Haskell," although the algorithms
are more for educational value than as good (i.e., fast, efficient)
implementations, see http://web.cecs.pdx.edu/~mpj/pubs.html . I give
you all this information for a simple reason: yes, Felix is a
language for implementing recent research; however, Felix runs into
two problems: (1) the simple combination of all the different
research is itself research of a sort and (2) holding the line to
category theory as opposed to type theory may not seem that different
at a high level (they should ultimately describe the same thing) but
the implementation of each is different so you will inevitably course
into uncharted waters. You might make that easier on yourself by
doing a little translation of the previous explorations. (I say
"yourself," but I might be able to get involved in this with the
caveat that I would probably do the implementation in Haskell, not
OCaml.)
I agree: the implementation of Type Classes is weak and currently
does not take the concept far enough but I think you should learn
Haskell and use type classes in a serious way before likening them to
object-oriented programming. At least read "From Hindley-Milner
Types to First-Class Structures," at http://web.cecs.pdx.edu/~mpj/
pubs/haskwork95.pdf , which got the whole type classes thing started
but remember that whatever the genesis of type classes may have been
(essentially polymorphism), their use is somewhat different today.
For a good example of how type classes have *not* been used for
object-oriented hierarchies, I refer you to the implementation of
wxHaskell which uses type hierarchies (not type classes) to model the
object-oriented model of wxWidgets in Haskell: the documentation is
here http://wxhaskell.sourceforge.net/doc/.
Felix's categorical type system is--as far as I know--something of a
novelty, so there is no escape from a kind of research in the
implementation. On a more fundamental level, look at the example of
the current implementation of typecases; while it is experimental it
is also unnecessary until you have a type system constraining you (as
it is now you may more or less freely cast between or out of types).
The opening Felix has--I suggested this before--is a system not based
on names (symbols) but numbers; the difference being that unlike
symbols numbers actually have an inherent relational value to one
another, whether you define them as "1,2,3..." or "a+bi." Of course
you would always be restricted to symbols for type identification--it
would be impossible to map out a number system for "types" when there
may be an infinite variety; my point is *relations* between types may
be numeric. A categorical system may borrow theorems from abstract
algebra or set theory to implement reductions in the simplifier or
reasoner.
-Pete
-------------------------------------------------------------------------
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
