I'm making good progress now, typeclassing the standard library.
Most of the tests now pass .. although some unchecked functions
may have been lost.
Here are some nasties.
1. to open typeclasses, you have to elaborate the instances:
************************************************************
open Eq[byte];
open Eq[address];
open Eq[caddress];
open Eq[vaddress];
open Eq[cvaddress];
open Signed_integer[tiny];
open Signed_integer[short];
open Signed_integer[int];
open Signed_integer[long];
open Signed_integer[vlong];
open Unsigned_integer[utiny];
open Unsigned_integer[ushort];
open Unsigned_integer[uint];
open Unsigned_integer[ulong];
open Unsigned_integer[uvlong];
open Real[float];
open Real[double];
open Real[ldouble];
open Addgrp[complex];
open Addgrp[dcomplex];
open Addgrp[lcomplex];
open Addgrp[imaginary];
open Addgrp[dimaginary];
open Addgrp[limaginary];
You cannot say
open Signed_integer[fast_sints];
where
typedef fast_sints = typesetof(tiny,short,int,long,vlong);
This is partly because the correct syntax would have to be
open[t] Signed_integer[t:fast_sints];
in line with other such cases of constrained polymorphism.
There is another difficulty here: because lookup depends on
open modules and typeclasses, actually any lookup required
opening modules and typeclasses cannot so easily be done
in the full environment .. because that includes the symbols
that the open directive itself would make available, leading
to a difficult circularity.
Felix resolves this with two restricted scopes: a bare bones
scope and a semi-bare scope. A bare scope is one without any
open modules, the semi-bare scope is a full scope up to the
current one, but the current one is bare.
All of this is quite nasty to implement, and currently this
feature just isn't available. I did look at it, but I can't
see an easy way to implement it. I may have to come back to
this, see below.
2. to provide an instance of a class, you have to provide
instances of all the inherited classes
**********************************************************
instance [t:basic_types] Eq[t] {
fun eq: t * t -> bool = "$1==$2";
}
instance[t:reals] Tord[t] {
fun lt: t * t -> bool = "$1<$2";
}
instance[t:numbers] Addgrp[t] {
fun zero: 1 -> t = "(?1)0" ;
fun add: t * t -> t = "$1+$2" ;
fun neg: t -> t = "-$1" ;
fun sub: t * t -> t = "$1-$2" ;
proc pluseq: lvalue[t] * t = "$1+=$2;";
proc minuseq: lvalue[t] * t = "$1-=$2;";
}
instance[t:numbers] MultSemi1[t] {
fun one: unit -> t = "(?1)1";
fun mul: t * t -> t = "$1*$2";
proc muleq: lvalue[t] * t = "$1*=$2;";
}
instance[t:numbers] Ring[t] {}
instance[t:numbers] Dring[t] {
fun div: t * t -> t = "$1/$2";
fun mod: t * t -> t = "$1/$2";
proc diveq: lvalue[t] * t = "$1%=$2;";
proc modeq: lvalue[t] * t = "$1%=$2;";
}
instance [t:fast_uints] Bits [t] {
fun bxor: t * t -> t = "$1^$2";
fun bor: t * t -> t = "$1|$2";
fun band: t * t -> t = "$1&$2";
fun bnot: t -> t = "~$1";
proc bxoreq: lvalue[t] * t = "$1^=$2;";
proc boreq: lvalue[t] * t = "$1|=$2;";
proc bandeq: lvalue[t] * t = "$1&=$2;";
}
instance[t:ints] Forward[t] {
fun succ: t -> t = "$1+1";
proc pre_incr: lvalue[t] = "++$1;";
proc post_incr: lvalue[t] = "$1++;";
}
instance[t:ints] Bidirectional[t] {
fun pred: t -> t = "$1-1";
proc pre_decr: lvalue[t] = "--$1;";
proc post_decr: lvalue[t] = "$1--;";
}
instance[t:ints] Integer[t] { }
instance[t:fast_sints] Signed_integer[t] {
fun sgn: t -> int = "$1<0??-1:$1>0??1:0";
fun abs: t -> t = "$1<0??-$1:$1";
}
instance[t:fast_uints] Unsigned_integer[t] {}
I am actually quite amazed that all this works.
I'm not even sure why, even though I wrote the code :)
Typeclasses inheritance works like C++ virtual bases:
it creates an undiscriminated union of all the signatures.
The instances only provide incremental implementations.
Thus, to specify the functions for an integer types,
you cannot just provide an instantiation of Integer
with all the required signatures: you have to discretely
instantiate each 'slice' as shown above.
3. Instances have to be in global scope to be found
****************************************************
You cannot put instances in a module,
and expect them to become visible when you open the
module. Instances have to be in the same scope as
the typeclass they're instantiation -- this is the same
as the rule in C++ that specialisations must be in the
same namespace as the template they're specialising.
However namespaces are extensible, whilst modules
are not, so this can be quite inconvenient.
in the example below in (4) you can see some of the
pain -- the type being instantiated is
Stl::vector::stl_vector_iterator[t]
and the name has to be written out in full.
You could use an abbreviation such as:
typedef vi[t] = Stl::vector::stl_vector_iterator[t];
but then that abbreviation would be public.
4. Typeclasses can only be parameterised by types
***************************************************
This is a severe restriction. To understand the problem
look at this:
//////////////////////////////////////////////////////////
instance[t] Eq[Stl::Vector::stl_vector_iterator[t]] {
fun eq: Stl::Vector::stl_vector_iterator[t] *
Stl::Vector::stl_vector_iterator[t] -> bool = "$1==$2";
}
instance[t] Tord[Stl::Vector::stl_vector_iterator[t]] {
fun lt: Stl::Vector::stl_vector_iterator[t] *
Stl::Vector::stl_vector_iterator[t] -> bool = "$1<$2";
}
instance[t] Iterator[Stl::Vector::stl_vector_iterator[t],t] {
fun deref : Stl::Vector::stl_vector_iterator[t] -> lvalue[t] = "*
$1";
}
instance[t] Forward[Stl::Vector::stl_vector_iterator[t]] {
proc succ: Stl::Vector::stl_vector_iterator[t] = "$1+1;";
proc pre_incr : lvalue[Stl::Vector::stl_vector_iterator[t]] =
"++$1;";
proc post_incr : lvalue[Stl::Vector::stl_vector_iterator[t]] =
"++$1;";
}
instance[t] Bidirectional[Stl::Vector::stl_vector_iterator[t]] {
proc pred: Stl::Vector::stl_vector_iterator[t] = "$1-11;";
proc pre_decr : lvalue[Stl::Vector::stl_vector_iterator[t]] =
"--$1;";
proc post_decr : lvalue[Stl::Vector::stl_vector_iterator[t]] =
"--$1;";
}
instance[t] Forward_iterator[Stl::Vector::stl_vector_iterator[t]] {}
instance[t]
Bidirectional_iterator[Stl::Vector::stl_vector_iterator[t]] {}
instance[t] Eq[Stl::Vector::stl_vector_reverse_iterator[t]] {
fun eq: Stl::Vector::stl_vector_reverse_iterator[t] *
Stl::Vector::stl_vector_reverse_iterator[t] -> bool = "$1==$2";
}
// REVERSE ITERATOR
instance[t] Tord[Stl::Vector::stl_vector_reverse_iterator[t]] {
fun lt: Stl::Vector::stl_vector_reverse_iterator[t] *
Stl::Vector::stl_vector_reverse_iterator[t] -> bool = "$1<$2";
}
instance[t] Iterator[Stl::Vector::stl_vector_reverse_iterator[t],t] {
fun deref : Stl::Vector::stl_vector_reverse_iterator[t] ->
lvalue[t] = "*$1";
}
instance[t] Forward[Stl::Vector::stl_vector_reverse_iterator[t]] {
proc succ: Stl::Vector::stl_vector_reverse_iterator[t] = "$1+1;";
proc pre_incr : lvalue[Stl::Vector::stl_vector_reverse_iterator[t]]
= "++$1;";
proc post_incr : lvalue[Stl::Vector::stl_vector_reverse_iterator[t]]
= "++$1;";
}
instance[t] Bidirectional[Stl::Vector::stl_vector_reverse_iterator[t]]
{
proc pred: Stl::Vector::stl_vector_reverse_iterator[t] = "$1-11;";
proc pre_decr : lvalue[Stl::Vector::stl_vector_reverse_iterator[t]]
= "--$1;";
proc post_decr : lvalue[Stl::Vector::stl_vector_reverse_iterator[t]]
= "--$1;";
}
instance[t]
Forward_iterator[Stl::Vector::stl_vector_reverse_iterator[t]] {}
instance[t]
Bidirectional_iterator[Stl::Vector::stl_vector_reverse_iterator[t]] {}
/////////////////////////////////////
All of this code is required to instantiate the properties of
a the two bidirectional iterators over an STL vector, the
forward and reverse ones.
As explained in point 1, it is necessary to write out the
instances of each base typeclass to instantiate a typeclass.
Note that although instance[t] is universally quantified
over the data type t, so that the instances are data polymorphic,
that isn't all we wanted! What we REALLY want is for the instances
to be polyadic:
instance[IT:TYPE->TYPE, t:TYPE ]
Eq[IT[t] where IT:bidirectional_iterators]
{
fun eq: IT[t] * IT[t] -> bool = "$1==$2";
}
Here, the kind of IT is
IT: TYPE -> TYPE
that is, IT is a type *constructor* or functor, and one of
those which is also a bidirectional iterator.
Haskell can do this. Felix can't at the moment: typeclass
parameters have to be kind
TYPE
Lacking such functorial polymorphism .. parameterisation
of the data functors, not just types, we are forced to
elaborate each container separately.
Functorial polymorphism is the Holy Grail for programming languages.
I am not sure how easy it will be to implement this.
Felix does have parameterised types:
typedef vector[t] = "std::vector<?1>";
and
typedef fun vect(t:TYPE):TYPE => vector[t];
may be regarded as specifying 'vector' and/or 'vect' as being
data functor and/or type constructors. Nevertheless neither
can be manipulated as such:
vect t
is simply substituted away, and vector[t] becomes a single
monomorphic type with an unknown argument: 'vector' cannot
be manipulated as an object in its own right.
Note this is the downfall of ML as well. Although it has
functors, they're not first class, they're just typesafe
macros which can be used to construct types given type
arguments.
--
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
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
