The second part of the question is what I’m interested in and I guess that first part will give me the answer.
So tail-recursive function calls itself as the last operation in one of it’s branches. As a consequence, the memory it was consuming is given to it’s successor. Right?
But if the last operation in a function is a call to some other function the memory will not be freed! Why is this so? Knowing that all the vals you used in previous function are not needed anymore same as in the first case when function called itself!
Thanks!
Tail recursion can be changed to a loop and that’s what Scala compiler does. Tail calls in general require stack frame replacement support from the underlying platform, but Java doesn’t provide that.
1 Like
Why settle for believing people when you can believe the compiler?
scala> :paste
// Entering paste mode (ctrl-D to finish)
def tailRecursiveSum(ints: List[Int], aggregate: Int): Int =
if (ints.isEmpty) aggregate
else {
val tail = ints.tail
val sum = aggregate + ints.head
tailRecursiveSum(tail, sum)
}
// Exiting paste mode, now interpreting.
tailRecursiveSum: (ints: List[Int], aggregate: Int)Int
scala> :javap tailRecursiveSum
Constant pool:
<elided for brevity>
{
public int tailRecursiveSum(scala.collection.immutable.List<java.lang.Object>, int);
descriptor: (Lscala/collection/immutable/List;I)I
flags: ACC_PUBLIC
Code:
stack=2, locals=6, args_size=3
0: aload_1 /* push the list from slot 1 (ints) onto the stack */
1: invokevirtual #27 // Method scala/collection/immutable/List.isEmpty:()Z
4: ifeq 11 /*
7: iload_2 * if List.isEmpty, push aggregate from slot 2 onto the stack and goto return
8: goto 40 */
11: aload_1 /* push the list from slot 1 onto the stack */
12: invokevirtual #31 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
15: checkcast #23 // class scala/collection/immutable/List
18: astore 4 /* store the tail in slot 4 (tail) */
20: iload_2 /* push aggregate from slot 2 onto the stack */
21: aload_1 /* push list from slot 1 onto the stack */
22: invokevirtual #34 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
25: invokestatic #40 // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
28: iadd /* add the head value (from 25) to the stack slot above it (the aggregate from 20), the list was consumed in 22 producing the head value */
29: istore 5 /* store the sum in slot 5 */
31: aload 4 /* push the tail from slot 4 (tail) (stored @ 18) onto the stack */
33: iload 5 /* push the sum in slot 5 (sum) onto the stack */
35: istore_2 /* store sum in slot 2 (aggregate) */
36: astore_1 /* store tail in slot 1 (ints) */
37: goto 0 /* go back to the top. Slot 1 is now tail instead of the first paramter to the method, and
40: ireturn
LocalVariableTable:
Start Length Slot Name Signature
18 22 4 tail Lscala/collection/immutable/List;
29 11 5 sum I
0 41 0 this L$line4/$read$$iw$$iw$;
0 41 1 ints Lscala/collection/immutable/List;
0 41 2 aggregate I
LineNumberTable:
line 12: 0
line 14: 11
line 15: 20
line 16: 31
StackMapTable: number_of_entries = 3
frame_type = 0 /* same */
frame_type = 10 /* same */
frame_type = 92 /* same_locals_1_stack_item */
stack = [ int ]
Signature: #56 // (Lscala/collection/immutable/List<Ljava/lang/Object;>;I)I
MethodParameters:
Name Flags
ints final
aggregate final
The /* comments are added by me to explain what’s going on, and also not aligned properly because the editor here doesn’t use a monospace font.
This optimization hinges on being able to set the state of the method so that it looks like it’s just been called with new parameters, and jumping back to the top, pretending it’s a new call with new parameters.
But you can’t just goto into a different method, so this trick doesn’t work when making a cross method call.
1 Like