在Julia中理解没有基本情况的递归

Question

这个片段来自Julia 中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!

# ...

查看//函数如何实现,然后与中缀表示法一起使用？这实际上如何返回一个值？

当我看到这段代码时,我解释如下:

1. //使用Rational和Integer调用该函数.
2. 但是它会在没有其他参数的情况下进行递归调用.

#2真的让我很困惑.数据结构中的递归在哪里结束？//如果不断评估任何值,如何返回值？

请帮我理解这个.

Answer 1

这是因为Julia最基本的功能之一:多次调度.在Julia中,函数可以有许多方法适用于参数类型的各种组合,当您调用函数时,Julia会调用最具体的方法,该方法与您调用它的所有参数的类型相匹配.//您发布的方法定义中的调用按整数整数定义了有理//整数//- 因此它实际上不是递归的,因为该方法不会调用自身,它调用的是另一个属于同一"泛型函数"的方法.

为了理解在这种情况下多个调度如何工作,让我们考虑表达式的评估(3//4)//6.我们将使用@which宏来查看每个函数调用调用的方法.

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

由于3//4是a Rational{Int} <: Rational和6a 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中,根据同一函数的另一种方法定义函数的一种方法是很常见的.例如,这就是参数默认值的工作方式.考虑这个定义:

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)