# Exercises 3

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

## Background for questions Q1-Q2

The following data structure is given:

````
0
field: node-left
field: node-right
field: node-key
field: node-value \ signed integer
constant node-size
````

### Q1: Write a word `tree-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.

### Q2: Write a word `tree-put ( nval nkey rootp -- )`

If the tree 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.

### Tests for Q1-Q2

````
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 777
````

## Backgroud for questions Q3-Q4

In 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: Write a word `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: Write a word `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->0
````

Use only `.`, `,`, the 6 fundamental control-flow words and `[
... cs-roll ]`.