Variable binding: (re-) assignment, argument passing, `let`, scope

Vic · October 30, 2018, 10:59pm

Thank you for your time to write such a detailed reply. I will study it.

We have a dependency graph between assignments, and if all inputs are known at compile time, we can compute the output at compile time.
…
We see that the pure julia steps of the compiler, pre-optimization, were enough to get the result, even before hitting the powerful llvm: The amount of runtime computation necessary for your example is zero.

Wow. So the historical notion of “execution” after "compilation has really become a misnomer. It’s just divided execution, in 2 phases, compile time and runtime (and often just compile time)

Edit: maybe better called “computation”? so that to include both the computation during compile time, and during runtime , the latter being called “execution” time as well, from what I read around

Sukera · October 31, 2018, 5:38am

Just FYI, this is known as constant folding and constant propagation and really isn’t anything new or unique to Julia. gcc also does this as well as many, many others.

A quick search finds references to this for multiple languages since at least 1991, so this has been known since before then. It’s even described as a “well known technique” in that papers abstract.

Dave.Shone · October 31, 2018, 10:03am

If memory serves me correctly, constant folding was common in several vendors’ compilers (e.g., DEC VAX FORTRAN) in the early-mid 1980s. It was a pitfall for naïve benchmarking exercises and, along with other optimisations, made single-stepping with a source-code debugger somewhat entertaining . I suspect the optimisation had been around for a while by then.

Vic · October 31, 2018, 4:48pm

By looking at the internal compilations steps as exposed in this reply above , especially

julia> code_typed(f, (); optimize=false)
1-element Array{Any,1}:
 CodeInfo(
2 1 ─       (x = 234 * 2342)::Const(548028, false)                          │
3 │         (y = 908 - x::Const(548028, false))::Const(-547120, false)      │
4 │         (y = 234 + 1001)::Const(1235, false)                            │
5 │   %4  = (y::Const(1235, false) + 23)::Const(1258, false)                │
  │   %5  = (%4 - 23)::Const(1235, false)                                   │
  │   %6  = (%5 - 23)::Const(1212, false)                                   │
  │   %7  = (%6 - 23)::Const(1189, false)                                   │
  │   %8  = (%7 + 23 + 5)::Const(1217, false)                               │
  │   %9  = (3 * %8)::Const(3651, false)                                    │
  │   %10 = (3 * 1000 * y::Const(1235, false))::Const(3705000, false)       │
  │         (z = %9 / %10)::Const(0.000985425, false)                       │
6 └──       return z::Const(0.000985425, false)                             │
) => Float64

I can see that this compile-time computation is still creating and addressing objects in memory locations – even though that’s not run-time.

Even for a source code like:

julia> function g()
       x=1
       x=2
       end
g (generic function with 1 method)

julia> code_typed(g, (); optimize=false)
1-element Array{Any,1}:
 CodeInfo(
2 1 ─     (x = 1)::Const(1, false)
3 │       (x = 2)::Const(2, false)
  └──     return 2
) => Int32

It seems like, during compilation, value of x 1 will be stored somewhere in memory : Else, how is it looked and determined that it’s Const(1, false) ?

It is not completely ignored, as I meant would happen to x in my original analogy here

Am I right?

kristoffer.carlsson · October 31, 2018, 4:57pm

Of course, during compilation, the constants have to be stored somewhere. When you talk about memory location of objects you are talking about runtime.

Vic · October 31, 2018, 6:33pm

No! When I talk about “memory location of objects”, I talk about memory location of objects, nothing more, nothing less, and nothing else!
It does has a meaning regardless of whether it’s about compile or runtime (both phases are part of an overall computation of a program)

My Goodness… There has been SO much misunderstanding in this WHOLE thread, from the beginning…

From the beginning, by “value location” I simply meant any mem. location with a bit pattern corresponding to that value we see on screen – not necessarily at runtime.

Also, I acknowledge, I did not know then that computation can happen at compile time - I had in mind compilation in the oldest sense as simply translating word for word to assembly then machine code, without execution of any operation/command in my code happening at compile time.

Note that “execution” also, in general, can mean any computation of an instruction, not just ~~“compile time”~~ run-time.

I think @yuyichao always had in mind run-time when he was contradicting me, while I had in mind the general computation (compile + run time).
And when he would say “execute” I’d just interpret in a general/loose sense of “compute”, not specifically after compilation. EDIT: like next (which also marked a turning point in the conversation)

I was at least partially right before striking out the text in this reply to him – and not just because everything in a source code (in REPL or not) get’s loaded in memory even before compilation
(in that sense, any value get’s a place in memory, obviously – but it’s not the memory location I defined from the beginning, an addressable one, i.e, a cell designated to hold that particular value, not just a string for the whole program).

I wish I stopped this thread here or here …

This reply with analogy partly confused things further, but partly led to the realization I have right now…

I’m also a bit frightened now to continue to study the docs, of Julia or of other langs , with this danger of words meaning not directly what they seem to mean…

StefanKarpinski · October 31, 2018, 7:17pm

From the beginning, by “value location” I simply meant any mem. location with a bit pattern corresponding to that value we see on screen – not necessarily at runtime.

Julia happens to represent most literal values as themselves in AST but there’s no inherent reason it has to be like that. The AST representation of 1 could be Expr(:integer_literal, "1") and that expression could be dead-code eliminated before the value 1 is ever created anywhere in the computer’s memory. So it’s still not necessarily true that the value 1 has to exist somewhere in memory at some point. The fact that Julia represents the literal 1 in AST in memory with the integer value 1 is a fairly incidental implementation detail, albeit one that comes in handy for metaprogramming.

I think @yuyichao always had in mind run-time when he was contradicting me, while I had in mind the general computation (compile + run time). And when he would say “execute” I’d often just interpret in a general/loose sense of “compute”, not specifically after compilation.

I think you’ll find that pretty much all programming language people will interpret things this way. When you talk about “execution” it means at run time; when you talk about parsing, lowering, type inference, inlining, constant propagation and other code transformations and optimizations, it’s at compile time.

I’m also a bit frightened now to continue to study the docs, of Julia or of other langs , with this danger of words meaning not directly what they seem to mean…

People manage to talk to each other about programming languages well enough all the time so once you’re aware of what people in the field generally mean by things, it’s no less precise than how people talk about most fields and much more so than many. We try very hard to use standard, established terminology when possible.

Sukera · October 31, 2018, 7:48pm

To add on to this, Julia doesn’t really show this distinction to someone using the language since it’s compiled JIT (just-in-time, or right before execution). Other languages like C show a much cleaner separation of the two, since a) there’s more than one way to compile a given file containing C source code to a runnable executable (meaning, there are multiple independent compilers for C) and b) since running the actual binary requires another step beside compilation, namely the actual call to some system provided function that’s bootstrapping execution. As far as I know, the second step doesn’t exist in Julia, because of the JIT compilation.

To stay with the example of C, both gcc and clang (the two most popular compilers for C, as far as I know) both support and actively do constant propagation and the like, but this is nothing codified into the C language specification - it’s more of an optimisation that’s not forbidden by the spec which is done to reduce execution time and (more or less minutely) increase compilation time. Julia also does this, but because the first call to a function is needed as “hey, compile and then run this”, it of course includes compilation time and after that also the execution time. Subsequent calls don’t need to be compiled again, so those calls don’t include compilation time, just the execution time. That’s also why it’s wrong to include compilation when talking about execution - it simply in general is not relevant at the time of execution what happens during compilation.

EDIT:
There is of course also precompilation of modules in julia and there are ongoing efforts to save precompiled functions and modules as a binary object to reduce function call overhead on the first call, but those efforts are largely in their infancy as far as I can tell and also don’t really change the overall point here, rather they support it.

kristoffer.carlsson · October 31, 2018, 8:20pm

As in any field, the words used typically have some specific meaning. For example, talking first to a programmer and then to a farmer in the 14th century about “execution”, and they might interpret these things differently.

In this thread, a lot of effort has gone to trying to to teach you what words in a programming context means. There are two approaches to take.

The accepting approach – “Ah, thats how the word is used, thanks now I know”.
The “stubborn” approach – “I have my own definition of words and these will not change”.

If you want to be able to talk to other programmers (this applies to any field) and make yourself understood it is important to learn what terms tend to mean in that field. The only way to do that is by experience and while gaining that experience it is important to have an open and receptive approach.

Vic · October 31, 2018, 10:49pm

Thank you very much for the last 3 replies. It is VERY valuable information about general compilation, for me
(and probably for anyone coming from a different field and who knows something about programming but wants to understand more, not just in terms of using the language).

I also appreciate your personal feedback. (I don’t usually spend time on forums and the like)

I’m not stubborn(EDIT: maybe a bit ) ; but I like precision and clarity. I wish people, in general, to have higher standards of clarity when expressing themselves. Sometimes a few extra words, which would be redundant to people in your exact field, would help alot other people. I think this is especially important for a mixed audience that I think Julia community, at large, is .

Tamas_Papp · November 2, 2018, 9:17am

Great to have this cleared up. This would mean that approximately 1/256 of my machine’s memory is the “value location” for any rand(UInt8) (I suspect it is not uniform though and UInt8(0) is somewhat overrepresented).