The Forth part of the lecture is over, so these exercises are not needed for understanding the lecture, but these exercises may still be of interest to you.
Once you have solved the task, or at least made a sincere attempt at
it, you can compare your solution with the reference solution
exercises3.4th in the same directory as this page (not
provided as a link to avoid seducing you to peek).
The following data structure is given:
0
field: node-left
field: node-right
field: node-key
field: node-value \ signed integer
constant node-sizetree-getp ( nkey rootp -- nodep f )If nkey is in the tree, nodep @ is the node that
contains it and f is true. If nkey is not in the tree, nodep points to a
field that currently contains 0 where a node for nkey should be
attached.
tree-put ( nval nkey rootp -- )If the tree at whose root is stored at rootp contains a node for nkey, change it’s value to nval. Otherwise insert a node with key nkey and value nval.
variable myroot 0 myroot !
123 7 myroot tree-put
888 1 myroot tree-put
234 2 myroot tree-put
987 9 myroot tree-put
777 1 myroot tree-put
2 myroot tree-getp . @ node-value @ . cr \ prints -1 234
1 myroot tree-getp . @ node-value @ . cr \ prints -1 777In the version installed on the course machine,
simple-see shows the address of each intermediate
representation instruction as hex number, but shows the targets of
branch and ?branch in the notation
“<word+offset>”. Because the hex numbers are different for each
gforth invocation, in the following the addresses are also shown in the
“<word+offset>” notation.
q3 that simple-see decompiles to:<q3> call 0->0
<q3+$8> .
<q3+$10> ?branch 0->0
<q3+$18> <q3+$90>
<q3+$20> call 0->0
<q3+$28> .
<q3+$30> call 0->0
<q3+$38> .
<q3+$40> ?branch 0->0
<q3+$48> <q3+$70>
<q3+$50> call 0->0
<q3+$58> .
<q3+$60> branch 0->0
<q3+$68> <q3+$30>
<q3+$70> call 0->0
<q3+$78> .
<q3+$80> branch 0->0
<q3+$88> <q3+$A0>
<q3+$90> call 0->0
<q3+$98> .
<q3+$A0> call 0->0
<q3+$A8> .
<q3+$B0> ;s 0->0 Use only ., ;, the 6 fundamental
control-flow words and else, while, and
repeat.
q4 that simple-see decompiles to:<q4> call 0->0
<q4+$8> .
<q4+$10> branch 0->0
<q4+$18> <q4+$70>
<q4+$20> call 0->0
<q4+$28> .
<q4+$30> call 0->0
<q4+$38> .
<q4+$40> ?branch 0->0
<q4+$48> <q4+$A0>
<q4+$50> call 0->0
<q4+$58> .
<q4+$60> call 0->0
<q4+$68> .
<q4+$70> call 0->0
<q4+$78> .
<q4+$80> ?branch 0->0
<q4+$88> <q4+$30>
<q4+$90> call 0->0
<q4+$98> .
<q4+$A0> call 0->0
<q4+$A8> .
<q4+$B0> branch 0->0
<q4+$B8> <q4+$60>
<q4+$C0> ;s 0->0Use only ., ,, the 6 fundamental
control-flow words and [ ... cs-roll ].