Nuerd

OpenGL ES 2.0 Gotchas

2011-12-07T03:38:00.001-08:00

Perhaps I can save somebody some time by sharing what I learned on my first OpenGL ES 2.0 program:

1) The coordinate system is probably left handed!

This may seem hard to believe bearing the entire history of OpenGL in mind, but it's certainly the case on my HTC Android phone and I've seen postings from confused iPhone programmers which seem to indicate the same. The ES 2.0 spec is agnostic about handedness, which seems incredibly dumb and destructive until you imagine the scene of twenty people sitting around a table all refusing to go home until they get their own way. When your eyelids are drooping, it doesn't matter how stupid the compromise is.

You can check the handedness by drawing a tetrahedral triangle strip with a peak towards +z, making e.g. blue proportional to z, and rendering it with no transformations at all. If you see blue it's right handed, if not, left. I think we can rely on +y being towards the top of the screen.

If you're accustomed to right handed systems, and you normally use your right hand to figure out the axes and rotations by pointing three fingers in the air at right angles or making a fist with your thumb sticking out, you just do all the same things with your left hand instead. The matrices are written in the usual way.

2) Z is clipped at +/- 1 whatever you put for glDepthRangef

I can't think of a good reason why they do this, but you can get around it by squashing z after the rotation and perspective transforms. You could simply write gl_Position.z*=0.01 at the end of your vertex shader, or you could pre-multiply your all-in-one matrix by a unit matrix with the 3x3 element replaced with 0.01.

3) Cube maps have the top at +y, not +z as you might expect.

'Nuff said.

If you see grey lines where the cubes join together, that means you have a discontinuity of texture coordinates over that boundary. For instance, consider the edge between the +y and +z faces. That edge is parameterised by x. You might have cocked up so that the +y face has x=0 at the left, but the +z face has x=0 at the right. If so, at e.g. x=0.25/0.75, OpenGL will try to interpolate the whole range of texture lookup results from 0.25 to 0.75 into the little triangle that straddles the boundary. The result is roughly grey.

You can test this theory by fiddling with your mipmaps. You can make every mipmap below a certain level plain red. According to the theory, it has to mipmap very deeply to get that grey. If your grey lines turn red after you've painted the deep mipmaps red, then you've proved that discontinuities are indeed the problem. Naturally, this assumes you have mipmapping switched on at all.

4) Matrices are the wrong way round

I suppose which way is the right way is arguable, but your matrix should be like
M[column][row].

5) Render to texture

While you are rendering to the texture, the texture extends from (-1,-1) to (+1,+1), but when you're looking something up in it, it's (0,0) to (1,1).

6) Performance

To speed things up, try to move everything from the fragment shader to the vertex shader. There's a quality cost here, but you might even like the resulting effects.

7) SGS 2

Just because it works on everything else, that doesn't mean it'll work on the SGS 2. If you meet somebody who's got one, be nice to them until they let you borrow it.

Monadic parser in python

2010-01-23T01:46:00.000-08:00


#!/usr/bin/python

# general stuff
id = lambda v : v
nott = lambda b : not b
fst = lambda (v,u) : v
snd = lambda (v,u) : u
eq = lambda w : lambda v : w==v
compose = lambda f,g : lambda x : f(g(x))
exists = compose(nott, eq(None))

# no query-colon in python even though it has lambdas    
# simpler forms than this dont work because python isn't lazy enough
#   so we get some superflous "lambda _ :"s later on
# the foos are only numbered to help with debugging - they could all have the same name
# (in python, you need a def instead of a normal lambda if you want ifs or assignments or 
#  other actions in there, or if you want to delay evaluation of things refered to in the function)

def query(test,yes,no):
    def foo4(v):
        if test(v):
            return yes(v)
        else:
            return no(v)
    return foo4

# underscores in variable names are a convention meaning we don't care
def throw(_):
    raise Exception

# a string-wrapping generator that repeatedly takes a filter function, 
#  applies it to the head of the stream, and if it passes, returns 
#  the character and moves along to the next one in the stream
#  or otherwise returns None and doesn't move along
# getting these generators in sync is a trial-and-error job
def nudger(str):
    def foo1(i):
        progress=0
        test = yield # see four lines below
        c = i.next() # consume first character from raw stream
        while True:
            if test == "Where": # for error reporting
                test = yield progress # waits for a send, sets 
                # test to send's parmeter, runs to the next yield, 
                # and then returns from send with progress as its return value
            elif test != None and c != None and test(c): # IF it matches, 
                test = yield c #yield it and pull another from raw stream                
                try:
                    c = i.next()
                    progress += 1
                except StopIteration:
                    c = None
            else: #ELSE yield None and don't pull
                test = yield None
    s = foo1(iter(str))
    s.next() # always gotta do this before sending to it
    return s

# wrapped test string
s = nudger("X3$5z2[3]1,2_1984foo1066bar1000*(25+3)-100*(5-10*(11/4))+1")

# just hide those ugly sends   
filter = lambda test : lambda s : s.send(test) 
# some basic filters
this = that = lambda want : filter(lambda c : c == want) # get specific character
member = lambda set : filter(lambda c : c in set) # get anything in set
between = lambda min,max : filter(lambda c : 
   ord(c)>=ord(min) and ord(c)<=ord(max)) # get within range
either = lambda test1,test2 : lambda s : test1(s) or test2(s) #or

# A parser is a function that chomps some characters out of a passed stream 
#  and returns a value corresponding to what it chomped
# If it doesn't find the first character of what it wanted must leave 
#  the stream unchanged and return None
# If it finds just some of what it expected it must raise an exception 
#  (LL(1) grammars only) 
# It may ignore the stream and just return a value it already knows
# These are parsers:

digit = between("0","9")    
letter = either(between("A","Z"),between("a","z"))
white = member([" ",chr(10),chr(13),chr(9)])

print this("$")(s) #should fail
print letter(s)
print digit(s)
print this("$")(s)

# Monadic bind : easy version
# If this fries your brain, start by reading "compressed" or "inbrackets" below 
# Takes a parser "first", a function "next" and returns a parser "big"
# The next function is supposed to return a parser when called with a value
# The big parser (when applied to a stream) runs the first parser, 
#  shoves its return value into the next function,
#  runs the resulting parser and returns its result
# If the first parser fails, the next function is not called but None is returned
# If the second parser fails, we throw an exception

# Monadic bind: fancy version:
# Adds customisation of what's returned if the first parser fails, 
#  and pre and post functions to be applied:
#  to the first parser's return value before passing it to the next function and
#  to both parsers' return values to decide what to return from the big parser, respectively
# The easy post function returns its second parameter unchanged but throws if it's None. 
# We can remove that throw for productions of indeterminate length
# Pre is a bit of a hack but otherwise we'd need a state monad, and this ain't a pure language anyway
# Post is legit

def bindfancy(fp,dv,pre,post,nf):
    def foo3(s):
        v1 = fp(s)               #call the first parser
        if v1 != None:
            p2 = nf(pre(v1))     #pre-process the answer and pass it to the next function 
            v2 = p2(s)           #run the parser resulting from the above
            return post((v1,v2)) #figure out the overall return value
        else:
            return dv            # if first parser fails return the default
    return foo3

# Good for most cases:
bindeasy = lambda fp,nf : bindfancy(fp,None,id,compose(query(exists,id,throw),snd),nf)

# If the next parser returns None, don't throw but return result of first:
bindmaybe = lambda fp,nf : bindfancy(fp,None,id,query(compose(exists,snd),snd,fst),nf)    

# Get a digit n then a character c and return c repeated n times
compressed = bindeasy(digit,  lambda n :       # Get a digit called n (it's a string, not an int)
             bindeasy(letter, lambda c :       # get a letter called c
             lambda s :       n_of(int(n),c))) # ignore the stream and return int(n) c's   

n_of = (lambda n,c :                     # query returns a function and we will throw n at it
        query(eq(0),                     # is query's result's parameter zero?
              lambda _:'',               # then the answer is '' irrespective of query's result's parameter
              lambda _: n_of(n-1,c) + c) # else recurse with n-1 and append c irrespective of query's result's parameter
        (n))                             # apply n to the ?: we just made

print compressed(s)
try:
 print compressed(s)
except Exception:                        # this tute isn't about exceptions
 print "Syntax error at character %d" % s.send("Where")

inbrackets = (lambda open,close :               # build a thing that modifies ... 
              lambda p :                        # ... another parser
              bindeasy(this(open),  lambda _a : # get a [ and forget it (_ convention)
              bindeasy(p,           lambda v :  # get a p called v
              bindeasy(this(close), lambda _b : # get a ] and forget it
              lambda s :            v           # ignore stream and return v
              ))))

print inbrackets('[',']')(digit)(s)

infix = (lambda p1,sep,p2,comb :          # get a separated pair but be flexible about
         bindeasy(p1,        lambda v1 :  #  the separator and how to combine the two values
         bindeasy(this(sep), lambda _ :
         bindeasy(p2,        lambda v2 :
         lambda s :          comb(v1,v2)
         ))))

coord = infix(digit,",",digit, lambda a,b : a+" by "+b)

print coord(s)          
print this("_")(s)

# Recursive monad: 
# word_ is the "next" function 
# its parameter is the word so far
# if parsing fails it returns the word so far
# if it succeeds it adds the letter it found to the word and passes it
# to the next function, which is _word

word_ = (lambda sofar :              # this is not a parser YET ,,, 
         bindfancy(letter,           # the first parser 
                   sofar,            # what to return if first parser fails
                   lambda l:sofar+l, # the next round's sofar
                   snd,              # same as bindeasy
                   word_             # the "next" function
                  ))

word = word_("")                     # ,,, NOW it's a parser

# generalising that:
# f should take sofar, then the value found by the parser 
# and return the value you want passed as sofar to the next round

def zeroormore(p,i,f):              # after providing these three you get an almost-parser
    def foo5(sofar):                #  like word_. provide sofar and you have a parser
        return bindfancy(p,          
                         sofar,
                         f(sofar),  # give f sofar and it returns a function of parse result 
                         snd,       #  onto the next round's sofar
                         foo5)      # recurse
    return foo5(i)                  # this is like word = word_("")
    
number = zeroormore(digit,
                    0,
                    lambda sofar: lambda v: 10*sofar+int(v) ) 
# but that returns 0, not None, if it finds nothing

print number(s)       
print word(s)
  
# oneormore: do one normal parse of p1 then go into zeroormore with p2
# bindfancy applies pre to the result of the first parse 
#  before passing it to zeroormore as sofar

oneormore = (lambda p1,pre,p2,f : 
             bindfancy(p1, 
                       None, 
                       pre,                       # result of this on p1's result is v
                       snd, 
                       lambda v : zeroormore(p2, 
                                             v,   # return this on fail 
                                             f))) # f combines v with results of p2s for new v

number = oneormore(digit, int, digit, lambda sofar: lambda v: 10*sofar+int(v))
word   = oneormore(letter, id, letter, lambda sofar: lambda v: sofar+v )

print number(s) 
print word(s)

# use the first parser in the list that works
def anyof(plist): 
    def foo6(s):
        for p in plist:
            v = p(s)
            if v != None:
                return v
    return foo6

#this lot has to be in defs because it's circular:
# otherwise this is just like factor = anyof([ number , inbrackets('(',')')(expression) ])
def factor(s):
    return anyof([ number,
                   inbrackets('(',')')(expression) ])(s)                             

def term(s):       
    return oneormore(factor, 
                     id, 
                     anyof([ bindeasy(this("*"), lambda _ : 
                             bindeasy(factor, lambda n : 
                             lambda s : n ))
                             ,
                             bindeasy(this("/"), lambda _ : 
                             bindeasy(factor, lambda n : 
                             lambda s : 1.0/n)) ]), 
                     lambda sofar : lambda m : sofar * m)(s)

def expression(s):       
    return oneormore(term, 
                     id, 
                     anyof([ bindeasy(this("+"), lambda _ : 
                             bindeasy(term, lambda n : 
                             lambda s : n ))
                             ,
                             bindeasy(this("-"), lambda _ : 
                             bindeasy(term, lambda n : 
                             lambda s : -n )) ]), 
                     lambda sofar : lambda m : sofar + m)(s)

print expression(s)

# Exercise (i.e. the bit I couldn't be bothered to finish): 
# write a generator that reads s and strips out anything that
#  fits the passed parser e.g. comments and/or whitespace and can be
#  used in place of s throughout the above.
# I.e.: fix strip and the comments so that:

blockcomment = linecomment = white   # write something more interesting
strip = lambda p : lambda s : s      # figure this out

# and use just like this:
print expression( strip(blockcomment)(
                  strip(white)( 
                  strip(linecomment)(   # better do linecomments before removing newlines
                  s)))) 

# Better still, make it a pre-processor that can replace the found bit with something
#  dependant on it.

A program to write a program

2009-09-30T06:34:00.001-07:00

I'm in the middle of writing a program to write a program. I'm not sure what kind of program it's going to write. I know that it'll be in Intel machine code though (and I don't mean assembly language.)

This is a bit like Corewars, only I'm not inventing any game. The game is to run on an Intel computer, but I didn't invent that. There's a limited amount of space and processor time on this computer, and there are lots of conceivable code snippets that can copy themselves, with or without variations. Even if they copy themselves perfectly, other snippets are likely to overwrite them. If the system doesn't get into an endless loop, I think I can expect evolution to break out at some point. I can make sure it doesn't get into an endless loop by overwriting snippets myself. I can just flip bits in the memory at random.

My code boots the chip into protected mode and sets up handlers for all the faults Intel know as well as a periodic interrupt. It then creates a ring 3 segment ("tank") aliased as both code and writable data, fills it with random numbers and jumps into it. When faults or timers occur, a few bits near the last point of execution get flipped, and control jumps back in somewhere else.

I'm pretty sure this must start evolving eventually, but I'm not sure how long I'll have to wait. To find out if anything is happening, I just need to zip the tank. A small zipfile would indicate evolution.

The code runs in VMWare Player, is about three quarters done and you can get it from here: http://github.com/adrianmay/digilife

Things the environmentalists don't tell you

2009-09-29T08:14:00.000-07:00

Recycling paper actually reduces the number of trees in the world by filling the demand for wood pulp, which is mainly supplied by the kind of soft, fast growing trees you can see lined up in rows all over Scotland. It becomes more lucrative to put greenhouse gas farting sheep on the land instead.

In the Salonga national park in Congo, the conservationists chase Pygmies out of the forest because they hunt bushmeat. Let that be a warning to any jaguars reading.

If we just threw all the plastic bottles into the sea, in a million years time there would probably be a cute new species of octopus using them as a shell.

Brazil is the number one producer of bio-diesel. It is also home to most of the world's rain forests. Do you still believe that bio-diesel is carbon-neutral?

The World Wildlife Fund are supporting a program to cut the horns off Rhinos in Zimbabwe and Namibia. The idea is to make it commercially unattractive to poach them. Preliminary results indicate a 100% calf mortality rate due to predators the dehorned cows cannot fight off, while poaching continues for the sake of what scraps of horn remain.

Most of the species we go dewy eyed about (whales, polar bears, tigers, etc) owe their existence to an extreme ecological catastrophe 65 million years ago. The ones we don't like (mosquitos, cockroaches, crocodiles, etc) were unaffected.

The Kyoto Protocol does not prevent global warming. In fact it barely even slows it down. It just spends a phenomenal amount of money shutting the door after the horse has bolted. Adapting to the new climate will also cost a lot of money but without us having the opportunity to decide whether we want to spend it or not. Perhaps we should stop wasting time and money failing to postpone the inevitable, and start spending money preparing for it before it's too late.

Yet another project health check

2009-09-29T07:33:00.000-07:00

Pick a random line of code from your large, buggy project and ask yourself the following question about it.

Was the problem it solves created by the requirements, or by the code?

Repeat that 100 times and you've got your percentage health score. Most large projects spend about 95% of their code worrying about the code.

For instance:

hr = CoCreateInstance(CLSID_SomeDummyObj, NULL, CLSCTX_INPROC,

This is definitely solving a problem in the code. It's pure Blindleistung resulting from the choice of technology, so that's bad.

if ( bus->driver->teatime() > now() ) bus->findnewdriver();

This is all about logic that the requirements engineer would recognise, so that's good.

getcommandqueue()->enqueuecommand(new SingCommand(song));

This is all codey code. The code to sing the song is a member of the SingCommand, so if you'd chosen that member, you'd score for useful work, but the need to put it in a queue first is not something the requirements engineer asked for.

This measurement is a productivity ratio. Codey code slows down writing, reading, debugging and documenting and it provides lots of places for bugs to hide. Sometimes you need some of it, but people normally write a lot more than they need.

Brevity=Quality

Creationism=Darwinism

2009-09-28T02:35:00.001-07:00

It's ironic that Richard Dawkins can think of nothing more useful to do with his golden years than beat up soft targets like the "Intelligent Design" protagonists. Why ironic? Because his main contribution to the world is the theory that could leave creationists and Darwinists apparently agreeing with one another.

Dawkins proposed that beliefs, habits, ideas, technologies, languages, religions, recipes, fashions, in fact, anything that goes on within or between human minds can be viewed as self interested, evolving life forms. It is undeniable that we can ask Darwinistic questions about such entities and the answers will tell us a lot about how common they are. For instance, there have been non-evangelical religions, but an awful lot of their followers now subscribe to an evangelical one instead. It's important to understand that we are talking about the success of the "memes" themselves, rather than that of the people they inhabit. So if you invented a great pizza but didn't make any money from it because every other pizzeria in town copied the recipe, then the recipe, viewed as a meme, would be doing well.

If we go along with Dawkins about intelligence being a Darwinian process, then the modus morons that all Darwinian processes could be considered intelligent presents itself. If it held, then it would be quite accurate to say that the animals etc came about through a process of "Intelligent Design" (albeit in more than 7 days, or is it 6?) Discussions about whether things like the eye are too good or bad to have evolved or been designed, would be moot, because the two processes would be the same anyway. (BTW, it evolved on at least forty independant occasions.)

But does the modus morons hold? We can see that the biosphere solves temporary problems so as to keep itself in equilibrium, just like we do. If we are hungry, we eat. When the biosphere had too much oxygen it invented animals, and it can usually come up with a disease or predator to cope with any excess of a single species. Human technology increases in both complexity and efficiency over time, as does natural technology. The results of human and natural development both exhibit ingenuity, but also dogmatism: our spines weren't really designed for walking upright but we have to make do, just like we have to make do with the Brits driving on the wrong side of the road.

One has to compare like with like here. Earths and humans are different, but mainly because of how many there are and the extent to which they interact, compete and reproduce. The proper comparison is between the biosphere and human society as a whole. An individual in an evolving population has intentionality (even if only to slither to the warm end of the microscope slide) and an evolutionary prognosis which it can, to some extent, influence. The Earth, by contrast, sits in a constant environment and could do nothing about it if it did start hurtling into the sun or something. Earths don't reproduce or compete with one another either.

Perhaps this explains why individual humans do so much talking about saving the environment but nothing significant ever happens at the global level. Individual humans have been trained by evolution to compete with one another, but there is no society of intelligent races competing to steer the climates of their worlds. If there were, the sensible ones would colonise more of the universe than us, so climactic common sense would evolve as a characteristic. But human society has not been through that evolutionary lesson, not even a tiny bit, so we just carry on doing what we have learned like the Earth carries on spinning around the sun.

Is the biosphere conscious then? Does it have feelings? This is a pointless question because one can never test for it anyway. Even if we made a totally human-like robot that claimed to have personal experiences, some people would still accuse it of merely bouncing electrons around a circuit while the robot retorted that they were merely rubbing neurons together. There have been cultures that even denied women consciousness and many people find it convenient to imagine that laboratory animals don't feel much pain because they can't recognise themselves in mirrors for instance. So why ask a question that can never be settled?

I don't think Dawkins can help with God's other jobs though: praying to the biosphere is unlikely to yield results and evolution is more interested in killing things than taking them to heaven afterwards. Nevertheless, the proposition that nature exhibits such ingenuity that an intelligent designer must be responsible, appears not to be so silly after all. I wouldn't be surprised, though, if half of the people gaining credibility here thought it meant that what humans have achieved is all mere chance.

Google gives up on open source

2009-09-26T20:15:00.001-07:00

Empires come and go, but they all behave like empires.

Android was supposed to be the open source phone. Anybody could contribute to it or modify it. That was the lie Google used to whip up some ideologically driven publicity for their most adventurous diversification ever. What diversification? Into phones? No. I mean into proprietory software.

Google are now saying that the software you'll find on a typical Android phone is not just Android. Gmail, YouTube and a bunch of other things are Google proprietary apps and "Android" does not include them. Whatever you develop for Android, you may not distribute these apps.

That's why they just sent a Cease and Desist letter to Cyanogen, who distributes his modified OS as a ROM that includes the latest Google apps in their original form. For some strange reason, Cyanogen seems to see this as wiping out his business overnight, and I'm eagerly awaiting some sign of flexibility from him.

Right now, web servers are crashing under the volume of furious protests this is causing. One of the leading Android developers at Google (Jean Baptiste Queru) threw such a tantrum that he twittered an offer of his services to the competition, but he seems to have got over it within a few days. It must be a mistake for Google to throw away their open source street-cred like this, and it's another nail in the coffin for the illusion that the new Microsoft would behave any better than the old one.

Assuming we never suffered from that illusion, it's also pathetic of Google to fail to get their brains around even this most elementary of open source monetisation puzzles. Those apps are already generating revenue in several ways. They drive traffic to the Google services they are named after, and land the customer with a huge 3G/UMTS bill.

So why did they do it? Why did they stop somebody distributing apps to customers who already had those apps on their phone before they took the shrink wrap off? It's because they charge fees to the networks and phone companies for distributing the apps, who must have been complaining about Cyanogen getting the same priviledge for free. This complaint would not be grounded because Cyanogen does not benefit from 3G traffic.

There's no question of charging anybody for the equivalent apps on your PC. Google don't deal with the PC manufacturers who pre-install Windows on your PC. Microsoft do, but Ubuntu don't. So who does Google seem to be aping here?

And what does Android now allow that the rest don't? People can and do develop apps for Windows Mobile, PalmOS, etc. The only special thing about Android was access to the OS itself, but Google just made that dependent on the customer not wanting any software from Google, knowing damned well that they do. If that isn't monopoly abuse, what, pray tell, would be?

If Google can't make up their mind which philosophy they want to follow, they won't be successful in either sense. They are forsaking a lot of fees for Android itself by leaving it open because they want the neo-socialist credentials to compete with Apple's cult image, but they just blew that for the sake of clawing a bit of proprietary revenue from apps that have never before been anything but interfaces to their services, and for which fees have never before been charged. The hypocrisy is almost as staggering as the stupidity of it.

If the Android leadership really is so schizophrenic as to combine their first foray into open source development with their first attempt to charge licence fees, then a lot of people might want to avoid this confused market altogether, and Cyanogen would seem to be of that opinion.

But he does still have the option of distributing his OS modifications without physically distributing the Google apps. After all, the customers have already got copies of them. All Cyanogen needs to do is suck the Google apps out of the original ROM, or install his modified OS without disturbing them. That ought to be possible, oughtn't it? The apps would still update themselves and the user could get entirely new apps by downloading the vendor's latest firmware, but presenting it to Cyanogen's sucker instead of installing it. There would be no legal challenge to this because Cyanogen would be not be giving the user any software that somebody else didn't already give them. I think even Google would be happy because they could still charge somebody for their apps, and that somebody couldn't complain about anyone else getting it for free. Everybody could be happy about Cyanogen's contribution to the attractiveness of any Android phone.

But Google would still have lost everybody's trust, and they would still be a corporate contradiction.

Data duplication is the root of all evil.

2009-09-24T03:04:00.000-07:00

It is astonishing that the style gurus never mention this issue. It's far more important than even basic modularisation, let alone OO. Think about the last bug you handled and ask yourself whether or not there was some duplicate data behind it. I reckon this accounts for at least 50% of bugs, probably more like 75%.

People duplicate data because they want it in a different format, in a different machine, process or module, because they don't know it already exists or just because nobody told them it was wrong to do so. It's inevitable that the two copies will end up with different values sooner or later, resulting in an inconsistent system state. These bugs are normally "fixed" by inserting some overseen update of the redundant copy, but there are probably dozens of other places in the code where it needs to be updated, if not now then after a few development cycles. When the bug resurfaces the symptoms will look the same, and the developer will say "But I already fixed that one." No you didn't; you just postponed it.

Once a redundancy exists, it's human nature to fail to maintain both copies. People normally expect one solution to one problem. When asked to write code to update the doofah, a programmer will declare himself finished when he's found the doofah and updated it. Even if he suspects that a second doofah might exist, how many more is he supposed to look for?

Code managers should scour their code for any data redundancy and eliminate it. Any change that adds heap data should be audited thoroughly. The heap should always be as small as possible. (In Haskell it's always zero.)

If machine or process boundaries force duplication, then a low-level update mechanism should be in place with policies for connectivity failures, locking, etc (but how many of our process or machine boundaries are really forced?) Module boundaries don't force data duplication, they just encourage it. If you can't be bothered to write

thismodule->parent->modulesmanager["theothermodule"]->doofahs[thismodule->parent->modulesmanager["theothermodule"]->getcurrentdoofah()]->asString()

every time, just put a function to say that in your own module, but don't copy the doofah.

Code redundancy can also be dangerous, but nowhere near as bad as duplicate data.

The data furnace

2009-09-23T01:51:00.000-07:00

Can't remember where I read this but I thought I'd regurgitate it anyway.

They used to think that quantum mechanics placed a limit on how efficient computers could be. They even estimated how many orders of magnitude more electricity it costs to flip one of today's best switches than the theoretical best one anybody could ever make.

But if you think about it, that doesn't really make sense. It's not QM, but thermodynamics that governs these things. Normally, things decay from ordered to disordered states, which means that if you set a bit to 1, it might be either 0 or 1 by the time you come back. That decay can happen by itself, but if you want to fix it back to 1, you'll accidentally randomise some other bit somewhere else in the universe. When machines "use" energy, they don't destroy it, they just let it escape their control. What they sell over the national grid is not just energy but energy where we want it.

So if we want to make a computer of unlimited efficiency, we have to be careful about taking bits whose values we don't know and setting them to a value we do. But supposing we already had a bit lying around whose value was what we wanted, and we just swapped that with the bit we want to set. Before and after, we would have one known bit and one unknown one, so we wouldn't have changed the amount of order in the universe. We can do that for free.

But where would all the known bits come from? We'd need a machine to make them. It would receive the bits we don't need anymore and set them to 1s and 0s ready to trade for our next batch of used data. It would certainly use energy and produce heat. Best keep it in the garden where it can cool down easily.

Monad tutorial in C++

2009-09-21T20:04:00.000-07:00

/*

IT'S NOT ABOUT THE MONADS

Every Haskell newbie is expected to write a monad tutorial for homework so here's mine. I'm gonna do it in C++ because Haskell and monads are actually two different learning curves, and I assume that anybody who has even heard of Haskell probably learnt C++ while the eggs were boiling one day.

Everybody struggles to understand what monads are, but that's not really the important question. Monads are how you tell the compiler which >>= you want, so the first question is, what's >>=?

>>= is a more flexible way of composing functions than the usual g(f(x).

Seeing as g(f(x) is the default way of composing functions, it's easy to assume it's the only way, and even when you spend half your life composing them differently, e.g. by checking return values, or logging, you don't necessarily realise that you are actually using an alternative notion of function composition.

C++ code generally includes a lot of boring error checking and logging at least, which just makes the code tedious to read. It normally remains unfinished resulting in bugs. If you can factor out the way functions are composed, you can make it comprehensive, concise and pretty.

So what we're trying to develop is a general scheme for writing alternative styles of function composition. On top of that, we'd like a slick way of choosing between them.

So let's try that on the three examples of normal, careful and logged function composition. Logging is going to mean appending the functions' return values to a string - we assume the programmer can read his own code and figure out the order of execution without a log. This is more closely associated with composition than the usual idea of logging the function entries and exits. Nevertheless, the subject functions will end up with the option of logging on their own.

We'll make composer functions that take two subject functions and return an overall composed function according to these definitions of composition.
*/


#include <string>
#include <sstream>
#include <iostream>
using namespace std;
string itoa(int i)
{
 std::stringstream sin;
 sin << i;
 return sin.str();
}

//Define some basic types to play with


typedef int A;
typedef string B;
struct C {int x; int y; C(){}; C(int x_, int y_)
 :x(x_),y(y_) {}};
ostream & operator<<(ostream & os, C & c) 
 {return os << c.x << "," << c.y;}

//Define some types for the subject functions. We'll avoid using return values altogether because they're even less flexible in C++ than parameters

//Define the subject functions


char numnames[][6]={"zero","one","two","three"};
void fn1(A & a, B & b)
{
 b=numnames[a]; 
 //crash on >3 is deliberate here
}
void gn1(B & b, C & c)
{
 c.x=b.length();
 c.y=b[0];
}

//Now for the composers...


void composeNormal1(
 void (&f) (A&, B&), 
 void (&g) (B&, C&), 
 A & a, C& c)
{
 B b;
 f(a,b);
 g(b,c);
}
void testNormal1() 
{
 C c; int a = 3;
 composeNormal1(fn1, gn1, a, c); 
}

/*

composeCareful is not going to work on the above types because they don't return errors at all, so lets fix that
*/


void fe1(A & a, B & b, bool & e)
{
 e = (a<=3); 
 if (e) b=numnames[a];
}
void ge1(B & b, C & c, bool & e)
{
 c.x=b.length();
 e = (c.x>0);
 if (e) c.y=b[0];
}
void composeCareful1(
 void (&f) (A&, B&, bool&), 
 void (&g) (B&, C&, bool&), 
 A & a, C & c, bool & e)
{
 B b;
 f(a,b,e);
 if (e) g(b,c,e);        
}
void testCareful1() 
{
 C c; A a=3; bool e;
 composeCareful1(fe1, ge1, a, c, e); 
}

/*

For logging, the functions themselves don't need to change because compose is going to handle the logging, but the composed function has to return the log. We would like to be able to take the composed function and pass it to another compose as either the first or the second parameter, so that means compose should take functions that output logs. Anyway, the log is supposed to grow so the log so far has to come from somewhere. The only place it can come from is the only place it can go to, i.e. the output of functions, whether composed or not.
*/


void fl1(A & a, B & b, string & log)
{
 b=numnames[a]; 
}
void gl1(B & b, C & c, string & log)
{
 c.x=b.length();
 c.y=b[0];
}
string toString(int i) {return itoa(i);}
string toString(string s) {return s;}
void composeLogged1(
 void (&f) (A&, B&, string&), 
 void (&g) (B&, C&, string&), 
 A & a, C & c, string & log)
{
 B b;
 f(a,b,log);
 log += "Got:";
 log += toString(b) + ";";
 string l_;
 g(b,c,l_);      
 log += l_;      
}
void testLogged1() 
{
 C c; A a=3; string log;
 composeLogged1(fl1, gl1, a, c, log); 
}

/*

OK, we've achieved something: we've factored out the logging and checking code into our own composer functions so we don't have to write those details all over the code. But we still have to write composeLogged, composeCareful or composeNormal everywhere, it'll be hard to change between them, and we have to write different versions of the subject functions according to which type of compose we're using. So let's try to improve on that.

An OO programmer might be thinking that compose could be an overridable in some yet-to-be-invented class hierarchy. Depending on which subclass we make, we'd get one of the composing styles. It would need the subject functions passing to it somehow, but we can't use an overridable for that because the C++ override system only overrides functions with the same parameters, wheras our subject functions have different types for the different composing styles. The same applies to the compose operation itself. Actually, there's no use for overrides here at all, but overloading global functions might work.

In fact, the composeLogged, composeCareful or composeNormal could all have the same name because they all take different auxillary parameters (nothing, string and bool) but this is just an accident of the example we're using. We can tighten that up while we write the overloads.
*/


struct HoldNormal {};
void compose2(
 void (&f) (A&, B&), 
 void (&g) (B&, C&), 
 A & a, C & c, HoldNormal& z) ;

struct HoldCareful {bool e;HoldCareful(bool e_):e(e_){}};
void compose2(
 void (&f) (A&, B&, HoldCareful&), 
 void (&g) (B&, C&, HoldCareful&), 
 A & a, C & c, HoldCareful& e)
{
 B b;
 f(a,b,e);
 if (e.e) g(b,c,e);      
}
void fe2(A & a, B & b, HoldCareful & e)
{
 e.e = (a<=3); 
 if (e.e) b=numnames[a];
} //etc for the other subject functions

struct HoldLogged {string log;};
void compose2(
 void (&f) (A&, B&, HoldLogged&), 
 void (&g) (B&, C&, HoldLogged&), 
 A & a, C & c, HoldLogged & log)
{
 B b;
 f(a,b,log);
 log.log += "Got:";
 log.log += toString(b) + ";";
 HoldLogged l_;
 g(b,c,l_);      
 log.log += l_.log;
}

/*

Sooner of later we have to extend this to types other than int, string and that struct, which we do in C++ using templates.

*/


void fl3(A & a, B & b, HoldLogged & log)
{
 b=numnames[a]; 
}
void gl3(B & b, C & c, HoldLogged & log)
{
 c.x=b.length();
 c.y=b[0];
}
template<class AA, class BB, class CC> 
void compose3(
 void (&f) (AA&, BB&, HoldLogged&), 
 void (&g) (BB&, CC&, HoldLogged&), 
 A & a, C & c, HoldLogged & log)
{
 B b;
 f(a,b,log);
 log.log += "Got:";
 log.log += toString(b) + ";";
 HoldLogged l_;
 g(b,c,l_);      
 log.log += l_.log;
}
void testLogged3() 
{
 C c; A a=3; HoldLogged log;
 compose3(fl3, gl3, a, c, log); 
}

/*

That was a bit messy. We had to make another HoldLogged in the middle of compose just to call the second function, and we've actually got three different log streams coalescing in debatable ways: the one passed to the combined function, and the ones generated by the two functions. In fact, we've had extra bools and strings from the start. All we really want is to concatenate the logs from the two subject functions with compose's two penn'orth in between and return that. Maybe a better way is to have the subject functions create the HoldLoggeds. This would mean you can't pass the Hold/string/bool or whatever into a subject function, but you probably don't need to anyway. If there had been an error in the first function, we wouldn't be calling the second at all, so the second doesn't need to be told that the first was OK. For logging, the second function can start with a blank log and compose puts the strings together. So it might work.

In that case, the Holds made by the subject functions should be returned as normal return values because then they'll be created on the stack and cleaned up easily.
*/


HoldLogged fl4(A & a, B & b)
{
 b=numnames[a]; 
 return HoldLogged();
}
HoldLogged gl4(B & b, C & c)
{
 c.x=b.length();
 c.y=b[0];
 return HoldLogged();
}
template<class AA, class BB, class CC> 
HoldLogged compose4(
 HoldLogged (&f) (AA&, BB&), 
 HoldLogged (&g) (BB&, CC&), 
 A & a, C & c)
{
 B b; 
 HoldLogged log = f(a,b);
 log.log += "Got:";
 log.log += toString(b) + ";";
 log.log += g(b,c).log;
 return log;
}
void testLogged4() 
{
 C c; A a=3; 
 compose4(fl4, gl4, a, c); 
}

/*

Something quite interesting has just happened though: compose no longer cares about A! We can call f ourselves and just pass its result (B) to compose along with the Hold it made. (Later we'll put that back so it looks nice from the test function, but we can do the checking and logging logic without A.)

*/


template<class BB, class CC> 
HoldLogged compose5(
 HoldLogged & logf, B & b, 
 HoldLogged (&g) (BB&, CC&), 
 C & c)
{
 logf.log += "Got:";
 logf.log += toString(b) + ";";
 logf.log += g(b,c).log;
 return logf; 
 //its a bit naughty that we're returning the same log we 
 //received, but it doesn't matter at this stage
}
HoldLogged fl5(A & a, B & b)
{
 b=numnames[a]; 
 return HoldLogged();
}
HoldLogged gl5(B & b, C & c)
{
 c.x=b.length();
 c.y=b[0];
 return HoldLogged();
}
void testLogged5() 
{
 B b; C c; A a=3; 
 HoldLogged log = fl5(a,b);
 compose5(log, b, gl5, c); 
}

/*

Its a bit of a faff pulling b and the log around seperately, but we could stash one inside the other.
*/


template<class T> 
struct Logged  : HoldLogged
{
 T t;
 Logged(T t_):t(t_){}
};
 
template<class BB, class CC> 
HoldLogged compose6(
 Logged<BB> logf, 
 HoldLogged (&g) (BB&, CC&), 
 C & c)
{
 logf.log += "Got:";
 logf.log += toString(logf.t) + ";";
 HoldLogged log2 = g(logf.t,c);                  
 logf.log += log2.log;
 return logf;
}
Logged<B> fl6(A & a)
{
 return Logged<B> (numnames[a]);
}
HoldLogged gl6(B & b, C & c)
{
 c.x=b.length();
 c.y=b[0];
 return HoldLogged();
}
void testLogged6() 
{
 C c; A a=3; 
 compose6(fl6(a), gl6, c); 
}

/*

But we want f and g to look the same.

*/


Logged<B> fl7(A & a)
{
 return Logged<B>(numnames[a]);
}
Logged<C> gl7(B & b)
{
 return Logged<C>(C(b.length(), b[0]));
}
template<class B, class C>
Logged<C> compose(
 Logged<B> logf, 
 Logged<C> (&g) (B &))
{
 Logged<C> logg = g(logf.t);                     
 logg.log = (logf.log 
  + "Got:" + toString(logf.t) + ";"  
  + logg.log);
 return logg;
}
void testLogged7() 
{
 A a=3; 
 Logged<C> log = compose(fl7(a), gl7);
}

/*

What >>= really does is return a function that acts on A. To do that in C++ we'll have to faff around
like this:

*/


template<class AA, class BB, class CC>
struct Logger
{
 Logged<B> (&f) (A &);
 Logged<C> (&g) (B &);
 Logger(
  Logged<B> (&f_) (A &), 
  Logged<C> (&g_) (B &))
  :f(f_),g(g_){}
 Logged<C> operator()(A & a) 
 {return compose(f(a),g);}
};
void testLogged8() 
{
 A a=3;
 Logger<A,B,C> logger(fl7, gl7) ;
 Logged<C> lc = logger(a);
}

/*

Now we've got something presentable for the logger, we should try to extend it to the careful and normal composers.
*/


template<class T> 
struct Careful 
{
 bool b;
 T t;
 Careful(T t_):t(t_),b(true){}
 Careful():b(false){}
};
Careful<B> fc7(A & a)
{
 return (a>3) 
  ? Careful<B>() 
  : Careful<B>(numnames[a]);
}
Careful<C> gc7(B & b)
{
 return (b.length()==0) 
  ? Careful<C>() 
  : Careful<C>(C(b.length(), b[0]));
}
template<class B, class C>
Careful<C> compose(
 Careful<B> carefulf, 
 Careful<C> (&g) (B &))
{
 if (!carefulf.b) return Careful<C>();
 return g(carefulf.t);                   
}
void testCareful7() 
{
 A a=3; 
 Careful<C> careful = compose(fc7(a), gc7);
}

/////////////


template<class T> 
struct Normal 
{
 T t;
 Normal(T t_):t(t_){}
};
Normal<B> fn7(A & a)
{
 return Normal<B>(numnames[a]);
}
Normal<C> gn7(B & b)
{
 return Normal<C>(C(b.length(), b[0]));
}
template<class B, class C>
Normal<C> compose(
 Normal<B> normalf, 
 Normal<C> (&g) (B &))
{
 return g(normalf.t);                    
}
void testNormal() 
{
 A a=3; 
 Normal<C> answer = compose<B,C>(fn7(a), gn7);
 //The main thing about this line is that compose 
 //is chosen based on the kind of monad we wrap 
 //the function returns in
}

/*

Normal, Logged and Careful are monads, but they're not exactly the same as their Haskell equivalents. A monad's purpose is to say which >>= we want and carry around the return values of the subject functions plus any other info that >>= needs. The constructors of these monads are like return in Haskell.

In Haskell we can just say return and let the type system figure out which monad to make, but C++ doesn't allow overloading based on return type. We could try to do that here but it would only introduce more red herrings like the Logger.

But even in Haskell, the subject functions can't be completely independant of the style of composition. MonadPlus makes this independance a little bit better, but nevertheless, the reason you would want to deploy something like the careful (Maybe) monad is that you know your functions will want to fail for reasons best known to themselves.

There are also monad transformers, which add monad functionality to existing monads. If you always write your functions to use the Id monad (normal above), you can decide later to add other monads to it using something like the MaybeT transformer. This will save some rewriting.


int main(int argc, char* argv[])
{
 A a=3; 
 Normal<C> answer1 = compose<B,C>(fn7(a), gn7);
 cout << "Normal test: Param="<<a<<
  " Answer="<<answer1.t<<endl;
 Careful<C> answer2 = compose<B,C>(fc7(a), gc7);
 cout << "Careful test: Param="<<a<<
  " Success="<<answer2.b<<
  " Answer="<<answer2.t<<endl;
 a=4;
 Careful<C> answer3 = compose<B,C>(fc7(a), gc7);
 cout << "Careful bad test: Param="<<a<<
  " Success="<<answer3.b<<
  " Answer="<<answer3.t<<endl;
 a=2;
 Logged<C> answer4 = compose<B,C>(fl7(a), gl7);
 cout << "Logged test: Param="<<a<<
  " Log="<<answer4.log<<
  " Answer="<<answer4.t<<endl;
 return 0;
}