8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does it have to work in a context like print(func(), func(func())), or will there only ever be a top-level call to the function right after it has been defined? \$\endgroup\$ – algorithmshark Jun 23 '14 at 1:22
  • \$\begingroup\$ It should work in that situation. \$\endgroup\$ – user26458 Jun 23 '14 at 1:27
  • 10
    \$\begingroup\$ Why accept so quickly? \$\endgroup\$ – Kyle Kanos Jun 23 '14 at 2:00
  • 1
    \$\begingroup\$ I dislike this question because it's only solvable in languages that allow you to examine the expression tree at runtime. \$\endgroup\$ – FUZxxl Feb 24 '15 at 19:37
  • 1
    \$\begingroup\$ @FUZxxl: I disagree; I've just posted an answer which works just fine even if the calls go indirectly through an FFI (and thus the expression tree of the interior functions can't be viewed). \$\endgroup\$ – user62131 Apr 20 '17 at 0:48

12 Answers 12

12
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What about f(new PcgBool())? \$\endgroup\$ – Qwertiy Feb 26 '15 at 8:07
  • \$\begingroup\$ Hmm... You are right about that one. It does look like it brakes my answer. Unfortunately, I'm too lazy to fix it by now (it's been a while...) \$\endgroup\$ – Jacob Feb 26 '15 at 8:57
3
\$\begingroup\$

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())))
\$\endgroup\$
  • \$\begingroup\$ And I was thinking of a way to compare tables recursively. Well done, I didn't think debug could be that powerful! \$\endgroup\$ – YoYoYonnY Feb 26 '15 at 21:31
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Really nice! What rule causes the second definition of is_given_foo to be preferred to the first one? \$\endgroup\$ – feersum Feb 25 '15 at 16:47
  • \$\begingroup\$ Maybe some one can help me, because I was not able to find the right place in the standard to cite. Anyway as the second is_given_foo is a template specialization of the first one it is always preferred when the template parameter(s) match the given pattern, in that case when the parameter is a template itself. \$\endgroup\$ – Felix Bytow Feb 26 '15 at 11:09
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Heh. We ended up with more or less the same solution at more or less the same time. \$\endgroup\$ – Art Jun 24 '14 at 11:19
  • \$\begingroup\$ @Art LOL. Also, I feel very silly now, as I wasn't aware of the comma operator (since C's somewhere around my 4th or 5th choice language), which I hacked around using && and ||. I may try to redeem my answer. \$\endgroup\$ – James_pic Jun 24 '14 at 11:26
  • \$\begingroup\$ Well, the comma operator is just for an extra layer of obfuscation. I'd never use it in normal code. But in this case I confused myself when trying to use logical operators. \$\endgroup\$ – Art Jun 24 '14 at 11:29
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is really a brilliant answer. \$\endgroup\$ – FUZxxl Feb 25 '15 at 13:36
  • \$\begingroup\$ Came across this while looking at old preprocessor posts... actually, this is wrong. F(F(0)) will happily first evaluate F's argument, F(0). That argument expands to 0. Then it evaluates F without blue paint on its argument of 0, resulting in 0. The non-recursive restriction does not apply; that's when e.g. I have #define F(X) G and #define G F(Y) is in play; in this case, while expanding F(0) to G, and then to F(Y), the token F appears. Because I'm currently expanding F, F has blue paint in this case, and thus the expansion stops at F(Y). \$\endgroup\$ – H Walters Aug 29 '16 at 4:03
  • \$\begingroup\$ @HWalters Wow, you're right. What do you think of my new explanation? \$\endgroup\$ – feersum Aug 29 '16 at 5:48
  • \$\begingroup\$ So it sounds like now you're saying that since X isn't in the argument replacement list, whatever macros were bound to it are never expanded. If we interpret that as a function being called, that means the argument's functions are never called. Yes, I think that's correct. \$\endgroup\$ – H Walters Aug 29 '16 at 6:54
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ What about the (admittedly very silly) case of printf("%d\n", foo(printf("%d\n", foo(1)))). The inner call to foo returns 1, but doesn't call foo. \$\endgroup\$ – James_pic Jun 24 '14 at 11:33
1
\$\begingroup\$

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(".

\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't work on BLAH(blub(BLAH(0))). \$\endgroup\$ – FUZxxl Feb 25 '15 at 13:36
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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();
}
}
\$\endgroup\$
  • \$\begingroup\$ I don't believe you can force the usage to invoke reset() after each function invocation. The idea of auxiliary functions is to allow you invoking other private methods from within function's body... But that's only my interpretation of the question, let's leave it to the asker to decide. \$\endgroup\$ – Jacob Jun 24 '14 at 6:08
  • \$\begingroup\$ I have the same feeling... Let's wait for the OP to clarify this point. Meanwhile I'm working for a reset()less version. Still the code above works if there is only one call in the main (without the variable count and the reset function) \$\endgroup\$ – Narmer Jun 24 '14 at 7:09
  • 1
    \$\begingroup\$ Sorry about the lack of clarity, but I meant what Jacob said by auxiliary function. Also, the 1st code you wrote will return "true" if any method, not just function(), is called inside function(...), won't it? \$\endgroup\$ – user26458 Jun 24 '14 at 18:17
  • \$\begingroup\$ Your edit has to be some of the worst code I have ever seen. Have a +1. \$\endgroup\$ – Cruncher Jun 25 '14 at 18:15
  • \$\begingroup\$ Ahaha! Thanks! That's what happens when trying to be creative with no creativity and very little time... That's probably the worst thing I ever made in java. Still compiles though! \$\endgroup\$ – Narmer Jun 26 '14 at 7:08
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy