How to represent a performant heterogenous stack in Julia

Question

I would like to implement a simple concatenative language (aka Joy or Factor) as a DSL in Julia and I am troubled how to optimally represent the stack.

The stack, which represents both data and program code, should be able to hold a sequence of items of different types. In the simplest case Ints, Symbols and, recursively again, stacks (to represent quoted code). The program will then heavily use push! and pop! to shuffle values between different such stacks.

One obvious implementation in Julia, which works but runs rather slow, is to use cell arrays. For example, the following Joy stack [ 1 [ 1 2 +] i + ] (which evaluates to [4]) can be implemented in Julia as stack = Any[:+,:i,Any[:+,2,1],1]. My typical code then looks like this:

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

This, however, runs really slow and uses huge memory allocations, probably because such code is not typestable (which is a big performance bottleneck in Julia).

Using C, I would represent the stack compactly as an array (or alternatively as a linked list) of a union:

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

Stackelem stack[n];

But how can I achieve such a compact representation of the heterogeneous stack in Julia, and how I avoid the type instability?

Scott Jones · Accepted Answer · 2016-04-01T22:59:12.253

3

This is one way, another way would be to represent args with type Vector{Any}:

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

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

edit: Another way to represent it might be:

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

and then you can do the following:

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

edited Apr 01 '16 at 22:59

answered Mar 29 '16 at 23:59

Scott Jones

1,750
14
14

I do not fully understand your answer. Exp: Are Tuples a data structure that lends itself to many operations of push and pop? How would you represent a Joy stack that contains no symbols, e.g. [1 [2 3]]; would this include nested Tuples? Immutable: what is the advantage of using an immutable data structure in this context? Wouldn't repeated pop's and push's result in heavy performance costs? – Bernd Mar 31 '16 at 20:09
Vector{Any}: What is the advantage compared to the cell array from my question? Is there not a better way in Julia to restrict the possible types of the array elements for the compiler than Any? And - what is the idiomatic way to avoiding type instability, when processing such a heterogeneous array? – Bernd Mar 31 '16 at 20:10
From your example above, I didn't realize that Joy might not have symbols, it looked like a typical AST. Do you have a link to the Joy syntax? – Scott Jones Apr 01 '16 at 22:32

How to represent a performant heterogenous stack in Julia

1 Answers1