Talk:Anonymous recursion

What constitutes correctness in this task

It seems that I could not make clear what this task is about. Anonymous recursion is the call equivalent to the jump of an anonymous branch.

Most programming languages allow you to branch to a previous location without that you must invent a name (label) for that.

An example for a non-anonymous branch would be:

  doThis();
  myLabel1:
     if (!condition())
        goto myLabel2;
     doThat();
     goto myLabel1;
  myLabel2:
  doMore();

This is normally written as an anonymous branch:

  doThis();
  while (condition())
     doThat();
  doMore();

The advantages are obvious: You don't have to invent label names for separate goto statements, and the program flow is not obfuscated by the explicit housekeeping for the loop.

In that sense, 'while' implements an anonymous jump: It does not disturb the program flow in any way, which goes from doThis() to doThat() without any special setup, and the branch back to the anonymous location (the start of the 'while' statement) is done transparently.

In the same sense, it is desirable to have an anonymous call. Ideally via some keyword, in the same way as 'while', 'for' etc. are keywords for anonymous jumps in most languages.

In PicoLisp, the corresponding keywords are 'recur' and 'recurse':

  (doThis)
  (recur ()
     (doThat)
     (if (condition)
        (recurse) ) )
  (doMore)

Note that 'recur' does not disrupt the program flow. It behaves like the 'while' in anonymous loops in that regard, the program goes from 'doThis' directly to 'doThat' without any intervening function call. Only if 'recurse' is executed somewhere in the body of 'recur', an actual call takes place.

In classic BASIC, such behavior could be directly programmed via GOSUB:

  100 doThis
  110 doThat
  120 IF condition THEN 140
  130 GOSUB 110
  140 doMore

Thus, defining an anonymous function is not a correct solution to this task. Even if that function is local to the main function, it is just hidden, being equivalent to a 'static' function in C.

Take the Ada solution:

  function Fib ...
     function Actual_Fib ...
        ...
     end Actual_Fib;
  begin
     if X < 0 then
        raise Constraint_Error;
     else
        return Actual_Fib (X);
     end if;
  end Fib;

There are still two named functions being defined. This is equivalent to a C program

  static int Actual_Fib(..) {
     ...
  }

  int Fib(..) {
     if (X < 0)
        error();
     return Actual_Fib(X);
  }

Note that the 'if' statement does not directly proceed to the fibonacci processing. There is a top-level call to 'Actual_Fib' in between.

With a 'recur' statement, this is not the case:

  (de fibo (N)
     (if (lt0 N)
        (quit "Illegal argument" N) )
     (recur (N)
        (if (> 2 N)
           1
           (+ (recurse (dec N)) (recurse (- N 2))) ) ) )

The first invocation of '(if (> 2 N)' happens in the top level context of 'fibo', without an intervening function call and thus saving one recursion level.

The JavaScript solution

  function fibo(n) {
    if (n < 0)
      throw "Argument cannot be negative";
    else
      return (function(x) {
        if (n < 2)
          return 1;
        else
          return arguments.callee(n-1) + arguments.callee(n-2);
      })(n);
  }

is correct IMHO, despite that it defines a new function. But it does this inline, in a clean way within the program flow.

If can't say whether the J solution is correct or not. I don't understand it well enough. Perhaps somebody else can judge?

The same goes for Mathematica. The text states that the check is performed once (though it still calls '#0'), so I'll believe it.

Concerning the Python, Ruby and Tcl versions, I'm not sure. They define a local function 'f' (or object 'o'), which is then called by name. It seems weaker to me than the elegant 'arguments.callee' mechanism of JavaScript.

The Ursala solution looks cool.--Abu 11:04, 8 January 2011 (UTC)

The J solution is incorrect because it does not check for a negative sign, it simply implements the fibonacci function. Using $: is problematic because it is a reference to the largest verb which means that it will re-execute the entire function including the check if such a check is included. I have fixed the Mathematica example so that the check is performed only once, #0 is local to the anonymous function it is referenced in, this is the fibonacci function and not the function with the check. --Zeotrope 16:18, 8 January 2011 (UTC)

Since the J solution acts like an identity when called with negative arguments the check for negative numbers can be performed after the fibonacci function is called, signalling a domain error if the result is negative: <lang J>fibN =: 3 : '[:^:(0&>) (-&2 +&$: -&1)^:(1&<) M. y'"0</lang> Alternatively using a control structure: <lang J>(3 : 'if. y<0 do. <negative argument else. <(-&2 +&$: -&1)^:(1&<) M. y end.'"0)</lang> --Zeotrope 19:48, 8 January 2011 (UTC)

The J solution does indeed check if the number is negative before using recursion, and will not use recursion with a negative argument. (Any number which is negative is not greater than 1, and the J solution checks to see if the number is greater than 1 before using recursion.) That said, the task does not specify the result to be returned for negative values. --Rdm 03:25, 9 January 2011 (UTC)

The Tcl version only gives the function a local name (i.e., stores the function in a local variable) in order to keep the lines relatively short. f is not a name in the space of commands (which Tcl partitions completely from the space of variables) so I'd argue that the code as written completely follows the rules of the task. It would certainly be understood as being anonymous from the perspective of a Tcl practitioner. –Donal Fellows 09:06, 9 January 2011 (UTC)

Recursion implies a function

I am the author of the examples for Ruby and for UNIX Shell which create and hide a recursive function.

I believe that the use of recursion implies the existence of a function. To have recursion, one must call a thing, and this thing must return; therefore this thing is a function. The task is to hide the extra function so that it does not pollute the namespace nor become available to other functions. JavaScript 'arguments.callee' and PicoLisp 'recurse' only hide a function. I show this by porting them to Ruby. --Kernigh 22:20, 8 January 2011 (UTC)

<lang ruby># a function almost like JavaScript class Function

 def initialize(*params, &block)
   @params = Struct.new(:callee, *params)
   @block = block  # ___ hiding a function! ___
 end

 def call(*args)
   @block[@params.new(self, *args)]
 end

 alias [] call

end

def fibo(n)

 if n < 0
   raise "Argument cannot be negative"
 else
   return (Function.new(:n) { |arguments|
             if arguments.n < 2
               next 1
             else
               next (arguments.callee[arguments.n-1] +
                     arguments.callee[arguments.n-2])
             end
           })[n]
 end

end</lang>

<lang ruby># recur/recurse almost like PicoLisp def recur(*args, &block)

 old_recurse = $recurse
 begin
   $recurse = block  # ___ hiding a function! ___
   $recurse[*args]
 ensure
   $recurse = old_recurse
 end

end

def fib(n)

 if n < 0
   raise "Illegal argument #{n}"
 end
 recur(n) { |n|
   if 2 > n
     1
   else
     $recurse[n.pred] + $recurse[n - 2]
   end
 }

end</lang>

Agreed. I think this strikes home. You could stuff that 'recur' function into some library, and use it whenever needed, right? --Abu 07:46, 9 January 2011 (UTC)

Is there something I'm doing wrong? The above version of 'fib' just returns its argument. --Abu 09:15, 12 January 2011 (UTC)

Concerning "recursion implies a function", it depends on what you consider a function. The GOSOB in the Basic code snippet is not really a function call. That's why I used the term "call" instead of "function". A Forth solution would involve two or three new immediate control words, similar to BEGIN/WHILE/REPEAT. In the PicoLisp version (and also in your second Ruby version, if I understand it right), the first pass through the 'recur' body does not actually involve a function call, but it is executed in the context of the surrounding function. --Abu 07:57, 9 January 2011 (UTC)