Re: framework for tail recursion in pure perl, including Ackerman function
On 31 Aug 2006, at 02:33, Dana Hudes wrote: I wish to also point out that no Perl book replaces a solid grounding in computer science. Tail-end recursion removal is certainly a technique covered in the CS literature quite extensively. Any undergraduate book on algorithms covers it. Sophisticated techniques and new approaches may well be in journal articles; I personally haven't done a search of the ACM and IEEE CS literature for this topic. If pushed I can pull down 3 different textbooks on the subject of algorithms and see what they have to say. Remember, MJD and Damian mostly don't invent new techniques. Rather, they adapt them to the particular strengths of Perl. Yes quite - that's all well and good. But this is not even vaguely new territory is it? Dealing with tail recursion and deep recursion by rewriting a function to use an explicitly managed stack or a queue - or by turning the tail call into a goto or whatever is just well established practice, no? I don't have anything against discussion (obviously...) but do we need to discuss something that's already so well understood? -- Andy Armstrong, hexten.net
framework for tail recursion in pure perl, including Ackerman function
the attached proof-of-concept is almost as ugly as my coroutines module on CPAN,
but i have succeeded in implementing a tail-recursion framework in pure perl.
In order to use it, all modifications to recursive function arguments must be
made directly into @_, but a method is suggested for using named arguments
nonetheless
instead of returning a value, the recursive routine must assign to $_[0] when a
result has been achieved
the magic of nonautovivifying nonexistent hash elements in argument lists
is used to allow the recursive routine to return undef, if that is what it needs
to return, by assigning undef to its $_[0]
The Ackerman function expressed with the framework might look something like
sub Ack {
tr_dispatch(SUB=\tr_Ack, ARGS=[EMAIL PROTECTED]);
}
sub tr_Ack
{
my ($x, $y) = \(@_[1,2]);
$$x == 0 and ( $_[0] = $$y + 1, return);
$$y == 0 and ($$x--, $$y=1, return);
$$x-- ; $$y= tr_dispatch(SUB=\tr_Ack, ARGS=[$$x, $$y - 1]);
}
Comments welcome, especially interface improvement ideas.
--
David L Nicol
Re: framework for tail recursion in pure perl, including Ackerman function
On 30 Aug 2006, at 21:05, David Nicol wrote: On 8/30/06, Dana Hudes wrote: Have you read MJD's _Higher Order Perl_? He addresses tail end recursion removal. I've skimmed it... did he put up a module that does it for you? I realized that I left my prototype/prrof-of-concept off of the previous message to module authors; here it is -- thanks, I'll try to review that chapter tr_framework.pl Sorry, I've missed something here - how is your 'framework' superior to a simple queue based approach? Oh and I can't believe you've only skimmed HOP - it's a superb book that should be mandatory reading if this is an area you're interested in. -- Andy Armstrong, hexten.net
Re: framework for tail recursion in pure perl, including Ackerman function
On 8/30/06, Andy Armstrong [EMAIL PROTECTED] wrote:
Sorry, I've missed something here - how is your 'framework' superior
to a simple queue based approach?
it demonstrates tail-recursion, as such, and is not intended to be
a superior approach to other practices.
I just realized that goto sub is a better framework for implementing
such things, anyway:
# perl -wle 'sub f{ f()}; f()'
Deep recursion on subroutine main::f at -e line 1.
Out of memory!
# perl -wle 'sub f{ goto f}; f()'
^C
#
Oh and I can't believe you've only skimmed HOP - it's a superb book
that should be mandatory reading if this is an area you're interested
in.
so was the textbook in Lisp class.
Re: framework for tail recursion in pure perl, including Ackerman function
On 30 Aug 2006, at 21:28, David Nicol wrote:
I just realized that goto sub is a better framework for implementing
such things, anyway:
I don't think goto sub can really be described as a framework... Or
if it can may I start describing if() as a decision support system too?
# perl -wle 'sub f{ f()}; f()'
Deep recursion on subroutine main::f at -e line 1.
Out of memory!
# perl -wle 'sub f{ goto f}; f()'
^C
#
Yup, OK.
But why are you showing us this stuff? Who is it for? I'd have
thought that anyone who was interested would have already read HOP
and/or worked it out for themselves.
Who on this mailing list do you believe is interested in your
investigations?
Oh and I can't believe you've only skimmed HOP - it's a superb book
that should be mandatory reading if this is an area you're interested
in.
so was the textbook in Lisp class.
I'm surprised it covered Perl.
--
Andy Armstrong, hexten.net
Re: framework for tail recursion in pure perl, including Ackerman function
On 8/30/06, Andy Armstrong [EMAIL PROTECTED] wrote: I don't think goto sub can really be described as a framework... Or if it can may I start describing if() as a decision support system too? I won't stop you :) But why are you showing us this stuff? Who is it for? I'd have thought that anyone who was interested would have already read HOP and/or worked it out for themselves. the question is, Is anyone interested in a framework for more explicit support of tail recursion optimization module? Who on this mailing list do you believe is interested in your investigations? Oh and I can't believe you've only skimmed HOP - it's a superb book that should be mandatory reading if this is an area you're interested in. so was the textbook in Lisp class. I'm surprised it covered Perl. Why is everyone being so difficult the last month?
Re: framework for tail recursion in pure perl, including Ackerman function
On 30 Aug 2006, at 23:13, David Nicol wrote: But why are you showing us this stuff? Who is it for? I'd have thought that anyone who was interested would have already read HOP and/or worked it out for themselves. the question is, Is anyone interested in a framework for more explicit support of tail recursion optimization module? I'm guessing not - given that there's a well known and not particularly ugly technique for rewriting any recursive function using an explicit queue. But of course I could be wrong - it wouldn't be the first time :) I'm surprised it covered Perl. Why is everyone being so difficult the last month? Sorry - flippancy as humour. It should probably be deprecated or something. -- Andy Armstrong, hexten.net
Re: framework for tail recursion in pure perl, including Ackerman function
the question is, Is anyone interested in a framework for more explicit support of tail recursion optimization module? yes. so was the textbook in Lisp class. I'm surprised it covered Perl. Why is everyone being so difficult the last month? The weather is wreaking havoc. -- Key fingerprint = 40D0 9FFB 9939 7320 8294 05E0 BCC7 02C4 75CC 50D9 Total Existance Failure
Re: framework for tail recursion in pure perl, including Ackerman function
On Aug 30, 2006, at 3:09 PM, Andy Armstrong wrote: Oh and I can't believe you've only skimmed HOP - it's a superb book that should be mandatory reading if this is an area you're interested in. I don't think the point of the book was to stop people from exploring whatever approaches they might be interested in. -Ken
Re: framework for tail recursion in pure perl, including Ackerman function
I wish to also point out that no Perl book replaces a solid grounding in computer science. Tail-end recursion removal is certainly a technique covered in the CS literature quite extensively. Any undergraduate book on algorithms covers it. Sophisticated techniques and new approaches may well be in journal articles; I personally haven't done a search of the ACM and IEEE CS literature for this topic. If pushed I can pull down 3 different textbooks on the subject of algorithms and see what they have to say. Remember, MJD and Damian mostly don't invent new techniques. Rather, they adapt them to the particular strengths of Perl. Ken Williams wrote: On Aug 30, 2006, at 3:09 PM, Andy Armstrong wrote: Oh and I can't believe you've only skimmed HOP - it's a superb book that should be mandatory reading if this is an area you're interested in. I don't think the point of the book was to stop people from exploring whatever approaches they might be interested in. -Ken
