Folding over an AST

[cscherrer]

I'd like to be able to do some simple fold operations over an AST. Here's my attempt:

julia> function fold(ast, leaf, branch) 
           function go(ast)
               @match ast begin
                   :(Expr(:call, $f, $args...)) => branch(f, map(go, args))
                   x                            => leaf(x)
               end
           end

           return go(ast)
       end
fold (generic function with 1 method)

julia> fold(ast, x -> :(f($x)), function(f,args) :($f($args...)) end)
:(f(2 * (4x - 1) + 7))

I would expect the first pattern to match, but it doesn't.

Beyond this, there are some general things I don't understand:

• when to use @match vs @matchast
• when do patterns need to be quoted (:(Expr(:call, $f, $args...)) above, though seem to indicate unquoted should work
• why/how does @match ast ... do anything at all? I would expect it to require $ast

I'd greatly appreciate any help or suggestions! :)

[thautwarm]

Hello @cscherrer! Sorry for my late reply, and it's indeed unexpected that I didn't receive the notifications. Take care about $args..., in fact it's incorrect. You codes could be fixed with

 function fold(ast, leaf, branch) 
           function go(ast)
               @match ast begin
                   Expr(:call, f, args...) => branch(f, map(go, args))
                  # or : :($f($(args...))) => branch(f, map(go, args))
                   x                            => leaf(x)
               end
           end

           return go(ast)
end
fold(ast, x -> :(f($x)), function(f,args) :($f($(args...))) end)

Just take a look at

x = [:a, :b]
quote
   $(x...)
end

will produce

quote
    #= REPL[13]:2 =#
    a
    b
end

[thautwarm]

About your following questions, the answers to them are presented here:

Q: when to use @match vs @matchast A: If you prefer to use a syntactic way(:($f($x)) => ...) to match asts instead of a constructive way(Expr(:call, f, x) => ...), and you don't want to write the first layer of AST quotation(:(...)), you should use @matchast. Here is a pair example about @matchast and @match.

@match :(a + b) begin
    :($a + $b) => (a, b)
    _ => nothing
end
# which is equivalent to
@matchast :(a + b) quote
    $a + $b => (a, b)
   _ => nothing
end

Q: when do patterns need to be quoted (:(Expr(:call, $f, $args...)) above, though seem to indicate unquoted should work? A: The patterns should quoted only if you want to match expressions/ASTs in a syntactic manner. Furthermore, in patterns, a $ is exactly a reverse operation to quotations:

@match 1 begin
   :($a) => a
end # 1
@match :(a + 1) begin
   :(a + $(::Int)) => true
   _ => false
end

[thautwarm]

Q: why/how does @match ast ... do anything at all? I would expect it to require $ast A: I think the reason why your codes didn't work as expected is answered before. If you still feel confused, please post your questions here again!

Thanks very much for issuing here!

[cscherrer]

Thanks for the detailed response! This is starting to make more sense to me, and I also found your blog post really helpful. I think this is just the thing my Soss project needs!

[thautwarm]

@cscherrer Again, thanks for your feedback and interaction! I did have read your plan about Soss.jl. As I used to be a student in mathematics major and work with those stuffs a little, I found it really impressive when comparing to some alternatives in R or Python side.

[cscherrer]

Ok so this is making me really happy:

function fold(ast, symbol, expr) 
    function go(ast)
        @match ast begin
            Expr(head, arg1, newargs...) => expr(head, arg1, map(go, newargs))
            x                            => symbol(x)
        end
    end

    return go(ast)
end

function leaves(ast)
    symbol(x) = [x]
    expr(head, arg1, newargs) = union(newargs...)
    fold(ast, symbol, expr)
end

function leafCount(ast)
    symbol(x) = 1
    expr(head, arg1, newargs) = sum(newargs)
    fold(ast, symbol, expr)
end

ast = :(f(x + 3y))

Then

julia> leaves(ast)
3-element Array{Any,1}:
  :x
 3  
  :y

julia> leafCount(ast)
3

[thautwarm]

Make sense!

[cscherrer]

Just tidying up, thanks for your help :)