mutal recursion

[backtracking]

In an attempt to figure out of mutual recursion us supported, with the following input file,

fun foo()
  bar()
fun bar()
  foo()
fun main()
  ()

I get the following error with Koka 3.1.2:

$ koka --console=raw -v0 -e test.koka
test(1, 1): internal error: Backend.C.FromCore.genFunDefSig: not a function: (test/bar,test/foo)
CallStack (from HasCallStack):
  error, called at src/Backend/C/FromCore.hs:326:42 in koka-3.1.2-2NpoSf9Uv2JEsgjfT7jQ0Q:Backend.C.FromCore

Failed to compile test.koka

[4y8]

The core generated by koka --console=raw -v0 -e --showcore test.koka is:

pub fun bar : forall<a,b> (x : a) -> div b
  = forall<a,b> test/foo;
pub fun foo : forall<a,b> (x : a) -> div b
  = forall<a,b> test/bar;
pub fun main : () -> ()
  = fn(){
    std/core/types/Unit;
  };

While the function genFunSig (which raises the issue) expects a Lam, the body of both functions are variables.

koka/src/Backend/C/FromCore.hs

Lines 341 to 348 in 70f5609

	genFunSig :: Bool -> Visibility -> Name -> Expr -> Doc
	genFunSig inlineC vis name defExpr
	= let tryFun expr = case expr of
	TypeApp e _ -> tryFun e
	TypeLam _ e -> tryFun e
	Lam params eff body -> genLamSig inlineC vis name params body
	_ -> error ("Backend.C.FromCore.genFunDefSig: not a function: " ++ show (name,defExpr))
	in tryFun defExpr

There seem to be an eta-contraction between initial core and core which causes the problem as the initial core is:

pub fun bar : forall<a> () -> div a
  = forall<a> forall<b> fn<div>(){
    test/foo();
  };
pub fun foo : forall<a> () -> div a
  = forall<a> forall<b> fn<div>(){
    test/bar();
  };
pub fun main : () -> ()
  = fn(){
    std/core/types/Unit;
  };

It seems to be caused by the following optimisation, deleting this snippet allows the program to compile. The bug could be fixed by eta-expanding function definitions when they aren't lambdas.

koka/src/Core/Simplify.hs

Lines 457 to 467 in 70f5609

	-- direct application of arguments to a lambda: fun(x1...xn) { f(x1,...,xn) } -> f
	bottomUp (Lam pars eff (App f@(Var _ info) args)) | notExternal && length pars == length args && argsMatchPars
	= f
	where
	argsMatchPars = and (zipWith argMatchPar pars args)
	argMatchPar par (Var name _) = par == name
	argMatchPar _ _ = False
	notExternal = case info of
	InfoExternal{} -> False
	_ -> True

[daanx]

That was such a strange bug! weird we never ran into it before but it should be fixed now.

[daanx]

btw. Koka support mutual recursion and does a topological sort. For polymorphic recursion one needs to add explicit type signatures.