Coding Poet, Coding Science

Julia类型系统与并发

一般认为有类型系统的编程语言分成静态类型系统与动态类型系统两大类。静态系统指的是每个程序表达式在程序执行之前都有一个可以计算的类型。而动态类型的类型,只是在运行的期间才被感知。面向对象的编程实践中,经常是在静态类型系统中添加一些灵活的机制。如果代码能够操作不同的类型,便称为是多态。在经典动态类型系统中,多态是显而易见的。

在理解动态系统的时候,需要注意binding与dispatch的区别。具体地说,绑定是把一个名子与一个类型关联起来,而dispatch指的是给出了方法,然后确定由哪个实现来执行这个方法。Julia’s type system is dynamic, but gains some of the advantages of static type systems by making it possible to indicate that certain values are of specific types. This can be of great assistance in generating efficient code, but even more significantly, it allows method dispatch on the types of function arguments to be deeply integrated with the language. Method dispatch is explored in detail in Methods, but is rooted in the type system presented here.

按照类型系统的理论,Julia属于那种dynamic, nominative, parametric类型。在Julia中,又有具体类型与抽象类型的区别。在Julia当中,所有的值都是一个真正的对象,而每一个真正的对象都有一个类型。整个类型系统是全连同的type graph。在Julia的世界中,“编译期类型”是没有意义的,因为只有“运行期类型”。

另外,在Julia中,只有值是有类型的,变量只是一个名称,具体地说,变量是与某个类型范围相绑定的名称而已。

在Julia中,也可以添加一些显式的类型声明,使用 :: 来表示。有时候,可以当成是运算符来对待,就像是关系运算符一样,比如(1+2)::FloatingPoint会引发程序错误,但是(1+2)::Int则会正常返回结果。也就是运算符的结果有两种:一种结果是引发程序停止,抛出异常,另外一种,就好像是完全不起作用一样。::相当于一个类型断言。

在出现变量的任何的地方,包括形参当中,都可以使用类型断言。

类型也是我们可以抽象地定义的。比如abstract name <: supertype定义了一个上界为supertype的类型(不过,它到底算是一个类型变量呢,还是一个类型常量呢?)。上界有时候可以省略。(不过,也许这不成为问题,因为没有说类型系统的结构是一个线必序集,它只需要是一个偏序集就可以了)。抽象类型的超类是所谓的Any类型。

Thus, abstract types allow programmers to write generic functions that can later be used as the default method by many combinations of concrete types. Thanks to multiple dispatch, the programmer has full control over whether the default or more specific method is used.

另外,具体类型可能是指的在程序运行期间会占据值的那些类型。比如具体的无符号短整型数据。比如bitstype 16 Float16 <: FloatingPoint就定义了一个具体的“比特类型”。

具体类型与抽象类型的区别可能在于,具体类型是负责实际的操作的,而抽象类型则提供的仅仅是检查操作合法性的功能。也就是抽象类型可以看成是纯粹的逻辑检查,但是具体类型则同时是与内存分配相绑定的。

Julia的类型可以进行组合,就像是结构体那样(其实语法与C的结构体类似)。

type Foo
bar
baz::Int
qux::Float64
end

可以使用构造函数来产生新类,以及给某个类型的变量新的值。(不使用new方法)。

另外,如果定义的一个类型完全没有任何的成员,比如

type NoField
end

那么,这个类型就对应着一个单件(singleton)。使用is(NoFields(), NoFields())得到的结果就是true(is用于判断两个对象是否是同一个对象)。

如果需要不可变类型,那么就在类型声明中,用immutable关键字代替type。看起来,不可变类型的每一次求值的时候都需要新的内存空间。但是其实问题没有这么简单。实现不可变类型的开销,可能并不比可变类型高多少。在Julia当中,可变类型是按照引用传递的,而不可变类型中通过copy来赋值的。这意味着把变量赋给一个可变类型的时候,并不会创建一个新的对象。

抽象类型、比特类型、组合类型是Julia的三种基本类型。此外,Julia还支持元组类型,也就是用(Int, String)来当成新的类型。这种类型之间也是可以比较的。另外,类型还可以合并起来,比如IntOrString = Union(Int, String),表示这个东西为一个整数或者字符型。

为了支持泛型编程,Julia还有含参类型。含参类型有一个类型参数。比如


type Point{T}
x::T
y::T
end

使用 Point{Float64} 可以构造出一个类。它就好像是Point这个类具有一个类型参数,当类型参数给出来的时候,Point类就调用它的构造函数,然后生成一个新的类型一样。注意Point是抽象类型,但是构造出来的是具体类型。

In other words, in the parlance of type theory, Julia’s type parameters are invariant, rather than being covariant (or even contravariant). This is for practical reasons: while any instance of Point{Float64} may conceptually be like an instance of Point{Real} as well, the two types have different representations in memory:

这真的应该参考类型理论了。

在Julia当中,函数是一个把一个参数元组映射一个返回值的类型。所以,在实践中,函数是非常抽象的类型概念。而在Julia中,把函数的实现,也就是把具体的执行看成是一个方法。显然可能会有多种对应。这种对应的过程称为分派(dispatch)。

The choice of which method to execute when a function is applied is called dispatch. Julia allows the dispatch process to choose which of a function’s methods to call based on the number of arguments given, and on the types of all of the function’s arguments. This is different than traditional object-oriented languages, where dispatch occurs based only on the first argument, which often has a special argument syntax, and is sometimes implied rather than explicitly written as an argument. [1] Using all of a function’s arguments to choose which method should be invoked, rather than just the first, is known as multiple dispatch. Multiple dispatch is particularly useful for mathematical code, where it makes little sense to artificially deem the operations to “belong” to one argument more than any of the others: does the addition operation in x + y belong to x any more than it does to y? The implementation of a mathematical operator generally depends on the types of all of its arguments. Even beyond mathematical operations, however, multiple dispatch ends up being a powerful and convenient paradigm for structuring and organizing programs.

里面提出一个不依赖于算术优先级文法的概念,比如x+y为什么调用的是x的方法而不是调用的y的方法?这个问题的提出的情景是这样的,对于一般的函数而言,可能应用的方法是很简单的,很确定,因为f(x,y)很容易确定是哪个函数。但是如果函数采用的是中缀的形式,那么问题就出现了。在出现中缀的地方,可能dispatch的意义更大。对于a f b这样形式的函数,我们知道f是一个纯粹的标签而已,但是这个方法是独立的方法,还是a的一个方法,或者b的方法。在多种可能的情况下,dispatch就显得必要了。

还有,如果参数允许多种类型的话,那么实际上函数代码中的行为也是不确定的。

function f(a,b)
 a +b 
end

对于这种情况,如果a是整数,那么+调用的是整型的+方法;但是a也可以是浮点类型,这样的话,就要调用不同的方法了。如果把+看成是一个方法的话,那么,确实+绑定的是哪一个方法是不确定的。但是在C++当中就没有这样的问题。

利用methods(f)可以查看当前的名子有多少种定义。比如+号,有92种定义。

table = methods(+)
length(table)

multiple Dispatch(多重分派)机制可以产生神奇的效果,比如

same_type{T}(x::T, y::T) = true
same_type(x,y) = false

上面的代码实际上是两个函数的定义,但是前一个定义的优先级更高,所以使用这种方法,可以实现一个判断两个变量的类型是否相等的函数。但是实际的执行是这样的:如果两个类型相同,调用的是第一个定义的方法;如果是其它情况,就匹配到后一个方法。结果,这样就可以调用same_type了。但是定义的方式确实是很特殊的。从中我们可以很明显地看到,同一个函数,可以绑定到不同的方法,而且是在运行期间决定的。

判断是否是同一个函数有一些不同的标准。如果仅仅看名称,就是Julia这里的。但是数学上,也许更习惯把函数的参数类型也当成函数的一部分,那时候就有不同的处理的方式。不过在动态类型的语言中,区分“函数”与“方法”确实是有必要的。

具有可选参数的函数,实际上在定义的时候同时产生了几种不同的方法。

f(a=1,b=2) = a + b
methods(f)

将会查看到f有三个方法绑定。(这种情况下,似乎只要定义函数的时候使用了模式匹配,并且分成了多个句子,似乎都可以看成是多分派的语言了)。

构造函数

在Julia当中,构造子被理解成创建新的对象的函数。这与面向对象语言有一些不同(面向对象倾向于把构造函数理解成类的初始化的过程)。不过,在函数式与面向对象的结合中,把构造子理解成创建新对象的函数确实是更好一些。

在函数式与面向对象的结合的过程中,区分外部构造方法与内部构造方法有一些必要。外部构造方法就是像函数式那样,由一个与类同名的,但是不属于这个类的函数构成。而内部构造方法,则在声明类型的过程中,在类型里面的那些与类同名的函数。

如何在类里面使用这个类的一个对象?这个看起来是很困难的。但是Julia允许这么做而不出现问题。

参数类型提升

这基本是和类型转换一个含义。关键在于是否允许自动类型提升。在分类上,Julia是属于那类不允许自动类型转换的语言。使用convert(Type, var)来进行显式的转换。

Julia的模块

模块使用module来声明,使用export来导出可被利用的函数,使用using或者import来应用。

元编程语言:The strongest legacy of Lisp in the Julia language is its metaprogramming support. Like Lisp, Julia represents its own code as a data structure of the language itself. Since code is represented by objects that can be created and manipulated from within the language, it is possible for a program to transform and generate its own code. This allows sophisticated code generation without extra build steps, and also allows true Lisp-style macros operating at the level of abstract syntax trees. In contrast, preprocessor “macro” systems, like that of C and C++, perform textual manipulation and substitution before any actual parsing or interpretation occurs. Because all data types and code in Julia are represented by Julia data structures, powerful reflection capabilities are available to explore the internals of a program and its types just like any other data.

元编程是把程序与数据混在一起,可以把数据当成程序看待。比如parse(“1+1”),把字符串1+1当成Julia代码。这种机制下,显然是运行期的特性,而且还要暴露编译器的结构。

利用dump(),还可以把程序变成数据(序列化的一种)。

介于字符串数据与程序之间的是所谓的symbol。一个symbol使用:symbolname来声明。symbol是不可变类型,因此:foo = symbol(“foo”)。symbol里面可以是任何的表达式,所以ex = :(a+b*c+1)也是合法的表达式。使用ex = :(\(a+b*\)c+1)的时候,带美元符号的变量会被立即被其值替换。

表达式可以使用eval()函数,根据当前的程序的上下文求出值。这对于符号计算来说可能是必须的。

元编程与宏又比较接近了。

Julia的异步与并行支持

按理说这应该是重点所在,但是现在还不容易理解它们。Julia使用Task的概念来描述一个异步过程。

运行julia -p n可以开启一个n个工作进程的程序。使用remotecall()可以调用另外线程的程序,借此可以实现并行编程的功能。

//julia -p 4
r = remotecall(2, rand, 2,2)
fetch(r)

The first argument to remotecall() is the index of the process that will do the work. Most parallel programming in Julia does not reference specific processes or the number of processes available, but remotecall() is considered a low-level interface providing finer control. The second argument to remotecall() is the function to call, and the remaining arguments will be passed to this function. As you can see, in the first line we asked process 2 to construct a 2-by-2 random matrix, and in the second line we asked it to add 1 to it. The result of both calculations is available in the two remote references, r and s. The @spawnat macro evaluates the expression in the second argument on the process specified by the first argument.

通过并行编程的方法也是使用装饰器。它可以把Julia的模块分散到多个工作进程中。

个人认为,在并行计算的情况下,如何保证机器不会运行在内存不够而经常使用交换空间,以及让机器随时能够保持响应是关键的。因为在并行计算的时候,总是要消耗很多的资源。但是确定资源是否够用也很重要。如果不够用,那就只能进入死机状态了。

Julia对于SSH方式工作也有支持。可以用来管理不同的机器。

运行Shell命令,使用 run(`echo hello`) 。其中左单引号表示一个外部程序。括号里面的美元符号里面的变量,同样地会被替换。

Julia对外部程序的支持是非常全面的,可以参考 http://docs.julialang.org/en/release-0.3/manual/running-external-programs/ 。管道等方式的运用,就好像是在Shell自身当中一样。通过julia.h,也可以在C中嵌入Julia的代码。

Julia的包管理功能

包管理功能是通过github来实现的。通过Pkg来管理。

@time装饰器可以在执行代码的时候显示时间和内存使用报告。

其实Julia实现这么多的特性,靠的大多也还是装饰器。在Base.Test中提供了大量的装饰器。

Jeff: Julia基于多分派(multiple dispatch)。这是一种强大的面向对象编程机制,以前其他语言也用过,但出于某些原因从未真正流行起来。我们设计的多分派旨在定义具有多种形式和行为的数学函数,事实证明它也能用于其他情形。它在“你能表达什么”和“编译器能用它做什么”之间达到了很好的平衡。

Julia的更多的特性

感觉之前在看Julia的维基百科的时候自己都没有看仔细,漏掉了很多的重要的东西。比如在Julia中,有几个非常有用的软件包,PyPlot与SIUnits。

以及比较重要的一类调用其它语言的代码的宏包JavaCall、Mathematica。两者分别可以实现在Julia中调用Java与Mathematica的代码。在维基百科上还介绍了使用Julia调用Torch的代码的程序。使用Spark可以调用Spark,以及调用Hadoop的大数据。虽然Julia使用积极求值的策略,但是通过Lazy.jl包,也可以实现惰性求值。

通过Rcall可以在Julia中调用R,反过来,通过RJulia可以在R里调用Julia。

虽然支持Lisp-like宏,但是大多数时候,宏是不向应用程序的开发者提供的。就像Java中的Lambda与反射一样。