Re: Bug in GHC type system

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@xxxxxxxxxxx
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs