Wie stelle ich einen performanten heterogenen Stack in Julia dar?

Question

Ich möchte gerne eine einfache Verkettungssprache (alias Joy oder Factor) als DSL in Julia implementieren und ich habe Probleme, den Stack optimal darzustellen.

Der Stapel, der sowohl Daten als auch Programmcode darstellt, sollte in der Lage sein, eine Sequenz von Elementen unterschiedlicher Typen zu halten. Im einfachsten Fall werden Ints, Symbole und, wieder rekursiv, Stacks (um den zitierten Code darzustellen). Das Programm wird dann stark push! und pop! um Werte zwischen verschiedenen solchen Stapeln zu mischen.

Eine offensichtliche Implementierung in Julia, die funktioniert, aber ziemlich langsam läuft, ist die Verwendung von Zellen-Arrays. Beispielsweise kann der folgende Joy-Stapel [ 1 [ 1 2 +] i + ] (der auswertet) in Julia als stack = Any[:+,:i,Any[:+,2,1],1] implementiert werden. Meine typische Code sieht dann wie folgt aus:

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

Dies läuft jedoch sehr langsam und nutzt große Speicherzuordnungen, wahrscheinlich, weil ein solcher Code nicht typestable ist (was ein großer Performance-Engpass in Julia ist).

Verwendung von C, würde ich den Stapel kompakt als Array repräsentieren (oder alternativ als eine verknüpfte Liste) eine Vereinigung:

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

Stackelem stack[n]; 

Aber wie kann ich erreichen so eine kompakte Darstellung des heterogenen Stapels in Julia und wie vermeide ich die Instabilität?

Answer 1

Dieser Weg ist, wäre eine andere Art und Weise args mit Typ-Vektor darzustellen {any}:

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

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

edit: Eine andere Art und Weise zu repräsentieren könnte sein:

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

und Sie dann kann Folgendes tun:

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