Blackflash

Linktipps Mai 2010

Blackflash — Sun, 02 May 2010 06:02:00 +0200

Should web developers say no to cookie-based authentication?: Was sind bei der Authentifizierung die Alternativen zu Cookies und sollte man diese den Cookies vorziehen? Zwar sollte diese Frage jeder f�r sich selbst beantworten, aber ich finde, dass dieser Artikel einige Denkanst��e gibt.
A Partial Ordering of some Category Theory applied to Haskell: Aufgrund des gro�en Interesses an kategorientheoretischen Anwendungen in Haskell hat Dan Piponi eine Sammlung seiner Artikel, die sich mit Kategorientheorie besch�ftigen, zusammengestellt.
DevOps at dealnews.com: Brian Moon plaudert aus dem N�hk�stchen �ber das Deployment bei dealnews.com.
On powersets and folds: Wer gerne cleveren Haskell-Code liest, der ist bei diesem Artikel gut aufgehoben.
Haskell anti-pattern: incremental ad-hoc parameter abstraction: Wie abstrahiert man am besten von einer Vielzahl von Parametern? Brent Yorgey beschreibt die L�sung: Records mit Data.Default.
File Recovery with Haskell: Neil Mitchell beweist, wie einfach man ein n�tzliches Werkzeug in Haskell schreiben kann: Korrupte Dateien m�glichst vollst�ndig kopieren.
You could have invented zippers: In Anspielung auf Dan Piponis You could have invented monads beschreibt Edward Z. Yang die Zipper-Datenstruktur unter Zuhilfenahme einiger Illustrationen.
Trait-like Functionality for PHP: Wer keine Lust hat, auf Traits in PHP zu warten, der wird diesen Artikel interessant finden, da er etwas, was Traits sehr �hnlich ist, anhand von PHPs Metaprogrammierung entwickelt.
CouchDB - Document Persistence Powered by CQRS: F�r welche Zwecke ist CouchDB trotz der Vorteile nicht geeignet? Dieser Artikel schneidet das Thema an.
The Maximum Segment Sum Problem: Its Origin, and a Derivation: Shin-Cheng Mu zeigt, wie man einen Linearzeitalgorithmus aus einer Problemstellung fast mechanisch ableiten kann.
Generational garbage collection and floating garbage: Johan Tibell kl�rt �ber einige Aspekte der Garbage Collection (des GHC) auf und erl�utert, wie man diesen Prozess optimieren kann. F�r jeden, der mehr �ber die Funktionsweise des GHC lernen will, ist dieser Artikel empfehlenswert.
Revenge of the Nerds: Paul Graham erl�utert vor allem die Ausdrucksf�higkeit verschiedener Programmiersprachen und die daraus folgenden Konsequenzen. Jeder, der Software schreibt, sollte sich diesen Artikel durchlesen!
NoSQL is About?: Worum geht es beim vielfach erw�hnten NoSQL? Jan Lehnhardt kl�rt diese Frage mit einem einfachen Satz: Bei NoSQL geht es um Auswahl. Wer diesen Satz verstehen m�chte, sollte unbedingt seinen Artikel lesen.
Programming with effects - the story so far: Jeder Haskellentwickler kennt Monaden, aber es gibt noch allgemeinere Konzepte, die sich mit Seiteneffekten befassen. Patai Gergely hat dazu ein anschauliches Diagramm angefertigt und erkl�rt die im Diagramm dargestellten Beziehungen.
Inessential Guide to data-accessor: Wer die nativen Haskell-Records unsch�n findet, der sollte sich diesen Artikel durchlesen, denn er gibt eine sch�ne Zusammenfassung �ber die data-accessor-Bibliothek.
cabal init: Ein Muss f�r jeden angehenden Haskellentwickler.
Direct and Indirect Effects of TDD: Neben den Effekten von testgetriebener Entwicklung bietet dieser Artikel auch einen allgemeinen Einblick in die Softwareentwicklung.
Moral obligations of Free Software authors?: Ist man als Autor freier Software moralisch verpflichtet, die Verantwortung f�r sein Projekt zu behalten, wenn diese Aufgabe niemand aus der Community �bernimmt? John Goerzen schildert dieses Dilemma aus seiner Sicht. Auch lesenswert sind die unterschiedlichen Meinungen in den Kommentaren.
Find your Files: Fabien Potencier stellt die Symfony Finder-Komponente vor, die mir durchaus gelungen erscheint.
Creative catamorphisms: Edward Z. Yang erl�utert kurz den Begriff Catamorphismus, um kreative Catamorphismen mit Bezug auf Guy Steeles Pr�sentation zu beschreiben.
The Problem with xUnit: Warum sind Unit-Tests suboptimal? Edward Z. Yang spricht mir mit diesem Artikel aus der Seele.
7 Reasons To Hate Your Code: Sieben Gr�nde, den eigenen Code zu hassen? Teils humorvoll, teils ernsthaft begr�ndet, gibt der Autor Aufschluss, warum guter Code nicht alles ist.

Linktipps April 2010

Blackflash — Thu, 01 Apr 2010 09:07:00 +0200

Evolving Faster Haskell Programs (now with LLVM!): Mit genetischen Algorithmen die Geschwindigkeit eines Haskell-Programms verbessern? Don Stewart zeigt, wie er es geschafft hat.
Try Haskell!: Ein interaktives Tutorial in grundlegende Sprachkonzepte von Haskell. Sehr sch�n, wenn man mal ein wenig ausprobieren m�chte, ohne viel lesen zu m�ssen. Letztendlich kann dieses interaktive Tutorial aber nur einen kleinen Vorgeschmack geben.
BSON - Binary JSON: Diese Webseite enth�lt sowohl Spezifikationen als auch weitere Informationen zum bin�ren JSON-Format, wie es von MongoDB verwendet wird.
The Categorification of the Naturals: Auf Typlevel wird anhand der Peano-Arithmetik ein Isomorphismus zwischen nat�rlichen Zahlen und Typen entwickelt. Sehr lesenswert f�r all jene, die von der M�chtigkeit der Typen in Haskell begeistert sind.
Programming with impossible functions, or how to get along without monads.: Pure Funktionen und IO passen nicht zusammen? sigfpe zeigt das Gegenteil.
Python�s lambda is broken!: Manchmal f�hrt auch aussagekr�ftiger Code zu unerwarteten Ergebnissen - wie hier in Python.
On programming language design: Programmierer werden jeden Fehler machen, den sie machen k�nnen. Deshalb sollten Programmiersprachen einen guten Entwurf vorzuweisen haben. Die popul�rsten Fehler werden in diesem Artikel vorgestellt, mitsamt Beispielen wie auch L�sungen in verschiedenen Sprachen.
checkMyCode.org: Wer seinen in C geschriebenen Code �berpr�fen lassen will, kann dies mit der genannten Webapplikation tun. Als Basis daf�r dienen ca. 16 Millionen Regeln, die aus 200 Millionen Zeilen Code von Linux-Programmen extrahiert wurden.
Where do monads come from?: sigfpe kl�rt �ber Zusammenh�nge zwischen Berechnungen, Algebren und Monaden auf - sehr lesenswert f�r Interessenten der Theorie.
Being an expert considered harmful: Die Schattenseiten des Expertentums... Man sollte sich immer wieder daran erinnern lassen.
Neural Networks in PHP: K�nstliche neuronale Netze und PHP? Anscheinend ist es doch kein Widerspruch, was dieser interessante Artikel beweist.
Synchronous Channels using MVars: Effiziente Synchronisierung in Haskell. F�r jeden, der parallel und beil�ufig mit Haskell arbeiten will, bietet der Artikel eine sehr gute Strategie sowie interessantes Hintergrundwissen.
Brewer's CAP Theorem: Dieser gut recherchierte Artikel bietet einen interessanten �berblick �ber das CAP-Theorem und adressiert auch die Konsequenzen desselben.
An intriguing use of lambda functions: Es ist sch�n zu sehen, wenn Lambda-Funktionen in PHP sinnvoll eingesetzt werden.
Code-Blasen statt -Dateien: Wer alte Konventionen aufbrechen will, sollte sich diese Innovation ansehen, denn das interessante Vorteile f�r professionelle Entwickler bieten.
Reflections on leaving Haskell: Welche Gr�nde k�nnte man haben, um die Haskell-Community zu verlassen? In diesem Artikel und vor allem in den Kommentaren finden sich viele Probleme, aber auch einige L�sungen derselben, wieder. F�r jeden, der einen vollst�ndigen Eindruck der Sprache erhalten will, enth�lt dieser Linktipp eine F�lle von Informationen.
Straitjacket programming: Was haben Zwangsjacken mit Programmierung zu tun? Mehr als man denkt! Ohne mehr dar�ber verraten zu wollen, kann ich den Artikel jedem ans Herz legen.
Repeat after me: �Cabal is not a Package Manager�: Gerade als Einsteiger in der Haskell-Community ist dieser Artikel gut geeignet, da er die M�glichkeiten von Hackage, Cabal und cabal install aufzeigt.
Haskell�s Big Three: Luke Palmer hat seine Liste der drei gr��ten Problempunkte in Haskell erstellt.
Hunting for abstractions in mathematics: Jedem Softwareentwickler ist Abstraktion gel�ufig, aber wie abstrakt arbeiten Softwareentwickler wirklich? Ohne behaupten zu wollen, dass Abstraktion immer die richtige L�sung darstellt, kann man betrachten, wie abstrakt die Mathematiker arbeiten.
The hacker, the architect and the superhero: three completely different ways to be an excellent programmer: Nach Mike Taylor gibt es drei Arten von exzellenten Programmierern - jeder dieser Typen ist mit einer anderen besonderen Fertigkeit ausgestattet. Dieser Artikel kann dabei helfen, seine eigenen St�rken zu erkennen und daraus Konsequenzen zu ziehen.
Tikanga, Pachika und Javalanche helfen bei der Fehlersuche : Golem.de hat eine sch�ne Zusammenfassung von drei wichtigen Projekten des Teams um Andreas Zeller erstellt. Bei allen drei Projekten geht es um Fehler: Wie man sie vermeidet, wie man sie (automatisiert) repariert und wie man Tests optimiert, sodass sie m�glichst viele Fehler erkennen.
What�s new in Apache CouchDB 0.11 � Part Three: New Features in Replication: Jan Lehnardt schreibt �ber eines der wichtigsten Features von CouchDB: Der Replikation. Auf einige Erkl�rungen zum Mechanismus folgt eine Reihe von interessanten Anwendungsf�llen.

Linktipps M�rz 2010

Blackflash — Sun, 28 Feb 2010 23:54:00 +0100

Haskell Antipattern: Existential Typeclass: Wie in jeder Sprache gibt es auch in Haskell Antimuster, wie Luke Palmer am Beispiel von existentiellen Typklassen zeigt.
HipHop for PHP: Move Fast: Facebooks Ank�ndigung eines Produkts, mit dessen Hilfe man PHP-Code in (schnelleren) C++-Code transformieren kann.
Faster PHP fo shizzle�HipHop for PHP: Terry Chay pr�sentiert den wahrscheinlich ausf�hrlichsten Artikel �ber HipHop for PHP, der zudem noch mit vielen interessanten Fakten �ber Facebook gespickt ist.
The Operational Monad Tutorial: Heinrich Apfelmus erkl�rt Monaden aus operationaler Sicht, so wie man es von ihm gewohnt ist: Profund, exakt und verst�ndlich.
Coding Is The Easy Part: Man sollte sich stets daran erinnern, dass Softwareentwicklung nicht nur aus Programmieren besteht. DIeser Artikel hilft dabei, denn er erkl�rt jede wesentliche Rolle im Lebenszyklus der Software.
Episode 17: Einstieg in REST: Der heise Developer SoftwareArchitekTOUR-Podcast gibt eine h�renswerte Einf�hrung in die REST-Welt.
ch-ch-ch-changes!: Auch CouchDB kennt Beobachter - und schon wird Comet trivial.
Software Engineering ≠ Computer Science: Chuck Connell schreibt �ber die Unterschiede zwischen Softwaretechnik und (mathematische) Informatik und zieht interessante Schl�sse. Sehr lesenswert f�r jeden, der mit beiden Themen hantiert. In diesem Sinne ist auch ein SE-Radion Podcast mit Chuck Connel h�renswert.
NoSQL GraphDB: Wer sich f�r die NoSQL und Graphentheorie interessiert, wird sich sicherlich auch f�r die Kombination derselben interessieren: Graphendatenbanken. Ricky Ho beschreibt ihre grundlegende Funktionsweise.
Gesammelte Links: Git: KingCrunch hat zahl- und hilfreiche Links gesammelt, die mir den Einstieg in github erleichtert haben - sehr empfehlenswert.
Cheat-Sheets.org: Fans von Cheat-Sheets werden an dieser Webseite ihre Freude haben.
Testing Code That Uses Singletons: Sebastian Bergmann hat sch�n auf den Punkt gebracht, weshalb man Singletons nicht verwenden sollte - auch wenn es ein sog. Entwurfsmuster ist.
Pure, extensible exceptions and self-returning functions: Auch wenn ich nur die H�lfte des Artikels verstanden habe, erscheint er mir ziemlich wertvoll, da er nicht nur gut geschrieben ist, sondern auch einen neuen Ansatz f�r Exceptions, wie er bisher nicht m�glich war, einf�hrt.
The Anatomy Of A Bug/Issue Reproduction Script: Dieser Artikel ist ein Muss f�r jeden, der ein Open-Source-Projekt durch einen Bug-Report unterst�tzen will. Wenn man bereits die f�nf genannten Punkte, auf die es ankommt, beherzigt, dann hilft man dem entsprechenden Entwickler enorm weiter!
Episode 18: (Anti-)Patterns und Tools f�r REST: Wie die Einf�hrung ein sehr sch�ner Podcast zum Thema REST. Vor allem die Patterns bzw. Anti-Patterns sind sehr interessant.
PHP Framework Benchmarks: Entertaining But Ultimately Useless: "Traue keiner Statistik, die du nicht selbst gef�lscht hast." Dies trifft auch auf Benchmarks zu, wie dieser unterhaltsame Artikel beweist.
Scaling Web Applications with HMVC: Hierbei geht es um das Hierarchische Model-View-Controller-Muster, das es sp�testens seit 2000 gibt, aber von dem ich erst heute geh�rt habe. Jedenfalls sieht das HMVC-Muster sauberer aus, wobei daraus auch Vorteile, wie gute Skalibarkeit, folgen k�nnen.
A Survey of Binary Search: Shin-Cheng Mu beschreibt, wie man das Konzept der bin�ren Suche mithilfe einer Relation aufbauen kann. Mithilfe einer solchen Relation und einem Algorithmus, der bewiesenerma�en (via Hoare-Kalk�l) einige Eigenschaften besitzt, kann man anschlie�end verschiedene Probleme mit demselben Algorithmus l�sen.
Actors are not a good concurrency model: Warum das vielgelobte Actor-Modell auch Schw�chen hat, wird in diesem Artikel er�rtert. Auch die kritischen Kommentare sind sehr lesenswert.

Currying in PHP

Blackflash — Sat, 20 Feb 2010 14:02:00 +0100

Mithilfe vom Currying (benannt nach Haskell Brooks Curry) kann man eine n-stellige Funktion in n einstellige Funktionen umwandeln. Da PHP keine funktionale Programmiersprache ist, wird dieses Verfahren zwar nicht unterst�tzt, aber mithilfe der Closures aus PHP 5.3 l�sst sich eine Funktion curry entwickeln, die das Currying-Verfahren auf PHP �bertr�gt. Bevor ich zur Implementierung komme, m�chte ich Currying anhand von Haskell beschreiben. Wir beginnen bei einem trivialen Beispiel: Der Multiplikation.


(*) :: (Num a) => a -> a -> a
(4*) :: (Num a) => a -> a
(4*2) :: (Num a) => a

An den Typen der Ausdr�cke (*), (4*) und (4*2) kann man bereits den Einsatz von Currying erkennen, wenn man wei�, dass die Klammerung bei Typsignaturen rechtsassoziativ ist. Schreiben wir diese Klammern explizit hin, ist der Typ von (*) n�mlich (a -> (a -> a)). Wenn man die Grundlagen funktionaler Programmierung beherrscht, kann man daraus ablesen, dass (*) ein Argument nimmt und eine Funktion vom Typ (a -> a) zur�ckgibt. Wenn man der zur�ckgegebenen Funktion ein weiteres Argument gibt, bekommt man eine null-stellige Funktion vom Typ a zur�ck. In Haskell geschieht dieses Currying und die damit verbundene partielle Anwendung von Funktionen transparent, sodass man diesem Umstand meist nicht gewahr ist.

Im Grunde genommen soll es also nur stets einstellige Funktionen geben, die entweder eine weitere einstellige Funktion oder das Ergebnis zur�ckgeben. Das Multiplikationsbeispiel k�nnte man in PHP folgenderma�en beschreiben:


$mult = function($x) {
	return function ($y) use ($x) {
		return $x*$y;
	};
};
$f = $mult(4);
$g = $f(2);

$mult ist hierbei eine einstellige-Funktion, die eine weitere einstellige Funktion zur�ckliefert. $mult(4) = $f ist eine solche einstellige Funktion, die ihr Argument mit 4 multipliziert und das Ergebnis $f(2) = $g = 8 zur�ckliefert. Die Art und Weise, mit der die zwei-stellige Multiplikation in eine gecurryte Funktion umgewandeln wurde, kann man f�r beliebige n adaptieren, wie folgender Code zeigt:


function curry($f, array $args = array()) {
	$refl = new ReflectionFunction($f);
	$n = $refl->getNumberOfParameters();
	
	if($n <= 1) {
		return $f;
	}
	if(count($args) == $n-1) {
		return function ($x) use ($f, $args) {
			$args[] = $x;
			return call_user_func_array($f, $args);
		};
	}
	
	return function ($x) use ($f, $args) {
		$args[] = $x;
		return curry($f, $args);
	};
}

Hierbei wird gro�er Nutzen von Closures und der Reflection-API gemacht. Insgesamt spiegelt der Algorithmus die Idee, wie ich sie bereits beschrieben habe, wieder. Die notwendigen Anpassungen, damit man die Idee in PHP ausdr�cken kann, sind rein technischer Natur. Allerdings haben solche gecurryte Funktionen einen Nachteil: Man kann nicht mehrere Argumente zugleich auswerten. Denkbar w�ren folgende Varianten:


$mult(4)(2); // funktioniert nicht
$mult(4,2); // funktioniert auch nicht, w�re aber denkbar
// eigene:
function call($f) {
	return array_reduce(
		array_slice(func_get_args(), 1),
		function ($f, $p) { return $f($p); },
		$f
	);
}
call($mult, 4, 2);

W�hrend die erste Variante durch die PHP-Syntax nicht erm�glicht wird, w�re die zweite Variante eine denkbare Alternative, die allerdings einige Spezialf�lle einf�hren w�rde. Eine eigene Funktion zur Auswertung mehrere Argumente ist jedoch auch sehr schnell implementiert und zugleich verst�ndlich.

Da es sich bei diesen Funktionen um Ideen aus der funktionalen Programmierung handelt, habe ich einen eigenen Ordner PhP, der f�r Phunctional Programming steht, in einem Github-Repository eingef�hrt, wo sich im Laufe der Zeit weitere solche Funktionen ansammeln werden.

Komponierbarkeit mit Bedarfsauswertung

Blackflash — Tue, 09 Feb 2010 18:26:00 +0100

Heute soll es um eine Eigenschaft gehen, die in einigen funktionalen Programmiersprachen helfen, die Funktionen h�chst wiederverwendbar zu gestalten - ohne immense Einbu�en in der Geschwindigkeit hinnehmen zu m�ssen. Es handelt sich dabei um die Bedarfsauswertung (engl. lazy evaluation) Inspiriert hat mich hierbei der Artikel Heap, heap, hooray! von Tobias Schlitt, der folgendes Problem in PHP l�st: Gib mir die k kleinsten Elemente aus einem Stream. Durch Haskells Bedarfsauswertung kann ich vom Stream abstrahieren und das Problem als Liste auffassen. Das Problem hei�t dann: Gib mir die k kleinsten Elemente einer Liste. Hierf�r werde ich den naiven Ansatz verwenden und zeigen, dass Naivit�t in Haskell nicht immer bestraft wird.

Der Code besteht aus den Standardfunktionen take und partition sowie aus einem selbstimplementierten Quicksort. F�r das Verst�ndnis habe ich die (interne) Implementierung der beiden Funktionen und eine Eigenschaft von partition angegeben.


take n _ | n <= 0 = []
take _ []  = []
take n (x:xs)  = x : take (n-1) xs

-- partition satisfies: partition p xs == (filter p xs, filter (not . p) xs)
partition p xs = foldr (select p) ([],[]) xs

qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort greater
 where (smaller,greater) = partition (<= x) xs

bottom k = take k . qsort

Anhand dieser Funktionen l�sst sich eine Auswertungsreihenfolge finden, mit der man die drei kleinsten Elemente der Liste [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9] ermitteln kann.


bottom 3 [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. bottom }
take 3 . qsort $ [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. $ }
take 3 $ qsort [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. qsort }
take 3 $ qsort smaller ++ [8] ++ qsort greater
~> { smaller auswerten }
take 3 $ qsort [2,1,4,5,3,6,7] ++ ...
~> { Def. qsort }
take 3 $ qsort smaller ++ [2] ++ qsort greater ++ ...
~> { smaller auswerten }
take 3 $ qsort [1] ++ [2] ++ qsort greater ++ ...
~> { Def. qsort }
take 3 $ qsort [] ++ [1] ++ qsort [] ++ [2] ++ qsort greater ++ ...
~> { Def. qsort }
take 3 $ [] ++ [1] ++ [] ++ [2] ++ qsort greater ++ ...
~> { ++ anwenden }
take 3 $ [1,2] ++ qsort greater ++ ...
~> { take solange anwenden wie m�glich }
1:2:(take 1 $ qsort greater ++ ...)
~> { greater auswerten }
1:2:(take 1 $ qsort [4,5,3,6,7] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ qsort smaller ++ [4] ++ qsort greater ++ ...)
~> { smaller auswerten }
1:2:(take 1 $ qsort [3] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ qsort [] ++ [3] ++ qsort [] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ [] ++ [3] ++ [] ++ ...)
~> { ++ anwenden }
1:2:(take 1 $ [3] ++ ...)
~> { Def. take }
1:2:3:(take 0 $ ...)
~> { Def. take }
1:2:3:[]
~> { Listenkonstruktor }
[1,2,3]

Die Variablen smaller bzw. greater werden erst ausgewertet, wenn sie wirklich ben�tigt werden, d.h. konkret wurden nur die ersten drei Elemente der Liste sortiert - und nicht die gesamte Liste. Wenn die Anzahl der gesuchten Elemente deutlich kleiner als die Liste, spart man (im Allgemeinen) deutlich mehr Zeit, als man bei einem naiven Ansatz erwarten w�rde.

Nichtsdestotrotz kann dieser Code nicht mit einer imperativen Implementierung, die f�r einen bestimmten Einsatz konzipiert wurde, mithalten. Daf�r sind Funktionen durch die Bedarfsauswertung besser komponierbar mit verh�ltnism��ig kleinen Geschwindigkeitseinbu�en.

Linktipps Februar 2010

Blackflash — Mon, 01 Feb 2010 12:17:00 +0100

PHP Is Like A Handgun?: Paul M. Jones zitiert eine interessante Analogie.
Academia vs Industry: an Updated Opinion: MarkCC von Good Math, Bad Math schreibt �ber seine Erfahrung und Ansichten �ber die Forschung in Industrie und akademischen Instituten.
Explaining Haskell IO without Monads: Ein sch�nes Tutorial zum Umgang mit IO in Haskell - ohne das Konzept von Monaden erkl�rt zu haben.
Wieso zum Teufel benutzt DU keine Versionskontrolle?: Eigentlich sollte das eine Frage sein, die sich heutzutage er�brigt haben m�sste... Die Erfahrung lehrt etwas anderes.
Is program proving viable and useful?: Trotz der fehlenden, klaren Antwort auf diese Frage, gibt Conal Elliott einige Anregungen zum Nachdenken.
Build Systems: Relevancy of Automated Builds In A Web World: Wozu ben�tigt man einen automatisierten Erstellungsprozess? Brandon Savage legt seine Gr�nde zu diesem Thema anhand seiner Erfahrungen dar.
Can functional programming be liberated from the von Neumann paradigm?: Conal Elliott propagiert einen neuen Ansatz f�r funktionale Programmierung: Das Auslagern von I/O-Operationen aus dem Programmierungsmodell. Aber auch viele weitere interessanten Gedanken sind in seinem Artikel enthalten.
Copy-on-Write in the PHP Language: Dieses Paper behandelt die Semantik von PHP in formaler Weise.
Dependency Injection Frameworks f�r PHP: Ein gelungener �berblick �ber die g�ngigsten Dependency Injection-Frameworks in PHP.
Do not use PHP references: Diese Klarstellung zum Thema Referenzen in PHP sollte f�r jeden ernsthaften PHP-Entwickler Pflicht sein.
Zippers: Making Functional "Updates" Efficient: Ein sehr hilfreicher Artikel zu einer sehr hilfreichen Datenstruktur funktionaler Programmiersprachen.
Top 20 Programming Lessons I've Learned in 20 Years: Wertvolle Tipps f�r die pers�nliche Weiterentwicklung rund ums Thema Programmieren.
Functional Programming Bibliography: Dieses Projekt wurde erst vor Kurzem gestartet und enth�lt schon eine ansehnliche Menge an Papers, die sich mit funktionaler Programmierung besch�ftigen.
Schleimiger Streckenplaner: Einzeller vs. Ingenieur. Ein Duell mit einem �berraschenden Ergebnis.
Was ein sicheres Passwort ist: Dieser Artikel sollte f�r jeden ernsthaften Internetanwender ein Muss sein!
Fighting Hype with Hype: Eine sachkundige Antwort auf Ryan Parks Top 10 Reasons to Avoid the SimpleDB Hype, welche die Problematik von NOSQL vs. SQL beleuchtet. Vor allem das Fazit sollte man sich zu Herzen nehmen.
Best Haskell Papers of 2009: Eine zugegebenerma�en subjektiv zusammengestellte Liste der besten Haskell-Papers 2009. Dennoch klingen die meisten beworbenen Paper sehr interessant.

Fibonacci-Folge in Haskell

Blackflash — Wed, 27 Jan 2010 13:57:00 +0100

Heute soll es um die bekannte Fibonacci-Folge gehen. Dabei werde ich, um mich wieder in funktionale Programmierung zu vertiefen, zwei in Haskell geschriebene Versionen der Fibonacci-Folge angeben und deren �quivalenz zeigen.

Die naive Implementierung k�nnte folgenderma�en aussehen:


fib n
 | n < 0 = error "n must be greater or equal zero"
 | n == 0 = 0
 | n == 1 = 1
 | n >= 2 = fib (n-1) + fib (n-2)

Am Beispiel bei n = 6 kann man bereits erkennen, weshalb diese Implementierung langsam ist:


fib 6 = fib 5 + fib 4
~> { fib 5 einsetzen }
fib 6 = fib 4 + fib 4 + fib 3
~> { fib 4 einsetzen }
fib 6 = fib 3 + fib 3 + fib 3 + fib 2 + fib 2
~> { fib 3 einsetzen }
fib 6 = fib 2 + fib 2 + fib 2 + fib 2 + fib 2 + fib 1 + fib 1 + fib 1
~> { fib 2 einsetzen }
fib 6 = fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 1 + fib 0 + fib 0
~> { fib 1 einsetzen }
fib 6 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + fib 0 + fib 0
~> { fib 0 einsetzen }
fib 6 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
~> { + einsetzen }
fib 6 = 8

Es finden also mehrfache Berechnungen desselben Werts statt. Durch genaueres Hinsehen stellt man folgende Korrelation fest:

fib 6 wird einmal (fib 1) berechnet.
fib 5 wird einmal (fib 2) berechnet.
fib 4 wird zweimal (fib 3) berechnet.
fib 3 wird dreimal (fib 4) berechnet.
fib 2 wird f�nfmal (fib 5) berechnet.
fib 1 wird achtmal (fib 6) berechnet.

D.h. das Ergebnis von fib n ist die Summe von fib n Einsen. F�r n = 100 w�rde das bedeuten, dass man 354.224.848.179.261.915.075 Einsen summiert. Eine effizientere Variante, die Haskells lazy evaluation ausnutzt, stellt folgende Definition dar.


fib' = let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in (fibs !!)

Der Vorteil an dieser Variante ist, dass jedes Element genau einmal berechnet und anschlie�end weiterverwendet wird. Aber bevor ich die �quivalenz zeige, m�chte ich noch die wesentlichen verwendeten Funktionen einf�hren. Beginnen wir bei der Funktion (++), sprich der Verkettung von zwei Listen, d.h. f�r zwei beliebige Listen [x₁, ..., x_n] und [y₁, ..., y_m] gilt [x₁, ..., x_n] ++ [y₁, ..., y_m] = [x₁, ..., x_n, y₁, ..., y_m]. Mittels xs !! i kann man das i-te (beginnend bei Null) Element aus der Liste xs entnehmen. Die anderen beiden wesentlichen Funktionen tail und zipWith werde ich anhand von Haskell-Code definieren.


tail [] = error "empty list"
tail (_:xs) = xs

zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = (x `f` y) : zipWith f xs ys

Satz. fib und fib' sind �quivalent.

Beweis. Da fib' n jeweils das n-te Element aus der Liste fibs entnimmt, gen�gt es zu zeigen, dass fibs die Fibonacci-Folge darstellt, d.h. fibs = [fib 0, fib 1, fib 2, ...]. Dass fibs !! 0 = 0 = fib 0 und fibs !! 1 = 1 = fib 1 gelten, ist offensichtlich. Da fibs die Verkettung von [fib 0, fib 1] und einer Liste, die mittels zipWith erstellt wird, darstellt, muss lediglich gezeigt werden, dass zipWith (+) fibs (tails fibs) und [fib 2, fib 3, ...] �quivalent sind. Nach Definition von zipWith entnimmt selbige jeweils das erste Element aus den beiden �bergebenen Listen und berechnet anhand der �bergebenen Funktion ein neues Element. D.h. ein i-maliges Anwenden der zipWith-Funktion erzeugt i Elemente, was wiederum bedeutet, dass man durch i-maliges Anwenden von zipWith den Wert von fib (1+i) berechnet. Diese Eigenschaft l�sst sich induktiv beweisen.

Induktionsanfang. Sei i = 1, dann l�sst sich fib (1+i) = fib 2 folgenderma�en berechnen:

fibs =[fib 0, fib 1] ++ zipWith (+) fibs (tail fibs)
~> { Def. von fibs }
= [fib 0, fib 1] ++ zipWith (+) [fib 0, fib 1, ...] (tail [fib 0, fib 1, ...])
~> { Def. von tail }
= [fib 0, fib 1] ++ zipWith (+) [fib 0, fib 1, ...] [fib 1, ...]
~> { Def. von zipWith }
= [fib 0, fib 1] ++ (fib 0 + fib 1) : zipWith (+) [fib 1, ...] [...]
~> { Def. von Fibonacci-Folge }
= [fib 0, fib 1] ++ (fib 2) : zipWith (+) [fib 1, ...] [...]
~> { Verkettung }
= [fib 0, fib 1, fib 2] : zipWith (+) [fib 1, ...] [...]

Induktionsschritt. Sei zipWith bereits i-mal angewendet worden, d.h. es sind bereits die ersten i+2 Werte von fibs bekannt, d.h. take (i+2) fibs = [fib 0, fib 1, ..., fib (i+1)]. Es ist zu zeigen, dass durch eine weitere Anwendung der Wert von fib (1+i+1) = fib (2+i) berechnet wird. Folgender Code illustriert dann die Berechnung f�r fib (2+i):

fibs = [fib 0, fib 1] ++ zipWith (+) fibs (tail fibs)
~> { i-maliges Anwenden von zipWith auf fibs }
= [fib 0, fib 1, ..., fib (1+i)] ++ zipWith (+) [fib i, fib (1+i), ...] (tail [fib i, fib (1+i), ...])
~> { Def. von tail }
= [fib 0, fib 1, ..., fib (1+i)] ++ zipWith (+) [fib i, fib (1+i), ...] [fib (1+i), ...]
~> { Def. von zipWith }
= [fib 0, fib 1, ..., fib (1+i)] ++ ((fib i) + fib (1+i)) : zipWith (+) [fib (1+i), ...] [...]
~> { Def. von Fibonacci-Folge }
= [fib 0, fib 1, ..., fib (1+i)] ++ (fib (2+i)) : zipWith (+) [fib (1+i), ...] [...]
~> { Verkettung }
= [fib 0, fib 1, ..., fib (1+i), fib (2+i)] ++ zipWith (+) [fib (1+i), ...] [...]

Der letzte Fall, der noch gezeigt werden muss, besteht im Fehlerfall. Denn, wenn eine Funktion einen Fehler liefert, soll die andere Funktion mit derselben Eingabe auch einen Fehler liefern. Die Funktion (!!) liefert einen Fehler, wenn entweder der Index zu gro� ist oder wenn er negativ ist. Zu gro� kann er nicht werden, da es sich bei fibs um eine unendlich lange Liste handelt. D.h. fib' n liefert genau dann einen Fehler, wenn n negativ ist. Da fib n auch nur bei negativen n einen Fehler liefert, sind fib' n und fib n auch f�r ung�ltige Eingaben �quivalent.

Linktipps Januar 2010

Blackflash — Sat, 02 Jan 2010 04:56:00 +0100

Templating Engines in PHP: Fabien Potencier erl�utert in dem Artikel den Status Quo von Template-Engines in PHP. Auch die Antwort von Eli und der weiterf�hrende Artikel von Fabien sind des Lesens wert.
How to build an API in 5 minutes: Im verlinkten Video wird erkl�rt, wie man innerhalb von f�nf Minuten eine kleine RESTful-Applikation schreibt. Der Ansatz hat in meinen Augen sehr gro�es Potential.
Self-optimizing data structures: using types to make lists faster: Don Stewart beschreibt in seinem Blog eine M�glichkeit, wie man Listenoperationen verschnellern kann. Auch wenn man wenig mit Listen arbeitet, so finde ich es dennoch beeindruckend, wie leicht man solche Tricks benutzen kann.
�Micro� Optimizations That Matter: Brandon Savage beschreibt, wie man mit verh�ltnism��ig kleinen �nderungen eine gro�e Wirkung erzielen kann.
Emulating Shared Mutable Variables with Message-Passing Processes: Funktionale Programmierung und Nebenl�ufigkeit passen zusammen, wie dieser Artikel in eleganter Weise zeigt.
Rewriting Playdar: C++ to Erlang, massive savings: Richard Jones, evtl. bekannt von last.fm, schreibt �ber seine Erfahrungen beim Rewrite von Playdar in Bezug auf Produktivit�t von Erlang, einer funktionalen Programmiersprache.
Wie Facebook die Daten von 300 Millionen Nutzern verkraftet: Ein interessanter Golem-Artikel, der aufzeigt, wie Facebook verschiedenste Performance-Probleme gel�st hat. Auch das Video mit Jeff Rothschild ist empfehlenswert.
Calculate a convex hull - The QuickHull algorithm: Jakob Westhoff erkl�rt in diesem Artikel den QuickHull-Algorithmus auf eine sehr intuitive Weise. Auch wenn es f�r mich (bisher) keinen praktischen Nutzen hat, hat es Spa� gemacht, den Artikel zu lesen.
Transforming polymorphic values: Martijn van Steenbergen gibt eine ausf�hrliche Erl�uterung zum Schreiben einer DSL zum Berechnen (und Vereinfachen) von Termen. F�r jeden Haskell-Programmierer empfehlenswert.
Notes on Memcached: In seinen Notizen beschreibt Ricky Ho die Architektur von memcached und folgert daraus die Nutzungsm�glichkeiten desselben.
Adapting The Joel Test To Web Development: Brandon Savage erkl�rt seine Adaption von Joel Spolskys 12-Punkte-Test f�r Softwarehersteller. Jeder, der professionell Software entwickelt, sollte diese zw�lf Punkte beherzigen.
Clean Code Developer in Brownfield-Projekten: Der Artikel beschreibt die gr��ten Probleme bei Brownfield-Projekten - auch als Abschreckung geeignet.
Is static type checking a redundant testing mechanism?: Luke Plant erl�utert einige interessante Feststellungen zu Unit-Tests sowie statischer Typisierung und deklarativer Programmierung im Allgemeinen und Haskell im Speziellen.
autoincrement considered harmful: Warum ist autoincrement doch nicht das Wahre? Abgesehen davon, dass es die Nebenl�ufigkeit erschwert, werden hier drei weitere Gr�nde aufgef�hrt.
PHP: So you'd like to migrate from MySQL to CouchDB? - Part II: Nach dem ersten Teil stellt dieser Artikel eine sehr pragmatische Einf�hrung in CouchDB (mittels PHP) dar.
The Observer Pattern using a Message-Passing Process: Auf dem CHP-Blog findet sich dieses Mal ein Artikel dar�ber, wie man das Observer-Entwurfsmuster nebenl�ufig in Haskell implementieren kann.
Four ways to fold an array: Neben den gel�ufigen zwei Faltungen (foldr und foldl) hat Twan van Laarhoven zwei weitere Faltungen mit Hilfe von Arrays entwickelt.
"What Category do Haskell Types and Functions Live In?": Dieser Artikel bringt Kategorientheorie und Haskell zusammen. Auch wenn ich nicht alle erw�hnten Begriffe kenne, finde ich ihn vor allem wegen der weiterf�hrenden Links sehr lesenswert.
Monads from Two Perspectives: Auch dieser Artikel bringt Kategorientheorie und Haskell zusammen, in dem er Monaden auf mathematische Weise erkl�rt und den Bezug zu den Monaden in Haskell erl�utert.
NoSQL Berlin Debrief: Auf Jan Lehnardts Blog finden sich Links zu den Pr�sentationen auf dem NoSQL-Berlin-Event.
Amazon Cloud Computing: Ricky Ho bietet einen sehr genauen �berblick �ber die Cloud Services von Amazon.
Long running Haskell applications: Dieser interessante Erfahrungsbericht �ber Haskell f�rdert das wohl h�ufigste Problem bei Haskellprogrammen zutage: Space Leaks. Die Wirksamkeit der L�sung wird dabei durch Diagramme untermauert. Weitere L�sungsm�glichkeit wurden durch die weiterf�hrende Diskussion erl�utert.
Haskell Monoids and their Uses: sigfpe erkl�rt auf seinem Blog Monoide und deren Use-Cases. Das ist wahrscheinlich die ausf�hrlichste Erkl�rung zu diesem Thema, auf die ich bisher gesto�en bin.
Haskell, DSL and Monad: Haskell, DSL und Monaden? Diese Begriffe klingen vielleicht schwierig, aber dieser Artikel zeigt das Gegenteil.
Cloud Computing Patterns: Ricky Ho stellt verschiedene Muster vor, die man beim Cloud-Computing verwendet.
An Introduction to Communicating Sequential Processes: Dass Haskell auf dem Lambda-Kalk�l aufbaut, ist nicht neu, aber mir war neu, dass CHP auf der CSP-Prozessalgebra basiert. Es ist immer wieder interessant zu sehen, wie die Theorie in der Praxis eingesetzt wird.
The Operators and Monoids of CHP: Auch hier schl�gt die Mathematik zu, denn auch Funktionen k�nnen wie algebraische Strukturen untersucht werden. Hier wird dies am Beispiel des Monoids getan.
Reviewing View Patterns: Auf seinem Blog beschreibt Neil Mitchell die sog. View-Patterns und schl�gt einige Verbesserungen vor. Auch wenn ich die View-Patterns noch nicht verwendet habe, sehen sie sehr hilfreich aus.
NOSQL Patterns: Sehr detailliert, sehr interessant, aber auch sehr lang. Wer etwas mehr �ber den aktuellen Stand der Technik der NoSQL-Welt erfahren will, ist mit dem Artikel bestens bedient.
What a Monad is not: Der Name sagt bereits alles - besonders f�r Einsteiger sehr lesenswert.
Monads are like burritos: Wer sich mit Haskell besch�ftigt, kennt evtl. Brent Yorgeys Meinung zum Thema Monaden-Tutorials - der Linktipp enth�lt die Antwort auf diesen Beitrag.

Linktipps #15

Blackflash — Sat, 26 Dec 2009 11:24:00 +0100

Automatically RESTful Web Applications: Marking Modular Serializable Continuations: Das Video zeigt einen inspirierenden Ansatz f�r Webprogrammierung.
The Cambrian Period of Concurrency: Ted Leung gibt einen �berblick verschiedener Concurrency-Konzepte.
Deployment of PHP Applications: Auch wenn der Titel suggeriert, dass es sich speziell um PHP-Applikationen handelt, kann die beschriebene Vorgehensweise beim Deployment jedes Projekts helfen.
Re-engineer Legacy Architecture : Wie geht man mit einem Legacy-System um? Ricky Ho erkl�rt es.
The Status of the P Versus NP Problem: Der Artikel enth�lt viele interessante Fakten zum P-NP-Problem - trotz der L�nge sehr empfehlenswert.

Linktipps reloaded

Blackflash — Wed, 23 Dec 2009 10:18:00 +0100

Ich habe mich dazu entschlossen, die Linktipps in anderer Form weiterzuf�hren. Nat�rlich m�chte ich diesen Schritt auch begr�nden und meine Pl�ne zu dieser Reformation darlegen.

Zuerst m�chte ich mein Bedauern ausdr�cken, dass sieben der letzten zehn Artikel Linktipps waren. Zwar finde ich die Linktipps weiterhin interessant, aber das rechtfertigt keinen Prozentsatz von 70 Punkten. Deshalb habe ich mich entschlossen, die Linktipps nur noch einmal im Monat zu ver�ffentlichen. Da ich in den letzten Monaten sehr viele interessante Links gefunden habe, konnte ich einen Vorrat von ca. 30 Links aufbauen. Ein gro�er Teil davon wird bereits im Januar gepostet. Danach werde ich wahrscheinlich 10-15 Links pro Monat empfehlen.

Linktipps #14

Blackflash — Sat, 12 Dec 2009 17:28:00 +0100

For Writing Software, a Buddy System: Ein sehr sch�n geschriebener Artikel �ber Paarprogrammierung von der New York Times.
Poison: Concurrent Termination: Wieder ein Artikel des CHP-Blogs, der dieses Mal einen simplen, aber effektiven Mechanismus zum sauberen Beenden von parallelen Programmen zum Thema hat.
let 5 = 6: Ein let-Ausdruck, der 5 = 6 ausdr�ckt, ist g�ltig? Der Artikel kl�rt �ber das Warum auf.
Requirements Engineering in Zeiten der Agilit�t: Dieser heise-developer-Artikel gibt einige Informationen zu agilem Projektmanagement in Bezug auf die Anforderungserhebung.
CouchDB: Relaxing Offline JavaScript: Ein gelungener Google Tech Talk �ber die gelungene CouchDB. Zwar geht die Pr�sentation eine Stunde, aber wer die Zeit hat, der kann sie gut investieren.

Linktipps #13

Blackflash — Sun, 29 Nov 2009 13:54:00 +0100

Configuring PHP: Essential INI Settings: Dem erfahrenen PHP-Entwickler werden diese wichtigen Konfigurationsdirektiven bereits ein Begriff sein, aber f�r Einsteiger ist es eine klare und vor allem kommentiere �bersicht.
Fine-grained SVN commit emails made easy: Um die Qualit�t eines (gr��eren) Projekts zu gew�hrleisten gibt es viele M�glichkeiten: Dieser Artikel beschreibt eine weitere, die ich durchaus sinnvoll finde.
Helios - Microsoft forscht am Betriebssystem der Zukunft: Nachdem ich bereits �ber Singularity gebloggt habe, m�chte ich dieses Mal auf ein weiteres Projekt von Microsoft Research verweisen, das ich recht interessant finde. Mir scheint es, als g�be es bei der Entwicklung von Betriebssystemen zu wenige Innovationen. Barrelfish und Gazelle sind �hnlich interessante Projekte von Microsoft Research.
10 Auswahlkriterien f�r PHP-Frameworks: Ralf Eggert gibt zehn Tipps, die man bei der Auswahl eines Frameworks beherzigen sollte.
Criterion, a new benchmarking library for Haskell: Bryan O�Sullivan, einer der Autoren von Real World Haskell, schreibt �ber seine Bibliothek zum Benchmark, die mir sehr gelungen erscheint.

Linktipps #12

Blackflash — Sat, 14 Nov 2009 14:48:00 +0100

How TDD and Pairing Increase Production: Mit diesem Artikel werden einige Vorurteile �ber testgetriebene Entwicklung und Paarprogrammierung ausger�umt.
Concurrent Pearl: The Expanding Prime Pipeline: Anhand dieses Artikels wird die Idee eines parallelen Primzahlsiebs erkl�rt.
Stanford MATH 198: Category Theory for Functional Programming: Hintergrundmaterial f�r einen Kurs �ber Kategorientheorie f�r funktionale Programmierung.
The Duct Tape Programmer: Warum ist schlechter manchmal besser? Dieser Artikel kl�rt �ber die Frage auf.
How I PHP: multiple inheritance: Der Autor erkl�rt einige Varianten, wie man etwas �hnliches wie Mehrfachvererbung in PHP realisieren kann.

Meine Firefox-Extensions

Blackflash — Wed, 04 Nov 2009 13:02:00 +0100

Obwohl ich den Firefox bereits seit langer Zeit und mit gro�er Intensivit�t nutze, geh�re ich wahrscheinlich zu denjenigen, die verh�ltnism��ig wenige Erweiterungen verwenden. Deshalb hier erstmal die Liste, der von mir verwendeten Erweiterungen:

Taboo

Jeder, der viel im Internet surft und auf viele interessante Webseiten st��t, aber meist nicht die Zeit hat, diese sofort zu lesen, wird von dieser Erweiterung begeistert sein. Solche Webseiten lassen sich dann mit einem Klick in einer Liste speichern, auf die man dann sp�ter problemlos zugreifen kann. Dadurch kann man Ordnung schaffen, ohne die Unordnung in die Lesezeichen zu verschieben.

Tab Mix Plus

Mit Tab Mix Plus kann man sehr viele Einstellungen an seinen Tabs vornehmen. Besonders das �ffnen von (versehentlich) geschlossenen Tabs ist bei mir sehr hilfreich.

Xmarks

Xmarks ist meine neueste Errungenschaft. Damit lassen sich Lesezeichen und ggf. Passw�rter mit einem Server synchronisieren. Besitzt man einen eigenen WebDAV-f�higen Server, so kann man Lesezeichen und Passw�rter auf dem eigenen Server speichern. Dadurch steigt nicht nur der Komfort, sondern im Allgemeinen auch die Sicherheit, da man nun bei jedem Webdienst sichere und unterschiedliche Passw�rter verwenden kann, ohne sie sich merken zu m�ssen.

Adblock Plus

Zu Adblock Plus muss wahrscheinlich nicht viel gesagt werden: Weg mit der Werbung!

Ghostery

Mit Ghostery bekommt man einen Einblick, wie viele Webdienstleister arbeiten: Web-Analytics, Werbenetzwerke und andere Widgets. Die meisten Webpr�senzen sind alles andere als datenschutzfreundlich, da im Hintergrund Anfragen an externe Webanalytic-Anbieter gesendet werden, von denen die meisten Benutzer nichts wissen. Ein Web-Analytic-Monopolist k�nnte dann sehr detaillierte Nutzerprofile anhand der besuchten Webseiten erstellen. Gl�cklicherweise gibt es Ghostery: Man kann solche Anfragen kurzerhand blockieren. Kurz noch in eigener Sache: Ich verwende zwar die Web-Analytic-Software Piwik, aber die ist auf meinem Server gehostet, sodass nur ich Zugriff auf diese Daten habe. Wer selbst das nicht m�chte, darf nat�rlich auch Piwik mit Ghostery blockieren.

FireGPG

Mit FireGPG kann man E-Mails ver- und entschl�sseln sowie Signaturen erstellen und verifizieren. Wieder ein Gewinn f�r die Sicherheit.

LiveHTTPHeaders

Diese Erweiterung ist f�r jeden, der mehr �ber das, was im Hintergrund passiert, erfahren m�chte, ist mit dieser Erweiterung gut bedient. Nicht nur f�r Webentwickler, die das HTTP besser verstehen wollen, sondern auch interessierte Nutzer, die erfahren wollen, welche Daten zu welchem Server gesendet werden, kann diese Erweiterung viele neue Erkenntnisse bringen.

Minimalist Gmail

Wer mag schon �berladene Benutzerschnittstellen? Ich nicht. Selbst beim bereits ziemlich schlanken Gmail lassen sich ungenutze Funktionalit�ten mit dieser Erweiterung ausblenden.

Linktipps #11

Blackflash — Sat, 31 Oct 2009 18:30:00 +0100

Cannibals, Missionaries and the State Monad pt. 2 : Eine sehr empfehlenswerte Einf�hrung in die State-Monade mit einigen hilfreichen �bungen - auch der erste und der dritte Teil sind lesenswert.
Applied Functional Programming: Part 1: Man kann funktionale Programmierung nicht nur benutzen, um funktionalen Code zu schreiben und zu verwenden, sondern auch um sinnvolle Semantiken in andere Sprachen zu �bertragen, was an einem praxisorientierten Beispiel (OpenSSL) gezeigt wird.
SVN commit hooks: Die Umsetzung einer Idee, die softwaretechnisch gesehen sehr interessant ist: Das Verhindern von Commits, die gegen bestimmte Regeln (Code-Guidelines, syntaktisch inkorrekter Code, ...) versto�en.
Concurrent Pearl: The Sort Pump: Es wird ein paralleler Sortieralgorithmus, dessen Zeitkomplexit�t O(n) betr�gt, entwickelt und erkl�rt. Nichtsdestotrotz bedeutet diese Komplexit�t nicht, dass der Algorithmus schneller als Quicksort l�uft, da durch die Parallelisierung Kommunktions�berhang zwischen den einzelnen Threads entsteht.
Snakes on the Web: Ein Python-Entwickler betrachtet die heutige Webentwicklung kritisch und liefert einige Vorschl�ge f�r die Zukunft.

Linktipps #10

Blackflash — Sat, 17 Oct 2009 09:47:00 +0200

REST Web Services - Eine Einf�hrung: Die Einf�hrung ist sehr ausf�hrlich und enth�lt viele Beispiele und Grafiken, die einem guten Verst�ndnis dienen. Insgesamt ist es eine sehr gute Aufarbeitung der Thematik.
REST - Der bessere Web Service?: Eigentlich steht dieser Artikel stellvertretend f�r die gesamte Serie, in der er erschienen ist. Dennoch habe ich gerade diesen Artikel verlinkt, da er die wichtigsten Fakten und Meinungen zu dem Thema nennt.
Ajax and REST: Erkl�rt einige Ideen, �ber die ich bereits berichtet habe, tiefgehend und stellt einige Implikationen dar.
RESTful HTTP in practice: Eine sehr praxisorientierte Einf�hrung in RESTful Webservices, die kaum einen Wunsch offen l�sst - was auch die L�nge des Artikels erkl�rt.
Graphs in the database: SQL meets social networks: Dieser sehr ausf�hrliche Artikel beschreibt, wie man Graphen und relationale Datenbanken miteinander verkn�pfen kann.

Linktipps #9

Blackflash — Sat, 03 Oct 2009 09:58:00 +0200

Fun with Morse Code: Im Prinzip geht es zwar nur um das Kodieren und Dekodieren von Morse-Code, aber der Artikel ist sehr ausf�hrlich und beschreibt neben verschiedenen L�sungswegen auch einige theoretische Aspekte wie Kategorientheorie oder GHC-Interna - sehr empfehlenswert.
Haskell/Packaging: Beschreibt Best Practices f�r Haskell-Projekte, u.a. darcs, Cabal und QuickCheck.
Debugging in Haskell: Eine kurze Einf�hrung ins Haskell-Debugging mit einigen weiterf�hrenden und lesenswerten Links.
Exploring Haskell's List Functions: Es wird ein �berblick �ber die wohl grundlegendste Datenstruktur in Haskell gegeben. Das interessanteste ist jedoch die weiterf�hrende Literatur.
RESTful Web services: The basics: Eine sch�ne Einf�hrung in RESTful Webservices.

Linktipps #8

Blackflash — Sat, 19 Sep 2009 08:17:00 +0200

Functional Refactoring and "You Can't Get There From Here": Eine interessante Beobachtung �ber das Refactoring in funktionalen Programmiersprachen.
NoSQL: If Only It Was That Easy: Sieben Datenbanksysteme werden auf Skalierbarkeit untersucht, um festzustellen, ob nicht-relationale Datenbanken wirklich besser skalieren als deren relationale Pendants. Leider wurde CouchDB in der Hinsicht nicht untersucht...
Mom Always Said to Share: In der Kindheit lernt man zu teilen und hier ist die Erkl�rung, wie bzw. weshalb man auch als Entwickler teilen kann bzw. sollte.
Trying to work out iteratees: Es wird ein Konzept, das in einem Kommentar als standard stream fusion hylomorphism stuff with a left fold beschrieben wurde, erl�utert - wieder eine Herausforderung f�r mich.
Extending objects with new methods at runtime: Wie der Titel bereits beschreibt, wird in diesem Artikel eine clevere M�glichkeit zum nachtr�glichen Hinzuf�gen von Methoden dargelegt.

HLint

Blackflash — Sun, 13 Sep 2009 09:26:00 +0200

Aus der Beschreibung von HLint geht hervor, dass es sich um ein Werkzeug handelt, das Hinweise f�r besseren Code gibt. Nachdem ich einen Artikel �ber HLint von Neil Mitchell, dem Autor von HLint, gelesen habe, installierte ich HLint sofort. Da die Installation per cabal aus unerfindlichen Gr�nden nicht funktioniert hat, habe ich es per yaourt installiert und �ber mein aktuelles Projekt laufen lassen. Nahezu augenblicklich hat mir HLint einige Hinweise gegeben, die ich verallgemeinert darstellen will:

Error: Use fromMaybe. Found maybe x id. Why not fromMaybe x?
Error: Use isJust. Found maybe False (const True). Why not isJust?
Warning: Use liftM. Found f x >>= return . g. Why not liftM g (f x)?
Warning: Eta reduce. Found \x -> liftM g (f x). Why not liftM g . f?

Die letzte Meldung erschien �brigens nach Beheben der ersten drei Hinweise und abermaligem Ausf�hren von HLint. Dass solche Vereinfachungen, die in den Hinweisen angegeben werden, m�glich sind, liegt vor allem daran, dass Haskell pur und statisch typisiert ist. Denn ohne Seiteneffekte lassen sich Haskell-Terme problemlos umformen - wie in der �blichen Arithmetik! Ich m�chte das an den o.g. Beispielen illustrieren.

Zuerst beginnen wir mit den Definitionen der Funktionen maybe, isJust und fromMaybe, die in der Dokumentation zu Data.Maybe genannt werden.

maybe: The maybe function takes a default value, a function, and a Maybe value. If the Maybe value is Nothing, the function returns the default value. Otherwise, it applies the function to the value inside the Just and returns the result.
fromMaybe: The fromMaybe function takes a default value and and Maybe value. If the Maybe is Nothing, it returns the default values; otherwise, it returns the value contained in the Maybe.
isJust: The isJust function returns True iff its argument is of the form Just _.

Daraus ergeben sich dann folgende Funktionsdefinitionen:

maybe def f Nothing = def
maybe def f (Just x) = f x

fromMaybe def Nothing = def
fromMaybe def (Just x) = x

isJust (Just _) = True
isJust (Nothing) = False

F�r die nachfolgenden Umformungen sind auch die Funktionen id, die das Argument, was sie erh�lt, zur�ckliefert, und const, eine zweistellige Funktion, die das erste Argument zur�ckgibt und das zweite ignoriert, relevant. Es muss gezeigt werden, dass maybe x id und fromMaybe x zum gleichen Ergebnis kommen, d.h. konfluent sind. Da es sich dabei um Funktionen handelt, m�ssen wir alle m�glichen Werte m betrachten, die auf die Funktionen angewendet werden k�nnen. Hierf�r m�ssen wir zwei F�lle betrachten: Entweder ist m = Nothing oder m = Just y f�r ein beliebiges y.

maybe x id m = fromMaybe x m
~> { Einsetzen von m = Nothing }
maybe x id Nothing = fromMaybe x Nothing
~> { Definition von maybe }
x = fromMaybe x Nothing
~> { Definition von fromMaybe }
x = x

maybe x id m = fromMaybe x m
~> { Einsetzen von m = Just y }
maybe x id (Just y) = fromMaybe x (Just y)
~> { Definition von maybe }
id y = fromMaybe x (Just y)
~> { Definition von id }
y = fromMaybe x (Just y)
~> { Definition von fromMaybe }
y = y

Analog geht man im Fall vor, wenn man beweisen m�chte, dass maybe False (const True) und isJust konfluent sind.

maybe False (const True) m = isJust m
~> { Einsetzen von m = Nothing }
maybe False (const True) Nothing = isJust Nothing
~> { Definition von maybe }
False = isJust Nothing
~> { Definition von isJust }
False = False

maybe False (const True) m = isJust m
~> { Einsetzen von m = Just y }
maybe False (const True) (Just y) = isJust (Just y)
~> { Definition von maybe }
const True (Just y) = isJust (Just y)
~> { Definition von const }
True = isJust (Just y)
~> { Definition von isJust }
True = True

Auch monadische Terme sind leichter als gedacht. Ich habe dabei folgende Definition f�r liftM und die Funktionskomposition (.) gefunden:

liftM f = \a -> do { a' <- a; return (f a') }
(.) f g = \a -> f (g a)

Da es sich im dritten Hinweis um eine nullstellige Funktion handelt, in der lediglich die ebenfalls nullstellige Funktion x frei ist - das ergibt sich aus der Logik der Funktion und nicht aus obigem Beispiel -, m�ssen wir die Konfluenz von f x >>= return . g und liftM g (f x) f�r alle x zeigen:

f x >>= return . g = liftM g (f x)
~> { Definition von liftM }
f x >>= return . g = (\a -> do { a' <- a; return (g a') }) (f x)
~> { Funktionsapplikation des Lambda-Ausdrucks mit (f x) }
f x >>= return . g = do { a' <- (f x); return (g a') }
~> { do-Notation }
f x >>= return . g = f x >>= \a' -> return (g a')
~> { Definition von (.) }
f x >>= \a -> return (g a) = f x >>= \a' -> return (g a')
~> { a' in a umbenennen }
f x >>= \a -> return (g a) = f x >>= \a -> return (g a)

Der Vollst�ndigkeit halber folgt noch der triviale Beweis f�r die Konfluenz von \x -> liftM g (f x) und liftM g . f.

\x -> liftM g (f x) = liftM g . f
~> { Definition von (.) }
\x -> liftM g (f x) = \a -> liftM g (f a)
~> { a in x umbenennen }
\x -> liftM g (f x) = \x -> liftM g (f x)

Res�mierend l�sst sich sagen, dass funktionale Programmierspachen einen gro�en Vorteil bei der statischen Programmanalyse haben. Das trifft vor allem auf pure Sprachen wie Haskell zu. Vor allem l�sst sich sehr leicht nachvollziehen, dass die vorgeschlagenen �nderungen nichts an der Semantik des Programms ver�ndern - dem Lambda-Kalk�l sei Dank.

PHP-Magazin 6.09

Blackflash — Sat, 12 Sep 2009 17:18:00 +0200

Heute ist das PHP-Magazin der Ausgabe 6.09 in meinem Briefkasten gelandet, weshalb ich �ber jeden Artikel einige Worte verlieren m�chte.

News: Hier entscheidet die eigene Interessenslage, ob man diese Neuigkeiten als relevant empfindet - auffallend war jedoch, dass in drei der f�nf Neuigkeiten ein Preis von 1595 Euro bis 8.900 US-Dollar genannt wurde.
PEAR-News: Ein sehr kurzer �berblick, da der Seitenkopf und die Werbung ca. 50% der Seite einnehmen, �ber die wahrscheinlich wichtigsten und interessantesten PEAR-Komponenten.
Let's talk about ez Components: Man kann geteilter Meinung �ber die Relevanz dieses Artikels sein, auch wenn der Inhalt gut erkl�rt ist.
Nils Langner im Gespr�ch mit Johannes Schl�ter: Das Interview mit dem Release-Manager von PHP 5.3 ist sehr interessant, da es viele Informationen zur PHP-Community und dem PHP-Projekt enth�lt, die interessant, wichtig oder beides sind. Man sollte dabei einige genannte Fakten im Hinterkopf behalten, wenn man das n�chste Mal einen unvollst�ndigen Bug-Report einsenden m�chte. Eine unwichtige Frage stellt sich mir dabei jedoch: Wieso gibt es kein Portr�t von Herrn Schl�ter?
Ein Neuer ist in der Stadt: Eine gelungene �bersicht �ber die Funktionalit�ten des Zend Servers, der in der Community Edition auch kostenfrei zur Verf�gung steht. K�nnte f�r den ein oder anderen Entwickler durchaus interessant sein.
.NET calling PHP: Der Beginn des Artikels wartet mit einer kurzen Einf�hrung in SOAP-Webservices auf. Anschlie�end geht es um die Implementierung eines PHP-basierten Webservices, der kompatibel zu .NET-Clients ist, worauf auch der Fokus dieses Artikels liegt. Insgesamt ist der Artikel lesenswert, da die meisten Informationen in ggf. abgewandelter Form auch f�r andere Clients gilt.
Wenn der Server dreimal klingelt: "Ein Blick �ber den Tellerrand" ist eine sehr passende Bezeichnung f�r diesen Artikel, da er ein Thema behandelt, mit dem die wenigsten PHP-Entwickler zu tun haben werden: Das Ansteuern der Telefonanlage Asterisk mittels PHP. Dennoch finde ich den Artikel recht interessant.
Subclipse und ihre Schwestern: Leider ist der Artikel sehr kurz geraten, weshalb nur eine begrenzte Anzahl an Konfigurationsm�glichkeiten beschrieben werden. Dennoch hat der Artikel mich dazu bewegt, Subversive, eine Alternative zu Subclipse, auszuprobieren. Au�erdem wurden beil�ufig einige mir noch unbekannte Fakten erw�hnt, die f�r den Subversion-Kenner wahrscheinlich alte H�te darstellen.
Ready for Enterprise: Hinter dem nichtssagenden Titel verbirgt sich ein Artikel �ber das Puppet-Framework mit dessen Hilfe sich der Aufwand f�r Systemadministratoren drastisch reduzieren l�sst, da man quasi ein Rezept angibt, wie das System am Ende aussehen soll, das Puppet dann abarbeitet. Diesen Artikel kann ich jedem uneingeschr�nkt empfehlen.
Up to date: �bliche Fallstricke und Strategien bei der Migration von PHP-Versionen im Allgemeinen und auf PHP 5.3 im Speziellen werden durch diesen Artikel abgedeckt. Man merkt dem Artikel an, dass der Autor bereits ein Buch �ber dieses Thema geschrieben hat - sehr empfehlenswert f�r diejenigen, die mit der Problematik der Migration konfrontiert sind.
Reporting mit BIRT: Wahrscheinlich ist die Anleitung nur f�r Personen interessant, denen es n�tzt, eine solche Software zu verwenden. Ich pers�nlich konnte hingegen so gut wie nichts aus dem Artikel mitnehmen.
Alles machbar: Auch wenn der Artikel einen sehr guten �berblick �ber die Entwicklung mit Oracle mittels PHP bietet, macht er keine Lust auf ein tieferes Eintauchen in die Oracle-Welt, was vor allem einigen antipathischen Kommentaren des Autors geschuldet ist.
Out now! PostgreSQL 8.4: Der Artikel an sich ist sehr gelungen und macht Lust auf mehr PostgreSQL.
Verteilte Herrschaft: Es wird ein kurzer �berblick �ber g�ngige Strategien gegeben, wenn ein einzelner MySQL-Server nicht mehr ausreicht. Dabei handelt es sich vor allem um Grundlagen, die man im Kopf behalten sollte.
Benimm dich!: Der einzige Artikel, der mich in keiner Weise dazu animiert hat, ihn zu lesen.
Vernetzt: Ein sehr gut ausgearbeiteter Artikel �ber das semantische Web. Es werden viele Ideen und Formate, aber auch einige geschichtliche Hintergr�nde geliefert. Wieder ein sehr lesenswerter Artikel, da er sich mit dem besch�ftigt, was man als Nachfolger vom Web 2.0 handelt.

Insgesamt war diese Ausgabe ziemlich gut, auch wenn man merkt, dass einige der Autoren Laien auf dem Gebiet des Schreibens sind, wie z.B. "Auch das CLI des PostgreSQL hat sein Fett wegbekommen.", "angucker" oder "Richtig durchgeknallt wird es, [...]". Dem Inhalt hat dies zumeist keinen Abbruch getan. �brigens liegt dem Magazin - zumindest im Abonnement - ein Poster �ber PHP-Web-Security im DIN-A0-Format bei.

Linktipps #7

Blackflash — Sun, 06 Sep 2009 08:27:00 +0200

Will content repositories kill the file?: Zwar ein sehr kurzer Artikel, daf�r regte er mich jedoch zum Denken an.
Do NOT try parsing with regular expressions: Kore beschreibt mithilfe des Pumping-Lemmas (f�r regul�re Sprachen), dass rekursive Strukturen nicht durch regul�re Sprachen erzeugt werden k�nnen und dass PCRE deshalb nicht zum Parsen dieser Strukturen verwendet werden sollten, was er im weiterf�hrenden Artikel auch kurz erl�utert.
some ideas for practical QuickCheck: Die Antworten auf einige Fragen zum praktischen Einsatz von Quickcheck.
Eight Reasons to Read Fiction: Acht gute Gr�nde, weshalb man neben Fachliteratur auch Belletristik lesen sollte.
Survive the Deep End: Ein freies Buch �ber das Zend Framework im HTML-Format.

Data.Default

Blackflash — Fri, 04 Sep 2009 15:22:00 +0200

Gestern bin ich auf ein Modul namens Data.Default gesto�en, das eine smarte M�glichkeit zum Definieren von Standardwerten bietet. Zwar mag diese Eigenschaft recht unspektakul�r wirken, aber in Verbindung mit Typinferenz sehr interessant ist. Auch die Definition der Typklasse ist sehr unspektakul�r:

class Default a where
	def :: a

F�r Instanzen dieser Typklasse muss also nur die Funktion def definiert werden, die lediglich den Standardwert des jeweiligen Typs darstellt. Einige Typinstanzen, die im o.g. Modul definiert wurden, sehen folgenderma�en aus:

instance Default Int where def = 0
instance Default [a] where def = []
instance Default (Maybe a) where def = Nothing

Nun ist man in der Lage def innerhalb des Codes zu verwenden. Das Elegante an dieser Typklasse ist, dass def durch den gerade ben�tigten Wert ersetzt wird und man somit nicht mehr explizit darauf achten muss, dass ein g�ltiger Standardwert gew�hlt wird, denn das �bernimmt der Compiler. Hierzu ein weiteres Beispiel (aus Hack.hs):

data Response = Response
 { status :: Int
 , headers :: [(String, String)]
 , body :: L.ByteString
 }
 deriving (Show)

instance Default Response where
 def = Response def def L.empty

Bei der Instanzierung der Default-Typklasse von Response l�sst sich erahnen, dass diese Verwendung sinnvoll ist. Zum einen wird der Code klarer, aber zum anderen braucht man sich bei einem Refactoring, z.B. wenn der Typ ge�ndert wird, nicht darum k�mmern, dass der richtige Standardwert gesetzt wird, denn der wird automatisch vom Compiler ausgew�hlt - man muss nat�rlich sicherstellen, dass ein Standardwert existiert. Derzeit ist das Feld status vom Typ Int, aber da es sich um HTTP-Codes handelt, k�nnte man einen weiteren Typ einf�hren, der nur g�ltige HTTP-Codes annehmen kann. W�rde man diesen neuen Typ in der Default-Typklasse instanzieren, br�uchte man beim Setzen von Standardwerten keine Zeile zu ver�ndern.

Zwar ist diese Idee nicht revolution�r, aber f�r mich zeigt sie sehr sch�n die Vorz�ge von Typinferenz und statisch-typisierten Programmiersprachen im Allgemeinen und Haskell im Speziellen.

Haskell, Hack und FastCGI

Blackflash — Fri, 28 Aug 2009 16:05:00 +0200

Bereits vor einiger Zeit bin ich auf ein interessantes Projekt namens Hack (von Jinjing Wang) gesto�en, das eine Schnittstelle f�r Webapplikation jeglicher Art darstellen soll, was �ber Handler realisiert wird. So sind bereits Handler f�r Happstack, Kibro, CGI, FastCGI und einigen weiteren entstanden. Da ich Lighttpd als Webserver verwende und die Konfiguration mittels FastCGI mit Lighttpd sehr leicht zu machen ist, habe ich mich kurzerhand entschlossen, Hack eine Chance zu geben.

Der erste Schritt war das Installieren der ben�tigten Hackage-Pakete. Da ArchLinux bisher verh�ltnism��ig viele Hackage-Pakete angeboten hat, habe ich das ben�tigte haskell-hack-handler-fastcgi mitsamt der Abh�ngigkeiten installiert per yaourt. Die Verwendung von cabal w�rde jedoch genauso gut funktionieren. Da Lighttpd bereits installiert war, war nur die Konfiguration desselben notwendig. Hierf�r habe ich einen virtuellen Host (taskell), der auf 127.0.0.1 zeigt, angelegt:

$HTTP["host"] == "taskell" {
 server.name = "taskell"
 server.document-root = "/home/blackflash/workspace/Taskell/src"
 fastcgi.server = (
 "/" => (
 "taskell" => (
 "socket" => "/tmp/taskell.socket",
 "check-local" => "disable",
 "bin-path" => "/home/blackflash/workspace/Taskell/src/Main",
 "min-procs" => 1,
 "max-procs" => 30,
 "idle-timeout" => 30
 )
 )
 )
}

Nat�rlich ist das nur eine rudiment�re Konfiguration zum �berpr�fen, ob es �berhaupt funktioniert, denn man sollte niemals direkt in den Workspace verlinken. Die Datei Main entspricht �brigens der kompilierten Main.hs, dessen Inhalt folgenderma�en aussieht:

module Main where

import Hack
import Hack.Handler.FastCGI
import Data.ByteString.Lazy.Char8 (pack)

main :: IO ()
main = runFastCGI app

app :: Application
app = return . Response 200 [ ("Content-Type", "text/plain") ] . (pack . show)

In der main-Funktion wird die Anbindung der Applikation app an FastCGI realisiert. Derzeit besteht sie nur aus dem Zusammenstellen einer HTTP-Antwort (200 OK) mit der Umgebung als Antwort. Eine Anfrage an den Webserver sieht dann folgenderma�en aus:

# curl http://taskell/
Env {requestMethod = GET, scriptName = "/", pathInfo = "", queryString = "", serverName = "taskell", serverPort = 80,
http = [("FCGI_ROLE","RESPONDER"),("SERVER_SOFTWARE","lighttpd/1.4.23"),
("SERVER_NAME","taskell"),("GATEWAY_INTERFACE","CGI/1.1"), ("SERVER_PORT","80"),
("SERVER_ADDR","127.0.0.1"),("REMOTE_PORT","56072"),("REMOTE_ADDR","127.0.0.1"),
("SCRIPT_NAME","/"),("PATH_INFO",""),("SCRIPT_FILENAME","/home/blackflash/workspace/Taskell/src/"),
("DOCUMENT_ROOT","/home/blackflash/workspace/Taskell/src"),("REQUEST_URI","/"),
("QUERY_STRING",""),("REQUEST_METHOD","GET"),("REDIRECT_STATUS","200"),
("SERVER_PROTOCOL","HTTP/1.1"),
("User-Agent","curl/7.19.6 (i686-pc-linux-gnu) libcurl/7.19.6 OpenSSL/0.9.8k zlib/1.2.3.3"),
("Host","taskell")("Accept","*/*")], hackVersion = [2009,7,15], hackUrlScheme = HTTP,
hackInput = Empty, hackErrors = Error Stream, hackHeaders = [], hackCache = []}

Insgesamt war das Aufsetzen einer solchen "Hallo Welt"-Applikation sehr einfach. Man ben�tigt dazu lediglich eine Informationsquellen (neben dem Quellcode), die ich hier der Vollst�ndigkeit halber noch erw�hnen m�chte:

Hack.hs: Das Hack-Modul, das die Umgebung beschreibt.
readme.md: Eine Art Kurztutorial, das vom Hack-Autor geschrieben wurde.
Hack Introduction: Eine konzeptionelle Einf�hrung in Hack, die f�r das Verst�ndnis sehr hilfreich ist.

Es sei noch angemerkt, dass ich einige Punkte wie das Kompilieren der Main.hs sowie das Neustarten des Webservers und das Eintragen des Hosts taskell nicht erl�utert habe, was daran liegt, dass dieser Artikel kein Tutorial darstellt, sondern lediglich einen �berblick �ber FastCGI-Entwicklung mit Hack und Haskell bietet.

Architekturstil: Ajax und REST

Blackflash — Tue, 25 Aug 2009 10:08:00 +0200

Der Trend geht derzeit zu Rich Internet Applications (RIA), weshalb ich mir Gedanken �ber dieses Thema gemacht habe. F�r mich als Informatiker stellte sich vordergr�ndig die Frage, wie sich solche Applikationen technisch elegant realisieren lie�en. Dabei ging es mir konkret um einen Architekturstil f�r solche Anwendungen.

Zuerst ist es jedoch wichtig zu wissen, wie konventionelle Webapplikationen entwickelt werden und welche Architektur sie nutzen, damit man die Limitationen derselben erkennt und sie derart modifizieren kann, dass sie sich gut f�r RIAs eignen. Der synchrone Mechanismus hat sich seit der Einf�hrung des HTTP nicht ge�ndert:

Der Benutzer stellt eine Anfrage an den Webserver.
Der Webserver empf�ngt die Anfrage und generiert eine HTML-Webseite.
Der Webserver sendet die Antwort zum Benutzer.

Auch bei dynamischen Webseiten wird dieser Mechanismus nur mit kleinen �nderungen verwendet. Was vor allem bemerkenswert ist, dass i.d.R. die komplette Webseite (in Form von HTML) zur�ckgesendet wird, was meist viele redundante Daten einschlie�t. Im Zuge des Web 2.0 gab es eine Entwicklung zu asynchronen Anfragen, bei der nur Teile einer Webseite neugeladen werden. Als Format der Wahl bei diesen asynchronen Anfragen wird kein HTML verwendet, sondern auf XML oder neuerdings auch JSON gesetzt. Erm�glicht wird dieser asynchrone Nachrichtenaustausch durch JavaScript, woraus sich letztendlich das Akronym Ajax ergibt. F�hrt man dieses Konzept konsequent weiter, gelangt man zu einem Architekturstil, der auf synchronen Nachrichtenaustausch soweit wie m�glich verzichtet.

Wie l�sst sich ein solcher Architekturstil jedoch umsetzen? Da die Applikationslogik aus offensichtlichen Gr�nden nicht beim Benutzer ausgef�hrt werden kann, ben�tigt man eine Komponente, die diesen Part �bernimmt: Ein Webservice. Konkret bietet sich hierf�r eine leichtgewichtige Art von Webservice an, die auf Ideen des HTTP aufbaut: Representational State Transfer (REST). Es wird also ein sog. RESTful Webservice ben�tigt. Im Gegensatz zu konventionellen Webapplikationen w�rde ein solcher Webservice weitaus mehr Anfragen erhalten, die allerdings weitaus k�rzer ausfallen - statt einer gesamten HTML-Webseite werden dem Client lediglich die ben�tigten Daten zur Darstellung gesendet. Betrachtet man dieses Konzept aus Sicht des MVC-Architekturmusters, so stellen sich die Zust�ndigkeiten folgenderma�en dar:

Modell: Der Webservice enth�lt die Gesch�ftslogik.
View: Der Webserver enth�lt die Rohfassung des Views und der Client wei�, wie er den View mit Daten aus dem Modell f�llen kann.
Controller: Auf dem Client werden die Benutzerinteraktionen abgehandelt.

Man erkennt eine klare Trennung zwischen Modell und View/Controller bzw. Webservice und Client. Durch diese konsequente Trennung wird man zu einer pr�zisen Beschreibung des Webservices gezwungen, was der Qualit�t des Softwareprodukts zugute kommen sollte. Ein weiterer Nebeneffekt ist, dass die Last zum Teil vom Server auf die Clients verteilt wird, was bei den Clients kaum ins Gewicht f�llt, aber f�r den Server sp�rbare Auswirkungen hat.

Ich f�r meinen Teil finde diesen Architekturstil sehr interessant, weshalb ich ihn ein wenig erkunden m�chte. Welche Komponenten ben�tigt man also daf�r? Zum einen braucht man eine gute Ajax-Bibliothek (z.B. Dojo, prototype.js) und zum anderen neben einem Webserver nat�rlich ein Framework mit dessen Hilfe man RESTful Webservices. Da Frontend-Entwicklung nicht zu meinen Interessen geh�rt und die Anforderungen an den Webservice sehr hoch sind, werde ich mich in naher Zukunft mit diesem Thema besch�ftigen, wobei es derzeit nach einer Haskell-L�sung mittels FastCGI aussieht, was der Geschwindigkeit von Haskell und meinem Interesse an funktionalen Programmiersprachen geschuldet ist. Zu diesem Thema werde ich euch nat�rlich auf dem Laufenden halten.

Insgesamt scheint die Idee �lter zu sein, als ich angenommen habe, da bereits 2006 ein Artikel �ber Ajax und REST erschienen ist - weshalb hat sie sich bisher nicht durchgesetzt? Oder wird sie bereits exzessiv eingesetzt und es ist mir nur noch nicht aufgefallen? Solltet ihr mehr zu diesem Thema wissen oder eine Meinung zu diesem Thema haben, w�rde ich mich nat�rlich freuen, wenn ihr mich dar�ber unterrichtet.

Linktipps #6

Blackflash — Sat, 22 Aug 2009 09:07:00 +0200

How to Use PHP Namespaces, Part 1: The Basics: Der Einstieg erkl�rt die Grundlagen zu Namespaces und deren Sinn.
How to Use PHP Namespaces, Part 2: Importing, Aliases, and Name Resolution: Im zweiten Teil der Trilogie werden Begriffe und die Funktionsweise gekl�rt und Hinweise zur Nutzung gegeben.
How to Use PHP Namespaces, Part 3: Keywords and Autoloading: Der finale Teil zeigt n�tzliche Methoden und Konstanten auf, die f�r Fortgeschrittene sicherlich von gro�em Wert sein d�rften.
Tom deMarco sieht Ende des Software-Engineering: Sowohl der Heise- als auch der verlinkte Artikel von Tom deMarco ist sehr lesenswert. Es geht um seine Ansicht zur Situation des Software-Engineerings. Auch wenn man nicht seiner Meinung sein muss, gibt er einige interessante Denkanst��e.
Everyone's talking about Haskell: Ein Art von Interview, das �ber Haskell gef�hrt wurde. Es geht vor allem um einen �berblick, wo Haskell industriell eingesetzt wird bzw. eingesetzt werden kann.

Uncle Bob�s Bowling Game Kata

Blackflash — Thu, 13 Aug 2009 15:38:00 +0200

Vor zwei Tagen gab es auf ProgrammingPraxis.com die Aufgabe Uncle Bob�s Bowling Game Kata durchzuf�hren. Bei dieser Kata geht es darum, anhand von der umgefallenen Pins die Gesamtpunktzahl einer Bowling-Runde zu ermitteln. Die in Haskell angefertigte L�sung ist sehr elegant, weshalb ich sie hier pr�sentieren und verifizieren will. Aber davor m�ssen noch einige wichtige Begriffe und nat�rlich die Regeln erkl�rt werden (vgl. Bowlingregeln).

Bowling-Runde: Die Bowling-Runde besteht aus 10 Frames.
Frame: Ein Frame endet entweder nach zwei W�rfen oder nach einem Strike.
Strike: Alle 10 Pins wurden nach dem ersten Wurf getroffen. Zus�tzlich zu den 10 Punkten werden die n�chsten beiden W�rfe addiert.
Spare: Alle 10 Pins wurden nach dem zweiten Wurf getroffen. Zus�tzlich zu den 10 Punkten wird der n�chste Wurf addiert.
Offener Frame: Es wurden mit den beiden W�rfen weniger als 10 Pins getroffen.
Miss: Es wurde kein Pin getroffen.
Letzter Frame: Die Runde hat mindestens zwei und maximal drei W�rfe deren Summe zum Ergebnis addiert wird. Der dritte Wurf wird genau dann gew�hrt, wenn ein Strike oder Spare geworfen wurde.
Punktzahl: Die Anzahl der getroffenen Pins bei einem Wurf.

Die folgende Grafik zeigt einen beispielhaften Verlauf (entnommen von ProgrammingPraxis.com):

Ist ein K�stchen zur H�lfe ausgef�llt, so wurde ein Spare geworfen, d.h. es wurden 10 Punkte in dem Frame geworfen. Bei einem vollst�ndig ausgef�lltem K�stchen wurde ein Strike geworfen, d.h. mit einem Wurf wurden 10 Pins getroffen. In der obigen Darstellung steht in der unteren Zeile die Gesamtpunktzahl nach dem jeweiligen Frame, wobei die speziellen Regeln f�r Strikes, Spares und den letzten Frame bereits ber�cksichtigt wurden.

Meine Implementierung macht sich diese Regelunterscheidungen zunutze:


pins [x,y] = x+y  -- last frame
pins [x,y,z] = x+y+z  -- last frame
pins (x:y:z:xs)
 | x == 10 = 10+y+z + pins (y:z:xs) -- Strike
 | x+y == 10 = 10+z + pins (z:xs) -- Spare
 | otherwise = x+y + pins (z:xs) -- open frame

Die Erkl�rung des Codes erfolgt dabei direkt anhand der Verifikation der Korrektheit. Es wird der Einfachheit halber angenommen, dass die W�rfe als Liste von Punktzahlen �bergeben wird, d.h. Strikes, Spares oder Misses werden anhand der Punktzahlen ermittelt. Au�erdem kann vorausgesetzt werden, dass die Eingabe korrekt ist. Eine wesentliche Eigenschaft zur Verifikation ist die Invariante, die besagt, dass bei einem Aufruf der Funktion pins genau ein Frame abgearbeitet wird.

Beginnen wir bei der Berechnung des letzten Frames: Der letzte Frame enth�lt entweder drei oder zwei W�rfe. Hier wird lediglich die Gesamtpunktzahl des Frames ermittelt. Durch das Pattern-Matching werden nur die F�lle abgearbeitet, in denen die Liste zwei oder drei Punktzahlen, sodass die Regeln, wie definiert, nur im letzten Frame gilt. Die Regeln entsprechen offensichtlich dem, was in der Definition des letzten Frames angegeben wurde. Au�erdem gilt die Invariante, da der letzte Frame in G�nze abgearbeitet wird.

Der andere Fall wird genau dann aufgerufen, wenn der letzte Frame noch nicht erreicht ist. Zuerst wird die Invariante gezeigt: Wurde ein Strike geworfen, hat der Frame nur einen Wurf, d.h. nur der Kopf der Liste (d.h. x) wird verarbeitet. In den restlichen F�llen werden die ersten beiden Elemente verarbeitet (d.h. x und y). Dies ist offensichtlich der Fall, da die jeweiligen Elemente in den nachfolgenden Aufrufen nicht mehr verarbeitet werden. Die Regeln werden regelkonform �bernommen: Bei einem Strike werden die n�chsten beiden (d.h. y und z), bei einem Spare nur die n�chste (d.h. z) sowie bei einem offenen Frame keine weiteren Punktzahlen zur Gesamtpunktzahl des jeweiligen Frames addiert.

Da die Regeln jeweils korrekt �bertragen wurden, wird die Gesamtpunktzahl jedes Frames korrekt berechnet. Es kann als bekannt vorausgesetzt werden, dass sich die Gesamtpunktzahl einer Bowling-Runde aus der Gesamtpunktzahl jedes einzelnen Frames ergibt. Da pins lt. Invariante jeweils einen Frame korrekt berechnet und diese Punktzahl anschlie�end auf Gesamtpunktzahl der restlichen Frames addiert wird, ist auch die Summe korrekt. F�r das Verst�ndnis exerziere ich die Funktionsweise am Beispiel der obigen Grafik durch:

pins [1,4,4,5,6,4,5,5,10,0,1,7,3,6,4,10,2,8,6]
= {open frame}
(1+4) + (pins [4,5,6,4,5,5,10,0,1,7,3,6,4,10,2,8,6])
= {open frame}
5 + (4+5) + (pins [6,4,5,5,10,0,1,7,3,6,4,10,2,8,6])
= {spare}
5 + 9 + (10+5) + (pins [5,5,10,0,1,7,3,6,4,10,2,8,6])
= {spare}
5 + 9 + 15 + (10+10) + (pins [10,0,1,7,3,6,4,10,2,8,6])
= {strike}
5 + 9 + 15 + 20 + (10+0+1) + (pins [0,1,7,3,6,4,10,2,8,6])
= {open frame}
5 + 9 + 15 + 20 + 11 + (0+1) + (pins [7,3,6,4,10,2,8,6])
= {spare}
5 + 9 + 15 + 20 + 11 + 1 + (10+6) + (pins [6,4,10,2,8,6])
= {spare}
5 + 9 + 15 + 20 + 11 + 1 + 16 + (10+10) + (pins [10,2,8,6])
= {strike}
5 + 9 + 15 + 20 + 11 + 1 + 16 + 20 + (10+2+8) + (pins [2,8,6])
= {last frame}
5 + 9 + 15 + 20 + 11 + 1 + 16 + 20 + 20 + 16
= {+}
14 + 15 + 20 + 11 + 1 + 16 + 20 + 20 + 16
= {+}
29 + 20 + 11 + 1 + 16 + 20 + 20 + 16
= {+}
49 + 11 + 1 + 16 + 20 + 20 + 16
= {+}
60 + 1 + 16 + 20 + 20 + 16
= {+}
61 + 16 + 20 + 20 + 16
= {+}
77 + 20 + 20 + 16
= {+}
97 + 20 + 16
= {+}
117 + 16
= {+}
133

Anhand dieses Beispiels kann man sehr gut erkennen, wie der Algorithmus arbeitet. Zuerst wird jeder einzelne Frame berechnet und anschlie�end dessen Summe gebildet. Zwar hat die Auswertungsreihenfolge lt. Church-Rosser-Theorem keinen Einfluss auf das Ergebnis, aber die obige Reihenfolge ist f�r das Verst�ndnis sehr gut geeignet. Ein Vergleich mit den korrigierten Testf�llen auf Tom Moertels Blog bekr�ftigt dieses Ergebnis.

Insgesamt bin ich sehr zufrieden mit meiner L�sung, da sie sehr kurz aber auch sehr pr�zise ist. Soweit ich wei�, sollten solche Code-Katas testgetrieben entwickelt werden, was in diesem Fall allerdings sehr wenig Sinn hat, denn sechs Zeilen Code sind schneller geschrieben als die Unit-Tests und man kann sich sehr leicht von der Korrektheit �berzeugen. Wenn man beim Schreiben des Codes bereits plant, den Code zu verifzieren, macht man sich automatisch Gedanken dar�ber, wie man das Problem dekomponieren und die Teill�sungen komponieren kann. In meinem Fall wurde die Gesamtpunktzahl der Bowling-Runde durch die Gesamtpunktzahl jedes Frames berechnet. Die Berechnung jedes Frames ist trivial und so mussten nur noch diese Teill�sungen zur Gesamtl�sung komponiert werden, d.h. die Summe der Frames musste berechnet werden. Diese Gedanken helfen beim Probleml�sen enorm.

Linktipps #5

Blackflash — Sat, 08 Aug 2009 11:13:00 +0200

Bei diesem Mal geht es nur um empfehlenswerte Artikel, die sich mit CouchDB befassen.

CouchDB: A Case Study: Es werden einige Gr�nde dargelegt, in welchen F�llen und weshalb CouchDB eine interessante Alternative zu RDBMS ist.
CouchDB: Databases and Documents: In dem Artikel wird in die Terminologie von CouchDB eingef�hrt und wesentliche Eigenschaften erl�utert.
CouchDB: Views � The Advantages: Eine Erl�uterung �ber die St�rken der Views von CouchDB und nat�rlich einige Beispiele, wie diese Views funktionieren.
CouchDB: Views � The Challenges: In diesem Artikel werden Probleme aufgezeigt, die durch Benutzung von Views entstehen k�nnen.
CouchDB: Application Changes: John P. Wood erkl�rt die notwendigen �nderungen an der Applikation, um CouchDB ins Projekt zu integrieren. Entstanden ist eine sehr ausf�hrliche Beschreibung dieser Migration.

Mein erster Artikel auf phphatesme.com

Blackflash — Fri, 31 Jul 2009 11:59:00 +0200

Am Mittwoch ist mein erster Artikel auf phphatesme.com im Rahmen des Akademischen Tags erschienen. Das Thema waren regul�re Ausdr�cke, wor�ber ich bereits vor einiger Zeit einen Artikel verfasst hatte. Diesmal ging es jedoch noch mehr um die Theorie, da dies mein wichtigstes Anliegen war, die Grundlagen verst�ndlich zu machen, sodass man auf diesen aufbauen und noch interessantere Themen behandeln kann. Ich hoffe auf viele weitere solcher Artikel mit solchem Feedback. :-)

Mengenpackungen und Ferienwohnungen

Blackflash — Sun, 26 Jul 2009 12:02:00 +0200

Dieses Mal geht es um ein scheinbar kleines Optimierungsproblem: Mich hat die Frage umtrieben, ob es m�glich ist, einen effizienten Algorithmus zu entwerfen, der eine optimale Auslastung bzw. den maximalem Gewinn einer Ferienwohnung bestimmt. Das erste Problem, das es zu l�sen gilt, ist das Finden eines geeigneten Formalismus. Nach ein wenig erfolglosem Rumprobieren mit Graphen und Recherche im Internet habe ich einen sehr geeigneten Formalismus gefunden, mit dem ich das Problem genau definieren kann:

Voraussetzung: Alle Anmeldungen sind bereits im Voraus bekannt.
Eingabe:
- Die Mengen S₁, ..., S_n, die jeweils eine Anmeldung darstellt und die Tage, an denen die Ferienwohnung gebucht werden soll, enth�lt.
- Eine Abbildung f: {1, ..., n} → N, die jeder Anmeldung seinen jeweiligen Preis zuordnet.
Ausgabe: Eine Menge von Indizes I ⊆ {1, ..., n} mit folgenden Eigenschaften:
- F�r je zwei unterschiedliche Elemente i, j ∈ I sind die Mengen S_i und S_j disjunkt.
- Die Summe Σf(i) aller i ∈ I ist maximal.

Diese Definition entspricht bis auf den Wortlaut der Definition des Mengenpackungsproblems in seiner gewichteten Optimierungsvariante. Da dieses Problem NP-vollst�ndig ist, gibt es unter Annahme, dass P ≠ NP, keinen effizienten Algorithmus zum L�sen dieses Problems. Jetzt wissen wir also, dass es keine algorithmische L�sung gibt, aber was bedeutet das? Das bedeutet, dass wir die (menschliche) Natur zum L�sen dieses Problems nutzen sollten: Jede Anmeldung wird m�glichst schnell best�tigt und es wird eine Liste mit freien Tagen ver�ffentlicht. Zum einen bedeutet das, dass die G�ste mit sehr geringer Wahrscheinlichkeit abspringen, und zum anderen wird eine Selektion betrieben, sodass sich meist nur die Leute melden, welche die Ferienwohnung zu den freien Terminen mieten wollen. Zwar wird man dadurch i.d.R. nicht das Optimum erhalten, aber es ist eine ausreichend gute Approximation und steigert die Planungssicherheit sowie evtl. die Zufriedenheit der G�ste.

Und die Moral von der Geschicht? Man sollte nicht versuchen, alles mit dem Computer zu l�sen, denn in vielen F�llen - vor allem im kleinen Ma�stab - erh�lt man durch weitaus einfachere Methoden sehr brauchbare Ergebnisse.

Linktipps #4

Blackflash — Sat, 25 Jul 2009 10:02:00 +0200

Heute erscheint die vierte Ausgabe der Linktipps:

A Monad for Combinatorial Search with Heuristics: Der Artikel zeigt die Entwicklung einer Monade mit der man auch kompliziertere Backtracking-Algorithmen formulieren k�nnte. Basis hierf�r sind Penalty-Listen durch die man Ansatzpunkte (f�r das Backtracking) priorisieren kann.
Choosing between SQL and Non-SQL: Ricky Ho beschreibt, aufgrund der zahlreichen Diskussionen �ber SQL vs. Non-SQL, einige wesentliche Aspekte von Anforderungen an Datenbanken, die sich jeder Applikationsentwickler vor Beginn eines Projekts stellen sollte.
Determining List Steepness in a Homomorphism: Ein Artikel f�r den theoretisch veranlagten Haskell-Entwickler, der interessante Zusammenh�nge liefert und beweist. F�r jemanden, der noch nicht in der Theorie steckt - so wie ich -, ist es auf jeden Fall eine angenehme Herausforderung, den Artikel zu verstehen.
Karps 21 NP-vollst�ndige Probleme: 21 Probleme, die man f�r eine Polynomialzeitreduktion gut verwenden kann - sehr n�tzlich.
Setter, Getter, public? Zugriff auf Attribute: Sebastian gibt eine kleine Einf�hrung in die elementaren M�glichkeiten des Zugriffs auf Attribute (in PHP) und diskutiert diese anschlie�end.