Schreiben Sie eine Funktion (oder ein Makro), die genau dann true zurückgibt, wenn mindestens eines ihrer Argumente einen Aufruf der Funktion selbst enthält, andernfalls false .

Zum Beispiel:

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) 

BEARBEITEN: Die Funktion / das Makro kann andere Hilfsfunktionen / Makros aufrufen.

EDIT 2: Die Funktion muss mindestens ein Argument annehmen, es sei denn, die verwendete Sprache verhält sich wie C, wobei eine Funktion, die keine Argumente akzeptiert, dennoch mit Argumenten aufgerufen werden kann.

Mathematica ...

... wurde dafür gemacht .

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 *)

Alles ist ein Ausdruck, und ein Ausdruck hat einen Kopf und eine Reihe von Elementen. So 1+2ist es tatsächlich Plus[1,2]und {1,2}ist es tatsächlich List[1,2]. Dies bedeutet, dass wir jedem Ausdruck für den Kopf, an dem wir interessiert sind, entsprechen können - in diesem Fall der Funktion fselbst.

Alles, was wir tun müssen, ist einen Weg zu finden, um zu verhindern, dass Mathematica die Funktionsargumente auswertet, bevor die Funktion aufgerufen wird, sodass wir den Ausdrucksbaum innerhalb der Funktion analysieren können. Was ist was Holdund wofür HoldAll. Mathematica selbst verwendet dies überall, um Sonderfälle für bestimmte Implementierungen bereitzustellen. Wenn Sie Length[Permutations[list]]es beispielsweise aufrufen , werden niemals all diese Permutationen erstellt und viel Speicher verschwendet, sondern es wird stattdessen erkannt, dass es dies einfach als berechnen kann Length[list]!.

Schauen wir uns den obigen Code am f[True || f[1]]Beispiel des letzten Aufrufs genauer an. Normalerweise wertet Mathematica zuerst Funktionsargumente aus, sodass dies einfach kurzgeschlossen und aufgerufen wird f[True]. Wir haben uns jedoch eingestellt

SetAttributes[f, HoldAll]

Dies weist Mathematica an, die Argumente nicht auszuwerten, so dass der FullFormAufruf (dh der interne Ausdrucksbaum ohne syntaktischen Zucker) lautet

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

Und das Argument wird tatsächlich fin dieser Form empfangen . Das nächste Problem ist, dass fMathematica innerhalb von , sobald wir das Argument verwenden, erneut versuchen wird, es zu bewerten. Wir können dies lokal mit Hold@x(syntaktischer Zucker für Hold[x]) unterdrücken . An diesem Punkt haben wir den ursprünglichen Ausdrucksbaum im Griff und machen damit, was wir wollen.

Um nach einem Muster in einem Ausdrucksbaum zu suchen, können wir verwenden FreeQ. Es wird überprüft, ob ein bestimmtes Muster nicht im Ausdrucksbaum gefunden wird. Wir verwenden das Muster _f, das jedem Unterausdruck mit dem Kopf entspricht f(genau das, wonach wir suchen). Gibt natürlich FreeQdas Gegenteil von dem zurück, was wir wollen, also negieren wir das Ergebnis.

Noch eine Subtilität: Ich habe das Argument als x___eine Folge von 0 oder mehr Elementen angegeben. Dies stellt sicher, dass fmit einer beliebigen Anzahl von Argumenten funktioniert. Beim ersten Aufruf f[]bedeutet dies, dass Hold@xeinfach wird Hold[]. Wenn es mehrere Argumente gäbe f[0,f[1]], Hold@xwäre das so Hold[0,f[1]].

Das ist wirklich alles.

C ++ 11

Ähnlich wie bei Ausdrucksvorlagen können wir die Tatsache verbreiten, dass wir die Funktion in einer Funktionsparameterliste in ihrem Rückgabetyp aufgerufen haben.

Zuerst brauchen wir einige Hilfsklassen und Funktionen:

#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!

Jetzt können wir es für genau den gleichen Code wie in der Frage verwenden:

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";
}

Ausgabe von ideone:

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

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);
    }
}

Verwendung (in LINQPad ):

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

Der Trick dabei ist, fdie Parameter besser bekannt zu machen , indem ein benutzerdefinierter Typ ( PcgBool) übergeben wird, der einem Booleschen Wert ähnelt.

PS Ich hoffe, dass die Rückgabe eines benutzerdefinierten Typs, der implizit von und zu einem Bool umgewandelt werden kann, nicht als Betrug angesehen wird. Technisch gesehen können Sie den Rückgabewert so verwenden, als wäre er vom Typ bool, und die Frage lautet "return true if and only if" usw., ohne jedoch anzugeben, dass der Rückgabetyp bool sein muss.

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())))

C ++ 11 TMP

Dieser ist etwas länger. Aufgrund einiger Einschränkungen in C ++ - Vorlagen musste ich alles mit Typen machen. So wurden "True" sowie die Zahlen in bool und int umgewandelt. Auch die Operationen +, - und || wurden in add, mul und or_ umgewandelt.

Ich hoffe, dass dies immer noch eine gültige Antwort ist.

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;
}

C.

Ich denke nicht, dass dies mit Prozeduren möglich ist, aber wir können immer (ab) Makros verwenden.

#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)))));
}

Dies gibt aus:

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

Unser Makro fverfolgt die aktuelle Tiefe und die maximale Tiefe, die seit dem Aufruf erreicht wurde. Wenn das letztere größer als das erstere ist, wurde es rekursiv aufgerufen.

C, 13

#define F(X)0

Das Argument wird nie erweitert, daher können keine Makros aufgerufen werden. Es ist nichts weiter als ein Haufen Klartext. Somit ist die Antwort immer falsch.

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;
}

Wir können die Rekursionstiefe im Makro zählen. Wir überschreiben dann den Rückgabewert des äußeren Makros im inneren Makro. !!bist es, den Rückgabewert auf einen Booleschen Wert zu normalisieren. Der vorverarbeitete Code endet wie folgt:

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;
}

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;
}

Das Makro vergleicht, ob sein Argument mit "BLAH (" beginnt).

Algol 60

Hier ist eine Funktion boolean procedure, die genau das tut, wonach die Frage verlangt (Hinweis: Algol 60 wird anhand einer Liste von Token definiert, ohne dass die Syntax für diese festgelegt wird. Im Folgenden wird die Marst-Syntax verwendet, um die einzelnen Token darzustellen, aus denen das Programm besteht):

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;

Nachprüfung

Hier ist der Testcode, den ich verwendet habe:

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

Wie erwartet ist die Ausgabe:

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

Erläuterung

Algol 60 hat eine andere Bewertungsreihenfolge als die meisten Sprachen, die eine eigene Logik hat und tatsächlich viel leistungsfähiger und allgemeiner als die typische Bewertungsreihenfolge ist, aber für Menschen ziemlich schwer zu verstehen ist (und auch ziemlich schwer für Computer effizient zu implementieren, weshalb es für Algol geändert wurde 68). Dies ermöglicht eine Lösung ohne Betrug (das Programm muss nicht auf den Analysebaum oder ähnliches schauen, und im Gegensatz zu fast allen anderen Lösungen hier würde dies gut funktionieren, wenn der verschachtelte Aufruf über eine erfolgt wäre FFI).

Ich beschloss auch, ein paar andere Macken der Sprache zu zeigen. (Insbesondere können Variablennamen Leerzeichen enthalten. Dies ist für die Lesbarkeit ziemlich nützlich, da sie keine Unterstriche enthalten können. Ich mag auch die Tatsache, dass der Kommentarindikator das wörtliche Wort commentin den meisten Syntaxcodierungen ist. Algol 68 fand dies kurz gesagt ziemlich umständlich Kommentare und ¢als Alternative eingeführt. Die Anführungszeichen um den Kommentarkörper werden normalerweise nicht benötigt. Ich füge sie nur hinzu, um Klarheit zu schaffen und um zu verhindern, dass der Kommentar versehentlich endet, wenn ich ein Semikolon eingebe.) Ich mag die allgemeinen Konzepte der Sprache wirklich sehr (wenn nicht die Details), aber es ist so ausführlich, dass ich es selten auf PPCG verwenden kann.

Algol 60 unterscheidet sich hauptsächlich von den Sprachen, die es inspiriert hat (wie Algol 68 und indirekt C, Java usw .; Leute, die K & R C kennen, werden diese Syntax für Funktionen wahrscheinlich erkennen), dass ein Funktionsargument ein bisschen wie behandelt wird ein kleines Lambda für sich; Wenn Sie beispielsweise das Argument 5einer Funktion geben, die nur die Zahl 5 ist, aber wenn Sie das Argument x+1angeben, erhalten Sie genau das, was Sie angegeben haben, das Konzept von " xplus 1" und nicht das Ergebnis von xplus 1. Der Unterschied hier Wenn xÄnderungen vorgenommen werden, wird beim Versuch, das betreffende Funktionsargument auszuwerten, der neue Wert von angezeigtx. Wenn ein Funktionsargument nicht innerhalb der Funktion ausgewertet wird, wird es auch nicht außerhalb der Funktion ausgewertet. Wenn es innerhalb der Funktion mehrmals ausgewertet wird, wird es jedes Mal separat ausgewertet (vorausgesetzt, dies kann nicht optimiert werden). Dies bedeutet, dass es möglich ist, beispielsweise die Funktionalität von ifoder whilein einer Funktion zu erfassen .

In diesem Programm nutzen wir die Tatsache, dass, wenn ein Aufruf einer Funktion in einem Argument für diese Funktion erscheint, die Funktion rekursiv ausgeführt wird (da das Argument genau an dem Punkt oder den Punkten ausgewertet wird, an denen die Funktion es auswertet nicht früher oder später, und dies muss notwendigerweise innerhalb des Funktionskörpers sein). Dies reduziert das Problem auf das Erkennen, ob die Funktion rekursiv ausgeführt wird, was viel einfacher ist. Alles, was Sie benötigen, ist eine threadlokale Variable, die erkennt, ob ein rekursiver Aufruf vorliegt (und in diesem Fall eine weitere, um Informationen in die andere Richtung zu übertragen). Wir können eine statische Variable verwenden (dhown) zu diesem Zweck, da Algol 60 Single-Threaded ist. Danach müssen wir nur noch alles so zurücksetzen, wie es war, damit die Funktion bei mehrmaligem Aufruf korrekt funktioniert (gemäß den PPCG-Regeln).

Die Funktion gibt im Moment nicht den gewünschten Wert aus den internen Aufrufen zurück (zumindest wenn Sie davon ausgehen, dass sie nur in ihren Argumenten nach Selbstaufrufen suchen sollten , anstatt sich selbst zu zählen). Diese Arbeit zu machen ist ziemlich einfach, wenn man dieselben allgemeinen Prinzipien verwendet, aber komplexer und würde die Funktionsweise der Funktion verdecken. Wenn dies zur Beantwortung der Frage als notwendig erachtet wird, sollte es nicht zu schwierig sein, dies zu ändern.

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;
}
}

kann reset()als Hilfsmittel gezählt werden?

Ausgabe:

First
0
Second
0
Third
1
Fourth
1
Fifth
1

BEARBEITEN

Hier ist eine andere Version, die diese reset()Methode nicht verwendet , aber viel Wahnsinn. Es erstellt und kompiliert zur Laufzeit den obigen Code mit dem Aufruf der Funktion, die als Argument in stdin übergeben wird. Ich wollte eine elegantere Lösung, aber leider habe ich nicht zu viel Zeit dafür :(

Um es auszuführen, rufen Sie einfach zum Beispiel auf 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();
}
}

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)

Speichern Sie es als selfarg.pyund führen Sie es oder from selfarg import functionin einem anderen Skript aus. Es funktioniert nicht in der Antwort.

Bei Verwendung des aktuellen und des äußeren Stapelrahmens werden functionName und Ort des Aufrufs (Datei- und Zeilennummer) ermittelt. Anschließend wird die erhaltene Datei geöffnet und in einen abstrakten Syntaxbaum analysiert. Es springt zu dem durch die Zeilennummer gekennzeichneten Funktionsaufruf und prüft, ob seine Argumente einen anderen Funktionsaufruf mit demselben Namen enthalten.

edit : Auch mit python2 ist es in Ordnung. Python3 wurde im Titel in Python geändert.