[Haskell-cafe] Eta Reduction
ekmett at gmail.com
Tue Apr 1 14:32:27 UTC 2014
Check the date and consider the process necessary to "enumerate all Haskell
programs and check their types".
On Tue, Apr 1, 2014 at 9:17 AM, John Lato <jwlato at gmail.com> wrote:
> I think this is a great idea and should become a top priority. I would
> probably start by switching to a type-class-based seq, after which perhaps
> the next step forward would become more clear.
> John L.
> On Apr 1, 2014 2:54 AM, "Dan Doel" <dan.doel at gmail.com> wrote:
>> In the past year or two, there have been multiple performance problems in
>> various areas related to the fact that lambda abstraction is not free,
>> though we
>> tend to think of it as so. A major example of this was deriving of
>> Functor. If we
>> were to derive Functor for lists, we would end up with something like:
>> instance Functor  where
>> fmap _  = 
>> fmap f (x:xs) = f x : fmap (\y -> f y) xs
>> This definition is O(n^2) when fully evaluated,, because it causes O(n)
>> expansions of f, so we spend time following indirections proportional to
>> depth of the element in the list. This has been fixed in 7.8, but there
>> other examples. I believe lens,  for instance, has some stuff in it
>> works very hard to avoid this sort of cost; and it's not always as easy
>> to avoid
>> as the above example. Composing with a newtype wrapper, for instance,
>> causes an
>> eta expansion that can only be seen as such at the core level.
>> The obvious solution is: do eta reduction. However, this is not
>> sound currently. The problem is that seq is capable of telling the
>> between the following two expressions:
>> \x -> undefined x
>> The former causes seq to throw an exception, while the latter is
>> defined enough to not do so. So, if we eta reduce, we can cause
>> programs to diverge if they make use of this feature.
>> Luckily, there is a solution.
>> Semantically one would usually identify the above two expressions. While
>> I do
>> believe one could construct a semantics that does distinguish them, it is
>> the usual practice. This suggests that there is a way to not distinguish
>> perhaps even including seq. After all, the specification of seq is
>> monotone and
>> continuous regardless of whether we unify ⊥ with \x -> ⊥ x or insert an
>> element for the latter.
>> The currently problematic case is function spaces, so I'll focus on it.
>> seq : (a -> b) -> c -> c
>> act? Well, other than an obvious bottom, we need to emit bottom whenever
>> given function is itself bottom at every input. This may first seem like a
>> problem, but it is actually quite simple. Without loss of generality, let
>> assume that we can enumerate the type a. Then, we can feed these values
>> to the
>> function, and check their results for bottom. Conal Elliot has prior art
>> this sort of thing with his unamb  package. For each value x :: a,
>> compute 'f x `seq` ()' in parallel, and look for any successes. If we
>> ever find
>> one, we know the function is non-bottom, and we can return our value of
>> c. If we
>> never finish searching, then the function must be bottom, and seq should
>> terminate, so we have satisfied the specification.
>> Now, some may complain about the enumeration above. But this, too, is a
>> matter. It is well known that Haskell programs are denumerable. So it is
>> easy to enumerate all Haskell programs that produce a value, check
>> whether that
>> value has the type we're interested in, and compute said value. All of
>> this can
>> be done in Haskell. Thus, every Haskell type is programatically
>> enumerable in
>> Haskell, and we can use said enumeration in our implementation of seq for
>> function types. I have discussed this with Russell O'Connor , and he
>> me that this argument should be sufficient even if we consider semantic
>> of Haskell that contain values not denoted by any Haskell program, so we
>> be safe there.
>> The one possible caveat is that this implementation of seq is not
>> uniform across all types, so the current fully polymorphic type of seq
>> may not
>> make sense. But moving back to a type class based approach isn't so bad,
>> this time we will have a semantically sound backing, instead of just
>> having a
>> class with the equivalent of the current magic function in it.
>> Once this machinery is in place, we can eta reduce to our hearts'
>> content, and
>> not have to worry about breaking semantics. We'd no longer put the burden
>> programmers to use potentially unsafe hacks to avoid eta expansions. I
>> for not sketching an implementation of the above algorithm, but I'm sure
>> should be elementary enough to make it into GHC in the next couple
>> Everyone learns about this type of thing in university computer science
>> programs, no?
>> Thoughts? Comments? Questions?
>> -- Dan
>>  http://hackage.haskell.org/package/lens
>>  http://hackage.haskell.org/package/unamb
>>  http://r6.ca/
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe