Как изобразить производительный гетерогенный стек в Юлии

Question

Я хотел бы реализовать простой конкатенационный язык (также известный как Joy или Factor) в качестве DSL в Julia, и меня беспокоит, как оптимально представить стек.

Стек, представляющий как данные, так и программный код, должен содержать последовательность элементов различных типов. В простейшем случае In ts, Symbols и, опять же, рекурсивно, стеки (для представления кода в кавычках). Затем программа будет активно использовать push! и поп! перемешать значения между различными такими стеками.

Одна из очевидных реализаций в Julia, которая работает, но работает довольно медленно, - это использование массивов ячеек. Например, следующий стек Joy [ 1 [ 1 2 +] i + ] (который оценивает [4]) может быть реализовано в Юлии как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

Это, однако, работает очень медленно и использует огромные объемы памяти, вероятно, потому, что такой код нестабилен (что является серьезным препятствием для производительности в Юлии).

Используя C, я бы представлял стек компактно как массив (или, альтернативно, как связанный список) объединения:

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

Stackelem stack[n];

Но как я могу добиться такого компактного представления гетерогенного стека в Юлии и как избежать нестабильности типов?

Answer 1

Это один из способов, другой способ будет представлять аргументы с типом Vector{Any}:

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