There was a small math and computer science bookstore near NYU that I used to like visiting on Saturdays when I lived in the New York area. Back in those days I used to be really into pure math so I'd go there mainly to peruse math books with all sorts of fancy titles. I also liked flipping through the many programming books the store had scattered about. One day I discovered a green book called "ML for the Working Programmer" by L.C. Paulson and it introduced me to the beautiful world of functional programming. To this day it is one of my favourite programming books (along with "Expert C Programming - Deep C Secrets" by Peter Van Der Linden and "Design Patterns" by Erich Gamma et al.).

The Deep C Secrets book is pretty awesome and a very funny read. A financial "quant" in my old company who loved his Sun workstation showed it to me. One of the jokes in it I like is the one on why programmer's can't tell the difference between Halloween and Christmas Day (hint: read the dates and think of different base representations of the numbers). Real nerdy stuff but a lot of fun! Anyway, the clear way Paulson described programs with his many little examples and discussions of basic data structures like trees made functional programming appear to make a lot of natural sense to me. Many of these programs use recursion which actually makes the solution easier to understand. It employs the well tested lazy mathematician's trick of doing the least possible amount of work to transform your problem into a form that's already been solved (the one Gauss used to dazzle his school teachers when asked to sum the numbers from 1 to 100)!

Paulson introduces the reader to functional programming by describing a Standard ML program with Euclid's algorithm for the Greatest Common Divisor of two natural numbers (GCD). I'll also begin this tutorial on using Avalda FPGA Developer with this program, but with two changes - one relatively small, the other major. The small change is to re-write the program as a "quoted" F# one. If you know ML then it's easy to switch to F#, although F# supports OOP and .Net in a way that makes it very special. Even if you were to stick to processors and use F# in the conventional manner, the language has so many benefits that I could spend ages in a profitable exploration of subsets of them (eg, the LINQ stuff). For the next change, instead of compiling the program in the conventional way for execution on the hardware of the x86 chip in my laptop, I'll use Avalda FPGA Developer to transform it into a form of RTL verilog that solves the problem in a hardware description language for direct implementation on an FPGA chip (no processor or assembly involved!). Keep in mind that Avalda FPGA Developer does not compile .Net, but focuses on the aspects of F# that are closer to its functional programming OCAML roots so we can implement algorithms on FPGAs to take advantage of the natural fine-grained parallelism they possess (plus the abundance of registers found in FPGAs!).

So with that long intro, let us begin veering off the well trodden paths of programming for processors and begin a new journey on to new territory. Install Visual Studio 2008 shell (integrated mode), the CTP F# version 1.9.6.2, Avalda FPGA Developer, and Xilinx's ISE 10.1. Details of these steps can be found in the documentation included with the Avalda FPGA Developer download. Launch Visual Studio 2008 shell and click on "New Project", select the "Visual F#" project type and "F# library" template. Give your project a name like "GCDTutorial" and press the "OK" button. The template starts with the files "Module1.fs" and "Script.fsx" which you can delete. Go to "Project" -> "Add New Item", select "F# Source File" and type in a file name like "gcdtutorial.fs". Then hit the "Add" button and a blank fsharp source code file will open. The "# light" at the top means, well, that you can use a lighter form of F# syntax, but I prefer to have it off so add "off" next to it (quotation characters included). Next, don't forget to add the references, so go to "Project" -> "Add References...", then in the "Browse" tab find the Avalda FPGA Developer installation folder and add the dlls "avaldafs.dll" and "avaldax.dll". Normally you would also add "FSharp.PowerPack.dll" if you use the OCAML compatibility operators, but this example does not use any of them so leave it out.

Avalda FPGA Developer compiles "quoted" F# programs. Quotations are a feature in F# in which you wrap an F# expression in the quotation operators "<@@" and "@@>" so that the expression is treated like data and can be manipulated as such. The Avalda FPGA Developer api then allows the quoted expression to be translated to an XML encoding suitable for the core Avalda FPGA Developer compiler tool. So, write the following program and go to "Build" -> "Build GCDTutorial" to build a dll called gcdtutorial.dll:

#light "off"

namespace GCDTutorial

type GCD =

class

static member gcdprogram = <@@ let rec gcd( (m : int), (n : int) ) =

                                                        if m = 0 then n

                                                        else gcd( n % m, m) in () @@>

end

I put the quoted F# program as a member of a class but it can also be defined at the top level with no reference to classes. In the recursive call to gcd in your program, the arguments are evaluated in parallel when run on an FPGA. There are other ways that parallel code can be written for Avalda FPGA Developer. This means that although the syntax looks like F#, the semantics that Avalda FPGA Developer uses employs parallelism so you can specify that various expressions are meant to be evaluated in parallel. This particular gcd example does not explicitly bind a non-function variable with a "let" expression (eg, "let x = 5 in ...") but one key shift in thinking when developing "pure" functional programs is that such a binding does not necessarily mean that memory is reserved somewhere for the variable. In C#, for example, if you write a statement like "int x;" then 4 bytes will get allocated on the stack to store the value of x (remember, value types like structures get allocated on the stack and reference types like classes get put on the heap!). Not so in a "pure" functional programming language. Think of "let x = exp" as merely identifying the expression "exp" with x and nothing more. It's just like when you're doing math. The compiler will transform stuff around and figure out where to put stuff eventually but as a programmer you don't have to worry about that as much as in conventional "imperative" languages. Functional programming is a lot closer to the Unix philosophy of giving the programmer a few powerful constructs that he or she can use over and over again to build neat programs. A compiler like Standard ML even has a mathematical proof for how the whole thing works!

The above Visual Studio 2008 shell GUI also shows the F# Interactive window which is quite convenient for running your F# programs. It can be launched via the "View" -> "Other Windows" menu items on Visual Studio 2008 shell. The above program is first converted to an Avalda XML file by calling the Avalda.FS.XmlGen.FSToXml() function found in avaldafs.dll, with two arguments: the quoted program, and the path where you want the xml file to be written. The great thing about .Net is that since we've put our program in a dll, we can call the FSToXml() function anywhere in .Net, even from a C# program. C# used to be my favourite OOP language mainly because it looks like Java but has delegates. When F# improved, though, I donated my C# Programming book to Oxfam. The documentation for Avalda FPGA Developer has a C# example but in this tutorial we'll just stick to F# and call it from the F# Interactive window. Close the tutorial project first if it's still open or you may have some issues due to its referencing dlls that you need. Then open the F# Interactive window if it's not already open. Reference the avaldax, avaldafs, and gcdtutorial dlls using the '#r "path\\to\\dll"' dll referencing command. The path is in quotation marks and uses the escape "\" character before the path separator "\" so you separate elements in your path with "\\". Then call FSToXml as follows:

Avalda.FS.XmlGen.FSToXml(GCDTutorial.GCD.gcdprogram, "path\\to\\xml\\gcd.xml")

where "path\\to\xml" is the full path to the xml file where you want the results to be written. The first argument has "GCDTutorial" as the namespace, "GCD" as the class, and "gcdprogram" as the static quoted member which is your Avalda program. Because it is a static member you do not need to create an instance of the GCD class. You may get a dll referencing error as the F# interactive system goes through resolving references, but it should then work and write out the gcd.xml file. The fact that we use an xml intermediate schema for mapping quoted F# programs will become handy later when we show you how to write your own front end languages to be mapped to FPGAs with Avalda FPGA Developer. Incidentally, F# itself is great for writing your own front end languages (that's right, you can write your own scripting language and call it "MyPerl" or "MyDiamond" or the name of an old high school flame like "Lisa"!).

The main program for compiling code to RTL verilog is the avaldac tool located in the bin directory of your Avalda FPGA Developer installation. Run the tool on the command line with one argument being the path to the gcd.xml file created above, and a second argument being a path where the RTL verilog files will be written to. After running the command, we've now left the beaten path and entered FPGA country. Verilog, like its cousin VHDL, is a hardware description language. Its syntax is close to C, but its semantics are very different since it describes digital logic executing in parallel for real (as opposed to using a memory/processor based thread model). That means very strange things can happen if you're not careful! VHDL's syntax is closer to pascal and is a bit verbose.

We'll be running our example on the XSA-3S1000 board from Xess. This board has the Xilinx XC3S1000 FPGA chip with 1 million gates, and also contains a VGA interface, a 256 Mbit SDRAM chip, a 16 Mbit Flash device, a seven-segment led, pushbuttons, a PS/2 port (for connecting a keyboard or mouse), a CPLD to help program the FPGA, and an oscillator to generate the clock signals (among other things). Please visit Xess's Web site to find out more details of this board. I like it because it's simple, cheap, reliable, and comes with lots of tutorials on Xess's Web site. For those of you who are more hardware inclined you can have lots of fun with it building classic VGA games that run from the board alone! It also has a sister board for providing more prototyping space and lots of other goodies (eg, for audio). It has some simple GUI apps to help load the FPGA or the SDRAM/Flash. Many FPGA board vendors have similar apps that make it easy to work with their boards, along with helper verilog or VHDL files to further facilitate their use. These VHDL and/or verilog files can be used in a "black box" fashion if you are not as familiar with hardware description languages.

The netlist files generated above with the avaldac tool describe digital hardware. To make sense of it and map it to a particular FPGA, we'll use the free ISE tool from Xilinx. Each FPGA vendor has its own tool for mapping digital logic to its FPGA and I like ISE's because the interface is very intuitive. It is process oriented so you have a clear idea of exactly what steps you need to do and in what order to get the job done. Later we'll port Avalda FPGA Developer for use with Altera's FPGAs and their Quartus software tool but for now let's stick with Xilinx and ISE. In the next part of this tutorial we'll fire up ISE 10.1 and go through creating the bitstream file that gets loaded on to the FPGA.