search

scala / bug

Scala 2 bug reports only. Please, no questions — proper bug reports only.
https://scala-lang.org
232 stars 21 forks source link

Type checker runs out of memory on deeply nested lambda term (generated code) #10964

Open mschlaipfer opened 6 years ago

mschlaipfer commented 6 years ago

I am trying to synthesize Scala code automatically and unfortunately the Scala type checker runs out of memory when running sbt compile on this generated code. I currently start sbt with sbt -J-Xmx6G -J-Xms6G -J-Xss40M -J-XX:+UseConcMarkSweepGC

The code causing it is at the bottom. It contains a deeply nested lambda term. The program might contain errors in and of itself.

I guess my question would be, what are the issues that I'm causing in the type checker (or should the type checker actually be able to handle such a term with "reasonable" amount of memory usage) and what would be a good workaround. I can think of, for example, breaking up the term into smaller sub-terms. Also, I'm not yet providing all the type annotations possible.

[error] Java heap space
[error] java.util.zip.InflaterInputStream.<init>(InflaterInputStream.java:88)
[error] java.util.zip.ZipFile$ZipFileInflaterInputStream.<init>(ZipFile.java:393)
[error] java.util.zip.ZipFile.getInputStream(ZipFile.java:374)
[error] java.util.jar.JarFile.getManifestFromReference(JarFile.java:199)
[error] java.util.jar.JarFile.getManifest(JarFile.java:180)
[error] sun.misc.URLClassPath$JarLoader$2.getManifest(URLClassPath.java:944)
[error] java.net.URLClassLoader.defineClass(URLClassLoader.java:450)
[error] java.net.URLClassLoader.access$100(URLClassLoader.java:73)
[error] java.net.URLClassLoader$1.run(URLClassLoader.java:368)
[error] java.net.URLClassLoader$1.run(URLClassLoader.java:362)
[error] java.security.AccessController.doPrivileged(Native Method)
[error] java.net.URLClassLoader.findClass(URLClassLoader.java:361)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:424)
[error] java.lang.ClassLoader.loadClass(ClassLoader.java:357)
[error] scala.tools.nsc.typechecker.Infer$Inferencer.inferMethodInstance(Infer.scala:89)
[error] scala.tools.nsc.typechecker.Typers$Typer.handlePolymorphicCall$1(Typers.scala:3694)
[error] scala.tools.nsc.typechecker.Typers$Typer.doTypedApply(Typers.scala:3699)
[error] scala.tools.nsc.typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4773)
[error] scala.tools.nsc.typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
[error] scala.tools.nsc.typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
[error] scala.tools.nsc.typechecker.Typers$Typer.typed1(Typers.scala:5603)
[error] scala.tools.nsc.typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
[error] scala.tools.nsc.typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
[error] scala.tools.nsc.typechecker.Typers$Typer.body$2(Typers.scala:5613)
[error] scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:5618)
[error] scala.tools.nsc.typechecker.Typers$Typer.$anonfun$typedArg$1(Typers.scala:3290)
[error] scala.tools.nsc.typechecker.Typers$Typer.typedArg(Typers.scala:477)
[error] scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgWithFormal$1(PatternTypers.scala:108)
[error] scala.tools.nsc.typechecker.PatternTypers$PatternTyper.$anonfun$typedArgsForFormals$4(PatternTypers.scala:122)
[error] scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgsForFormals(PatternTypers.scala:122)
[error] scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgsForFormals$(PatternTypers.scala:103)
[error] scala.tools.nsc.typechecker.Typers$Typer.typedArgsForFormals(Typers.scala:111)
[error]            
[debug] Forcing garbage collection...
[error] java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError: Java heap space
[error]     at java.util.concurrent.FutureTask.report(FutureTask.java:122)
[error]     at java.util.concurrent.FutureTask.get(FutureTask.java:192)
[error]     at sbt.ConcurrentRestrictions$$anon$4.take(ConcurrentRestrictions.scala:207)
[error]     at sbt.Execute.next$1(Execute.scala:105)
[error]     at sbt.Execute.processAll(Execute.scala:108)
[error]     at sbt.Execute.runKeep(Execute.scala:85)
[error]     at sbt.EvaluateTask$.liftedTree1$1(EvaluateTask.scala:387)
[error]     at sbt.EvaluateTask$.run$1(EvaluateTask.scala:386)
[error]     at sbt.EvaluateTask$.runTask(EvaluateTask.scala:405)
[error]     at sbt.internal.Aggregation$.$anonfun$timedRun$4(Aggregation.scala:100)
[error]     at sbt.EvaluateTask$.withStreams(EvaluateTask.scala:331)
[error]     at sbt.internal.Aggregation$.timedRun(Aggregation.scala:98)
[error]     at sbt.internal.Aggregation$.runTasks(Aggregation.scala:111)
[error]     at sbt.internal.Aggregation$.$anonfun$applyTasks$1(Aggregation.scala:68)
[error]     at sbt.Command$.$anonfun$applyEffect$2(Command.scala:130)
[error]     at sbt.internal.Aggregation$.$anonfun$evaluatingParser$11(Aggregation.scala:220)
[error]     at sbt.internal.Act$.$anonfun$actParser0$3(Act.scala:387)
[error]     at sbt.MainLoop$.processCommand(MainLoop.scala:154)
[error]     at sbt.MainLoop$.$anonfun$next$2(MainLoop.scala:137)
[error]     at sbt.State$$anon$1.runCmd$1(State.scala:242)
[error]     at sbt.State$$anon$1.process(State.scala:248)
[error]     at sbt.MainLoop$.$anonfun$next$1(MainLoop.scala:137)
[error]     at sbt.internal.util.ErrorHandling$.wideConvert(ErrorHandling.scala:16)
[error]     at sbt.MainLoop$.next(MainLoop.scala:137)
[error]     at sbt.MainLoop$.run(MainLoop.scala:130)
[error]     at sbt.MainLoop$.$anonfun$runWithNewLog$1(MainLoop.scala:108)
[error]     at sbt.io.Using.apply(Using.scala:22)
[error]     at sbt.MainLoop$.runWithNewLog(MainLoop.scala:102)
[error]     at sbt.MainLoop$.runAndClearLast(MainLoop.scala:58)
[error]     at sbt.MainLoop$.runLoggedLoop(MainLoop.scala:43)
[error]     at sbt.MainLoop$.runLogged(MainLoop.scala:35)
[error]     at sbt.StandardMain$.runManaged(Main.scala:113)
[error]     at sbt.xMain.run(Main.scala:76)
[error]     at xsbt.boot.Launch$$anonfun$run$1.apply(Launch.scala:109)
[error]     at xsbt.boot.Launch$.withContextLoader(Launch.scala:128)
[error]     at xsbt.boot.Launch$.run(Launch.scala:109)
[error]     at xsbt.boot.Launch$$anonfun$apply$1.apply(Launch.scala:35)
[error]     at xsbt.boot.Launch$.launch(Launch.scala:117)
[error]     at xsbt.boot.Launch$.apply(Launch.scala:18)
[error]     at xsbt.boot.Boot$.runImpl(Boot.scala:56)
[error]     at xsbt.boot.Boot$.main(Boot.scala:18)
[error]     at xsbt.boot.Boot.main(Boot.scala)
[error] Caused by: java.lang.OutOfMemoryError: Java heap space
[error]     at java.util.zip.InflaterInputStream.<init>(InflaterInputStream.java:88)
[error]     at java.util.zip.ZipFile$ZipFileInflaterInputStream.<init>(ZipFile.java:393)
[error]     at java.util.zip.ZipFile.getInputStream(ZipFile.java:374)
[error]     at java.util.jar.JarFile.getManifestFromReference(JarFile.java:199)
[error]     at java.util.jar.JarFile.getManifest(JarFile.java:180)
[error]     at sun.misc.URLClassPath$JarLoader$2.getManifest(URLClassPath.java:944)
[error]     at java.net.URLClassLoader.defineClass(URLClassLoader.java:450)
[error]     at java.net.URLClassLoader.access$100(URLClassLoader.java:73)
[error]     at java.net.URLClassLoader$1.run(URLClassLoader.java:368)
[error]     at java.net.URLClassLoader$1.run(URLClassLoader.java:362)
[error]     at java.security.AccessController.doPrivileged(Native Method)
[error]     at java.net.URLClassLoader.findClass(URLClassLoader.java:361)
[error]     at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
[error]     at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
[error]     at scala.tools.nsc.typechecker.Infer$Inferencer.inferMethodInstance(Infer.scala:89)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.handlePolymorphicCall$1(Typers.scala:3694)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.doTypedApply(Typers.scala:3699)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.normalTypedApply$1(Typers.scala:4773)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typedApply$1(Typers.scala:4801)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typedInAnyMode$1(Typers.scala:5586)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typed1(Typers.scala:5603)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.runTyper$1(Typers.scala:5640)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typedInternal(Typers.scala:5672)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.body$2(Typers.scala:5613)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:5618)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.$anonfun$typedArg$1(Typers.scala:3290)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typedArg(Typers.scala:477)
[error]     at scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgWithFormal$1(PatternTypers.scala:108)
[error]     at scala.tools.nsc.typechecker.PatternTypers$PatternTyper.$anonfun$typedArgsForFormals$4(PatternTypers.scala:122)
[error]     at scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgsForFormals(PatternTypers.scala:122)
[error]     at scala.tools.nsc.typechecker.PatternTypers$PatternTyper.typedArgsForFormals$(PatternTypers.scala:103)
[error]     at scala.tools.nsc.typechecker.Typers$Typer.typedArgsForFormals(Typers.scala:111)
[error] java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError: Java heap space
[error] Use 'last' for the full log.

The code that causes the type checker to run OOM:

object extracted extends App {
  def s( x: Int ) = x + 1
  def mul( x: Int )( y: Int ) = x * y
  def leq( x: Int )( y: Int ) = x <= y

  def pow2( x: Int ) = x * x
  def pi2[A, B]( p: ( A, B ) ) = p._2
  sealed trait Sum[A, B]
  final case class Inr[A, B]( v: B ) extends Sum[A, B]
  def inr[A, B]( v: B ): Sum[A, B] = new Inr( v )

  def matchSum[A, B, C]( p1: Sum[A, B] )( p2: A => C )( p3: B => C ) = {
    p1 match {
      case Inl( a ) => p2( a )
      case Inr( b ) => p3( b )
    }
  }

  def eq[X]( x: X )( y: X ) = x == y
  def lt( x: Int )( y: Int ) = x < y
  final case class Inl[A, B]( v: A ) extends Sum[A, B]
  def inl[A, B]( v: A ): Sum[A, B] = new Inl( v )
  def f( x: Int )( y: Int ) = x < ( y + 1 ) * ( y + 1 ) && y * y <= x

  def natRec[A]( p1: A )( p2: ( Int => A => A ) )( p3: Int ): A = {
    if ( p3 == 0 ) {
      p1
    } else {
      p2( p3 - 1 )( natRec( p1 )( p2 )( p3 - 1 ) )
    }
  }
  class NewException[A]( m: A ) extends Exception
  def exception[A]( p: A ) = { new NewException( p ) }

  def subst[A, B]( x: A )( y: B ): Unit = ()
  def bar2[X, A, B, C]( p1: X => Boolean )( p2: A => C )( p3: B => C ): C = { ??? }

  def pi1[A, B]( p: ( A, B ) ) = p._1
  def bar[A, B, C]( p2: A => C )( p3: B => C ): C = { ??? }

  def pair[A, B]( p0: A )( p1: B ) = ( p0, p1 )
  def efq( p: Throwable ) = { throw p }

  val prog: ( Int => Unit ) => ( Int => Unit ) => ( Int => Unit ) => ( Int => Int => Unit => Unit ) => ( Int => Int => Sum[Sum[Unit, Unit], Unit] ) => ( Int => Int => Int => ( Unit, Unit ) => Unit ) => ( Int => Int => ( ( Unit, Unit ), Unit ) => ( Unit, Unit ) ) => ( Int => Int => ( Unit => ( Unit, Unit ), ( Unit, Unit ) => Unit ) ) => ( Int => Int => ( Unit => Sum[Unit, Unit], Sum[Unit, Unit] => Unit ) ) => ( Int => Unit ) => Int => ( Int, Unit ) =
    {
      v_86: ( Int => Unit ) =>
        {
          v_84: ( Int => Unit ) =>
            {
              v_78: ( Int => Unit ) =>
                {
                  v_77: ( Int => ( Int => ( Unit => Unit ) ) ) =>
                    {
                      v_75: ( Int => ( Int => Sum[Sum[Unit, Unit], Unit] ) ) =>
                        {
                          v_73: ( Int => ( Int => ( Int => ( ( Unit, Unit ) => Unit ) ) ) ) =>
                            {
                              v_63: ( Int => ( Int => ( ( ( Unit, Unit ), Unit ) => ( Unit, Unit ) ) ) ) =>
                                {
                                  v_66: ( Int => ( Int => ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) ) ) =>
                                    {
                                      v_69: ( Int => ( Int => ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) ) ) =>
                                        {
                                          v_70: ( Int => Unit ) =>
                                            {
                                              v_2: Int =>
                                                ( {
                                                  v_5: Unit =>
                                                    ( {
                                                      v_7: Unit =>
                                                        ( {
                                                          v_85: ( Int => ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) ) =>
                                                            ( {
                                                              v_82: ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) =>
                                                                ( {
                                                                  v_6: Unit =>
                                                                    ( {
                                                                      v_83: ( Int => ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) ) =>
                                                                        ( {
                                                                          v_80: ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) =>
                                                                            ( {
                                                                              v_9: ( Sum[Unit, Unit] => Unit ) =>
                                                                                ( {
                                                                                  v_81: ( Unit => Sum[Unit, Unit] ) =>
                                                                                    ( {
                                                                                      v_2: ( ( Unit, Unit ) => Unit ) =>
                                                                                        ( {
                                                                                          v_79: ( Unit => ( Unit, Unit ) ) =>
                                                                                            ( {
                                                                                              v_0: ( Int => ( Int, Unit ) ) =>
                                                                                                ( {
                                                                                                  v: ( Int, Unit ) => v
                                                                                                } )( ( v_0 )( v_2 ) )
                                                                                            } )( {
                                                                                              x: Int =>
                                                                                                ( ( ( natRec[( Int, Unit )] )( ( ( pair[Int, Unit] )( 0 ) )( ( {
                                                                                                  v_1: Unit => v_1
                                                                                                } )( ( v_2 )( ( ( pair[Unit, Unit] )( ( {
                                                                                                  v_4: Unit =>
                                                                                                    ( {
                                                                                                      v_3: Unit => v_3
                                                                                                    } )( ( ( subst )( v_4 ) )( v_5 ) )
                                                                                                } )( ( ( subst )( v_6 ) )( v_7 ) ) ) )( ( {
                                                                                                  v_8: Unit =>
                                                                                                    ( {
                                                                                                      v_4: Unit => ( ( subst )( v_4 ) )( v_8 )
                                                                                                    } )( ( ( subst )( v_6 ) )( v_7 ) )
                                                                                                } )( ( v_9 )( ( inl[Unit, Unit] )() ) ) ) ) ) ) ) )( {
                                                                                                  v_0: Int =>
                                                                                                    {
                                                                                                      v_10: ( Int, Unit ) =>
                                                                                                        ( {
                                                                                                          v_21: Unit =>
                                                                                                            ( {
                                                                                                              v_76: ( Int => ( Unit => Unit ) ) =>
                                                                                                                ( {
                                                                                                                  v_23: ( Unit => Unit ) =>
                                                                                                                    ( {
                                                                                                                      v_74: ( Int => Sum[Sum[Unit, Unit], Unit] ) =>
                                                                                                                        ( {
                                                                                                                          v_42: Sum[Sum[Unit, Unit], Unit] =>
                                                                                                                            ( {
                                                                                                                              v_72: ( Int => ( Int => ( ( Unit, Unit ) => Unit ) ) ) =>
                                                                                                                                ( {
                                                                                                                                  v_71: ( Int => ( ( Unit, Unit ) => Unit ) ) =>
                                                                                                                                    ( {
                                                                                                                                      v_19: ( ( Unit, Unit ) => Unit ) =>
                                                                                                                                        ( {
                                                                                                                                          v_17: Unit =>
                                                                                                                                            ( {
                                                                                                                                              v_20: Unit =>
                                                                                                                                                ( {
                                                                                                                                                  v_67: ( Int => ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) ) =>
                                                                                                                                                    ( {
                                                                                                                                                      v_68: ( Int => ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) ) =>
                                                                                                                                                        ( {
                                                                                                                                                          v_61: ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) =>
                                                                                                                                                            ( {
                                                                                                                                                              v_59: ( ( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit ) ) =>
                                                                                                                                                                ( {
                                                                                                                                                                  v_64: ( Int => ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) ) =>
                                                                                                                                                                    ( {
                                                                                                                                                                      v_65: ( Int => ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) ) =>
                                                                                                                                                                        ( {
                                                                                                                                                                          v_57: ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) =>
                                                                                                                                                                            ( {
                                                                                                                                                                              v_55: ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) =>
                                                                                                                                                                                ( {
                                                                                                                                                                                  v_53: ( ( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit ) ) =>
                                                                                                                                                                                    ( {
                                                                                                                                                                                      v_62: ( Int => ( ( ( Unit, Unit ), Unit ) => ( Unit, Unit ) ) ) =>
                                                                                                                                                                                        ( {
                                                                                                                                                                                          v_41: ( ( ( Unit, Unit ), Unit ) => ( Unit, Unit ) ) =>
                                                                                                                                                                                            ( ( ( bar2 )( {
                                                                                                                                                                                              y: Int => ( ( f )( ( s )( v_0 ) ) )( y )
                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                              v_11: ( Int, Unit ) => v_11
                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                              v_13: ( ( Int, Unit ) => Exception ) =>
                                                                                                                                                                                                ( ( pair[Int, Unit] )( ( pi1[Int, Unit] )( v_10 ) ) )( ( ( bar )( {
                                                                                                                                                                                                  v_12: Unit => v_12
                                                                                                                                                                                                } ) )( {
                                                                                                                                                                                                  v_30: ( Unit => Exception ) =>
                                                                                                                                                                                                    ( efq )( ( v_13 )( ( ( pair[Int, Unit] )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )( ( {
                                                                                                                                                                                                      v_37: ( Sum[Unit, Unit] => Unit ) =>
                                                                                                                                                                                                        ( {
                                                                                                                                                                                                          v_60: ( Unit => Sum[Unit, Unit] ) =>
                                                                                                                                                                                                            ( {
                                                                                                                                                                                                              v_50: ( Sum[Unit, Unit] => Unit ) =>
                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                  v_58: ( Unit => Sum[Unit, Unit] ) =>
                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                      v_56: ( ( Unit, Unit ) => Unit ) =>
                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                          v_27: ( Unit => ( Unit, Unit ) ) =>
                                                                                                                                                                                                                            ( {
                                                                                                                                                                                                                              v_31: ( ( Unit, Unit ) => Unit ) =>
                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                  v_54: ( Unit => ( Unit, Unit ) ) =>
                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                      v_15: ( ( Unit, Unit ) => Unit ) =>
                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                          v_52: ( Unit => ( Unit, Unit ) ) =>
                                                                                                                                                                                                                                            ( {
                                                                                                                                                                                                                                              v_14: Unit => v_14
                                                                                                                                                                                                                                            } )( ( v_15 )( ( ( pair[Unit, Unit] )( ( {
                                                                                                                                                                                                                                              v_26: ( Unit, Unit ) =>
                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                  v_25: Unit =>
                                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                                      v_24: Unit =>
                                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                                          v_18: Unit =>
                                                                                                                                                                                                                                                            ( {
                                                                                                                                                                                                                                                              v_16: Unit => v_16
                                                                                                                                                                                                                                                            } )( ( ( subst )( v_17 ) )( v_18 ) )
                                                                                                                                                                                                                                                        } )( ( v_19 )( ( ( pair[Unit, Unit] )( ( ( subst )( v_20 ) )( ( ( subst )( v_17 ) )( v_21 ) ) ) )( ( {
                                                                                                                                                                                                                                                          v_22: Unit => v_22
                                                                                                                                                                                                                                                        } )( ( v_23 )( ( ( subst )( v_20 ) )( v_24 ) ) ) ) ) )
                                                                                                                                                                                                                                                    } )( ( pi1[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                                } )( ( pi2[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                            } )( ( v_27 )( ( pi2[Int, Unit] )( v_10 ) ) ) ) )( ( ( bar )( {
                                                                                                                                                                                                                                              v_29: Unit => v_29
                                                                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                                                                              v_33: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                ( efq )( ( v_30 )( ( {
                                                                                                                                                                                                                                                  v_12: Unit => v_12
                                                                                                                                                                                                                                                } )( ( v_31 )( ( ( bar )( {
                                                                                                                                                                                                                                                  v_32: ( Unit, Unit ) => v_32
                                                                                                                                                                                                                                                } ) )( {
                                                                                                                                                                                                                                                  v_34: ( ( Unit, Unit ) => Exception ) =>
                                                                                                                                                                                                                                                    ( efq )( ( v_33 )( ( ( bar )( {
                                                                                                                                                                                                                                                      v_29: Unit => v_29
                                                                                                                                                                                                                                                    } ) )( {
                                                                                                                                                                                                                                                      v_33: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                        ( ( bar )( {
                                                                                                                                                                                                                                                          v_29: Unit => v_29
                                                                                                                                                                                                                                                        } ) )( {
                                                                                                                                                                                                                                                          v_33: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                            ( efq )( ( v_34 )( ( ( pair[Unit, Unit] )( ( {
                                                                                                                                                                                                                                                              v_26: ( Unit, Unit ) =>
                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                  v_25: Unit =>
                                                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                                                      v_24: Unit =>
                                                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                                                          v_48: Unit =>
                                                                                                                                                                                                                                                                            ( ( bar )( {
                                                                                                                                                                                                                                                                              v_35: Unit => v_35
                                                                                                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                                                                                                              v_39: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                ( efq )( ( v_33 )( ( ( bar )( {
                                                                                                                                                                                                                                                                                  v_29: Unit => v_29
                                                                                                                                                                                                                                                                                } ) )( {
                                                                                                                                                                                                                                                                                  v_33: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                                                                      v_36: Unit =>
                                                                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                                                                          v_29: Unit => v_29
                                                                                                                                                                                                                                                                                        } )( ( ( subst )( v_20 ) )( v_36 ) )
                                                                                                                                                                                                                                                                                    } )( ( v_37 )( ( inr[Unit, Unit] )( ( ( bar )( {
                                                                                                                                                                                                                                                                                      v_38: Unit => v_38
                                                                                                                                                                                                                                                                                    } ) )( {
                                                                                                                                                                                                                                                                                      v_44: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                        ( efq )( ( v_39 )( ( {
                                                                                                                                                                                                                                                                                          v_32: ( Unit, Unit ) =>
                                                                                                                                                                                                                                                                                            ( {
                                                                                                                                                                                                                                                                                              v_40: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_35: Unit => v_35
                                                                                                                                                                                                                                                                                                } )( ( pi1[Unit, Unit] )( v_32 ) )
                                                                                                                                                                                                                                                                                            } )( ( pi2[Unit, Unit] )( v_32 ) )
                                                                                                                                                                                                                                                                                        } )( ( v_41 )( ( ( pair[( Unit, Unit ), Unit] )( ( ( pair[Unit, Unit] )( ( ( ( matchSum )( v_42 ) )( {
                                                                                                                                                                                                                                                                                          v_43: Sum[Unit, Unit] =>
                                                                                                                                                                                                                                                                                            ( ( ( matchSum )( v_43 ) )( {
                                                                                                                                                                                                                                                                                              v_38: Unit => ( efq )( ( v_44 )( v_38 ) )
                                                                                                                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                                                                                                                              v_45: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_35: Unit => v_35
                                                                                                                                                                                                                                                                                                } )( ( ( subst )( v_20 ) )( v_45 ) )
                                                                                                                                                                                                                                                                                            } )
                                                                                                                                                                                                                                                                                        } ) )( {
                                                                                                                                                                                                                                                                                          v_49: Unit =>
                                                                                                                                                                                                                                                                                            ( efq )( ( v_33 )( ( {
                                                                                                                                                                                                                                                                                              v_46: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_47: Unit => ( ( subst )( v_46 ) )( v_47 )
                                                                                                                                                                                                                                                                                                } )( ( ( subst )( v_46 ) )( v_48 ) )
                                                                                                                                                                                                                                                                                            } )( ( ( subst )( v_49 ) )( v_20 ) ) ) )
                                                                                                                                                                                                                                                                                        } ) ) )( v_24 ) ) )( v_25 ) ) ) ) )
                                                                                                                                                                                                                                                                                    } ) ) ) )
                                                                                                                                                                                                                                                                                } ) ) )
                                                                                                                                                                                                                                                                            } )
                                                                                                                                                                                                                                                                        } )( ( v_50 )( ( inl[Unit, Unit] )() ) )
                                                                                                                                                                                                                                                                    } )( ( pi1[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                                                } )( ( pi2[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                                            } )( ( v_27 )( ( pi2[Int, Unit] )( v_10 ) ) ) ) )( ( {
                                                                                                                                                                                                                                                              v_26: ( Unit, Unit ) =>
                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                  v_25: Unit =>
                                                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                                                      v_24: Unit =>
                                                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                                                          v_48: Unit =>
                                                                                                                                                                                                                                                                            ( ( bar )( {
                                                                                                                                                                                                                                                                              v_40: Unit => v_40
                                                                                                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                                                                                                              v_51: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                ( efq )( ( v_33 )( ( ( bar )( {
                                                                                                                                                                                                                                                                                  v_29: Unit => v_29
                                                                                                                                                                                                                                                                                } ) )( {
                                                                                                                                                                                                                                                                                  v_33: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                    ( {
                                                                                                                                                                                                                                                                                      v_36: Unit =>
                                                                                                                                                                                                                                                                                        ( {
                                                                                                                                                                                                                                                                                          v_29: Unit => v_29
                                                                                                                                                                                                                                                                                        } )( ( ( subst )( v_20 ) )( v_36 ) )
                                                                                                                                                                                                                                                                                    } )( ( v_37 )( ( inr[Unit, Unit] )( ( ( bar )( {
                                                                                                                                                                                                                                                                                      v_38: Unit => v_38
                                                                                                                                                                                                                                                                                    } ) )( {
                                                                                                                                                                                                                                                                                      v_44: ( Unit => Exception ) =>
                                                                                                                                                                                                                                                                                        ( efq )( ( v_51 )( ( {
                                                                                                                                                                                                                                                                                          v_32: ( Unit, Unit ) =>
                                                                                                                                                                                                                                                                                            ( {
                                                                                                                                                                                                                                                                                              v_40: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_35: Unit => v_40
                                                                                                                                                                                                                                                                                                } )( ( pi1[Unit, Unit] )( v_32 ) )
                                                                                                                                                                                                                                                                                            } )( ( pi2[Unit, Unit] )( v_32 ) )
                                                                                                                                                                                                                                                                                        } )( ( v_41 )( ( ( pair[( Unit, Unit ), Unit] )( ( ( pair[Unit, Unit] )( ( ( ( matchSum )( v_42 ) )( {
                                                                                                                                                                                                                                                                                          v_43: Sum[Unit, Unit] =>
                                                                                                                                                                                                                                                                                            ( ( ( matchSum )( v_43 ) )( {
                                                                                                                                                                                                                                                                                              v_38: Unit => ( efq )( ( v_44 )( v_38 ) )
                                                                                                                                                                                                                                                                                            } ) )( {
                                                                                                                                                                                                                                                                                              v_45: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_35: Unit => v_35
                                                                                                                                                                                                                                                                                                } )( ( ( subst )( v_20 ) )( v_45 ) )
                                                                                                                                                                                                                                                                                            } )
                                                                                                                                                                                                                                                                                        } ) )( {
                                                                                                                                                                                                                                                                                          v_49: Unit =>
                                                                                                                                                                                                                                                                                            ( efq )( ( v_33 )( ( {
                                                                                                                                                                                                                                                                                              v_46: Unit =>
                                                                                                                                                                                                                                                                                                ( {
                                                                                                                                                                                                                                                                                                  v_47: Unit => ( ( subst )( v_46 ) )( v_47 )
                                                                                                                                                                                                                                                                                                } )( ( ( subst )( v_46 ) )( v_48 ) )
                                                                                                                                                                                                                                                                                            } )( ( ( subst )( v_49 ) )( v_20 ) ) ) )
                                                                                                                                                                                                                                                                                        } ) ) )( v_24 ) ) )( v_25 ) ) ) ) )
                                                                                                                                                                                                                                                                                    } ) ) ) )
                                                                                                                                                                                                                                                                                } ) ) )
                                                                                                                                                                                                                                                                            } )
                                                                                                                                                                                                                                                                        } )( ( v_50 )( ( inl[Unit, Unit] )() ) )
                                                                                                                                                                                                                                                                    } )( ( pi1[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                                                } )( ( pi2[Unit, Unit] )( v_26 ) )
                                                                                                                                                                                                                                                            } )( ( v_27 )( ( pi2[Int, Unit] )( v_10 ) ) ) ) ) )
                                                                                                                                                                                                                                                        } )
                                                                                                                                                                                                                                                    } ) ) )
                                                                                                                                                                                                                                                } ) ) ) ) )
                                                                                                                                                                                                                                            } ) ) ) )
                                                                                                                                                                                                                                        } )( ( pi1[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_53 ) )
                                                                                                                                                                                                                                    } )( ( pi2[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_53 ) )
                                                                                                                                                                                                                                } )( ( pi1[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_55 ) )
                                                                                                                                                                                                                            } )( ( pi2[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_55 ) )
                                                                                                                                                                                                                        } )( ( pi1[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_57 ) )
                                                                                                                                                                                                                    } )( ( pi2[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_57 ) )
                                                                                                                                                                                                                } )( ( pi1[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_59 ) )
                                                                                                                                                                                                            } )( ( pi2[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_59 ) )
                                                                                                                                                                                                        } )( ( pi1[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_61 ) )
                                                                                                                                                                                                    } )( ( pi2[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_61 ) ) ) ) )
                                                                                                                                                                                                } ) )
                                                                                                                                                                                            } )
                                                                                                                                                                                        } )( ( v_62 )( v_0 ) )
                                                                                                                                                                                    } )( ( v_63 )( ( pi1[Int, Unit] )( v_10 ) ) )
                                                                                                                                                                                } )( ( v_64 )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )
                                                                                                                                                                            } )( ( v_64 )( ( pi1[Int, Unit] )( v_10 ) ) )
                                                                                                                                                                        } )( ( v_65 )( ( pi1[Int, Unit] )( v_10 ) ) )
                                                                                                                                                                    } )( ( v_66 )( v_0 ) )
                                                                                                                                                                } )( ( v_66 )( ( s )( v_0 ) ) )
                                                                                                                                                            } )( ( v_67 )( ( s )( v_0 ) ) )
                                                                                                                                                        } )( ( v_68 )( ( s )( v_0 ) ) )
                                                                                                                                                    } )( ( v_69 )( ( ( mul )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) )
                                                                                                                                                } )( ( v_69 )( ( s )( v_0 ) ) )
                                                                                                                                            } )( ( v_70 )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )
                                                                                                                                        } )( ( v_70 )( ( s )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) )
                                                                                                                                    } )( ( v_71 )( ( ( mul )( ( s )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) )( ( s )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) ) )
                                                                                                                                } )( ( v_72 )( ( s )( ( ( mul )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) ) )
                                                                                                                            } )( ( v_73 )( ( s )( v_0 ) ) )
                                                                                                                        } )( ( v_74 )( ( ( mul )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) )
                                                                                                                    } )( ( v_75 )( ( s )( v_0 ) ) )
                                                                                                                } )( ( v_76 )( ( ( mul )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) )( ( s )( ( pi1[Int, Unit] )( v_10 ) ) ) ) )
                                                                                                            } )( ( v_77 )( v_0 ) )
                                                                                                        } )( ( v_78 )( ( pi1[Int, Unit] )( v_10 ) ) )
                                                                                                    }
                                                                                                } ) )( x )
                                                                                            } )
                                                                                        } )( ( pi1[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_80 ) )
                                                                                    } )( ( pi2[( Unit => ( Unit, Unit ) ), ( ( Unit, Unit ) => Unit )] )( v_80 ) )
                                                                                } )( ( pi1[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_82 ) )
                                                                            } )( ( pi2[( Unit => Sum[Unit, Unit] ), ( Sum[Unit, Unit] => Unit )] )( v_82 ) )
                                                                        } )( ( v_83 )( 0 ) )
                                                                    } )( ( v_66 )( 0 ) )
                                                                } )( ( v_84 )( 0 ) )
                                                            } )( ( v_85 )( 0 ) )
                                                        } )( ( v_69 )( 0 ) )
                                                    } )( ( v_70 )( 0 ) )
                                                } )( ( v_86 )( 0 ) )
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

  val arg1 = { x: Int => () }
  val arg2 = { x: Int => () }
  val arg3 = { x: Int => () }
  val arg4 = { x: Int => { y: Int => { z: Unit => () } } }
  val arg5 = { x: Int => { y: Int => inr[Sum[Unit, Unit], Unit]( () ) } }
  val arg6 = { x: Int => { y: Int => { z: Int => { foo: ( Unit, Unit ) => () } } } }
  val arg7 = { x: Int => { y: Int => { z: Int => { foo: ( ( Unit, Unit ), Unit ) => ( (), () ) } } } }
  val arg8 = { x: Int => { y: Int => ( { z: Unit => ( (), () ) }, { foo: ( Unit, Unit ) => () } ) } }
  val arg9 = { x: Int => { y: Int => ( { z: Unit => inr[Unit, Unit]( () ) }, { foo: Sum[Unit, Unit] => () } ) } }
  val arg10 = { x: Int => () }
  val p2 = prog( arg1 )( arg2 )( arg3 )( arg4 )( arg5 ) //(arg6)
  val p3 = p2( arg6 )
  val p4 = p3( arg7 )
  val p5 = p4( arg8 )
  val p6 = p5( arg9 )
  val p7 = p6( arg10 )
  println( s"res: ${pi1( p7( 4 ) )}" )
}
mschlaipfer commented 6 years ago

I wrote a code generator for F# and fsharpc on the "equivalent" F# program terminates within less than a second (with a type error as of now), so I think this is a valid Scala issue.

SethTisue commented 1 year ago

I wonder if Scala 3 does any better here.

som-snytt commented 1 year ago

Dotty errors immediately by cheating.

➜  ~/projects/dotty/bin/scalac -d /tmp t10964.scala
-- Error: t10964.scala:48:18 -------------------------------------------------------------------------------------------
48 |      v_86: ( Int => Unit ) =>
   |              ^^^^^^^^^^^
   |              not a legal formal parameter for a function literal
***
parentheses are required around the parameter of a lambda