Go Language: Boolean Grammars

Posted
Comments 5

As part of the new project "New Project: Cross-Validation, Var Importance & More", we are also adding support for the Go programming language in Logic Synthesis. And as usual, this includes support for 6 different Boolean Grammars: The All Gates Grammar, the NOT-AND-OR Grammar, the NAND Grammar, the NOR Grammar, the MUX Grammar, and the Reed-Muller Grammar (or NOT-AND-XOR Grammar).

As mentioned in the post "Support for the Go Language in GeneXproTools", the support for the Go language in GeneXproTools was spearheaded by Glenn Lewis, who also shared with the GeneXproTools community 5 of the Go Boolean Grammars. We've now tested Glenn's Boolean Grammars and also added the missing Reed-Muller Grammar.

Creating the grammar for the Reed-Muller System (NOT-AND-XOR system) can be a little bit tricky for programming languages such as Go that don't have a built-in XOR function for booleans. And I must say that of all programming languages supported by GeneXproTools (Ada, C, C++, C#, Excel VBA, Fortran, Go, Java, JavaScript, Matlab, Octave, Pascal, Perl, PHP, Python, R, Visual Basic, VB.Net, Verilog, and VHDL), Go is the only one without a built-in XOR!

This could be really problematic because we would have to go from the most common encoding of "x XOR y" used in almost all programming languages to "XOR(x,y)". And I can tell you this is no easy task, especially if you're doing this for the first time for all the 258 built-in Boolean functions of GeneXproTools!

But fortunately we don't have to do this from scratch! We already have in GeneXproTools two programming languages that use the required "XOR(x,y)" encoding: Matlab and Octave (the R language is another odd ball, but the R Boolean Grammars will only be added to GeneXproTools with this mini-release). Both these languages have a built-in XOR function that for whatever reason is implemented as a function call. This means that we can use the Matlab Grammar for the Reed-Muller System as template to create the Go Reed-Muller Grammar!

I must say I was very relieved when I realized that I could use the Matlab Grammar as template for the Reed-Muller System. For a couple of hours I just cursed the Go language and whoever decided not to include a XOR function. But then I went back to my archives and that's when I found the work I've done several years ago for the Reed-Muller System in Matlab (I must have cursed Matlab then, but I don't remember). But anyway, the world returned to its axis and I couldn't care less about the nonexistence of XOR in Go (although I should say, it would be a nice addition to the language).

Over the next posts I'll talk more about each of these Boolean systems and how to generate them for the Go language.

Update:

It turns out there's already an XOR operator in Go! It was buried so deep we had some trouble getting it out, but here it is:

x != y

Many thanks, Tony! I'll have to update the Grammars now…

Author

Comments

  1. Tony Wilson

    Maybe I am missing something but Go has x ^ y as a normal integer operator and Xor(x,y) in math/big

  2. Candida Ferreira (Author)

    Thanks, Tony. That is true but for GeneXproTools we need a Boolean xor function or operator. I’ll update the post to reflect that.

  3. Tony Wilson

    Ok. Think I’m caught up. Go has strong typing on bools preventing arithmetic. So you cannot say “if x ^ y “ in Go but you can in C.
    The only way around it is to forego the use of bools and use uint8s with the more messy “if x ^ y != 0” (or == 1).
    Of course the NOT ! then also becomes messy.
    Pity Go forgot the gates it runs on ;)

  4. Tony Wilson

    After reading code.google.com/p/go/issues/detail?id=6304 it clicked that x != y is x XOR y for bools. Ugly but true. (Oops)

  5. Candida Ferreira (Author)

    Thanks, Tony! It’s indeed true; the Go gang is forgiven. I’ll have to update the post and the Boolean Grammars too…

Comment

Enter your comment below. Fields marked * are required. You must preview your comment first before finally posting.





← Older Newer →