Tail Call Optimization

TheAdriCoolManDude

TheAspiringHacker wrote:
See my edit with the example.

It's just even more confusing. Maybe I should come back when I am done with Javascript lessons (which is probably never)

DownsGameClub

So it's a way of efficiently storing variables by “reusing” previous result or function in a series, such as:

?
In other words, I want to solve this equation on a graphing calculator:

3*2*5*1*4*9

The answer is 1080, but there are multiple ways to get to this answer according to what you're suggesting:

Without tail call optimization, variables would calculate this equation where you continuously put new numbers at the end of each equation like this:

With tail call optimization, a calculator essentially calls the last answer that was calculated to be placed in the equation, similar to what I think tail call optimization does:

Is this correct?

(edit - clearer screenshot images)

Last edited by DownsGameClub (Sept. 27, 2018 01:00:28)

Paddle2See

This topic seems to be generating a fair number of contentious posts, mostly because of the framing of the suggestion.

To the OP - I suggest that, at a minimum, you spell out the benefits and costs of your suggestion, from the point of view of the user. Do you anticipate a performance increase? Are there certain algorithms that you can not currently perform that you think might be within reach of Scratch if TCO were implemented? Are they algorithms that a beginning programmer would be likely to use?

To be clear, I have no idea if TCO is currently implemented in Scratch or not. And if it isn't, what it would take to make it happen. But without some understanding of the expected benefits, I have no reasons to forward the suggestion to the developers for consideration.

Last edited by Paddle2See (Sept. 27, 2018 00:58:46)

TheAspiringHacker

@DownsGameClub. No, TCO isn't about reusing results. That's just storing something in a variable or register, another optimization that a compiler may make (as well as something programmers write themselves).

TCO is about reusing stack space for a function call at the end of a function definition.

Let's say that you have this code:

int foo(int x)
{
    return x - 4;
}
 
int bar(int x)
{
    return foo(x * 2);
}
 
int main()
{
    return bar(2);
}

Let “main” be the function that is called at the program start. Let's walk through the evaluation without TCO:

The main function calls the bar function with the argument 2. The computer pushes a new frame onto the stack to store the argument 2 and jumps to the code for bar. The bar code retrieves the argument in its stack frame (AKA 2), multiplies it by 2, and calls the foo function with the result, 4, as the argument, pushing a new frame onto the stack to store 4 before jumping to the code for foo. The foo function subtracts 4 from its argument on the stack, 4, to get 0. Then, it returns the result and pops its frame off the stack. Now, the top frame is the frame for the call to bar. The bar function retrieves the returned 0 and returns it, popping its frame off the stack. Now, the frame for the starting main function is at the top of the stack. The main function retrieves the return value of bar, 0, returns it, and pops its frame, the last frame, off the stack.

Now, let's walk through the evaluation with TCO:

The main function jumps to the bar function, reusing its own stack frame for the argument to bar, 2. Bar multiplies its argument, 2, by 2, getting 4. Then, bar reuses its stack frame for the call to foo, storing the argument 4 and jumping to foo's code. The foo function subtracts 4 from its agrument, 4, getting 0. Then, 0 is returned as the result of the entire program. Only a single call frame was necessary!

Last edited by TheAspiringHacker (Sept. 27, 2018 01:31:49)

badatprogrammingibe

Paddle2See wrote:
This topic seems to be generating a fair number of contentious posts, mostly because of the framing of the suggestion.

To the OP - I suggest that, at a minimum, you spell out the benefits and costs of your suggestion, from the point of view of the user. Do you anticipate a performance increase? Are there certain algorithms that you can not currently perform that you think might be within reach of Scratch if TCO were implemented? Are they algorithms that a beginning programmer would be likely to use?

To be clear, I have no idea if TCO is currently implemented in Scratch or not. And if it isn't, what it would take to make it happen. But without some understanding of the expected benefits, I have no reasons to forward the suggestion to the developers for consideration.

Benefits:
Recursive procedures no longer take up large amount of memory, meaning they are more feasible to use.

Costs:
None, it is just an optimization.

Algorithms that you can not currently perform:
Sometimes, you want a procedures to remain mostly pure (without side-effects), for various reasons, for example if you want a procedures to be able to be run multiple times concurrently.
Currently, when you run (mostly, truly pure procedures currently aren't possible with scratch) pure procedures, a lot of memory is taken up, so they are not feasible, so you are forced to use non-pure procedures for optimization reasons.
TCO fixes this.

badatprogrammingibe

BUMP
U
M
P

Zatnik

FWIW, here's my attempt at an explanation in terms of Scratch code:

EDIT: I should probably clarify that the examples in this post are very minimal and aren't the main things that tail call optimization would be useful for. Also, tail call optimization is something that's built into the language – it's not something that Scratchers would have to pay attention to or understand, because it would happen completely automatically. Anyway….

Say you have some scripts like this. (Though it doesn't really matter what the specific blocks are.)

When the computer runs the custom block “whatever” inside the custom block “move around”, it has to remember that when “whatever” finishes running, it should go back to “move around” and run the “turn 15 degrees” block.

What if “whatever” was at the end of “move around”, though?

In this case, “whatever” is a tail call, because it's the last thing that's done in the custom block. Since it's at the end, there isn't anything left to do in “move around” when “whatever” finishes running. Because of that, the computer doesn't really need to remember to go back to “move around” - it could just forget about “move around” and instead go straight back to the “wait 1 secs” block in the main script.

Many programming languages, though, including Scratch apparently, always remember to go back to “move around”, even if there's nothing left to do in it.

Tail call optimization is when a programming language tells the computer that if there's a custom block like “move around” in the last example, with a tail call like “whatever”, it should forget about going back to “move around” after running “whatever” and instead just remember to go back to the main script. Tail call optimization can be useful because there's a limit to how much a computer can remember, so it's nice for it to not waste memory on remembering to go back to custom blocks that it doesn't need to go back to.

Last edited by Zatnik (Sept. 30, 2018 20:54:09)

Za-Chary

Zatnik wrote:
FWIW, here's my attempt at an explanation in terms of Scratch code:

Thank you, @Zatnik, for explaining this.

However, I'd probably say no support, because you can easily move the “whatever” block to the end of the script.

badatprogrammingibe

Za-Chary wrote:
Zatnik wrote:
FWIW, here's my attempt at an explanation in terms of Scratch code:
Thank you, @Zatnik, for explaining this.

However, I'd probably say no support, because you can easily move the “whatever” block to the end of the script.

Tail-call optimization only helps if the “whatever” block is at the end of the script.
Tail-call optimization doesn't change projects, what it does is makes them run more efficiently.

TheAdriCoolManDude

Zatnik wrote:
-snip-

Thank you.

Anyways, No Support, just do this:

TheAspiringHacker

Nevermind, misunderstood the above no-support reasons

Last edited by TheAspiringHacker (Sept. 29, 2018 03:23:33)

Zatnik

TheAdriCoolManDude wrote:
Zatnik wrote:
-snip-
Thank you.

Anyways, No Support, just do this:

That does work for that specific example, but there are other cases where it would be harder to do something like that. Tail call optimization would be particularly useful for recursive custom blocks, i.e. ones that contain themselves, like this:

For that, you can't just move the tail call outside of the custom block, because for the block to work properly, it has to run inside itself running inside itself running inside itself, etc, whereas if you moved it outside of itself it would only run once.

Now, again, for this particular example, there's an easy solution that doesn't involve tail calls (specifically, you could just use the repeat block to make it run the right number of times), but for more complicated scripts, it can sometimes be more convenient to use tail calls than to use other techniques, and when that's the case, it would be helpful for Scratch to have tail call optimization so that you could make the scripts in the more convenient way without worrying about filling up too much of the computer's memory.

Last edited by Zatnik (Sept. 29, 2018 02:51:39)

PrincessFlowerTV

OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!

Anyways, thank you Zatnik for explaining this. I get the basic concept, I guess.

No support.

TheAdriCoolManDude wrote:
…No Support, just do this:

Simple as that.

Last edited by PrincessFlowerTV (Sept. 29, 2018 15:27:21)

TheAspiringHacker

*Sigh* I see why badatprogrammingibe told people who don't know what TCO is not to reply. Even after Zatnik explained TCO and people think that they understand, they're still missing the point…

The purpose of functions is logical code organization and reuse. Cutting off the last function call in the definition and manually inlining it at all call sites ruins the whole point of the function abstraction…

badatprogrammingibe

PrincessFlowerTV wrote:
OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!

I don't really care whether people support my suggestion, I would just like it to be implemented.

TheAdriCoolManDude

badatprogrammingibe wrote:
PrincessFlowerTV wrote:
OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!
I don't really care whether people support my suggestion, I would just like it to be implemented.

Acting like that won't get it implemented.

adsuri

badatprogrammingibe wrote:
BUMP
U
M
P

Ooh, nice.

badatprogrammingibe

TheAdriCoolManDude wrote:
badatprogrammingibe wrote:
PrincessFlowerTV wrote:
OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!
I don't really care whether people support my suggestion, I would just like it to be implemented.
Acting like that won't get it implemented.

The amount of people “supporting” the suggestion is pretty much irrelevant to whether the suggestion is implemented.
Acting like this won't get it implemented, but not acting like this won't either.

Last edited by badatprogrammingibe (Sept. 30, 2018 01:40:48)

TheAdriCoolManDude

badatprogrammingibe wrote:
TheAdriCoolManDude wrote:
badatprogrammingibe wrote:
PrincessFlowerTV wrote:
OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!
I don't really care whether people support my suggestion, I would just like it to be implemented.
Acting like that won't get it implemented.
The amount of people “supporting” the suggestion is pretty much irrelevant to whether the suggestion is implemented.

I am talking about your attitude. Your saying it like “implement this, even if no one understands it!”

badatprogrammingibe

TheAdriCoolManDude wrote:
badatprogrammingibe wrote:
TheAdriCoolManDude wrote:
badatprogrammingibe wrote:
PrincessFlowerTV wrote:
OP, If you want people to support your suggestion, you should explain it, otherwise… No one will know what you are suggesting!
I don't really care whether people support my suggestion, I would just like it to be implemented.
Acting like that won't get it implemented.
The amount of people “supporting” the suggestion is pretty much irrelevant to whether the suggestion is implemented.
I am talking about your attitude. Your saying it like “implement this, even if no one understands it!”

Whether they understand it or not is irrelevant to its impact, it is just an optimization that makes the scratch VM better handle memory.

Discuss Scratch