Opened 10 years ago

Closed 9 years ago

Last modified 8 years ago

#1495 closed merge (fixed)

newtype fixpoint sends the compiler into an infinite loop

Reported by: guest Owned by: igloo
Priority: normal Milestone: 6.8.3
Component: Compiler Version: 6.6.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: T1495
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I was playing around with some edge cases in the type system and hit an infinite loop compiling the following program:

module CompilerBug where

newtype Fix a = Fix (a (Fix a))
data ID a = ID a
newtype I a = I a

testOk :: Fix ID
testOk = undefined

-- this definition causes the compiler to fail to terminate
testInfiniteLoop :: Fix I
testInfiniteLoop = undefined

Change History (12)

comment:1 Changed 10 years ago by guest

Summary: newtype fix sends the compiler into an infinite loopnewtype fixpoint sends the compiler into an infinite loop

comment:2 Changed 10 years ago by chevalier@…

Sounds like the same behavior described in section 12.2 of the manual - http://www.haskell.org/ghc/docs/latest/html/users_guide/bugs.html "GHC's inliner can be persuaded into non-termination using the standard way to encode recursion via a data type..."

comment:3 Changed 10 years ago by guest

That's possible, although I suspect not; that bug refers specifically to the inliner (which I assume means function inlining), whereas with this bug there's no inlining to do; testInfiniteLoop = undefined.

(code from that page for comparison)

data U = MkU (U -> Bool)

russel :: U -> Bool
russel u@(MkU p) = not $ p u

x :: Bool
x = russel (MkU russel)

comment:4 Changed 10 years ago by Isaac Dupree

Architecture: x86Multiple
Operating System: WindowsMultiple

There is no recursion, in fact nothing at all on the value level here, only types, and no -O flags. 'russel' doesn't need newtypes either. Also fails on 6.7 (and works with testInfiniteLoop commented); here is 6.7's -v output:

Glasgow Haskell Compiler, Version 6.7.20070525, for Haskell 98, compiled by GHC version 6.6.1
Using package config file: /home/isaac/hardly-mine-at-all/build/5ghc-6.7/driver/package.conf.inplace
wired-in package base mapped to base-2.1
wired-in package rts mapped to rts-1.0
wired-in package haskell98 mapped to haskell98-1.0
wired-in package template-haskell mapped to template-haskell-0.1
Hsc static flags: -static
Created temporary directory: /tmp/ghc6326_0
*** Checking old interface for main:CompilerBug:
*** Parser:
*** Renamer/typechecker:
*** Desugar:
    Result size = 10
*** Simplify:
    Result size = 6
*** Tidy Core:
    Result size = 6
*** CorePrep:
    Result size = 12
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:

and the end of 6.7's -v5 output:

*** Stg2Stg:

==================== Stg2Stg ====================
CompilerBug.testInfiniteLoop =
    \u srt:SRT:[(rQ, GHC.Err.undefined)] [] GHC.Err.undefined;
CompilerBug.testOk = \u srt:SRT:[(rQ, GHC.Err.undefined)] [] GHC.Err.undefined;
CompilerBug.ID = \r srt:SRT:[] [eta_s7x] CompilerBug.ID [eta_s7x];



==================== STG syntax: ====================
CompilerBug.testInfiniteLoop = \u srt:(0,*bitmap*) [] GHC.Err.undefined;
SRT(CompilerBug.testInfiniteLoop): [GHC.Err.undefined]
CompilerBug.testOk = \u srt:(0,*bitmap*) [] GHC.Err.undefined;
SRT(CompilerBug.testOk): [GHC.Err.undefined]
CompilerBug.ID = \r [eta_s7x] CompilerBug.ID [eta_s7x];
SRT(CompilerBug.ID): []


*** CodeGen:

The CPU is still going, but memory usage is not increasing, and ghc doesn't terminate.

comment:5 Changed 10 years ago by simonpj

Milestone: 6.8
Owner: set to simonpj

I agree. I think this one can and should be fixed. I'll look at it in due course.

Simon

comment:6 Changed 10 years ago by guest

comment:7 Changed 9 years ago by simonpj

Milestone: 6.8 branch6.8.3

comment:8 Changed 9 years ago by simonpj

Owner: changed from simonpj to igloo
Test Case: T1495

I've finally fixed this.

Ian: have a go at merging this patch to 6.8. If it doesn't work easily, then I think we can leave it unfixed on the branch, unless kfrdbs is really keen.

Fri Dec 21 09:04:06 GMT 2007  simonpj@microsoft.com
  * Improve handling of newtypes (fixes Trac 1495)

Simon

comment:9 Changed 9 years ago by simonpj

Type: bugmerge

comment:10 Changed 9 years ago by igloo

Resolution: fixed
Status: newclosed

Merged (it pulled cleanly)

comment:11 Changed 8 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:12 Changed 8 years ago by simonmar

Operating System: MultipleUnknown/Multiple
Note: See TracTickets for help on using tickets.