This semester I decided to do something very different from my usual Programming Languages work and decided to do something AI-ish to relax. The class I chose was Biomorphic Computation by Mike Gasser. The empahsis in this course was on algorithms/techniques for generally "intelligent" behaviour that are heavily biased in favor of what is described as "biological plausibility". It was a fun course and Mike Gasser is a great lecturer. One of the things we are required to do for teh course is to work on some sort of a project.

A colleague (Craig Michaud) and I teamed up to do something fun - we decided to explore the idea of multiple sexes. In nature we mostly encouter creatures that reproduce assexually or reproduce by mating. The argument in favor of mating from an evolutionary standpoint is that mating involves mixing of genes from both parents and hence offspring have qualities of both parents. Thereby the the entire state-space of genomes is more effectively explored by mating as opposed to assexual repoduction. Assexual reproduction relies only on freak-mutation to explore the genome-space. In nature however mating always involves two sexes - if the argument in favor of mating is that that 2 parents means better gene mixing, then why don't we have creatures with larger numbers of sexes? Say 3 sexes or 4.. or even larger numbers.

As caveat note that we are not intersted in the nature of gender roles - we are not interested in males and females and such distinctions, we are only interested in looking at the effect on evolution when a species has n-sexes, without any specific gender roles. In other words an individual of this n-sex species can be either the first parent or the second parent or the third parent and such.

To avoid biasing the experiment heavily in favor of lower numbers of sexes we decided to create a system of egg laying and egg fertilisation to facilitate mating. When its time to mate, a critter looks for an egg in its vicinity to fertilise. If its finds one that has not been parented by it previously, it fertlises the egg. If there are not eggs in the vicinity, the critter lays an egg. That's the basic idea. When I was runnign the experiment today after tunign some parameters, I noticed something that I didnt expect.

I had built in an energy scale up factor for egg-hatching. If a new born critter is required to have x-units of energy, the sum of energy lost my the contributing parents need be only k*x, where k is a scale factor between 0 and 1. What this means is that whenever an egg hatches, the total gain of energy in the system is more than the energy lost. This scale up factor was added with the thought that some eggs might be lost and anyway the energy utilisaion of a full grown parent is usually less than that of a new born, so to compensate a scale-up would be nice.

In the above screen shot the critters are the little pac-man like things. Their relative health is indicated by their opacity. The more transparent ones are really weak. The eggs are the little cirlces. The eggs progress from a bluish-violet color to red, when they are ready to hatch.

The unexpected thing was that creatures started to organise themselves into little breeding clusters consisting of several parents each. I have circled these in a screen shot above. What the clusters do is that they simply sit around and lay eggs and fertilise them. By the time a parent is too exhausted and dies, a child is born taking advanatge of the scale up energy factor. Hence the cluster on the whole survives and even grows, even though the individuals die out. Spooky!

'Twas in another lifetime, one of toil and blood
When blackness was a virtue and the road was full of mud
I came in from the wilderness, a creature void of form.
"Come in," she said,
"I'll give you shelter from the storm."

And if I pass this way again, you can rest assured
I'll always do my best for her, on that I give my word
In a world of steel-eyed death, and men who are fighting to be warm.
"Come in," she said,
"I'll give you shelter from the storm."

Not a word was spoke between us, there was little risk involved
Everything up to that point had been left unresolved.
Try imagining a place where it's always safe and warm.
"Come in," she said,
"I'll give you shelter from the storm."

I was burned out from exhaustion, buried in the hail,
Poisoned in the bushes an' blown out on the trail,
Hunted like a crocodile, ravaged in the corn.
"Come in," she said,
"I'll give you shelter from the storm."

Suddenly I turned around and she was standin' there
With silver bracelets on her wrists and flowers in her hair.
She walked up to me so gracefully and took my crown of thorns.
"Come in," she said,
"I'll give you shelter from the storm."

Now there's a wall between us, somethin' there's been lost
I took too much for granted, got my signals crossed.
Just to think that it all began on a long-forgotten morn.
"Come in," she said,
"I'll give you shelter from the storm."

Well, the deputy walks on hard nails and the preacher rides a mount
But nothing really matters much, it's doom alone that counts
And the one-eyed undertaker, he blows a futile horn.
"Come in," she said,
"I'll give you shelter from the storm."

I've heard newborn babies wailin' like a mournin' dove
And old men with broken teeth stranded without love.
Do I understand your question, man, is it hopeless and forlorn?
"Come in," she said,
"I'll give you shelter from the storm."

In a little hilltop village, they gambled for my clothes
I bargained for salvation an' they gave me a lethal dose.
I offered up my innocence and got repaid with scorn.
"Come in," she said,
"I'll give you shelter from the storm."

Well, I'm livin' in a foreign country but I'm bound to cross the line
Beauty walks a razor's edge, someday I'll make it mine.
If I could only turn back the clock to when God and her were born.
"Come in," she said,
"I'll give you shelter from the storm."

Shelter from the Storm
Bob Dylan, 1974

This one of gems that come across mailing lists every now and then:
http://www.haskell.org/mailman/listinfo/haskell

------------

Asked how she had come to choose GHC as the topic for her award-nominated PhD dissertation, freshly graduated doctor of software archeology Simone Tolduso revealed:

"At first, there were a few small curiosities that triggered my interest, like why were darcs patches sent to the cvs-ghc mailinglist, or why did GHC releases traditionally bundle the predecessor of the current Cabal version when the missing libraries depended on its successor?

But then I looked into the repository, with its layers on layers of build systems, source formats, deprecation warnings, directory structure fragments, todo logs, broken builds resulting either from OS-tools advancing and playing havoc with the built-in assumptions of fragile build configurations or from multiple, partially completed, mutually incompatible heart-liver-and-lung transplants supporting the newest language extensions (which of course were all needed to build the compiler branch supporting said features, and whose documentation tended to be spread over user manual, API comments, mailing list threads, research papers, plus half a dozen different Wikis and ticket trackers), supported by often outdated documentation in a never-ending variety of formats, and I knew I had stumbled onto a goldmine.

Not to mention remains of earlier projects (what were fptools, or libraries?), a variety of test and compilation languages (including Haskell, C, Perl, Python, alongside the usual scripting suspects), or the proliferation of sediment layers into user space by the simple, but ingeneous, means of binary incompatibility. In spite of its comparatively small size, the project was beginning to rival the complexities of other Microsoft products of the same period.

In what seems to have been an attempt to push open source ideas to their logical conclusion, you actually had to guess at the right combination of versions for a number of independently evolving toolchains, libraries, OSes, and use those to bootstrap from a consistent snapshot of the compiler, library, and sometimes even tool sources, or nothing works - a situation which was later increasingly exacerbated by the dispersion of the Haskell Cabal replacing coordinated releases. Preliminary mining of the relevant mailinglist and bug tracker archives suggests that binary releases were mainly public data points used to indicate intermediate states of GHC _not_ suitable for specific applications (apart from the obligatory Cabal pre-version lacking the new features needed for installing the extra libraries, other examples include versions of Data.ByteString _not_ based on the famous paper, _not_ supporting essential optimisations, or _not_ supporting API safety fixes). So there seemed to be no way to avoid direct access to the source repositories with their associated build processes and toolchains.

And let us not forget that, unlike the programmers at the time, we are in the fortunate situation of already having complete repositories for the pieces and dependencies involved. Finding matching versions is a non-trivial, but essentially combinatorial exercise, while for them, the process of building GHC would often have involved developing and submitting the patches that make up our repositories of all the pieces of software GHC builds depended on.

We still haven't found the key that enabled the ancients to navigate this labyrinth and to keep their toolchains up to date while still making any progress in their daily work, not to mention recording such progress via darcs (in itself written in Haskell, and not free of troubles). Agent-based simulations of developer communities at arbitrary slices through the repositories show the majority of agents getting stuck in a recursive cycle of installing, debugging, and updating dependency chains without ever reaching a productive state, so we do know that we are missing some crucial information.

Several of my correspondents have come to favour the somewhat controversial theory that the general programmer in those days must have been substantially more intelligent than people are today. And it does make sense, in a way - I mean, if anyone had been the slightest bit bothered by all this complexity, surely someone would have tried to simplify things?

Of course, my work has not all been happy progress: for instance, while there really was an 'evil mangler', the equally persistent rumour that GHC was named after some scottish town has turned out to be a wild goose chase (cf Appendix GC); my colleagues in dirt archeology assure me there was no town called 'glorious'. The 'real' archeologists, as they call themselves, had a field day laughing about my gullability there. Still, there are so many burried treasures in this area - just waiting to be investigated."

Dr Tolduso is currently working on a follow-on project, "Haskell by committee - design and syntax through the ages".

Dept. of Software Archeology, University of New Atlantis
(for immediate release)

Ruby's yield has been traditionally credited to CLU and Icon. I finally found a refrence for CLU's yield statement. The defintion of yield is closely related to their definition of iterator. This is from the CLU manual available at http://www.pmg.lcs.mit.edu/CLU.html

A.7.11 Yield Statement

Yield statements may occur only in the body of an iterator. The form of a yield statement is

yield [ ( expression , ... ) ]

It has the effect of suspending operation of the iterator and returning con­trol to the invoking for statement. The values obtained by evaluating the expressions (from left to right) are passed to the for statement to be as­ signed to the corresponding list of identifiers. The type of each expression must be included in the corresponding yield type of the iterator. After the body of the for loop has been executed, execution of the iterator is resumed at the statement following the yield statement.

A.8.2 Iterators

An iterator computes a sequence of items, one at a time, where each item is a group of zero or more objects. It has the form

idn = iter [ parms ] args [ yields ] [ signals ] [ where ] 
         routine body
         end idn

where

yields ::= yields ( type spec , ... )

The idn following the end of the iterator must be the same as the idn naming the iterator. In this section we discuss nonparameterized iterators, in which the parms and where clauses are missing. Parameterized modules are discussed in section A.8.4; own variables are discussed in section A.8.5. The form of an iterator is very similar to the form of a procedure. There are only two differences:

1. An iterator has a yields clause in its heading in place of the returns clause of a procedure. The yields clause specifies the number, order, and types of objects yielded each time the iterator produces the next item in the sequence. If zero objects are yielded, the yields clause is omitted.

2. Within the iterator body, the yield statement is used to present the caller with the next item in the sequence. An iterator terminates in the same manner as a procedure, but it may not return any results. An iterator is an object of some iterator type. For a nonparameterized iterator, this type is derived from the iterator heading by removing the iterator name, rewriting the formal argument declarations with one idn per decl, deleting the formal argument names, and, finally, replacing iter by itertype.

An iterator can be invoked only by a for statement. The execution of iterators is described in section A.7.6.

A.7.6 For Statement

The only way an iterator can be invoked is by use of a for statement. The iterator produces a sequence of items (where an item is a group of zero or more objects) one item at a time; the body of the for statement is executed for each item in the sequence. The for statement has the form

for [ idn , ... ] in invocation do body end

or

for [ decl , ... ] in invocation do body end

The invocation must be an iterator invocation. The idn form uses previ­ously declared variables to serve as the loop variables, while the decl form introduces new variables, local to the for statement, for this purpose. In either case, the type of each variable must include the corresponding yield type of the invoked iterator. Execution of the for statement proceeds as follows. First the iterator is invoked, and it either yields an item or terminates. If the iterator yields an item, its execution is temporarily suspended, the objects in the item are assigned to the loop variables, and the body of the for statement is executed. The next cycle of the loop is begun by resuming execution of the iterator from its point of suspension. Whenever the iterator terminates, the entire for statement terminates. If the for statement terminates, this also terminates the iterator.

Today I was talking to Kent Dybvig and Kent mentioned that the Chez Scheme user guide is now available in hardcopy form from www.lulu.com. What is lulu.com? It is a service through which you can publish your own books without going to a conventional publishing house. You get to format your book and Lulu gives you a bunch of print options wherein you decide paper size, hardbound/paperback and several other things. Authors can choose the cost of their book - there is a certain minimum that Lulu charges as the printing cost. Lulu charges a percentage of the cost beyond that mimimum amount as their cut - the authors get the rest. Authors can also request that their book be sold via Amazon and such. Essentially you get to publish real books without the overhead of a publishing company.

People wishing to buy a copy of your book can buy one online from lulu.com (much like you would buy a book from Amazon). When you buy a copy, the copy is actually printed on demand (much like Dell manufacturing your computer when you order it). Much like ordering from Dell, there is a minimum time period in which your copy is printed and shipped to you.

I was pretty zapped by this idea. This is so much in the spirit of the internet age - a do-it-your-own low-overhead publishing capability. Of course, a coventional publishing house offers many other services such as marketing/advertising machinery and such - but osmetimes you dont need these. The uderlying do-it-your-own spirit is really neat - there could be similar services for music (lulu already does some music) - what would happen to the big record labels then? It would be an interesting and different world when services like this become pervasive. People could sell advertising services in this way (much the way Google does with ads today) and such.

Finally, if you are (by any chance) interested in a copy of the Chez Scheme User Guide, you can find it here.

Wikipedia

Tehelka Story

I have been confused by something for a while and maybe someone can give me a pointer.

I need to release several locks (or critical sections) and sleep on several condition variables atomically. The windows API SleepConditionVariableSRW lets me release one lock and sleep-on one condition variable  atomically. I dont see how I can generalise this.

Windows allows waiting for multiple objects for wakeup signals via WaitForMultipleObjects, however I dont see how I can safely realease several locks and call this API without risking missed wakeups to my threads.

Any solutions?

What might be ideal is a way to track wakeups before the thread goes to sleep. So the thread can register for wakeups on a set of variables, do some work and then go to sleep. If a wakeup had come in the meanwhile, the sleep operation would be a no-op and things would be fine.

Does something like this exist?

Here are some relevant MSDN pages:

http://msdn2.microsoft.com/en-us/library/ms686360.aspx

Here is a tool that can let you schedule a process to run on one of more processors of your multiprocessor machine as specified by you. You can spawn the process you want by starting the exe at the command line with procaff and a switch that indicates the processors that it can run on.

This is very handy is you want to do some customised tinkering on a multiprocessor machine. Also if you thing a process is a CPU hog and you have a mutlicore machine, you can restrict its behaviour to a specific set of CPUs at start time. Rather handy.

ProcAff

http://www.stefan-kuhr.de/procaff/main.php3

I had to do some intense amount of searching at one point to find something like this. Hopefully a couple of links will make it easier for other people.