> When is a broadcast expression transformed (and fused) into vectorized code?

A broadcast expression is dealt with during lowering from expression trees to the linear IR. The trick is that it just turns into function calls. When you write

    a .+ f.(b)

that turns into

    materialize(broadcasted(+, a, broadcasted(f, b))

where the broadcasted calls are lazy, uninstantiated representations of the call. The `materialize` function then performs the fusion.

As long as you write type-inferrable code, the handling and fusion will all happen during compile time with no dynamism.

> Do you always (statically) know the input types? In Futhark, due to parametric polymorphism, you don't necessarily know the input types.

A method in julia always knows its concrete input types when it is called. Julia basically works by stitching together chunks of static code. So if something dynamic happens in the middle of your program, the compiler just waits until the the types are known at runtime and then resumes, and compiles new static code as far forward as its able to analyze the program.

If your program is fully inferrable, then the whole program is compiled 'just-ahead-of-time' when you first call the outermost function.

> Doesn't something like `[[1,2,3]] .+ 4` go two levels deep? Or have I misunderstood something?

No, that would error in julia.