Hackety hack hack

Atypisches Nutzerverhalten mit Rat und Tat.

Autovivication in Python

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.

Fred BrooksThe Mythical Man-Month: Essays on Software Engineering

Datenstrukturen sind Magie. In einer magischen, fast vergessenen Sprache wie Perl sind sie sogar noch ein bisschen magischer, um nicht zu sagen: frankensteinhaft. Die Rede ist von Autovivication.

Wenn ich einen langen komplexen Pfad in meinem Dateisystem anlege, der ein Directory in einem noch zu erstellenden Directory erstellt, möchte mein Unix-System nichts davon wissen:

[~]$ mkdir a/b/c
mkdir: a/b: No such file or directory

Frankenstein's monster (Boris Karloff) In anderen Betriebssystemen wäre das anders. Die fehlenden, implizit genannten Schachtelungen, würden automatisch erzeugt. Wie von Geisterhand würden sie ins Leben gerufen werden. Es lebt! Ergänzung: Ganz richtig in den Kommentaren bemerkt: mkdir -p a/b/c bringt unter Unix natürlich auch das erwünschte Ergebnis.

Autovivication ist je nach Erwartungshaltung an die Programmiersprache eine überraschende oder logische Eigenschaft von verschachelten Datentypen wie Hashes in Perl, die auch als assoziative Arrays oder in Python-Lingo als Dictionaries bekannt sind. Wenn ich ein Elemente zuweise oder abfrage, das in einem anderen Element geschachtelt ist, das ich bisher noch nicht belegt habe, wird das implizit benannte Element der höheren Schachtelungstiefe automisch angelegt oder eben belebt.

Die automatische Belebung hilft zum Beispiel, wenn ich mit einem Klumpen an Daten arbeite, vielleicht aus einer Open-Data-Quelle wie der Liste der als Naturdenkmale geschützte Findlinge in Charlottenburg-Wilmersdorf oder einer Abfrage bei Wikidata. In dem Klumpen können diverse Verschachtelungstiefen bestehen, ohne dass ich die dahinterstehende Struktur im Detail kenne oder kennen möchte. Wenn ich die Struktur naiv in ein assoziatives Array hineinschlürfe, geht das mit Perl, in anderen Sprachen würde ich höflich, aber bestimmt darauf hingewiesen werden, dass ich einem noch nicht definierten Key einen Wert zuweisen will und das Programm stürzt typischerweise ab. Besonders drollig stellt sich hier PHP mit einem Verhalten an, das als Pseudo-Autovivication bezeichnet werden könnte: Zuweisungen an noch nicht vorher definierte Keys beliebiger Schachtelungstiefe gehen (wie in Perl), Abfragen von nicht definierten Keys gehen nicht (wie in anderen Sprachen).

Schauen wir uns doch mal Autovivication in Perl an:

Autovivication in Perl
 
 
 
 
 
 
 
 
#!/usr/bin/perl -w

use strict;
use Data::Dumper;

my %data;
$data{1}{2}{3} = 10;
print Dumper(%data);

Das CPAN-Modul Data::Dumper ist möglicherweise vorher noch mit cpan install Data::Dumper zu installieren, bevor es benutzt werden kann. Es dient einfach dazu, eine Datenstruktur in Perl zu inspizieren oder formatiert auszugeben. Mit my %data; definieren wir ein assoziatives Array (Hash) namens data. $data{1}{2}{3} = 10; weist diesem Hash den Wert 10 zu für den Key 3, der in einem Hash mit dem Key 2 steckt, das wiederum in dem Hash-Key 1 von data steckt. Für diejenigen, die in der schwarzen Magie von Perl nicht (mehr) so bewandert sind: Bei der Zuweisung wird aus dem Hash-Vorzeichen % ein $, weil die Variable hier in einem skalaren Kontext benutzt wird.

Die Ausgabe ergibt dann:

$VAR1 = '1';
$VAR2 = {
          '2' => {
                   '3' => 10
                 }
        };

In Python wäre der entsprechende Code nicht möglich und würde mit einem Fehler abbrechen:

>>> data = {}
>>> data[1][2][3] = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 1

Da für die Keys der höheren Schachtelungstiefe noch nichts angelegt wurde, wird die Ausnahme KeyError geworfen und das Programm beendet.

In seiner Standard-Library hat Python allerdings im Modul collections auch den Datentyp defaultdict. Gedacht ist er dafür, um Dictionaries zu erzeugen, bei denen ein Defaultwert schon vorgegeben ist — wenn der Wert nicht definiert ist, soll zum Beispiel standardmäßig 0 als Wert angelegt werden.

Indem wir defaultdict auf leicht kreative Weise mißbrauchen, können wir Autovivication in Python bekommen. Was wäre, wenn wir die Datenstruktur rekursiv definieren und als Defaultwert eine Funktionsreferenz auf eine die Datenstruktur selbst erzeugende Funktion angeben?

Wenn sich die leichte Verwirrung im Kopf über den letzten Satz und rekursiv definierte Datenstrukturen gelegt haben, können wir uns diese Lösung auch mal einfach ansehen:

Autovivication in Python
 
 
 
 
from collections import defaultdict
AutovivicationDict = lambda: defaultdict(AutovivicationDict)
data = AutovivicationDict()
data[1][2][3] = 10

Hurra, Python kann jetzt Autovivication! Allerdings sind die auf diese Weise erzeugten Dictionaries immer noch ziemlich besonders. Wir können (in beliebiger Schachtelungstiefe) zuweisen und abfragen, aber dass es kein herkömmliches Dictionary ist, stellen wir fest, wenn wir es uns einmal ansehen:

>>> data
defaultdict(<function <lambda> at 0x10a774938>, {1: defaultdict(<function <lambda> at 0x10a774938>, {2: defaultdict(<function <lambda> at 0x10a774938>, {3: 10})})})

Huch, da ist ja alles voller Referenzen auf eine anonyme Funktion! Für die meisten Anwendungen sollte das keinen Unterschied machen, mit welchem Wert das defaultdict gefüllt wird. Wenn wir allerdings eine Umwandlung unseres speziellen autovivizierten Dictionaries in ein herkömmliches Dictionary brauchen (etwa, um daraus JSON zu machen), brauchen wir noch eine Umwandlungsfunktion. Weil wir gerade so schön im Flow sind, definieren wir diese auch wieder rekursiv und unter Einsatz von lambda:

dictify
 
dictify = lambda dd: {k:dictify(v) for k,v in dd.items()} if isinstance(dd, defaultdict) else dd

Und jetzt haben wir hier ein ganz normales Dictionary:

>>> dictify(data)
{1: {2: {3: 10}}}

Wie bereits eingangs erwähnt: Datenstrukturen sind magisch.