New implementation for `ImpredicativeTypes`

Fri Sep 6 19:03:51 UTC 2019

Hi Alex,
Also de-railing the conversation, the Utrecht Haskell Compiler supports
existential types in addition to universally-quantified ones. The work on
Atze Dijkstra (among others) describes some of the problems and possible
solutions to inference:
- His PhD thesis [https://dspace.library.uu.nl/handle/1874/7352] describes
existentials in Section 8.
- Their paper "A Lazy Language Needs a Lazy Type System" [
https://dspace.library.uu.nl/handle/1874/346316] proposes treating
existential types as "polymorphic contexts".

Going back to impredicativity, adding existential types would only
complicate inference more, since there are more types to choose from while
instantiating. But the delta would not be that large, since once a type
constructor guards a type, everything inside of it should be equal, and
checking equality of existential types is as hard as checking for universal
types.

Alejandro

El vie., 6 sept. 2019 a las 16:21, Alex Rozenshteyn (<rpglover64 at gmail.com>)
escribió:

> Hi Simon,
>
> You're exactly right, of course. My example is confusing, so let me see if
> I can clarify.
>
> What I want in the ideal is map show [1, 'a', "b"]. That is, minimal
> syntactic overhead to mapping a function over multiple values of distinct
> types that results in a homogeneous list. As the reddit thread points out,
> there are workarounds involving TH or wrapping each element in a
> constructor or using bespoke operators, but when it comes down to it, none
> of them actually allows me to say what I *mean*; the TH one is closest,
> but I reach for TH only in times of desperation.
>
> I had thought that one of the things preventing this was lack of
> impredicative instantiation, but now I'm not sure. Suppose Haskell *did*
> have existentials; would map show @(exists a. Show a => a) [1, 'a', "b"]
> work in current Haskell and/or in quick-look?
>
> Tangentially, do you have a reference for what difficulties arise in
> adding existentials to Haskell? I have a feeling that it would make working
> with GADTs more ergonomic.
>
> On Fri, Sep 6, 2019 at 12:33 AM Simon Peyton Jones <simonpj at microsoft.com>
> wrote:
>
>> I’m confused.   Char does not have the type (forall a. Show a =>a), so
>> our example is iill-typed in System F, never mind about type inference.
>> Perhaps there’s a typo?   I think you may have ment
>>
>>                exists a. Show a => a
>>
>> which doesn’t exist in Haskell.  You can write existentials with a data
>> type
>>
>>
>>
>> data Showable where
>>
>>    S :: forall a. Show a => a -> Showable
>>
>>
>>
>> Then
>>
>>                map show [S 1, S ‘a’, S “b”]
>>
>> works fine today (without our new stuff), provided you say
>>
>>
>>
>>                instance Show Showable where
>>
>>                  show (S x) = show x
>>
>>
>>
>> Our new system can only type programs that can be written in System F.
>> (The tricky bit is inferring the impredicative instantiations.)
>>
>>
>>
>> Simon
>>
>>
>>
>> *From:* ghc-devs <ghc-devs-bounces at haskell.org> *On Behalf Of *Alex
>> Rozenshteyn
>> *Sent:* 06 September 2019 03:31
>> *To:* Alejandro Serrano Mena <trupill at gmail.com>
>> *Cc:* GHC developers <ghc-devs at haskell.org>
>> *Subject:* Re: New implementation for `ImpredicativeTypes`
>>
>>
>>
>> I didn't say anything when you were requesting use cases, so I have no
>> right to complain, but I'm still a little disappointed that this doesn't
>> fix my (admittedly very minor) issue:
>> https://www.reddit.com/r/haskell/comments/3am0qa/existentials_and_the_heterogenous_list_fallacy/csdwlp2/?context=8&depth=9
>> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.reddit.com%2Fr%2Fhaskell%2Fcomments%2F3am0qa%2Fexistentials_and_the_heterogenous_list_fallacy%2Fcsdwlp2%2F%3Fcontext%3D8%26depth%3D9&data=02%7C01%7Csimonpj%40microsoft.com%7Cf5bddbe8c13b424fad8a08d732724d04%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637033338810706935&sdata=a5c3ujC0kiPlocgHg8AX%2BwIP6ZH2hnqszCpnWOiqpGQ%3D&reserved=0>
>>
>>
>>
>> For those who don't want to click on the reddit link: I would like to be
>> able to write something like map show ([1, 'a', "b"] :: [forall a. Show
>> a => a]), and have it work.
>>
>>
>>
>> On Wed, Sep 4, 2019 at 8:13 AM Alejandro Serrano Mena <trupill at gmail.com>
>> wrote:
>>
>> Hi all,
>>
>> As I mentioned some time ago, we have been busy working on a new
>> implementation of `ImpredicativeTypes` for GHC. I am very thankful to
>> everybody who back then sent us examples of impredicativity which would be
>> nice to support, as far as we know this branch supports all of them! :)
>>
>>
>>
>> If you want to try it, at
>> https://gitlab.haskell.org/trupill/ghc/commit/a3f95a0fe0f647702fd7225fa719a8062a4cc0a5/pipelines?ref=quick-look-build
>> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Ftrupill%2Fghc%2Fcommit%2Fa3f95a0fe0f647702fd7225fa719a8062a4cc0a5%2Fpipelines%3Fref%3Dquick-look-build&data=02%7C01%7Csimonpj%40microsoft.com%7Cf5bddbe8c13b424fad8a08d732724d04%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637033338810716935&sdata=PP1imEsNrkIhloEV3AS52nrZBtyjen4i1e3pJTcMi6M%3D&reserved=0>
>> you can find the result of the pipeline, which includes builds for several
>> platforms (click on the "Artifacts" button, the one which looks like a
>> cloud, to get them). The code is being developed at
>> https://gitlab.haskell.org/trupill/ghc
>> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Ftrupill%2Fghc&data=02%7C01%7Csimonpj%40microsoft.com%7Cf5bddbe8c13b424fad8a08d732724d04%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637033338810716935&sdata=IgtSqJP4%2BhCfy3%2FHVsqX6wpPYVMS8D1wN46aXHnFcUw%3D&reserved=0>
>> .
>>
>>
>>
>> Any code should run *unchanged* except for some eta-expansion required
>> for some specific usage patterns of higher-rank types. Please don't
>> hesitate to ask any questions or clarifications about it. A merge request
>> for tracking this can be found at
>> https://gitlab.haskell.org/ghc/ghc/merge_requests/1659
>> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2Fmerge_requests%2F1659&data=02%7C01%7Csimonpj%40microsoft.com%7Cf5bddbe8c13b424fad8a08d732724d04%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637033338810716935&sdata=YJ5N9d7gXC2JbpqTvpqs4wjY%2F7Ev%2FikRdYIK%2Bhv4rRE%3D&reserved=0>
>>
>>
>>
>> Kind regards,
>>
>> Alejandro
>>
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> <https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=02%7C01%7Csimonpj%40microsoft.com%7Cf5bddbe8c13b424fad8a08d732724d04%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637033338810726922&sdata=jw0sroJW1D8MoBBxVKJROdGefo5gir%2BtQSto0b%2Bj3NA%3D&reserved=0>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20190906/e4a9048c/attachment.html>