Sun 03 June 2018

The billion dollar mistake, Scala edition

Prologue

Today's blog post originates from an internal presentation at my workplace and describes the paper Java and Scala’s Type Systems are Unsound by Amin and Tate. Hence the presented ideas are not really my own and all the praise goes to the paper's authors. All mistakes are, of course, mine alone.

By the end of the post, you will see how to provoke a ClassCastException at runtime without ever using a cast (or Scala's equivalent of a cast, asInstanceOf). This post shows the Scala version of the paper, but it's worth to mention that the same can be done for Java's type system (as shown in the paper).

You can find a Jupyter notebook version of the blogpost here. It requires the Jupyter Scala kernel to run.

Subtyping

If S is a subtype of T, any term of type S can be safely used in a context where a term of type T is expected. This subtyping relation is often written as S <: T. The subtyping relation typically is also reflexive (A <: A) and transitive (A <: B and B <: C implies A <: C), making it a preorder.

Example: Integer <: Number <: Object

Subtyping is also a form of type polymorphism (a single interface to entities of different types), namely subtype polymorphism. Example: ArrayList <: List.

Path-dependent types

Scala has path-dependent types. They allow values to have individualized types associated with them. Note that the type is associated with the value, not with the value’s type!

For example, given the following trait:

trait Box {
    type Content
    def revealContent(): Content
}
defined trait Box

and the following two values:

val box1: Box = new Box {
    type Content = Int
    def revealContent(): Int = 42
}

val box2: Box = new Box {
    type Content = Int
    def revealContent(): Int = 21 + 21
}

// Note the different types and specifically that it's not Box.Content!
var content1: box1.Content = box1.revealContent()
val content2: box2.Content = box2.revealContent()
box1: Box = $sess.cmd1Wrapper$Helper$$anon$1@387d316
box2: Box = $sess.cmd1Wrapper$Helper$$anon$2@6cdc9e37
content1: box1.Content = 42
content2: box2.Content = 42

Then all of the following is not possible:

val c: Box.Content = box1.revealContent()
cmd2.sc:1: not found: value Box
val c: Box.Content = box1.revealContent()
       ^

Compilation Failed
// Note the mix of box1 and box2!
val c2Prime: box1.Content = box2.revealContent()
cmd2.sc:1: type mismatch;
 found   : cmd2Wrapper.this.cmd1.wrapper.box2.Content
 required: cmd2Wrapper.this.cmd1.wrapper.box1.Content
val c2Prime: box1.Content = box2.revealContent()
                                              ^

Compilation Failed

Using (witness) values to reason about code

It’s possible to use values as a proof that some other value has a certain property. For example, we can define a trait LowerBound[T] that reflects that a value of type T has a super class M.

// T is a subclass of M
trait LowerBound[T] {
    type M >: T
}
defined trait LowerBound

Now, with the help of that value, we can write an upcast function that casts T to M, without ever using a cast:

def upcast[T](lb: LowerBound[T], t: T): lb.M = t

// Proof that it works
val intLowerBound = new LowerBound[Integer] {
    type M = Number
}

val int42: Integer = 42
val intAsNumber: Number = upcast(intLowerBound, int42)
defined function upcast
intLowerBound: AnyRef with LowerBound[Integer]{type M = Number} = $sess.cmd3Wrapper$Helper$$anon$1@306ad96a
int42: Integer = 42
intAsNumber: Number = 42

Note that it works because we state the subtyping relation M >: T and Scala verifies that the relation holds. For example, trying to state that Integer is a lower bound of String doesn’t work:

val intWithStringAsLowerBound = new LowerBound[Integer] {
    type M = String
}
cmd4.sc:2: overriding type M in trait LowerBound with bounds >: Integer;
 type M has incompatible type
    type M = String
         ^

Compilation Failed

Reasoning about nonsense

Now comes the fun part: reasoning about nonsense. First, we introduce a complementary trait UpperBound[U] that states that U is a subtype of M.

trait UpperBound[U] {
    type M <: U
}
defined trait UpperBound

In Scala, it’s possible for a value to implement multiple, traits, hence we can have a value of type LowerBound[T] with UpperBound[U] which states the subtype relation T <: M <: U (that’s the reason why we named the path-dependent type in both traits M, so we can express this relation).

Note that a type system always only helps so much. We made the type system argue for us about certain values, but the type system doesn’t hinder us from expressing complete nonsense. For example, the following compiles perfectly fine:

// We take a proof `bounded` that states that String <: M <: Integer and a value of
// bottom type String, and we will raise to the top and return an integer
def raiseToTheTop(bounded: LowerBound[String] with UpperBound[Integer], value: String): Integer = {
    // Subtle, but: the LowerBound[String] allowes the upcast (because String <: M)
    // On the other hand, the `UpperBound[Integer]` states that M <: Integer holds
    // as well and because Scala allows subtypes as return value, we are totally fine
    // returing the (intermediate) M as Integer!
    return upcast(bounded, value)
}
defined function raiseToTheTop

Of course nothing good can come from such a function. On the other hand, we can argue that while it’s a bit sad that the type system allows to express such a type, nothing bad can happen really happen. The function above only works because we have proof that the typing relation exists, via the bounded witness value. We can only call the function if we get hold of such a witness value. And we have seen above that it’s impossible to construct such a witness value, because Scala checks the typing relation expressed in the traits:

val proof = new LowerBound[String] with UpperBound[Integer] {
    type M = ??? // what should we put here?
}

The billion dollar mistake

Tony Hoare, the “inventor” of null, once called it his billion dollar mistake:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing > the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

And, as you might have already guessed from the title, it haunts as again. Scala has the concept of implicit nulls, meaning that a null value can take any type. Unfortunately for us, it also means that it can take the nonsense type LowerBound[String] with UpperBound[Integer]:

val sadness: LowerBound[String] with UpperBound[Integer] = null

// Et voilà, watch the impossible being possible
raiseToTheTop(sadness, "and that is why we can't have nice things")
java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

  $sess.cmd5Wrapper$Helper.raiseToTheTop(cmd5.sc:6)

  $sess.cmd6Wrapper$Helper.<init>(cmd6.sc:4)

  $sess.cmd6Wrapper.<init>(cmd6.sc:139)

  $sess.cmd6$.<init>(cmd6.sc:90)

  $sess.cmd6$.<clinit>(cmd6.sc:-1)

A ClassCastException was thrown - and we didn’t even use a single cast in our code.

As a matter of fact, we can generalize our raiseToTheTop function to coerce an arbitrary type to any type we want:

def coerce[T, U](t: T): U = {
    val bounded: LowerBound[T] with UpperBound[U] = null
    return upcast(bounded, t)
}

// Same as before
coerce[String, Integer]("and that is why we can't have nice things")
java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

  $sess.cmd7Wrapper$Helper.<init>(cmd7.sc:7)

  $sess.cmd7Wrapper.<init>(cmd7.sc:139)

  $sess.cmd7$.<init>(cmd7.sc:90)

  $sess.cmd7$.<clinit>(cmd7.sc:-1)

Tue 30 January 2018

Unerwartet: def vs. val

Nach einem Jahr der Blog-Abstinenz heute zur Erfrischung mal ein wenig Scala. Nehmen wir an, wir haben die folgende login-Funktion, die REST-assured nutzt, um HTTP-Requests für einen Login zu tätigen. Zurückgegeben wird ein Tupel mit einem Access-Token und wie lange selbiges gültig ist.

def login(credentials: Credentials): (String, Int) = {
  def json = given()
    // Skipped: add the credentials somehow to the request
    .post("…")
    .Then
    .statusCode(HttpStatus.SC_OK)
    .extract()
    .jsonPath()

  (json.getString("access_token"), json.getInt("expires_in"))
}

Manchmal gibt die Methode ein Access-Token zurück, das nicht gültig ist, obwohl es laut der ebenfalls zurückgegebenen Gültigkeitsdauer noch lange gültig sein sollte. Warum?

Sehr subtil, aber das def json = … sollte natürlich ein val json = … sein. Ansonsten findet bei der Erstellung des Rückgabe-Tupel zwei mal ein Aufruf der Funktion json statt: einmal bei der Auswertung von json.getString("access_token") und das andere Mal bei der Auswertung von json.getInt("expires_in"). Beides mal wird natürlich auch ein frischer HTTP-Request abgesetzt. Es konnte daher passieren, dass für das Access-Token ein Token zurückgegeben wurde, das gerade am ablaufen ist, und für den expires_in-Wert wurde bereits ein neues Token ausgestellt. Daher sieht es so aus, als wäre das Token noch lange gültig, dabei ist es bereits abgelaufen.

Sun 10 January 2016

Typsicheres verlinken mit Java 8

Im heutigen Blog-Post geht es um Webrahmenwerke. Genauer: es geht darum, wie man auf typsichere Art und Weise Links zu Controllern erzeugt. Typsicher in dem Sinne, dass man Variablen im Routing nur durch Werte des selben Typs ersetzen kann, den der Controller auch tatsächlich erwartet. Übergibt man die falsche Anzahl an Werten oder Werte des falschen Typs, soll der Code erst gar nicht kompilieren – in anderen Worten: Es sollen nicht erst Exceptions zur Laufzeit geworfen werden, sondern bereits beim kompilieren. Für das Beispiel beschränken wir uns auf Pfad-Variablen.

Die Code-Beispiele für die Controller sind dabei lose an JAX-RS orientiert. Es werden die folgenden Konventionen benutzt:

  • Methoden, die Requests behandeln, haben lediglich die Pfad-Variablen als Parameter. Die Reihenfolge der Parameter ist dabei die Reihenfolge, in der sie im Routing-Template definiert sind.

Note

In diesem Blog-Beitrag wird nur die Methode vorgestellt, mit der man Links erstellen kann. Ein Router, der Requests auf Controller dispatcht, wird nicht vorgestellt.

Außerdem wird eine gewisse Vertrautheit mit Java 8 (insbesondere Lambdas) vorausgesetzt sowie auch ein wenig mit JAX-RS. Für eine Intro zu Lambdas siehe etwa den Lambda Quick Start

Prior Art

Da Links erzeugen ein Recht häufiges Problem ist, gibt es natürlich so einiges an Prior Art. Wahrscheinlich in so ziemlich jedem Webrahmenwerk, in den unterschiedlichsten Ausprägungen. Ich habe stellvertretend einmal drei herausgegriffen:

  • Pyramids route_url

    Zeigt schon mal die grobe Idee, wenn auch in Python und nicht in Java. Gewisse Fehler werden abgefangen (falsche Anzahl an Argumenten zum Beispiel). Allerdings passiert alles zur Laufzeit. Man braucht also eine recht gut ausgeprägte Test-Suite, um Fehler beim Linken zu erkennen.

  • Declarative Hyperlinking in Jersey

    Mit Annotationen umgesetzt und dadurch stringly typed. Fehler werden erst zur Laufzeit erkannt.

  • Spring HATEOAS

    Kommt schon recht nahe dran. Insbesondere Building links pointing to methods geht stark in die Richtung:

    Method method = PersonController.class.getMethod("show", Long.class);
    Link link = linkTo(method, 2L);
    

    Allerdings funktioniert die Methoden-Auflösung zur Laufzeit und via Name als String. Die Parametertypen müssen explizit angegeben werden und die Typüberprüfung passiert ebenfalls erst zur Laufzeit.

Warum nicht Methodenreferenzen?

Da Java 8 endlich Methodenreferenzen eingeführt hat, liegt natürlich die Idee nahe, es damit irgendwie zu versuchen.

Stellen wir uns vor, dass wir den folgenden Controller hätten:

@Path("/hello")
class HelloWorldController {

    @GET
    public String hello() {
        return "Hello, world!";
    }
}

Als erstes erstellen wir ein FunctionalInterface. Das Interface soll eine Referenz auf eine Methode der Klasse H darstellen, die keine Parameter entgegen nimmt und ein R als Ergebnis zurück gibt. Dementsprechend sieht das Interface wie folgt aus:

@FunctionalInterface
interface NoParam<H, R> {
    R apply(H h);
}

Dieses Interface kann aus einer Methodenreferenz erstellt werden:

NoParam<HelloWorldController, String> hello = HelloWorldController::hello;
// Aufrufen könnte man die Methode jetzt so (angenommen,
// someHelloWorldController ist eine Instanz von HelloWorldController):
String result = hello.apply(someHelloWorldController);
assert "Hello, world!".equals(result);

Folglich können wir damit dann die folgende Methode bauen:

<H, R> URI linkTo(NoParam<H, R> handler) {
    // Hier der Code, der die Routing-Informationen von handler ausliest und
    // daraus dann eine URI baut
}

Jetzt ist es möglich, aus einem anderen Controller heraus einen Link zu unserer gewünschten Methode HelloWorldController#hello() zu bauen:

URI helloLink = linkTo(HelloWorldController::hello);

Wenn wir ein Argument zu viel übergeben würden (zum Beispiel, weil wir denken, dass die hello-Ressource einen Namen entgegen nimmt, um einen personalisierten Gruß zu erzeugen, kompiliert der Code nicht:

java: no suitable method found for linkTo(HelloWorldController::hello)

Ziel erreicht. Um tatsächlich Pfad-Parameter zu unterstützen, müssen wir jetzt einfach (relativ mechanisch) weitere Interfaces einführen.

Erweitern wir zunächst unseren Controller um einen personalisierten Gruß:

@GET
@Path("/{name}")
public String greeting(String name) {
    return "Hello, " + name + "!";
}

Der Parameter name repräsentiert hierbei die Pfad-Variable name. Links dazu können dann folgenderweise erstellt werden:

URI link = linkTo(HelloWorldController::greeting, "Joe");

Dazu führen wir ein weiteres Interface ein:

@FunctionalInterface
interface OneParam<H, P, R> {
    R apply(H h, P p);
}

Wenig überraschend steht H hierbei für den Typ des Controllers, P für den Parameter und R für den Rückgabewert.

Desweiteren muss eine weitere Überladung von linkTo eingeführt werden:

URI linkTo(OneParam<H, P, R> handler, P param) {
    // Hier wieder Routing-Infos von handler auslesen und dann param einsetzen
}

Das ist zum Implementieren zwar ein wenig wortreich (für jede Anzahl an Pfad-Variablen ein eigenes Interface und eine entsprechende linkTo-Methode), aber das muss man zum Glück nur einmal tun und außerdem hat man ja auch nicht unendlich lange Pfade in der Praxis.

Viel gravierender ist jedoch: es funktioniert überhaupt nicht. Man kann zwar aus einer Methodenreferenz ein Lambda bauen. Allerdings geht die Information, aus welcher Methode das Lambda erzeugt wird, dabei verloren. Wir brauchen die Information, um welche Methode es sich handelt, jedoch, da wir ansonsten nicht an die Route kommen.

Proxies to the rescue

Da die Antwort auf die meisten Probleme in Java "(dynamische) Code-Generierung" ist, probieren wir es doch auch einmal damit. Genauer gesagt dynamische Proxy-Objekte. Die Idee ist dabei folgendermaßen:

  • Wir erzeugen uns ein Proxy-Objekt vom gleichen Typ der Handler-Klasse.
  • Wir rufen die Methode auf, die übergeben wurde (genauer gesagt, das Lambda)
  • Das Proxy-Objekt ruft nicht wirklich die eigentliche Methode auf, sondern merkt sich einfach, welche Methode aufgerufen wurde.
  • Wir holen uns die gemerkte Methode vom Proxy-Objekt.

Gehen wir davon aus, dass wir eine Klasse MethodResolver<T>, die die Proxy-Objekte erstellt, könnte unsere linkTo-Methode also in der Art aussehen:

URI linkto(Class<H> handlerClass, OneParam<H, P, R> handler, P param) {
    MethodResolver<H> methodResolver = MethodResolver.on(handlerClass);
    handler.apply(methodResolver, param);
    Method method = methodResolver.resolve();
    // Mit handlerClass und method kann man jetzt an die Routing-Informationen
    // kommen
}

Die meisten AOP-Rahmenwerke bieten Method-Interceptors an, mit denen man das recht einfach umsetzen kann. Für Proxetta könnte ein entsprechendes Advice zum Beispiel so aussehen:

/**
 * MethodResolver advice applied on all methods. It puts the method in a class
 * variable that can be accessed later using reflection.
 */
class MethodResolverAdvice implements ProxyAdvice {

    public Method method;

    public Object execute() {
        final Class<?> targetClass = targetClass();
        final String methodName = targetMethodName();
        final Class<?>[] argumentTypes = createArgumentsClassArray();
        try {
            method = targetClass.getMethod(methodName, argumentTypes);
        } catch (NoSuchMethodException e) {
            throw new RuntimeException(e);
        }
        return returnValue(null);
    }
}

Beispielimplementierung

Im Github-Repo java8_linking_experiments habe ich eine Beispielimplementierung für das Ratpack-Mikro-Webrahmenwerk umgesetzt.

Mon 10 August 2015

AmazonS3Client mit Pithos benutzen

Pithos, ein S3-Klon, der Cassandra zur Ablage benutzt, unterstützt aktuell nur Signaturen in V2. S3 unterstützt inzwischen aber eigentlich nur noch V4, weswegen der offizielle AmazonS3Client ein paar Probleme bei der Verwendung mit Pithos macht:

 Exception in thread "main" com.amazonaws.services.s3.model.AmazonS3Exception: The request signature we calculated does not match the signature you provided. Check your key and signing method. (Service: Amazon S3; Status Code: 403; Error Code: SignatureDoesNotMatch; Request ID: 1e04fbc1-bf91-4bb3-af1e-6829ce549524), S3 Extended Request ID: 1e04fbc1-bf91-4bb3-af1e-6829ce549524
      at com.amazonaws.http.AmazonHttpClient.handleErrorResponse(AmazonHttpClient.java:1182)
      at com.amazonaws.http.AmazonHttpClient.executeOneRequest(AmazonHttpClient.java:770)
      at com.amazonaws.http.AmazonHttpClient.executeHelper(AmazonHttpClient.java:489)
      at com.amazonaws.http.AmazonHttpClient.execute(AmazonHttpClient.java:310)
      at com.amazonaws.services.s3.AmazonS3Client.invoke(AmazonS3Client.java:3608)
      at com.amazonaws.services.s3.AmazonS3Client.getObject(AmazonS3Client.java:1135)
      at com.amazonaws.services.s3.AmazonS3Client.getObject(AmazonS3Client.java:1015)
...

Mit einem kleinen (Trick|Hack) kann man den Client dann aber trotzdem dazu bewegen, V2 zum Signieren zu benutzen:

private static final String PITHOS_ENDPOINT = "s3.example.com";
private static final String ACCESS_KEY = "AKIAIOSFODNN7EXAMPLE";
private static final String SECRET_KEY = "wJalrXUtnFEMI/K7MDENG/bPxRfiCYEXAMPLEKEY";

// …

final AWSCredentials credentials = new BasicAWSCredentials(ACCESS_KEY, SECRET_KEY);
final ClientConfiguration clientConfig = new ClientConfiguration();
clientConfig.setSignerOverride("S3SignerType");
clientConfig.setProtocol(Protocol.HTTP);
final AmazonS3Client s3Client = new AmazonS3Client(credentials, clientConfig);
s3Client.setEndpoint(PITHOS_ENDPOINT);

Getested mit dem AWS Java SDK Version 1.10.10. Mit etwas Suchen kann man das auch in den Issues finden: #277 und #372.

Sun 11 November 2012

Automatisiert Refleaks in Unittests erkennen

Wenn man händisch CPython-Erweiterungen mit Hilfe der C-API baut (und nicht etwa Cython oder Ähnliches benutzt), läuft man leider sehr leicht Gefahr, dass man versehentlich Reference Leaks einbaut.

Um das Auffinden von Refleaks zu erleichtern, zählt CPython bei einem Debug-Build die Summe aller Referenzen:

Python 3.4.0a0 (default:9214f8440c44, Nov 11 2012, 00:15:25)
[GCC 4.7.1] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>
[60488 refs]
>>> n = 42
[60490 refs]

Die Summe der Referenzen ist die Zahl zwischen den []. In diesem Beispiel hat sich die Gesamtanzahl der Referenzen um zwei erhöht, weil die Zahl 42 an zwei Namen gebunden wurde: einmal an n und einmal an _, weil Python im interaktiven Modus immer unter _ eine Referenz auf den letzten Wert hält.

Die Gesamtanzahl der Referenzen kann man in Debug-Builds auch programmatisch über die Funktion sys.gettotalrefcount erhalten. Also liegt es nahe, dass man versucht, Refleaks automatisch zu finden, beispielsweise, indem man die Gesamtanzahl der Referenzen vor und nach einem Testlauf betrachtet.

Die Idee ist hierbei recht einfach: Wird die Test-Suite mit einem Debug-Python ausgeführt, wird jeder Test fünf mal ausgeführt. Bei den letzten zwei Durchläufen wird dann die Gesamtzahl der Referenzen vor und nach dem Test verglichen. Die drei Durchläufe vorher werden nicht ausgewertet, damit sich die Zahl der Referenzen erst auf einen Wert einpendeln kann (beispielsweise, wenn Caches im Test eine Rolle spielen etc.).

Im Folgenden eine simple Umsetzung der Idee für das klassische unittest-Modul:

hunt_leaks = hasattr(sys, "gettotalrefcount")
if hunt_leaks:
    import gc

def _is_not_suite(test):
    try:
        iter(test)
    except TypeError:
        return True
    return False


def _cleanup():
    sys._clear_type_cache()
    gc.collect()

def _hunt(test):
    def test_wrapper(*args, **kwargs):
        deltas = []
        _cleanup()
        for i in xrange(5):
            before = sys.gettotalrefcount()
            test(*args, **kwargs)
            _cleanup()
            after = sys.gettotalrefcount()
            if i > 2:
                deltas.append(after - before)
        if any(deltas):
            print("{0!r} leaks: {1}".format(test, deltas))
    return test_wrapper

class TestSuite(unittest.TestSuite):
    def __iter__(self):
        for test in super(TestSuite, self).__iter__():
            if hunt_leaks and _is_not_suite(test):
                yield _hunt(test)
            else:
                yield test

Anzumerken ist hierbei, dass bei umfangreichen Testsuites _cleanup noch erweitert werden muss. Beispielsweise muss man die ABC-Registry aufräumen, Caches (re, struct, urllib, linecache) und warnings müssen aufgeräumt werden, etc.

Jetzt muss man nur noch unittest beibringen, dass es die obige TestSuite benutzen soll. Benutzt man keinen besonderen Test-Runner, kann man das beispielsweise einfach wie folgt tun:

def test():
    loader = unittest.TestLoader()
    loader.suiteClass = TestSuite
    unittest.main(testLoader=loader)

if __name__ == "__main__":
    test()

Reference Leaks können natürlich auch mit "reinem" Python-Code passieren, indem man globalen Zustand verändert. Ein etwas konstruiertes Beispiel:

class Observable(object):
    def __init__(self):
        self.observers = []

    def add_observer(self, callable):
        self.observers.append(callable)

    def notify_observers(self, value):
        for observer in self.observers:
            observer(value)

value = Observable()

class SpamTest(unittest.TestCase):
    def test_observable(self):
        class Observer(object):
            def __init__(self):
                self.called = False

            def __call__(self, value):
                self.called = True

        observer = Observer()
        value.add_observer(observer)
        value.notify_observers(42)
        self.assertTrue(observer.called)

Führt man die Tests jetzt aus, führt das zu folgender Ausgabe:

.....<__main__.SpamTest testMethod=test_observable> leaks: [40, 40]

----------------------------------------------------------------------
Ran 5 tests in 0.007s

Jetzt weiß man zumindest, dass der Test test_observable leckt. Was genau leckt, muss man aber immer noch selbst herausfinden. Was nicht unbedingt immer leicht und offensichtlich ist.

Wed 21 September 2011

1001 Wege, PHP zum Segfaulten zu bringen

Da es aber in etwa so ist wie behinderte Kinder zu schubsen, werde ich nur zwei zeigen.

<?PHP

class Spam {
    function __toString() {
        (string)$this;
    }
};

(string)new Spam();

?>
<?PHP

$spam = array();
implode(&$spam, &$spam);

?>

Tue 11 January 2011

nonlocal in Python 2.x

In Python 3 gibt es ein neues Statement nonlocal, das es erlaubt, bei verschachtelten Funktionen in der inneren Funktion einen neuen Wert an einen lokalen Namen der äußeren Funktion zu binden. In Python 2 war es nur möglich, sich auf einen lokalen Namen der äußeren Funktion zu beziehen.

Note

Der größte Teil dieses Blogeintrags dürften Implementierungsdetails von CPython sein und müssen keinesfall für andere Python-Implementierungen gelten.

Dazu schauen wir uns als erstes eine Funktion näher an:

def f():
    local_name = 42

(In Python implementierte) Funktionien haben in CPython ein sogenanntes Code-Objekt, das als func_code-Attribut (in Python 3 als __code__-Attribute) an die Funktion gebunden ist. In ihm sind der Bytecode, alle verwendeten lokalen Namen und Konstanten und andere Informationen gespeichert. All das ist direkt in Python selbst benutzbar und sollte durchaus einmal im interaktiven Interpreter ausprobiert werden. Der generierte Bytecode für diese Funktion sieht wie folgt aus (die Ausgabe wurde mit dem dis-Modul von Python gemacht):

2           0 LOAD_CONST               1 (42)
            3 STORE_FAST               0 (local_name)
            6 LOAD_CONST               0 (None)
            9 RETURN_VALUE

Dabei ist die 2 in der ersten Spalte die Zeilennummer, die Spalte rechts davon ist der Offset des Opcodes im Bytecode, gefolgt vom Opcode selbst und (falls vorhanden) einem Argument. In Klammern steht dann jeweils, was das Argument bedeutet.

Im konkreten Fall für die Funktion f wird also zunächst die Konstante 1 geladen, in unserem Fall ist das 42. 42 ist hierbei im co_consts-Attribut des Code-Objekts gespeichert. Diese 42 wird dann auf einem internen Stack der CPython-VM abgelegt. Der nächste Opcode, STORE_FAST, speichert den obersten Wert vom Stack in die lokale Variable local_name. Lokale Variablen werden dabei einfach als Array im aktuellen Frame umgesetzt (wobei dieses Array nicht von Python aus erreichbar ist). Der Opcode speichert also einfach den Wert als ersten Eintrag im Array. Falls jemand auf den lokalen Namensraum als Dict zugreifen wird (etwa über locals() oder das f_locals-Attribut eines Frames), wird das Dict des lokalen Namenraumes dann einfach mit den Werten aus dem Array aktualisiert. Die benötigten Informationen, nämlich die Namen der lokalen Variablen, finden sich im co_varnames-Attribut des Code-Objekts.

Als nächstes wird dann die Konstante None geladen und zurückgegeben (da eine Funktion in Python ja implizit None zurückgibt, wenn kein anderer Rückgabewert angebeben wurde).

Als nächstes betrachten wir eine Funktion, die eine geschachtelte Funktion zurückgibt, die einen Namen der äußeren Funktion benutzt:

def outer():
    outer_name = 42

    def inner():
        return outer_name
    return inner

Der Bytecode für outer():

2           0 LOAD_CONST               1 (42)
            3 STORE_DEREF              0 (outer_name)

4           6 LOAD_CLOSURE             0 (outer_name)
            9 BUILD_TUPLE              1
           12 LOAD_CONST               2 (<code object inner at 0x7ff7fe792cd8, file "<stdin>", line 4>)
           15 MAKE_CLOSURE             0
           18 STORE_FAST               0 (inner)

6          21 LOAD_FAST                0 (inner)
           24 RETURN_VALUE

Und für inner():

5           0 LOAD_DEREF               0 (outer_name)
            3 RETURN_VALUE

Was hat sich geändert? Zunächst einmal fällt auf, dass in outer() nicht mehr STORE_FAST zum Speichern der lokalen Variable benutzt wird, sondern STORE_DEREF. Das liegt daran, dass outer_name von der inneren Funktion benutzt wird. Anstatt in einem Array wird der Wert jetzt in einem sogenannten Cell-Objekt gespeicher (wobei diese Cell-Objekte wiederum auch in einem Array im Frame gespeichert werden). outer_name ist auch nicht mehr in co_varnames aufgelistet, sondern in co_cellvars. Als nächstes wird dieses Cell-Objekt dann auf den Stack geladen (mit LOAD_CLOSURE) und in ein Tupel gepackt (BUILD_TUPLE). Dieses Tupel bildet dann das func_closure-Attribut der neuen Funktion inner(), die mit MAKE_CLOSURE erstellt wird. Schließlich wird die neu erstellte Funktion, die sich oben auf dem Stack befindet, mit STORE_FAST an den lokalen Namen inner gebunden, wieder geladen und zurückgegeben.

In inner() wird einfach der Wert aus dem Cell-Objekt geladen, das aus func_closure genommen wird und zurückgegeben. Genau genommen werden die Cell-Objekte aus func_closure zum Array der Cell-Objekte im Frame hinzugefügt, wenn das Frame erstellt wird.

Was passiert jetzt, wenn man in inner() outer_name einen Wert zuweist?

def outer():
    outer_name = 42

    def inner():
        outer_name = 43

    return inner
5           0 LOAD_CONST               1 (43)
            3 STORE_FAST               0 (outer_name)
            6 LOAD_CONST               0 (None)
            9 RETURN_VALUE

Wie man sieht, wird outer_name in inner() automatisch zu einer lokalen Variable, der Wert in outer() selbst wird nicht geändert. Versucht man vorher außerdem auf outer_name zuzugreifen, erhält man einen UnboundLocalError.

Für diesen Fall bietet Python 3 das neue nonlocal-Statement. Damit kann man in inner() sagen, dass man den Wert in outer() ändern mag:

def outer():
    outer_name = 42

    def getter():
        return outer_name

    def increaser(n):
        nonlocal outer_name
        outer_name += n

    return (getter, increaser)

(getter, increaser) = outer()
print(getter())
increaser(42)
print(getter())

Führt man den Code aus, erhält man die folgende Ausgabe:

42
84

Doch wie funktioniert nonlocal? Schauen wir uns dazu wieder den Bytecode an. Von getter():

5           0 LOAD_DEREF               0 (outer_name)
            3 RETURN_VALUE

Wenig überraschend hat sich hier nichts geändert. Und der Bytecode von increaser()?

9           0 LOAD_DEREF               0 (outer_name)
            3 LOAD_FAST                0 (n)
            6 INPLACE_ADD
            7 STORE_DEREF              0 (outer_name)
           10 LOAD_CONST               0 (None)
           13 RETURN_VALUE

Wie man sieht, wird zum Laden der Variable wieder LOAD_DEREF benutzt. Was jetzt aber interessant ist: Zum Speichern wird STORE_DEREF benutzt, also derselbe Opcode, der auch in outer() benutzt wird. Was ja auch eigentlich logisch ist, denn in beiden Fällen wird der Wert in ein Cell-Objekt geschrieben -- sogar in dasselbe Cell-Objekt. Das bringt uns also zur folgenden Erkenntnis: Das nonlocal-Statement wäre auch problemlos in Python 2.x möglich, es fehlt nur die Syntax dafür (und natürlich auch die Compiler-Unterstützung).

Also werden wir im Folgenden probieren, das nonlocal-Statement in Python 2.x umzusetzen. Dazu müssen in der inneren Funktion alle STORE_FAST-Opcodes für einen nonlocal-Namen durch STORE_DEREF ersetzt werden und alle LOAD_FAST durch LOAD_DEREF. Außerdem müssen die Namen dann zu co_freevars hinzugefügt werden. Man kann ein Code-Objekt jedoch nicht einfach so verändern, sondern muss ein neues erstellen. Da man Funktionen verändert, drängt sich ein Dekorator geradezu auf:

def nonlocal(*args):
    def decorator(f):
        code = Code.from_code(f.func_code)
        code.freevars.extend(args)
        for (i, (op, arg)) in enumerate(code.code):
            if op in ["LOAD_FAST", "STORE_FAST"]:
                name = code.code_obj.co_varnames[arg]
                if name in args:
                    if op == "LOAD_FAST":
                        code.code[i] = ("LOAD_DEREF", code.freevars.index(name))
                    else:
                        code.code[i] = ("STORE_DEREF", code.freevars.index(name))

        caller_locals = sys._getframe(1).f_locals
        return types.FunctionType(
            code.to_code(),
            f.func_globals,
            f.func_name,
            f.func_defaults,
            tuple(caller_locals["_[%s]" % (name, )] for name in args)
        )
    return decorator

Dabei zeigt sich ein weiteres Problem: Man muss an die Cell-Objekte der äußeren Funktion bekommen. Dies tun wir, indem wir nach jedem STORE_DEREF (also jedes mal, wenn ein Wert in ein Cell-Objekt geschrieben wird), zwei weitere Opcodes einfügen: LOAD_CLOSURE und STORE_FAST. Damit wird direkt nach dem Speichern das Cell-Objekt auf den Stack geladen und in einem lokalen Namen gespeichert. Dazu führen wir für jeden Namen, der ein Cell-Objekt hat, eine lokale Variable _[<Name>] ein. Die [] deshalb, dass der Name nicht mit einem anderen lokalen Namen zu Konflikten führt. Im Dekorator der inneren Funktion kann man dann einfach über f_locals vom Frame des Aufrufers auf die Cell-Objekte zugreifen, den man mit sys_getframe(1) bekommt. Der Dekorator für die äußere Funktion sieht also so aus:

def outer(*args):
    def decorator(f):
        code = Code.from_code(f.func_code)
        code.varnames.extend("_[%s]" % (name, ) for name in args)
        code.nlocals += len(args)
        code.cellvars.extend(args)

        i = 0
        while i < len(code.code):
            (op, arg) = code.code[i]
            if op == "STORE_DEREF":
                if arg < len(code.cellvars) and code.cellvars[arg] in args:
                    name = code.cellvars[arg]
                    code.code[i+1:i+1] = [
                        ("LOAD_CLOSURE", arg),
                        ("STORE_FAST", code.varnames.index("_[%s]" % (name, )))
                    ]
                    i += 2
            i += 1

        f.func_code = code.to_code()
        return f
    return decorator

Und die Dekoratoren können dann wie folgt benutzt werden:

import nonlocal

@nonlocal.outer("a")
def spam():
    a = 23

    def getter():
        return a

    @nonlocal.nonlocal("a")
    def increaser(n):
        a += n

    return (getter, increaser)

g, i = spam()
assert g() == 23
i(19)
assert g() == 42

Dabei ist anzumerken, dass dabei nicht alle Fälle abgedeckt sind und außerdem davon ausgegangen wird, dass die äußere Funktion bereits Cell-Objekte für die nonlocal-Namen benutzt (in diesem Fall wird dies ausgelöst durch die getter()-Funktion).

Außerdem wird Code-Klasse von Aaron Gallagher benutzt, die bereits aus einem vorigen Blogeintrag bekannt ist:

class Code(object):
    @classmethod
    def from_code(cls, code_obj):
        self = cls()
        self.code_obj = code_obj
        self.cellvars = list(code_obj.co_cellvars)
        self.freevars = list(code_obj.co_freevars)
        self.names = list(code_obj.co_names)
        self.nlocals = code_obj.co_nlocals
        self.varnames = list(code_obj.co_varnames)
        self.consts = list(code_obj.co_consts)
        ret = []
        line_starts = dict(dis.findlinestarts(code_obj))
        code = code_obj.co_code
        labels = dict((addr, Label()) for addr in dis.findlabels(code))
        i, l = 0, len(code)
        extended_arg = 0
        while i < l:
            op = ord(code[i])
            if i in labels:
                ret.append(('MARK_LABEL', labels[i]))
            if i in line_starts:
                ret.append(('MARK_LINENO', line_starts[i]))
            i += 1
            if op >= opcode.HAVE_ARGUMENT:
                arg, = short.unpack(code[i:i + 2])
                arg += extended_arg
                extended_arg = 0
                i += 2
                if op == opcode.EXTENDED_ARG:
                    extended_arg = arg << 16
                    continue
                elif op in opcode.hasjabs:
                    arg = labels[arg]
                elif op in opcode.hasjrel:
                    arg = labels[i + arg]
            else:
                arg = None
            ret.append((opcode.opname[op], arg))
        self.code = ret
        return self

    def to_code(self):
        code_obj = self.code_obj
        co_code = array.array('B')
        co_lnotab = array.array('B')
        label_pos = {}
        jumps = []
        lastlineno = code_obj.co_firstlineno
        lastlinepos = 0
        for op, arg in self.code:
            if op == 'MARK_LABEL':
                label_pos[arg] = len(co_code)
            elif op == 'MARK_LINENO':
                incr_lineno = arg - lastlineno
                incr_pos = len(co_code) - lastlinepos
                lastlineno = arg
                lastlinepos = len(co_code)

                if incr_lineno == 0 and incr_pos == 0:
                    co_lnotab.append(0)
                    co_lnotab.append(0)
                else:
                    while incr_pos > 255:
                        co_lnotab.append(255)
                        co_lnotab.append(0)
                        incr_pos -= 255
                    while incr_lineno > 255:
                        co_lnotab.append(incr_pos)
                        co_lnotab.append(255)
                        incr_pos = 0
                        incr_lineno -= 255
                    if incr_pos or incr_lineno:
                        co_lnotab.append(incr_pos)
                        co_lnotab.append(incr_lineno)
            elif arg is not None:
                op = opcode.opmap[op]
                if op in opcode.hasjabs or op in opcode.hasjrel:
                    jumps.append((len(co_code), arg))
                    arg = 0
                if arg > 0xffff:
                    co_code.extend((opcode.EXTENDED_ARG,
                        (arg >> 16) & 0xff, (arg >> 24) & 0xff))
                co_code.extend((op,
                    arg & 0xff, (arg >> 8) & 0xff))
            else:
                co_code.append(opcode.opmap[op])

        for pos, label in jumps:
            jump = label_pos[label]
            if co_code[pos] in opcode.hasjrel:
                jump -= pos + 3
            assert jump <= 0xffff
            co_code[pos + 1] = jump & 0xff
            co_code[pos + 2] = (jump >> 8) & 0xff

        return types.CodeType(code_obj.co_argcount, self.nlocals,
            code_obj.co_stacksize, code_obj.co_flags, co_code.tostring(),
            tuple(self.consts), tuple(self.names), tuple(self.varnames),
            code_obj.co_filename, code_obj.co_name, code_obj.co_firstlineno,
            co_lnotab.tostring(), tuple(self.freevars), tuple(self.cellvars))

Wed 06 October 2010

Variable Tab-Breite in Python

In Python 2 kann man dem Tokenizer mittels Kommentaren mitteilen, wie breit ein Tab ist:

# :ts=4
if 1:
    if 0:
        print 1
     print 2 # hard tab here

Führt man den Code aus, wird 2 ausgegeben. Entfernt man den Kommentar, wird nichts ausgegeben.

Sat 06 March 2010

Every language has its flaws - C++

Scott Meyers auf die Frage, welche drei Dinge er am wenigsten mag in C++:

I'd like to answer this question with "complexity, complexity, complexity!", but naming the same thing three times is cheating. Still, I think that C++'s greatest weakness is complexity. For almost every rule in C++, there are exceptions, and often there are exceptions to the exceptions. For example, const objects can't be modified, unless you cast away their constness, in which case they can, unless they were originally defined to be const, in which case the attempted modifications yield undefined behavior.

Das gesamte (zugegebenermaßen schon etwas ältere) Interview gibt es hier.

Thu 31 December 2009

Der "läuft gegen"-Operator in C++

#include <iostream>

int main(int argc, char **argv)
{
    int x = 10;

    // x goes to 0
    while (x --> 0)
        std::cout << x << std::endl;
}