newtype fixpoint sends the compiler into an infinite loop

[guest]

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

[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..."

[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)

[Isaac Dupree]

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.

[simonpj]

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

Simon

[simonpj]

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

[igloo]

Merged (it pulled cleanly)