Понимание рекурсии без базового случая в Джулии

Этот фрагмент из реализации Rational Numbers в Джулии:

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

# ...

Посмотрите, как реализована функция //, а затем используется с нотификацией infix? Как это действительно возвращает значение?

Когда я увидел этот код, я интерпретировал его так:

  • Функция // вызывается с помощью Rational и Integer.
  • Но тогда он делает рекурсивный вызов без каких-либо других аргументов.

# 2 - это тот, который меня действительно смущает. Где заканчивается рекурсия в структуре данных? Как // возвращает значение, если оно постоянно ничего не оценивает?

Пожалуйста, помогите мне понять это.

Ответы

Ответ 1

Это работает из-за одной из самых основных особенностей Julia: множественная отправка. В Julia функции могут иметь много методов, которые применяются к различным комбинациям типов аргументов, а когда вы вызываете функцию, Julia вызывает наиболее специфический метод, который соответствует типу всех аргументов, с которыми вы его вызывали. Вызов // в объявленном методе определяет рациональное целое число // в терминах integer-integer // - поэтому он не является фактически рекурсивным, потому что метод не вызывает себя, он вызывает другой метод, который является частью той же "общей функции".

Чтобы понять, как многократная диспетчеризация работает в этом случае, рассмотрим оценку выражения (3//4)//6. Мы будем использовать макрос @which, чтобы узнать, какой метод вызывает вызов каждой функции.

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

Так как 3//4 является Rational{Int} <: Rational, а 6 является Int <: Integer, и другие другие специфические методы не применяются, этот метод вызывается:

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

текущая версия метода на самом деле немного сложнее, чем вы опубликовали, потому что она была изменена для проверки переполнения целых чисел, но она по существу такая же, и она проще понять более старую, более простую версию, поэтому я буду использовать ее. Обозначим аргументы x и y и посмотрим, какой метод вызовет определение:

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

Как вы можете видеть, это выражение не вызывает тот же метод, он вызывает другой метод:

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

Этот метод просто вызывает конструктор Rational, который ставит отношение n и d в младшие члены и создает объект числа Rational.

Общепринято определить один метод функции в терминах другого метода той же функции, в Юлии. Так, например, работают аргументы по умолчанию. Рассмотрим это определение:

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

Синтаксис аргумента по умолчанию просто генерирует второй метод с единственным аргументом onee, который вызывает форму с двумя аргументами со значением по умолчанию. Таким образом, f(x, y=1) = 2x^y в точности эквивалентно определению двух методов, где унарный метод просто вызывает двоичный метод, задавая значение по умолчанию для второго аргумента:

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

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