Is there a reason why Expressions are not subtyped?

General Usage
1

When working with expressions I often find myself writing things like:

    if ex.head == :call 
    ...
    if ex.head == :tuple

Code in Base is also full of that kind of pattern.

It would be much easier to write such code if there was a CallExpr, TupleExpr, etc. so that one can use dispatch rather than all these conditionals.

Is there some fundamental reason why this cannot be done, or is a bad idea to begin with ?

2

There was a little discussion about the possibility of making Expr parametric, with the expression type as its only parameter, for example Expr{:call}. As I recall, the core devs ultimately rejected the idea because it is no substitute for the kind of full-blown pattern matching which is needed for handling Julia’s AST (and presumably it would also be a ton of work).

3

It’s bad for performance.

These are used in the AST which is generally mixed of all the types (of expressions). If you make each type of expression it’s own type you’ll be just forcing dynamic dispatch on every operations on them.

7 Likes
4

@yuyichao is correct. The cost of runtime method lookup is high. If the compiler couldn’t infer which method will be called in advance, a good performance trick is to have only one method for each function. In such cases you’re explicitly avoiding dispatch.

Note that Meta has Meta.isexpr which may make your life more convenient.

2 Likes
5

Thanks, that makes sense. Maybe there’s some cases where the performance / code clarity tradeoff is worth it though. I might give it a try.

6

You’re prepared to fix Core.Compiler? And the Scheme code in src?

Independent of being hard, I really don’t think this will work. Play around a bit with adding dispatch to some key methods of JuliaInterpreter first and re-run the benchmarks, and I think you’ll see our concerns. For example you could rely on dispatch for these lines. (The isa(a, T) && meth(a) construct lets the compiler deduce which method of meth will be called.) You can think of this as “manual union splitting,” and it generates fast but ugly code.

1 Like
7

I’m thinking more of building my own custom AST that I can convert an expression into and then work with, so I wouldn’t have to deal with internals. E.g. this seems to work quite well :

abstract type AbstractExpr end

econvert(::Type{T}, x) where T <: AbstractExpr = x
isa_expr(ex::Expr, ::Type{T}) where T <: AbstractExpr = false

struct ECall <: AbstractExpr
    fun::Any
    args::Vector{Any}
end
ECall(ex::Expr) = ECall(ex.args[1], ex.args[2:end])
isa_expr(ex::Expr, ::Type{ECall}) = ex.head == :call

function econvert(::Type{T}, ex::Expr) where T <: AbstractExpr
    for i in 1:length(ex.args)
        ex.args[i] = econvert(T, ex.args[i])
    end
    isa_expr(ex,T) ? T(ex) : ex
end

ex = :(f(x, g(y)) = h(1,2,3))
ex = econvert(ECall, ex)

I can then dispatch on expression type, for example to collect the call names:

collect_calls!(exs::Vector, calls) =
    begin (a->collect_calls!(a, calls)).(exs); calls end

collect_calls!(ex::Expr, calls=[]) =
    collect_calls!(ex.args, calls)

function collect_calls!(ex::ECall, calls=[])
    push!(calls, ex.fun)
    collect_calls!(ex.args, calls)
end
collect_calls!(x, arg) = nothing

julia> collect_calls!(ex)
3-element Array{Any,1}:
 :f
 :g
 :h

That said my use case is mainly refactoring (e.g. extract all variables that are not assigned in an expression), so this doesn’t need to be super general.

8

CSTParser did this. Then it went back to all expressions having the same type for performance (https://github.com/julia-vscode/CSTParser.jl/pull/95).

5 Likes