Donnerstag, Januar 18, 2007

Python und statische Typisierung

Wenn wir schon einmal bei dem Thema sind, Python zu erweitern, noch eine Projektidee:

Es gibt immer wieder Diskussionen darüber, ob statische Typisierung, wie sie beispielsweise bei Compiler-Sprachen wie Java und C# zum Einsatz kommt, besser oder schlechter ist als die dynamische Typisierung bei Skript-Sprachen. Der Streit darum soll konstruktiv angegangen werden, indem am Beispiel der Skript-Sprache Python die Herausforderung angenommen wird, Python um ein frei programmierbares, statisches Typsystem zu erweitern. Das Typsystem soll in Python entwickelt und als Modul importierbar sein. Auf diese Weise können Python-Programme optional mit strikter Typisierung entwickelt werden.

Zunächst ist ein frei programmierbares Typsystem inklusive Inferenz-Maschinerie zu entwickeln; der Vorschlag ist, sich dabei stark an der Umsetzung eines solchen Systems in der Sprache Qi zu orientieren. Qi ist eine funktionale Sprache, die von Mark Tarver entwickelt wurde, siehe www.lambdassociates.org. Qi nutzt zur Typspezifikation den Sequent-Calculus und greift auf eine Prolog-Implementierung zur Umsetzung der Inferenz-Maschinerie zurück. Analog könnte bei der Umsetzung in Python vorgegangen werden. Im zweiten Schritt wäre die Einbettung des Typsystems in Python zu untersuchen. In Python kann eine Funktionsdefinition mit einem so genannten Dekorator versehen und einer Vorverarbeitung unterworfen werden. Durch einen Typ-Dekorator soll die Typinformation an eine Funktion gebunden und die Typ-Korrektheit überprüft werden. Dazu muss der AST (Abstract Syntax Tree) der Funktion analysiert werden. An dieser Stelle sollte ein Proof of Concept genügen. Es wäre per Implementierung zu klären, wie weit der Ansatz für Python tragfähig ist und wo seine Grenzen liegen.

Nicht einfach, ein echte Herausforderung. Der Fun-Faktor könnte dafür aber auch extrem hoch liegen!

Mittwoch, Januar 17, 2007

Python um Scheme-Features erweitern

Ich habe eine Projektidee für Sie, wenn Sie sich für Sprachen wie Python und Scheme begeistern und sich tiefergehend mit einigen Konzepten befassen wollen:

Es gibt Bestrebungen, imperative Programmiersprachen um Eigenschaften aus der funktionalen Sprachwelt zu bereichern. (Imperative Sprachen sind Anweisungssprachen wie z.B. Java, C#, Ruby, Python, etc.) Dieser Trend ist der Einsicht geschuldet, dass funktionale Programme einige Vorteile durch die Einfachheit ihrer zustandsfreien Eingabe-/Rückgabe-Logik mit sich bringen. In der Kombination mit der Pragmatik zustandsbasierter Herangehensweisen bei imperativen Sprachen ergibt sich für den Programmierer bzw. die Programmiererin die zwanglose Option, beide Paradigmen ohne Integrationsprobleme einsetzen zu können. Die Herausforderung ist, die Skript-Sprache Python um funktionale Fähigkeiten zu erweitern.

Die Skript-Sprache Python soll um Spracheigenschaften erweitert werden, die Python prinzipiell in den Sprachkonzeptionen der Sprache Scheme gleichstellt. Konkret geht es um Tail Recursion (einer Optimierung von rekursiven Funktionen), Continuations (einem Mittel zur Flusskontrolle) und die Möglichkeit zur Verwendung von Macros (PreCompiling durch Ersetzungsmuster). In Python kann eine Funktionsdefinition mit einem so genannten Dekorator versehen und einer Vorverarbeitung unterworfen werden. In der Vorverarbeitung soll der AST (Abstract Syntax Tree) der Funktion manipuliert werden. Im ersten Schritt sind alle Statements durch Ausdrücke (expressions) zu ersetzen; damit ist die Ausdrucksqualität von Scheme erreicht, und grundsätzlich können Macros auf einem reinen "Ausdrucks-AST" angewendet werden. Der AST ist auf Tail Recursion hin zu untersuchen und gegebenenfalls in eine Iteration umzuwandeln. Continuations sollen durch Umwandlung des ASTs in einen Continuation Passing Style (CPS) ermöglicht werden. Nach all diesen Verarbeitungsschritten ist der AST in Python-ByteCode zu compileren. Dabei ist möglicherweise die Rückübersetzung in Statements sinnvoll.

Wenn Sie sich damit z.B. im Rahmen einer Diplomarbeit befassen wollen, melden Sie sich bei mir.

Dienstag, Januar 02, 2007

Does Functional Programming Matter?

More than 20 years ago, John Hughes wrote a seminal paper about "Why Functional Programming Matters" -- a paper still worth reading. He argues that functional programming provides new kinds of "glue", which enable a programmer to modularize code in a much better way than is possible in a "conventional" (imperative) language. He talks about "the importance of having the right glue". Hughes identifies two kinds of glue: lazy evaluation and higher-order functions.

Meanwhile, conventional languages have caught up -- I don't think that John Hughes' arguments still hold. Let me briefly explain, why I think so.

Lazy Evaluation

Lazy evaluation is a fascinating feature. It delays a computation until a result is really needed. Haskell, for instance, is based on this evaluation paradigm. In Lisp or Scheme, lazy evaluation can be simulated with so-called streams.

With lazy evaluation, code can be in fact highly modularized. One example in Hughes' paper is the Newton-Raphson algorithm for finding square roots. I re-wrote the code in Scheme (using DrScheme), which looks like this:


(require (lib "stream.ss" "srfi" "40"))

(define (next_c N)
(lambda (a)
(/ (+ a (/ N a)) 2.0)))

(define (repeat f init)
(stream-cons init (repeat f (f init))))

(define (within eps stream)
(let ((a (stream-car stream))
(b (stream-car (stream-cdr stream))))
(if (<= (abs (- a b)) eps)
b
(within eps (stream-cdr stream)))))

(define (my-sqrt guess eps N)
(within eps (repeat (next_c N) guess)))


The point is that the algorithm for approximating the square root ("next_c") is cleanly separated from "within". Even better, "within" is not specifically programmed for "next_c", it can be used generically! That's what Hughes means, when he talks about modularization. The concerns (approximating the square root and checking if the difference of two subsequent values of a stream lies within a threshold) are separately put in independent functions and used in combination by a combining function "my-sqrt".

If you take a language like Python, which offers generators as a language feature (see also here), you can easily modularize the code in the very same way. With generators, streams can be easily emulated. Here's my hack:


def next(N,a):
while True:
a = (a + N/a) / 2.0
yield a

def within(eps,generator,*args):
g = generator(*args)
a,b = g.next(), g.next()
while abs(a-b) > eps:
a,b = b, g.next()
return b

def my_sqrt(guess,eps,N):
return within(eps,next,N,guess)


The code is practical identical in structure and lines of code. Generators enable a programmer to modularize code in the very same way as is provided by streams and/or lazy evaluation.

Higher-Order Functions

Higher-Order Functions (HOFs) are functions, which can digest one or more functions and/xor return a function as a result. In pure functional programming, HOFs are a must, otherwise, function composition would be impossible.

Other languages are not built around the notion of a function. Their basic units of handling are, for instance, objects or components. In object-orientation or component-orientation you have other means of modularization. So, there is limited need to simulate HOFs. Despite this, most "conventional" languages provide some sort of support for HOFs. In Python, for example, there is a built-in "map" and "reduce" function. It's even possible to return functions as a result; Python supports lambda expressions.

Final Remark

Before someone misunderstands me: I would still agree that functional programming matters. But in a different way. It is just not a matter of "modularization glue" (in the sense of John Hughes) any more. The gap between functional and imperative languages is closing!

Kunden haben, Sprachen bauen

Am Neujahrstag kam ich mit einem Unternehmer ins Gespräch. Was er denn so mache? Sein Unternehmen entwickle Software für die Wasserwirtschaft. Das fand ich natürlich spannend -- und fragte neugierig nach. Die nächsten Minuten hörte ich allerlei Interessantes: dass haufenweise Daten z.B. zu Wasserständen gesammelt werden, die Daten abgerufen, zusammengeführt, ausgewertet und visuell aufbereitet werden müssen. Ich war überrascht und meinte verblüfft: "Was es alles für Nischen gibt, mit denen sich Geld verdienen lässt! Das beeindruckt mich immer wieder!". Darauf leuchteten die Augen meines Gesprächspartners auf, als ob er mühelos mit einem Dutzend Geschäftsideen aufwarten könne:

Nischen für Softwareentwicklung gibt es viele und Geld machen kann man damit auch ...


Und er fügte augenzwinkernd hinzu:

... wenn man die Kunden hat.


Kurz darauf verriet er mir noch, dass sein Unternehmen eine eigene Programmiersprache für ihr Problemfeld (Verarbeitung von Zeitreihen, Erstellung von Reports) entwickelt habe. Er halte das für entscheidend, es habe vieles an der Software-Entwicklung vereinfacht. Man könne eine solche Sprache mit Techniken des Compilerbaus mühelos in einer Woche entwickeln. Er wundere sich, warum das nicht mehr gemacht werden würde.

Interessant, gell? Software-Entwicklung als das Problem, eine geeignete Beschreibungsform zu finden -- das kommt sicher dem einen oder anderen Leser bzw. der einen oder anderen Leserin bekannt vor, oder?