Tail Call Optimization

badatprogrammingibe

Is it too much to ask for?
If you don't know what Tail Call Optimization is, please learn what it is before you post on this topic.

Here are some explanations you can use to help you learn what it is:
https://scratch-mit-edu.ezproxyberklee.flo.org/discuss/post/3263409/
https://scratch-mit-edu.ezproxyberklee.flo.org/discuss/post/3264561/

Last edited by badatprogrammingibe (Oct. 1, 2018 06:00:34)

TheAdriCoolManDude

How does that suppose to get implemented in Scratch? Also, you should probably explain what the heck that is before making a suggestion.

DaEpikDude

*looks up what tail call optimisation is*

Eh… it might be useful if you are making super complicated / intensive programs or whatever but I'm not entirely sure if that sort of stuff is really necessary for Scratch? It's not really intended to be a super efficient high-power language or anything anyway?

(There's probably like a good 65% chance that I'm misunderstanding what you're talking about considering my information on the subject was based on just searching up “tail call optimisation” but y'know)

badatprogrammingibe

DaEpikDude wrote:
*looks up what tail call optimisation is*

Eh… it might be useful if you are making super complicated / intensive programs or whatever but I'm not entirely sure if that sort of stuff is really necessary for Scratch? It's not really intended to be a super efficient high-power language or anything anyway?

(There's probably like a good 65% chance that I'm misunderstanding what you're talking about considering my information on the subject was based on just searching up “tail call optimisation” but y'know)

It's not necessary, but it doesn't hurt to have tail call optimization, as all it does is making a project use up less RAM when running recursive procedures.

TheAdriCoolManDude wrote:
How does that suppose to get implemented in Scratch? Also, you should probably explain what the <removed bad word> that is before making a suggestion.

badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.

Also, please do not swear.

Last edited by badatprogrammingibe (Sept. 26, 2018 02:38:11)

ShinigamiBlacky

badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.

You yourself are not really helping the discussion by not explaining what da heck youre talking about

braxbroscratcher

badatprogrammingibe wrote:
DaEpikDude wrote:
*looks up what tail call optimisation is*

Eh… it might be useful if you are making super complicated / intensive programs or whatever but I'm not entirely sure if that sort of stuff is really necessary for Scratch? It's not really intended to be a super efficient high-power language or anything anyway?

(There's probably like a good 65% chance that I'm misunderstanding what you're talking about considering my information on the subject was based on just searching up “tail call optimisation” but y'know)
It's not necessary, but it doesn't hurt to have tail call optimization, as all it does is making a project use up less RAM when running recursive procedures.

TheAdriCoolManDude wrote:
How does that suppose to get implemented in Scratch? Also, you should probably explain what the <removed bad word> that is before making a suggestion.
badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.
Also, please do not swear.

'heck' isn't a swear. Go back to kindergarten with that junk. You should explain the suggestion in full no matter what. You're not being constructive at all.

space_elephant

No support, you probably shouldn't be using recursion for this and scratch is so slow that nothing can make it even slower.
Also write you suggestion on the OP
I wish I could post without bumping this

rdococ

Full support. It wouldn't be too difficult to implement, New Scratchers probably wouldn't even notice, and tail call recursion can be useful to remove otherwise unnecessary variables or even simply for students to learn about recursion without as much of a risk of crashing Scratch or causing an error. It fits completely with the principle of “low floor, high ceiling”.

I've never been able to get a stack overflow in Scratch, to be honest - it might already have tail call optimization.

Last edited by rdococ (Sept. 26, 2018 18:39:49)

TheAdriCoolManDude

badatprogrammingibe wrote:
TheAdriCoolManDude wrote:
How does that suppose to get implemented in Scratch? Also, you should probably explain what the <removed bad word> that is before making a suggestion.
Also, please do not swear.

Are you kidding me! How the heck is heck a bad word?

badatprogrammingibe wrote:
Is it too much to ask for?
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.

Let me check again…
Okay, never mind. But I don't understand it. How does it work?

DownsGameClub

Stop being lazy and tell us what it means already. Unless someone's really good at programming and algorithms, or is in AP Computer Science a regular person is not going to be able to understand.
You're the one facilitating the discussion and should be prepared in explaining in everyday words what a tail call is. If you can't explain your suggestion and its benefits, let someone else make the suggestion instead.

Lucky for you, I looked at several articles, and I'm still having trouble understanding what it is. It seems to be an optimization of memory of some sort, correct?

And please, if you're not the OP, do not respond to my prompt. I'm a bit disappointed at the effort put into this suggestion and I'd like to see if the OP knows that they're talking about so I know whether or not to support the argument.

TheAspiringHacker

DownsGameClub wrote:
Stop being lazy and tell us what it means already. Unless someone's really good at programming and algorithms, or is in AP Computer Science a regular person is not going to be able to understand.
You're the one facilitating the discussion and should be prepared in explaining in everyday words what a tail call is. If you can't explain your suggestion and its benefits, let someone else make the suggestion instead.

Lucky for you, I looked at several articles, and I'm still having trouble understanding what it is. It seems to be an optimization of memory of some sort, correct?

And please, if you're not the OP, do not respond to my prompt. I'm a bit disappointed at the effort put into this suggestion and I'd like to see if the OP knows that they're talking about so I know whether or not to support the argument.

The Suggestions forum is infamous for having people contribute to programming discussions while spreading misinformation and I think that Badatprogrammingibe is trying to filter in the people who are “qualified” to participate.

I'm not trying to sound condescending or anything. I personally would have explained TCO because I want to teach people (and just talk about programming). However, this forum tends to have regulars with high post counts who are taken more authoritatively, many times undeservedly, and those people may in fact be the ones spreading the CS misinformation. In my experience the Suggestions forum is a huge obnoxious circle-backpat clique of forum regulars repeating each other's unconstructive and uninformed talking points. Badatprogrammingibe probably doesn't want the uninformed claims of this crowd to have credence.

EDIT: Whoops, I didn't see the transparent text until I replied. From what I've seen of Badatprogrammingibe, they definitely know about the programming that they talk about, especially pertaining to Lisp, FP, and the lambda calculus.

Last edited by TheAspiringHacker (Sept. 26, 2018 22:00:58)

venyanwarrior

badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.

Bro.

Just tell us.

TheAdriCoolManDude

venyanwarrior wrote:
badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.
Bro.

Just tell us.

Seriously, badatprogramming, no one will understand if you tell us nothing.

TheAspiringHacker

I understand badatprogrammingibe because I already knew what TCO is. If you don't, you really need to learn how to search up documentation, but I will link some articles:

https://stackoverflow.com/questions/310974/what-is-tail-call-optimization#310980

https://en.wikipedia.org/wiki/Tail_call

https://en.wikipedia.org/wiki/Call_stack

https://mitpress-mit-edu.ezproxyberklee.flo.org/sites/default/files/sicp/full-text/book/book-Z-H-34.html#%_idx_6088

TheAdriCoolManDude

TheAspiringHacker wrote:
I understand badatprogrammingibe because I already knew what TCO is. If you don't, you really need to learn how to search up documentation, but I will link some articles:

https://stackoverflow.com/questions/310974/what-is-tail-call-optimization#310980

https://en.wikipedia.org/wiki/Tail_call

https://en.wikipedia.org/wiki/Call_stack

https://mitpress-mit-edu.ezproxyberklee.flo.org/sites/default/files/sicp/full-text/book/book-Z-H-34.html#%_idx_6088

I'm just gonna be an idiot and wait for him to say something.-removed-

Last edited by TheAdriCoolManDude (Sept. 27, 2018 00:14:16)

TheAspiringHacker

TheAdriCoolManDude wrote:
TheAspiringHacker wrote:
I understand badatprogrammingibe because I already knew what TCO is. If you don't, you really need to learn how to search up documentation, but I will link some articles:

https://stackoverflow.com/questions/310974/what-is-tail-call-optimization#310980

https://en.wikipedia.org/wiki/Tail_call

https://en.wikipedia.org/wiki/Call_stack

https://mitpress-mit-edu.ezproxyberklee.flo.org/sites/default/files/sicp/full-text/book/book-Z-H-34.html#%_idx_6088
I'm just gonna be an idiot and wait for him to say something. If he doesn't, then no offense, but that would make him a hypocrite.

How would badatprogrammingibe not saying anything make them a hypocrite? They aren't criticizing anyone else for not teaching them some idea.

*Sigh* you know what, I'm sure there were times that I didn't understand something on the forums, be it lambda or first-class lists or whatever, and people explained it to me and I understood, so I guess the right thing to do is to explain TCO, even though I've already linked some very helpful resources that you should spend some effort understanding.

When you call a function (a Scratch block), the computer needs to store the state (e.g. the values of the parameters). Notably, if the function is recursive, the state of the nested function calls all need to be maintained, so the computer can't simply use some fixed part of memory. What the computer does is keep a “stack” of function call states, known as “activation records” or “frames.” When a function is called, the computer “pushes” a new frame onto the call stack, and when the function finishes, the computer “pops” the top frame off the stack. If there are many nested function calls, then the stack will grow and the computer may not have enough memory to store it, resulting in a “stack overflow.”

When a function call is the last instruction in a function definition, the computer doesn't need to push a new frame onto the stack, but can simply reuse the current frame. The reuse is known as tail-call optimization.

Example:

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

might be expressed in low-level pseudocode as:

foo:
    reg1 <- [sp - 4]      ; store the argument in reg1; [sp - 4] is some offset from the top of the stack (the stack pointer, or sp) that holds the argument
    reg2 <- sub reg1 4    ; subtract 4 from the contents of reg1 and store the result in reg2
    return reg2           ; return the contents of reg3
 
bar:
    reg1 <- [sp - 4]      ; store the argument in reg1; [sp - 4] is some offset from the stack pointer that holds the argument
    reg2 <- mul reg1 2    ; multiply reg1 by 2 and store the reuslt in reg2
    push reg2             ; push reg2 onto the stack
    reg3 <- call foo      ; call foo with the contents of reg2 on the stack, storing the results in reg3
    return reg3           ; return the contents of reg3
 
main:
    push 2                ; push 2 onto the stack
    reg1 <- call bar      ; call the function "bar" with the argument 2 on the stack, storing the result in reg1
    return reg1           ; return the contents of reg1

reg1, reg2, and reg3 are “registers” that store results of instructions. Think of them like Scratch variables. (You don't need to understand this, but the comparison to variables is more apt for Scratch than for other programming languages, because Scratch doesn't have function-local variables.)

Last edited by TheAspiringHacker (Sept. 27, 2018 00:24:44)

badatprogrammingibe

TheAdriCoolManDude wrote:
venyanwarrior wrote:
badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.
Bro.

Just tell us.
Seriously, badatprogramming, no one will understand if you tell us nothing.

I didn't want to have to say it so harshly, but the audience this suggestion is made for is the developers of scratch, who most likely already know about tail call optimization. (I would be a bit surprised, and to be honest a bit concerned if they didn't.)

This doesn't mean that you can't learn what it is, and become part of the discussion, but you shouldn't join the discussion if you don't know what it is. TheAspiringHacker has given some resources and an explanation to what TCO is.

rdococ wrote:
Full support. It wouldn't be too difficult to implement, New Scratchers probably wouldn't even notice, and tail call recursion can be useful to remove otherwise unnecessary variables or even simply for students to learn about recursion without as much of a risk of crashing Scratch or causing an error. It fits completely with the principle of “low floor, high ceiling”.

I've never been able to get a stack overflow in Scratch, to be honest - it might already have tail call optimization.

It is hard to achieve a stack overflow in scratch because of how slow scratch is, but I have run some tests, and it did slowly eat up memory with tail recursive (and any type of recursive) procedure. Eventually after running a tail recursive procedure for say a few minutes, you should get a stack overflow.

Edit: Here's an example project to show this: https://scratch-mit-edu.ezproxyberklee.flo.org/projects/248734098/
Run a task manager or a resource manager, and watch as the amount of memory used up increases.

Last edited by badatprogrammingibe (Sept. 27, 2018 00:14:29)

TheAdriCoolManDude

-removed-

Last edited by TheAdriCoolManDude (Sept. 27, 2018 00:14:35)

TheAdriCoolManDude

badatprogrammingibe wrote:
TheAdriCoolManDude wrote:
venyanwarrior wrote:
badatprogrammingibe wrote:
If you don't know what Tail Call Optimization is, please do not post on this suggestion until you find out what it is, you're not helping the discussion.
Bro.

Just tell us.
Seriously, badatprogramming, no one will understand if you tell us nothing.
I didn't want to have to say it so harshly, but the audience this suggestion is made for is the developers of scratch, who most likely already know about tail call optimization. (I would be a bit surprised, and to be honest a bit concerned if they didn't.)

This doesn't mean that you can't learn what it is, and become part of the discussion, but you shouldn't join the discussion if you don't know what it is. TheAspiringHacker has given some resources and an explanation to what TCO is.

I already tried. I'm still confused, no matter what. Maybe it could help, if you do tell us. You'd help everyone. I'm also sorry for making you say to us so harshly.

Last edited by TheAdriCoolManDude (Sept. 27, 2018 00:15:09)

TheAspiringHacker

See my edit with the example.

Discuss Scratch