+++
title = "Tail call conversion"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["1b2"]
forwardlinks = ["1b4"]
zettelid = "1b3"
+++

Each function is effectively converted to a module in Verilog, meaning
the tail call will have to refer to the current module it is called in.

In software, this is done by jumping to the start of the function with
the arguments set to the new values for the new iteration. There is then
normally a condition that is checked before the tail call is executed,
which will return the final value back to the caller.

The first intuition about how to convert these tail calls to hardware
may be to somehow detect that a function contains a tail call and wire
up the outside of the module correctly, so that it takes the outputs and
passes them back to the module until the condition is meat. However,
this changes the structure of the module quite a lot, meaning it is
difficult to prove anything about it. It is simpler to prove equivalence
between the hardware and the software if the translation between the two
is more direct.

In hardware, the function becomes a module. In our case, each module
contains a state machine with a state variable that controls what
instruction will be executed next. This means a similar approach to the
software translation, where the inputs to the module can just be set to
the updated variables, and the state can be set back to the start of the
module. The final end flag of the module will therefore only go high
when the default condition of the function is meat.