StackOverflowError in RCFLAEInterp

[tud_std]

Hi everyone,

In https://repository.st.informatik.tu-dar ... terp.scala the following assertion throws a java.lang.StackOverflowError :

Code: Alles auswählen

assert(interp(
    Rec('fact, Fun('n, If0('n, 1, Mult('n, App('fact, Sub('n, 1))))),
      App('fact, 5))) == NumV(120))

I tried to debug step by step the execution of the given instruction so I tried to add some slight changes to the source code of the case Rec such that :

Code: Alles auswählen

    case Rec(boundId, namedExpr, boundBody) =>
            Console.println("expr: #"+expr+"#")
	    val recEnv = collection.mutable.Map() ++ env
	    Console.println("recEnv.keys before teta: #"+recEnv.keys+"#")
            Console.println("recEnv.valus before teta: #"+recEnv.values+"#")
            val teta = boundId -> interp(namedExpr, recEnv)
            Console.println("teta: #"+teta+"#")
	    recEnv += teta
             Console.println("recEnv.keys after teta: #"+recEnv.keys+"#")
            Console.println("recEnv.values after teta: #"+recEnv.values+"#")
            Console.println("############################")
	    interp(boundBody, recEnv)

The traceout looks like :

Code: Alles auswählen

expr: #Rec('fact,Fun('n,If0(Id('n),Num(1),Mult(Id('n),App(Id('fact),Sub(Id('n),Num(1)))))),App(Id('fact),Num(5)))#
recEnv.keys before teta: #Set()#
recEnv.values before teta: #HashMap()#
teta: #('fact,Closure('n,If0(Id('n),Num(1),Mult(Id('n),App(Id('fact),Sub(Id('n),Num(1))))),Map()))#
recEnv.keys after teta: #Set('fact)#
[info] de.tuda.stg.copl.RecursionTest *** ABORTED ***
[info]   java.lang.StackOverflowError:
[info]   at de.tuda.stg.copl.recursion.RCFLAEInterp$Id.productIterator(RCFLAEInterp.scala:14)
[info]   at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:143)
[info]   at de.tuda.stg.copl.recursion.RCFLAEInterp$Id.toString(RCFLAEInterp.scala:14)
[info]   at java.lang.String.valueOf(String.java:2994)
[info]   at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:199)
[info]   at scala.collection.TraversableOnce.$anonfun$addString$1(TraversableOnce.scala:358)
[info]   at scala.collection.Iterator.foreach(Iterator.scala:937)
[info]   at scala.collection.Iterator.foreach$(Iterator.scala:937)
[info]   at scala.collection.AbstractIterator.foreach(Iterator.scala:1425)
[info]   at scala.collection.TraversableOnce.addString(TraversableOnce.scala:356)
[info]   ...

It seems that error is somehow related to recEnv.values (after adding teta to recEnv). Could someone please explain the cause of this error ? thank you in advance.

Kind regards.

[0b101101101]

Hey, it would be easier if the posts would mention the assignment and task?

But from what you just wrote, as I understand you so far, you got an StackOverflowError, meaning you probably have an endless recursive call. According to the stack trace its happening during some toString methods. If we look at the print-trace we can see, that the "recEnv.keys ..." was the last line printed, and according to the code the "recEnv.values ..." print should be next, but the error occurs before the print.

I guess one explanation for a StackOverflow in a toString call would be that there is a datastructure which contains itself and the toString method would have to create a String like "Map(a -> Map(a -> Map(a -> Map(a -> Map(a -> ...)))))" and so on. Of course one would need infinite stack to print an infinite datastructure so we get an StackOverflow, right?

So I guess, if there is supposed to be an infinite datastructure then maybe one should not try to print it, on the other hand if its not supposed to be infinite, you know what error to look for? Is this of any help?

[tud_std]

Thanks for your reply. I have edited the thread and added a url to the object RCFLAEInterp. Since recEnv was empty (i.e. recEnv before teta), the evaluation of recEnv.values after adding teta to recEnv, should in fact return teta._2 which is the value part of the pair :

Code: Alles auswählen

(key, value) = ('fact,Closure('n,If0(Id('n),Num(1),Mult(Id('n),App(Id('fact),Sub(Id('n),Num(1))))),Map()))

which is nothing other than

Code: Alles auswählen

Closure('n,If0(Id('n),Num(1),Mult(Id('n),App(Id('fact),Sub(Id('n),Num(1))))),Map())

. I still don't see any infinite recursion here or I am missing something?

[mirko-koehler]

The infinite recursion occurs in the println statement printing the recEnv. It should be something like this:

Code: Alles auswählen

Map('fact, Closure(..., Map('fact, Closure( ...))))

[tud_std]

Thank you for your reply. I got it now.