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