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

[yuyichao]

@foobar_lv2

FWIW, I agree with your approach to understanding: Mentally compile your code into unoptimized assembly; then allow llvm to work its magic to give you the assembly you should have written in the first place.

That is a very good way to understand compiler and I use that too. And that’s what I really recommend ppl to do to be able to write efficient code.

@foobar_lv2

Luckily, compilers go to great effort to preserve the illusion that they are simple; i.e. complicated optimizing compilers emit code that has the same observable behavior as naive “platonic” compilers.

Compilers try very hard to adhere to a simple spec. They don’t try at all to behave in a simple way though… The end result is usually understandable (sometimes not) but the reasoning why the compiler can actually do something is more usually not obvious.

And the issue for all this is that there are still statement that are wrong that wouldn’t have even appear if one don’t mix in the implementation details. I should also note that this is also not just for someones’ perferences but it has real consiquences. Many people (more that I like) confuses implementation detail from the spec and that’s exactly why enabling more optimizations exposes so many bugs in peoples code.

[yuyichao]

@Vic

Then you misunderstood what I believe true and what not. What I said is that at x=1 , when that get’s “taken” by the computer, value 1 will be stored at some memory location. I never said that value will stay there forever, or until in the compiled code, or untill the so-called “run-time” (which I don’t have a simple picture for due to JIT) .
I only said what I said, and meant what I said! It’s that simple.
What the compiler does in your example – it still works with values 1 and 2 both stored initially in memory. That’s it.
I see the big picture, and in that big picture , the work of compiler is part of the overall work of the computer to convert my program into the final results. That work happens with memory, and cache, and registers (as you said “you name it”)

Still wrong. Say you have x = a + 2; x = 3; For certain input type of a, the result of a + 2 will never have appeared anywhere in the compilation and execution of the code. And this is still just a very simple case.

@Vic

This again sounds like “proof by authority” to me: because you neither explain, nor link to a reference that explains.

The reference is that 1 and 2 are of type Int. It’s a immutable type, so values (objects) of that type cannot be overwritten.

@Vic

I was talking about 2 ojbects for which Julia gives the same reference, say as in: a=b=[0 0]

That is what I’m talking about as well. Yes in a = b = [0 0] it is actually allowed to give a and b different address. It is indeed a case we don’t yet because we don’t do any optimizations on arrays. More specifically though, I’m talking about the case you are talking about. (maybe slightly different, too lazy to scroll up.)

f(a) = ...
x = 1
f(x)

The x outside the f and the a inside f are referring to the same object but stored at the same place after compilation.

@Vic

all along that memory locations are not part of Julia language semantics, and you’ve been preaching to discuss strictly only what’s part of language semantics.

Yes. And I say that because your concept of “memory location” is inconsistent. I’ll actually be fine with it if you actually talk about a consistent definition of “memory location”, say, whatever the object may or may not be in the final code. You can understand everything about assignment that way, albeit much and unnecessarily harder. (edit: and I acknowledge that this “harder” is certainly subjective. A computer will almost certainly find this way easier, for example.)

The problem, though, is that you are actually (from my perspective) constantly changing your definition of your “memory locatioin”/“value location”.

You started as x = 2 in REPL overwriting a “value-location” with 2, which is simply not something that ever happen in this case.

You then give the definition of

@Vic

space/region/box in computer memory that would hold that value, as distinct from the “address” of that space/region/box.

which may not exist at runtime and generally does not exist at compile time and it still doesn’t have any of the properties you give it.

[foobar_lv2]

@yuyichao

I should also note that this is also not just for someones’ perferences but it has real consiquences. Many people (more that I like) confuses implementation detail from the spec and that’s exactly why enabling more optimizations exposes so many bugs in peoples code.

Nobody wants to become a language lawyer.

I understand that a lot of relevant assumptions are super subtle, like e.g. which accesses may alias, or which things are constant (e.g. fields of Matrix, as you recently demonstrated). It would be most awesome to have an educational version of code_llvm that contains this info, even if much of it is in a way that llvm is currently incapable of using (we can attach a lot of metadata to llvm that gets preserved on optimization passes, right?). That would be a really cool way of encoding the spec.

Something I always wished for in C (and C++) is a compile flag “-fasshole” that emits runtime checks for everything that is UB per spec. So that I get a very slow executable that I can then fuzz to find the kind of bugs that stem from programmers assuming that their compiler is a mere tool, instead of a spec-abiding hostile language lawyer. Even more important for multithreading.

[Vic]

(he is always right, even though it is sometimes necessary to meditate on his words).

I’m sure you wanted to say he is most often right. NO ONE IS ALWAYS RIGHT
(& I’m not implying anything about him, either from this thread or in general).
I’m emphasizing this because it’s important to uphold preserve the culture that we have at least in western world, that one should always question any authority, if he/she thinks so (of course with due respect). Else, sooner or later a mistake surfaces, and the more people believe without questioning, the graver the consequences.

Relative to you or yuyichao, I have next to nothing specific compiler knowledge. But here’s what I understand, by an analogy.
Say I’m given that:

x= 234 *2342
y=908 - x
y= 234 +1001
z= 3*(y+ 23 -23 -23 -23 +23 +5)/(3*1000*y)

And I’m asked to what is z.
Then I break the solving in 2 parts: simplification and actual-computation

1. Simplification. I’ll look at what’s asked, and realize I only need y, and so ignore x completely. Also, ignore the older y.
   Then , in expression for z, I’ll try scan the expression, notice cancellations possible and do that. Eventually get an equivalent problem:

   y=234+1001
   z=(y- 23 +5)/(1000*y)
   

2. Computation. Compute y, store result. Substitute for y in z. Finally do all operations in expression of z.

The Ist phase to me is one an optimizing compiler could do, at a very high level; and the “execution” would be 2nd step.

I can indeed see that the computer is not going to do the instructions in a top-down fashion as I presented the original program/problem, but instead take the whole program as a whole and try to give an answer that would be equivalent to running each statement in turn, but in a much smarter &faster way.
On the other hand, if given those instructions one by one, like in REPL, the computer is forced to follow them literally.

So I can see now what @yuyichao might have meant when he was saying that an instruction like x=100 may or may not result in storing 100 at some place in memory. It really depends on the other instructions next to x=100, given as a block or not, and context.

And I had in mind REPL, and 1 instruction at a time, when I was surprised to hear that; it was like a religious authority telling you that the earth is flat.

@yuyichao

FWIW, I agree with your approach to understanding: Mentally compile your code into unoptimized assembly; then allow llvm to work its magic to give you the assembly you should have written in the first place.

That is a very good way to understand compiler and I use that too. And that’s what I really recommend ppl to do to be able to write efficient code.

I guess in complex problems it helps to do the simplification step I mentioned above yourself, to help the compiler.

[yuyichao]

@Vic

I’m emphasizing this because it’s important to preserve the culture that we have at least in western world, that one should always question any authority, if he/she thinks so (of course with due respect).

That due respect should include considering why something that seems wrong could be right rather than straight denying the official definition.

@Vic

The Ist phase to me is one an optimizing compiler could do, at a very high level; and the “execution” would be 2nd step.

Sort of but close enough.

@Vic

So I can see now what @yuyichao might have meant when he was saying that an instruction like x=100 may or may not result in storing 100 at some place in memory. It really depends on the other instructions next to x=100 , given as a block or not, and context.

That is exactly what I said.

@yuyichao

The simplest example is that if you write x = 1; x = 2; in a local scope I can guarantee you that the 1 will not appear in the compiled code.

@Vic

I guess in complex problems it helps to do the simplification step I mentioned above yourself, to help the compiler.

As I said, if your goal is to understand the compiler then yes. However, trying to understand the compiler is completely based on what the compiler is allowed to do.

And as I already said above, I really have no problem if you can describe things consistently. It’s only because your description is wrong and inconsistent that I suggest you to please not think about compiler level stuff.

I’ll repeat again that.

@Vic

? Keeps the same binding (name-location and value-location), just
overwrites the value-location with 2

Is just wrong. For all possible definition of value-location at all level.

@Vic

produced: new name-location (but with same name string “x”), and , new value-location as well,

(the value-location part) Is also just wrong for basically all definition of value-location in all levels.

The only way I can think of (and tried) to help you resolve these issues is to avoid talking about your "value-location"s at all. If you want to keep it, I really have no idea how to build a consistent picture with that.

[mbauman]

Personally, I found Julia so much easier to understand once I stopped trying to jam in “memory locations” into my mental model.

In Julia, there are things and you can give these things names. Things can have multiple names, or no names at all. The names are there just for us humans to allow us to describe our programs. Even executing x=1 at the REPL doesn’t mean that we now have a box named x holding the value 1. Instead, Julia just knows that when we use the name x we are referring to the value 1.

Now, yes, this enables all sorts of compiler optimizations, but exactly what those optimizations are and how they work do not really matter.

[Vic]

Mentally compile your code into unoptimized assembly; then allow llvm to work its magic to give you the assembly you should have written in the first place.

How do you (or @yuyichao , as you said you use that too) “Mentally compile your code into unoptimized assembly” ? I guess imagine that the program is executed in the exact given order, and every operation there? Would inserting each instruction/operation at REPL, one at a time, and working with the resulting ans simulate that?
For example, for x = 5- 23 * 34 , do 23*34, then 5-ans, then x=ans ?

Assembly is a high-level abstraction as well: Whatever you wrote, the CPU will probably do something else (much of it at the same time).

Even if that assembly is the output of an optimizing compiler?

[StefanKarpinski]

I have to wonder if it is productive to continue this thread… @Vic, if this is helping you understand things, then carry on, but the tone has gotten a bit more combative that is preferable.

[Vic]

It is helping me understand things, for sure. IMO, we are close to settling most of the misunderstandings.

[StefanKarpinski]

Glad to hear it.

Here’s another observation that may help. If you want to, you can think of variables as pointing (in the sense of C pointers) to objects, which you can think of as living in memory. When you think about x = 1; y = x; x = 2, however, you should not interpret x = 2 as putting 2 in the location that x points at. That would amount to mutating the (immutable) value 1 and would result in y == 2, which is not what happens. Instead, you have to interpret x = 2 as changing the pointer x to point at the location of the object 2; the object 1 remains where it is and y still points at it.

This mental model is valid regardless of the mutability of the objects being pointed at. The model is, however, more literally true for mutable objects since they are generally associated with a particular memory location. Immutable objects, on the other hand, can be copied around since they cannot change, and are not generally meaningfully associated with a particular location in memory.

All of this is completely unrelated to scope. Scope is about determining where the name x means the same thing and where it means something different. There’s not really a pointer or memory analogy for this and I think that trying to map it to that is likely to go poorly.

[yuyichao]

@Vic

I guess imagine that the program is executed in the exact given order, and every operation there? Would inserting each instruction/operation at REPL, one at a time, and working with the resulting ans simulate that?

No. Following each instruction is just to examing the language semantics and does not “compile” anything. It’s of course useful and is exactly what I suggested you to do, as long as you stick to the semantics that assignment are bindings/references/store of pointer(references).
Mentally compile (for me) is much more C like. It’s completely different from the execution you get in the REPL so inserting each instruction/operation into the REPL will not get you anything.

@Vic

Even if that assembly is the output of an optimizing compiler?

Correct.

@Vic

we are close to settling most of the misunderstandings.

Yes. And I repeat for at least the third time that there are basically only two things that you’ve got completely wrong since the very beginning. Everything you’ve had are otherwise correct (also pretty much from the beginning) if you remove all notion of “value-location”. If you still don’t want to give up on that concept, you really need to clearify exactly what you are talking about because there’s really nothing that has the properties you’ve presented at all.

[Tamas_Papp]

@Vic

preserve the culture that we have at least in western world, that one should always question any authority, if he/she thinks so

I don’t think that anyone is posing as an authority in this thread, so framing this discussion as such is not very useful. In case you missed this, @yuyichao is helping you.

Also, in general, while everything can of course be debated, doing this in a meaningful way requires a lot of background when you want to talk about compiler internals.

Finally, as many have pointed out, compiler internals are orthogonal to understanding (not implementing) scope (which was the original question). You can become a very proficient Julia programmer with a perfect understanding of binding and scope without having a detailed understanding of what happens under the hood (especially since it keeps evolving ).

[carstenbauer]

@Tamas_Papp

You can become a very proficient Julia programmer with a perfect understanding of binding and scope without having a detailed understanding of what happens under the hood.

Gladly so, otherwise I’d be screwed

[foobar_lv2]

@Vic

Would inserting each instruction/operation at REPL, one at a time, and working with the resulting ans simulate that?

function f()
x= 234 *2342
y=908 - x
y= 234 +1001
z= 3*(y+ 23 -23 -23 -23 +23 +5)/(3*1000*y)
return z
end

Now we need to compile that, instruction by instruction. Since you don’t know assembly, I’ll stick with quasi-julia. First, compound expressions need to be broken up, and we need temporary variables:

julia> @code_lowered f()
CodeInfo(
2 1 ─       x = 234 * 2342                                                  │
3 │         y = 908 - x                                                     │
4 │         y = 234 + 1001                                                  │
5 │   %4  = y + 23                                                          │
  │   %5  = %4 - 23                                                         │
  │   %6  = %5 - 23                                                         │
  │   %7  = %6 - 23                                                         │
  │   %8  = %7 + 23 + 5                                                     │
  │   %9  = 3 * %8                                                          │
  │   %10 = 3 * 1000 * y                                                    │
  │         z = %9 / %10                                                    │
6 └──       return z                                                        │
)

Next we can constant-fold: We have a dependency graph between assignments, and if all inputs are known at compile time, we can compute the output at compile time. This depends on assumptions: no side-effects of multiplications, etc. This, in turn depends on types (what is integer, what is floating point, what is matrix, etc). That step is called inference.

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

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.

julia> f()
0.000985425101214575
julia> @code_native f()
	.text
; Function f {
; Location: REPL[1]:2
	movabsq	$139649067102312, %rax  # imm = 0x7F029509B068
	vmovsd	(%rax), %xmm0           # xmm0 = mem[0],zero
	retq
	nop
;}

I am no big fan of ASTs and prefer to think about code_lowered. Unfortunately I was recently informed that lowering is an implementation detail, and AST is the spec. So I am doing things wrong, with the real consequence that some compiler updates break my mind and possibly code.
I am thankful that Yuyichao and Stefan told me that I’m wrong (I will continue to do it wrong and pay the price for sticking to an unsupported abstraction).

[jameson]

@foobar_lv2

Something I always wished for in C (and C++) is a compile flag “-fasshole” that emits runtime checks for everything that is UB per spec

It’s spelled -fsanitize=undefined

[Vic]

Thank you, this is helpful.

When you think about x = 1; y = x; x = 2 , however, you should not interpret x = 2 as putting 2 in the location that x points at. That would amount to mutating the (immutable) value 1 and would result in y == 2 , which is not what happens.

? One question though (to you or someone else who wants to answer). Is the semantics, and this mental model, of y=x above , same as for argument passing as in

x=object
f(y)= do_with_object(y)
f(x)

when y gets bound to “same” object as x? And again regardless of mutability of object?
I think it’s yes.
It seems I could summarize the semantics of both by saying that:

• in x=object , provided object is literal and not just name, assignment makes x bind to a new object (with new “reference” hence identity).
• in y=x, assignment makes y bind to the same object as x is bound to (with same “reference” hence identity)
• in f(x) above, it happens same thing as in y=x (except that y name is local to the function)

If yes, for the sake of ease of learning/understanding (simpler semantics), I wish Julia offered a way to check the “reference” of even immutable objects.

[Vic]

@yuyichao

Still wrong.[…]

You are right – and not just based on the recent replies you wrote, but I was simply making no sense not much sense with that particular region of reply: “Then you misunderstood what I believe true and what not…” here , I’ve striken it out and edited – please read if you want.

Perhaps because of that, my concept of “memory location” for values seemed inconsistent to you. Other than that, I don’t see where I ever changed my definition for it.

You started as x = 2 in REPL overwriting a “value-location” with 2, which is simply not something that ever happen in this case.

True (or…really? ever? ) but let’s not dig into what I wrote so many replies ago . I’ve learnt many things by now, I don’t believe everything I wrote there anymore.

I think you’ll be pleased to see how my interpretations read now: Variable binding: (re-) assignment, argument passing, `let`, scope

@yuyichao

That due respect should include considering why something that seems wrong could be right rather than straight denying the official definition.

Believe me, I did a lot of consideration (all these replies took me an incredible amount of time). If you noticed, I actually tried to quote and follow official definitions from documentation whenever I could.
You often did not give reference, did not explain in detail, and I did not know you: why would I take your words as “official definition”?
(And such situations is when one should question and not believe blindly)

@yuyichao

So I can see now what @yuyichao might have meant when he was saying that an instruction like x=100 may or may not result in storing 100 at some place in memory. It really depends on the other instructions next to x=100 , given as a block or not, and context.

That is exactly what I said.

yuyichao:

The simplest example is that if you write x = 1; x = 2; in a local scope I can guarantee you that the 1 will not appear in the compiled code.

Indeed. I was actually not thinking at all about compiler optimizations. I had in mind compiler executing my instructions word for word, as if one at a time in REPL.
Also, I had taken (long ago) an intro C course. There, teacher told us that re-assignment literally meant re-writing the memory location with a diff value, and never told us that “it depends, may or may not” (so he lied to me then because he didn’t mention possible optimizations )

The only way I can think of (and tried) to help you resolve these issues is to avoid talking about your "value-location"s at all. If you want to keep it, I really have no idea how to build a consistent picture with that.

I see how you wanted to protect me against extra confusion( Edit: thanks for that intention). But with a person like me, just “don’t” doesn’t work well… I needed to know “Why”… I think now I understand.

[Vic]

Even executing x=1 at the REPL doesn’t mean that we now have a box named x holding the value 1 .

But – in case it’s just that x=1 followed by enter – I think, we have a box holding 1 , linked to “x” through the address of that box (and perhaps one or more intermediate addressess)

[mbauman]

Yes, that is technically true, but it’s not really exposed to the user — you can’t use any first-class Julia constructs to find that location.

[Vic]

I don’t think that anyone is posing as an authority in this thread, so framing this discussion as such is not very useful. In case you missed this, @yuyichao is helping you.

This reply to him probably will address your concerns. Let me know if not.

Also, in general, while everything can of course be debated, doing this in a meaningful way requires a lot of background when you want to talk about compiler internals.

The things I “debated” are elementary notions of memory locations which are taught in almost any intro programming , or comp. science class. It often takes just a couple sentences or examples, well formulated, to clear up confusion that dozens of reply exchanges may not.

Finally, as many have pointed out, compiler internals are orthogonal to understanding (not implementing) scope (which was the original question).

Scope was not the original question; neither compiler internals.
(Is “SCOPE” in title why so many readers/ viewers in this thread ? )

You can become a very proficient Julia programmer with a perfect understanding of binding and scope without having a detailed understanding of what happens under the hood (especially since it keeps evolving ).

I agree