3 ms·

Functional programming doesn't make sense for this sort of thing as you can't define a circuit recursively. Mitrion-C is an example of a higher-level functional

Functional programming doesn't make sense for this sort of thing as you can't define a circuit recursively. Mitrion-C is an example of a higher-level functional language aimed at configuring FPGAs. It's pretty useless unless you have insider knowledge on how the system works.

DanWaterworth 13y ago
> you can't define a circuit recursively Could you elaborate on this? Depending on what you mean, I might have a direct counter-example.
- stinos 13y ago
  please show that example anyway :P pretty sure skylan_q means you'd run out of hardware gates if you try something infinite?
  - DanWaterworth 13y ago
    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.
- skylan_q 13y ago
  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.
stygianguest 13y ago
Synchronous data-flow programming is a functional style language made for programming embedded systems. It follows the paradigm of clocked circuits, where variables are wires. Check for example Lustre/Scade: http://www.esterel-technologies.com/ http://www.esterel-technologies.com/ or its more recent successor Lucid synchrone: http://www.di.ens.fr/~pouzet/lucid-synchrone/ http://www.di.ens.fr/~pouzet/lucid-synchrone/ The latter has explicit recursion which can be disabled when designing embedded systems. Haskell libraries closely follow this paradigm with their functional reactive DSLs. Recursion is actually useful to recursively define circuits with repeated patterns, e.g., the butterfly FFT.

DanWaterworth 13y ago

> you can't define a circuit recursively Could you elaborate on this? Depending on what you mean, I might have a direct counter-example.

stinos 13y ago
please show that example anyway :P pretty sure skylan_q means you'd run out of hardware gates if you try something infinite?
- DanWaterworth 13y ago
  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.
skylan_q 13y ago
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.

stygianguest 13y ago

Synchronous data-flow programming is a functional style language made for programming embedded systems. It follows the paradigm of clocked circuits, where variables are wires. Check for example Lustre/Scade: http://www.esterel-technologies.com/ http://www.esterel-technologies.com/ or its more recent successor Lucid synchrone: http://www.di.ens.fr/~pouzet/lucid-synchrone/ http://www.di.ens.fr/~pouzet/lucid-synchrone/ The latter has explicit recursion which can be disabled when designing embedded systems. Haskell libraries closely follow this paradigm with their functional reactive DSLs. Recursion is actually useful to recursively define circuits with repeated patterns, e.g., the butterfly FFT.