Verständnis Rekursion ohne Basisfall in Julia

Question

Dieser Ausschnitt ist aus der Umsetzung von Rational Numbers in Julia:

# Rational.jl 
# ... 
Rational{T<:Integer}(n::T, d::T) = Rational{T}(n,d) 
Rational(n::Integer, d::Integer) = Rational(promote(n,d)...) 
Rational(n::Integer) = Rational(n,one(n)) 

//(x::Rational, y::Integer) = x.num // (x.den*y) <--- HERE! 

# ... 

Sehen Sie, wie die // Funktion implementiert ist und dann mit Infixschreibweise verwendet? Wie liefert das tatsächlich einen Wert zurück?

Wenn ich diesen Code sah ich es wie folgt interpretiert:

1. Die // Funktion mit einem Rational und Integer genannt wird.
2. Aber dann macht es einen rekursiven Aufruf mit keinen anderen Argumenten.

# 2 ist derjenige, der mich wirklich verwirrt. Wo endet die Rekursion innerhalb der Datenstruktur? Wie liefert // einen Wert zurück, wenn er ständig nichts auswertet?

Bitte helfen Sie mir, dies zu verstehen.

Answer 1

Dies funktioniert wegen einer der grundlegenden Funktionen von Julia: Multiple Dispatch. In Julia können Funktionen viele Methoden haben, die für verschiedene Kombinationen von Argumenttypen gelten. Wenn Sie eine Funktion aufrufen, ruft Julia die spezifischste Methode auf, die dem Typ aller Argumente entspricht, mit denen Sie sie aufgerufen haben. Der Aufruf // in der von Ihnen geposteten Methodendefinition definiert rational-Integer // als Ganzzahl-Integer // - also ist es eigentlich nicht rekursiv, weil die Methode sich nicht selbst aufruft, sondern eine andere Methode aufruft, die Teil desselben ist. generische Funktion ".

Um zu verstehen, wie die Mehrfachversendung in diesem Fall funktioniert, betrachten wir die Auswertung des Ausdrucks (3//4)//6. Wir werden das @which Makro verwenden, um zu sehen, welche Methode jeder Funktionsaufruf aufruft.

julia> @which (3//4)//6 
//(x::Rational{T<:Integer}, y::Integer) at rational.jl:25 

Seit 3//4 ist ein Rational{Int} <: Rational und 6 ein Int <: Integer ist, und keine andere spezifischere Methoden anwenden, diese Methode aufgerufen wird:

//(x::Rational, y::Integer) = x.num // (x.den*y) 

The current version des Verfahrens, als tatsächlich etwas komplizierter ist, was Du hast gepostet, weil es geändert wurde, um nach einem Integer-Überlauf zu suchen - aber es ist im Wesentlichen das Gleiche, und es ist einfacher, die ältere, einfachere Version zu verstehen, also werde ich das verwenden. Lassen Sie uns x und y den Argumenten zuordnen und sehen, welche Methode die Definition nennt:

julia> x, y = (3//4), 6 
(3//4,6) 

julia> x.num 
3 

julia> x.den*y 
24 

julia> x.num // (x.den*y) 
1//8 

julia> @which x.num // (x.den*y) 
//(n::Integer, d::Integer) at rational.jl:22 

Wie Sie sehen können, ist dieser Ausdruck die gleiche Methode nicht nennen, es ruft eine different method:

//(n::Integer, d::Integer) = Rational(n,d) 

Diese Methode ruft einfach den Konstruktor Rational auf, der das Verhältnis n und d in die niedrigsten Begriffe einfügt und ein Rational Nummernobjekt erstellt.

Es ist ziemlich üblich, eine Methode einer Funktion in Bezug auf eine andere Methode der gleichen Funktion in Julia zu definieren. So funktionieren beispielsweise die Standardvorgaben für Argumente.Betrachten wir diese Definition:

julia> f(x, y=1) = 2x^y 
f (generic function with 2 methods) 

julia> methods(f) 
# 2 methods for generic function "f": 
f(x) at none:1 
f(x, y) at none:1 

julia> f(1) 
2 

julia> f(2) 
4 

julia> f(2,2) 
8 

Die Standardargument Syntax erzeugt einfach ein zweites Verfahren mit nur onee Argument, das die zwei Argumenten mit dem Standardwert aufruft. So f(x, y=1) = 2x^y entspricht genau zwei Methoden zu definieren, wobei die unäre Verfahren nur die binäre Methode aufrufen, einen Standardwert für das zweite Argument an:

julia> f(x, y) = 2x^y 
f (generic function with 1 method) 

julia> f(x) = f(x, 1) 
f (generic function with 2 methods)