Closed bergmark closed 11 years ago
Unless I'm missing something, we would never encounter an expression like minBound r
because minBound
is not a function.
We already discussed this on IRC. I think you can solve it this way for single-variable classes and methods of a particular form. Otherwise you need to know the instance dictionaries either at compile-time or attach some type meta-data to all expressions. Consider read "abc"
, how do you handle that? Or def
?
For show r
and x*y
we have some chance, though. Those could be, as a general solution, r.show(r)
and x.mult(x,y)
, or some-such (probably more like var mymethod=function(a,b,c){a.mymethod(a,b,c)}
where a
contains is whatever is type-class polymorphic in the method declaration). I thought about implementing a subset of type-classes like that, it seemed feasible. We could merely disable class or instance declarations outside of the scope of what we are able to support like this. For this approach I think you're on the right track, but that there are some strict limitations of what's possible.
Otherwise I think we're confined to waiting for haskell-type-exts to get polished off (seems like that will take some time), or to polish it ourselves.
FWIW, constructors are scoped:
> function X(){}; var x1 = new X(); var x2 = (function(){ function X(){}; return new X(); });
> [x1.constructor == x2.constructor,x2 instanceof X]
→ [false, false]
Wouldn't typeclasses come for free if you compiled from System FC rather than the Haskell source directly? Being pretty naive about the internals of Fay's compiler, I'm not sure how feasible this is/how much of a rewrite this would entail.
Anyway, the implementation of a typeclass is detailed in a talk somewhere by SPJ. It went something like this:
Each instance's definition is stored somewhere, for example
instance Show Int, we save the function
showInt :: Int -> Stringin a table that maps type identifiers to their respective show implementations. The real show function actually has type
show :: Type -> a -> String.
Or at least that's how they translate it into a System FC function. Probably not necessary if you're thinking about more quickly mapping it to js source.
John, the paper is “How to make ad-hoc polymorphism less ad hoc” and the approach is:
class Eq a where eq :: a -> a -> Bool
foo :: Eq a => a -> a -> Int
foo x y = if eq x y then 0 else 1
instance Eq Int where eq = …
becomes
data EqD a = EqDict { eq :: a -> a -> Bool }
foo :: EqD a -> a -> Int
foo eqDa x y = if eq eqDa x y then 0 else 1
eqDInt = EqD { eq = … }
And then
foo 1 2
becomes
foo eqDInt 1 2
But that assumes you have a type system and so you know that you should put eqDInt
there and not something else.
We could compile from Core which would avoid the type-class problem altogether, but then we are too low-level. We want to, I think, sit somewhere in the middle.
Maybe core is worth re-looking at again. The kind of code it generates is kind of awful to read, and makes lots of GHC-specific assumptions about the representation of values and data structures. But still worth looking at again, perhaps.
Also the GHC API we should re-look at. Despite being rather undocumented, it may hold the secrets to giving us type-analysis at the concrete syntax level, or at least a mapping to it. I had a horrible time getting it to do anything or figuring out its API, but if I'm feeling optimistic one day I might try again.
Rethinking the design of GHCJS, I think a working plan for Javascript generation, using GHC API can be:
Process type-checked Haskell AST: replace some bits of code with Javascript (Fay) specific equavalents to prevent GHC interpret them his way.
You can replace string literals with something like:
StringLiteral "Test" -> Fay.Core.haskellStringFromNativeJavascriptString ("Test"#)
And replace numeric literals into something like:
NumericLiteral 123 -> Fac.Core.numericFromNativeJavascriptDouble 123.0#
Feed modified type-checked Haskell AST back into GHC and get back GHC Core or GHC STG AST.
The idea of step 2 is to totally prevent GHC from wireing in GHC specific bits, like functions from GHC.* modules. So you can have totally independent Javascript runtime and use GHC only as type checker and optimizer.
Interesting idea!
I started implementing a trivial codegen to see how the Core output looks. The AST is of course simple but indeed I was concerned about all these GHC.* functions that I will have to support but don't know them ahead of time.
So your approach is to replace all literals in the AST before GHC throws in its own internal stuff and get back a nice clean AST. I like it! Using GHC as only a type-checker/optimizer is exactly what I want.
Thanks for your input, your experience with Core/STG generation gives me confidence to try.
I've been lurking around and thinking about this typeclass issue, since I feel it is one of the major impediments to using Fay on an industrial scale. Without typeclasses Haskell becomes a lot more tedious to write. That said...
I feel like Core is a good place to start because we may even be able to run some of the GHC optimization passes on the Core. This is something we can look at later, but GHC already has some strong optimization passes we could run and I expect some of them will really help the code. It also sounds like Core will map much more closely to JavaScript.
What do you mean about the "GHC.* functions that I will have to support but don't know them ahead of time"? Couldn't most of those be ported to JS?
Drew Haven drew.haven@gmail.com
On Sat, Sep 22, 2012 at 4:06 AM, Chris Done notifications@github.comwrote:
Interesting idea!
I started implementing a trivial codegen to see how the Core output looks. The AST is of course simple but indeed I was concerned about all these GHC.* functions that I will have to support but don't know them ahead of time.
So your approach is to replace all literals in the AST before GHC throws in its own internal stuff and get back a nice clean AST. I like it! Using GHC as only a type-checker/optimizer is exactly what I want.
Thanks for your input, your experience with Core/STG generation gives me confidence to try.
— Reply to this email directly or view it on GitHubhttps://github.com/faylang/fay/issues/98#issuecomment-8787834.
One thing I wonder about is how source mappings will be doable with Core.
I have now experimented a bit with both Fay, UHC-JS and the Haste compiler, which all seem to be projects with similar scope. Some observations:
The Haste approach seem to be to convert STG to JS, using a representation that mirrors what GHC does in its codegen very closely. The good side of this is full GHC Haskell support, the bad is that the generated code is not very good. For example, all numbers are boxed (unnecessary as the JavaScript engines does internal tagging anyway) and all all application is unflattened (i.e. f(g(x), h(x))
becomes var _1 = g(x); var _2 = h(x); var _3 = g(_1, _2);
) possibly preventing optimizations by the JavaScript JITs.
I do not know the details of the UHC representation, but the generated code looks similarly low-level, so I assume it is generated from a post-core representation. Then the UHC frontend is of course much less complete than GHC, lacking attractive extentions such as TFs, GADTs, generalized newtype deriving etc. They do support Haskell98, existential types and some other things though.
If Fay strives to be Haskell98 (or better) any day soon then reusing an existing frontend seems to be the only way. These parsers/typechekers/desugarers have taken years to develop and test. Reusing them would probably be good for the parent projects too, as it would improve modularity in the original system.
References:
I should add that the GHC internals are quite well documented if you know where to look:
For example, here is the authoritative list of primops (used to generate the source code):
except that if you really try to make a full compiler, you often find yourself searching through lots of source code, or spend a lot of time looking at some GHC native code generator output, scratching your head, wondering why it did generate that. The wiki is a good start, but "quite well documented" is a stretch
And in what sense is the current implementation of Fay not a "full" compiler? It translates between two languages with different syntax and semantics.
Of course GHC is first and foremost a standalone compiler, hence it has "commentary" instead of "documentation". Projects like Fay could help improve its qualities as a library though.
Seems to me that sviperll has this one right. Reimplementing type classes from scratch is almost surely a step too far down the road toward duplicating GHC. Not sure how feasible it is to use AST pattern matching phases and some kind of opaque substitution bits to stop GHC from doing too much low-level stuff... but if it is possible as sviperll suggests, then going via core sounds like the ideal approach. Core is much simpler than Haskell, and this would solve a lot of those trivial "oops, we missed this source language construct in this specific usage" and "that kind of bind works with case but not with where" type of issues that are now making Fay seem so flaky.
I did start on a core-based code gen, I got stuck when I couldn't figure out a way to make the code less ugly. I've not given up, but it's not exactly the free lunch that one might expect. The authors of GHCJS and Haste know that. You have different kinds of flakiness instead.
I'm holding out on Haskell-suite: http://cleantypecheck.wordpress.com/2012/10/23/updates-on-haskell-suite/ Which would provide type-classes and desugaring with a mapping from the original to desugared code.
And there's always the GHC API which can provide desugaring and type annotated tree, but the GHC API also drove me demented slightly.
So there are these approaches:
Doing (1) has got me something workable quickly and, I think, contribution because it is self-contained, you just need to look at the haskell-src-exts and read the compiler. (2) would let us compile all the fancy super-Haskell 2010 stuff. But I don't see many people jumping on that, it's been in the works for a few years now. Fay is four months old. I think (3) would be cleanest and maintain the community benefits of (1), while (3) would produce cleaner code like Fay, but wouldn't have the benefits of (1) because the GHC API makes people run away screaming.
The GHCJS and Haste folk are already working on (2). I'm happy for them to explore that area. I don't think anyone has tried (3) apart from me, but I'm not going to attempt it again for a while.
Anyway, the goal of Fay is to replace JavaScript with something I prefer, in this case a Haskell subset, for me it already does that. Technically the language construct issues aren't “oops we missed” so much as “I don't need that enough to have bothered implementing it yet” (contrast to GHCJS/UHC which in my experience just let you compile everything and then throw something at runtime for unsupported stuff, instilling little confidence). Anyhoo, I'm trying to focus on actually writing programs at the moment, I'm just fixing bugs at the moment, don't plan on doing any drastic reworking.
@chrisdone Thanks for sharing your thoughts. Of course a Haskell compiler is not something you hack together in an afternoon. The Haskell Suite looks promising though.
@chrisdone That makes a lot of sense. The current situation, with using GHC for type checking but then backing off and reparsing in haskell-src-exts, definitely makes me cringe a little; but if the long-term plan is to use haskell-suite as a front end, then it still seems like the right way to go in the short term. I do hope to see others continuing to pursue compiling from Core, though.
Incidentally, it's not so much that the language is a subset that I'm concerned about, and I'm actually far from convinced that adding type classes is important (certainly not for my uses; I deliberately exclude them from my teaching). It's really more of the bunch of little things that would have already been handled by desugaring in GHC. Like converting pattern matching in where clauses to case expressions, for example. Those threaten to make me rewrite a lot of code, and it's difficult to predict what will be missing because it's not one huge feature; it's a bunch of nits.
Understandable, I don't feel the nits as much, as usual with these kind of projects.
For what it's worth, the let
/where
lack of support is due to a lack of lazy patterns. If we implement ~e
then we get let
, where
, and top-level pattern bindings for free. If someone (probably me) implements that, we're good to go. Haskell-suite does desugaring, I already played with the tree and it's very System F-y, so that's good.
Oh, I haven't heard about Haskell-suite. Thank you for mentioning it, Chris. Using it as a front-end will be really great!
Yeah, typeclassess are a major killer feature of Haskell. If Fay added support for typeclasses, it would make life so much easier.
What's the current plan / thinking on adding any form of type class support?
I have motive, means and opportunity if no-one else is working on it.
We're waiting for haskell-suite to be reddy.
What would the next priority be? On Dec 1, 2012 1:08 PM, "Chris Done" notifications@github.com wrote:
We're waiting for haskell-suite to be reddy.
— Reply to this email directly or view it on GitHubhttps://github.com/faylang/fay/issues/98#issuecomment-10916885.
How come this issue is marked closed?
Spring cleaning! We decided to wait for haskell-suite to be ready so until then we don't need to see the ticket. I don't think we'll forget about it :)
I'd like to research working on this issue. Has anyone done work yet on Haskell Suite toward this end, or should I just start from scratch and try to improve Haskell Suite to the point where it can handle type classes?
I was looking at haskell-packages and haskell-names this weekend, they require ghc 7.6 (which isn't in HP) and cabal 1.17 which is only on github. And I didn't manage to get them compiling >:| (although I didn't try very hard)
I'm not sure exactly which of the suite packages we need to support type classes, so that might need some research.
All of them aren't online either, but we have: https://github.com/shayan-najd/Haskell-Desugar https://github.com/feuerbach/haskell-names https://github.com/feuerbach/haskell-packages See http://cleantypecheck.wordpress.com/2012/10/23/updates-on-haskell-suite/ like chris posted above.
Has any thought been put into if type classes should be supported, and if so how this should be done?
I've been thinking about one way of doing it, but I'm not sure how well it would work out.
When we parse
We store this information in the CompileState as
stateClassDecls :: [(Name, [Name])]
generates
When we encounter an expression like
minBound r
we check if it's defined instateClassDecls
and in that case we callr.minBound
otherwise we treat it like we always do.This is the simplest solution but has the problem that a instance declaration that's local in Haskell would be made global in JS. If we solve this by subclassing Rec locally to the instance declaration
instanceof
checks for types will still work, but it will probably cause issues when encoding (which subclass do we deserialize to?). We might instead be able to declare instances separatelyinstanceDecls.Rec_Bounded = { minBound : r0, maxBound : r1 };
We would then need to know the concrete type in order to generate the
Rec_Bounded.minbound
expression. This could be accomplished by transformingminBound r
toinstanceDecls[r.constructor.name + "_Bounded"]
, the "Bounded" part can be retrieved during compilation.Is this a proper solution or did I miss anything?