Avoiding construction of dead dictionaries

Simon Peyton Jones simonpj at microsoft.com
Mon Aug 9 15:56:27 UTC 2021


> . So apparently it is possible for a dictionary to be bottom somehow.
That should not happen.

Except in the case of single-method dictionaries like
                class C a where op ::  a -> a
In these cases the "dictionary" is represented by a newtype, like this
                newtype C a = MkC (a->a)

Then you could say
                instance C Int where
                 op = bottom

and now a (C Int) dictionary is simply bottom.

It would be easy to change this decision, and use a data constructor even for single-method classes.  Some programs would become slightly less efficient, but things would be a bit more uniform.  If there was a real advantage to doing this, it'd definitely be worth measuring the perf cost (if any).

Simon

From: Glasgow-haskell-users <glasgow-haskell-users-bounces at haskell.org> On Behalf Of Brandon Allbery
Sent: 09 August 2021 16:32
To: Tom Smeding <x at tomsmeding.com>
Cc: GHC users <glasgow-haskell-users at haskell.org>; sperber at deinprogramm.de
Subject: Re: Avoiding construction of dead dictionaries

We haven't figured out what they did, but the other day we had someone in #haskell with an infinite loop evaluating a dictionary. So apparently it is possible for a dictionary to be bottom somehow.

On Mon, Aug 9, 2021 at 11:27 AM Tom Smeding <x at tomsmeding.com<mailto:x at tomsmeding.com>> wrote:
Hi Mike,


> But wouldn't that imply that ghc can build dictionary-construction code

> that evaluates to bottom? Can that happen?


I assume no, but here the dictionary is embedded as a field in the GADT, right? So if the data value is bottom, there is not even a dictionary to be found, let alone not-bottom.


This assumes that the Dict in `Entail (Sub Dict)` is a GADT like


Dict :: Con b => Dict something


where the Con dictionary is contained in the GADT. Remember that in Core, dictionaries are values, and there is no difference between => and ->.


- Tom



-------- Original Message --------

On 9 Aug 2021, 15:24, Michael Sperber < sperber at deinprogramm.de<mailto:sperber at deinprogramm.de>> wrote:


Thanks for thinking about this one!

On Fri, Aug 06 2021, Tom Smeding <x at tomsmeding.com<mailto:x at tomsmeding.com>> wrote:

> Would it not be unsound for ghc to elide dictionary construction here?

> After all, the right-hand side might actually be a bottom

> (e.g. undefined) at run-time, in which case the pattern match cannot

> succeed according to the semantics of Haskell.

But wouldn't that imply that ghc can build dictionary-construction code

that evaluates to bottom? Can that happen?

> I suspect that if you make the pattern match lazy (i.e. ~(Entail (Sub

> Dict))) or ignore the argument altogether (i.e. _), dictionary

> construction will be elided.

Thanks for the hint! ghc gives me this unfortunately, implying that it

agreed with your first comment:

src/ConCat/Category.hs:190:29: error:

* Could not deduce: Con b arising from a use of 'r'

from the context: Con a

bound by the type signature for:

(<+) :: forall a b r. Con a => (Con b => r) -> (a |- b) -> r

at src/ConCat/Category.hs:189:1-46

* In the expression: r

In an equation for '<+': r <+ ~(Entail (Sub Dict)) = r

* Relevant bindings include

r :: Con b => r (bound at src/ConCat/Category.hs:190:1)

(<+) :: (Con b => r) -> (a |- b) -> r

(bound at src/ConCat/Category.hs:190:3)

|

190 | r <+ ~(Entail (Sub Dict)) = r

| ^

Other ideas welcome!

--

Regards,

Mike

_______________________________________________

Glasgow-haskell-users mailing list

Glasgow-haskell-users at haskell.org<mailto:Glasgow-haskell-users at haskell.org>

http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users<https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fglasgow-haskell-users&data=04%7C01%7Csimonpj%40microsoft.com%7C7bf3769704884ed6592e08d95b4aeb26%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637641199636853840%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=ix06XQPvpu%2B1PLzoc5rRQM6cMv8yPF6o87uVwD0sUwQ%3D&reserved=0>

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users at haskell.org<mailto:Glasgow-haskell-users at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users<https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fglasgow-haskell-users&data=04%7C01%7Csimonpj%40microsoft.com%7C7bf3769704884ed6592e08d95b4aeb26%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637641199636863837%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=sQDTBnklNv7YLRvhiY5CEtbZgcZT8p7RR%2Bw57sCqFJk%3D&reserved=0>


--
brandon s allbery kf8nh
allbery.b at gmail.com<mailto:allbery.b at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/glasgow-haskell-users/attachments/20210809/5092b88d/attachment.html>


More information about the Glasgow-haskell-users mailing list