Monkeypatched

A New Dynamic Dispatch Algorithm?

2009-07-16T02:35:00.000-07:00

I'm playing around a little with dynamic dispatch algorithms in a dynamically typed language.

An idea I had was for each function to create a small dispatch table, where each function slot also was a tree node.


typedef struct Slot
{
   SEL selector;
   IMP function;
   struct Slot* left;
   struct Slot* right;
} Slot;

With the class looking like this:


typedef struct Class
{
   // ... Other stuff
   Slot slot[FUNCTION_SLOTS];
   // ... More stuff
} Class;

For dispatch we can now do:


Slot* slotPtr = object->class->slot + selector & SEL_HASH;
do
{
   if (slotPtr->selector == selector) return slotPtr->function(object, selector);
   slotPtr = (slotPtr->selector > selector) ? slotPtr->left : slotPtr->right;
} while (slotPtr);
// ... execute MethodNotFound:

This means a worst case O(log(N)) lookup where N is the maximum number of methods hashed to the same slot.

My tests seem to indicate that it is surprisingly fast, at least when inlining the dispatch method:


Best case:                   207 million sends/s.
Worst case 6<N<11:           138 million sends/s
Direct dispatch table call:  234 million sends/s.

I'm not sure how reliable these benchmarks are, but it would be interesting to compare these results to the algorithm in the Objective-C runtime.

The downside of course is that all classes need to keep all methods they respond to in the dispatch table, as opposed to only the methods they override.

[Edit:]
Here are results of microbenchmarks on the Obj-C runtime (smaller is better):


Virtual call            1.00
Best case inlined call  1.13
Best case non-inlined   1.77
Best case lookup        1.82
Worst case inlined call 1.70
Worst case non-inlined  2.30
Worst case lookup       2.44
Objective-C OS X 10.5   1.77

Note that the Objective-C result gives the best case for the runtime.

How should the syntax look in a c-like language with closures?

2009-05-15T23:17:00.000-07:00

I'm trying to see if I can create a nice syntax for a language that looks as close to C/C++/Java as possible while allowing syntax-like constructs to be defined by the programmer.

It turns out it's not as easy as it sounds.

The problem lies in defining multi-part function. We start out easy: how do you define the following code as functions?

if (b) 
{
   doWork();
}
else
{
   doSomeOtherWork();
}

A stab at this particular syntax-turned-function might look like this:

void if_new(boolean b, &statement) else(&elsestatement)
{
   if (b)
   {
      statement();
      return;
   }
   elsestatement();
}

That looks mighty fine (let's assume the compiler knows that our syntax with the "&statement" means that it should take a block and turn it into a function), but what about the compiler?

if_new(b) { doSomething(); }

else { doSomethingElse(); }

fooFun() { foo(); }

barFun() { bar(); }

In this case, how does the compiler know that the first line is a multi-part function and the second is not? I.e. how does it know that I want the function if_new(b)else(), but not fooFun()barFun()?

One solution would be to impose a terminating ";" tax on every {}, like this:

if_new(b) { doSomething(); }

else { doSomethingElse(); };

fooFun() { foo(); };

barFun() { bar(); };

Another solution would be to make a much looser compilation the first time, and then actually treat these functions as formal syntax extensions, so that when the compiler sees "if_new" it would recognize that an "else" that follows it should be part of the function signature.

This sounds vaguely ok until you realize that you probably would like to be able to have multi-part object methods as well.

An alternative, though syntax-altering, would be to explicitly add a linking character, something like this:

if_new(b) 
{ 
   doSomething(); 
} 
:else 
{ 
   doSomethingElse(); 
}

Unfortunately this means that all other multi-part syntax would have to follow the same rules, e.g.:

if (x)
{
   ...
}
:else
{
   ...
}

do
{
   ...
}
:while(x);

try
{
   ...
}
:catch (Exception e)
{
   ...
}
:finally
{
   ...
}

":" was the least intrusive character I could find, but if anyone else has a better suggestion I'd be happy to hear it.

What got me thinking if this could be done was a blog entry by Neal Gafter on multi-part method names in Java, and a follow-up by Stefan Schulz.

(Ruby) Closures - jack of all trades, master of none.

2009-02-19T05:38:00.001-08:00

Ruby is based around closures. Closures are both used to represent blocks of code, as well as anonymous functions:

As an anonymous function:

[1, 2, 3, 4].select { |i| i % 2 == 0 }

# => returns [2, 4]

As a block of code:

10.times do

puts "Hello World"

end

The problem is that they are not quite the same, and don't solve quite the same problem. In fact, I would go so far as to say that closures solve both problems... poorly.

As an anonymous function, closures grab a whole lot more context than you usually would like, and especially in ruby where you each closure by necessity always retain the complete context.

Its double nature as block and anonymous function means that exiting a closure occasionally works a bit different that expected, "return" alternately exits the current method or just returns the closure with that value. In some cases one can use "break" with an argument (a bit depending on what version of ruby you're using):

def test1

[1, 2].collect(&Proc.new{ |i| return i })

end

p test1 # => 1

def test2

[1, 2].collect(&lambda{ |i| return i })

end

p test2 # => 1 ([1, 2] in 1.9)

def test3

[1, 2].collect { |i| return i }

end

p test3 # => 1

def test4

[1, 2].collect(&Proc.new{ |i| break i })

end

p test4 # Illegal

def test5

[1, 2].collect(&lambda{ |i| break i })

end

p test5 # [1,2] (Illegal in 1.8)

def test6

[1, 2].collect { |i| break i }

end

p test6 # => 1

I am tempted to suggest that instead of lumping these two different usages into a single concept (the closure), we would be better served by separating these into anonymous functions and blocks.

A block would inherit context but an anonymous function would not (it would instead resolve variable values during creation).

Of course, the following could would be slightly different from the closure version:

a = 1

f = function() { return a; }

a = 2

p f.call() # => 1 (2 if this would have been a closure)

For our blocks this would allow us to unroll method calls, and in general optimize methods taking blocks as arguments by treating them as if the methods were macros.

Blocks and anonymous functions might not cover everything you can do with a closure, but how often do you really want a function that retains the whole context it was created in?

New version of xmlwise out now.

2008-12-27T04:32:00.000-08:00

My tiny java library for looking through xml has been updated. The only new addition is a small addition to allow simple reading of plist files.

Read The Code

2008-11-16T05:40:00.000-08:00

I've been thinking a bit about code reading lately. When code reading usually comes up in a discussion, it is usually about how to document the code and how much comments to add.

But I'm thinking about the skill of pure code reading - the ability to read raw source code and figure out how it works.

Up until recently, I wasn't really aware of its importance. To be more exact, I assumed everyone's code reading skill more or less followed the overall amount of programming experience.

It turns out it's not quite like that. Instead I've come to understand that code reading is a skill quite separate from the "general programming" skill.

I talked to one colleague about reading code, and he told me his way through complex code was not to rush headlong into the code and read it until he understood it (my preferred method), but instead he would look to divide and refactor the code into separate pieces with clear interfaces until each piece could be understood on its own.

While I think that this is a good approach to clear up complex code, it will still be hard to do the best possible refactorings unless you really understand the inner workings of the code you trying to clean.

This brings to mind a story that was related to me by another of my colleagues:

This colleague had been hired as a consultant to finish some software project. Working his way through the code he was struck by how strange the programmer who originally worked on the project had designed the program.

Believing the previous programmer had simply made some design mistakes, he went ahead and threw away the weird parts of the code and started to rewrite them.

His newly written code started out pretty clean, but as he began work on the details he noticed the need for amendments to his original design.

As he implemented more of the details and corrected his design to accomodate them, he began to realize that his design grew more and more to resemble the original "strange" design he had thrown out.

I think this illustrates how hard it is to know what parts of the code are needlessly complex and can be safely thrown away, and what parts are complex because the code is handling some very complex details.

I suspect that good code reading skills always will be an edge, and in some cases even an essential skill.

So what can we do to get better?

There are a few ways I know of that will teach code reading:

When reading a programming example, always try to run the whole programming code in your head to figure out what it does - never use code you don't understand.
Fix bugs in other people's code.
Translate code from one language into another.

I haven't read it myself, but I suspect Diomidis Spinellis's Code Reading also has some good ideas, and Joel Spolsky has an interesting blog entry that suggested a form "pair-reading" to get through truly complex code.

But most important is, as always, the desire to improve.

Good docs

2008-11-14T07:50:00.001-08:00

Good source code documentation is valuable because trying to document your code well tells you how (re)usable your code is:

- If it's hard to explain (i.e. hard to write clear documentation) then it is hard to understand.

- If it is hard to understand it is hard to use (correctly).

- If it is hard to use, then others (and probably you yourself as well) are most likely to write something new next time rather than using or bug-fixing your code.

Busy busy

2008-10-26T01:24:00.000-07:00

Not much written in a while, but that is mostly because I've been busy with different projects. I added a list to this blog with the tiny open source projects I'm working/have been working on.

Naga is my wrapper library around Java NIO that implements the surprisingly complex amount of boiler-plate code you usually need to use NIO for socket client-server communication.

Xmlwise is even more modest. Basically it is a few Java classes that extract data from an already parsed XML document, making the data easy to access by moving it into standard structures (HashMaps and LinkedLists). These classes have made it a delight for me to work with XML documents, and hopefully they'll be of use to others as well.

There are some other libs in progress as well.

The sad sad state of automatic docs

2008-10-10T01:10:00.000-07:00

At work I do server programming in Java and after a while I guess you start to get erronous idea that all automatic docs are like javadoc or better.

Oh, so rdoc (Ruby) sucks like the end of the world, and ri is a joke, but those are just exceptions - right?

...or so I thought until I tried to look at some Doxygen documentation for LLVM... It made me want to claw my eyes out to make the horrible thing go away.

I mean WHAT IS WRONG WITH THE WORLD people!? Look, when old-timers man and javadoc still is the cutting edge, you know you're in a really sad place.

I thought the Objective-C documentation was pretty bad, but it's like a shining beacon of light in comparison.

The bat-crazy thing is that people write stuff like "I love Doxygen, it is teh bestest", like there is even a remote possibly it could be true.

I read one exchange where people argued that the reason Doxygen docs sucked - everywhere - was because people didn't configure it right and didn't stick with the conventions...

I hate to break it to you people but it is a f*****g tool, and a tool is supposed to help, not make you spend hours in configuration and figuring out best practices. So if your so-called tool isn't helpful, you're way better off writing the docs by hand - and I don't care if the tool creates some fancy but utterly unusable class diagrams, it is still worthless.

Javadoc and man already shows exactly what any documentation at least have to live up to.

It is really easy, here is a check-list on what an auto-doc tool needs.

1. Great formatting.

Not "acceptable", not "good". It has to be great. You already had to break your coding flow to look something up, so the formatting needs to be crisp sharp to guide you to exactly the information you need as fast as possible so you can get back as fast as possible.

2. Zero configuration.

Configurable tools suck, yes they suck. Because most of the time "configurability" is nothing more than an excuse for the tool coder not to figure out good defaults for you.

Yes it is worthwhile to have some configurable parameters, but it should be the exception rather than the rule. If things are configurable, then doc A and doc B will look different, and a programmer used to look at docs generated with style A will be confused by style B and vice-versa. In documentation, consistency is king.

Obviously this has to be language specific, but within a language the docs should look the same. If you are making a tool and plan to make the user to configure everything, then you are a lazy bastard.

3. Well thought out and clear doc conventions

Your tool should make it easy for a programmer to know what the can make the auto-doc tool improve the documentation.
Start looking at Javadoc - it is not great but it works. We have the basic @param, @throws and @return. It should be easy to expand that and adapt specific conventions for each language.

4. Remember the needs of the programmer.

Find the common use cases and optimize for them.

When programming Java, in the majority of cases I look up docs for one of three reasons:

  1. To find the correct method to call on a class.
  2. To understand the workings of a method of a class.
  3. To find the correct class to use in a library/framework.

Javadoc is fairly optimized to for this: It's easy to scroll through the methods. If you click a method then the description gives you the basic arguments, and there is a doc convention to describe the most important information (parameters, return value, when exceptions are thrown).
It is also easy to find a class due to the package structuring and the quick links to implementing classes/subclasses.

Automatic documentation is a solved problem. Too bad no-one seems to be looking at the solutions.

I'm going to finish with a quote from the Qt-list:

"It's [blaming Doxygen for the bad documentation], or blame almost every single user of the tool. At this point, I'd prefer to blame the tool."

The old static vs dynamic typing...

2008-10-04T10:57:00.000-07:00

Instead of rehashing the old arguments, I'd like to point out some observations I've made.

The best GUI builder I've encountered is Interface Builder on Mac OS X and it works because Objective-C is a dynamically typed language. It is very to use and yet incredibly powerful.

What you notice from the beginning, is that you are building the GUI by instantiating flexible objects, instead of creating thousands of subclasses like Java would make you do.

IB is one of the few development tools that actually manage to deliver on the concept of object oriented programming as assembly of reusable building blocks.

What makes this possible is the way dynamic typing naturally decouples the system. It is almost like magic.

Another kind of magic made possible by dynamic typing is dynamic message forwarding.

Here is an example, code is in an imagined dynamically typed Java.

Here is a tree class:

Class Tree

{

Map m_values;

public Tree()

{

m_values = new HashMap();

}

public Object methodMissing(Method method,

Object... args)

{

if (args.length == 0)

{

return m_values.get(method.getName());

}

if (args.length == 1

&& isSetterMethod(method.getName()))

{

set(getVariableToSet(method.getName()), args[0]);

}

public Object set(String value, Object object)

{

m_values.put(value, object);

}

public Object addBranch(String name)

{

m_values.put(name, new Tree());

}

// return true if the string is a typical

// setter, e.g. "setSomeVariable"

public boolean isSetterMethod(String) { ... }

// return variable name from a setter, e.g.

// "setSomeVariable" returns "someVariable"

public boolean getVariableToSet(String) { ... }

}

We can use it this way:

Tree registry = new Tree();

t.addBranch("settings");

t.settings().setTimeout(100L);

t.settings().setHost("www.google.com");

System.out.println(t.settings().timeout());

// prints "100"

System.out.println(t.settings().host());

// prints "www.google.com"

Although this kind of coding can be misused, it is immensely powerful when it comes to avoiding boilerplate coding. In fact, the whole concept of automatic code generation used by many Java frameworks becomes completely unnecessary in dynamically typed languages.

Without dynamic typing, we deny ourselves a range of tools that does not fit in a statically typed universe. If all you've used is statically typed languages it is hard to understand the kind of freedom dynamic typing really give you, and therefore it's also hard to understand what you are sacrificing.

That said, a statically typed language has the advantage of clarity of intent which can be a substantial win in certain situations.

This is why I think that the next big development language ought to be dynamically typed but with optional static typing: the best of both worlds.

Heard about Newspeak

2008-09-21T12:12:00.000-07:00

Newspeak hit the blogosphere recently, popping up on Reddit.

I obviously had to have a look, and it could be briefly described as an OO language with a (currently) smalltalk-ish syntax.

This is not Smalltalk however, despite borrowed syntax and Smalltalk-like dynamic typing. Instead it tries to be a new language that incorporates many of the newer ideas in language design.

One of the people working on Newspeak is Gilad Bracha. Aside from working on Strongtalk (a fast Smalltalk implementation with optional typing) he's known for writing a lot of papers on various aspects on OO as well as having had a hand in how generics was added to Java.

Looking through the papers is like looking through the feature list of Newspeak: pluggable types, the concept of mirrors for reflection, mixins for Strongtalk... they're all there.

I could write something about the language in general, but it's easier just to direct you to the website for the overview.

Anyway, I was reading through the spec today and found a bunch of small but interesting things about the language. For instance, Newspeak will be implementing fixed decimal representations, which means that doing something like 1.0000000000001 - 1.0 will actually return 0.0000000000001 instead of some unexpected number due to an imprecise floating point representation. It will use Actor model concurrency (very nice), it's going to have true immutable objects and of course the mirrors and pluggable types are there too.

Everything boiling down to a (potentially) very interesting language.

More multiple dispatch

2008-09-08T08:12:00.001-07:00

I've been looking a bit more at multiple dispatch (multimethods).

The neat thing is that you can view multiple dispatch as sort of a superset of dynamic typing.

For example, if I define (I'm going to use Java-like syntax here) the free function:

void open(Door this, Key key)

{

...

}

then this is equivalent to creating the method

class Door

{

void open(Key key)

{

....

}

So something like door.open(myKey) could be considered simply syntactic sugar for open(door, myKey).

Unlike in Java, this would compile:

Door door = new Door();

Object hiddenDoor = door;

hiddenDoor.open(myKey);

...since the actual check is always done during runtime.

If we try to pass off something as a door, this will fail during runtime as well:

Dog dog = new Dog();

dog.open(myKey); // => Runtime Error!

Which is essentially dynamic typing.

What is so damn cool about multiple dispatch, is that this far from all you can do with it.

In an dynamically typed language like Ruby, your method would look like this:

class Door

def open(key)

...

end

But what happens if we do something like door.open(tomato)? Well there are two ways out: fail-fast or fail-at-some-other-time. Fail-fast would mean some check on the incoming object to make sure that it has the required key-like properties, fail-later would be to let the "key" fail when - at some later time - it is used under the assumption that it is a key.

With typed multiple dispatch we can make sure that it is a key (like in a statically typed language), while retaining a lot of flexibility.

However, there is one issue. What if Key is a class, and you want to pass in a LockPick that doesn't inherit from Key?

Basically what you want to do is:

LockPick pick = new LockPick(key);

door.open(pick);

The standard way to solve this in normal Java would be to replace the Key with an interface and let both LockPick and Key implement it.

So we replace the function with:

void open(Door this, KeyInterface keyInterface)

{

...

}

Now as long as Key and LockPick both implement KeyInterface we're ok.

What happens in Java is that KeyInterface actually allows us to have something akin to multiple inheritance while retaining most of the simplicity of single inheritance.

With single inheritance like Java, we cannot create

class TrollWarrior extends Warrior, Troll

{

...

}

Instead we have to select one to be an interface, like this:

class TrollWarrior extends Warrior implements Troll

{

...

}

Something funny happens if we have multiple-dispatch though:

If we can define:

void exposeToSunlight(Object self) {}

void exposeToSunlight(Troll self)

{

self.turnToStone();

}

Then obviously humanWarrior.exposeToSunlight()is going to be different than trollWarrior.exposeToSunlight()! So what has happened? Well, it turns out that once we add multiple dispatch, interfaces basically turn into classes.

The downside is that multiple inheritance can be a bit tricky, especially when functions overlap.

Say both classes A and B implement their special version of toString(), what version should the class C, inheriting from A and B use?

It turns out that creating a precedence rule isn't trivial. Fortunately, the problem has pretty much been solved already, and the answer is called C3 linearization.

Basically this is an algorithm that takes an inheritance tree and flattens it in a way that ensures consistency in three ways (hence the 3).

Here is a pseudo Java example:

class A

{

public String hello() { return "A"; }

}

class B

{

public String hello() { return "B"; }

}

class C extends B

{

public String hello() { return "C"; }

}

class D extends A, B

{}

class E extends A, C

{}

If we suppose that new D().hello() returns "A", what does new E().hello() return?

The surprising result is that many implementations of multiple dispatch in different languages would return "C"! The C3 algorithm however, does the right thing and gives us the "A" we would expect.

The C3 linearization algorithm was first created for Dylan, but has eventually worked itself into other languages as default.

I couldn't find any implementation of the algorithm in other languages than Dylan and Scheme, but the page on C3 for Python 2.3 had a very clear description of the algorithm.

Here's my Ruby version of it (the Java version was about 5 times as long):

def c3(own_class, list_of_linearizations)

linearization = [own_class]

while !list_of_linearizations.empty? do

next_value = list_of_linearizations.find do |c|

list_of_linearizations.all? do |d|

!d[1..-1].member?(c[0])

end

raise "Illegal inheritance" unless next_value

head = next_value[0]

linearization <<>

list_of_linearizations.each { |c| c.delete(head) }

list_of_linearizations.reject! { |c| c.empty? }

end

linearization

end

It might look a bit tricky, but it's not so bad once you wrap your head around it.

Multiple dispatch keeps looking better every time I look at it, which makes me all the more embarrassed that I never looked at CLOS (CLOS bases its OO system on multiple dispatch).

I was really surprised and impressed by the fact that support for dynamic typing and multiple inheritance arose spontaneously from just following consequences of basic multiple dispatch.

Java multi threaded blocking IO wins over NIO?!

2008-09-03T12:13:00.000-07:00

I just read through a blog post titled "Writing Java Multithreaded Servers - What's old is new". Basically they did some serious benchmarking on java with NIO vs threads with blocking IO and found that the latter was faster and scaled well too.

Before you run into the streets shouting "Lies! Bloody lies all of it!", I think I should mention that this was on the 2.6 Linux kernel. If you have played around with threads on earlier Linux kernels, you know that threads on those systems ate resources like crazy. Apparently the new threading implementation changed all that. Interestingly, Windows XP also show significantly better performance with multiple threads rather than NIO.

Talk about the world turning upside down.

That said, I still am not 100% convinced that the last word has been said. Most of the examples were of IO where data flows in one direction at a time. This is where multi-threaded blocking IO rules. But what if you have something like say an online poker server, where you have continuous input and output? Suddenly one thread isn't good enough, you need at least one for input and one for output. In addition, any timeouts require yet another thread, since it has to be unaffected by the blocking IO.

So say you have your java process with 15k connections. That's a whopping 30k threads just to handle the IO. That is not counting the threads for the poker tables or db access.

What's more, both input and output threads become little more than worker threads to receive and send data, since the actual gameplay will necessarily run on another thread. This means that all the connection input thread will do is really to read input and dispatch it to some poker table thread. A message being another word for "event".

Which means we're back to event handling just like in the NIO case, and we just gained 30k threads mostly doing nothing.

What I'm trying to say is that I don't think the results are as conclusive as they may seem. Yes, there are many applications where threads with blocking IO makes things incredibly easy to code, and that's where the benchmarks are applicable, but then there are other situations where they quite simply doesn't make sense, like in the poker server example, where each connection would require more threads and those threads in turn would need to communicate with other threads a lot more.

Multiple Dispatch can be neat

2008-08-31T01:35:00.000-07:00

I was looking at this paper regarding multiple dispatch.

Coming from a java point of view, I still remember the disappointment the first time I realized that Java didn't have multiple dispatch. You know, the first time you realize that:

public static void a(Object o)

{

System.out.print("1");

}

public static void a(Number n)

{

System.out.print("2");

}

public static void main(String... args)

{

Object o = new Integer(3);

a(o);

a((Number) o);

}

...would write "12" instead of "22". (Of course, in functional languages this is taken even further with pattern matching)

I found more examples when looking at Slate, a Smalltalk-ish langage with this type of multiple dispatch (apparently development on the language is pretty much abandoned now though).

The advantages with multiple dispatch is discussed in the paper I linked to, but as a quick recap it allows you to push variant behaviour into different methods instead of using something like "instance of" or its variants.

Sure, it is possible to push back behaviour to the target object, but it is not always possible. Here is a standard "equals" method in java:

public boolean equals(Object otherKey)

{

if (this == otherKey)

{

return true;

}

if (otherKey instanceof Key)

{

Key key = (Key) otherKey;

return m_id == key.getId();

}

return false;

}

If java had multiple dispatch we could simplify this to:

public boolean equals(Key otherKey)

{

return m_id == key.getId();

}

public boolean equals(Object otherObject)

{

return false;

}

Which one is better should be pretty obvious.

There has been work on multiple dispatch for C++ that almost made it to C++0x, but apparently it came a bit too late to be included. CLOS and Dylan are the two languages usually mentioned in regards to multiple dispatch, but there is also support for it in Nice, the previously mentioned Slate, Cecil, Perl 6 and Groovy.

My Own Language Wish List

2008-08-26T08:43:00.000-07:00

I am working on a programming language idea, it's just for fun and nothing will probably come out of it, but the research itself is proving incredibly rewarding.

Here is my wish list:

OO with C-like syntax
Both implicitly and explicitly defined protocols (interfaces)
Mixins for shared implementation.
Categories (add methods but not ivars to existing classes)
Dynamically typed with optional static typing with both static and runtime checks.
Unambiguous grammar (Compare with Ruby where you can shadow methods with local variables and vice-versa)
All statements return a value ("self" is default)
Compiles to C
Should work seamlessly with C-code (may include .h files, call C directly without implicit type conversion)
Module system similar to that of D.
Real hygienic macros.
Coroutines
Closures
Invariants
First class functions.
Metaprogramming (including directly working with the current context, replacing Closure bindings etc)
Arrows

I'm also considering no direct thread access, but to provide other ways to easily parallelize things across multiple threads.

Basically I think that raw multithreading usually is more of a problem than a solution.

Asynchronous communication should be built in and be the default. I am looking at Io as a good example here.

The Compiler Puzzle

2008-08-24T00:26:00.001-07:00

I've been playing with the idea to create a programming language, mostly for fun - to learn something about writing programming languages.

Now I almost regret it, it's like an addiction, reading about different languages, compile-time optimization, fast message dispatch, garbage collection algorithms and the list goes on. It's really a fascinating subject, as addictive as any puzzler game.

This is, by the way, why I even started to look at D in depth (unfortunately for me, D 2.0 has no mac compiler so I can't really play around with it), and today I stumbled over Factor while looking for ways to optimize simple calls like +, -, *, % and /.

One problem in dynamically typed languages without primitives is that a simple a + 1 is as expensive as the call a.doSomething(1).

So the code that looks like this in C:

int someFunction(int a, int b, int c)

{

a = 10 * b + c;

b = a % 37;

c += (a + c) % 3;

return a + b + c;

}

would in a dynamically typed language with a naive compiler translate to:

someFunction(a, b, c)

{

a = b.mult(10).add(c);

b = a.mod(37);

c = c.add(a.add(c).mod(3));

return a.add(b).add(c);

}

If this was C++ and the methods non-virtual, then it would be a simple thing for the compiler to inline them, with dynamic dispatch on the other hand, it's not that simple, and when you have dynamic typing the situation is even worse, because at compile time there is no way to even know what type a, b and c will have. It gets worse because dynamic message passing is a lot slower than than normal dynamic dispatch in statically typed languages.

One of the ways to alleviate this problem somewhat is by using type inference, which is one thing that Factor does.

It's like a game... how do you make the computer work as fast when you feed it objects it has to figure how to use, as when it is given clear instructions? If "as fast" is impossible, then how do you get it really, really close? Oh, it's a very nice puzzler indeed.

I like Ruby - but big projects suck.

2008-08-23T05:52:00.000-07:00

I like Ruby, I like it a lot, but I keep running into some issues.

But first off let me say that for small programs, Ruby is absolutely wonderful. It is sad to see people struggle to write x10 or x100 the amount of code trying to do the same thing in Java because they don't know anything easier to use.

But then there are the huge projects. The ones with 50.000+ lines of code if written in Java and a fraction of that if written in Ruby. That is where the problems show up. Because even at 50.000 lines of code, a project is quite manageable in Java with a good IDE. With Ruby, 5000 is frickin bad.

I think some of the reason is because Ruby doesn't provide an easy way to maintain a project structure. Where a hierarchy is almost required in Java, it is actually outright hard to get it to work in Ruby. I don't particularly enjoy adding a header to every ruby file just to make sure it both can run stand-alone and compile properly with the rest of the project. Unit tests need even more path-magic to work.

The problem is compounded by the fact that you really would like to have well encapsulated libraries of code within a single project. In Ruby you sometimes write fiendishly clever and hard-to-understand code to simplify development in the rest of the code. Normally you'd then hide that implementation either as a separate jar/library/module, or at least in some (in Java terms) sub-package to insulate you from the implementation.

Unfortunately there are few ways to achieve that aside from building a full-fledged gem. And since there are no interfaces/protocols in Ruby, nor is it immediately clear from a class definition what public functions and methods your code actually provides, you probably are going try to read that code many times again, trying to understand exactly what it did, losing something like half an hour of productive work every time.

This problem could have been made smaller if rdoc was better, but when comparing it to say Javadoc, it is laughingly bad. Add to this the fact that rdoc is really lacking everywhere, both for ruby core classes and as for ruby gems, you should count yourself lucky if you find one with rdocs. So... again you are forced to read the actual code to understand how to properly use it.

Speaking of gems... this is yet another sad point compared to other languages. Jars and classpaths with Java suck, but at least you have your dependencies bundled up in a few files, whereas with gems you have them installed somewhere on your computer. This might be convenient for development, but not as good if you are writing something as a stand-alone program. Even c headers bundled with a library is a lot easier to get the hang of.

When I look at Python, which seems to have a sane module system and even docs bundled with the classes. I can't help but to wonder why Ruby hasn't borrowed these things already.

Could it really be that most people still are only using Ruby for small projects?

D' nice kitchen sink

2008-08-19T02:46:00.000-07:00

I have been looking a bit at D, without playing around with it any. That, of course, means I know nothing about the language whatsoever. It looks like it has pretty much everything in it.

C-style programming - check, type inferrence - check, contracts - check, modules - check, classes - check ...and so on.

(Which actually makes me pretty reluctant to use it for anything. Kitchen-sink programming languages always worry me for some reason.)

Anyway, the really cool thing about it is all those articles that keep popping up where people extend it to do neat things.

I only have two articles on the top of my head:
www.digitalmars.com/d/2.0/accu-functional.pdf
bartoszmilewski.wordpress.com/2008/08/16/thin-lock-implementation/

...but there are a lot more of them, and they're not just interesting from a D-programmer perspective, but the articles actually feel relevant to other imperative languages as well.

Very nice indeed.

Starting a blog

2008-08-19T00:13:00.000-07:00

So, after getting addicted to reading programmer blogs, I'm going to try my hand at keeping one of my own. We'll see how it works out.