mIRC Home    About    Download    Register    News    Help

Print Thread
Page 1 of 2 1 2
Recursion #250610 24/01/15 06:22 AM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
In earlier version of mIRC, we had recursion, direct recursion. Then it was limited (/maxdepth), then it was removed.
Well, I think it was removed because it was too often used in a bad way, resulting in infinite loop etc etc..
We have indirect recursion with /scid or /scon, which was previously limited to 85 iterations (probably more in the past, before 6.17), as of 7.38, looks like it reduced to 43 iterations max.
We have indirect recursion with two aliases as well (calling each other), limited to 255 iterations max.

I'm not going to talk about how useful recursion is, this is not the point.
I don't buy the argument that it was removed because it was used in a wrong way, /while loop can be used in the same bad way, so can /signal, they weren't removed..

Indirect recursion's methods are fine, their current limit could simply be extended but well, they are workarounds, I would rather like the feature itself being back.
Of course it still would need a limit, but that limit could be high enough to be useful, perhaps defaulting to the current behavior (send the command to the server if the name of the command is a custom alias, or call the built-in if it's a built-in name) but bringing back /maxdepth, with a new parameter, the name of an alias..

/maxdepth <alias name> [depth] where mIRC would use the maximum number of call allowed if [depth] isn't specified

There are many threads about recursion, I think it would be a good idea to bring it back.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Wims] #250611 24/01/15 07:00 AM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
I do use indirect recursion in my scripts. Mostly I use the alias name "/recur </alias>" but I also started using it as an identifier "$recur($foo($2-))" for return values. I would like to see it enabled again without having to make silly work-arounds. There are some situations where it's just the elegant solution.

I don't know anything about /maxdepth <alias name>, that sounds too complex and I'd rather just see work "out of the box" the same way indirect recursion works right now. Neither way seems to be harmful to mIRC.

op { mode # +oooo $$1-4 | op $5- }
Looks really really nice.

op { mode # +oooo $$1-4 | recur op $5- }
recur $$1-

Works just as well.

I agree with you. Recursion is hardly a dangerous thing, even if someone accidentally uses it incorrectly.
They won't make mIRC seize up, unlike a /while loop that forgot to /inc.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Recursion [Re: Raccoon] #250612 24/01/15 08:12 AM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
We can't get it to work out of the box because it would break backward compatibility.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Wims] #250613 24/01/15 08:17 AM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
Didn't it work OOTB in much earlier versions?

There is the '!' prefix to explicit no recursion should take place, for instances where people are overwriting an internal mIRC command or server command.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Recursion [Re: Raccoon] #250614 24/01/15 08:19 AM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
It did but it was a very very long time ago..
The '!' command prefix just call the built-in command, it has nothing to do with recursion.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Wims] #250615 24/01/15 08:22 AM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
It has everything to do with it.

The only issue with breaking backward compatibility is if someone overwrote the MODE command with their own /mode alias, expecting it to fallback instead of recur.

In any other case where it's not a built-in command, the current behavior is to raise an error "no such command." A change that avoids an error can't be considered as breaking compatibility.

They SHOULD be using !mode when overwriting a command if it shouldn't recur.

mode { !mode ... }

The help file is very clear that you should use the '!' prefix if you do not want it to be processed as an alias. The current fallback behavior is just coincidental since the removal of recursive abilities. Breaking this fallback behavior shouldn't be considered breaking compatibility, because it's invalid usage according to documentation.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Recursion [Re: Raccoon] #250616 24/01/15 09:32 AM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
No, it doesn't, the '!' command prefix is only about processing the built-in command rather than your alias:
Code:
alias filter echo -a you're a filter!
If you have this, you can do /!filter to process the built-in command but /filter will echos "you're a filter!" to the active window, there is nothing about recursion here.
Recursion occurs only when you are calling the same alias from itself:
Code:
alias filter echo -a you're a filter! | filter
As you may know, since mIRC doesn't support direct recursion, rather than throwing an error when trying to execute /filter from the filter alias, it executes it as the built-in command, which here, will report "/filter: invalid parameter", but if you were not using an alias's name which is a built-in command, it would have sent the command to the server.

Allowing direct recursion means calling /filter here would keep printing "you're a filter" to the active window" because the /filter call at the end of that filter alias would just call itself, it wouldn't call the built-in /filter command and, since that behavior would be different from the current behavior, you would be breaking compatibilities.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Raccoon] #250618 24/01/15 11:17 AM
Joined: Aug 2013
Posts: 73
Iire Offline
Babel fish
Offline
Babel fish
Joined: Aug 2013
Posts: 73
Originally Posted By: Raccoon
The only issue with breaking backward compatibility is if someone overwrote the MODE command with their own /mode alias, expecting it to fallback instead of recur. [...] They SHOULD be using !mode when overwriting a command if it shouldn't recur.

This is a far bigger and more common issue than you may realize...

Originally Posted By: Racoon
The help file is very clear that you should use the '!' prefix if you do not want it to be processed as an alias. The current fallback behavior is just coincidental since the removal of recursive abilities. Breaking this fallback behavior shouldn't be considered breaking compatibility, because it's invalid usage according to documentation.

The thing is, even though people SHOULD use the ! prefix, many don't, and so changing the behavior would indeed break many scripts. (The fact that those scripts can be considered incorrect is irrelevant when it comes to Khaled's insistence on maintaining backwards compatibility)

Keep in mind that this exact behavior was once altered during the "Error: recursive call" fiasco, and when this happened, you may remember that we saw hordes of people - notably non-scripters - complaining and submitting bug reports because their old scripts no longer worked. If direct recursion is implemented, the (unfixed versions of) those same scripts will break again, only instead of getting a harmless but annoying "* Error: recursive call", people will be treated to a potentially dangerous (e.g. risk of self-flood-off) command repetition, a possible temporary freeze, and the "* Error allocating stack memory" error instead. Quite simply, this is the kind of thing that Khaled, (and I'm sure many helpers/scripters), probably won't want to deal with again, thus the chance of this being done is virtually 0. *cough* "compatibility mode: you know you want to!" (o_o( )o_o) (o_o(

Ouims, everything aside, I don't think I actually understand your original suggestion.

Re: Recursion [Re: Wims] #250620 24/01/15 12:23 PM
Joined: Dec 2002
Posts: 4,871
Khaled Offline
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 4,871
Unfortunately this is not possible as recursion is limited by stack space. Stack space is limited memory that is defined for an application at compile time. Stack space is automatically used whenever a function is called, so recursion depth is always limited. If an application uses more than its allocated stack space, this causes a stack overflow crash. Most languages place limits on recursion depth because of this. In languages where you can increase the recursion depth, this can still cause an application/script to crash if it goes beyond the stack space limit. That is why the /maxdepth command was removed from mIRC and the maximum depth was set low.

The default stack space for Windows applications is 1MB. mIRC sets its own stack space at 2MB, which would technically allow recursion beyond 255, perhaps to about 1500, but it is set to 255 as a precaution as other routines can be chained recursively during script parsing.

Even if I did increase mIRC's reserved stack space, say to 32MB (which is not recommended), in my tests this still only allowed a recursive depth of about 30000 and used 600MB of memory. I could probably improve on these numbers by rewriting parts of the script parser but not by much.

There is a special case recursion call that conserves stack space called a tail call but this would not work for the scripter parser as a tail call requires a very specific set of conditions to work.

Re: Recursion [Re: Iire] #250621 24/01/15 12:24 PM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
I simply want recursion to be allowed for a reasonable amount of iteration.
In the past, recursion was allowed but limited with a command /maxdepth, but that command would only control the depth that could be used (the number of iteration), I suggested to add the alias's name to /maxdepth for protection, to only allows very specific alias to be able use recursion.

Code:
alias factorial {
  if ($1 <= 1) return 1
  return $calc( $1 * $factorial( $calc($1 -1) ) )
}
Would work.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Khaled] #250622 24/01/15 01:03 PM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
Yeah, I know the stack space is set at compile time. Who is saying increasing that value is not recommended? Imho there is nothing wrong with increasing that stack size.
Well recursion on a depth of 30000 isn't something that would happen every day anyways, indeed heavy recursion leads to a lot of memory usage, however that memory used is released at the end so it's not really an issue I think, but certainly a limit of 30000 would be enough smile even 20000 would be enough.
I don't know, it looks like your test is showing it's working pretty well wink


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Wims] #250624 24/01/15 03:18 PM
Joined: Dec 2002
Posts: 4,871
Khaled Offline
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 4,871
Microsoft recommends that you decrease the stack size from 1MB if you can and that "It is best to choose as small a stack size as possible and commit the stack that is needed for the thread or fiber to run reliably. Every page that is reserved for the stack cannot be used for any other purpose."

On my Windows 7, there are currently 74 processes, and many threads (each of which require their own stack space), running in the background. If they all set a reserved stack space of 32MB, that would require at least 2.4G of reserved stack space. As I have no idea what the side-effects are of reserved stack space on system and/or application performance, I would rather take the more conservative option.

Even though I do not plan to increase the stack space, I did some more testing and noticed that with a stack size of 32MB the first time I called the recursive alias, it took about four seconds to complete. The second time, and every time afterwards, it took ten seconds to complete. This raises a red flag for me. Without knowing more about stack size and its potential side-effects on applications and Windows in general, I am very wary of changing it.

Apart from the above, increasing stack space, which will affect all mIRC users, possibly negatively, just to increase the recursion limit to an arbitrary and still limited value that will only be useful in a small number of cases, and is both more speed and memory intensive than an iterative solution, does not seem reasonable.

Re: Recursion [Re: Khaled] #250625 24/01/15 03:21 PM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
I'm not really understanding how any of the discussion about stack size affects simple little recursive scripts like the ones I posted above. ?

I like the current behavior... if it iterates too many times, it just complains and stops. I've never seen mIRC spike when typing /op <50 nicknames>


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Recursion [Re: Khaled] #250629 24/01/15 04:53 PM
Joined: Apr 2004
Posts: 853
Sat Offline
Hoopy frood
Offline
Hoopy frood
Joined: Apr 2004
Posts: 853
Originally Posted By: Khaled
"Every page that is reserved for the stack cannot be used for any other purpose."

On my Windows 7, there are currently 74 processes, and many threads (each of which require their own stack space), running in the background. If they all set a reserved stack space of 32MB, that would require at least 2.4G of reserved stack space.

I'm afraid you're misinterpreting the text from Microsoft. The full text shows that "reserved" means "set aside for that purpose in the process's virtual address space" in this context. It does not mean that all of that virtual address space has physical pages backing it. The virtual stack pages will only have associated physical memory if they 1) are part of the initially committed set, or 2) have been actually used at some point. Thus, increasing the maximum ("reserved") stack size does not automatically lead to more memory usage. On the other hand, once a stack page has actually been used at any point, it basically cannot be freed anymore, so that in mIRC's single-threaded case..

Originally Posted By: Wims
however that memory used is released at the end so it's not really an issue I think

.."the end" is the moment that mIRC exits, and no earlier.

Originally Posted By: Khaled
I did some more testing and noticed that with a stack size of 32MB the first time I called the recursive alias, it took about four seconds to complete. The second time, and every time afterwards, it took ten seconds to complete.

One possible explanation is that Windows aggressively swaps large stacks to the page file, which means that for all but the first time, the pages need to be reread from disk before they can be reused. Task Manager can probably confirm (or deny) this.

Originally Posted By: Khaled
Apart from the above, increasing stack space, which will affect all mIRC users, possibly negatively, just to increase the recursion limit to an arbitrary and still limited value that will only be useful in a small number of cases, and is both more speed and memory intensive than an iterative solution, does not seem reasonable.

I completely agree. The examples given so far can easily be implemented iteratively, and with hardly any extra code to boot.

Last edited by Sat; 24/01/15 04:59 PM. Reason: proper quote attribution

Saturn, QuakeNet staff
Re: Recursion [Re: Sat] #250630 24/01/15 06:53 PM
Joined: Jul 2006
Posts: 3,741
W
Wims Offline OP
Hoopy frood
OP Offline
Hoopy frood
W
Joined: Jul 2006
Posts: 3,741
Quote:
.."the end" is the moment that mIRC exits, and no earlier.
I was thinking those 600MB he was talking about where the result of the test, not related to the stack since he talked about '32MB', which would be released after the test, not when mIRC exit.

@Khaled: well that's not a good news, but I understand.


Looking for a good help channel about mIRC? Check #mircscripting @ irc.swiftirc.net
Re: Recursion [Re: Wims] #250653 25/01/15 10:44 AM
Joined: Apr 2004
Posts: 853
Sat Offline
Hoopy frood
Offline
Hoopy frood
Joined: Apr 2004
Posts: 853
Fair enough. That would be the best approach if any.


Saturn, QuakeNet staff
Re: Recursion [Re: Sat] #250872 01/02/15 10:38 PM
Joined: Dec 2002
Posts: 4,871
Khaled Offline
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 4,871
Quote:
I'm afraid you're misinterpreting the text from Microsoft. The full text shows that "reserved" means "set aside for that purpose in the process's virtual address space" in this context. It does not mean that all of that virtual address space has physical pages backing it. The virtual stack pages will only have associated physical memory if they 1) are part of the initially committed set, or 2) have been actually used at some point. Thus, increasing the maximum ("reserved") stack size does not automatically lead to more memory usage. On the other hand, once a stack page has actually been used at any point, it basically cannot be freed anymore, so that in mIRC's single-threaded case..

Thanks, I did understand that it was not committed memory. Perhaps I should have stated that in my post. My point was that if every application reserved and used stack space without consideration, it would have a negative effect on the system as a whole. Since Microsoft recommends that as little stack space is used as possible, it would be better for mIRC to stay as close to that recommendation as possible. That said, I increased it somewhat unwillingly a few years ago from the default 1MB to 2MB (as an extra precaution, in addition to limiting recursion depth, in order to mitigate freezes\crashes related to recursion) so extending it even further is something I would prefer to avoid.

Update: I forgot to mention that I found a way to make the script parser determine the exact remaining stack space during recursion. The method seems to work correctly under XP, 7, 8.1, 10, and Wine. It allows the script parser to more precisely determine whether it can continue with a recursive call and to use more of the available reserved stack space, while still providing a conservative buffer. This increases recursion depth from about 250 to about 4000. The actual maximum depth will depend on the whether command/identifier calls are used, and which commands/identifiers are used, as some may have longer call chains than others.

Last edited by Khaled; 01/02/15 10:51 PM.
Re: Recursion [Re: Khaled] #250873 01/02/15 10:48 PM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
This may seem like a silly question... but why do functions and aliases use stack space? I mean, we're talking about a virtual programming environment, a scripting language. Our code isn't that significant smile

I know I can do infinite recursion in other scripting languages (AutoHotkey) and even real languages. What's the difference here?


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Re: Recursion [Re: Raccoon] #250879 01/02/15 11:28 PM
Joined: Dec 2002
Posts: 4,871
Khaled Offline
Hoopy frood
Offline
Hoopy frood
Joined: Dec 2002
Posts: 4,871
Wikipedia has a good explanation of the call stack and why stack overflows happen. Basically, when a function calls another function, the chain of calls and their parameters need to be stored on the call stack and this uses stack space.

A language needs to be designed to handle deep recursion by allocating heap memory to store and manage the call stack and parameters itself and avoiding nested calls. One side-effect is that this is usually much slower than letting the system handle it, so unless recursion is important, it is better not to do it.

There is an interesting recursion limit page that lists the recursion limits for various languages, although it says that AutoHotkey has a limit of 827, so the page might not be up-to-date. If you are able to do deep recursion in AutoHotkey, it may be that AutoHotkey was unable do that at some point and was rewritten to do so.

It is difficult to tell what the recursion limits are for most languages without testing them out. Some have arbitrarily low recursion limits to mitigate unintentional recursion but these can be increased with a command/setting, however this itself may be limited depending on the settings used to compile the language, which may either enable stack use or own stack management, and may compile with a larger or smaller reserved stack size to allow deeper recursion.

Last edited by Khaled; 01/02/15 11:39 PM.
Re: Recursion [Re: Khaled] #250881 01/02/15 11:49 PM
Joined: Feb 2003
Posts: 2,729
Raccoon Offline
Hoopy frood
Offline
Hoopy frood
Joined: Feb 2003
Posts: 2,729
Cool beans, thanks! smile

In your opinion, do you think the '!' command prefix is in itself enough to say that backwards compatibility wouldn't be broken if you just enabled recursion again? That is, calling a same-named command from within a scripted alias, by definition in the help file SHOULD have a '!' in front of it to indicate that you don't want to trigger a scripted alias.

There seems to be some argument over this point -- I don't think it would break compatibility because the help file is clear -- Wiz thinks it would, because of the happenstance behavior introduced when recursion was disabled.

If you want to perform a command without it being processed as an alias, you can prefix it with a ! exclamation mark.


Well. At least I won lunch.
Good philosophy, see good in bad, I like!
Page 1 of 2 1 2