Anonymous recursion: Difference between revisions
Added simple D entry |
Add Axiom task |
||
Line 52: | Line 52: | ||
{ return n < 0 ? "error" : n < 2 ? 1 : n * fib(n-1) |
{ return n < 0 ? "error" : n < 2 ? 1 : n * fib(n-1) |
||
}</lang> |
}</lang> |
||
=={{header|Axiom}}== |
|||
Axiom currently has scope issues with calling a local function recursively. One solution is |
|||
to use the Reference (pointer) domain and initialise the local function with a dummy value: |
|||
<lang axiom>)abbrev package TESTP TestPackage |
|||
Z ==> Integer |
|||
TestPackage : with |
|||
fib : Z -> Z |
|||
== add |
|||
fib x == |
|||
x <= 0 => error "argument outside of range" |
|||
f : Reference((Z,Z,Z) -> Z) := ref((n, v1, v2) +-> 0) |
|||
f() := (n, v1, v2) +-> if n<2 then v2 else f()(n-1,v2,v1+v2) |
|||
f()(x,1,1)</lang> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
Revision as of 20:58, 1 October 2012
You are encouraged to solve this task according to the task description, using any language you may know.
While implementing a recursive function, it often happens that we must resort to a separate "helper function" to handle the actual recursion.
This is usually the case when directly calling the current function would waste too many resources (stack space, execution time), cause unwanted side-effects, and/or the function doesn't have the right arguments and/and return values.
So we end up inventing some silly name like "foo2" or "foo_helper". I have always found it painful to come up with a proper name, and see a quite some disadvantages:
- You have to think up a name, which then pollutes the namespace
- A function is created which is called from nowhere else
- The program flow in the source code is interrupted
Some languages allow you to embed recursion directly in-place. This might work via a label, a local gosub instruction, or some special keyword.
Anonymous recursion can also be accomplished using the Y combinator.
If possible, demonstrate this by writing the recursive version of the fibonacci function (see Fibonacci sequence) which checks for a negative argument before doing the actual recursion.
Ada
In Ada you can define functions local to other functions/procedures. This makes it invisible to outside and prevents namespace pollution.
Better would be to use type Natural instead of Integer, which lets Ada do the magic of checking the valid range. <lang Ada> function Fib (X: in Integer) return Integer is
function Actual_Fib (N: in Integer) return Integer is begin if N < 2 then return N; else return Actual_Fib (N-1) + Actual_Fib (N-2); end if; end Actual_Fib; begin if X < 0 then raise Constraint_Error; else return Actual_Fib (X); end if; end Fib;</lang>
AutoHotkey
If: <lang ahk>fib(n) { if(n < 0)
return error else if(n < 2) return 1 else return n * fib(n-1)
}</lang> Ternary: <lang ahk>fib(n) { return n < 0 ? "error" : n < 2 ? 1 : n * fib(n-1) }</lang>
Axiom
Axiom currently has scope issues with calling a local function recursively. One solution is to use the Reference (pointer) domain and initialise the local function with a dummy value: <lang axiom>)abbrev package TESTP TestPackage Z ==> Integer TestPackage : with
fib : Z -> Z == add fib x == x <= 0 => error "argument outside of range" f : Reference((Z,Z,Z) -> Z) := ref((n, v1, v2) +-> 0) f() := (n, v1, v2) +-> if n<2 then v2 else f()(n-1,v2,v1+v2) f()(x,1,1)</lang>
Bracmat
lambda 'light'
The first solution uses macro substitution. In an expression headed by an apostrophe operator with an empty lhs all subexpressions headed by a dollar operator with empty lhs are replaced by the values that the rhs are bound to, without otherwise evaluating the expression. Example: if (x=7) & (y=4)
then '($x+3+$y)
becomes =7+3+4
. Notice that the solution below utilises no other names than arg
, the keyword that always denotes a function's argument. The test for negative or non-numeric arguments is outside the recursive part. The function fails if given negative input.
<lang bracmat>( (
= . !arg:#:~<0 & ( (=.!arg$!arg) $ ( = . ' ( . !arg:<2 | (($arg)$($arg))$(!arg+-2) + (($arg)$($arg))$(!arg+-1) ) ) ) $ !arg )
$ 30 ) </lang> Answer:
832040
pure lambda calculus
(See http://en.wikipedia.org/wiki/Lambda_calculus). The following solution works almost the same way as the previous solution, but uses lambda calculus <lang bracmat>( /(
' ( x . $x:#:~<0 & ( /('(f.($f)$($f))) $ /( ' ( r . /( ' ( n . $n:<2 | (($r)$($r))$($n+-2) + (($r)$($r))$($n+-1) ) ) ) ) ) $ ($x) ) )
$ 30 )</lang> Answer:
832040
C
Using scoped function fib_i inside fib, with GCC: <lang C>#include <stdio.h>
long fib(long x) {
long fib_i(long n) { return n < 2 ? n : fib_i(n - 2) + fib_i(n - 1); }; if (x < 0) { printf("Bad argument: fib(%ld)\n", x); return -1; } return fib_i(x);
}
long fib_i(long n) /* just to show the fib_i() inside fib() has no bearing outside it */ {
printf("This is not the fib you are looking for\n"); return -1;
}
int main() {
long x; for (x = -1; x < 4; x ++) printf("fib %ld = %ld\n", x, fib(x));
printf("calling fib_i from outside fib:\n"); fib_i(3);
return 0;
}</lang>
- Output:
Bad argument: fib(-1) fib -1 = -1 fib 0 = 0 fib 1 = 1 fib 2 = 1 fib 3 = 2 calling fib_i from outside fib: This is not the fib you are looking for
C++
In C++ (as of the 2003 version of the standard, possibly earlier), we can declare class within a function scope. By giving that class a public static member function, we can create a function whose symbol name is only known to the function in which the class was derived. <lang cpp>double fib(const double n) {
if(n < 0) { throw "Invalid argument passed to fib"; } else { class actual_fib { public: static double calc(const double n) { if(n < 2) { return n; } else { return calc(n-1) + calc(n-2); } } };
return actual_fib::calc(n); }
}</lang>
<lang cpp>#include <functional> using namespace std;
double fib(double n) {
if(n < 0) throw "Invalid argument"; function<double(double)> actual_fib = [&](double n) { if(n < 2) return n; return actual_fib(n-1) + actual_fib(n-2); };
return actual_fib(n);
}</lang>
Clojure
The JVM as of now has no Tail call optimization so the default way of looping in Clojure uses anonymous recursion so not to be confusing. <lang clojure> (defn fib [n]
(when (neg? n) (throw (new IllegalArgumentException "n should be > 0"))) (loop [n n, v1 1, v2 1] (if (< n 2) v2 (recur (dec n) v2 (+ v1 v2)))))
</lang> Using an anonymous function
CoffeeScript
<lang coffeescript># This is a rather obscure technique to have an anonymous
- function call itself.
fibonacci = (n) ->
throw "Argument cannot be negative" if n < 0 do (n) -> return n if n <= 1 arguments.callee(n-2) + arguments.callee(n-1)
- Since it's pretty lightweight to assign an anonymous
- function to a local variable, the idiom below might be
- more preferred.
fibonacci2 = (n) ->
throw "Argument cannot be negative" if n < 0 recurse = (n) -> return n if n <= 1 recurse(n-2) + recurse(n-1) recurse(n)
</lang>
Common Lisp
Using labels
This puts a function in a local label. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace. <lang lisp>(defun fib (number)
"Fibonacci sequence function." (if (< number 0) (error "Error. The number entered: ~A is negative" number) (labels ((fib1 (n a b) (if (= n 0) a (fib1 (- n 1) b (+ a b))))) (fib1 number 0 1))))</lang>
Although name space polution isn't an issue, in recognition of the obvious convenience of anonymous recursive helpers, here is another solution: add the language feature for anonymously recursive blocks: the operator RECURSIVE, with a built-in local operator RECURSE to make recursive calls.
Here is fib
rewritten to use RECURSIVE:
<lang lisp>(defun fib (number)
"Fibonacci sequence function." (if (< number 0) (error "Error. The number entered: ~A is negative" number) (recursive ((n number) (a 0) (b 1)) (if (= n 0) a (recurse (- n 1) b (+ a b))))))</lang>
Implementation of RECURSIVE: <lang lisp>(defmacro recursive ((&rest parm-init-pairs) &body body)
(let ((hidden-name (gensym "RECURSIVE-"))) `(macrolet ((recurse (&rest args) `(,',hidden-name ,@args))) (labels ((,hidden-name (,@(mapcar #'first parm-init-pairs)) ,@body)) (,hidden-name ,@(mapcar #'second parm-init-pairs))))))</lang>
RECURSIVE works by generating a local function with LABELS, but with a machine-generated unique name. Furthermore, it provides syntactic sugar so that the initial call to the recursive function takes place implicitly, and the initial values are specified using LET-like syntax. Of course, if RECURSIVE blocks are nested, each RECURSE refers to its own function. There is no way for an inner RECURSIVE to specify recursion to an other RECURSIVE. That is what names are for!
Exercises for reader:
- In the original
fib
, the recursive local function can obtain a reference to itself using#'fib
. This would allow it to, for instance,(apply #'fib list-of-args)
. Add a way for RECURSIVE blocks to obtain a reference to themselves. - Add support for &optional and &rest parameters. Optional: also &key and &aux.
- Add LOOPBACK operator whose syntax resembles RECURSE, but which simply assigns the variables and performs a branch back to the top rather than a recursive call.
- Tail recursion optimization is compiler-dependent in Lisp. Modify RECURSIVE so that it walks the expressions and identifies tail-recursive RECURSE calls, rewriting these to use looping code. Be careful that unevaluated literal lists which resemble RECURSE calls are not rewritten, and that RECURSE calls belonging to any nested RECURSIVE invocation are not accidentally treated.
Using the Y combinator
<lang lisp>(setf (symbol-function '!) (symbol-function 'funcall)
(symbol-function '!!) (symbol-function 'apply))
(defmacro ? (args &body body)
`(lambda ,args ,@body))
(defstruct combinator
(name nil :type symbol) (function nil :type function))
(defmethod print-object ((combinator combinator) stream)
(print-unreadable-object (combinator stream :type t) (format stream "~A" (combinator-name combinator))))
(defconstant +y-combinator+
(make-combinator :name 'y-combinator :function (? (f) (! (? (g) (! g g)) (? (g) (! f (? (&rest a) (!! (! g g) a))))))))
(defconstant +z-combinator+
(make-combinator :name 'z-combinator :function (? (f) (! (? (g) (! f (? (x) (! (! g g) x)))) (? (g) (! f (? (x) (! (! g g) x))))))))
(defparameter *default-combinator* +y-combinator+)
(defmacro with-y-combinator (&body body)
`(let ((*default-combinator* +y-combinator+)) ,@body))
(defmacro with-z-combinator (&body body)
`(let ((*default-combinator* +z-combinator+)) ,@body))
(defun x-call (x-function &rest args)
(apply (funcall (combinator-function *default-combinator*) x-function) args))
(defmacro x-function ((name &rest args) &body body)
`(lambda (,name) (lambda ,args (macrolet ((,name (&rest args) `(funcall ,',name ,@args))) ,@body))))
(defmacro x-defun (name args &body body)
`(defun ,name ,args (x-call (x-function (,name ,@args) ,@body) ,@args)))
- examples
(x-defun factorial (n)
(if (zerop n) 1 (* n (factorial (1- n)))))
(x-defun fib (n)
(case n (0 0) (1 1) (otherwise (+ (fib (- n 1)) (fib (- n 2))))))</lang>
D
<lang d>uint fib(in uint n) pure nothrow {
immutable self = &__traits(parent, {}); return (n < 2) ? n : self(n - 1) + self(n - 2);
}
void main() {
import std.stdio; writeln(fib(39));
}</lang>
- Output:
63245986
With Anonymous Class
In this version anonymous class is created, and by using opCall member function, the anonymous class object can take arguments and act like an anonymous function. The recursion is done by calling opCall inside itself. <lang d>import std.stdio;
int fib(in int n) pure nothrow {
assert(n >= 0);
return (new class { static int opCall(in int m) pure nothrow { if (m < 2) return m; else return opCall(m - 1) + opCall(m - 2); } })(n);
}
void main() {
writeln(fib(39));
}</lang> The output is the same.
Dylan
This puts a function in a local method binding. The function is not anonymous, but the name fib1 is local and never pollutes the outside namespace.
<lang dylan> define function fib (n)
when (n < 0) error("Can't take fibonacci of negative integer: %d\n", n) end; local method fib1 (n, a, b) if (n = 0) a else fib1(n - 1, b, a + b) end end; fib1(n, 0, 1)
end </lang>
Ela
Using fix-point combinator: <lang ela>fib n | n < 0 = fail "Negative n"
| else = fix (\f n -> if n < 2 then n else f (n-1) + f (n-2)) n</lang>
Function 'fix' is defined in standard Prelude as follows: <lang ela>fix f = f (& fix f)</lang>
Elena
<lang elena>#define std'dictionary'*.
- define std'patterns'*.
- symbol fibo : i =
[
Control ifNot:(i < 0).
#if (i < 2) ? [ ^ i. ] | [ ^ fibo::(i - 2) + fibo::(i - 1). ].
].
- symbol Program =
[
loop &&from:-1 &to:10 run: i = [ 'program'output << "%nfib(" << i << ")=". 'program'output << fibo::i | << "failed". ].
].</lang>
F#
Using a nested function:
The function 'fib2' is only visible inside the 'fib' function. <lang fsharp>let fib = function
| n when n < 0 -> None | n -> let rec fib2 = function | 0 | 1 -> 1 | n -> fib2 (n-1) + fib2 (n-2) in Some (fib2 n)</lang>
Using a fixed point combinator: <lang fsharp>let rec fix f x = f (fix f) x
let fib = function
| n when n < 0 -> None | n -> Some (fix (fun f -> (function | 0 | 1 -> 1 | n -> f (n-1) + f (n-2))) n)</lang>
- Output:
Both functions have the same output. <lang fsharp>[-1..5] |> List.map fib |> printfn "%A" [null; Some 1; Some 1; Some 2; Some 3; Some 5; Some 8]</lang>
Factor
One would never use anonymous recursion. The better way defines a private word, like fib2
, and recurse by name. This private word would pollute the namespace of one source file.
To achieve anonymous recursion, this solution has a recursive quotation. <lang factor>USING: kernel math ; IN: rosettacode.fibonacci.ar
- fib ( n -- m )
dup 0 < [ "fib of negative" throw ] when [ ! If n < 2, then drop q, else find q(n - 1) + q(n - 2). [ dup 2 < ] dip swap [ drop ] [ [ [ 1 - ] dip dup call ] [ [ 2 - ] dip dup call ] 2bi + ] if ] dup call( n q -- m ) ;</lang>
The name q in the stack effect has no significance; call( x x -- x )
would still work.
The recursive quotation has 2 significant disadvantages:
- To enable the recursion, a reference to the quotation stays on the stack. This q impedes access to other things on the stack. This solution must use
dip
andswap
to move q out of the way. To simplify the code, one might move q to a local variable, but then the recursion would not be anonymous. - Factor cannot infer the stack effect of a recursive quotation. The last line must have
call( n q -- m )
instead of plaincall
; butcall( n q -- m )
defers the stack effect check until runtime. So if the quotation has a wrong stack effect, the compiler would miss the error; only a run offib
would detect the error.
Falcon
Falcon allows a function to refer to itself by use of the fself keyword which is always set to the currently executing function. <lang falcon>function fib(x)
if x < 0 raise ParamError(description|"Negative argument invalid", extra|"Fibbonacci sequence is undefined for negative numbers") else return (function(y) if y == 0 return 0 elif y == 1 return 1 else return fself(y-1) + fself(y-2) end end)(x) end
end
try
>fib(2)
>fib(3)
>fib(4)
>fib(-1)
catch in e
> e
end</lang>
- Output:
1 2 3 ParamError SS0000 at falcon.core.ParamError._init:(PC:ext.c): Negative argument invalid (Fibbonacci sequence is undefined for negative numbers) Traceback: falcon.core.ParamError._init:0(PC:ext.c) "/home/uDTVwo/prog.fam" prog.fib:3(PC:56) "/home/uDTVwo/prog.fam" prog.__main__:22(PC:132)
Forth
Recursion is always anonymous in Forth, allowing it to be used in anonymous functions. However, definitions can't be defined during a definition (there are no 'local functions'), and the data stack can't be portably used to get data into a definition being defined.
- and any Forth in which colon-sys consumes zero cells on the data stack.
<lang forth>:noname ( n -- n' )
dup 2 < ?exit 1- dup recurse swap 1- recurse + ; ( xt )
- fib ( +n -- n' )
dup 0< abort" Negative numbers don't exist." [ ( xt from the :NONAME above ) compile, ] ;</lang>
Portability is achieved with a once-off variable (or any temporary-use space with a constant address - i.e., not PAD): <lang forth>( xt from :noname in the previous example ) variable pocket pocket !
- fib ( +n -- n' )
dup 0< abort" Negative numbers don't exist." [ pocket @ compile, ] ;</lang>
Fortran
Since a hidden named function instead of an anonymous one seems to be ok with implementors, here is the Fortran version: <lang Fortran>integer function fib(n)
integer, intent(in) :: n if (n < 0 ) then write (*,*) 'Bad argument: fib(',n,')' stop else fib = purefib(n) end if
contains
recursive pure integer function purefib(n) result(f) integer, intent(in) :: n if (n < 2 ) then f = n else f = purefib(n-1) + purefib(n-2) end if end function purefib
end function fib</lang>
Go
Y combinator solution. Go has no special support for anonymous recursion. <lang go>package main
import "fmt"
func main() {
for _, n := range []int{0, 1, 2, 3, 4, 5, 10, 40, -1} { f, ok := arFib(n) if ok { fmt.Printf("fib %d = %d\n", n, f) } else { fmt.Println("fib undefined for negative numbers") } }
}
func arFib(n int) (int, bool) {
switch { case n < 0: return 0, false case n < 2: return n, true } return yc(func(recurse fn) fn { return func(left, term1, term2 int) int { if left == 0 { return term1+term2 } return recurse(left-1, term1+term2, term1) } })(n-2, 1, 0), true
}
type fn func(int, int, int) int type ff func(fn) fn type fx func(fx) fn
func yc(f ff) fn {
return func(x fx) fn { return f(func(a1, a2, a3 int) int { return x(x)(a1, a2, a3) }) }(func(x fx) fn { return f(func(a1, a2, a3 int) int { return x(x)(a1, a2, a3) }) })
}</lang>
- Output:
fib 0 = 0 fib 1 = 1 fib 2 = 1 fib 3 = 2 fib 4 = 3 fib 5 = 5 fib 10 = 55 fib 40 = 102334155 fib undefined for negative numbers
Groovy
Groovy does not explicitly support anonymous recursion. This solution is a kludgy trick that takes advantage of the "owner" scoping variable (reserved word) for closures. <lang groovy>def fib = {
assert it > -1 {i -> i < 2 ? i : {j -> owner.call(j)}(i-1) + {k -> owner.call(k)}(i-2)}(it)
}</lang> Test: <lang groovy>def fib0to20 = (0..20).collect(fib) println fib0to20
try {
println fib(-25)
} catch (Throwable e) {
println "KABOOM!!" println e.message
}</lang>
- Output:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] KABOOM!! assert it > -1 | | | false -25
Haskell
Haskell has two ways to use anonymous recursion. Both methods hide the 'anonymous' function from the containing module, however the first method is actually using a named function.
Named function:
We're defining a function 'real' which is only available from within the fib function. <lang haskell>fib :: Integer -> Maybe Integer fib n
| n < 0 = Nothing | otherwise = Just $ real n where real 0 = 1 real 1 = 1 real n = real (n-1) + real (n-2)</lang>
Anonymous function:
This uses the 'fix' function to find the fixed point of the anonymous function. <lang haskell>import Data.Function (fix)
fib :: Integer -> Maybe Integer fib n
| n < 0 = Nothing | otherwise = Just $ fix (\f -> (\n -> if n > 1 then f (n-1) + f (n-2) else 1)) n</lang>
- Output:
Both functions provide the same output when run in GHCI. <lang haskell>ghci> map fib [-4..10] [Nothing,Nothing,Nothing,Nothing,Just 1,Just 1,Just 2,Just 3,Just 5,Just 8,Just 13,Just 21,Just 34,Just 55,Just 89]</lang>
Icon and Unicon
The following solution works in both languages. A cache is used to improve performance.
This example is more a case of can it even be done, and just because we CAN do something - doesn't mean we should do it. The use of co-expressions for this purpose was probably never intended by the language designers and is more than a little bit intensive and definitely NOT recommended.
This example does accomplish the goals of hiding the procedure inside fib so that the type and value checking is outside the recursion. It also does not require an identifier to reference the inner procedure; but, it requires a local variable to remember our return point. Also, each recursion will result in the current co-expression being refreshed, essentially copied, placing a heavy demand on co-expression resources. <lang Icon>procedure main(A)
every write("fib(",a := numeric(!A),")=",fib(a))
end
procedure fib(n)
local source, i static cache initial { cache := table() cache[0] := 0 cache[1] := 1 } if type(n) == "integer" & n >= 0 then return n @ makeProc Template:I := @(source := &source)
end
procedure makeProc(A)
A := if type(A) == "list" then A[1] return (@A, A) # prime and return
end</lang> Some of the code requires some explaining:
- The double curly brace syntax after makeProc serves two different purposes, the outer set is used in the call to create a co-expression. The inner one binds all the expressions together as a single unit.
- At #1 we remember where we came from and receive n from our caller
- At #2 we transmit the new parameters to refreshed copies of the current co-expression setup to act as a normal procedure and cache the result.
- At #3 we transmit the result back to our caller.
- The procedure makeProc consumes the the first transmission to the co-expression which is ignored. Essentially this primes the co-expression to behave like a regular procedure.
For reference, here is the non-cached version: <lang Icon>procedure fib(n)
local source, i if type(n) == "integer" & n >= 0 then return n @ makeProc {{ i := @(source := &source) if i = (0|1) then i@source ((i-1)@makeProc(^¤t) + (i-2)@makeProc(^¤t)) @ source }}
end</lang> The performance of this second version is 'truly impressive'. And I mean that in a really bad way. By way of example, using default memory settings on a current laptop, a simple recursive non-cached fib out distanced the non-cached fib above by a factor of 20,000. And a simple recursive cached version out distanced the cached version above by a factor of 2,000.
J
Copied directly from the fibonacci sequence task, which in turn copied from one of several implementations in an essay on the J Wiki: <lang j> fibN=: (-&2 +&$: -&1)^:(1&<) M."0</lang> Note that this is an identity function for arguments less than 1 (and 1 (and 5)).
Examples: <lang j> fibN 12 144
fibN i.31
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040</lang> (This implementation is doubly recursive except that results are cached across function calls.)
$:
is an anonymous reference to the largest containing verb in the sentence.
Java
Creates an anonymous inner class to do the dirty work. While it does keep the recursive function out of the namespace of the class, it does seem to violate the spirit of the task in that the function is still named.
<lang java>public static long fib(int n) {
if (n < 0) throw new IllegalArgumentException("n can not be a negative number"); return new Object() { private long fibInner(int n) { return (n < 2) ? n : (fibInner(n - 1) + fibInner(n - 2)); } }.fibInner(n);
}</lang>
JavaScript
<lang javascript>function fibo(n) {
if (n < 0) throw "Argument cannot be negative"; else return (function(n) { if (n < 2) return 1; else return arguments.callee(n-1) + arguments.callee(n-2); })(n);
}</lang>
Note that arguments.callee
will not be available in ES5 Strict mode.
K
<lang k>fib: {:[x<0; "Error Negative Number"; {:[x<2;x;_f[x-2]+_f[x-1]]}x]}</lang> Examples: <lang k> fib'!10 0 1 1 2 3 5 8 13 21 34
fib -1
"Error Negative Number"</lang>
Lua
Using a Y combinator. <lang lua>local function Y(x) return (function (f) return f(f) end)(function(y) return x(function(z) return y(y)(z) end) end) end
return Y(function(fibs)
return function(n) return n < 2 and 1 or fibs(n - 1) + fibs(n - 2) end
end)</lang> using a metatable (also achieves memoization) <lang lua>return setmetatable({1,1},{__index = function(self, n)
self[n] = self[n-1] + self[n-2] return self[n]
end})</lang>
Mathematica
An anonymous reference to a function from within itself is named #0, arguments to that function are named #1,#2..#n, n being the position of the argument. The first argument may also be referenced as a # without a following number, the list of all arguments is referenced with ##. Anonymous functions are also known as pure functions in Mathematica. <lang Mathematica>check := #<0& fib := If[check[#],Throw["Negative Argument"],If[#<=1,1,#0[#-2]+#0[#-1]]&[#]]& fib /@ Range[0,10]
{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}</lang> Making sure that the check is only performed once. <lang Mathematica>check := (Print[#];#<0)& fib /@ Range[0,4] 0 1 2 3 4
{1, 1, 2, 3, 5}</lang>
Nemerle
Not anonymous exactly, but using inner function solves all problems stated in task description.
- name is basically the same as outer function and doesn't pollute the namespace
- inner function not expected to be called from anywhere else
- nesting maintains program flow in source code
<lang Nemerle>using System; using System.Console;
module Fib {
Fib(n : long) : long { def fib(m : long) { |0 => 1 |1 => 1 |_ => fib(m - 1) + fib(m - 2) } match(n) { |n when (n < 0) => throw ArgumentException("Fib() not defined on negative numbers") |_ => fib(n) } } Main() : void { foreach (i in [-2 .. 10]) { try {WriteLine("{0}", Fib(i));} catch {|e is ArgumentException => WriteLine(e.Message)} } }
}</lang>
Objective-C
This shows how a method (not regular function) can recursively call itself without explicitly putting its name in the code. <lang objc>#import <Foundation/Foundation.h>
@interface AnonymousRecursion : NSObject { } - (NSNumber *)fibonacci:(NSNumber *)n; @end
@implementation AnonymousRecursion - (NSNumber *)fibonacci:(NSNumber *)n {
int i = [n intValue]; if (i < 0) @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"fibonacci: no negative numbers" userInfo:nil]; int result; if (i < 2) result = 1; else result = [[self performSelector:_cmd withObject:[NSNumber numberWithInt:i-1]] intValue] + [[self performSelector:_cmd withObject:[NSNumber numberWithInt:i-2]] intValue]; return [NSNumber numberWithInt:result];
} @end
int main (int argc, const char *argv[]) {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; AnonymousRecursion *dummy = [[AnonymousRecursion alloc] init]; NSLog(@"%@", [dummy fibonacci:[NSNumber numberWithInt:8]]); [dummy release];
[pool release]; return 0;
}</lang>
- With internal named recursive block
<lang php>#import <Foundation/Foundation.h>
int fib(int n) {
if (n < 0) @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"fib: no negative numbers" userInfo:nil]; __block int (^f)(int); f = ^(int n) { if (n < 2) return 1; else return f(n-1) + f(n-2); }; return f(n);
}
int main (int argc, const char *argv[]) {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; NSLog(@"%d", fib(8));
[pool release]; return 0;
}</lang>
OCaml
OCaml has two ways to use anonymous recursion. Both methods hide the 'anonymous' function from the containing module, however the first method is actually using a named function.
Named function:
We're defining a function 'real' which is only available from within the fib function. <lang ocaml>let fib n =
let rec real = function 0 -> 1 | 1 -> 1 | n -> real (n-1) + real (n-2) in if n < 0 then None else Some (real n)</lang>
Anonymous function:
This uses the 'fix' function to find the fixed point of the anonymous function. <lang ocaml>let rec fix f x = f (fix f) x
let fib n =
if n < 0 then None else Some (fix (fun f -> fun n -> if n <= 1 then 1 else f (n-1) + f (n-2)) n)</lang>
- Output:
# fib 8;; - : int option = Some 34
OxygenBasic
An inner function keeps the name-space clean: <lang oxygenbasic> function fiboRatio() as double
function fibo( double i, j ) as double if j > 2e12 then return j / i return fibo j, i + j end function return fibo 1, 1
end function
print fiboRatio
</lang>
Perl
recur
isn't built into Perl, but it's easy to implement.
<lang perl>sub recur (&@) {
my $f = shift; local *recurse = $f; $f->(@_);
}
sub fibo {
my $n = shift; $n < 0 and die 'Negative argument'; recur { my $m = shift; $m < 3 ? 1 : recurse($m - 1) + recurse($m - 2); } $n;
}</lang> Although for this task, it would be fine to use a lexical variable (closure) to hold an anonymous sub reference, we can also just push it onto the args stack and use it from there: <lang perl>sub fib { my ($n) = @_; die "negative arg $n" if $n < 0; # put anon sub on stack and do a magic goto to it @_ = ($n, sub { my ($n, $f) = @_; # anon sub recurs with the sub ref on stack $n < 2 ? $n : $f->($n - 1, $f) + $f->($n - 2, $f) }); goto $_[1]; }
print(fib($_), " ") for (0 .. 10);</lang>
One can also use caller
to get the name of the current subroutine as a string, then call the sub with that string. But this won't work if the current subroutine is anonymous: caller
will just return '__ANON__'
for the name of the subroutine. Thus, the below program must check the sign of the argument every call, failing the task. Note that under stricture, the line no strict 'refs';
is needed to permit using a string as a subroutine.
<lang perl>sub fibo {
my $n = shift; $n < 0 and die 'Negative argument'; no strict 'refs'; $n < 3 ? 1 : (caller(0))[3]->($n - 1) + (caller(0))[3]->($n - 2);
}</lang>
Perl 5.16 and __SUB__
Perl 5.16 introduced __SUB__ which refers to the current subroutine. <lang Perl>use v5.16; say sub {
my $n = shift; $n < 2 ? $n : __SUB__->($n-2) + __SUB__->($n-1)
}->($_) for 0..10</lang>
Perl 6
In addition to the methods in the Perl entry above, and the Y-combinator described in Y_combinator, you may also refer to an anonymous block or function from the inside: <lang perl6>sub fib($n) {
die "Naughty fib" if $n < 0; return { $_ < 2 ?? $_ !! &?BLOCK($_-1) + &?BLOCK($_-2); }($n);
}
say fib(10);</lang> However, using any of these methods is insane, when Perl 6 provides a sort of inside-out combinator that lets you define lazy infinite constants, where the demand for a particular value is divorced from dependencies on more primitive values. This operator, known as the sequence operator, does in a sense provide anonymous recursion to a closure that refers to more primitive values. <lang perl6>constant @fib = 0, 1, *+* ... *; say @fib[10];</lang> Here the closure, *+*, is just a quick way to write a lambda, -> $a, $b { $a + $b }. The sequence operator implicitly maps the two arguments to the -2nd and -1st elements of the sequence. So the sequence operator certainly applies an anonymous lambda, but whether it's recursion or not depends on whether you view a sequence as iteration or as simply a convenient way of memoizing a recursion. Either view is justifiable.
At this point someone may complain that the solution is doesn't fit the specified task because the sequence operator doesn't do the check for negative. True, but the sequence operator is not the whole of the solution; this check is supplied by the subscripting operator itself when you ask for @fib[-1]. Instead of scattering all kinds of arbitrary boundary conditions throughout your functions, the sequence operator maps them quite naturally to the boundary of definedness at the start of a list.
PHP
Don't know if this counts, but... <lang php><?php function fib($n) {
if ($n < 0) throw new Exception('Negative numbers not allowed'); else if ($n < 2) return 1; else { $f = __FUNCTION__; return $f($n-1) + $f($n-2); }
} echo fib(8), "\n"; ?></lang> However, __FUNCTION__ won't work for anonymous functions created with create_function() or closures in PHP 5.3+.
- With internal named recursive function
<lang php><?php function fib($n) {
if ($n < 0) throw new Exception('Negative numbers not allowed'); $f = function($n) use (&$f) { if ($n < 2) return 1; else return $f($n-1) + $f($n-2); }; return $f($n);
} echo fib(8), "\n"; ?></lang>
PicoLisp
<lang PicoLisp>(de fibo (N)
(if (lt0 N) (quit "Illegal argument" N) ) (recur (N) (if (> 2 N) 1 (+ (recurse (dec N)) (recurse (- N 2))) ) ) )</lang>
Explanation: The above uses the 'recur' / 'recurse' function pair, which is defined as a standard language extensions as <lang PicoLisp>(de recur recurse
(run (cdr recurse)) )</lang>
Note how 'recur' dynamically defines the function 'recurse' at runtime, by binding the rest of the expression (i.e. the body of the 'recur' statement) to the symbol 'recurse'.
PostScript
Postscript can make use of the higher order combinators to provide recursion. <lang postscript>% primitive recursion /pfact {
{1} {*} primrec}.
%linear recursion /lfact {
{dup 0 eq} {pop 1} {dup pred} {*} linrec}.
% general recursion /gfact {
{0 eq} {succ} {dup pred} {i *} genrec}.
% binary recursion /fib {
{2 lt} {} {pred dup pred} {+} binrec}.</lang>
Prolog
Works with SWI-Prolog and module lambda, written by Ulrich Neumerkel found there http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl The code is inspired from this page : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#Hiord (p 106). It uses the Y combinator. <lang prolog>:- use_module(lambda).
fib(N, _F) :- N < 0, !, write('fib is undefined for negative numbers.'), nl.
fib(N, F) :-
% code of Fibonacci PF = \Nb^R^Rr1^(Nb < 2 ->
R = Nb
;
N1 is Nb - 1, N2 is Nb - 2, call(Rr1,N1,R1,Rr1), call(Rr1,N2,R2,Rr1), R is R1 + R2 ),
% The Y combinator.
Pred = PF +\Nb2^F2^call(PF,Nb2,F2,PF),
call(Pred,N,F).</lang>
Python
<lang python>>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) >>> fib = lambda f: lambda n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))) >>> [ Y(fib)(i) for i in range(-2, 10) ] [None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>
Same thing as the above, but modified so that the function is uncurried: <lang python>>>> Y = lambda f: (lambda x: x(x))(lambda y: lambda *args: f(y(y), *args)) >>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))) >>> [ Y(fib)(i) for i in range(-2, 10) ] [None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>
A different approach: the function always receives itself as the first argument, and when recursing, makes sure to pass the called function as the first argument also <lang python>>>> from functools import partial >>> Y = lambda f: partial(f, f) >>> fib = lambda f, n: None if n < 0 else (0 if n == 0 else (1 if n == 1 else f(f, n-1) + f(f, n-2))) >>> [ Y(fib)(i) for i in range(-2, 10) ] [None, None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>
Qi
Use of anonymous recursive functions is not common in Qi. The philosophy of Qi seems to be that using a "silly name" like "foo2" or "foo_helper" makes the code clearer than using anonymous recursive functions.
However, it can be done, for instance like this:
<lang Qi> (define fib
N -> (let A (/. A N (if (< N 2) N (+ (A A (- N 2)) (A A (- N 1))))) (A A N)))
</lang>
R
R provides Recall() as a wrapper which finds the calling function, with limitations; Recall will not work if passed to another function as an argument. <lang R>fib2 <- function(n) {
(n >= 0) || stop("bad argument") ( function(n) if (n <= 1) 1 else Recall(n-1)+Recall(n-2) )(n)
}</lang>
REXX
[Modeled after the Fortran example.]
Since a hidden named function instead of an anonymous function seems
to be OK with implementors, here is the REXX version:
<lang rexx>/*REXX program to show anonymous recursion (of a function/subroutine). */
numeric digits 1e6 /*in case the user goes kaa-razy.*/
do j=0 to word(arg(1) 12, 1) /*use argument or the default: 12*/ say 'fibonacci('j") =" fib(j) /*show Fibonacci sequence: 0──►x */ end /*j*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────subroutines─────────────────────────*/ fib: procedure; if arg(1)>=0 then return .(arg(1))
say "***error!*** argument can't be negative."; exit
.:procedure; arg _; if _<2 then return _; return .(_-1)+.(_-2)</lang> output when using the default input ( 12 ):
fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = 1 fibonacci(3) = 2 fibonacci(4) = 3 fibonacci(5) = 5 fibonacci(6) = 8 fibonacci(7) = 13 fibonacci(8) = 21 fibonacci(9) = 34 fibonacci(10) = 55 fibonacci(11) = 89 fibonacci(12) = 144
Ruby
Ruby has no keyword for anonymous recursion.
We can recurse a block of code, but we must provide the block with a reference to itself. The easiest solution is to use a local variable.
Ruby with local variable
<lang ruby>def fib(n)
raise RangeError, "fib of negative" if n < 0 (fib2 = proc { |m| m < 2 ? m : fib2[m - 1] + fib2[m - 2] })[n]
end</lang>
<lang ruby>(-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]</lang>
Here 'fib2' is a local variable of the fib() method. Only the fib() method, or a block inside the fib() method, can call this 'fib2'. The rest of this program cannot call this 'fib2', but it can use the name 'fib2' for other things.
- The fib() method has two local variables 'fib2' and 'n'.
- The block has a local variable 'm' and closes on both 'fib2' and 'n'.
Caution! The recursive block has a difference from Ruby 1.8 to Ruby 1.9. Here is the same method, except changing the block parameter from 'm' to 'n', so that block 'n' and method 'n' have the same name. <lang ruby>def fib(n)
raise RangeError, "fib of negative" if n < 0 (fib2 = proc { |n| n < 2 ? n : fib2[n - 1] + fib2[n - 2] })[n]
end</lang> <lang ruby># Ruby 1.9 (-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
- Ruby 1.8
(-2..12).map { |i| fib i rescue :error } => [:error, :error, 0, 1, 0, -3, -8, -15, -24, -35, -48, -63, -80, -99, -120]</lang> Ruby 1.9 still shows the correct answer, but Ruby 1.8 shows the wrong answer. With Ruby 1.9, 'n' is still a local variable of the block. With Ruby 1.8, 'n' of the block closes on 'n' of the fib() method. All calls to the block share the 'n' of one call to the method. So fib2[n - 1] changes the value of 'n', and fib2[n - 2] uses the wrong value of 'n', thus the wrong answer.
Ruby with Hash
<lang ruby>def fib(n)
raise RangeError, "fib of negative" if n < 0 Hash.new { |fib2, m| fib2[m] = (m < 2 ? m : fib2[m - 1] + fib2[m - 2]) }[n]
end</lang> This uses a Hash to memoize the recursion. After fib2[m - 1] returns, fib2[m - 2] uses the value in the Hash, without redoing the calculations.
- The fib() method has one local variable 'n'.
- The block has two local variables 'fib2' and 'm', and closes on 'n'.
Ruby with recur/recurse
<lang ruby>require 'continuation' unless defined? Continuation
module Kernel
module_function
def recur(*args, &block) cont = catch(:recur) { return block[*args] } cont[block] end
def recurse(*args) block = callcc { |cont| throw(:recur, cont) } block[*args] end
end
def fib(n)
raise RangeError, "fib of negative" if n < 0 recur(n) { |m| m < 2 ? m : (recurse m - 1) + (recurse m - 2) }
end</lang>
Our recursive block now lives in the 'block' variable of the Kernel#recur method.
To start, Kernel#recur calls the block once. From inside the block, Kernel#recurse calls the block again. To find the block, recurse() plays a trick. First, Kernel#callcc creates a Continuation. Second, throw(:recur, cont) unwinds the call stack until it finds a matching Kernel#catch(:recur), which returns our Continuation. Third, Kernel#recur uses our Continuation to continue the matching Kernel#callcc, which returns our recursive block.
Ruby with arguments.callee
<lang ruby>require 'continuation' unless defined? Continuation
module Kernel
module_function
def function(&block) f = (proc do |*args| (class << args; self; end).class_eval do define_method(:callee) { f } end ret = nil cont = catch(:function) { ret = block.call(*args); nil } cont[args] if cont ret end) end
def arguments callcc { |cont| throw(:function, cont) } end
end
def fib(n)
raise RangeError, "fib of negative" if n < 0 function { |m| if m < 2 m else arguments.callee[m - 1] + arguments.callee[m - 2] end }[n]
end</lang> Our recursive block now lives in the 'block' variable of the Kernel#function method. Another block 'f' wraps our original block and sets up the 'arguments' array. Kernel#function returns this wrapper block. Kernel#arguments plays a trick to get the array of arguments from 'f'; this array has an extra singleton method #callee which returns 'f'.
Scala
Using a Y-combinator: <lang scala>def Y[A, B](f: (A ⇒ B) ⇒ (A ⇒ B)): A ⇒ B = f(Y(f))(_)
def fib(n: Int): Option[Int] =
if (n < 0) None else Some(Y[Int, Int](f ⇒ i ⇒ if (i < 2) 1 else f(i - 1) + f(i - 2))(n))
-2 to 5 map (n ⇒ (n, fib(n))) foreach println</lang>
- Output:
(-2,None) (-1,None) (0,Some(1)) (1,Some(1)) (2,Some(2)) (3,Some(3)) (4,Some(5)) (5,Some(8))
Scheme
This uses named let to create a function (aux) that only exists inside of fibonacci: <lang scheme>(define (fibonacci n)
(if (> 0 n) "Error: argument must not be negative." (let aux ((a 1) (b 0) (count n)) (if (= count 0) b (aux (+ a b) a (- count 1))))))
(map fibonacci '(1 2 3 4 5 6 7 8 9 10))</lang>
- Output:
'(1 1 2 3 5 8 13 21 34 55)
Tcl
This solution uses Tcl 8.5's lambda terms, extracting the current term from the call stack using introspection (storing it in a local variable only for convenience, with that not in any way being the name of the lambda term; just what it is stored in, and only as a convenience that keeps the code shorter). The lambda terms are applied with the apply
command.
<lang tcl>proc fib n {
# sanity checks if {[incr n 0] < 0} {error "argument may not be negative"} apply {x {
if {$x < 2} {return $x} # Extract the lambda term from the stack introspector for brevity set f [lindex [info level 0] 1] expr {[apply $f [incr x -1]] + [apply $f [incr x -1]]}
}} $n
}</lang> Demonstrating: <lang tcl>puts [fib 12]</lang>
- Output:
}
144
The code above can be written without even using a local variable to hold the lambda term, though this is generally less idiomatic because the code ends up longer and clumsier: <lang tcl>proc fib n {
if {[incr n 0] < 0} {error "argument may not be negative"} apply {x {expr { $x < 2 ? $x : [apply [lindex [info level 0] 1] [incr x -1]] + [apply [lindex [info level 0] 1] [incr x -1]] }}} $n
}</lang>
However, we can create a recurse
function that makes this much more straight-forward:
<lang tcl># Pick the lambda term out of the introspected caller's stack frame
proc tcl::mathfunc::recurse args {apply [lindex [info level -1] 1] {*}$args}
proc fib n {
if {[incr n 0] < 0} {error "argument may not be negative"} apply {x {expr { $x < 2 ? $x : recurse([incr x -1]) + recurse([incr x -1]) }}} $n
}</lang>
UNIX Shell
The shell does not have anonymous functions. Every function must have a name. However, one can create a subshell such that some function, which has a name in the subshell, is effectively anonymous to the parent shell. <lang bash>fib() {
if test 0 -gt "$1"; then echo "fib: fib of negative" 1>&2 return 1 else ( fib2() { if test 2 -gt "$1"; then echo "$1" else echo $(( $(fib2 $(($1 - 1)) ) + $(fib2 $(($1 - 2)) ) )) fi } fib2 "$1" ) fi
}</lang> <lang bash>$ for i in -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12; do > fib $i > done fib: fib of negative fib: fib of negative 0 1 1 2 3 5 8 13 21 34 55 89 144</lang>
Ursala
<lang Ursala>#import nat
fib =
~&izZB?( # test the sign bit of the argument
<'fib of negative'>!%, # throw an exception if it's negative {0,1}^?<a( # test the argument to a recursively defined function ~&a, # if the argument was a member of {0,1}, return it sum^|W( # otherwise return the sum of two recursive calls ~&, # to the function thus defined predecessor^~( # with the respective predecessors of ~&, # the given argument predecessor)))) # and the predecessor thereof</lang>
Anonymous recursion is often achieved using the recursive conditional operator, ( _ )^?( _ , _ )
, which takes a predicate on the left and a pair of functions on the right, typically one for the base and one for the inductive case in a recursive definition. The form ^?<
can be used if the relevant predicate is given by membership of the argument in a constant set, in which case only the set needs to be specified rather than the whole predicate.
The recursive conditional operator ^?
differs from the ordinary conditional ?
seen at the outermost level by arranging for its predicate and component functions to be given an input of the form where is the original argument, and is a copy of the whole function. Code within the function body may then access itself anonymously according to all the usual language idioms pertaining to deconstruction of tuples, and call itself by any of several recursion combinators, such as the pairwise recursion form W
seen above.
XPL0
In XPL0 you can nest functions/procedures inside other functions/procedures up to eight levels deep. This makes those nested functions invisible to the outside, thus preventing namespace pollution.
<lang XPL0>include c:\cxpl\codes;
func Fib(X); int X;
func ActualFib(N); int N; [if N<2 then return N else return ActualFib(N-1) + ActualFib(N-2); ]; \ActualFib;
[if X<0 then [Text(0, "Error "); return 0] else return ActualFib(X); ]; \Fib;
[IntOut(0, Fib(8)); CrLf(0);
IntOut(0, Fib(-2)); CrLf(0);
]</lang>
Output:
21 Error 0
- Programming Tasks
- Recursion
- Ada
- AutoHotkey
- AutoHotkey examples needing attention
- Examples needing attention
- Axiom
- Bracmat
- C
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dylan
- Ela
- Elena
- F Sharp
- Factor
- Falcon
- Forth
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- K
- Lua
- Mathematica
- Nemerle
- Objective-C
- OCaml
- OxygenBasic
- Perl
- Perl 6
- PHP
- PicoLisp
- PostScript
- Initlib
- Prolog
- Python
- Qi
- R
- REXX
- Ruby
- Continuation
- Scala
- Scheme
- Tcl
- UNIX Shell
- Ursala
- XPL0
- ACL2/Omit
- PureBasic/Omit