Symmetry in Languages

This post is about languages and grammars*, and I'll be using examples in a pseudo-BNF notation which looks like the following:

abc ::= ('foo' <bar>) | <baz> | <bar> <baz>

This reads as "An abc is defined as the letters 'foo' followed by a bar, or as a baz, or as a bar followed by a baz."

Consider the Newspeak language from George Orwell's 1984. Part of the grammar would look like the following:

word ::= ('un' <base>) | <base>
emphasised ::= 'plus' <word>
twiceemphasised ::= 'double' <emphasised>
valid ::= <word> | <emphasised> | <twiceemphasised>

Such a grammar allows us to, given the base word "good", say the valid words "good", "ungood", "plusgood", "plusungood", "doubleplusgood" and "doubleplusungood". This is the entire spectrum of "goodness" allowed by Newspeak, which is a purposefully restrictive language.

Now, what happens if we get rid of some of these rules? Let's try getting rid of 'twiceemphasised':

word ::= ('un' <base>) | <base>
emphasised ::= 'plus' <word>
valid ::= <word> | <emphasised>

We reduce the expressiveness, since we now only have one way to emphasise things, there's no level above "plusgood".

Now what if we get rid of "emphasised", but just call it another kind of "word"?

word ::= 'un' <base> | <base> | 'plus' <word>
valid ::= <word>

Now, the definition of "word" contains the use of a "word", which is recursive. What does this mean? Well "plusgood" is now a "word", and we're allowed to write 'plus' in front of "words", so we can say "plusplusgood", "plusplusplusgood" and any other number of new words. We can also say "plusplusungood" along with an infinite number of negatives.

Thus getting rid of rules completely (like "twiceemphasised") reduces what we can say, but by getting rid of distinctions and special cases (like the distinction between "word" and "emphasised") we get a whole new level of expressiveness. In fact, since we can say "plusplusgood" there isn't a need for "doubleplusgood" anymore, it's redundant, so there's no point putting it back in. Also, the idea of "valid" is also redundant, since it's now just the same as a "word", so we can get rid of that too, to reduce our entire grammar (minus the "base" vocabulary of words like "good") to:

word ::= 'un' <base> | <base> | 'plus' <word>

This grammar, even though it only contains two concepts, allows us to say infinitely more than the original grammar that contained five. We can even get rid of the distinction between "base" and "word" by writing it as:

word ::= 'un' <word> | <base> | 'plus' <word>

Now we can say "unungood", "unplusgood", "plusunununununplusplusunplusgood" and infinitely more new words.

Now, where am I going with this? Well, let's consider a bit of grammar for the C programming language:

simpletype ::= 'int' | 'float' | 'double' | 'char'
modifiedtype ::= <simpletype> | ('const' | 'long' | 'signed' | 'unsigned') <modifiedtype>
composite ::= <union> | <struct>
pointer ::= <type> '*'
type ::= <pointer> | <composite> | <modifiedtype>

This is a bit off, but will serve for our purposes. It says, quite simply, that we can make things that have type "int", "float", "double" or "char", or we can modify those types to get things like "unsigned long long int". We can have "unions" and "structs", which are built out of other types, and we can have pointers to any of them (including pointers to pointers (to pointers...)).

Now let's consider a similar thing in Java, which claims to be an "object oriented" language:

basetype ::= 'byte' | 'short' | 'int' | 'long' | 'float' | 'double' | 'boolean' | 'char'
type ::= <object> | <basetype>

Where anybody can create their own kind of "object", for example strings of text, key/value pairs, Web browsers, customers, etc. In the end though, everything in Java ends up being defined via a few things from "basetype".

If we look at the first Object Oriented language, Smalltalk, we can see why I said Java is "object oriented" in quotes:

object

That's it. EVERYTHING in Smalltalk is an object. If you want a number, that's fine since there are number objects. You want a true/false boolean? That's fine since there are true and false objects. No expressiveness has been lost by throwing away the complicated special-cases of languages like C, and by adding "base types" Java has gained no expressiveness over Smalltalk. In fact, by having more special cases we lose expressiveness. For example if we want to write, in pseudocode, a function for the square of something, we can do so in C like so:

int square(int num) {
return num*num;
}

char square(char num) {
return num*num;
}

float square(float num) {
return num*num;
}

double square(double num) {
return num*num;
}

We would also need to take into account the various modified versions, whilst structs and unions can't be squared in a general way. We're also forgetting here that C would complain about multiple function definitions, so we would have to call each function something different (eg. int square_int(int num)), and the obvious issue that some of these number types might not be able to store the result of the multiplication if it's too big (don't get me started on that bollocks). In Java we get a similar thing, although we're allowed multiple functions with the same name since they take different argument types:

int square(int num) {
return num*num;
}

float square(float num) {
return num*num;
}

byte square(byte num) {
return num*num;
}

long square(long num) {
return num*num;
}

short square(short num) {
return num*num;
}

char square(char num) {
return num*num;
}

boolean square(boolean num) {
return num*num;
}

double square(double num) {
return num*num;
}

Object square(Object num) {
return Object*Object;
}

The last case, of Object, won't work since Java has EVEN MORE special cases to do with operators like *, defining them for some kinds of objects and not others. Now, what would we write for Smalltalk?

[:num | ^ num * num]

That's it. Done. Works for everything (for which multiplication is valid).

The nice thing about using objects in this way is that everything stays symmetric, ie. you can treat everything in the same way. This lack of special cases and artificial distinctions means that it's much easier and more intuitive to make systems which handle everything thrown at them. As long as there's a sane fallback in the case of failure, we can leave this function (that one line) alone FOREVER and be confident that it will still work with everything we give it; we don't need to keep fiddling with it as more types are added to the language.

What's more, now that we've got this working function, we can stick it in a library and use it everywhere. We can do the same for branches, via the methods:

foo isTrue: [something run] isFalse: [somethingelse run]

That works for ANY foo, and the two code blocks given are of course examples. We can do the same for iteration:

foo do: [:x | something run using x]

That will work for ANY foo which is iterable. Everything works in the same way, 40 year old code can work with objects written last week, code written last week can work with objects defined 40 years ago.

If you're adding a feature to a language via extra syntax, ask yourself whether you're allowing the expression of something new which was not previously possible, or whether you're just breaking the symmetry between that feature and the entirety of the rest of the language.

To bring this back to where it started, I'm very interested in the development of Newspeak.

* More specifically formally defined languages and grammars, not broken grammars retrofitted to natural languages via the use of duct tape and insistence that the language's users aren't adhering to the 'standard' which is based around the user's use of it anyway.

Some Reading Material

I thought I'd upload some of my University work, since I'm quite proud of it, so if you want to know about parallel programming, Physics simulations and Nvidia's CUDA then take a read of this http://chriswarbo.webs.com/CUDAProject.pdf

If you're interested in the world of the tiny, and what you can build given some pieces of DNA, take a look here http://chriswarbo.webs.com/DNAEssay.pdf

My thoughts on the new Amiga

I heard a while back that there's a new Amiga being worked on, and it cropped up in my browsing today too. I thought it would be worth espousing my opinions on this.

The new machine is, supposedly:

• Dual-core 1.8GHz PowerISA v2.04+ CPU.
• "Xena" 500MHz XMOS XS1-L1 128 SDS.
• ATI Radeon R700 graphics card.
• 2GB RAM.
• 500GB Hard drive.
• 22x DVD combo drive.
• Customised case, keyboard and mouse.
• 7.1 channel HD audio.
• Ports and connectors:
• 4x DDR2 RAM slots.
• 10x USB 2.0.
• 1x Gigabit Ethernet.
• 2x PCIe x16 slots (1x16 or 2x8).
• 2x PCIe x1 slots.
• 1x Xorro slot.
• 2x PCI legacy slots.
• 2x RS232.
• 4x SATA 2 connectors.
• 1x IDE connector.
• JTAG connector.
• 1x Compact Flash.

Now, straight away I can say that most of this is marketing bollocks because it's commodity stuff that can be picked up from a skip somewhere. What matters is the following:

• Dual-core 1.8GHz PowerISA v2.04+ CPU.
• "Xena" 500MHz XMOS XS1-L1 128 SDS.
• Ports and connectors:
• 1x Xorro slot.
• JTAG connector.

Now, these are what sets this computer apart from others. The processor may well be a Cell, which would be great for programmers but we'll have to wait and see (remember: there are NO games out there that would use this; only intensive, custom-written code would benefit). The JTAG connector is nice for low-level and hardware debugging, whilst the XMOS and 'Xorro' make reprogrammable hardware useful. So what may it be used for?

The idea that one would buy a computer with integrated FPGA for developing embedded FPGA systems is optimistic to say the least. A PCI card with an FPGA is a much better investment, since it's cheaper, can be replaced when newer chips come out and can be put into any computer from the last 15 years (or PCIe if you're really wanting speed, at the sacrifice of capable computers). Development for external devices is thus out, so the existence of this chip is only of use to the machine itself.

Now, what can the machine do, given this chip on board? Well, right away we can say nothing: since the chip is accessible via the Xorro slot, requiring a loopback connector to something like the PCI ports in order to actually use the chip for anything. The requirement to install such a loopback negates a lot of the advantage of building it into the machine (ie. that it's guaranteed to be there and accessible). So what does that leave us with? Well, if you're not a programmer, nothing, since you'll have to wait for others to build stuff for it and that isn't going to happen, so you'll need to get out of your Microsoft/Apple bubble and learn how your computer actually works for a change.

Now, if you are a programmer then you could rewrite the chip to, for example, offload intensive computation. This would, like the (potential) Cell, only be of extremely limited use. For a comparison, just look at the amount of software that uses GPUs to offload intensive tasks: there's hardly any, except for a few graphics apps, and GPUs are everywhere. The big winners from General Purpose GPU programming at the moment are researchers wanting more speed in their similations. The reason for this is that once the code has been written, it is immediately useful. There's no requirement for support software like GUIs to be made, there's no need to create specific data like graphics, 3D models, etc. like there is in games development, there's no need to market or deliver the code to others. There's no need to make it general enough for large numbers of computers. Once it's been written and is working on your GPU, then give it some numbers to crunch and get back the results. Done. Once again I'll state it: if you're not a programmer, this is of no use to you.

So what could we use an FPGA for, really? I would like to see FPGAs become integrated alongside CPUs/GPUs as co-processors, such that often-used programs (eg. Web browsers) can be compiled to the FPGA and run much faster. This would require a paradigm shift in compiler technology which puts it a long way off as yet, but in any case this isn't a good start since, as I said earlier, the FPGA isn't connected to the rest of the machine in a closed loop! When we consider that those experimenting with FPGA compilers, high-level languages, static analysis and such are often releasing their code as Open Source, then we can be rather certain that a Linux box would do much better than an AmigaOS box, and that if Linux is the target then any off-the-shelf/out-of-the-skip box will do, given a PCI FPGA card.

tl;dr: All if does is integrate (badly) existing technology, in a way that won't appeal to developers and doesn't have any point for "consumers" (a word I am defining to mean those too lazy to learn how to read and write).

Diet Python

I've talked about this before, but have been doing some more work on Diet Python (available in my Python Decompiler on gitorious.org).

Diet Python is a sub-set of Python which is just as expressive. The PyPy project, for example, uses a subset of Python called RPython which is restricted to exclude the really dynamic stuff, and Google's Go language does a similar thing. They exist to keep handy things found in Python, eg. the garbage collection, but throw away bits that are hard to implement in machine code.

That's not the goal of Diet Python. In Diet Python we don't really care about readability or programmer-friendliness, and the syntax can be as awkward as we like as long as it's still valid Python. What Diet Python does is throw away the redundant bits of Python that can be replaced with other Python that does exactly the same thing.

As a simple example, a + b does the same thing as a.__add__(b), but if we're making a Python interpreter we have to handle both + and .__add__. Diet Python throws away the +, since it's less general than the function call, so that Diet Python implementations only have to care about .__add__, which they would have to handle anyway since it's a function call and function calls are everywhere in Python. Diet Python has a 'compiler' which translates Python into Diet Python, so that we can write normal Python (eg. a + b) and then strip away the fat to get the __add__ equivalent. This id "Diet Python", but since it's also perfectly valid Python it will still run fine in a standard Python interpreter.

There are two approaches I'm taking with Diet Python. The first is to remain 100% compatible, so that there is no change between the semantics of the Python input and the Diet Python output, and both will run the same in a standard Python interpreter. The other goal is to see just how much of Python we can throw away, without losing any functionality. Some of this relies on incompatibilities with the standard CPython interpreter, but only due to limitations in the interpreter.

For example, in Python we can do conditional branches like this:

if a:

print b

else:

print c

Whilst in Smalltalk the same thing is done with a message send (function call) like:

a ifTrue: [Transcript put b] ifFalse:[Transcript put c]

So, can we throw away Python's keywords and use a Smalltalk-style message-send? Well, this would look something like the following:

a.__if__(lambda:print b, lambda:print c) # Stupid function use, for demonstration only

But this would require a bit of support in the form of:

True.__if__ = lambda first, second: first()

False.__if__ = lambda first, second: second()

Now, this all looks fine and dandy until CPython tells you off for trying to modify the True and False objects, which are written in C without any of Python's dynamic capabilities. To me this is a bug in the implementation, however since the only standard for Python is what the CPython interpreter does, this is actually the expected, valid behaviour of Python :( This is the reason Diet Python has two approaches: one does everything we can, given the inherent limitations of CPython's internal structure, whilst the other sees what we can do with a language if it were 'Python all the way down'.

Given enough of each type of translation, compatible and uncompatible, I hope to able to get Python code down to a bare minimum of syntax. At the moment I believe that at least all operators can be done away with, since the only ones left are bit shifts which I've not bothered translating yet since I've never used them. After that I think every keyword can be thrown away; elif is sugar for else: if:, whilst all of the hard work in if: and else: conditions is actually just working out the truth value of the condition, which it does itself, so we can thus give True and False methods like the above. I'm undecided about for loops at the moment, I may try a map approach or I may convert them to a while using the __iter__ method. while itself may require a translation to Continuation Passing Style which would be interesting, but that would also get rid of try:, except:, finally:, yield, pass, break, continue and return for us. Function and class definition can be achieved with __new__, and if we change the behaviour of globals() and locals() to define mutable return values then we can do away with assignment, imports, numbers, strings and other such things.

Once we've done this, we have a tiny target which Python implementations must handle. Everything else can be implemented by asking Diet Python to translate it away :)

=-=-=-=-=
Powered by Blogilo

What Makes Me A Geek: Reason 0x54F6

I have only ever paid for one album in my life. The rest of my music is freely distributable online. The name of that album is 01011001, which is Y in ASCII.

=-=-=-=-=
Powered by Blogilo