Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rebol Tail Call Optimization

I come from a functional programming background and think first about recursive solutions to problems rather than iterative ones. I'm starting to work with Rebol a bit (specifically R3) and have written a solution to the primefactor kata using a tail-recursive function with an accumulator. But with any sufficiently large input I blow the stack. I have a script for Rebol2 called "tail-func.r" which implements a version of tail-call optimization that AFAIK has not been ported to R3. I know that Rebol 3 implements things differently than R2 in many cases, so is there a way to get TCO in Rebol 3 without any extra code? If not, is there a simpler way to get it without porting the old script?

Edited to add my code:

primefactors: function [n m factors] [
  either n > 1
    [ either (modulo n m) == 0
      [ primefactors (n / m) m (append factors m) ]
      [ primefactors n (m + 1) factors ] ]
    [ factors ]
  ]

  primefactors 30 2 (copy []) => [2 3 5]
like image 761
Jamie Avatar asked Mar 05 '14 03:03

Jamie


1 Answers

Not without code, sorry. Rebol isn't compiled, so there's no way to know ahead of time exactly what constitutes a tail call. Even calls to the return function propagate back up the call stack, quickly but not by a goto.

IIRC the author of tail-func works on Rebol 3 now, and whether or not he does it should be easy to port over. Now that you mention it I'll take a look. Function generators and preprocessors are easy to do in Rebol.

like image 92
BrianH Avatar answered Sep 30 '22 10:09

BrianH