StackOverflowError in RCFLAEInterp

Moderator: Konzepte der Programmiersprachen

tud_std
Erstie
Erstie
Beiträge: 19
Registriert: 13. Apr 2016 16:29

StackOverflowError in RCFLAEInterp

Beitrag von tud_std » 25. Nov 2018 21:02

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.
Zuletzt geändert von tud_std am 26. Nov 2018 00:54, insgesamt 3-mal geändert.

0b101101101
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 179
Registriert: 15. Apr 2015 18:24

Re: StackOverflowError in RCFLAEInterp

Beitrag von 0b101101101 » 25. Nov 2018 21:40

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
Erstie
Erstie
Beiträge: 19
Registriert: 13. Apr 2016 16:29

Re: StackOverflowError in RCFLAEInterp

Beitrag von tud_std » 25. Nov 2018 22:05

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
Moderator
Moderator
Beiträge: 79
Registriert: 16. Okt 2017 12:28

Re: StackOverflowError in RCFLAEInterp

Beitrag von mirko-koehler » 27. Nov 2018 16:56

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
Erstie
Erstie
Beiträge: 19
Registriert: 13. Apr 2016 16:29

Re: StackOverflowError in RCFLAEInterp

Beitrag von tud_std » 28. Nov 2018 02:03

Thank you for your reply. I got it now.

Antworten

Zurück zu „Konzepte der Programmiersprachen“