Friday 28 December 2012

That damn halting problem

I'm fixing my gEDA fork so that it will work with Guile 2.0. There are several good reasons for doing so, including moving with the times and hopefully cleaner valgrind output. There's an interesting new feature in this new major release of Guile: scheme source files get compiled automatically. (They get cached under $HOME/.cache/guile, in case you're wondering.)

All that cleverness presumably leads to faster-running code (at the cost of slower startup), but it also results in this output to stderr:


;;; compiling /usr/local/geda/share/gEDA/system-gafrc
;;; /usr/local/geda/share/gEDA/system-gafrc:31:18: warning: possibly unbound variable `build-path'
;;; /usr/local/geda/share/gEDA/system-gafrc:40:24: warning: possibly unbound variable `build-path'
;;; /usr/local/geda/share/gEDA/system-gafrc:43:0: warning: possibly unbound variable `load-scheme-dir'
;;; /usr/local/geda/share/gEDA/system-gafrc:48:19: warning: possibly unbound variable `build-path'
;;; compiled /home/berndj/.cache/guile/ccache/2.0-LE-8-2.0/usr/local/geda/share/gEDA/system-gafrc.go
;;; compiling /usr/local/geda/share/gEDA/scheme/geda.scm
;;; compiled /home/berndj/.cache/guile/ccache/2.0-LE-8-2.0/usr/local/geda/share/gEDA/scheme/geda.scm.go

system-gafrc loads geda.scm with a call to (load-from-path "geda.scm") that occurs before the first use of build-path or load-scheme-dir. Unfortunately, the compiler can't "see through" the call to load-from-path, and hence can't see that geda.scm provides the definitions of the functions system-gafrc calls.

The compiler can't see through these calls in the general case because to do so would be to solve the halting problem. Just imagine that just above the call to (load-from-path "geda.scm") were a chunk of code that wrote a definition for build-path if and only if it searched ℤ3 and found a triple such that x3 + y3 = z3. We know now (thanks, Andrew Wiles) that this is impossible, so substitute a search based on any other as yet unproven conjecture, if you like. (This is a counter to the objection of the student (my younger self included) to the impossibility of solving the halting problem: "But I can show that these programs halt!")

And that is why it isn't reasonable to expect guile's auto-compiler to know that build-path and load-scheme-dir are, in fact, defined before use. That's a separate matter from whether it should warn or not.

Thursday 1 November 2012

Life in gEDA?

Vital signs weak, but detectable

A few days ago the geda-user mailing list suddenly remembered that development on gEDA/gaf had slowed to a near standstill. Some soul-searching ensued, and as usual John Doty castigated anyone daring to suggest that gschem's UI could stand a bit of improvement. If it ain't broke, don't fix it! In turn, as usual there were others to castigate him in turn for being unreasonable. Over the years that I've come to know his mailing list persona, I've long known that I disagree with him about the "micro" things: whether, and how, to use keyboard shortcuts, to integrate various tools more closely, and whether and how to add attributes that do special things. In my fork's case: to implement my solution to the "transistor problem", as well as to the related "package pin numbering problem" - both specific instances of the broader light-versus-heavy symbols problem.

My fork is found

And somebody noticed my fork! I'm glad - both because I'm vain and want to be noticed, and because I hope it's a sign that the cliqueishness / insularity of a few years is giving way to a more outward-looking culture. Perhaps they have to: commits to the main repository have slowed to near standstill and KiCAD has all but eaten gEDA's lunch ever since CERN chose the former over the latter. Perhaps, like some people afflicted with depression, the patient has now suffered enough and decides to get better. We'll see.

The truth shall set you free (but first it will cause pain)

There's also what I find a more credible explanation for why Anthony Blake quit working on gEDA than the notion that (presumably - see footnote [1]) KMK "drove him away". I stand by what I told Ales during an IRC conversation in #geda about the disintegrating developer community:

2011-05-19 04:58:21 <berndj>    i could also submit that when people quit, they may indicate "excuses" rather than "reasons" if, say, real-life circumstances were causing them to want to quit soon anyway

If DJ has, as I suspect, the real reason here, then I think a few apologies are due to the victims of the toxic-people witch-hunt. If apologies are too personal for what may have been an emergent and collective phenomenon, an olive branch.

Return from self-imposed exile?

I don't know yet. I've long suspected that I may have been a supposed "toxic person" - it is my perhaps somewhat paranoid way to make sense of how comprehensively my non-trivial patches have failed to find any traction with any of the "gEDA developers" clique. I'm done with explaining, at length, the features that my patches implement, and why I think they are a good idea. Clearly they're forgettable, and not as self-evidently the superior solution to the problems they seek to address as other folks' favoured solutions. No matter. I'm fluent in C, and I can keep maintaining my fork so that I, at least, can have my abstract slots and, one day when I teach pcb to do the other half of the work, pin and gate swapping back-annotations. Perhaps I'll just speak when spoken to, and not earlier.


[1] I'm piecing together the details from fragments, as Ales vaguely described the contents of the "I quit!" private emails he has received. Both KMK and JPD seemed to be the black sheep around the time the elders were discussing the breakdown of the community, but overall, I think the context of the IRC discussion hints that they attributed Anthony's departure to KMK's "abusiveness".

Tuesday 21 August 2012

My response to "A Generation Lost in the Bazaar"

Poul-Henning Kamp argues that a whole generation of programmers is "lost" in the bazaar (strangely, although he refers to it, he seems to use different meanings of the words "bazaar" and "cathedral" than the ones used in ESR's The Cathedral and the Bazaar - PHK's "cathedral" seems to be an analogy for a designed program, rather than an analogy for a xenophobic elite) and wouldn't even recognize a cathedral if encountering one.

I added a comment and then a few hours later it was gone! ACM was censoring me! Luckily Google had indexed the page after I had commented, but before my comment disappeared, and I was able to reconstruct nearly my whole comment by searching for words and phrases I know I had used, and copying the search results' excerpts where I recognized them. It was only a temporary blackout though; I checked again as I write this and noticed my comment was back. Here it is, with some elaboration. (Sentences I missed in italics. Pretty good reconstruction, eh?)
Much of your rant seems predicated on the badness of the autotools. While some of your criticisms are certainly valid (even though I might not necessarily agree what the response should be), you seem to be burning the sources of inelegant software in effigy, by attacking the autotools. The creators of the autotools are not the ones responsible for the problems which the autotools were designed to address!

Secondly, some of your criticisms (here and in your autocrap rant) against the autotools are again misplaced: you seem to want to hold the autotools' creators responsible for the misuses to which others put them, sometimes due to innocent ignorance, other times due to an arrogant sense of superiority (poor translation: I want to convey the german word "besserwisserisch").

As others have pointed out, I'm not surprised either that there are features in a large dependency graph that go into a black hole, like the TIFF support you mention. My curiosity is somewhat piqued to know how this irony resolves. And specifically, is this a run-time dependency or a build-time dependency?

But here's another irony: you don't recognize the deliberate architecture to which the autotools were built. I wasn't around at the time to know if they were originally built cathedral-style (their development now seems very bazaar-like), and you might not appreciate the architectural style used, but boy, you'd better believe it, much of your interaction with them was *designed*. In my experience most of the "friction" in interacting with the autotools is due to the very sort of meta-ignorance you write of: not even knowing what the tools' raison d'être are, or "disagreeing" with them (as if that is possible). I like to say: Those who do not understand the autotools are doomed to reinvent them, poorly. Please understand that I mean a philosophical understanding; I'm sure you know very well what AC_CHECK_LIBS does, for example. And yes, I think I can agree with your criticism of keeping around 20-years-superseded feature checks.

P.S. I know I'm conflating cathedral-as-designed-artifact with cathedral-as-home-of-a-priesthood.
Others argued, and I agree, that a bazaar is the only style that is capable of delivering the gamut of systems we use today. PHK's lament reads a bit like a town planner despairing that there are no cities that consist only of cathedrals, that there's just so much damn chaos in the streets, with people just building their houses where they please! But that's pining for an unworthy goal: centrally planned economies don't work - a universally planned city would result in suburbs that are convenient to administer, but are not what their residents desire. Likewise, in the software world, one could have a landscape of only cathedrals, but then the bazaars would be gone, and so would be the users who shop at the bazaars.

I think it's important to consider the results of the evolutionary pressures acting on the software development industry. Clearly, the unruly bazaar strategies have largely displaced the cathedrals. In some instances we have even had direct invasions of individual members of the cathedral population: witness GCC's conversion to bazaar style with the 2.95 release. More recently, we had the XFree86 conversion to Xorg, another such conversion. I'm not aware of any conversions going the other way. This sort of conversion just doesn't happen consistently if there aren't strong ecological advantages to the bazaar strategy. And I suppose that's my objection to PHK's portrayal of our modern industry as a bunch of unruly wet-behind-the-ears kids who should get off his lawn, dammit, distilled into one word: ecology.

Monday 9 July 2012

Ambiguous output from mysql command-line client

You'd think that a command-line tool would show you when something funny is going on. I was scratching my head for an hour, wondering why, when PHP loaded $_SESSION from my database, it seemed to ignore one of the object members. A private member in fact. Here's what I saw:

mysql> select * from sessions where data <> '';
+-----+----------------------------------------------------------------------------------------+-----------+
| id  | data                                                                                   | last_used |
+-----+----------------------------------------------------------------------------------------+-----------+
| foo | user|O:4:"User":2:{s:11:" User email";s:18:"dev@bpj-code.co.za";s:8:"verified";b:1;}   | NULL      |
+-----+----------------------------------------------------------------------------------------+-----------+

See those gaps around 'User'? Those aren't spaces! (And nor are they tabs.) They are, in fact, NUL characters:

Note:
Object's private members have the class name prepended to the member name; protected members have a '*' prepended to the member name. These prepended values have null bytes on either side.
 Why did this matter? Because I had made a change to the web pages that would need the serialized User object to have an id member, and it seemed easier to hand-hack the database's 3 entries in the sessions table than to write a ream of backwards-compatibility code that would conjure up the right id at the right time, when needed. "Easy!" I thought. "Not on your chinny-chin-chin," the computer replied:

mysql> update sessions set data = 'user|O:4:"User":3:{s:11:" User email";s:18:"dev@bpj-code.co.za";s:8:"verified";b:1;s:2:"id";s:2:"16";}' where id = 'foo';
Query OK, 1 row affected (0.00 sec)

Looks encouraging! Refresh page and check results:

mysql> select * from sessions where data <> '';
+-----+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------+
| id  | data                                                                                                                                                                      | last_used           |
+-----+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------+
| foo | user|O:4:"User":5:{s:11:" User email";N;s:8:"verified";b:1;s:11:" User email";s:18:"dev@bpj-code.co.za";s:2:"id";s:2:"16";s:11:"permissions";s:19:"9223372036854775807";} | 2012-07-09 03:22:41 |
+-----+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------+

Blast! What's going on here? Like I wrote above: those weren't NULs. Let's try again:

mysql> update sessions set data = 'user|O:4:"User":3:{s:11:"\0User\0email";s:18:"dev@bpj-code.co.za";s:8:"verified";b:1;s:2:"id";s:2:"16";}' where id = 'foo';
Query OK, 1 row affected (0.00 sec)

That change sticks! I guess it's too much to ask to have both tabular output and escaping of special characters?

Saturday 12 May 2012

OpenStreetMap for BVE routes

A.S. It looks like OpenBVE's Michelle has exited the stage in just the last few days. I doubt the whole back story is public yet, but let's say thanks and wish her well for whatever she's up to now. Still, this means that the OpenBVE community is in a bit of turmoil now. Who takes on the work now? I hope reason prevails and this "only serious developers need apply" / "we don't need outside interference" elitist attitude, expressed on the BVEStation forum, dies quickly. We really don't need another cathedral vs bazaar experiment now - the bazaar has clearly won. Now where is the OpenBVE git repository?

I would like to be able to drive the local suburban train, a Metrorail 5M2A, from Cape Town station to Simons Town. Especially the latter half of the route would be picturesque.

It's painstaking work to write up a BVE route by hand. A route is organized in fixed-length blocks, typically 25m, and "things happen" at the boundaries between these blocks: curve radius changes, cant changes, station starts and stops. Directly measuring curve radii and adding those to the route will result in a route that has roughly the correct shape, but it will be difficult to get the route to line up exactly with the modelled territory. Here's an example of this divergence you get without feedback:

That's a part of Cape Town - the so-called "City Bowl". The route that veers off westwards is one I originally wrote by eye-stimating distances and curve radii from satellite imagery retrieved from a certain very popular online mapping service. You can see that the route has roughly the right shape, but relatively small errors in distances and curve radius make it diverge from where it should be.

To get the route exactly coincident on the modelled territory, I decided to compare the route map with OpenStreetMap data. The OSM data of my city is well tagged, so it was easy to teach PHP to pick out railway=rail "way"s and draw them on a PDF. Just because it was easy, and seemed like it would be pretty, I also made it draw other ways in the lightest grey that is still visible.

Future directions?

It's still painful to have to fiddle the curve radii, segment by segment, until the route exactly coincides with the background map. It should be possible to use the extant way data to generate a whole run of track, interrupted only by the random breaks in data from the OSM contributors. Perhaps I should make a command-line tool that generates a route "skeleton", by accepting a list of way IDs and gluing them together with some curve-fitting trigonometry.

As an extension of such way-gluing, it could be useful (if not perfect) to transform road ways into asphalt road surface objects, perhaps some generic kerbs and road markings as decorations. OSM data is probably too sparse to be able to infer a whole lot of building objects, but even just a few scattered ones might already make the route a lot more fun to drive.

Apparently the XML export format is deprecated, and there is a "better" format, a binary one. I didn't feel like reading up on the binary format, and just wanted something that worked now. The benefits of using the binary format include being able to export larger areas and future-proofing (for when XML goes away).

Copyright

You should carefully consider whether using OSM data as a template against which to align your route makes your route a derivative work of the OSM data. On the one hand, tracing a map seems like the sort of thing that passes the "derivative work" test, and on the other, facts aren't necessarily copyrightable. I don't know which side is more persuasive to me, so for my own routes I will assume that my route is a derived work, and release them under a license compatible with that of OpenStreetMap data. You could do that too if you don't want to think too hard about it.

P.S. Until there's an "official" project repository, you could do worse than cloning Debian's Alioth repository:
git clone git://anonscm.debian.org/pkg-cli-apps/packages/openbve.git

Wednesday 18 April 2012

FFT of shortwave radio

Fourier transforms are a bit magical, and I've never permanently grokked any of the FFT algorithms. No matter, FFTW will just apply them for me. The result is this: my FFTW client utility. (Remember to link against libfftw3 when building it.)

A few nights ago I had the shortwave receiver on, and there was someone working another station I didn't hear. Eager to test my little Fourier transform utility, I captured some audio from my laptop microphone and fed it into the FFT. At one point the signal consisted of a long run of "dit"s, which is makes the audio signal quite spectrally pure. Here's a part of the result, featuring that stream of dits:


The audio carrier is visible at about 1002Hz, and then a number of sidebands each side, showing how the carrier is modulated with dits running at about six every second. Since the signal itself was pretty clean, a number of odd-numbered harmonics are also visible: the 3rd, 5th, and beyond, depending on your standards of evidence. This reflects a square wave's spectrum: odd harmonics only.

Pop quiz: does the human ear work in the time domain or frequency domain?

Tuesday 28 February 2012

Tricking GCC into TCO

Recursion is good. Recursion is bad. It's good for expressing algorithms clearly, but sometimes it's bad when the machine starts a new stack frame instead of just jumping to near the start of the recursing function.

Can you see the difference between



int collinear(int a_0, int a_1, int b_0, int b_1)
{
        printf("%d/%d %d/%d\n", a_0, a_1, b_0, b_1);
        if (a_1 == 0 || b_1 == 0) {
                return a_1 == b_1;
        }
        return (a_0/a_1 == b_0/b_1 && collinear(a_1, a_0%a_1, b_1, b_0%b_1));
}

and

int collinear(int a_0, int a_1, int b_0, int b_1)
{
        printf("%d/%d %d/%d\n", a_0, a_1, b_0, b_1);
        if (a_1 == 0 || b_1 == 0) {
                return a_1 == b_1;
        }
        return (a_0/a_1 == b_0/b_1 ? collinear(a_1, a_0%a_1, b_1, b_0%b_1) : 0);
}

? GCC emits a call instruction for the former, and the desired jmp instruction for the latter.

It looks like GCC (my copy identifies itself as "gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5") can't reason through the logical AND to conclude that all terminating returns from collinear already return a boolean value. I'll probably keep the logical AND as it seems to express the intent of the test more clearly, and in my application, the recursion will terminate quickly anyway. I think the worst case is O(log n) recursions.

(FWIW this relates to my question on StackOverflow; I'm hacking on my gEDA fork and I need to determine if an endpoint of one net connects to another, both of which may be diagonal.)