Function/macro that returns true if one of its arguments contains a call to itself

Question

Write a function (or macro) that returns true if and only if at least one of its arguments contains a call to the function itself and false otherwise.

For example:

int a=function(); //a==false
int b=function(0); //b==false
int c=function(function(0)); //c==true
int d=function(3*function(1)+2); //d==true (weakly-typed language)
bool e=function(true||function(1)); //e==true (strongly-typed language) 

EDIT: The function/macro may call other auxiliary function/macros.

EDIT 2: The function must take at least one argument, unless the language used behaves like C, where a function that takes no arguments may still be called with arguments nonetheless.

Answer 1

Mathematica...

...was made for this.

SetAttributes[f, HoldAll]
f[x___] := ! FreeQ[Hold@x, _f]

f[]             (* False *)
f[0]            (* False *)
f[f[0]]         (* True *)
f[3 f[1] + 2]   (* True *)
f[True || f[1]] (* True *)

Everything is an expression, and an expression has a Head and a number of elements. So 1+2 is actually Plus[1,2], and {1,2} is actually List[1,2]. This means we can match any expression for the head we're interested in - in this case the function f itself.

All we need to do is find a way to prevent Mathematica from evaluating the function arguments before the function is called, such that we can analyse the expression tree within the function. What's what Hold and HoldAll is for. Mathematica itself uses this to all over the place to provide special cases for certain implementations. E.g. if you call Length[Permutations[list]] it will never actually create all those permutations and waste loads of memory, but instead realise that it can simply compute this as Length[list]!.

Let's look at the code above in detail, using the last call f[True || f[1]] as an example. Normally, Mathematica will evaluate function arguments first, so this would simply short-circuit and call f[True]. However we have set

SetAttributes[f, HoldAll]

This instructs Mathematica not to evaluate the arguments, so the FullForm of the call (i.e. the internal expression tree, without any syntactic sugar) is

f[Or[True,f[1]]]

And the argument will actually be received by f in this form. The next issue is that, within f, as soon as we use the argument, Mathematica will again try to evaluate it. We can suppress this locally with Hold@x (syntactic sugar for Hold[x]). At this point we've got a handle on the original expression tree and do with it whatever we want.

To look for a pattern in an expression tree we can use FreeQ. It checks that a given pattern is not found in the expression tree. We use the patter _f, which matches any subexpression with head f (exactly what we're looking for). Of course, FreeQ returns the opposite of what we want, so we negate the result.

One more subtlety: I've specified the argument as x___, which is a sequence of 0 or more elements. This ensures that f works with any number of arguments. In the first call, f[] this means that Hold@x will simply become Hold[]. If there were multiple arguments, like f[0,f[1]], then Hold@x would be Hold[0,f[1]].

That's really all there is to it.

Answer 2

C++11

Similar to expression templates we can propagate the fact that we did call the function inside a functions parameters list in its return type.

At first we need some helper classes and functions:

#include <iostream>

template <bool FunctionWasInParameters> struct FunctionMarker {
  operator bool() const { return FunctionWasInParameters; }

  operator int() const { return FunctionWasInParameters; }
};

template <bool... values> struct Or;

template <bool first, bool... values> struct Or<first, values...> {
  static constexpr bool value = first || Or<values...>::value;
};

template <> struct Or<> { static constexpr bool value = false; };

template <class T> struct is_FunctionMarker {
  static constexpr bool value = false;
};

template <bool B> struct is_FunctionMarker<FunctionMarker<B>> {
  static constexpr bool value = true;
};

#define OVERLOAD_OPERATOR_FOR_FUNCTION_MARKER(OPERATOR)                        \
  template <bool B, class T>                                                   \
  FunctionMarker<B> operator OPERATOR(FunctionMarker<B>, T) {                  \
    return {};                                                                 \
  }                                                                            \
  template <bool B, class T>                                                   \
  FunctionMarker<B> operator OPERATOR(T, FunctionMarker<B>) {                  \
    return {};                                                                 \
  }                                                                            \
  /* to break ambiguity by specialization */                                   \
  template <bool B, bool B2>                                                   \
  FunctionMarker<B || B2> operator OPERATOR(FunctionMarker<B>,                 \
                                            FunctionMarker<B2>) {              \
    return {};                                                                 \
  }

OVERLOAD_OPERATOR_FOR_FUNCTION_MARKER(|| )
OVERLOAD_OPERATOR_FOR_FUNCTION_MARKER(+)
OVERLOAD_OPERATOR_FOR_FUNCTION_MARKER(*)
// TODO: overload all other operators!

Now, we can use it for the exact same code as in the question:

template <class... Args>
auto function(Args... args)
    -> FunctionMarker<Or<is_FunctionMarker<Args>::value...>::value> {
  return {};
}

FunctionMarker<false> function() { return {}; }

int main() {
  int a = function();
  int b = function(0);
  int c = function(function(0));
  int d = function(3 * function(1) + 2);
  bool e = function(true || function(1));

  // clang-format off
  std::cout << a << "//a==false\n"
            << b << "//b==false\n"
            << c << "//c==true\n"
            << d << "//d==true (weakly-typed language)\n"
            << e << "//e==true (strongly-typed language)\n";
}

Output from ideone:

0//a==false
0//b==false
1//c==true
1//d==true (weakly-typed language)
1//e==true (strongly-typed language)

Answer 3

C#

public PcgBool f(params object[] args)
{
    return args.Any(p => p is PcgBool);
}

public class PcgBool
{
    public PcgBool() { }
    public PcgBool(bool value)
    {
        Value = value;
    }

    private bool Value;

    public static implicit operator bool(PcgBool pcgBool)
    {
        return pcgBool.Value;
    }    

    public static implicit operator PcgBool(bool value)
    {
        return new PcgBool(value);
    }
}

Usage (in LINQPad):

void Main()
{
    Console.WriteLine(f(1,2,f(3),4)); // True
    Console.WriteLine(f(1,2,3,"4")); // False
}

The trick here is to make f more aware of the parameters, by passing a custom type (PcgBool) which is kind-of-like a boolean.

P.S. I hope returning a custom type which is implicitly castable from and to a bool is not considered as cheating. Technically you can use the return value as if it was of bool type, and the question asked to "return true if and only if" etc., but never stated the return type must be bool.

Answer 4

Lua

local x
local function f()
    local y = x
    x = true
    return y
end
debug.sethook(function()
        if debug.getinfo(2).func ~= f then
            x = false
        end
    end, "l")
print(f())
print(f(0))
print(f(f()))
print(f(f(0)))
print(f("derp" .. tostring(f())))

Answer 5

C++11 TMP

This one is a bit longer. Because of some limitations in C++ templates I had to do everything with types. Thus "True" as well as the numbers were turned into bool and int. Also The operations +, - and || were turned into add, mul and or_.

I hope this still qualifies as a valid answer.

template <typename... Args>
struct foo;

template <>
struct foo<>
{
    static bool const value = false;
};

template <typename T>
struct is_foo
{
    static bool const value = false;
};

template <typename... Args>
struct is_foo<foo<Args...>>
{
    static bool const value = true;
};

template <typename T>
struct is_given_foo
{
    static bool const value = false;
};

template <template <typename...> class T, typename... Args>
struct is_given_foo<T<Args...>>
{
    static bool const value = foo<Args...>::value;
};

template <typename Head, typename... Tail>
struct foo<Head, Tail...>
{
    static bool const value = is_foo<Head>::value || is_given_foo<Head>::value || foo<Tail...>::value;
};

template <typename... Args>
struct add {};

template <typename... Args>
struct mul {};

template <typename... Args>
struct or_ {};

static_assert(foo<>::value == false, "int a=function(); //a==false");
static_assert(foo<int>::value == false, "int b=function(0); //b==false");
static_assert(foo<foo<int>>::value == true, "int c=function(function(0)); //c==true");
static_assert(foo<add<mul<int, foo<int>>, int>>::value == true, "int d=function(3*function(1)+2); //d==true (weakly-typed language)");
static_assert(foo<or_<bool,foo<int>>>::value == true, "bool e=function(true||function(1)); //e==true (strongly-typed language)");

// just for the sake of C++
int main()
{
    return 0;
}

Answer 6

C

I don't think it can be done with procedures, but we can always (ab)use macros.

#include <stdio.h>
#define f(x) ((max_depth = ++depth), (x), (depth-- < max_depth))

int depth = 0;
int max_depth = 0;

char* bool(int x) { // Helper - not necessary for solution
  return x ? "true" : "false";
}

int main() {
  printf("f(1): %s\n", bool(f(1)));
  printf("f(f(1)): %s\n", bool(f(f(1))));
  printf("f(bool(f(1))): %s\n", bool(f(bool(f(1)))));
  printf("f(printf(\"f(1): %%s\\n\", bool(f(1)))): %s\n", bool(printf("f(1): %s\n", bool(f(1)))));
}

This outputs:

f(1): false
f(f(1)): true
f(bool(f(1))): true
f(1): false
f(printf("f(1): %s\n", bool(f(1)))): true

Our macro f keeps track of the current depth, and the maximum depth achieved since it was invoked. If the latter is greater than the former, then it has been called recursively.

Answer 7

C, 13

#define F(X)0

The argument is never expanded, so it cannot call any macros. It is nothing more than a bunch of plain text. Thus, the answer is always false.

Answer 8

C

#include <stdio.h>

int a, b;
#define foo(x) (b=a++,(void)x,a--,!!b)

int
main(int argc, char **argv)
{
        printf("%d\n", foo(1));
        printf("%d\n", foo(0));
        printf("%d\n", foo(foo(1)));
        printf("%d\n", foo(foo(foo(1))));
        return 0;
}

We can count the recursion depth in the macro. We then overwrite the return value of the outer macro in the inner macro. !!b is to normalize the return value to a boolean. The preprocessed code ends up like this:

int a, b;

int
main(int argc, char **argv)
{
 printf("%d\n", (b=a++,(void)1,a--,!!b));
 printf("%d\n", (b=a++,(void)0,a--,!!b));
 printf("%d\n", (b=a++,(void)(b=a++,(void)1,a--,!!b),a--,!!b));
 printf("%d\n", (b=a++,(void)(b=a++,(void)(b=a++,(void)1,a--,!!b),a--,!!b),a--,!!b));
 return 0;
}

Answer 9

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BLAH(x) (strncmp( "BLAH(", #x, strlen("BLAH(")) == 0)

int main(int argc, char** argv)
{
  printf("%d\n", BLAH(1));
  printf("%d\n", BLAH("1234"));
  printf("%d\n", BLAH("BLAH"));
  printf("%d\n", BLAH(BLAHA));
  printf("%d\n", BLAH(BLAHB()));
  printf("%d\n", BLAH(BLAH));
  printf("%d\n", BLAH(BLAH()));
  printf("%d\n", BLAH(BLAH("1234")));
  return 0;
}

The macro compares if its argument starts with "BLAH(".

Answer 10

Algol 60

Here's a boolean procedure that does what the question asks for (note: Algol 60 is defined in terms of a list of tokens without fixing syntax for them, the below uses Marst syntax to represent the individual tokens that make up the program):

boolean procedure recursion detector(n);
  boolean n;
  begin
    own boolean nested, seen nested;
    boolean was nested, retval;
    was nested := nested;
    begin if nested then seen nested := true end;
    nested := true;
    retval := n; comment "for the side effects, we ignore the result";
    nested := was nested;
    retval := seen nested;
    begin if ! nested then seen nested := false end;
    recursion detector := retval
  end;

Verification

Here's the test code I used:

procedure outboolean(c, b);
  integer c;
  boolean b;
  begin
    if b then outstring(c, "true\n") else outstring(c, "false\n")
  end;

begin
  outboolean(1, recursion detector(false));
  outboolean(1, recursion detector(true));
  outboolean(1, recursion detector(recursion detector(false)));
  outboolean(1, recursion detector(false | recursion detector(true)));
  outboolean(1, recursion detector(false & recursion detector(true)));
  outboolean(1, recursion detector(recursion detector(recursion detector(false))))
end

As expected, the output is:

false
false
true
true
true             comment "because & does not short-circuit in Algol 60";
true

Explanation

Algol 60 has a different evaluation order from most languages, which has a logic of its own, and is actually much more powerful and general than the typical evaluation order, but is fairly hard for humans to get their head around (and also fairly hard for computers to implement efficiently, which is why it got changed for Algol 68). This allows for a solution with no sort of cheating (the program doesn't need to look at the parse tree or anything like that, and unlike almost all the other solutions here, this would work just fine if the nested call were made via an FFI).

I also decided to show off a few other quirks of the language. (Notably, variable names can contain whitespace; this is fairly useful for readability, because they can't contain underscores. I also love the fact that the comment indicator is the literal word comment in most syntax encodings. Algol 68 found this fairly awkward for short comments, and introduced ¢ as an alternative. The quotes around the comment body aren't normally needed, I just add them for clarity and to prevent the comment accidentally ending when I type a semicolon.) I actually really like the broad concepts of the language (if not the details), but it's so verbose that I rarely get to use it on PPCG.

The main way in which Algol 60 differs from the languages it inspired (such as Algol 68, and indirectly C, Java, etc; people who know K&R C will probably recognise this syntax for functions) is that a function argument is treated a bit like a little lambda of its own; for example, if you give the argument 5 to a function that's just the number 5, but if you give it the argument x+1 you get exactly what you specified, the concept of "x plus 1", rather than the result of x plus 1. The difference here is that if x changes, then attempts to evaluate the function argument in question will see the new value of x. If a function argument isn't evaluated inside the function, it won't be evaluated outside the function either; likewise, if it's evaluated multiple times inside the function, it'll be evaluated separately each time (assuming that this can't be optimised out). This means that it's possible to do things like capture the functionality of, say, if or while in a function.

In this program, we're exploiting the fact that if a call to a function appears in an argument to that function, that means that the function will run recursively (because the argument is evaluated at exactly the point or points that the function evaluates it, no earlier or later, and this must necessarily be inside the function body). This reduces the problem to detecting if the function is running recursively, which is much easier; all you need is a thread-local variable that senses if there's a recursive call (plus, in this case, another one to communicate information back the other way). We can use a static variable (i.e. own) for the purpose, because Algol 60 is single-threaded. All we have to do after that is to put everything back the way it was, so that the function will function correctly if called multiple times (as required by PPCG rules).

The function doesn't return the desired value from the inside calls at the moment (at least if you assume they should look for self-calls in only their arguments, rather than counting themselves); making that work is fairly easy using the same general principles, but more complex and would obscure the workings of the function. If that's deemed necessary to comply with the question, it shouldn't be too hard to change.

Answer 11

Java

public class FuncOFunc{

private static int count = 0;

public static void main(String[] args){

    System.out.println("First\n" + function());
    reset();

    System.out.println("Second\n" + function(1));
    reset();

    System.out.println("Third\n" + function(function(1)));
    reset();

    System.out.println("Fourth\n" + function(3*function(1)+2));
    reset();

    System.out.println("Fifth\n" + function(function(1), function(), 4));
}

/**
 * @param args
 */
private static int function(Object...args) {
    StackTraceElement[] stackTraceElements = Thread.currentThread().getStackTrace();
    count+=stackTraceElements.length;
    if(count>3) return 1;
    else return 0;
}

static void reset(){
    count = 0;
}
}

can reset() be counted as auxiliary?

Output:

First
0
Second
0
Third
1
Fourth
1
Fifth
1

EDIT

Here is another version that doesn't use the reset() method, but a lot of madness. It creates and compiles at runtime the above code with the call to the function passed as an argument in stdin. I wanted a more elegant solution but sadly I don't have too much time for this :(

To run it simply call for example javac FuncOFunc.java function(function(1),function(),4).

import java.io.File;
import java.io.PrintWriter;
import java.net.URL;
import java.net.URLClassLoader;

import javax.tools.JavaCompiler;
import javax.tools.JavaFileObject;
import javax.tools.StandardJavaFileManager;
import javax.tools.ToolProvider;

public class FuncOFunc {
    public static void main(String[] args) throws Exception {
        JavaCompiler jc = ToolProvider.getSystemJavaCompiler();
        StandardJavaFileManager sjfm = jc.getStandardFileManager(null, null, null);
        File jf = new File("FuncOFuncOFunc.java");
        PrintWriter pw = new PrintWriter(jf);
        pw.println("public class FuncOFuncOFunc{"
                + "public static void main(){ "
                + "     System.out.println("+ args[0] +");"
                + "}"
                + "     private static int function(Object...args)     {"
                + "         StackTraceElement[] stackTraceElements = Thread.currentThread().getStackTrace();"
                + "         if(stackTraceElements.length>3) return 1;"
                + "         else return 0;"
                + "     }"
                + "}");
    pw.close();
    Iterable<? extends JavaFileObject> fO = sjfm.getJavaFileObjects(jf);
    if(!jc.getTask(null,sjfm,null,null,null,fO).call()) {
        throw new Exception("compilation failed");
    }
    URL[] urls = new URL[]{new File("").toURI().toURL()};
    URLClassLoader ucl = new URLClassLoader(urls);
    Object o= ucl.loadClass("FuncOFuncOFunc").newInstance();
    o.getClass().getMethod("main").invoke(o);
    ucl.close();
}
}

Answer 12

Python

import ast, inspect

def iscall(node, name, lineno=None):
    return isinstance(node, ast.Call) \
            and (node.lineno == lineno or lineno is None) \
            and hasattr(node.func, 'id') \
            and node.func.id == name

def find_call(node, name, lineno):
    for node in ast.walk(node):
        if iscall(node, name, lineno):
            return node

def is_call_in_args(call):
    descendants = ast.walk(call);
    name = next(descendants).func.id
    return any(map(lambda node: iscall(node, name), descendants))

def function(*args):
    this = inspect.currentframe()
    _, _, funcname, _, _ = inspect.getframeinfo(this)
    outer = inspect.getouterframes(this)[1]
    frame, filename, linenum, _, context, cindex = outer
    module = ast.parse(open(filename).read())
    call = find_call(module, funcname, linenum)
    return is_call_in_args(call)

if __name__ == '__main__':

    print("Works with these:")
    assert(function() == False)
    assert(function(3*function(1)+2) == True)
    assert(function(0) == False)
    assert(function(function(0)) == True)
    assert(function(True or function(1) == True))

    print("Does not work with multiple expressions on the same line:")
    assert(function(function()) == False); function()
    function(); assert(function(function()) == False)

Save it as selfarg.py and run it or from selfarg import function in another script. It does not work in the repl.

Using the current and outer stack frames function obtains its name and place of call (file and line number). It then opens the obtained file and parses it into an abstract syntax tree. It skips to the function call identified by the line number and inspects if it has another function call with the same name in its arguments.

edit: It's OK with python2 too. Changed python3 to python in the title.