It is obvious that nothing concrete can usually be calculated or compiled if the input types are still abstract or ‘just annotations’. This is surely something else that has to be considered for AOT but I guess it does not directly collide with the property of type stability. If you would have passed a concrete struct - or better a type-stable or typed struct - there would have been no problem for AOT compilation.
In the end, I do not want to start discussions about details here as I just wanted to give a suggestion of how doing efficient statical compilation safely may(!) be achieved in Julia with a minimal intrusion into the language. I hope I could at least share the essence of my idea with you. If you have too many reservations against it (as I have the impression ) then just throw this idea over board - no hard feelings on my side
It’s not so much I have reservations against it, it’s more like it looks like it wouldn’t do anything. I can’t tell what the purpose is, let alone have any reservation against it. Maybe an example of a hypothetical AOT compilation script will make clear what I mean? Let’s imagine Base.precompile can do the whole compilation process, and we have a stricter version AOTcompile that throws an error at any type instability:
f(x) = 2*x
g(x::Vector{Any}) = x[1]
AOTcompile(f, (Int,) ) # e.g. f(1), stable
AOTcompile(g, (Vector{Any},) ) # e.g. g(Any[0]), InstabilityError
By your proposal, we can annotate methods to assert type stability. But I don’t expect anything to change:
@typestable f(x) = 2*x
@typestable g(x::Vector{Any}) = x[1]
# writing it for g is obviously wrong, but nothing is stopping me
AOTcompile(f, (Int,) ) # e.g. f(1), stable
AOTcompile(g, (Vector{Any},) ) # e.g. g(Any[0]), InstabilityError
I think if there’s anything wrong with my understanding, you could point out how this should act differently from what I expect.
You are right, nothing obvious in the code will change. However, my personal advantage would be that if I want to write an AOT compilable function I get assistance from the language and the compiler:
from the language because I can simply look up which functions I could call to preserve type stability (obviously all which are marked with @typestable). E.g., when calling some standard library function like Base.randn(), how should I know a priori if this function is intended to be type stable without testing it (for all possible variants in which I’m using it)?
from the compiler because if I mess up my own function it should warn me that type stability can not be inferred, e.g., simple example:
@typestable foo(x::Number) = x<1 ? 0 : 1.0
AOTcompile(foo, (Int32,) ) #error: type instability detected Union{Int64,Float64}
#or in REPL
foo(3) #error: type instability detected Union{Int64,Float64}
returning different data types is maybe just a programming error in this case. @typestable could warn me about that (already when calling in REPL).
additional advantage: I could then test smaller units of my final program for type stability
This is basically what I expect. Note that in your example @typestable g(x::Vector{Any}) = x[1] should be perfectly fine - the concrete output type can always be inferred by the concrete input type. E.g., when calling
AOTcompile(g, (Vector{Int64},) ) #is fine, or
AOTcompile(g, (Vector{Float32},) ) #is also fine
AOTcompile(g, (Vector,) ) #not fine because the type is not concretized,
#this can always happen independently of the type stability
Sukera already provided an example of a method where one call is stable and another call is unstable, so if you’re fine with that inconsistency between calls, then attaching an automatic warning feature to a method would be fine for you. It’ll just be complicated to implement, especially throwing an error during type inference of a simple foo(3) call, and I think inspecting type stability per function call would be more useful for compiling small executables and just generally. At least we’re on the same page on what this could accomplish, now.
The type of x[1] is not inferrable. All variables’ runtime values have concrete types, that doesn’t imply all variables or expressions have inferrable types (inference occurs at compile-time, not runtime):
julia> g(Any[0])
0
julia> isconcretetype(typeof(Any[0]))
true
julia> isconcretetype(typeof(0))
true
julia> @code_warntype g(Any[0])
MethodInstance for g(::Vector{Any})
from g(x::Vector{Any}) in Main at REPL[27]:1
Arguments
#self#::Core.Const(g)
x::Vector{Any}
Body::Any
1 ─ %1 = Base.getindex(x, 1)::Any
└── return %1
First off, I don’t think seperating the language into “AOT-compilable” and “not AOT-compilable” parts purely based on a function annotation is good. A priori every function should be AOT-compilable, as long as it doesn’t require eval, even type unstable ones (“just” compile all reasonable code paths and put them in your binary. Perhaps deny Any). So arbitrarily introducing a split based on some annotation splits julia smack dab down the middle into two “languages”, which I think most people would really like to avoid.
Second, we can do exactly that kind of assistance today, via the same mechanism that JET.jl and Cthulhu.jl use. They’re even already usable as part of a test suite.
So from my POV, adding such an annotation would just add another “color” of function (if you’re familiar with async functions, where I’ve borrowed that term from), without really adding a whole lot of benefit that we don’t already have or we can’t already get with less disruptive means.
From what I gather you’re looking for ways to have a compiled julia binary, without any runtime code generation, and which tools would help developers work in such a workflow, correct? Wouldn’t it be better for developers if the compiler told them which part of their code is problematic for static compilation, instead of them having to hunt down functions written specifically for that purpose (and thus being unable to reuse the existing libraries)?
So, note, that’s an exception, but since I think the small binary, as opposed to just binary option, is overblown, I’ll not take much time explaining, the limitations and potential workarounds.
I think JIT is not necessary for the actual final executable
Yes, the JIT is handled by LLVM, and the LLVM (Julia’s largest dependency at 79MB + 41M (libjulia-codegen) = 120 MB, besides the sysimage at 221M, that can be made smaller, 4th largest at 32MB OpenBLAS can be dropped) can be excluded as of just released Julia 1.8.0. From its NEWS:
The LLVM-based compiler has been separated from the run-time library into a new library, libjulia-codegen. It is loaded by default, so normal usage should see no changes. In deployments that do not need the compiler (e.g. system images where all needed code is precompiled), this library (and its LLVM dependency) can simply be excluded (#41936).
and:
New option --strip-ir to remove the compiler’s IR (intermediate representation) of source code when building a system image. The resulting image will only work if --compile=all is used, or if all needed code is precompiled (#42925).
Oh sorry to you and @Sukera. I just realized that Array Types in Julia can have elementwise individual typing (I was not aware of that since in most other languages arrays do have one fixed type for all elements). Your example with @typestable g(x::Vector{Any}) = x[1] could then really never compile just as you mentioned (only @typestable g(x::Vector{<:Any}) = x[1] would make sense). Maybe the fact that newcomers like me need some time to realize all the freedom that Julia provides is one more reason for keywords like that (since I would have introduced an error here but the compiler should have warned/corrected me if my intend would have been provided through this keyword).
Yep, sometimes type instability doesn’t just come from failed inference, it comes from putting abstract type parameters into our types (sometimes this flexibility is necessary for some programs, but we do try to avoid it because it’s less performant). Like type annotations, type parameters serve as restrictions on the types of runtime values, and they partially determine what can be known at compile-time. So for example, Vector{Number} restricts the elements’ types to subtypes of the abstract Number parameter. All of its elements at runtime must have concrete types, but at compile-time, only Number is known.
I also do not think that a simple annotation can and should divide the code into two classes. An annotation like this could theoretically be implemented through a macro which is evaluated at compile time and which leaves nothing back but a message/error. I agree that AOT-compilability should generally be the default. However, as you pointed out with your Vector{Any} example, unaware usage of the language brings you easily in big trouble. I believe it should be a key feature of any language to allow static compilation in a very straight forward manner even for newbies which don’t know nothing about things like multiple dispatch. Maybe there is a better way than through annotations but I think, in the current state, Julia is not there yet to really support you doing static (AOT) compilation. I’m not fully aware of what JET.jl, @assume_effects and others are capable of, hopefully they can provide a straight forward solution in the future. At the moment it seems to me they are more like tools for expert and not meant to be used by normal users which may not have their focus on informatics (correct me if I’m wrong).
A better description (hopefully): each element of an Array (or other container) has it’s own concrete type, but the type of the container value doesn’t necessarily encode fully the types of the elements. For example:
julia> [nothing, missing]
2-element Vector{Union{Missing, Nothing}}:
nothing
missing
julia> [Val{1}(), Val{2}()]
2-element Vector{Val}:
Val{1}()
Val{2}()
julia> struct A end
julia> struct B end
julia> [A(), B()]
2-element Vector{Any}:
A()
B()
julia> Union{A, B}[A(), B()]
2-element Vector{Union{A, B}}:
A()
B()
In each of these examples the vector elements have a certain concrete type: abstract types can’t have instances. But abstract types can be type parameters to other types, such as container types, like Array.
There is no meaningful concept of a “compile-time type”: the only type a value has is its actual type when the program is running. This is called a “run-time type” in object-oriented languages where the combination of static compilation with polymorphism makes this distinction significant.
Only values, not variables, have types – variables are simply names bound to values, although for simplicity we may say “type of a variable” as shorthand for “type of the value to which a variable refers”.
) then just throw this idea over board - no hard feelings on my side 
(I was not aware of that since in most other languages arrays do have one fixed type for all elements). Your example with