A circuit that calculates the nth Fibonacci number or performs quicksort. I imagine any synthesis would have to generate something that is effectively an iterative solution: instead of producing n identical circuit blocks for n calls of the function, it would only have one circuit used over and over again. But this defeats the ability to exploit the potential parallelism that could be achieved in the execution of the algorithm.

please show that example anyway :P pretty sure skylan_q means you'd run out of hardware gates if you try something infinite?

Well, you can define a combinational circuit as something that has n inputs and m outputs and it is one of:

* a gate,

* a circuit that takes two inputs and produces two outputs by swapping the order,

* a circuit that takes one input and produces one output,

* a circuit that takes one input and produces no outputs,

* the circuit obtained by taking two circuits and composing them in serial,

* the circuit obtained by taking two circuits and composing them in parallel.

This produces a simple inductive definition for combinational circuits. Synchronous, sequential circuits can be obtained by taking a combinational circuit and connecting the first n outputs to the first n inputs via D flip-flops. If you want asynchronous circuits, you can add another combinator that takes a circuit and a connects the first n outputs to the first n inputs without the flip-flops.

With these definitions, it's quite straight forward to manipulate circuits in a functional manner.