Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are implicit parameters a difficulty for inlining in GHC?

I'm curious about the objections to implicit parameters discussed in the Functional Pearl: Implicit Configurations article by Kiselyov and Shan.

It is not sound to inline code (β-reduce) in the presence of implicit parameters.

Really? I'd expect that GHC should inline into the same scope as the passed implicit parameter, no?

I believe I understand their objection that :

A term’s behavior can change if its signature is added, removed, or changed.

GHC's user documentation explains that programers must take care around polymorphic recursion and monomorphism restriction. Is this somehow what they mean by a problem for inlining?

I presume this polymorphic recursion example covers what they mean by "generalizing over implicit parameters" as well? Anything else?

Is the ReifiesStorable type class from Data.Reflection really a sensible solution to these difficulties? It seemingly deserializes the entire implicit data structure every time it's accessed, which sounds be disastrous for performance. We might for-example want our implicit information to be Cayley table or character table that occupies a gig of ram and must be access during millions of algebraic operations.

Is there perhaps some better solution that employs implicit parameters, or another technique the compiler can easily optimize, behind the scenes, while still guaranteeing more via the type system using state threads or whatever?

like image 241
Jeff Burdges Avatar asked Apr 28 '12 12:04

Jeff Burdges


1 Answers

Yes, the example from the GHC manual shows how adding a type signature can change the semantics of code with implicit parameters, and I believe this is what they mean by breaking inlining; inlining an application of len_acc1 vs. an application of len_acc2 produces the same code, despite the two having different semantics.

As far as generalising over implicit parameters, it means that you can't write a function that can operate on multiple implicit parameters; there is no mechanism to abstract over them, as the implicit parameter a function uses is fixed by its type. With reflection, you can easily write a function like doSomethingWith :: (Reifies s a, Num a) => Proxy s -> a, which can operate over any type that reifies a numeric value.

As for ReifiesStorable, you're looking at an old version of the reflection package; the latest version has a very efficient implementation in which reify only costs as much as a function call.1 Note that, even with the old implementation, you would generally not use the ReifiesStorable class directly, but instead Reifies, which uses ReifiesStorable to reify a StablePtr, so only a few bytes end up being copied, not the entire object. (This is what the original implementation in the paper does, too.) Both implementations are definitely fast enough for practical use, with the old, "slow" implementation taking about 100 ms to reify and reflect 100000 values, and the new implementation under 10 ms.

(Full disclosure: I worked on the new implementation.)

1 The fast implementation depends on Haskell implementation details. The older, slower implementation is automatically used for Haskell implementations that the fast implementation has not yet been tested with; so far, GHC and Hugs have been shown to work with the fast implementation. You can request the slow implementation with -fslow, but it's unlikely to stop working unless GHC significantly overhauls its implementation of typeclasses. (Even if it does, you'd only have to recompile the packages that use reflection to get it working again.)

like image 59
ehird Avatar answered Sep 28 '22 00:09

ehird