Comment représenter une pile hétérogène performante dans Julia

Question

Je voudrais implémenter un langage concaténatif simple (alias Joy ou Factor) comme un langage DSL dans Julia et je suis troublé comment représenter de façon optimale la pile.

La pile, qui représente à la fois le code de données et le code de programme, doit pouvoir contenir une séquence d'éléments de types différents. Dans le cas le plus simple, Ints, Symbols et, récursivement à nouveau, empile (pour représenter le code cité). Le programme utilisera alors fortement le push! et pop! pour mélanger les valeurs entre différents empilements.

Une implémentation évidente dans Julia, qui fonctionne mais qui est plutôt lente, consiste à utiliser des réseaux de cellules. Par exemple, la pile Joy suivante [ 1 [ 1 2 +] i + ] (qui évalue à [4]) peut être implémentée dans Julia comme stack = Any[:+,:i,Any[:+,2,1],1]. Mon code typique ressemble alors à ceci:

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

Mais cela tourne vraiment lent et utilise d'énormes allocations de mémoire, probablement parce que ce code n'est pas typestable (ce qui est un goulot d'étranglement dans Julia).

utilisant C, je représente la pile compacte comme un tableau (ou encore comme une liste chaînée) d'une union:

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

Stackelem stack[n]; 

Mais comment puis-je obtenir une telle représentation compacte de la pile hétérogène Julia , et comment j'évite l'instabilité de type?

Answer 1

C'est une façon, une autre façon serait de représenter args de type vecteur {Tous}:

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

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

modifier: Une autre façon de le représenter peut-être:

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

et vous peut faire ce qui suit:

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