Monthly Archives: June 2013

0.0.2 posted: Adds module/subcircuit support

Version 0.0.2 is now up. The sole goal of this version is to enable subcircuits. Admittedly, if the immediate goal were to simply bring Toves to a usable level, I might concentrate on copy-and-paste or saving files, which it still lacks in this version. But subcircuits are central to Toves’ core, and I wanted to make sure it was built into Toves as quickly as possible. Indeed, in implementing this I found that it is already more complicated than I had expected.

Subcircuits are implemented by adding “Input Pins” and “Output Pins.” This is something of a departure from Logisim, where the toolbar had these pins that doubled as Toggle Switches and LEDs. In Toves, this is currently separate, and my plan is to keep them that separate unless there’s a groundswell of disapproval. (However, I do hope to make Input Pins be interactive in the same way that Toggle Switches are.)

Unlike Logisim, signals are propagated into Toves subcircuits instantaneously. That is, suppose I have a subcircuit “Invert” that consists simply of an input feeding into a NOT gate feeding into an output. In Logisim, using “Invert” would be a bit slower than simply using a NOT gate: If I were to connect a signal into a simple NOT gate and also into an “Invert,” and if I were to connect both into a XOR gate, the XOR gate would occasionally (though very quickly) have an output of 1. In Toves, the XOR gate is always 0.

Also unlike Logisim, the pins are genuinely bidirectional. The terms “input” and “output” are somewhat misleading: The only difference is in which way they face and in what side of the subcircuit they appear. If you wanted to send a signal out the left-hand side of the subcircuit (which admittedly is a bit confusing), then you’d simply use an “input pin.” If Toves already had controlled buffers, then you could easily have a pin that sometimes acts as an input and sometimes acts as an output.

C# regrets? No.

I mentioned the decision to implement Toves in C# earlier, leaving discussion of C# itself for later.

I came to C# after years of developing in Java, including Logisim but also several other smaller projects. I had grown familiar familiar with Java. Since C# is quite similar to Java, I expected the adjustment to be easy. And while it has been straightforward, it’s been more involved than I expected. The two languages do have some key differences.

Overall, the differences are just that C# has more features – the language has evolved at a more rapid pace than Java has. Some features are nice, others just aren’t very useful. I particularly like properties, language-level event support, and anonymous functions. Also, extension methods are a nice idea that works better than I would have expected.

What I miss most from the language is Java’s package-level protection. Instead, C# has “internal,” which allows access across all namespaces in the assembly, which is more permissive than is useful. I’ve ended up doing some ugly work with “keys,” which some objects generate and which other classes demand in order to perform a method. What I’d really like is “friend” classes such as C++ has, but only members specifically marked as for friends (“shared”?) would be available to them.

My complaints about C# have to do mostly with the infrastructure. First, as I already mentioned, I haven’t yet figured out a way to make it easy to install and execute Toves across multiple platforms. I’m sure there’s an answer, but it’s not there yet.

The libraries are decent, but I miss the JavaDoc API reference. Mono’s documentation is too spotty to be competitive. The MSDN documentation is reasonably complete, but it’s not as easy to navigate as JavaDocs. For GTK#, I find I often have to go to the original GTK+ documentation of the C API and then guess how it might have been translated into the GTK# API.

There’s also the matter of the development environment. I’ve heard that Visual Studio is impressive, but I’m developing on a Macintosh, so I’m using MonoDevelop. It’s a passable development environment, but I miss Eclipse. One persistent though simple missing feature: It’s difficult to view compiler error messages in their entirely. Another is that the IDE seems to pause unreasonably at times, even when code completion is turned off.

Overall, though, I’ve been happy working in C#/Mono, just as doable as Java.

Main window layout

The feature that I’m currently working on is adding subcircuits. This is relatively complex, but doing this well is central to Toves’ design, potentially cutting across all layers of its design, so I want to tackle it early.

I’m beginning, naturally, with the interface for managing circuits. In Logisim, to the left you find the canvas, to the left of which you find the “explorer pane” with the “attribute table” below it. In the explorer pane, you find a list of the loaded “libraries,” including the project’s subcircuits as the first “library”. So far, what I’ve implemented for Toves is basically the same. The only significant difference is in terminology: I’m planning to call this the “toolbox” with “drawers” (rather than an explorer pane with libraries). But the appearance is identical.

(On a tablet, screen real estate is more precious, so I think the toolbox wouldn’t always be visible. Instead, there’d be an icon of a toolbox, which when tapped would pop up basically the same structure (though shown as an accordion rather than as a tree). On a desktop computer, being able to see the toolbox continuously seems a good way to use the extra real estate – plus clicking an icon is more laborious with a mouse than with a finger.)

I’d like to think about this more creatively, but ultimately I’m not coming up with good alternatives.

Naming Toves

So what’s going on with the name “Toves”? After all, Logisim has built up solid name recognition over the years.

When I started it back in 2000, I didn’t put much thought into the name at all. I was simply interested in building the software for my students without any hope of the project going further. So I simply chose a functional name summarizing the purpose of the software. But I posted it in case somebody else would like the project, and as Logisim began being picked up by other schools, the software began becoming more sophisticated. But while I never really liked the name much, it was never time to split with it.

The name Logisim has some disadvantages. For one, a domain name isn’t available. Even on SourceForge, Logisim is filed under a different directory because a previous open-source Logisim project already existed. (It didn’t exist when I started Logisim, but my Logisim didn’t go to open-source and go onto SourceForge until much later.)

Besides, keeping the name Logisim could lead people to expect backward compatibility. But Toves is planned as a clean break: Several of the components will be designed with different appearances, incompatible with what appears in Logisim.

What’s more, if I kept the name Logisim, I was left wondering what to do with version numbering while Toves was in the middle of development.

So what’s behind the name “Toves”?

  • Since I was thinking that it would eventually have Verilog support, I decided to look for short words with the letter v in them. I knew I needed a rare word so that I had a ghost of chance of landing a domain name. So I looked through a dictionary, and Toves stood out.

  • Of course, anybody thinking of a tove is bound to think of Lewis Carroll’s books, and Lewis Carroll was himself a logician. A bonus: Carroll’s book contains some nice public-domain artwork depicting a tove, which I’ve reused liberally.

  • There is no other software package named toves, and the domain name was available.

  • I could come up with a tortured acronym that perhaps would apply some day:
    The Omnific Verilog-based Editor and Simulator.

  • Lots of open-source projects have a mascot. GNU has its gnu, Linux its penguin, GIMP its coyote, Firefox its firefox, Hadoop its elephant. But the tove has sadly been neglected.

Under the hood: Transactions

The final major “under-the-hood enhancement” in Toves’s design worth discussing is the transactional-based access scheme. In Logisim, there is a persistent bug where a circuit’s simulation occasionally messes up. It seems to be quite rare, even for large circuits, and it happens unpredictably. My best guess is that it has to do with multithreaded access.

To avoid multithreading issues, Toves uses the concept of a “transaction” from databases. Its key data structures (the circuit layout, the simulation engine, the overall project) provide no way to access them directly. Instead, you have to nest all access within a transaction. In the program, it looks like this:

Transaction xn = new Transaction();
ILayoutAccess layout = xn.RequestReadAccess(layoutStructure);
ISimulationAccess sim = xn.RequestWriteAccess(simulationStructure);
using (xn.Start()) {
    // code using layout and sim to read layoutStructure and modify simulationStructure

The ‘layoutStructure‘ object actually doesn’t even have methods like ‘GetWires‘ or ‘AddWire‘. Such methods are provided in the ILayoutAccess interface, and such methods always confirm that the transaction is still live before proceeding with their work.

The example above shows how a transaction can request simultaneous locks on different structures. If there prove to be issues with deadlock between transactions, these will hopefully be able to be addressed by making Transaction’s Start method more sophisticated in the order in which it obtains locks.

(I suspect that the distinction between read access and write access is a matter of overengineering: In practice, it probably happens that two threads never end up getting read access simultaneously.)

This should degrade performance somewhat, as repainting the circuit (which happens often) will never happen at the same time as stepping the circuit (which happens extremely often). But this simultaneous access is exactly what makes bugs possible – and in practice I believe the interface events like repainting the circuit happen at most 50 times per second, whereas the simulation-stepping transactions happen upwards of 1,000 times per second. In any case, the locking can easily be removed (by making Transaction’s Start method do absolutely nothing) if performance proves problematic – though that requires more fine-grained concurrency that may actually hurt performance even more than the exclusive access.

Under the hood: Hash tables

[I have a few more posts describing what’s going on “under the hood.” I hope you’re finding this interesting… but what I’m really hoping for is to find commenters who are ready to discuss/critique what they’d like to see from the user-facing features. For instance, how should a counter be drawn in the circuit, and with what inputs/outputs? Or what file format should Toves use?]

Another change “under the hood” in Toves is a move away from hash tables. Logisim uses hash tables liberally: For the circuit under simulation, there is one hash table that maps locations to the values stored at those, and there is another hash table that maps circuit components to their individual state (for components that have state, like flip-flops). And there are several hash tables beyond that.

I believe a large fraction of Logisim’s simulation time is spent in hash table lookups, and so Toves is much more careful in avoiding hash tables. For example, stylistically it’s tempting to have a hash table mapping each “node” to its current “value,” since the current value is conceptually not a property of the node. But it’s more efficient for each node to have a mutable field saying what its value is. (Actually, Toves groups linked nodes together into “subnets,” and each node has a mutable field saying what subnet it belongs to; the subnet is actually where the value is stored.) To look up a node’s value, it has only to dereference a couple of pointers, which should be far faster than a hash table lookup.

In fact, right now the simulation engine in Toves includes just two hash tables. (More could easily be added as more features are added – two big missing features that potentially will involve substantial edits to the simulation engine are subcircuits and splitters.) One of these hash tables is used to track which subnets have changed in the current time step, so that subnets’ values aren’t re-computed when the result is guaranteed to be the same. Another tracks which components have seen their inputs changed, so that we don’t ask the components to recompute their output values.

As I write this, I believe each of these remaining two hash tables could be replaced with an array-backed list accompanied by a boolean flag in the subnet/instance indicating whether it is already in the list. That should be more efficient (though there are potential problems with this for a multithreaded implementation to take advantage of multicore computation, which is something that I hope in the vague future to tackle). I plan to look into that after adding subcircuits and splitters.

Under the hood: Simulation data

Many of the biggest changes from Logisim to Toves are “under the hood,” some of the more important of which I’ll explain in the next few days. These changes are basically invisible to a user, though it has major implications for the code design and features provided.

This post will discuss the biggest of the changes: How circuits are represented during simulation. Logisim has just one representation of the circuit layout: During simulation, it remembers, “there’s a 0 at this coordinate, X at that coordinate” and so on. By contrast, as you build a layout, Toves “compiles” the physical layout into a separate data structure corresponding to the circuit’s logical connections. Toves represents a set of linked wire segments as a system of “nodes” and “links” between them. The simulation code has no knowledge of coordinates. It also forgets about components and subcircuits, dealing simply with a collection of “instances.”

Naturally, Logisim’s approach has some advantages. It is conceptually simpler, and it has less redundancy, so there are fewer data structures to keep “in sync.” By contrast, Toves maintains two redundant representations of the circuit – one representation used for drawing and editing, with another representation being used for simulation. Keeping these two representations in sync is tricky. In fact, I started work on this concept several times over the last several years before finally getting this version to work.

While Toves’s technique is more complex, there are of course important reasons to keep them separate. First is the efficiency angle. Actually, the Logisim approach has the potential to be more efficient for *drawing the circuit*, which works with the layout information but Toves must repeatedly map to the simulation to determine what values to draw. But for *simulating a circuit*, the Toves approach can potentially be faster – both because the data structure it’s working with is designed explicitly for simulation, and because the structure itself is simpler, providing more room for further optimization. So do we go for efficiency at drawing or at simulation? Well, there’s little reason to repaint the circuit more than 30 times a second, but we hope to execute thousands of simulation steps each second, so priority should go to simulation.

Another advantage to Toves’s approach is an issue of software architecture. Once you get past the complexity of maintaining a mapping between layout and simulation representations, Toves has the advantage of being cleanly broken into “layers”: At the bottom, you have the simulation model, then the simulation state on top of that, then the layout model, then the abstract GUI code (written to be independent of platform), then the actual GUI implementation. Toves tries to keep the layers more separate, with one-way dependencies between them; by contrast, Logisim is not very cohesive, with packages/namespaces freely depending on one another.

Finally, separating the simulation representation from the physical layout should make it easier to support project modules being defined not by a physical layout but by HDL code (whether Verilog or VHDL). With Logisim, we’d have to make up a fictional graphical layout corresponding to the textual code, whereas with Toves we can compile both the HDL code and the physical layout into the same underlying representation. Admittedly, support for HDL code is a long way off, but I’m hopeful that Toves will be ready for this when the time comes.

Choosing C#

In starting Toves, one of the first decisions was: What language to use? Of course, Logisim uses Java. This has served it well, particularly in providing a platform where development can happen on any platform and it easily ports to Linux, MacOS, and Windows computers. Being cross-platform is a central feature of Logisim: Many universities assign Logisim projects as homework, and students want to complete the projects on their own computers, whatever they are.

At the same time, a lot of people have wanted to run Logisim on a tablet device (iOS and Android in today’s world). Unfortunately, there’s no strong solution for executing Java under iOS; and while Java works well for Android, its Swing GUI API does not, and unfortunately Swing is more deeply embedded throughout Logisim than it should be. (With Toves, I’ve been careful to add a layer so that the core program doesn’t refer to the GUI.)

Beyond tablet compatibility, Java also has some political problems – to me, these are secondary to tablet considerations, but they still can’t be ignored. One problem is the open-source angle: Oracle doesn’t seem committed to a genuinely open system (witness the Google lawsuit). More practically, Java suffers from a bad reputation on the security front. As far as I can tell, this reputation is unfair. Sure, the browser plug-in for running applets has shown persistent problems, but Logisim isn’t an applet. Though the message people should get is “Java is OK, but disable the Java browser plug-in” (as I certainly recommend, since it’s not too useful anyway), but what they hear is “uninstall Java.” That’s unfortunate, since Java is quite useful for applications like Logisim, and I believe Java has a good security record for such applications. Nonetheless, it’s reality that Java’s reputation suffers.

What about a browser-based implementation using JavaScript? Actually, I looked at this fairly carefully. Performance would take a hit, but the no-installation benefits were too great to ignore. Last summer (Summer 2013), I used JavaScript to develop a bare-bones browser-based logic simulator (Electra’s Workshop, – which does roughly everything that Toves currently does. Despite quite a bit of effort, it still doesn’t work as well as I’d like, which is why I haven’t publicized the effort much. In any case, I don’t think browsers are ready for a Logisim-scale program.

Ultimately, I chose C#, since it still allows development that works across Linux/MacOS/Windows, and it should also port to iOS and Android (though I haven’t really toyed with this enough to be sure). I had some reservations, largely because I would have to learn the language from scratch, though admittedly C# is very similar to Java.
So far, I’ve been happy with C#. My biggest surprise is that, despite being so similar to Java, C# is just different enough to require a substantial adjustment. I still haven’t adjusted entirely, and overall I still prefer Java, but I’m finding C# a very workable alternative. I’ll probably write more later about my critiques of C#.

My biggest recent frustration has been in packaging Toves for cross-platform distribution. This wasn’t particularly easy with Java, but over the years I had basically figured out a workable solution. I’m confident I’ll be able to figure it out for C# as well. For right now, I have some fairly ugly instructions written up for each platform at Linux and MacOS are OK – though not as easy as I’d like – but installing and executing Toves on Windows is a major pain. You might think: C# was originally designed for Windows, so shouldn’t it be easy? But Toves depends on Mono being installed, and I haven’t yet found a way for Toves to automatically find Mono upon startup. I’ll be looking for a better technique.

Why Toves?

Why Toves? I’ve developed Logisim for over twelve years, but over time I’ve found some inherent limitations that are deeply embedded in the system but prevent it from maturing to “the next level.” Rather than try to find some route to overcoming these several limitations within the current framework, I wanted to build on a replacement system from scratch. Hence this project.

Logisim represents a lot of accumulated work, so naturally replacing it will take a lot of work. Though I’ve put significant work into what Toves is today, it’s not very far. Right now, all Toves can do is allow you to build and simulate a simple circuit out of 2-input AND, OR, and NOT gates. No subcircuits, no multibit wires, not even copy-and-paste or opening a file. For now, what makes Toves interesting is primarily what’s under the hood, which I’ll discuss in later posts.

But while it’s hardly useful, I’ve now uploaded the first working version – version 0.0.1. While it’s not particularly useful, it’s there for you to look at and critique.

In this blog, I hope to chronicle the progress of Toves development. Some posts will present user-facing design decisions, seeking feedback on ways to improve. Others will describe internal architectural decisions, reflecting lessons learned the hard way from Logisim. My hope is that others will contribute comments, leading to ideas that ultimately will lead Toves to be even better than it would be if I worked in isolation.

To give you a taste of what to hope for from this project, here are a few of the features that I eventually hope to include in Toves, but which aren’t in Logisim:

  • Diagonal wires [This is in Toves today: Horizontal/vertical is the default, but alt-drag creates a diagonal wire.]
  • Canvas extends infinitely in all directions (rather than having a fixed upper left corner) [This is in Toves today.]
  • Z-ordering of components preserved
  • Drawing arbitrary shapes like rectangles or lines in a layout
  • Modules of varying types – usually a layout (the only Logisim option), but a module might also be a memory, a truth table, or a state machine – and hopefully one day source code (perhaps written in Verilog)
  • No delay in sending signals into a subcircuit (Logisim introduced a one-step delay when sending a signal into or out of a subcircuit)
  • Bidirectional connections into subcircuits
  • Eight-valued logic, allowing weakly-driven 1’s and 0’s – particularly useful for open-collector circuits
  • An oscilloscope for viewing how signals change over time
  • Components that must be “closed” once the simulation becomes inactive – particularly file and network I/O
  • Components that “time out” after a period, like a monoflop.
  • Tablet support under iOS and Android.

I invite you to follow along in the coming months – maybe years – and to participate in the discussion!

What features would you particularly like to see (or not see)?