Surprising evaluation order

New to Julia
1

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 rotateright1and rotateright2 to behave identical but must be missing something?

2

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
3

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;)

4

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
5

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.