2

我想在 Julia 中实现一种简单的连接语言（又名 Joy 或 Factor）作为 DSL，我很困惑如何以最佳方式表示堆栈。

代表数据和程序代码的堆栈应该能够保存一系列不同类型的项目。在最简单的情况下，Ints、Symbols 以及递归的堆栈（以表示引用的代码）。然后该程序将大量使用推送！和流行！在不同的此类堆栈之间打乱值。

Julia 中一个明显的实现是使用元胞数组，它有效但运行速度相当慢。例如，以下 Joy 堆栈[ 1 [ 1 2 +] i + ]（计算结果为[4]）可以在 Julia 中实现为 stack = Any[:+,:i,Any[:+,2,1],1]。我的典型代码如下所示：

x = pop!(callstack)
if isa(x,Int)
   push!(x,datastack)
elseif isa(x,Symbol)
   do_stuff(x,datastack)
end

然而，这运行速度非常慢并且使用了巨大的内存分配，可能是因为这样的代码不是可类型化的（这是 Julia 的一个很大的性能瓶颈）。

使用 C，我会将堆栈紧凑地表示为联合的数组（或链表）：

typedef union Stackelem{
    int val;
    char *sym;
    union Stackelem *quote;
} Stackelem;

Stackelem stack[n];

但是如何在 Julia 中实现异构堆栈的如此紧凑的表示，以及如何避免类型不稳定性？

4

1 回答 1

3

这是一种方式，另一种方式是用 Vector{Any} 类型表示 args：

julia> immutable Exp
          head::Symbol
          args::Tuple
       end

julia> q = Exp(:+, (1, Exp(:-, (3, 4))))
Exp(:+,(1,Exp(:-,(3,4))))

编辑：表示它的另一种方式可能是：

immutable QuoteExp{T} ; vec::Vector{T} ; end
typealias ExpTyp Union{QuoteExp, Int, Symbol}
typealias Exp QuoteExp{ExpTyp}

然后您可以执行以下操作：

julia> x = Exp(ExpTyp[:+, 1, 2])
QuoteExp{Union{Int64,QuoteExp{T},Symbol}}(Union{Int64,QuoteExp{T},Symbol}[:+,1,2])
julia> x.vec[1]
:+
julia> x.vec[2]
1
julia> x.vec[3]
2
julia> push!(x.vec,:Scott)
4-element Array{Union{Int64,QuoteExp{T},Symbol},1}:
  :+    
 1      
 2      
  :Scott
julia> x.vec[4]
:Scott
于 2016-03-29T23:59:04.387 回答