Category Archives: programming

Random linear algebra hackery in Scala

One of my random pet projects at the moment is putting together a prettified linear algebra API for Scala. I’m not implementing the linear algebra routines myself, but am instead implementing it as a wrapper over Colt. This isn’t really any sort of stable release or project. It’s more of a “If you want this sort of thing you might find it useful” comment.

The basic design is:

Everything is mutable, but the API encourages using it in an immutable way.
Makes no attempt to hide its colt origins. If you want to use it with Colt proper, it will cheerfully let you do so, and you will often have to explicitly use colt classes.
API loosely inspired by matlab/Octave
Hideous abuses of overloading, implicits, functional programming and symbolic method names abound in order to get an API that allows for very compact code. If you don’t like this sort of thing you may want to steer clear. :-)

It’s currently available from my misc hg repository, but it’s getting large enough that I’ll probably factor it out into its own soon.

SBinary 0.2

I quietly uploaded SBinary 0.2 last night. I was going to write up some documentation for it today and do an official announcement, but it’s now coming up to 19:00 and I still haven’t written any documentation so I have a sneaking suspicion it ain’t happening today. So, if you want to have a play with it there’s a new jar and scaladoc up there.

Changes from 0.1:

Improved API which is less closely tied to java.io
Supports a wider range of collections and standard types (not the entire standard library as I’d originally said I was going to do. There are some issues surrounding collections and open unions which I want to resolve before I do that).
A limited amount of support for lazy IO using Stream. (Specifically, Stream is read lazily from an input. However there are a lot of limitations on this at the moment). The design is such that it should be impossible to incorrectly interleave IO actions (i.e. reading something else from the input will force pending lazy reads to complete).
Improved some performance stupidities (nonbuffered reading/writing to files, unspecialised reading/writing of byte arrays)
Improved generic combinators for building binary instances (although the “case classes for free” one I want to add is waiting on a compiler bug before I can add it)

I hope to write up some proper documentation soon, and when I do I’ll send an announcement to the mailing list. In the meantime, feel free to have a play.

Book Review: The Art of Assembly Language

I’ve been meaning to get a handle on a lot more low level programming details for a while. I can do C, more or less, but I only had the vaguest notion of the lower level CPU architecture and assembly language. While I was over in the states, Victoria made the mistake of taking me into a book store. I emerged several books later. Among them, The Art of Assembly Language. This post is a review of the book. Well, ok. It’s more of a rant about the book.

First off, let me say this: I liked this book. I read it cover to cover (although a few of the chapters I only skimmed), which is extremely rare for a programming book. I can’t offhand think of another example of one I own (of which there are many) which I’ve read that thoroughly. Most of them I dip into and read chapters out of order as I feel like it. I came out feeling like I had a much better understanding of the way the x86 architecture works and various details that had previously escaped me. It’s interesting and largely well written.

So, it’s a good book, and I’m glad I read it. And that’s the last positive thing I’m likely to say about it in this post. The rest of the post is me being mean about its flaws.

First off: After reading this book, one comes out with a good sense the way various aspects of assembly are constructed and used. It clears up a lot of misconceptions you might have had if you don’t already know assembly and provides a high level sense of what makes up an assembly program (Examples: I had previously assumed that the stack was purely a higher level construct and didn’t have any specific CPU support. I also hadn’t realised quite how significant registers were for… well, everything, or the way the FPU was set up in relation to the rest of the CPU instructions). What it doesn’t teach you to do is write assembly.

The text uses High Level Assembler. This is an interesting pedagogical tool, as it certainly helps to remove a lot of the scariness of writing assembler (compare the hello worlds for example). The problem is that it’s not really an assembler. Instead it’s the bastard offspring of a highish level language (well, low to mediumish. Somewhere a little above C but below C++) and x86 assembly. Worse, the bits that look like x86 assembly often aren’t. Some of this takes the form of relatively harmless little extensions. e.g. in x86 assembly the mov instruction may only move data between registers or a register and a memory location. You can’t mov between two addresses in main memory. In HLA you can. mov(x, y) translates to push(x) pop(y).

If you know your assembly, you’ll just have spotted the other far more insidious way in which it’s different (I do not know my assembly, hence only discovered this on a) Reading some NASM source and getting very confused and b) Reading FAQ entry 8). The operands are backwards from intel’s mnemonics. Mostly. Except when they’re not. So in other words if you learn to write HLA you will most likely completely destroy your ability to write other assemblers because you will constantly get fuddled by operand order (ok, that’s probably not true. I suspect a few weeks with an assembler and someone standing over you with a big stick would cure that).

But that’s ok. I mean, surely HLA is a mature and well tested product? It’s been around for over a decade. If it’s that much better than existing approaches to assembler, what’s the harm in doing things differently?

Um.

Setting aside any philosophical issues with the way HLA does things, the author repeatedly and insistently describes the current implementation of HLA as horrible, not designed for performance and a prototype. This does not exactly fill me with confidence.

So, what does HLA add on top of x86 assembly?

A nice standard library.
In particular, good String handling (better than C’s in my opinion).
Support for composite datatypes (records, unions, pointers, arrays)
A calling convention for passing arguments to procedures. I’m not thrilled by this – something like it is definitely useful to have, but the calling convention chosen suffers from the C problem of making it all too easy to copy large amounts of data around on the stack (more so: It passes arrays by value).
A macro language (the author seems to be convinced that this is the most advanced macro language ever. It’s not. It’s a half assed scripting language built into a preprocessor. It’s not really better than using something like fmpp or similar. It’s not even close to lispy macros).
Ten thousand different types of loop.
Exceptions ?!
Objects ?!?!

The exception subsystem makes me particularly mad. The book goes into a great deal of detail (too much detail) about how all the different control flow extensions are implemented and is completely silent on the subject of exceptions. I assumed that this was an advanced subject left to the HLA manual. Not so much – no description of detail there.

So, we have a high level feature whose implementation is undocumented and which is used in many places in the standard library. It’s good that we’re writing assembly here – it really lets us see what the close to the metal programming is like.

The objects section is just sad. I don’t really have anything more to say about it than that.

As a tool for teaching, HLA serves its purpose, but it would work a lot better if it were heavily trimmed down and made less of an attempt at being higher level than normal assembly and more of one at being a lot of useful libraries, some extensions for procedure calls and a better macro language. As it is, I certainly wouldn’t want to program in it.

A cute hack: Changing the scope of System.out

This isn’t any sort of deep trick. I just found the results surprisingly pleasant, so thought I’d share.

In the GUI interpreter I need to be able to capture standard out. Doing println in the interpreter should print to the screen, not the console. And that’s fine. Java provides System.setOut. I had to fight the stupidities of java.io a bit to make it work (annoying details with flushing among other things), but it did in the end.

There is of course a problem with this. System.out is basically a great honking big global variable. We’ve now made it impossible to run multiple interpreters in the same VM. Le sigh.

Ok. So, what we do is a bit of juggling and set System.out appropriately before interpreting each thing. Right?

Nope. Doesn’t work. These things can and do live in separate threads. And for that matter, what about background threads spawned by one of the interpreters?

The solution is to make System.out thread local. And not just any type of thread local – an inheritable thread local. Spawned threads need to inherit the System.out of their parent thread so that something like spawn { println(“Hello world”) } prints to the right screen.

Once you have this, the idea is obvious. You define an object which extends OutputStream but delegates all functionality to some thread local variable (snarfing the System.out that was present when the object loads as the default value), set System.out to be a print stream wrapping that and you’re done. You can now set its value in a thread local way and multiple interpreters can coexist peacefully.

Like I said, nothing special, but it seems like a surprisingly handy trick.

GUI interpreter frontend coming along nicely

I’ve separated the interpreter frontend out into its own separate project. It’s available at http://www.drmaciver.com/repos/guinterpreter/

It’s doing pretty well. The UI has been improved, it supports multiple interpreter windows in the same VM, and is generally in a pretty usable state. It still has a few quirks, but it’s getting there (still a little bit of a headache to set up, but I’ll work on that). My plans for the immediate future mainly revolve around UI polishing and embeddability – I’d like it to be really easy to include this inside another (Jambi) application. hemant / gnufied has been taking a look at the code and has some interesting plans for it, starting with syntax highlighting. I’ve given him commit access, so we’ll see what happens on that front.

If you want to give it a try, go right ahead. You’ll need to resolve the Jambi dependency yourself, but otherwise it should be pretty easy (I will probably set up some sort of maven (sigh) repository for the jambi dependencies and switch the build script over to buildr so it can use them at some point, but I haven’t yet).