Showing posts from January, 2010

Wrestling with C

I am by no means a critic of the C language. I think of it as portable assembler. If you need fine-grained control of every machine cycle, you use C. If not, you don't.  It's inappropriate for just about anything else. However, if you have control over everything the machine does, you have to tell the machine to do things that would happen automatically in other languages. Initializing integers to zero instead of whatever is laying around in memory. This caused a surprising problem in my advanced graphics class today. The professor has a library of matrix manipulation routines designed for translating, rotating, and scaling objects in three dimensions. He used them for a sample program with two dimensional graphics. However, sometimes the graphic would have a bunch of points at the corner of the window, even though it was supposed to be in the middle. What he eventually figured out was that he hadn't initialized the array that contained the z-coordinates. He assumed, qu

The elegance of Haskell

I'm usually pretty enamored with Python, but I think Haskell has it beat when it comes to generating the Fibonacci sequence. The most obvious way to write the Fibonacci sequence in Python is with a generator. def fib(): x,y = 0,1 while True: yield x x,y = y, x+y Hasekll, in contrast, uses a lazily evaluated list. At first I thought of such a list as a generator, but when I saw this example I realized that the lazy list was a lot more powerful. fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) In Haskell, 0 : 1 : 2 : 3 is equivalent to [0, 1, 2, 3] : it generates a new list. In this case, you're starting with [0, 1] , then adding more stuff to the end. In the first example, it's a list comprehension, approximately equivalent to [a+b for (a, b) in zip(fibs, fibs[1:])] in Python. However, you can't build a succint one-liner like this in Python because fibs has to be defined before

Implementing DES

It's a quite outdated now, but back in the day the venerable Data Encryption Standard was a really popular form of symmetric-key cryptography. I have learned about DES twice in my life, once my freshman year of High School and once this year in my Cryptography class. The second time around, having taken Computer Architecture, I was struck by how neatly DES's operations mapped to the most common machine instructions. I decided that this would be a good opportunity to practice some assembly programming. It seemed tailor-made for the purpose. I haven't actually written the assembly program. I wanted to get a working copy in Python running first, as a point of reference. I have made two implementations in python. The first converts all the integers to lists of ones and zeros, and uses Python's list manipulation abilities. The second stays at a low level and just uses bit shifting and that sort of thing. I'll post a more extensive write-up later. For now, l

XML can suck as a data format

There's a lot of hype about XML as a data format these days. Everything is supposed to be XML. This isn't such a bad idea. Any time you decide to use XML you don't need to invent your own syntax. (Side note: I think many people are confused about what XML actually is . I like to think of it as a syntax, rather than a language. When you make your own XML format, your basically inventing the semantics that go with the syntax.) Now, I think XML is great as a format for documents. I think that the combination of XML and XSLT could do a lot for achieving the kind of awesome flexibility of LaTeX while providing a stronger separation of semantics and presentation. The trouble is that XML often falls down when it comes to dealing with data (as opposed to a document). The bread and butter data structures of any programming language are sequences (variously called lists, vectors, arrays) and maps (variously called hashes, dictionaries, and associative arrays). For seria