Category: Architecture & Engineering

Three Kinds of Typed Languages

There are a lot of questions on stackoverflow about difference between static and dynamic typing, e.g. why is Smalltalk considered dynamically typed. Here is my very own perception on the subject.

Background: Type systems are conservative static analysis

Here is the definition of a type system from Types and Programming Languages:

A type system is a tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute.

The “kind of values they compute” is usually referred as a “type”. What the type system usually proves is that the program will not be “stuck”. Thinking of the semantics of the programming language as a set of evaluation rules, it means the evaluation of the program will terminate.

int x = 0;
if (false) {
   x = "hello";
} else {
   x = 1;
}

The above program will actually always terminate, since the true-branch will never be executed. However, it would fail to type-check, since the type system rejects x=”hello”. Reaching this statement would stuck the evaluation, since there is no consistent evaluation rules for it (unless the semantics define coercion rules). Type checking is a conservative analysis.

Run-time checks

For very simple language, evaluation rules do not perform run-time checks, and type checking usually means that the program terminates without run-time error. For any realistic program, there will be run-time checks for certain evaluation rules.

int x = 10;
int y = 0;
return x / y

One of the simple evaluation rules that requires a run-time check is integer division. Dividing by zero is not possible. If this situation occurs, a run-time error occurs. Run-time errors can either lead to the abrupt termination of the program, or the semantics can define error handling. Null pointers are other typical run-time checks.

Run-time type tags

Certain languages do not need run-time type tags to distinguish different kinds of structure in the heap. Evaluation rules depend on the static type solely, and the heap is flat array of unstructured data. (Lambda calculs with record and references, and C-like languages fall in this category, I guess.)

However, in many languages, run-time type tags are needed to distinguish different kinds of structures in the heap. Run-time type tags are requires to implement polymorphic behavior. In object-oriented language, this corresponds to interface and subclasses. The specific type of an object might be unknown, but it conforms to a type that is known statically.

Run-time type checks

Evaluation rules in such language perfrom run-time type checks. The check is necessary to “dynamically dispatch” the operation accordingly to the run-time type. Type systems can prove that the run-time type check will never fail, that is, the operation can always be dispatched, and the execution will not be stuck.

Three kinds of languages

The evaluation rules of the programming language, which define its semantics, can use static types and/or run-time types.

  1. Run-time type only — Let us consider Smalltalk. Smalltalk’s core semantics is entirely defined by the dynamic types: When you send a message to an object what must be executed depends on the dynamic types of the receiver. If a message can not be dispatched, the program is stuck. In practice, the error is reified into message not understood exception.
    The semantics of the language does not need a type system/type checking. You can however type check the code to guarantee that there will be no such run-time type error, see Strongtalk. With type inferrence, only minimal static types will be needed.  This is the approach that pluggable types promotes. The type system is optional.
  2. Static type only — A language with object, but without subtyping nor inteface. Such a language would not need type information at run-time. The heap is flat array of data whose type/structure can not be discovered at run-time. With proper information in the code about the expected type of objects, you can still define a valid semantics for the language: when you send a message to an object you know what must be executed since the type in statically known in the code. By definition such a language could not have dynamic dispatch and inheritance polymorphism. (The typed lambda calculus without subtyping is maybe of this kind).
  3. Static and run-time types — Let’s consider Java. It mixes both static and run-time types. Objects have dynamic types for dynamic dispatch and polymorphism. However,the exact semantics of the language rely also on static types. For instance, method overloading in Java depends on the static types of the paramters. A class can define methods print( A a ) and print( B b ). The semantics of anObject.print( anotherObject ) depends on the static type of anotherObject: when you send a message to an object, you define what must be executed depending on the dynamic type of the receiver, and the static types of the parameters. 

Note that by “static type”, I don’t mean the type is explicitely in the source. The static type is the result of a static analysis, and can be inferred. Inferred types can be the union of explicit types. The static types can be though of a “parametrization” of the evaluation rules.

function printHello( object ) {
     object.hello();
}
function printHelloA() {
     A a = new A();
     printHello( a );
}
function printHelloB()  {
     B b = new B();
     printHello( b );
}
Even if A and B are distinct types (not implement an interface or so), a type system can still figure out that printHello in passed either A or B and that both implement hello().

First-class functions

A language with first-class function can implement dynamic dispatch even without interface nor subclassing. Indeed, an object can store function that a client can access to emuate polymorphism. Functions have a type and are polymorphic by nature.
More pointers

The Object Cube

There’s the lambda cube, and the big data cube. Why not a an object cube? Here would be three axis:

  1. Object Existence — The object existence dimension can range for everything ia a mutable object, to more distinctions between mutable and immutable objects, or objects and values. Existence, identity and mutability are tightly related (“I have an identity therefore I exist”).
  2. Object Composition — The object composition dimension can range from no composition at all (an object define its unique behavior without any possiblity of reuse) to behavior reuse with class-based inheritance or prototype-base delegation, possibly with additional mechanisms like mixin and traits. Essential, the machinery of reuse implies late-binding and certain lookup rules. Composition is then also related to virtualization (of methods, classes). It is also about procedural abstraction.
  3. Object Interaction — The object interaction dimension can range from complete freedom (any object can interact with another object) to more displined approach with control visibility via module and namespaces, or behavioral restriction (read-only, priviledges, aliasing).

Let us consider inheritance. Inheritance itself is a composition feature: the behavior of a class can be flattened and duck typing is possible. The type system that enforce inheritance is an interaction feature that prevents run-time type errors, but also duck typing. Inheritance does not relate closely to existence (but hierarchies must be sound wrt to existence).

Object modularity could have been a way to subsume composition and interaction — making the cube a square — but composition and interaction capture two different kinds of features: composition is about defining the exact behavior of one object possibly involving other entites, while interaction is about the behavior of objects when two of them communicate. Both composition and interaction might rely on namespaces and scoping mechanisms, though. These mechanisms have no mean in itself, they serve a cause that is either composition or interaction.

More

2017.09.21: there’s also the Scale Cube!

Writing Immutable Objects with Elegance

Edit: This blog post has been turned into a draft paper.

Today, I got burned with design issues of Smalltalk’s dictionaries. They implement object comparison = using value equality, but are at the same time mutable. The internal state of a dictionary consists of an array of associations. In addition to problems of equality, the the internal state can be accessed and aliased with Dictionary>>associationsDo: and Dictionary>>add:

We should instead have an immutable dictionary using value comparison, and a mutable dictionary using identity comparision. Mixing styles is too dangerous. For the mutable dictionary, the internal state should never be accessible and data should be copied to ensure no dependencies on mutable state are established.

In an old post I rant on the conflict between the imperative object paradigm that promotes mutable state, and the functional paradigm that promotes immutable data structures. It is mostly a problem of readability, though.

Assignment Syntax

To make the use of immutable objects more readable, we could actually generalize operator assignment syntax like +=, -=, <<= to any message.  Postfixing a message with = would imply that the reference pointed to the receiver of the message is updated with the value of the message.

aReference message=: 5            
<-->      
aReference := aReference message: 5
aDictionray at: key put=: value   
<-->      
aDictionary := aDictionary at: key put=: value

When the selector has multiple arguments, the prefix comes at the very end. This is simple, efficient syntactic suggar.

What about self-sends? Accordind to the previous examples, self would be updated with the value of message. While it might sound counter-intuitive or plain absurd, this is what we need:

Point>>moveX: offsetX y: offsetY
self x=: self x + offsetX. 
self y=: self y + offsetY.
^ self

Assuming #x: and #y: return copies of the objects, wihth this semantics, the reference to self on the last line corresponds to the last copy created.

The only difference between self-sends and regular sends is the implicit contract that is assumed for the method. In the regular case, the message send can return any object. Any invocation of the returned object will happen with a regular send that will in the worst case raise a message not understood exception. For self-sends to work as in the example above, messages #x: and #y: must return instances of Point, so that the activation frame can be updated correctly. Updating the activation frame rebinds self to the new object, but preserves the temporary variables.

(I believe this would have an incidence on closures. More investigations are needed. The precise semantics could maybe be simulated with continuations)

Copy syntax

The previous proposal still leaves the burden of copying the objects to the developers. In the previous examples, #x: , #y: and #at:put: would need to first clone the receiver (self), then update it.

Point>>x: newX
^ ( self clone ) basicX: newX ; yourself.

Ugly, right? Following a similar syntactic approaches, message sends could be prefixed with % to indicate that the message must be delivered to a clone of the receiver:

aReference %message: 5 <--> aReference clone message: 5

We know that cloning is broken. However, it is not the subject of this post, so we will assume that we have a reasonable implementation of #clone. With % and = we have all ingredient to implement immutable structures easily.

Point>>x: newX
  self basicX: newX

Point>>moveX: offsetX y: offsetY
self %x=: self x + offsetX. 
self %y=: self y + offsetY.
^ self

(The accessor Point>>x is actually superfluous, since it is similar to basicX. It serves as example only.)

For an even more concise syntax, a third prefix/postfix could be introduced.

aReference ~message: 5 <--> aReference %message=: 5

Nested Objects

The proposed syntactic suggar has limited benefits for more complex mutation of objects with nested objects. Let’s consider an immutable circle with an immutable point as center.

Circle>>moveX: offsetX y: offsetY
   self ~center: (self center %moveX: offsetX y: offsetY )
  ^ self

But what we would really like to write is

Circle>>moveX: offsetX y: offsetY
   self center ~moveX: offsetX y: offsetY
  ^ self

Handling this situation so that the receiver “self center” is replaced with the new point, implies first the replacement of “self” with a new circle. The replacement of the receiver “self center” (that is not an L-value) could be achieved if by convention the corresponding setter is used. The above code would then execute implicitely “self ~center: xxx” to replace “self center”. This corresponds to the intended behavior. In other words,

self a ~m: args <--> self ~a: (self a %m: args)
self a b ~m: args <--> self ~a: (self a %b: (self a b %m: args))
etc.

The ~ can appear only before the last message send. The statement “self a ~b m: args” would be ill-defined.

More Links

Transformation for Class Immutability

Features Interaction

Hoare’s famous paper “Hints on Programming Language Design” distinguishes two main aspects of language design:

  • Part of language design consists of innovation. This activity leads to new language features in isolation.
  • The most difficult part of language design lies in integration: selecting a limited set of language features and polishing them until the result is a consistent simple framework that has no more rough edges.

I will try to keep here a list of inspiring articles that illustrate this two parts, especially edge cases in integration of individiual features.You can also follow Shoot Yourself In The Foot for examples of unexpected problems resulting from the language design rationale.

Development Hygiene

I recently attented three keynotes: Alan Kay and Andreas Kuehlmann at TOOLS and Jeff Kramer at ICSE. Hearing these talks, the software industry seems to be stuck: we don’t know how to move beyond manual development and testing of fine-grained software artefacts. However, as software engineering matures over time, a body of best practices emerges that increases quality of development. For instance, Jeff Kramer showed that certain ideas from the architecture community had indirectly made their way to industry under another form, e.g. dependency injection.

Andreas Kuehlmann used the word hygienic to refer to teams with sound engineering practices. The wikipedia definition of hygiene is a “set of  practices employed as preventative measures to reduce the incidence and spreading of disease”. High hygiene standards favor clean code. Assertions, contracts, refactoring are examples of hygienic practices. Hygienic practices lower the risk that your software become a drity pile of code. I like this analogy with health.

Progress in health promotion didn’t happen in one day. Medical and everyday practices such as sterilization, quarantine, treatment of wastes, dental care take took time to be established. Next to these practices, the healthcare industry enjoyed several breakthrough such as the creation of vaccines, or organ transplants that enabled this remarkable progress. Progress in development is similar to progress in healthcare.

  • Testing hygiene. Unit testing is similar to the daily routine of brushing ones teeth after each meal. It’s a defacto standard practice. Testing hygiene prevents bugs.
  • Code quality hygiene. IDE with code styling enforcement prevent unreadable code from spreading.
  • Modularity hygiene. A vast set of principles help keep software modular and prevent coupling and big balls of mud.
  • I/O hygiene. Sanitize your inputs and protect yourself from a malicious external environment. Don’t disclose sensitive information to the outside.
  • Monitoring hygiene. The first step to stay healthy is to identify problems and remedy before it’s too late. Yearly check-ups are becoming more and more common to detect symptoms of diseases. The same is true for applications, with monitoring, stress tests, and periodic reviews.

Hygiene refers to daily common pratices. Healthcare directly improves with improvement in hygiene, but also needs expert at time. When somebody is sick, he is sent to the hospital to follow a cure. For software, when an unreliable component is detected, it is put in quarantine, then analyzed and fixed with proper tools and techniques.  Expert troubleshooting is the equivalent of surgery.

Finally, what makes software remarkable is that similarly to organisms, software is grown, not built. Also, organisms and software are highly dynamic systems. This makes the analogy even stronger.

Hygienic programmers grow clean code and run healthy software.

MORE

Sandboxed Evaluation

JSON is a data exchange format, and a the same time is valid javascript. You don’t need a parser to read them, and you can use the almighty eval to interpret the data. This is however a security breach. Malicious JSON data could be provide and would be evaluted without further notice. Parsing is therefore still necessary to validate the data. There’s nothing really new there: reflection and security are known to be orthogonal.

It doesn’t need necessary to be the case, though. Reflection could be limited so as to allow what is necessary and deny malicious actions. In the case of JSON evaluation, one should prevent the access to global data, and the creation of new functions. That is possible, e.g. with a custom first-class interpreter. The data might still not be valid JSON data from point of view of the data format, and might contain expressions. More advanced “security” policies could specify execution protocols that would be forbidden, so as to prevent the executions of certain expression, or sequences of expressions.

But then comes the question of error handling. Isn’t it “too late” to catch errors at run-time? An error–even if cought in time–might leave the system in a invalid transient state from which it is hard to recover. Validating the data statically prior any execution seems therefore an easier approach. This is for instance the approach taking by the Java platform: mobile code is verified when loaded.

Checking for potential errors statically is however more restrictive than checking for errors at run-time. Similarly to type systems, valid programs or data might be rejected because of the conservative nature of static checking.

Going back to a dynamic perspective on security, we need a way to (1) catch errors at run-time and (2) recover from errors at run-time. To provide the same level of security as its static counterpart, such an approach should make sure that nothing can happen at run-time that can not be undone. Recovery blocks, transactional memory, and first-class worlds are all techniques to enable undo easily.

What can be recovered must match what is allowed. Undoing changes to memory will not be enough if one can read from I/O streams ; either I/O operations should be denied, or the recovery mechanism should be strong enough to safely undo I/O read and write if needed. Spawning threads might be allowed, if we are able to detect and escape from infinite loop and reliably cancel execution of untrusted code.

Let’s take for instance that case of Java Enterprise Edition (JEE). Applications deployed on JEE application server must obey such specific restrictions. Most constraints arise from the transactional nature of EJBs, and the fact that clustring should be transparent. JEE applications run in a managed environement and should not spawn threads, access static data, performing blocking I/O, etc. they should be side-effect free. The sandboxing facilities of the JVM do not suffice to enforce these constraints, and many of them are conventions. The run-time itself does not prevent messing with the infrastructure.

We need a configurable runtime with adequate programming language abstractions to define and enforce security policies at various level of granularities. Such a runtime should be flexible enough to enforce the safe evaluation of JSON data, and the safe execution of JEE applications.

On Parallel Class Families

I discussed yesterday with Raffael Krebs, a master student at SCG, who was disappointed of his design in Java that lacked extensibility. The main problem was that he wanted parallel class hierachies, which you can’t do easily in Java.

This problem isn’t new. Let’s illustrate the problem and explore a bit the various design in pure Java, then with existing language extension.

Below is a sample situation. The core of the model is composed of Document, Item, Text and Image. The Reader reads data from a file and creates the model. The client uses the model. To be generic, it must be possible to specialize the model with as little effort as possible, that is, provide reuse in a natural way. One would like conceptually to specialize (that is, subclass) the model for instance for HTML documents.

This conceptual view can not be achieved with Java. There are several problems: (1) multiple inheritance is not supported, (2) the Reader class still references the core model and will not create instance of the more specialized one, and (3) in most statically-type languages, parameters in a subclass must be covariant to those in its superclass.

The two first problems can be circumvented with interfaces and factories. The third one might require a downcast in add(), if specialized classes have added methods. If only existing methods have been overriden, traditional polymorphism is enough.

Generics provide a partial solution to the problem. Document can accept a parameteric type <A extends Item>, so that HtmlDocument can be defined as an extension of Document<HtmlItem> (see this answer for an example). The downcast in method add() disappears. Item is however abstract, and the system assumes there are two implementations of it, Text and Image. With generics, the class Document can not create instances of these with regular instantiations new Text() or new Image(). First it would not comply necessary with the parametric type <A extends Item>, second, these instantiations would not be rewired correctly to their corresponding class in the other family. If classes were first-class, one could at least define abstract static factory methods createText() and createImage() in Item. This is however not  possible in Java, and static method can not be overriden, because classes are not first-class.

In a dynamicaly typed language, the usage of interface vanished, as well as the third issue. However, in both case problem (1) and (2) remain.

The lack of multiple inheritance in this case leads to code duplication between the classes for which not inheritance relationship exist. To avoid such code duplication, delegation could be used and an instance of HtmlText could delegate to an instance of BaseText. As pure delegation is not supported, this require writing boilerplate forwarding methods, which is still clusmy. Another way to avoid code duplication would be to factor the duplicated code into traits or mixin that can be reused among unrelated classes.

No matter what, this design is ugly–and it is really found in practice.

Revisiting the three problems

The  problems discussed before can be rephrased into three separated questions:

– How can the reader produce the right kind of document (either basic, or html) without invasive changes?

– How can variations of a class hierarchy be created with minimal efforts and no boilderplate code ?

– How can the type system be aware of logical relationship between types, e.g. HtmlDocument always goes with HtmlItem?

The fourth problem

One fourth problem not depicted but that happens in practice, is that two class hierarchy relate to each other, but in slightly incompatible ways. This typically happens due to software evolution, when method are renamed, signature are changed, etc. An example would be to change the “data” in Item from binary byte[]  to base64 string. While certain kinds of changes can be accomodated by providing convertion functions (they act as wrapper), this bloats the design and prevent clean evolution.  Sometimes it is impossible to create an inheritance relationship between the two variants of the classes, which  means that whole graphs must be adapted back and forth from one representation to the other. We state the fourth problem as follows:

– How can graph of objects be converted from one logical representation to another easily, whithout that the convertion logic bloats the code?

The fifth problem

One fifth problem not discussed so far is actually a requirement:

– How can the new families be introduced a posteriori, without entailing modification or invalidation of exisitng code.

This problem is usually referred to as modularity.

Language constructs

These problems are clearly related to each others, as is showed by the example.  A definitive solution to all three of them is to my knowledge still not available, but there has been progress in programming language to provide means to tackle part of them.

  • Design patterns (strategy, factory)
  • Generics
  • Static & dynamic reuse mechanisms (delegation, traits, talents)
  • Family polymorphism
  • Virtual classes (newspeak/gbeta, dependency injection, first-class class)
  • Object Algebras
  • Local rebinding (classbox)
  • Open classes
  • Multi-dimensional dispatch (subject-oriented programming, context-oriented programming, worlds, namespace selector)
  • Non-standard type coercion (translation polymorphism in Object Team & lifted Java, expander)
  • Type versioning (type hot swapping, upgradeJ, revision classes)

It seems to me there is room for something actually missing that would solve the problem depicted above–or myabe it exist but I am not aware of it?

Links

Ownership for Dynamic Languages

Edit: the idea presented in this post was worked out into a consistent language feature and accepted for publication.

Ownership type systems have been designed for statically typed languages to confine and constraint aliasing, which in turn increases security and safety. Ownership type systems are conservative, and can only enforce properties that are known to hold globally and statically.

Rather than taking a static view on ownership, a dynamic view would be more natural–and accurate–and could also be applied to dynamic languages. The pendent of static typing in dynamic languages is testing. Ownership violations would raise run-time errors. The system would need to be tested to ensure it is free of ownership violation. This bears resemblance with contracts, and ownership could be seen as special kind of run-time contracts. Also, similarly to contracts, once the system has been exhaustively tested, run-time ownership checks could be disabled.

The ownership relationship between objects could be changed at run-time. While we can expect that most of the time, the owner of an object remains the same and is known at object creation-time, this must not necessary be the case. Whether an object can have multiple owners or not is an open question. If we restrict the system to one owner per object, the syntax could be as simple as:

anObject := MyClass newOwn. "create a new instance that will be owned by self"
anObject := MyClass new ownedBy: anOwner. "assigned an arbitraty owner"

Of course, only an ower that satifies the ownership constraint can be assigned, not any object. Once assigned an owner, the system would enforce no aliasing happen that would violate the ownership constraint. In practice, this means that assignments, and parameter passing must be checked at run-time. This is not trivial without entailing a high overhead in space and time.

Combined with resumable exceptions, ownership violations might not be fatal, and could be considered as special events one can catch when objects escape their owners. For instance, when an object escapes its threads, it could be adapted to become thread-safe, or objects could be frozen (i.e. made read-only) when then escape their owner. An variant would be be able to specify a treatment block per ownership relationship, that would be executed if the constraint is broken. By default, objects would have flag that indicates if the contraints holds (for sure) or not. Raising exception or other strategies would be built on top of that.

MyClass new ownedBy: anOwner ifViolated: aBlock. "treatment if constraint is violated"
aFlag := anObject isOwnershipEnforced.

There are few interesting questions around this run-time perspective on ownership:

  • Can certains patterns be better expressed with ownership?
  • Does the ownership information help program understanding?
  • Do objects have one natural owner in practice?
  • Do run-time ownership checking help spot bugs or increase safety?
  • How can run-time ownership checking be made practical from point of view of performance?

Ah! As usual, more questions than answers…

Implementation of Semaphores

For the need of the experimental Pinocchio research VM, we needed to add support for threading and concurrency. We implemented green threads, a la Squeak and there is then no “real” multi-core concurrency going on. The VM relies on AST interpretation, instead of bytecode. With green threads, the interpretation of an AST node can always be considered atomic: no two AST node can be interpreted concurrently. This is unlike Java and its memory model, where individual bytecodes can be interpreted concurrently, possibly with nasty side-effects (e.g. manipulation of long is not atomic). Thread preemption can happen anytime between AST nodes evaluation.

How can we add support for semaphores?

The pharo design

The pharo design can be informally summarize like this: when a semaphore is instantiated, its counter is set to one. Whenever a block needs to be evaluated in an exclusive way, the counter is checked. If the counter > 0, it is decreased and the block is evaluated. If the counter = 0, the thread is suspended an added to the list of threads currently waiting on this semaphore. When the critical block has been evaluated, the list of suspended threads is checked. If there are not suspended threads, the counter is incremented to 1. Otherwise, one of the suspended thread is picked and resumed.

This implementation explains why Semaphore extends LinkedList. I’m not sure it’s the best design decision, because it’s not conceptually a list and the list protocol should not be exposed by a semaphore. It uses inheritance for implementation reuse, but composition would have been just fine here if the semaphore was internally holding a linked list (and maybe use a pluggable ownership type system to check that the list does not leak out of the semaphore…).

Also, semaphores must be created using the forMutualExclusion factory method. This method instantiates and initialize the semaphore to allow exactly one execution at a time (hence the term mutual exclusion), but nothing would prevent you from initializing the semaphore so that up to N blocks can be executed concurrently.

The respective code for wait and signal (which respectively decrement and increment the counter) are:

wait
 excessSignals>0
 ifTrue: [excessSignals := excessSignals-1]
 ifFalse: [self addLastLink: Processor activeProcess suspend]
signal
 self isEmpty
 ifTrue: [excessSignals := excessSignals+1]
 ifFalse: [Processor resume: self removeFirstLink]

They are however implemented as primitives. I suspect this is not for performance reason, but for the sake of concurrency correctness. These operation themselves need to be atomic. Implemented in Smalltalk, the thread could be preempted during one of these, breaking the semaphore’s design.

The test-and-set design

These two methods and the internal counter suggest that an implementation relying on more generic concurrency primitive is possible. Typical concurrency primitives for this are test-and-set or compare-and-swap.
 We’ve added a primitive testAndSet to Boolean, and implemented the Semphore with busy waiting (also sometimes called spin lock):
 
 critical: aBlock
 | v |
 "we spin on the lock until we can enter the semaphore"
 [ lock testAndSet ] whileTrue: [ PThread current yield ].
 "we evaluate the block and make sure we reset the flag when we leave it"
 [ v := aBlock value. ] ensure: [ lock value: false ].
 ^ v.

The design could be improved to no use busy waiting. Instead of yielding, the thread would be suspended and added to a list. In the ensure block,  the flag would be reset and one of the thread would be resumed. The resumed thread would however still need to testAndSet the lock to prevent that no other thread has entered the semaphore in the meantime, possibly delaying the thread forever. So if fairness is required, this algorithm is not optimal.

The bakery design

You can also implement critical section without the support of other concurrency primitives. The most famous one is probably Lamport’s bakery algorithm:

What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion.  Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location.  So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion.  Such an algorithm cannot really be said to solve the mutual exclusion problem.  Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable–that you could implement mutual exclusion only by using lower-level mutual exclusion.

In our case with green threads, read and write are atomic because they are single AST nodes, but this isn’t necessary the case.

Here ends this little trip into basic concurrency. There is a rich litterature on the topic — which is truely fantastic — and we might explore and implement more sophisicated abstractions later on.

References

The Java Memory Model
Thread Synchronization and Critical Section Problem
A New Solution of Dijkstra’s Concurrent Programming Problem

Anti-if Programming

If are bad, if are evil. If are against object-oriented programming. If defeats polymorphism — These popular remarks are easier said than enforced.

Ifs can pop up for various reasons, which would deserve a full study in order to build a decent taxonomy. Here is however a quick one:

  • Algorithmic if. An algorithmic if participate in an algorithm that is inherently procedural, where branching is required. No much can be done for these ones. Though they tend to increase the cyclomatic complexity, they are not the most evil. If the algorithm is inherently complex, so be it.
  • Polymorphic if. A class of object deserve some slightly different treatment each time. This is the polymorphic if. Following object oriented principles, the treatment should be pushed in the corresponding class, and voila! There are however million of reasons why we don’t want the corresponding logic to be in the class of the object to treat, defeating object oriented basics. In such case, the problem can be alleviated with visitor, decorator, or other composition techniques.
  • Strategic if. A single class deals with N different situations. The logic is still essentially the same, but there are slight different in each situation. This situation can be refactored with an interface, and several implementations. The implementations can inherit from each other, or use delegation to maximize reuse.
  • Dynamic if. Strategic if assumes that the situation doesn’t change for the lifetime of the object. If the behavior of the object needs to change dynamically, the situation becomes even more complicated. Chances are that attributes will be used to enable/disable certain behavior at run-time. Such if can be refactored with patterns such as decorators.
  • Null if. Test for nullity is so common that it deserves a special category, even though it could be seen as a special case of another category.  Null if can happen to test the termination of an algorithm, the non-existence of data, sanity check, etc. Various techniques exist to eradict such if depending on the situation: Null Object pattern, add as many method signature as required, introducing polymorphism, usage of assertions, etc.

A step-by-step Anti-If refactoring

Here is a step-by-step refactoring of a strategic if I came accross . I plan to send it to the anti-If compaign and took then the time to document it. The code comes from the txfs project.

Let’s start with the original code:

public void writeFile (String destFileName, InputStream data, boolean overwrite)
throws TxfsException
{
FileOutputStream fos = null;
BufferedOutputStream bos = null;
boolean isNew = false;
File f = new File (infos.getPath (), destFileName);
if ( !overwrite && f.exists () )
{
throw new TxfsException ("Error writing in file (file already exist):" +
destFileName);
}

try
{
if ( !f.exists () )
{
isNew = true;
}
DirectoryUtil.mkDirs (f.getParentFile ());
try
{
Copier.copy (data, f);
}
finally
{
if ( isNew && isInTransaction () )
{
addCreatedFile (destFileName);
}
IOUtils.closeInputStream (data);
}
}
catch ( IOException e )
{
throw new TxfsException (“Error writing in file:” + destFileName, e);
}
}

Not very straightforward, isn’t it? The logic is however quite simple: if the overwrite flag is set, file can be written even if it already exists, otherwise an exception must be thrown. In addition to that, if a transaction is active, the file must be added to the list of created file, so that they can be removed in the transaction is rolled back later.  The file must be added even if an exception occurs, for instance if the file was partially copied.

What happens is that we have two concerns: (1) the overwrite rule and (2) the transaction rule.

Let’s try to refactor that with inheritance. A base class implements the logic when there is no transaction. And a subclass refines it to support transactions.

public void writeFile (String destFileName, InputStream data, boolean overwrite)
throws TxfsException
{
FileOutputStream fos = null;
BufferedOutputStream bos = null;
boolean isNew = false;
File f = new File (infos.getPath (), destFileName);
if ( !overwrite && f.exists () )
{
throw new TxfsException ("Error writing in file (file already exist):" +
destFileName);
}

try
{
// if ( !f.exists () )
// {
//    isNew = true;
// }
DirectoryUtil.mkDirs (f.getParentFile ());
try
{
Copier.copy (data, f);
}
finally
{
// if ( isNew && isInTransaction () )
// {
//     addCreatedFile (destFileName);
// }
IOUtils.closeInputStream (data);
}
}
catch ( IOException e )
{
throw new TxfsException (“Error writing in file:” + destFileName, e);
}
}

The transaction concern is removed from the base method. The overridden method looks then like:

public void writeFile (String destFileName, InputStream data, boolean overwrite)
throws TxfsException
{
try
{
super.writeFile( destFileName, data, overwrite );
}
finally
{
addCreatedFile (destFileName);
}
}

But we have then two problems: (1) we don’t know if the file is new, and it’s always added to the list of created file. (2) if the base method throw an exception because the file already exists and the flag is false, we still add it to the list of created file when we shouldn’t.

We could change the base method to have a return code (e.g. FileCreated and NoFileCreated). But return code are not generally a good solution and are quite ugly.

No, what we must do, is remove some responsibility to the method. We then split it into two methods createFile and writeFile. One expects the file to not exsits, the other the file to exists.

void writeFile (String dst, InputStream data ) throws TxfsException
void createFile (String dst, InputStream data ) throws TxfsException

(The method writeFile which takes the additional overwrite flag can be composed out of the two previous one )

So our simplified writeFile method looks like:

public void createFile(String destFileName, InputStream data)
throws TxfsException
{
try
{
super.createFile(destFileName, data);
}
finally
{
// we add the file in any case
addCreatedFile(destFileName);
}
}

Alas, there is still the problem that if super.writeFile fails because the file already exists, we add it to the list.

And here we start to realize that our exception handling scheme was a bit weak. The general TxfsException is rather useless: we need to refine the exception handling to convey sufficient information to support meaningful treatment.

void writeFile (String dst, InputStream data )
throws TxfsException, TxfsFileDoesNotExsistException

void createFile (String dst, InputStream data )
throws TxfsException, TxfsFileExistsAlreadyException

Here is then the final code:

public void createFile(String destFileName, InputStream data)
throws TxfsFileAlreadyExistsException, TxfsException
{
// I can not use a finally block because
// if failure happens because file already existed       
// I must not add it the list
try {
super.createFile(destFileName, data);
// we add the file if creation succeeds
addCreatedFile(destFileName);
}
catch (TxfsFileAlreadyExistsException e)
{
// we don't add the file if it already exists
throw e;
}
catch (Throwable e)
{
// we add the file in any other case
addCreatedFile(destFileName);
}
}
}

Conclusion

Anti-If refactoring is not so easy. There are various kind of ifs, some of which are ok, and some of which are bad. Removing ifs can imply changing the design significantly, including the inheritance hierarchy and the exception hierarchy.

A tool to analyze and propose refactoring suggestion would be cool, but for the time being, NoIF refactoring is probably in the hands of developers which can ensure the semantics equivalence of the code before and after the refactoring.

Links

http://www.technology-ebay.de/the-teams/mobile-de/blog/an-exercise-in-unconditional-programming.html