Which programming languages support functions that take themselves as arguments?
It is possible in any language, that features either mutability or recursion or both, to call a function with a pointer to itself. Basically, all conventional Turing complete languages, have those features, therefore there are so many answers.
The real question is how to type such functions. Non strongly typed languages (like C/C++) or dynamically (or gradually) typed are of no interest, as they enable type coercing of some form, that basically makes the task trivial. They rely on a programmer to provide a type and take it as granted. Therefore, we should be interested in strictly typed languages with the static type system.
If we will focus on OCaml, then your definition could be accepted by the compiler if you pass the -rectypes option, which will disable the occurrence check, that disallows recursive types. Indeed, the type of your function is ('a -> int -> string as 'a) -> int -> string,
# let foo x y = if y < 1 then "hi" else x x (y - 1);;
val foo : ('a -> int -> string as 'a) -> int -> string = <fun>
Note that, you don't need rec here, as your function is not really recursive. What is recursive is the type, ('a -> int -> string as 'a), here as expands to the left up to the parenthesis, i.e., 'a = 'a -> int -> string. This is a recurrence and, by default, many compilers disallow such equations (i.e., equations where the same type variable occurs on both sides of the equation, hence the name occurrence check). If this check is disabled, the compiler will allow this and alike definitions. However, it was observed that the occurrence check catches more bugs than disallows well-formed programs. In other words, when the occurrence check is triggered it is more likely a bug, rather than a deliberate attempt to write a well-typed function.
Therefore, in real life, programmers feel reluctant to introduce this option to their build systems. The good news is that if we will massage the original definition a little bit, we don't really need recursive types. For example, we can change the definition to the following,
let foo x y = if y < 1 then "hi" else x (y - 1)
which now has type
val foo : (int -> string) -> int -> string = <fun>
I.e., it is a function that takes another function of type (int -> string) and returns a function of type (int -> string). Therefore, to run foo we need to pass it a function that recursively calls foo, e.g.
let rec run y = foo run y
This is where the recursion comes into play. Yes, we didn't pass the function to itself directly. Instead, we passed it a function, that references foo and when foo calls this function it, in fact, calls itself, via an extra reference. We may also notice, that wrapping our function in a value of some other kind1) (using, record, or variant, or object) will also allow your definition. We can even specify those extra helper type as [@@unboxed] so that the compiler will not introduce extra boxing around the wrapper. But this is a sort of cheating. We still won't be passing the function to itself, but an object that contains this function (even though the compiler optimization will remove this extra indirection, from the perspective of the type system, those are still different objects, therefore the occurrence check is not triggered). So, we still need some indirection, if we don't want to enable recursive types. And let's stick to the simplest form of indirection, the run function and try to generalize this approach.
In fact, our run function is a specific case of a more general fixed-point combinator. We can parametrize run with any function of type ('a -> 'b) -> ('a -> 'b), so that it will work not only for foo:
let rec run foo y = foo (run foo) y
and in fact let's name it fix,
let rec fix f n = f (fix f) n
which has type
val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
And, we can still apply it to our foo
# fix foo 10
The Oleg Kiselyov web site is an excellent resource that shows many ways of defining the fixed point combinator in OCaml, Scheme, and Haskell.
1) This is essentially the same as the delegate approach, that was shown in other answers (both including languages with type inference like Haskell and OCaml, and languages that don't, like C++ and C#).
Your OCaml function requires a recursive type, i.e., a type that contains a direct reference to itself. You can define such types (and have values of such types) if you specify -rectypes when you run OCaml.
Here's a session with your function:
$ rlwrap ocaml -rectypes
OCaml version 4.06.1
# let rec foo x y = if y < 1 then "hi" else x x (y - 1);;
val foo : ('a -> int -> string as 'a) -> int -> string = <fun>
# foo foo 10;;
- : string = "hi"
#
The default is not to support recursive types, because they almost always are the result of programming errors.
Some examples I can write:
- C++
- C
- C#
- Python
- Scheme
C++
Ok, so not the first language you would think of, and definitely not a painless way of doing it, but it's very much possible. It's C++ and it's here because they say write about what you know :) Oh, and I wouldn't recommend doing this outside of academic interest.
#include <any>
#include <iostream>
void foo(std::any x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
// one line, like in your example
//std::any_cast<void (*) (std::any, int)>(x)(x, y - 1);
// or, more readable:
auto f = std::any_cast<void (*) (std::any, int)>(x);
f(x, y - 1);
}
int main()
{
foo(foo, 10);
}
If the casts are too much (and too ugly) you can write a small wrapper like bellow. But the biggest advantage is performance: you completely bypass the std::any heavy type.
#include <iostream>
class Self_proxy
{
using Foo_t = void(Self_proxy, int);
Foo_t* foo;
public:
constexpr Self_proxy(Foo_t* f) : foo{f} {}
constexpr auto operator()(Self_proxy x, int y) const
{
return foo(x, y);
}
};
void foo(Self_proxy x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
x(x, y - 1);
}
int main()
{
foo(foo, 10);
}
And a generic version of the wrapper (forwarding omitted for brevity):
#include <iostream>
template <class R, class... Args>
class Self_proxy
{
using Foo_t = R(Self_proxy<R, Args...>, Args...);
Foo_t* foo;
public:
constexpr Self_proxy(Foo_t* f) : foo{f} {}
constexpr auto operator()(Self_proxy x, Args... args) const
{
return foo(x, args...);
}
};
void foo(Self_proxy<void, int> x, int y)
{
std::cout << y << std::endl;
if (y == 0)
return;
x(x, y - 1);
}
int main()
{
foo(foo, 10);
}
C
You can do this in C also:
https://ideone.com/E1LkUW
#include <stdio.h>
typedef void(* dummy_f_type)(void);
void foo(dummy_f_type x, int y)
{
printf("%d\n", y);
if (y == 0)
return;
void (* f) (dummy_f_type, int) = (void (*) (dummy_f_type, int)) x;
f(x, y - 1);
}
int main()
{
foo((dummy_f_type)foo, 10);
}
The trap to avoid here is that you cannot use void* as the type for x as it's not valid to cast a pointer type to a data pointer type.
Or, as shown by leushenko in the comments, you can use the same pattern with a wrapper:
#include <stdio.h>
struct RF {
void (* f) (struct RF, int);
};
void foo(struct RF x, int y)
{
printf("%d\n", y);
if (y == 0)
return;
x.f(x, y - 1);
}
int main()
{
foo((struct RF) { foo }, 10);
}
C #
https://dotnetfiddle.net/XyDagc
using System;
public class Program
{
public delegate void MyDelegate (MyDelegate x, int y);
public static void Foo(MyDelegate x, int y)
{
Console.WriteLine(y);
if (y == 0)
return;
x(x, y - 1);
}
public static void Main()
{
Foo(Foo, 10);
}
}
Python
https://repl.it/repls/DearGoldenPresses
def f(x, y):
print(y)
if y == 0:
return
x(x, y - 1)
f(f, 10)
Scheme
And finally here's a functional language
https://repl.it/repls/PunyProbableKernelmode
(define (f x y)
(print y)
(if (not (= y 0)) (x x (- y 1)))
)
(f f 10)