| 10-07-2007, 06:36 AM | #1 |
Haskell has a pretty good type system. We can't be as cool as a modern FP language because we don't have garbage collection, but I think we can still do some nice things. Namely we can get good abstractions with out the OO notion of a class, and I think we can do it with out abandoning our (i.e. Vex's) work so far. There are two features in particular that I think we can rip out of haskell to our benefit. One is parametric polymorphism, which has in the been adopted by mainstream languages in the form of generics. We can use these to write generic code at very little cost. The second is type classes, which give us functionality similar to traditional OO virtual classes, but are lighter weight. They avoid the virtual indirect call. Using them effectively comes at the cost of throwing out our old methods. Parametric Polymorphism  JASS:struct list<a> a x list<a> xs static method create takes a x, list<a> xs returns list<a> local list<a> p = list<a>.allocate(x,xs) set p.x = x set p.xs = xs return p endmethod endstruct And we'd use it for something like JASS:local list<Int> int_list = list<Int>.create(37,0) Now we can define generic functions such as length: JASS:function length<a> takes list<a> lst returns integer if lst == 0 then return 0 else return 1 + length<a>(lst.xs) endif endfunction This could also be a method of list JASS:method length takes nothing returns integer // no <a> because the struct parameterizes it if this == 0 then return 0 else return 1 + .xs.length() endif endstruct More interesting is to have some higher order functions like foldr. JASS:function interface istos takes integer, string returns string function prepend takes integer x, string s returns string return I2S(s)+s endfunction function foldr<a,b> takes istos f, a accum, list<b> lst returns a if lst == 0 then return accum else return foldr<a,b>(f,f.evaluate(lst.x,accum),lst.xs) endif endfunction function bignum_to_s takes list<integer> n returns string return foldr<string,integer>(istos.prepend,"",n) endfunction Compilation for these functions is straight forward, because you can't touch the parameterized type. Just replace the types, e.g. JASS:function foldr_string_integer takes integer f, string accum, integer lst returns string if lst == 0 then return accum else return foldlr_string_integer(f,evaluate_string_integer(f,x[lst],accum),xs[lst]) endif endfunction Type Classes Interfaces for structs are kind of weak, and we all know how lame inheritance is. There's another way to express that we want functions that operate on families of types. JASS://Interface is a fine name for it too class Eq a function cmp takes a x, a y returns boolean endclass JASS:function notequal<Eq a> takes a x, a y returns boolean return not cmp<a>(x,y) endfunction Let's make this work for integers. JASS:instance Eq integer function cmp takes integer x, integer y returns boolean return x == y endfunction endinstance And let's compile JASS:local boolean b = notequal<integer>(0,1) JASS:function cmp_integer takes integer x, integer y returns boolean return x == y endfunction function notequal_integer takes integer x, integer y returns boolean return cmp_integer(x,y) endfunction // ... local boolean b = notequal_integer(0,1) Example, boxed sorted lists JASS:class Ord a function cmp takes a x, a y returns boolean endclass struct list<a> a x list<a> xs static method create takes a x, list<a> xs returns list<a> local list<a> p = list<a>.allocate(x,xs) set p.x = x set p.xs = xs return p endmethod endstruct struct SortedList<Ord a> list<a> x static method create takes nothing returns SortedList<a> local SortedList<a> sl = SortedList<a>.allocate() set sl.x = 0 return sl endmethod method insert takes a newv returns nothing local list<a> cur = .x if cur == 0 then set .x = list<a>.create(newv,0) return endif loop exitwhen cur.xs == 0 or cmp<a>(newv,cur.x) set cur = cur.xs endloop set cur.xs = list<a>.create(newv,cur.xs) endmethod endstruct instance Ord vector function cmp vector x, vector y returns boolean // strange for cmp to find its way outside of the vector class return x.length() > y.length() endfunction endinstance function foo takes nothing returns nothing local SortedList<vector> lst = SortedList<vector>.create() call lst.insert(vector.create(300.0,200.0)) call lst.insert(vector.create(5.0,7.0)) call lst.insert(vector.create(1000.0,0.0)) endfunction And we can make sorted collections themselves a class. Here we have to accept the strangeness of having methods outside of the struct definition by abandoning methods and just using functions. JASS:class SortedColl (Ord a) function insert takes SortedColl<a>, a x returns nothing endclass struct SortedList<Ord a> list<a> x endstruct instance SortedColl SortedList<Ord a> function insert takes SortedList<a>, a x returns nothing ... endfunction endinstance function AddTwoToColl<SortedColl a<Ord b>> takes SortedColl<a<Ord b>> sc, b x, b y returns nothing call insert<SortedColl a<b>>(x) call insert<SortedColl a<b>>(y) endfunction function foo takes nothing returns nothing local SortedList<integer> sl = SortedList<integer>.create() call AddTwoToColl<SortedList<integer>>(sl,3,5) endfunction With out type inference it might just be useless though, typing out insert<SortedColl a<b>>(x,y) is pretty lame. The goal is to have polymorphic functions, so that you just write insert. Summary
There is an object oriented extension to haskell which might contain the solution to the method problem for type classes. I haven't looked at it. |
| 10-07-2007, 09:50 AM | #2 |
| 10-07-2007, 03:30 PM | #3 |
err dunno why nobody looked at this: http://www.wc3campaigns.net/pastebin...9bf38be3066a0f  quote:this doesn't make sense, or am I missing something? Wouldn't the whole istos function interface also need type parameters? I would also say you don't want to I2S s. Edit: I was planning not to use <> at all and to require some type usage to call stuff, but I guess using <> got some merit for some extra nesting, but then we end up having more confusing syntax, you are right this is the only way to have higher order functions like map, I don't know foldr but I do know map... JASS:function interface err<type t> takes t returns t function map<type t> takes list<t> L, err<t> F returns list<t> return list<t>.create( F.evaluate(L.x) , map<t>(L.sx, F) ) endfunction Posting this mostly to make sure I am understanding you... |
| 10-07-2007, 04:33 PM | #4 |
Yes, I screwed up that example. That may significantly complicate things too. Let's try compiling another example. JASS:class Show a function show takes a x returns string endclass instance Show integer function show takes integer x returns string return I2S(x) endfunction endinstance instance Show unit ... endinstance instance Show list<a> function show takes list<a> lst returns string return show<a>(lst.x)+" : "+show<list<a>>(lst.xs) endfunction endinstance function foo takes nothing returns nothing local list<integer> lst = ... local list<list<unit>> lst2 = ... call show<list<integer>>(lst) call show<list<list<unit>>>(lst2) // not having to specify the type of show here is where it becomes really nice endfunction I'd implement your example like this JASS:function interface k1<a,b> takes a returns b // ignore termination case for now function map<a,b> takes k1<a,b> f, list<a> lst returns list<b> return list<b>.create( f.evaluate(lst.x), map<a,b>(lst.xs, f) ) endfunction Example JASS:function bar takes nothing returns nothing local list<integer> lst = ... local list<string> lst2 set lst2 = map(k1<integer,string>.show<integer>,lst) endfunction JASS:function interface k1_integer_string takes integer returns string function map_integer_string takes k1_integer_string f, list_integer lst returns list_string return list_string.create(f.evaluate(lst.x),lst.xs) endfunction function show_integer takes integer x returns string return I2S(x) endfunction function bar takes nothing returns nothing local list_integer lst = ... local list_string lst2 set lst2 = map_integer_string(k1_integer_string.show_integer,lst) endfunction Hm works out fine. In fact it's practically just a macro. |
| 10-07-2007, 07:57 PM | #5 |
should not be taken seriously: JASS:function show<integer> takes integer x returns string return I2S(x) endfunction function show<unit> takes unit x returns string return GetUnitName(x)+I2S(H2I(x)) endfunction function DebugMessage<showable f> takes string vname, f v returns nothing call BJDebugMsg( vname+" : "+show<f>(v) ) endfunction function aaa takes unit u, integer k, real f returns nothing call DebugMessage<unit>("u", u) call DebugMessage<integer>("k", k) call DebugMessage<real>("f", f) endfunction In a perfect world, this should be enough, and the instantiation of DebugMessage<real> should be enough to popup an error message about not having show<real> declared, of course it isn't usually the case... JASS://not sure, perhaps it would also work if it was like the other one class showable function show<showable> takes showable x returns string endclass //perhaps we could use typeclass so people don't confuse it with the more evil OOP class concept... function show<integer> takes integer x returns string return I2S(x) endfunction function show<unit> takes unit x returns string return GetUnitName(x)+I2S(H2I(x)) endfunction function DebugMessage<org f> takes string vname, f v returns nothing call BJDebugMsg( vname+" : "+show<f>(v) ) endfunction function aaa takes unit u, integer k, real f returns nothing call DebugMessage<unit>("u", u) call DebugMessage<integer>("k", k) call DebugMessage<real>("f", f) endfunction This would just make the parsing easier. At the time you use DebugMessage<> anything should tell the compiler to make sure the type is implementing the required functions to be considered a type that belongs to the showable type (in this case only requires Show<> and the error would be, "show<real> is not declared and therefore real does not belong to the showable class" And also at the time of parsing DebugMessage we can popup errors when we find usage of stuff not specific to the declared showable class... |
| 10-07-2007, 08:33 PM | #6 |
I like dropping instance, but I don't like the 'doesn't need to belong to any class' keyword. Fixing up the collection example JASS:// a simple list type struct list<a> a x list<a> xs endstruct function cons<a> takes a x, list<a> xs returns list<a> local list<a> lst = list<a>.create() set lst.x = x set lst.xs = xs return lst endfunction // equality on some element for a set of unique elements class Eq a function cmp a x, a y returns boolean endclass // instanciation of the class for integers function cmp<integer> takes integer x, integer y returns boolean return x == y endfunction // a set class for unique elements class Set s<Eq a> function intersect takes s<a>, s<a> returns s<a> function has takes s<a>, a returns boolean endclass // instance of set for lists function has<list<Eq a>> takes list<a> lst, a ele returns boolean if lst == 0 then return false elseif cmp<a>(lst.x,ele) then return true else return has<list<a>>(lst.xs,ele) endif endfunction function intersect<list<Eq a>> takes list<a> u, list<a> v returns list<a> if u == 0 then return v endif if has<list<a>>(v,u.x) then return cons<a>(u.x,intersect<list<a>>(u.xs,v)) else return intersect<list<a>>(u.xs,v) endif endfunction // Use function dostufftosets<Set a> takes a u, a v returns a return intersect<a>(u,v) endfunction function foo takes nothing returns nothing local list<integer> lst = ... local list<integer> lst2 = ... local list<integer> lstinter = dostufftosets<list<integer>>(lst,lst2) endfunction JASS:// first check that intersect<list<integer>> is valid // check that intersect defined for lists // it's defined for list<Eq a> // check that integer is in Eq // first pass. Erase innermost type variables // a simple list type struct list_integer integer x list_integer xs endstruct function cons_integer takes integer x, list_integer xs returns list_integer local list_integer lst = list_integer.create() set lst.x = x set lst.xs = xs return lst endfunction // instanciation of the class for integers function cmp_integer takes integer x, integer y returns boolean return x == y endfunction // a set class for unique elements class Set list_integer // here we matched the entire s<a> with list_integer, while matching a with integer function intersect takes list_integer, list_integer returns list_integer function has takes list_integer, integer returns boolean endclass // instance of set for lists function has<list_integer> takes list_integer lst, integer ele returns boolean if lst == 0 then return false elseif cmp_integer(lst.x,ele) then return true else return has<list_integer>(lst.xs,ele) endif endfunction function intersect<list_integer> takes list_integer u, list_integer v returns list_integer if u == 0 then return v endif if has<list_integer>(v,u.x) then return cons_integer(u.x,intersect<list_integer>(u.xs,v)) else return intersect<list_integer>(u.xs,v) endif endfunction function dostufftosets<list_integer> takes list_integer u, list_integer v returns a return intersect<list_integer>(u,v) endfunction function foo takes nothing returns nothing local list_integer lst = ... local list_integer lst2 = ... local list_integer lstinter = dostufftosets<list_integer>(lst,lst2) endfunction |
| 10-14-2007, 02:20 AM | #7 |
Proof of concept (i.e. toy) generics compiler In: JASS:struct list<a> a x list<a> xs endstruct function cons<a> takes a x, list<a> xs returns list<a> local list<a> p = list<a>.create() set p.x = x set p.xs = xs return p endfunction struct bar real x integer n endstruct function foo takes nothing returns nothing local list<integer> lst = cons<integer>(37,cons<integer>(2,0)) local list<bar> lst2 = cons<bar>(bar.create(),0) set lst = foo() endfunction Out: JASS:struct list_integer integer x list_integer xs endstruct struct list_bar bar x list_bar xs endstruct function cons_integer takes integer x, list_integer xs returns list_integer local list_integer p = list_integer.create() set p.x = x set p.xs = xs return p endfunction function cons_bar takes bar x, list_bar xs returns list_bar local list_bar p = list_bar.create() set p.x = x set p.xs = xs return p endfunction struct bar real x integer n endstruct function foo takes nothing returns nothing local list_integer lst = cons_integer(37,cons_integer(2,0)) local list_bar lst2 = cons_bar(bar.create(),0) set lst = foo() endfunction Or handle vars: JASS:function GetHandle<a> takes handle subject, string name returns a return GetStoredInteger(LocalVars(),I2S(H2I(subject)),name) return null endfunction function foo takes nothing returns nothing local location loc = GetHandle<location>(nu,"foo") endfunction JASS:function GetHandle_location takes handle subject, string name returns location return GetStoredInteger(LocalVars(),I2S(H2I(subject)),name) return null endfunction function foo takes nothing returns nothing local location loc = GetHandle_location(nu,"foo") endfunction |