 # Surprising evaluation order

The following program

``````mutable struct Node{T}
value::T
left::Union{Nothing, Node{T}}
right::Union{Nothing, Node{T}}
end
const Tree{T} = Union{Nothing, Node{T}}

function rotateright1(tree::Node{T}) where T
save1 = tree.left.right
tree.left.right = tree
save2 = tree.left
tree.left = save1
tree = save2
tree
end

function rotateright2(tree::Node{T}) where T
tree, tree.left, tree.left.right =
tree.left, tree.left.right, tree
tree
end

tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
println(rotateright1(tree))
println(rotateright2(tree))
``````

prints

``````Node{String}("P", Node{String}("A", nothing, nothing), Node{String}("Q", Node{String}("B", nothing, nothing), Node{String}("C", nothing, nothing)))
ERROR: LoadError: type Nothing has no field right
``````

I’d expect `rotateright1`and `rotateright2` to behave identical but must be missing something?

As far as I know this expands to

``````a = tree.left
b = tree.left.right
c = tree
tree = a
tree.left = b
tree.left.right = c
``````

which doesn’t match your `rotateright1`. I don’t know what evaluation order you expected but

``````    tree.left.right, tree.left, tree =
tree, tree.left.right, tree.left
``````

should be a better match to `rotateright1`.

To see what evaluation order Julia actually uses you can do

``````@code_lowered rotateright2(tree)
``````
2 Likes

Testing this

``````mutable struct Node{T}
value::T
left::Union{Nothing, Node{T}}
right::Union{Nothing, Node{T}}
end
const Tree{T} = Union{Nothing, Node{T}}

function rotateright1(tree::Node{T}) where T
save1 = tree.left.right
tree.left.right = tree
save2 = tree.left
tree.left = save1
tree = save2
tree
end

function rotateright2(tree::Node{T}) where T
tree, tree.left, tree.left.right =
tree.left, tree.left.right, tree
tree
end

function rotateright3(tree::Node{T}) where T
tree.left.right, tree.left, tree =
tree, tree.left.right, tree.left
tree
end

tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
println(rotateright1(tree))
# println(rotateright2(tree)) # Errors
println(rotateright3(tree))
``````

results in

``````Node{String}("P", Node{String}("A", nothing, nothing), Node{String}("Q", Node{String}("B", nothing, nothing), Node{String}("C", nothing, nothing)))
Node{String}("B", nothing, Node{String}("Q", nothing, Node{String}("C", nothing, nothing)))
``````

Now even more confused;)

Looks consistent with

``````julia> tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
Node{String}("Q", Node{String}("P", Node{String}("A", nothing, nothing), Node{String}("B", nothing, nothing)), Node{String}("C", nothing, nothing))

julia> println(rotateright1(tree))
Node{String}("P", Node{String}("A", nothing, nothing), Node{String}("Q", Node{String}("B", nothing, nothing), Node{String}("C", nothing, nothing)))

julia> println(rotateright1(tree))
Node{String}("B", nothing, Node{String}("Q", nothing, Node{String}("C", nothing, nothing)))
``````

Possibly you’re confused because you don’t actually give the same input to the different functions, `tree` gets updated by each call you make.

3 Likes

Yeah, you are damned right!

The correction

``````mutable struct Node{T}
value::T
left::Union{Nothing, Node{T}}
right::Union{Nothing, Node{T}}
end
const Tree{T} = Union{Nothing, Node{T}}

function rotateright1(tree::Node{T}) where T
save1 = tree.left.right
tree.left.right = tree
save2 = tree.left
tree.left = save1
tree = save2
tree
end

function rotateright2(tree::Node{T}) where T
tree, tree.left, tree.left.right =
tree.left, tree.left.right, tree
tree
end

function rotateright3(tree::Node{T}) where T
tree.left.right, tree.left, tree =
tree, tree.left.right, tree.left
tree
end

tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
println(rotateright1(tree))
tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
println(rotateright2(tree))
tree = Node("Q", Node("P", Node("A", nothing, nothing), Node("B", nothing, nothing)),
Node("C", nothing, nothing))
println(rotateright3(tree))
``````

explains it for me. Thanks for your help.