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