Read lots of discussions about branches of object variants not yet allowing shared fields. I liked Araq's first proposal, but that seems tabled for new approach in v 2.
The code below took a c++ implementation (trivialized) of "polish notation" (apologies to actual people from Poland) using pointers to nodes, in which each node type was derived type of parent node. Instead of using pointers, I did it in c++ vector with an index to the vector instead of a pointer. Then, I did this in Nim, which was easier. In both c++ and Nim, I replaced the node subtypes with a single node that had all of the fields used by any node type (poor man's union). They are all ints or single chars, so not a big size waster. And I used an enum as the type discriminator. As you see below, works just fine.
Question: in Nim v 1.6.x I don't think I can use object variants because the val field is used by 2 types, l_idx is used by 2 types, and op is used by 2 types. So... ....should I split up the shared fields and use 2 names: l_idx and child_idx and leaf_value and sym_value and unop and binop? I end up with 9 fields instead of 6. Is there some "magic" in object variants that avoids using memory for unused fields in a variant? Or is it really just a run type check on what fields are allowed in which variant?
If it's just a run type check then I'll just stick with what I have (it's just a learning toy example...). The run time checks are explicit as case statements in the code below. If there is a memory savings or perf. benefit, then I'll try it with unique fields in every variant.
Sorry if the code is long:
type
nodetype = enum
BinaryNode, UnaryNode, LeafNode, Symbol
type
node = object
op: char # arithmetic operator for BinaryNode and UnaryNode
name: char # name of a symbol
val: int # int for now, value for LeafNode and Symbol
l_idx: Natural # index to a tree node for BinaryNode and UnaryNode
r_idx: Natural # index to a tree node for BinaryNode
nt: nodetype # the type that is used for branching to appropriate code
type
TreeStore = object
tree: seq[node]
syms: array[0 .. 127, int]
# BinaryNode
proc makeNode(t: var TreeStore, op: char, tr1: int, tr2: int): int {. inline .}=
case op
of '-', '+', '*', '/':
t.tree.add(node(op: op, l_idx: tr1, r_idx: tr2, nt: BinaryNode))
result = t.tree.len() - 1
else:
echo "Error: invalid op. Must be one of '-', '+', '*', or '/'."
quit()
# LeafNode
proc makeNode(t: var TreeStore, n: int): int {. inline .} =
t.tree.add(node(val: n, nt: LeafNode))
result = t.tree.len() - 1
# UnaryNode
proc makeNode(t: var TreeStore, op: char, tr1: int): int {. inline .}=
case op
of '-', '+', ' ':
t.tree.add(node(op: op, l_idx: tr1, nt: UnaryNode))
result = t.tree.len() - 1
else:
echo "Error: invalid op. Must be one of '-' or '+'."
quit()
# Symbol node
proc makeNode(t: var TreeStore, v: int, c: char): int {. inline .}=
t.syms[int(c)] = v
t.tree.add(node(name: c, nt: Symbol))
result = t.tree.len() - 1
# calculate value of node, dispatch on nodetype
proc eval(t: var TreeStore, tr_idx: Natural): Natural =
var node = t.tree[tr_idx]
case node.nt
of LeafNode:
result = node.val
of BinaryNode:
case node.op
of '-':
result = t.eval(node.l_idx) - t.eval(node.r_idx)
of '+':
result = t.eval(node.l_idx) + t.eval(node.r_idx)
of '*':
result = t.eval(node.l_idx) * t.eval(node.r_idx)
of '/':
result = t.eval(node.l_idx) div t.eval(node.r_idx)
else:
echo "Error: invalid op. Must be one of '-', '+', '*', or '/'."
quit()
of UnaryNode:
case node.op
of '-':
result = - t.eval(node.l_idx)
of '+', ' ':
result = + t.eval(node.l_idx)
else:
echo "Error: invalid op. Must be one of '-' or '+'."
quit()
of Symbol:
result = t.syms[int(node.name)]
# run it with some examples
var t: TreeStore # a place for all of the trees
var tr1 = t.makeNode('+', t.makeNode(5), t.makeNode(7))
echo "tr1 index: ", tr1, " value: ", t.eval(tr1)
var tr2 = t.makeNode(5, 'a')
echo "tr2 index: ", tr2, " value: ", t.eval(tr2)
var tr3 = t.makeNode('-', t.makeNode(7))
echo "tr3 index: ", tr3, " value: ", t.eval(tr3)
var tr4 = t.makeNode('-', tr1)
echo "tr4 index: ", tr4, " value: ", t.eval(tr4)
What about 7 fields instead of 9? :)
type
Node = object
name, op: char
val: int
case nt: NodeType
of BinaryNode:
blidx, bridx: Natural
of UnaryNode:
ulidx: Natural
else: discard
Sure. Thanks.
I haven't tried object variants yet, but what I implemented was effectively a union. There can't be any memory savings because all the objects in a seq of an object variant must have the same memory layout.
So, it looks like the advantage would be eliminating the case statement for the "pseudo-constructors". But, I sort of like what I have because the logic for each node kind is more than just populating the struct. For a couple of the node kinds there is more to do.
If it was just a matter of populating the right fields of each kind, then I can see object variants make the code more compact and still pretty obvious.
And, of course, better than inheritance...