Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Exponentional blow-up typing GADT-based continuation #7692

Closed
vicuna opened this issue Dec 19, 2017 · 2 comments
Closed

Exponentional blow-up typing GADT-based continuation #7692

vicuna opened this issue Dec 19, 2017 · 2 comments
Assignees

Comments

@vicuna
Copy link

vicuna commented Dec 19, 2017

Original bug ID: 7692
Reporter: @dra27
Assigned to: @garrigue
Status: assigned (set by @dra27 on 2017-12-19T11:36:25Z)
Resolution: open
Priority: normal
Severity: minor
Version: 4.06.0
Target version: undecided
Category: typing
Monitored by: @nojb @gasche

Bug description

On my machine, the following snippet takes 12 seconds to type.

type _ t =
         | T : ('a t -> 'a) t
         | End : unit t

let rec process : type a . a t -> a = function
| T ->
    process
| End ->
    ()

let () =
  process T T T T T T T T T T T T T T T T T T T T
          (* 1.5 seconds *)
          T
          (* 3 seconds *)
          T
          (* 6 seconds *)
          T
          (* 12 seconds *)
          T
          (* and so forth... *)
          End

Additional information

This has obviously been reduced from a much larger script (it would even be useful, if it didn't take 30 minutes to type it!).

(I realise that it's possible that this is simply a pattern which will always be difficult to type)

@vicuna
Copy link
Author

vicuna commented Dec 19, 2017

Comment author: @dra27

drup has pointed out to me that the GADT is not the fault here - the example can be reduced to a known exponential problem. I expect therefore that there will be nothing to change here!

@github-actions
Copy link

github-actions bot commented May 7, 2020

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 7, 2020
@lpw25 lpw25 closed this as completed May 7, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants