What exactly code lowering is an how to do "unlowering"?


#1
  1. I’ve seen a number of snippets produced by code_lowered and have rough intuition of what it does, but what’s exact definition of code lowering? Does “lower” means “more low-level”?

  2. In my package I need to get an expression of a function. I do it using the code at the end of this post, but essentially I get it using Base.uncompressed_ast which, as far as I understand, returns lowered code that is a bit hard to work with. Is there a way to “undo” lowering or get function expression exactly as it has been written?


The code for getting a function’s expression:

    function replace_slots(ex::Expr, slotnames::Vector)
        new_args = Array(Any, length(ex.args))
        for (i, arg) in enumerate(ex.args)
            if isa(arg, Slot)
                new_args[i] = slotnames[arg.id]
            elseif isa(arg, Expr)
                new_args[i] = replace_slots(arg, slotnames)
            else
                new_args[i] = arg
            end
        end
        new_ex = Expr(ex.head, new_args...)
        return new_ex
    end

    """Extract arguments and (sanitized) expression of a function body"""
    function funexpr(f::Function, types::Vector{DataType})
        ms = methods(f, types).ms
        length(ms) != 1 && error("Found $(length(ms)) methods for function $f " *
                                 "with types $types, expected exactly 1 method")
        lambda = ms[1].lambda_template
        slot_ex_arr = Base.uncompressed_ast(lambda)
        slot_ex = sanitize(Expr(:block, slot_ex_arr...))
        slotnames = lambda.slotnames
        ex = replace_slots(slot_ex, slotnames)
        # 1st arg is a function name, next `lambda.nargs-1` are actual arg names                                                                                                     
        args = map(Symbol, slotnames[2:lambda.nargs])
        return args, sanitize(ex)
    end

Example function:

f(a, b) = sum(a' * b + a * b')

Output of funexpr / Base.uncompressed_ast:

Main.sum(Main.+(Main.Ac_mul_B(a,b),Main.A_mul_Bc(a,b)))

The role of femtolisp in Julia?
#2

I have been working on Sugar.jl for various reasons, which does exactly this:

Sorry for the sparse documentation, but I’m running out of time at the moment.
I hope to finish and clean things up soon!


#3

“Lowering” means transforming code from Julia’s high-level syntax (if, for, while, etc.) to a smaller set of common primitives (calls, conditionals, labels, gotos). See discussion and definitions of primitive node types and expressions and execution flow in the devdocs.

A Julia lowered-form decompiler could be written; it’s a sub-subfield of computer science. But I don’t think one currently exists. There’s probably a limit to how closely the returned expression can match the original.

Macros? They exist to capture and transform surface-level syntax.


#4

Looks interesting, thanks! Is there anything to get not lowered version of function expression?


#5

Thanks! I will take a look at it.

In my case it’s not an option, unfortunately. To give you some context: I’m working on a library for source-to-source symbolic differentiation. Even I force users to wrap the function to differentiate into a macro, this function internally may call many other functions that user doesn’t have access to. Currently with funexpr as above I’m able to parse about 85% of functions, but lowering seems to break my code for the other 15%.


#6

With e.g.: Sugar.sugared(func, (Types...), code_typed)
code_typed indicated from which lowered version to start and in this case will result in typed expressions.
If the code is not high enough, you need to insert additional pattern match passes.
Like in:


Sorry if there is quite a bit of noise, unneeded functions and no comments :wink:
I just very recently got this to a point where it works for my use case and still haven’t cleaned up.


#7

There is also: macro_form(f, types)
Which tries to look up the source in the file and then returns the parsed expression exactly like a macro would.
This will fails for clojures, which e.g. broadcast produces and REPL code, so I kinda stopped working on that function.


#8

While the exact contents of lowered expressions is not as stable as the front-end parsing, it may be better suited for you in doing this sort of transform. You can sort of think of it as a normalization pass that converts the parse syntax and annotates it with lots of crucial information (like the targets of loops and other branch, the scope of variables, etc)


#9

After playing around a bit with Sugar.jl I think macro_form is good enough for most practical uses, so I think in the next iteration of that part I’ll use it with fallback to lowered code. Thanks!

As for using lowered expressions instead of high-level ones, although it’s a reasonable approach, I’d like to avoid it when possible to keep parsed and generated expressions human-readable. And by “human-readable” I mean not only by humans who know Julia AST details :slight_smile: