Looking for dctrl-tools testcases

If you use grep-dctrl, sort-dctrl or tbl-dctrl, I’d like to see your use cases! I’m building a system test automaton for dctrl-tools, and I’d like to include as much real-world examples as possible so that any regressions get found before uploading.

You can send example command lines (and preferably also a test file, unless it’s one of the standard Debian files like Packages) to me by email at <ajk@debian.org>, as a wishlist bug report against dctrl-tools or by a Darcs patch against the experimental repository (see instructions).

Announcing darcs-monitor

There aren’t many features I grew fond of with CVS that I haven’t yet found a satisfactory solution for in Darcs. One of them was, until today, sending commit mails to mailing lists. There are a number of more or less ugly hacks floating around the net, but I never found them very satisfactory, so I wrote my own.

Darcs-monitor will send email to a specified recipient about new changes added to a specific darcs repository. It can be run as an apply posthook (resulting in near-instantaneous “push” emails), or periodically from Cron, or occasionally by hand, whatever seems most convenient.

You can get it by darcs at http://antti-juhani.kaijanaho.fi/darcs/darcs-monitor/ (darcsweb available), or as a tarball at http://antti-juhani.kaijanaho.fi/software/dist/. It depends on mtl and HaXml and is written in Haskell, naturally. It has been tested only with GHC 6.6 so far. For installation and usage instructions, refer to the README.

Please note that this software is very new and thus can be buggy. As with any email-sending software, bugs can result in major annoyance; user caution is warranted.

Introducing Quadmachine II

Quadmachine is a virtual instruction set architecture, designed mainly as a target for simple educational compilers. It has the following noteworthy features:

  • RISC design
  • word size 64 bits
  • address size 64 bits (theoretical maximum memory size 16 exabytes)
  • all memory access is in word units
  • 65534 general-purpose 64-bit registers
  • 2 additional special-purpose 64-bit registers
  • a variant of the “register windows” technique with automatic spilling

All of these, except for the preposterously large register file, are more or less realistic for a 64-bit RISC design. The size of the register file is intended to trivialize register allocation in compilers.

This is the second Quadmachine design. Main differences from the previous design are a move to a load-store RISC architecture and the upgrade of the word size to 64 bits.

There is a software realization of the Quadmachine architecture, with a graphical debug console. It is written in Java for portability; speed was not an implementation concern.

Read more

Dealing with multiple parallel sources of translations

I get translations for dctrl-tools from multiple sources: one translator has direct commit rights to my darcs repository, others bug me; still others use Rosetta (dctrl-tools upstream). On top of this, I just found out that there are active translators working on the Ubuntu branch of dctrl-tools in Rosetta. There have been several cases of different sources of translations having different parts of the programs translated, so it would make sense to combine them somehow.

Dear LazyWeb, how do I combine translations from all these sources?

Graph reduction

Graph reduction is the basic operational model of lazy functional programming. The idea is that the program is represented as a huge λ-term abstract syntax tree, and the program is executed by performing outermost-leftmost β-reductions to this tree, and whenever a subtree must be replaced by another tree (such as, when performing the substitution operation), the root node of the replacee is overwritten by the root node of the replacement (or a redirection node pointing to the replacement) instead of making copies (the body of an abstraction still needs to be copied, of course). The effect is the familiar laziness: when a function refers to its parameter more than once, the argument term is shared between the parameter references instead of making copies, and so any reduction in any one of them is shared by all of them.

For some strange reason, I decided I must write a set of C functions that demonstrate graph reduction. I wrote them, and then in order to test them I expanded them to become a complete implementation of λ-calculus (extended with integers) graph reduction. The program can be found here; it is written in portable ANSI–C. It is able to show the complete trace of reductions. It is intended for demonstrating the technique, and therefore is effectively a stupid interpreter and does not implement any of the sophisticated optimization techniques that industrial-strength functional language implementations routinely use.

Example usage:

$ cat examples/fib
TRUE = \t.\f.t
FALSE = \t.\f.f
IF = \x.x
ISNIL = \x. x TRUE
CONS = \car. \cdr. \x. IF x FALSE (\y. IF y car cdr)
CAR = \cell. cell FALSE TRUE
CDR = \cell. cell FALSE FALSE
MAP = \f. \xs. IF (ISNIL xs) NIL (CONS (f (CAR xs)) (MAP f (CDR xs)))
AT = \n. \xs. CAR (DROP n xs)
DROP = \n. \xs. IF (n = 0) xs (DROP (n - 1) (CDR xs))
TAKE = \n. \xs. IF (n = 0) NIL (CAR xs (TAKE (n - 1) (CDR xs)))
GENFIB = \pair. CONS (CDR pair) ((CAR pair) + (CDR pair))
FIB = \n. (CDR (AT n FIBS))
$ ./graph-reduction -t -S10K -H1M examples/fib
graph-reduction 1.0 by Antti-Juhani Kaijanaho, report bugs to antkaij@mit.jyu.fi
examples/fib> FIB 3
1 + (1 + (0 + (\f[4].f[4]) (\y[11].(\x[5].x[5]) y[11] 0 1) (\t[3].\f[4].f[4])))
1 + (1 + (0 + (\y[11].(\x[5].x[5]) y[11] 0 1) (\t[3].\f[4].f[4])))
1 + (1 + (0 + (\x[5].x[5]) (\t[3].\f[4].f[4]) 0 1))
1 + (1 + (0 + (\t[3].\f[4].f[4]) 0 1))
1 + (1 + (0 + (\f[4].f[4]) 1))
1 + (1 + (0 + 1))
1 + (1 + 1)
1 + 2

(In the trace output, each bound variable is annotated by a scope identifier that effectively allows me to ignore variable caputure problems.)

I plant to further extend the language to handle algebraic data types and simple pattern matching, to get rid of the noise of simulating these concepts in the traces.

Technically, perhaps the most interesting part of the program is that it contains a fully portable copying garbage collector.

Haskell responses for Eric Warmenhoven

Eric Warmenhoven asked a couple of Haskell questions. Here are my answers.

BTW, do you want to be added to Planet Haskell? If so, drop me an email.

Also, be sure to subscribe to the Haskell mailing lists.

Where did all the shared libraries go? Turning a Haskell module into a static library looks like it’s fairly straightforward, but it looks like it’s impossible to create a shared library that’s usable by other Haskell programs.

See the GHC FAQ.

Why do header files have a bizzare suffix? If module A uses something from module B and module B uses something from module A, there’s a circular dependency that GHC can’t resolve on its own. The solution to this is to create a “boot” copy of module A that defines the things that B depends on without depending on B. In C this is called a header file. In GHC this is called a boot file and is given the extension “.hs-boot”.

There are no header files with Haskell. Or rather, there are (the .hi files), but they are generated by the compiler when compiling the module. The .hs-boot files are not header files but a workaround for GHC’s inability to compile circularly dependent modules (which the language spec requires).

Why does everyone ignore all the practical stuff? I read through five tutorials before I finally found one (on Monads, of all things) that actually had a usable getArgs example.

Perhaps many people consider the practicals easy and want to discuss the hard things instead.

Where’s the Debian-specific documentation? For example, there’s a GTK module. Where is that? How do I get it? Is there a package for it? If not, how do I make one? (I saw the debian haskell mailing list but didn’t feel like wading through the archives hoping that one of my questions might be answered.)

There is no Debian-specific documentation apart from a draft “policy”.

Googling, I found this repository that contains Gtk2HS debs. Haven’t tried them, though.


To everybody’s amazement, I’ve today released a BASIC compiler.

Agora BASIC is a compiler for Standard Full BASIC. It doesn’t have any aspirations to become a trendy or “modern” BASIC: it’s goal in life is to implement the Full BASIC standard to the best of its ability. Some modest extensions making it possible to write useful programs are certainly in the cards, but no object system until the standard acquires one.

The initial release implements enough of the language to write simple programs; a lot remains to be done. Join us now and share the software! Err…

Check out the home page.

Mitä avoimet ohjelmat ovat?

(Tämä on aiemmin tänään pitämäni luennon käsikirjoitus. Itse luennossa käytin käsikirjoitusta vain tukena, en lukenut sitä ääneen. Valokuva: 40100.)

Hei vaan, ja tervetuloa tähän Yläkaupungin yöhön kuuluvaan Linux tutuksi -seminaariin, jonka järjestää Suomen Linux-käyttäjien yhdistyksen paikallisosasto. Minun nimeni on Antti-Juhani Kaijanaho, ja olen ollut avoimien ohjelmien ja Linuxin käyttäjä nyt jo kymmenen vuotta. Tämän esitelmän tarkoituksena on kertoa, mistä on kysymys, kun puhutaan avoimista ohjelmista.

Kerron aluksi pienen tarinan, joka perustuu tositapahtumiin. Sain kerran, noin viisitoista vuotta sitten, synttärilahjaksi ohjelman, juuri sellaisen kuin halusin. Sillä ei liene väliä, mitä sillä tarkkaan ottaen tehtiin, sanotaan vain, että sen avulla saatoin alkaa toteuttaa itseäni taiteellisesti. Harjoittelin ohjelman käyttöä pitkään, ja teinpä muutaman käyttökelpoisenkin tuotoksen. Eräänä päivänä aloin tehdä erittäin haasteellista teosta, haasteellista ainakin omien silloisten taitojeni kannalta. Tiedättekö, mitä tapahtui? Ohjelmasta löytyi virhe, enkä päässyt siitä yli enkä ympäri.

Ohjelman valmistajan nimi sattui olemaan Microsoft. Ohjelman käsikirjassa kehoitettiin lähettämään palautetta tiettyyn osoitteeseen. Minä lähetin. En ole vieläkään saanut vastausta. Siitä on tosiaan jo viisitoista vuotta.

Tarinallani on opetus. Mitä teet, kun käyttämäsi ohjelman valmistaja lopettaa ohjelman tukemisen ja siirtyy paremmille metsästysmaille, joko uusien tuotteiden pariin tai, vieläkin pahempaa, lopettaa kokonaan toimintansa?

Kerronpa toisenkin tarinan. Tämä tapahtui yli kaksikymmentä vuotta sitten Amerikan Yhdysvalloissa, Massachusettsin teknillisen korkeakoulun eli MIT:n tekoälylaboratoriossa. Eräänä päivänä heiltä hajosi laboratorion tulostimen ohjausohjelma. Toisin kuin minä viisitoista vuotta sitten, tekoälylaboratorion työntekijät olivat kokeneita ohjelmoijia. Taitoa siis kyllä olisi löytynyt vian korjaamiseen, mutta ohjelman valmistaja kielsi. Tiedättehän, ohjelmaan sai laillisesti koskea vain sen valmistaja. Tietääkseni valmistaja ei pyynnöistä huolimatta koskaan korjannut vikaa. Tekoälylaboratoriossa jouduttiin tyytymään rampaan tulostusjärjestelmään.

Kuinka moni teistä on koskaan elämänsä aikana tieten tahtoen asentanut tietokoneeseensa tai muuten tietoisesti käyttänyt laittomia ohjelmia?

Heh. Suurin osa teistä valehtelee, mutta annetaan sen olla. Lautamiehenä tiedän, että ihmisellä on oikeus olla avustamatta rikostensa selvittämisessä.

Lienee aika tavallinen tarina, että naapurilta lainataan Wordin romppu ja asennetaan omaan koneeseen. Kenties naapurikin oli omansa kopioinut jonkun tuttunsa rompusta. Tällainen toiminta on erittäin yleistä ruohonjuuritasolla. Jostakin syystä media, suuret yhtiöt ja monet poliitikot ovat nähneet parhaaksi antaa tälle toiminnalle nimen, jonka historiasta löydämme murhia, raiskauksia ja muuta iljettävää toimintaa: piratismi eli merirosvous.

Muuten, viime syksynä törmäsin uutiseen Somalian rannikolla tapahtuneesta välikohtauksesta. Matkustajalaivaa oli uhannut joukko merirosvoja. Vain laivan päällikön neuvokkuus pelasti matkustajat ja laivan tuholta. Toisessa uutisessa kerrottiin, että Somaliaan ei enää uskallettu lähettää avustuskuormia, sillä niiden perillepääsy ei ollut enää kovin varmaa, sillä merirosvoja oli reitin varrella yllin kyllin.

Minä haluan olla lainkuuliainen kansalainen. Toisaalta olen tietokonenörtti. Lapsuudessani ja nuoruudessani 1980-luvulla ja pitkälle 1990-lukua elin niukkuudessa. Ruokaa oli kyllä enemmän kuin tarpeeksi, mutta tietokoneohjelmia saatiin yksi tai kaksi vuodessa. Ei ihme, sillä halvimmatkin ohjelmat, joista tiesimme, maksoivat tuhansia markkoja. Tuolla rahalla oli lapsuuden-taloudessani runsaasti muutakin käyttöä.

Kymmenkunta vuotta sitten kuuli tämä tamperelainen lukiolainen uudesta ihmeestä, Internetistä. Aluksi pummasin kaverin yhteyttä, sitten aloin käyttää kirjaston koneita. Löysin uusia, omituisia ajatuksia. Löysin kymmenittäin ohjelmia, joista ei tarvinnut maksaa mitään, sen kun latasi omalle koneelleen. Ohjelmien mukana tuli kirjoituksia, jotka herättivät ajatuksia tässä lukiolaisessa. Joku Richard Stallman -niminen kaveri kirjoitti pitkälti samanlaisista asioista, joista olen teille nyt kertonut – Stallman oli ollut yksi tekoälylaboratorion työntekijöistä tulostinjupakan aikaan. Hän ei ole kovin kuuluisa nörttipiirien ulkopuolella, mutta on pitkälti hänen ansiotaan, että on olemassa vaihtoehto.

Stallmanin vaihtoehdon ansiosta minä olen lainkuuliainen enkä silti kärsi tietokoneohjelmien niukkuudesta. Nykyisin ongelmanani on, jos mikään, niin runsaudenpula.

Stallman aloitti 1980-luvun puolivälissä projektin, jonka tarkoituksena oli luoda ohjelmia, joita nämä ongelmat eivät koske. Hänen tarkoituksenaan oli luoda kokonainen käyttöjärjestelmä ja siinä toimivat hyötyohjelmat, jotka olisivat vapaasti käytettävissä ja muokattavissa. Hän antoi järjestelmälleen nimeksi GNU.

Vuonna 1991 GNU oli lähes valmis. Puuttui vain käyttöjärjestelmän ydin, se osa, jota pidettiin kaikkein haasteellisimpana. Samaan aikaan Helsingin yliopistossa alkoi leikkiä uudella PC:llään opiskelija nimeltään Linus Torvalds. Hän ei kuulunut GNU-projektiin, vaan hän alkoi rakentaa omaa käyttöjärjestelmän ydintään lähinnä kaiketi opiskelutarkoituksessa – niin, ja hauskanpitotarkoituksessa. Meillä nörteillä on omalaatuinen käsitys siitä, mikä on hauskaa.

Linusin ytimen, jota alettiin kutsua Linuxiksi, ympärille oli suhteellisen helppo koota muilta osin täysin valmis GNU. Tämän kokonaisuuden pohjalta syntyi useita ns. jakelupaketteja, joissa rosoiset kulmat on viilattu pyöreiksi ja pinnat on maalattu tai lakattu kauniisti. Tunnettuja jakelupaketteja ovat Red Hat, Fedora, Ubuntu ja Debian. Itse olen kuulunut Debianin kehittäjäjoukkoon vuodesta 1999.

Pohjimmiltaan kyse on lähes vallankumouksellisesta ajatuksesta, että tietokoneohjelmien kuuluisi olla vapaita. Puhumme sananvapaudesta, mutta nykyisin pitäisi puhua myös ohjelmistonvapaudesta. Richard Stallman puhuu neljästä keskeisestä vapaudesta, voidaan varmaankin puhua Stallmanin teeseistä:

Ensiksi: Ihmisen tulee olla vapaa käyttämään tietokoneohjelmaa mihin tahansa tarkoitukseen.

Toiseksi: Ihmisen tulee olla vapaa muokkaamaan ja korjaamaan ohjelmaa, jotta se täyttäisi hänen tarpeensa.

Kolmanneksi: Ihmisen tulee olla vapaa levittämään ohjelmaa eteenpäin maksutta sekä halutessaan myös maksua vastaan.

Neljänneksi: Ihmisen tulee olla vapaa levittämään muutettuja versioita ohjelmasta, jotta koko yhteisö hyötyisi muutoksista.

Stallmanille ja hänen seuraajilleen kyse on olennaisesti ohjelmoijan etiikasta. Siinä missä perinteinen ohjelmistoteollisuus rinnastaa ohjelmien laittoman vapaan käytön merirosvouteen, rinnastavat Stallman ja kumppanit perinteisen ohjelmistoteollisuuden hamstraukseen. Onhan nimittäin niin, että kun ohjelma on luotu, se on uniiikki, yksilöllinen, eikä samanlaista toista ole; onko siis kovin kaukaa haettua syyttää sitä, joka haluaa omia ohjelman omakseen, samanlaisesta rikoksesta kuin sitä, joka piilottaa nälänhädän tullen ruokaa vain omaan käyttöönsä – ja armollisesti myy sitä kiskurihintaan muille?

On olemassa toinenkin koulukunta, jota voitaneen luonnehtia Linus Torvaldsin innoittamaksi. Heille vapaat ohjelmat ovat käytännön kysymys, ja puhe etiikasta saa heidät noloksi, jos hyvin käy. Huonommassa tapauksessa voi syntyä riitaa. Heille nimenomaan kyse ei ole etiikasta.

Torvaldsin koulukunnalle vapaissa ohjelmissa, tai käyttääkseni heidän suosimaansa termiä, avoimen lähdekoodin ohjelmissa eli avoimissa ohjelmissa, kyse on sosiaalisesta sopimuksesta, joka mahdollistaa uudenlaiset ohjelmankehityskäytänteet. Koska ohjelmaa saa kuka tahansa muokata ja muokkauksensa julkistaa, löytyy ohjelmille parhaimmillaan tuhansia kehittäjiä. He panevat kortensa yhteiseen kekoon omien tarkoitusperiensä vuoksi. Yksittäisen kehittäjän työpanos voi olla melko vaatimatonkin, mutta kun kehittäjiä on paljon, työ etenee.

Avoimet ohjelmat ovat usein laadukkaampia kuin perinteisesti tuotetut ohjelmat. Isot, aktiiviset avoimet ohjelmistoprojektit pystyvät käyttämään ohjelmankehitykseen paljon enemmän työaikaa kuin useimmat ohjelmistotalot. On päivänselvää, että kun kehittäjiä on runsaasti, joukosta löytyy usein joku, jonka on helppo korjata kulloinkin tarkasteltavana oleva vika.

Avoimilla ohjelmilla on sekin etu, että ohjelman käyttäjä ei ole koskaan sidottu yhteen toimittajaan. Jos jostain syystä käy niin, että kukaan ohjelman kehittäjistä ei ole kiinnostunut korjaamaan jotain tiettyä vikaa tai lisäämään jotain pyydettyä ominaisuutta, ei tarinan tarvitse päättyä siihen. Jos ohjelman käyttäjä on itse taitava ohjelmoija, hän voi liittyä ohjelman kehitystiimiin ja tehdä ohjelmasta sellaisen, millaisen siitä itselleen haluaa. Jos ei itse ole ohjelmoija, on täysin mahdollista ja laillista ostaa tämä palvelu joltakulta. Maailmalla on runsaasti konsultteja ja yrityksiä, jotka tarjoavat tällaisia palveluita. Suomessa niitä on vähemmän, mutta varmasti kysynnän kasvaessa tarjontakin kasvaa.

Avoimet ohjelmat ovat myös perinteisiä ohjelmia sivistävämpiä. Varsinkin lasten ja nuorten käyttöön avoimet ohjelmat ovat erityisen suositeltavia. Niissä nimittäin on mahdollista kurkistaa niin sanoakseni pellin alle, mitä ohjelma on syönyt. Tällä tavalla nuori oppii paitsi käyttämään myös hallitsemaan tietotekniikkaa eikä vain pinnallisesti vaan, mikäli hänessä on siihen taipumusta, myös syvällisesti.

Millä sitten ohjelmoijat elävät, jos ohjelmia saa ladata netistä ilmaiseksi?

Selvää on, että tällaisessa tilanteessa ohjelmistotyömarkkinat eivät kasva niin suuriksi kuin perinteisen ohjelmistoalan puitteissa, koska hinnosta katoaa keinotekoisten monopolien aiheuttamaa ilmaa. Mutta onko tämä huono asia? Kumpi on tärkeämpää, se että ohjelmoijat rikastuvat vai se, että ihmiskunnalla on tarvitsemansa ohjelmat?

Ohjelmoijat elävät ohjelmoimisesta. He saavat siitä asianmukaisen palkan ja sitten siirtyvät seuraavaan projektiin. Vapaiden ohjelmien vallitessa ohjelmoija muistuttaa enemmän arkkitehtia, joka suunnittelee talon, saa siitä maksun ja sitten siirtyy suunnittelemaan seuraavaa taloa, kuin jotain rytsölän veljestä.

Saattaa myös herätä kysymys, että mitenkäs ohjelmoijia motivoidaan töihin, jos äkkirikastuminen ei ole kiikarissa. Tähän on helppo vastata. Valtaosa ohjelmoijista tekevät sitä ihan muista syistä kuin rahasta. Tavallisesti ohjelmoija on iloinen siitä, että hänelle maksetaan sellaisesta, jota hän tekisi ilmaiseksikin.

No mistä sitä rahaa tulee, josta ohjelmoija palkkansa saa, jos sitä ei ohjelman myynnistä tule?

Ne, jotka ohjelmointityötä tarvitsevat, maksavat siitä käyvän hinnan. Voisin kuvitella, että hiljalleen syntyvät todelliset ohjelmointityön markkinat, joissa samasta korjauksesta tai uudesta ominaisuudesta kiinnostuvat tahot lyövät rahansa yhteen ja maksavat yhdessä ohjelmoijalle tämän työstä; jonkinlainen ohjelmointityön pörssi siis. Joitakin ohjelmointitöitä on syytä lisäksi rahoittaa verorahoilla.

Joku saattaisi vielä ihmetellä, että millä vapaiden ohjelmien kehittäjät elävät nyt, kun ohjelmointityön pörssiä ei vielä ole. Käytännössä monet vapaita ohjelmia kehittävät ohjelmoijat tekevät tätä työtä harrastuksena, eräänlaisena kolmannen sektorin työnä. Osa tekee vapaita ohjelmia vapaista ohjelmista riippuvien yritysten palkkalistoilla. Jotkut ovat itsenäisiä konsultteja. Tarinoita on paljon.

Minulle vapaat ohjelmat ovat vapautus niukkuudesta ja keino pysyä silti lainkuuliaisena. Minä olen ohjelmoijana sitoutunut laatimaan parhaan kykyni mukaan laadukkaita ohjelmia, joita en hamstraa enkä kahlitse.

Naapurihuoneessa on esittelypöytiä eri aiheista, ja tässä salissa alkaa kello puoli kolme seuraava esitelmä, jossa neuvotaan Linuxin käytön alkeet. Nyt meillä on aikaa keskustella tässä, ja minä olen myös paikalla koko päivän tuossa naapurihuoneessa.

Vapauttakaa itsenne kahleista ja tutustukaa vapaisiin ohjelmiin tämän seminaarin aikana!

Creative Commons License
The text of this blog entry is licensed under a Creative Commons Public Domain License.