Bug in GHC type system
Christian Maeder
maeder at tzi.de
Thu Nov 10 06:21:19 EST 2005
Hi Baltasar,
maybe it's GHC's inliner. See
http://www.haskell.org/ghc/docs/latest/html/users_guide/bugs.html#bugs-ghc
and the "russel" example is similar enough to yours. (I have not
checked, though.)
I apologize, again, for the wrong spelling, It must be "Russell" with
two "l"!
Cheers Christian
Baltasar Trancon y Widemann wrote:
> Hi,
>
> I have found a three-line program that will cause recent GHC type
> checker to diverge. The program is admittedly pathological, so here's
> the story:
>
> As part of my PhD thesis I am investigating a backend virtual machine
> for functional programs where
>
> * beta reduction is explicit,
> * consequently, (->) is a free type constructor that can be mixed with
> (*) and (+) in arbitrary mutual recursion.
>
> In such a system, is possible to define a well-typed, effective Y
> combinator. Of course, the reduction strategy has to be hand-coded
> explicitly. Since the lazy strategy is not the worst choice, I tried to
> abuse the Haskell type system for an experiment:
>
>> y f = w w
>> where w x = f (x x)
>
> This is, naturally, rejected by the type checker because of recursive
> type equations of the form:
>
>> t = t -> u
>
> But one can put a datatype constructor in between:
>
>> newtype Auto a = { self :: Auto a -> a }
>> y f = self w w
>> where w = Auto (\x -> f (self x x))
>
> Sadly, I cannot load this program into GHCi or compile it with GHC. HUGS
> (as of November 2003) has no such problem, and computes the factorial
> function:
>
>> let fac f x = if x == 0 then 1 else x * f (x - 1)
>> in y fac 10
>
>
> Technical details:
>
> x86 PC with AMD Athlon XP CPU
> SuSE 9.0 Linux with kernel 2.6.10
> ghc-6.2.2
>
> also observed for 6.4 on a different machine
>
> The log of `ghc -v -C Ups.hs` is attached. The compiler hangs after the
>
>> *** Simplify:
>
> line, slowly consuming unbounded amounts of heap (presumably due to a
> divergent type unification). The last two log lines are issued only
> after a ^C signal. If 'newtype' is replaced by 'data', one more line of
> statistics
>
>> Result size = 17
>
> is issued before the compiler hangs, too.
>
>
> Greetings,
>
> Baltasar Trancon y Widemann
>
> ------------------------------------------------------------------------
>
> module Ups where
>
> -- y f = w w where w x = f (x x)
>
> newtype Auto a = Auto {self :: Auto a -> a}
> y f = self w w
> where w = Auto (\x -> f (self x x))
>
>
> ------------------------------------------------------------------------
>
> Glasgow Haskell Compiler, Version 6.2.2, for Haskell 98, compiled by GHC version 5.04.3
> Using package config file: /usr/local/lib/ghc-6.2.2/package.conf
>
> ==================== Packages ====================
> Package
> {name = "data",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/data"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSdata"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["haskell98", "lang", "util"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "rts",
> auto = False,
> import_dirs = [],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSrts"],
> extra_libraries = ["m", "gmp", "dl"],
> include_dirs = ["/usr/local/lib/ghc-6.2.2/include"],
> c_includes = ["Stg.h"],
> package_deps = [],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts =
> ["-u",
> "GHCziBase_Izh_static_info",
> "-u",
> "GHCziBase_Czh_static_info",
> "-u",
> "GHCziFloat_Fzh_static_info",
> "-u",
> "GHCziFloat_Dzh_static_info",
> "-u",
> "GHCziPtr_Ptr_static_info",
> "-u",
> "GHCziWord_Wzh_static_info",
> "-u",
> "GHCziInt_I8zh_static_info",
> "-u",
> "GHCziInt_I16zh_static_info",
> "-u",
> "GHCziInt_I32zh_static_info",
> "-u",
> "GHCziInt_I64zh_static_info",
> "-u",
> "GHCziWord_W8zh_static_info",
> "-u",
> "GHCziWord_W16zh_static_info",
> "-u",
> "GHCziWord_W32zh_static_info",
> "-u",
> "GHCziWord_W64zh_static_info",
> "-u",
> "GHCziStable_StablePtr_static_info",
> "-u",
> "GHCziBase_Izh_con_info",
> "-u",
> "GHCziBase_Czh_con_info",
> "-u",
> "GHCziFloat_Fzh_con_info",
> "-u",
> "GHCziFloat_Dzh_con_info",
> "-u",
> "GHCziPtr_Ptr_con_info",
> "-u",
> "GHCziPtr_FunPtr_con_info",
> "-u",
> "GHCziStable_StablePtr_con_info",
> "-u",
> "GHCziBase_False_closure",
> "-u",
> "GHCziBase_True_closure",
> "-u",
> "GHCziPack_unpackCString_closure",
> "-u",
> "GHCziIOBase_stackOverflow_closure",
> "-u",
> "GHCziIOBase_heapOverflow_closure",
> "-u",
> "GHCziIOBase_NonTermination_closure",
> "-u",
> "GHCziIOBase_BlockedOnDeadMVar_closure",
> "-u",
> "GHCziIOBase_Deadlock_closure",
> "-u",
> "GHCziWeak_runFinalizzerBatch_closure",
> "-u",
> "__stginit_Prelude"],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "base",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSbase"],
> extra_libraries = ["HSbase_cbits"],
> include_dirs = [],
> c_includes = ["HsBase.h"],
> package_deps = ["rts"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "haskell98",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HShaskell98"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "haskell-src",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HShaskell-src"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["base", "haskell98"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "network",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSnetwork"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = ["HsNet.h"],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "parsec",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSparsec"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "QuickCheck",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSQuickCheck"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "readline",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSreadline"],
> extra_libraries = ["readline", "ncurses"],
> include_dirs = [],
> c_includes = ["HsReadline.h"],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "unix",
> auto = True,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/imports"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSunix"],
> extra_libraries = ["HSunix_cbits", "dl"],
> include_dirs = [],
> c_includes = ["HsUnix.h"],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "lang",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/lang"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSlang"],
> extra_libraries = ["HSlang_cbits"],
> include_dirs = [],
> c_includes = ["HsLang.h"],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "concurrent",
> auto = False,
> import_dirs =
> ["/usr/local/lib/ghc-6.2.2/hslibs-imports/concurrent"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSconcurrent"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["base"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "posix",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/posix"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSposix"],
> extra_libraries = ["HSposix_cbits", "dl"],
> include_dirs = [],
> c_includes = ["HsPosix.h"],
> package_deps = ["lang", "unix"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "util",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/util"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSutil"],
> extra_libraries = ["HSutil_cbits"],
> include_dirs = [],
> c_includes = ["HsUtil.h"],
> package_deps =
> ["lang", "concurrent", "QuickCheck", "readline", "posix"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "text",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/text"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HStext"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["lang", "parsec"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "net",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/net"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HSnet"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["network"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
> Package
> {name = "hssource",
> auto = False,
> import_dirs = ["/usr/local/lib/ghc-6.2.2/hslibs-imports/hssource"],
> source_dirs = [],
> library_dirs = ["/usr/local/lib/ghc-6.2.2"],
> hs_libraries = ["HShssource"],
> extra_libraries = [],
> include_dirs = [],
> c_includes = [],
> package_deps = ["haskell-src"],
> extra_ghc_opts = [],
> extra_cc_opts = [],
> extra_ld_opts = [],
> framework_dirs = [],
> extra_frameworks = []}
>
>
> Hsc static flags: -static
> *** Checking old interface for Ups:
> *** Parser:
> *** Renamer/typechecker:
> *** Desugar:
> Result size = 20
> *** Simplify:
> *** Deleting temp files
> Deleting:
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Glasgow-haskell-bugs mailing list
> Glasgow-haskell-bugs at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
More information about the Glasgow-haskell-bugs
mailing list