The goto sin

This is the best rant on the demise of the goto statement I have ever heard. It is from the Tango conference 2008 – Fibers talk by Mikola Lysenko. If you fast forward to 23 min 05 secs, you will hear this:

One way you can think about states [in a state machine] is that they’re kind of a label. And you put this label here for where you want the code to goto after you’re done with this other, sort of, state. A state machine is kind of an indirect goto and so these states and switch statements are just like nested gotos within gotos.

Now if you use coroutines, you can then use structured programming to represent the states. I mean this is a debate that was you know, played out years ago in a more limited context of structured programming versus gotos and ultimately, structured programming won out.

Nowadays I mean if you go into entry level programming course, they’ll just fail you on your projects if you even use a goto statement because those goto statements are that toxic to the integrity of programming code. You’re much better off using structured programming. And yet despite that, people still advocate using these state machines which are basically a really indirect horrible obfuscated goto mess, just split across multiple source files and larger projects.

So it’s like if you make the goto sin big enough, then no one is going to call you on how bad it is! But the thing is if you use coroutines, not a problem! So why have we been using this all along? Oh once again I’d probably appeal to the fact that, ah, you know, ignorance, right, people just don’t know about coroutines.

Now I want my goto back… er… coroutines!

Book review: Learn to Tango with D

Learn to Tango with DOn my never ending quest to find the utlimate language for ASIC Verification, I decided to learn DigitalMars D. Yes, it’s called D, as in A, B, C, C++, D. It is a compiled, object-oriented, garbage collected programming language which runs as fast as C/C++, without the hassles of C/C++ and without the verbosity of Java.

So I picked up a bit of D on my spare time, and then a book came out, Learn to Tango with D. D is the language, Tango is a systems library. My main worry about the book was that I am not a Java, nor a C/C++ programmer. But to understand the book, you do not need to know C/C++ or Java. The authors take the time to explain the concepts as they apply to D, which is really great. Most of the book is about D, and that’s perfect for me. Starting from chapter 6 is where the authors present the packages of the Tango library.

If you want to learn D, you could read the D manual, but it would be like reading a dictionary: long and dry. To me reading the online D manual was not enough, because there were things that I did not understand, such as the imports of modules, the use of the static keyword (what it really does), procedural lifetimes, and some intricate details of templates. All those and more are explained in the the book. The book also does a great job at explaining arrays. Arrays in D are awesome, and go above and beyond what you find in Vera. For instance, D dynamic arrays support slicing, which means you can have multiple references to the same data in memory, or portions of that data. Isn’t this great? Imagine how this could simplify and speed up nested packing/unpacking of data structures: your data would not move in the computer memory!

So can D be used for ASIC Verification? Well, you’d need a few things, such as threading and fixed sized integers, aka bit vectors of arbitrary size. The Tango library has Threads and Fibers, and with Fibers you can build coroutines, and with coroutines, you can build a simulator with mailboxes, semaphores, mutexes, etc. The first time I saw a demonstration that a simulator could be built with coroutines was in MyHDL but I am sure there are others. So I have no doubt a HVL simulator can be built with Tango Fibers. Tango also has a nice Logger package, meaning you don’t have to invent one.

D has assertions, which are equivalent to the boolean layer of SystemVerilog assertions. This is really an unfair comparison, since D was not designed as an HDL, nor as an HVL. If you need the full spectrum of HDL assertions, you’ll have a lot of work to do. Ideally, you’d also want a constraint solver, a constraint language, and something for functional coverage too. That’s a lot of things to be added before D can be used for ASIC Verification.

Nevertheless, D is great and I definitely recommend the book if you want to learn D and the important packages of the Tango library. The book has many code examples which greatly help understand the concepts.

Living without a constraint solver

For a while I was hooked on constraint solvers, to the point I relied on them to solve even the most simplistic problem, paying a hefty price in simulation time. One of those simple problems is selecting values from a list. The typical wrong way to do this is with the constraint solver. You’d usually declare a constraint like this:

class A {
  rand integer thing;
  constraint my_con {
    thing in {7,8,34};
  }
}

Obviously, this is short and sweet, but picking a value for the “thing” variable invokes the constraint solver. It is much more efficient to approach the problem by randomly picking from a list:

integer things[] = [7,8,34];
thing = things[random()%things.length];

A variant of that is when we want to pick a sequence of things, without repetition. Once we’ve gone through the sequence, we want to shuffle it and start over. I coded the following in D, to demonstrate:


import tango.io.Stdout;
import tango.math.Random;

// The Knuth Shuffle (from wikipedia)
void shuffle(int [] list) {
  auto rand = new Random();
  int n = list.length;
  while (--n > 0) {
    int k = rand.next(n+1);
    int temp = list[n];
    list[n] = list[k];
    list[k] = temp;
  }
}

class Buffer {
  int size;
  byte [] data;
  this(int size) {
    this.size = size;
  }
}

void main() {
  // Some buffers with interesting sizes
  Buffer [] buffers;
  buffers.length = 3;
  buffers[0] = new Buffer(7);
  buffers[1] = new Buffer(8);
  buffers[2] = new Buffer(34);

  // A list of numbers
  int [] list;
  list.length = buffers.length;
  foreach(idx, ref value;list) value = idx;
  shuffle(list);

  // Use the shuffled list to traverse
  // the list of buffers in random order
  foreach(idx,value;list) {
    Stdout.formatln(
      "buffers[{0}].size = {1}",
      idx,
      buffers[value].size
    );
  }
}

Shuffling the list is a O(n) operation, and there is no need to invoke a constraint solver. Each time you need to go through a list of things in random order, you can use the shuffled list of integers to traverse it.