Death to printf()

A couple of weeks ago, Jean-Francois Roy twote:

Actually, there’s a conceptually simple win: don’t let your format strings determine the byte-level interpretation of data. Especially without bounds.

I mean, duh. Who’d do something so obviously stupid? Well, unfortunately, the C standard library does, and its example has been followed all too many times. I contend that printf()-style formatting is broken and its use should be considered a bug.
Continue reading

Posted in Cocoa, Code | 1 Comment

P och NP nästan utan datorsvammel

1928 ställde matematikern David Hilbert sitt Entscheidungs­problem. Frågan var: finns det en algoritm – alltså en ändlig, fast uppställning deterministiska beräkningssteg – som, givet ett formellt språk och ett valfritt matematiskt påstående på det språket, kan avgöra om påståendet är sant eller falskt?

Alonzo Church löste problemet 1936 – svaret är nej. 1937 kom Alan Turing självständigt fram till samma svar med en annorlunda metod, och den lösningen är mest känd. För att formalisera algoritmbegreppet introducerade han en teoretisk “maskin”, Turing­maskinen, som kan manipulera symboler på en remsa enligt en uppsättning regler.

Praktiska datorer är inspirerade av Turing­maskinen, och har stora likheter med den. Bland annat kan de beräkna samma saker, och de har också samma komplexitets­begränsningar: förhållandet mellan storleken på ett problem och den mängd tid och minne det tar att lösa följer samma mönster. (Principiellt gäller samma begränsningar också för människor under optimala förhållanden, det vill säga att de räknar rätt och i fast takt.)

Ett problem anses vara “hanterligt” om det kan lösas inom en tid som beskrivs av ett polynom i problems storlek, eller mindre (t.ex. n² mikrosekunder för att lösa ett beräkning med n poster). Dessa problem sägs tillhöra komplexitets­klassen P (”polynomial time”).

Turing­maskinen anses kunna beräkna alla funktioner som kan beräknas “effektivt”, vilket dock inte är bevisbart. Ett sätt att försöka motbevisa det är att luckra upp begränsningar i Turing­maskinens definition, där den mest uppenbara är att den är deterministisk, alltså alltid gör samma sak i varje givet tillstånd. Frågan är: om man låter den välja slump­mässigt mellan olika regler, kan den då lösa problem som en deterministisk Turing­maskin (DTM) inte kan? Med andra ord, kan den få fram ett korrekt svar på ändlig tid som en deterministisk aldrig kan nå, om man antar att den vid varje tillfälle väljer “rätt”?

(Gammalt datavetar­skämt – man kan sortera en lista i linjär tid enligt följande: välj en ordning slumpmässigt efter en kvant-slumpkälla. Om listan är oordnad, förstör universum. Om flervärlds­tolkningen stämmer har du rätt ordning i de världar som är kvar, annars finns det ingen kvar som kan klaga.)

Svaret på detta är nej; en ickedeterministisk Turing­maskin (NTM) är inte mer generell än en deterministisk, eftersom en NTM kan simuleras av en DTM. Däremot förefaller den vara snabbare: det finns problem som har polynomtids­lösningar på en NTM men ingen känd för DTM. Problem som kan lösas i polynomtid på en NTM tillhör komplexitets­klassen NP (”nondeterministic polynomial time”).

Alla problem i P tillhör också NP, men man vet inte om motsatsen gäller. Man skulle kunna bevisa att de är lika genom att lösa ett så kallat NP-fullständigt problem i polynomtid. Ett problem K är NP-fullständigt om man kan bevisa att alla problem i NP kan omformuleras till K.

Exempel på NP-fullständiga problem:

  • Handelsresandeproblemet: givet en uppsättning städer och vägar, hitta den kortaste rutten som besöker varje stad och slutar vid startpunkten. Uppenbara tillämpningar på logistik, men också mycket annat som programmering av industrirobotar.
  • Kappsäcksproblemet (med varianter): givet en uppsättning saker med olika volym och värde, välj ut den värdefullaste kombinationen som kan packas i en viss behållare. Viktigt för handelsresande, men också för schemaläggning och andra typer av planering.
  • Primtalsfaktorisering: givet ett stort tal x, hitta två primtal vars produkt är x. Grunden för de flesta kryptografiska system, eftersom det är väldigt lätt att bekräfta en korrekt lösning.
  • Diverse problem inom molkylärbiologi, till exempel multipel linjering/inpassning.

Den som löser ett NP-fullständigt problem har således en lysande karriär framför sig i speditionsbranschen. Dessutom väntar ett startkapital på en miljon dollar i form av Millenniepriset.

Posted in Uncategorized | Tagged | Leave a comment

Imitating Greateness: 16-bit Hack ALU Design in Minecraft

In the autumn of 2010, a video of a sixteen-bit ALU in Minecraft by theinternetftw went viral. A month later, I’d bought the game, played around with circuits a bit and published a detailed description of a functionally identical (but much smaller) ALU on the Minecraft forum – although not exactly in that order.

Due to changes in the Minecraft forum you can now only read the original thread if you’re logged in, and the formatting is messed up, so I’m reposting it here.

By functionally identical, I mean that my ALU has the same instruction set as theinternetftw’s – the Hack instruction set developed for the book The Elements of Computing Systems. I haven’t read the book, but there’s enough information available online to implement the ALU and most other components.

I didn’t copy any part of theinternetftw’s implementation, but I did use pre-existing XNOR gates and adders as noted in the text.

Minecraft is a moving target, but the ALU still works perfectly (and performs much better). If I built it today, I’d consider using repeaters for the data and control busses, but probably stick with torches because repeaters still aren’t implemented in Redstone Simulator. (Repeaters are simpler, and also give you a signal speed of 18 blocks per cycle if you use them well. Torches can do 17, but only 16 in tightly packed parallel busses.)

Some references:

Original posts follow. They’re largely unedited, so they reflect the evolution of the ALU.

Continue reading

Posted in Minecraft | Tagged , , | Leave a comment

On the Mac App Store

When the Mac App Store was announced, I said to someone, “‘Convenient’ isn’t the same as ‘good for you’.” This might look slightly odd in a community dedicated to improving people’s workflows, so I’d like to expand on it. (I should point out that I myself don’t make any money on software and don’t particularly care how big my audience is, so I’m approaching this as an aware consumer.)

My position on convenience is this:

  • Good user experience is the convenience of not having to use a difficult and dangerous hand crank to start your car.
  • The Mac App Store is the convenience of having McDonald’s open in your apartment building.

Continue reading

Posted in Cocoa, Politics | 2 Comments

Almost elegant cave man debugging

Recently, the Twitternets pointed me at Vincent Gable’s blog post, The Most Useful Objective-C Code I’ve Ever Written. It is indeed quite useful; given a semi-arbitrary expression, it prints out the value, using @encode() and macros to minimize drudgery.

Continue reading

Posted in Cocoa, Code | Tagged , | 8 Comments

Black Tuesday

███ ██ ███ ████ ██, ██████ ███████ ███. ██ █ ███ ███. ████ ███ ███, █ █████ ███. ████ █ ██ █ ███ ███ ██ ██ ██. ██ ███ ██ ███ █ █████. ███ ████ ███ ██, ██ ████ ███ ███ FRA ████. ███ ████ █████ ██, █ ███ ██ ███ █. █████ ███ ██ ██ ███ ███ █ ████ ██ ███. ███ █ ██ ███, █ ███ ██. ██ ███ ████ ███. ███ ██████ ███ ██, ██ ███ █ ███ ██.

████ █████ ███ ███. ██ █ █, ███ █ ██ ███ █, ███ █ ██. ████ ██████ ██ █ ███ ███ ███████. ███ █ ██ ██ ██ ████ ███ █ █ ██. ████ ██████, ██ █████ ███ ████, █ ██ ████ ██, █ ██████ ██ ███ █ ██. ██ ████ █████ ██ █ █████. ███ ███ ██ █ ██, ██████ █████ █. ███ ██ ████ ██. ██ ████ ███ ███. ████ █ ████ ██. █ ███ ████ ███, █ ██ ██████ █ ███ ████. ███ █ ██ ██ ██ ███ ████ █ ██ ███. ███ ████ ██ ███ ███ ████ ████. ██ ██ ██ █ ███ ████ ███.

███ █ ███ █. ████ ██ ███ █ ███ ███ ███ █ █ ██. ██ ████ █████ ████. ██ ███ ██ ██ ██ ████ ██ █████ ███ ███. ███ ██ ██, ███ █ ██ █, █████ ██ ███. ██ ███ ██ ████ ███ ████ █ ███ ██ █████. ██ █ ██ █ ██ ███ ████. ███ ██ ██████ ██, █ ████ ███ ███ ██. █████ ████, ██ █ ████ ████, ███ ██ █████ ██, █ █████ ███ ███ █ ██. ███ ██ ██, ███ ████ ████ █, ███ ██ ███. █ █ █████ ███. ████ ████ █████ ███ ██ ████. █████ ██ ███ ███ █ ████ ██ ███ █ ███ ████ ███ ███; █████ █████, ██ ██ ████ █████, ███ ██ █████ █ FRA █ ██ ████ ███ ██ ██ ███. ██ █ ██ ██. ██ █ ████ ███. ██ ██ █, █████ █ █████ █ ██, ████ ██ ███. ██ ███. ███ █ ██ ███, █ ████ ██.

█████ █ ██ ██ ██ ███ █████. ██ ████ ███████ ███ █ ████. ███ ███ ██ █ ██ █████ ██ ████ ██ ████. ██████ ████ ███ ██ ██ ██. ██ █ █████ ██. ██ █████ ████ ███. ███ ████ █████ ██, █ ████ ███ ███ █. ██ █████ ████ ██ ██ █████. ██ ██████, █ █ █████ ███, ██ ██ █████ ██, ██ ████ ███ █ █ ██ █. ██ ██ ██, ████ ██ ███ █ ██, █████ █ ███. ██ ████, ██ █ ██████ ███, █ ██ ████ ███, █████ ███ ███ ██ █████ ██. ██ █ ███ █ ██ ███ ████. ██ ███ ███, ████ █ FRA ███ ██, █████ █ ██. ███ ████ ████ ██ █ ████. ████ ██ ███ ██, ██ ████ ██. ██████ ████ ███ ██ ██ ████. ██ █████ ███ ████.

Posted in Politics | Tagged | Leave a comment

Proposal: generics (and some other stuff) for Objective-C

Some time ago, Greg Parker asked the Twitternets what we’d like to see in a purely hypothetical Objective-C-without-the-C language. Someone — I believe it was Landon Fuller — pointed at an article about the Strongtalk type system for Smalltalk. I quite like the idea of Objective-C-without-the-C (i.e., a language that is native to the Objective-C object system and runtime without the baggage of C), but after reading that article I found myself asking why we couldn’t do something similar in Objective-C.

I don’t think my random musings have much influence on the design of the language, but if I don’t write it down nobody’s going to know how nuts I am, so here’s a semi-concrete proposal for contextual types and generics for Objective-C. Since anyone even mentioning generics in the vicinity of Objective-C will inevitably be flamed for trying to turn it into C++, this is followed by an aside entitled Why This is Not the Baby-eating Spawn of Bjarne Stroustrup. (Nothing personal, Bjarne.)

Continue reading

Posted in Cocoa, Code | Tagged , , , , , | 9 Comments

Multi-type Save Panel Controller

As a change of pace, I thought I’d post some code that doesn’t go out of its way to be bad.

JAMultiTypeSavePanelController is a class (abstracted from ImageIO Export for Acorn) to handle the case where you want to offer the user a choice of formats to save in.

Save panel
Continue reading

Posted in Cocoa, Code | Leave a comment

Wanted: a Right-Handed Keyboard

My current keyboard looks like this:

Left-handed keyboard: keypad on right, empty space on left.

(Well, roughly. It actually looks like this, but I couldn’t find a decent-resolution Swedish one.)

This was a sensible design for the right-handed majority when it was introduced, some time in the stone age. However, since then, something quite important has happened: the keyboard has been joined by another input device, which I suspect is used more than the keypad by most people who are not cursed with an Excel-dominated career.

Continue reading

Posted in Hardware | 4 Comments

Net Neutrality (EU edition)

Network neutrality in Europe is under threat. Not in some vague possible future; right now. In one week, on Tuesday the fifth of May, the European Parliament will vote on the second reading of the Telecoms Package and amendments.

I urge all EU citizens to contact an MEP, via e-mail or (preferably) phone, and encourage them to support the Citizens’ Rights Amendments, which reaffirm net neutrality and anti-censorship positions adopted by the European Parliament in the first reading but subsequently removed by the Council of Ministers in their “common position”.

The primary purpose of these amendments is to make it explicit that the European Convention on Human Rights applies to internet and telecoms legislation. This should be obvious, but it is clear from the actions of politicians that it is not; it is all too clear that many see the internet as a frivolous toy, and civil rights obviously do not apply to toys. (It occurs to me that politicians are probably among those in the western world least affected by the digital communications revolution; if they need to communicate, they talk to their secretaries.)

Draft texts of the amendments (not yet numbered) can be found here: part I, part II, part III. There’s a (rather bad) campaign site here, and a less bad editorial – for all that it’s in a pointy-haired e-mag – in Computer World UK here.

Posted in Politics | Tagged | Leave a comment