Would LISP/FP help here?


I am working on tools aimed at chips design (I'm hardware designer). I have written a very usefull front-end that allows me to write things like: 'a wire b wire add r wire assign;'
This in actually an adder. To be clearer, 'wire' has 1 argument while 'assign' and 'add' have 2. (I am using a HP-like notation as the parsing is easy using stacks).

My tool creates a abstract tree that is being specialized depending on the domain: functional simulation, register-level simulation, simulation+timing, documentation,...

For instance, if I want to do timed simulation, the tool(C++) will use the abstract tree to create a new tree with nodes taken from classes implementing timed simulation.

It works fine, but I find it hard to add new features (I won't give any details here as this would be too much details). I was wondering whether FP would be of any help to create and/or specialize the abstract tree to a specific application? Any idea, pointers to example implementing something like this would be appreciated.

I am asking this because I've come to believe I would be more helped by a language like LISP than by C++..


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


While I don't think it's exactly what you're looking for, you might get something worthwhile out of looking at Lava. It's an experimental hardware description language for Xilinx FPGAs, built on top of Haskell.


Wasn't this in Koen Claessen's PhD thesis? I remember liking the approach but to go industrial this actually, sigh, is one example where I would implement it in ocaml (better performance, eager thus predictable, and yeah well, impure). I also remember not really liking the block structured approach for circuit design - felt it would be way to cumbersome to actually use industrially.

My own shot-out-of-the-hip approach would be to implement some language on top of some hardware combinator library in ocaml and to translate to VHDL or SystemC. What's wrong with SystemC for your project anyway?

For what it's worth, your language seems simple enough to easily translate to any HDL, even if implemented in C++.

Wasn't this in Koen Claessen'

Wasn't this in Koen Claessen's PhD thesis?

I believe that Koen was one of several people who worked on Lava, among them Satnam Singh (then at Xilinx), who owns the Lava website that I pointed to. Koen's thesis (which I've just grabbed) does appear to cover Lava.

I personally have no opinion on the Lava implementation - I've never used it. But I imagine that the ideas would port pretty easily to OCaml.


I designed Lava primaraily for efficient and compact implementation of structural circuit descriptions onto Xilinx FPGAs. So if you want to have a lot of control over layout and/or you want to have interfaces to SAT-solvers etc. then there might be some benefit in using Lava (and I am willing to update it to newer devices if there is any interest). However, if you want something higher level which can be subjected to synthesis etc. then you will find Lava is proably at the wrong level of abstraction.


I have no practical experience of digital circuit design but two of my favourite bits of computer science literature are based on it. I'm thinking of Guy Steele's thesis on constraint-based programming in Lisp and the Simulator for Digital Circuits in SICP. This is great reading though I'm sure it doesn't represent the state of the art in circuit simulation.


Sounds like Confluence to me.

stacks and chips design - looked into Forth yet?

I know that Forth has been used in chip design, especially by the Charles "Chuck" Moore, inventor of the language.

Forth is based on stacks and a HP-like notation, you define words that take x elements off the stack and returns y elements to the stack. Words may also toggle the environment between runtime/designtime, or have different behaviour based on this mode.

Moore has taken this approach pretty far, by using color as an indicator in his ColorForth, used for chip design, where he boots the system into a forth interpreter.

Forth is a refactoring friendly language, but may be hard to read, especially as the system words are very concise.

You might take a look - at the very least it will give you a different take on things.


Thanks! Any thoughts on tree manipulation then?

Thank you for the review of previous work. Lava looks intersting indeed. I'll have a look into Forth.

But my main point is not HDL generation here. I would be more interested to have some thoughts and/or pointer regarding what I call (excuse my newbee foolishness..): "the tool will use the abstract tree to create a new tree with nodes taken from classes implementing timed simulation." If there is some standardized ways of doing something approaching this with FP, please let me know!



Well, you might take a look at Strafunski. It's a Haskell package for generic traversal. Quoting from their website:

Strafunski provides programming support for generic traversal as useful for the implementation of program analyses and transformation components of language processors. Strafunski is based on the notion of a functional strategy. These are generic functions that can traverse into terms of any type while mixing type-specific and uniform behaviour.

What, you actually want help?!

Rather than everyone just trotting out their favourite tools?

Ok, I'll try. First up, modularity: OO makes it very easy to extend a data type: you just create a new subclass. However adding a new method requires you to alter every class in the hierarchy. FP is the exact opposite. Adding a new function to a datatype is easy, but extending a datatype requires you to modify every existing function. So FP is more appropriate if you think you'll be creating more new functions than datatypes, and from your problem description I think you will be. BTW, generic functions are a middle ground that solve this modularity dilemma, but introduce a bunch of new issues.

Now let's look at expressing tree traversals and transforms. I find the Visitor pattern in OO very convoluted. In comparison FP lends itself naturally to expressing transformations of recursive data structure (i.e. trees). Pattern matching is a great advantage here, and every FP language has some form of pattern matching. The use of higher-order functions also allows you to concisely express common traversal patterns and then parameterise the traversals by the types of transforms you want to perform. Generic traversals are known as folds in the literature, and I suggest looking at Oleg Kiselyov's foldts for a generic tree fold.

Summary: manipulating trees is one of the strengths of FP.

I know nothing about hardware design but

Functional languages are indeed excellent at expressing transformations on recursively-defined data structures like trees. Very concise, very elegant.

Check John O'Donnels Hydra.

Check John O'Donnels Hydra. It's a DSL in Haskell for HW description and simulation.

I'm not a hw guy, but it was nice to use (Dr O'Donnel uses it to teach computer architecture to CS/SE students at Glasgow Uni, where I studied).

It's probably best to email John to get the info on where it's at currently as I have not used it in more than a year.