Software Architecture

Your Language is a Start-up

Watching the TIOBE index of programming language popularity is depressing. PHP and Javascript rule the web, despite the consensus that they are horrible; Haskell and Smalltalk are relegated to academic prototyping, but unanimously praised for the conceptual purity. How technolgy adoption happens is a puzzling question.

Evidences seem to suggest that what matters is to attract a set of initial users, and then expand. The initial offer needn’t be particularly compelling. As long as it wins on one dimension  maybe because it’s ambarassingly simple, or provides a very effective solution to a very specific problem it might attract early adopters. PHP won because of its simplicity to get things done; Javascript won because it was the first to provide a solution to make HTML dynamic. After initial success in a niche, the technology can evolve to attract more users. PHP and Javascript  evolved later to fix their initial design flaws. They are both now mature object-oriented languages.

The price for fixing initial flaws is however extraordinary high. Once a language feature is designed and made available, it’s cast in stone. Evolving a language while maintaining backward compatibility is extremelly challenging, but breaking compatibility and dealing with multiple branches isn’t much of an easy solution neither. Notorious examples of evolutions in Java are the Java Memory Model and generics. It took years of research to plan them, and years of availability to reeducate the community. C++ is still trying to catch up, and still lacks feature that we take for granted on some plateforms, e.g. a standardized serialization.

Surprisingly, when adoption happens, it might be from a difference audience than the one expected.  “Languages designed for limited or local use can win a broad clientele, sometimes in environments and for applications that their designers never dreamed of.”  say the authors of Mastermind of programming. This is definitively true. Java was initially designed for embedded systems, but succeed instead in the enterprise. Javascript was thought as a thin veneer for web pages, but now powers the new generation of client-side web app and is even expanding to the server-side.

When a technology starts to decline after the adoption peak, don’t be too quick to claim it dead. It might enjoy an unexpected renaissance. Many have for instance claimed that Java was dead. They have failed however to recognize the the underlying JVM is a rocking beast, amazingly fast and versatile for those who know how to tame it. Nowadays, one of the best strategy to implement new languages is to leverage the JVM and provide interoperability with Java libraries. In turn, this massive adoption of the JVM by new language implementors is driving innovation in the JVM itself, which has been extended with new bytecode for languages other than Java. I doubt that James Gosling had anticipated this evolution of the platform.

Clearly, the key characteristics of a language are its syntax and semantics, since they define together its expressive power. Expressivity isn’t however the unique force at play for adoption. What a real-world check suggests is that expressivity is only one factor amongst many other technical and social factors. The ease of debugging or the existence of a friendly community could for instance turn out to more important for some users than the ease of writing code. Language designers typically understimate such factors, severly impeding their chances of success.

To foster adoption, one must also rekon that people are reluctant to change. What people are already familiar with must be taken in consideration: in 2008, mobile users wouldn’t have been ready for the minimalistic iOS 7 interface. They were however ready for the original skeuomorphic interface, and now that they have become familiar with it, they can get rid of the skeuomorphic ornaments. People don’t change for the sake of changing, they change to solve or problem, and they change only if the gain outweight the pain. For programming languages, the problem is productivity and the pain is learning a new platform. In 2013, developers might not be familiar enough with functional programming to adopt a pure functional language like Haskell, but they definitively are ready to adopt a hybrid language like Scala.

Together, these elements might help explain the failure of some great languages, for instance Lisp. Lisp is a beautiful programming language that offers amazing flexibility. For a skilled practitionner, lisp is a secret weapon. However, lisp does nothing particularly well out of the box. “Lisp isn’t a language, it’s a building material.”, dixit Alan Kay. Clojure, on the other hand, is a Lisp dialect with just enough direction to solve one very painful problem: writting concurrent code. Given that the problem is so painful, people won’t mind a few parenthesis to solve it. This choice paid off, and in 2012 Clojure moved in the “adopt” quadrant of Thoughwork’s technology radar.

The language business is a competitive business where idealism won’t prevail. For a language to be adopted, it must solve a problem for some early adopters, who will then create an attractive ecosystem that will convince the late majority. In other words: language designers should think of their language like a start-up.

Software Architecture

Thinking in Lifecycle

After having worked hard on a design I came once to a colleague to ask him his opinion about it. “Do you think I’ve decomposed the problem in the right way?” I said. He look at it and answered “You are mixing elements with different lifecycles”. I came back to my desk confused and worried.

What I understood later is that  every element in the system always has a lifecycle, be it objects in memory, data in the database, business logic in the code, build artifacts, design documents, or configuration properties. Too many times, the lifecycles are poorly understood or poorly managed. Elements with different lifecycles need to be able to change independently of each other’s. Your design should reflect these lifecycles.

Thinking in terms of lifecycle is a very powerfull design tool. Surprisingly, it isn’t particularly emphazised in the literature about software design and architecture. The closest would be the concepts of coupling and cohesion, which capture how changes ripple in the system. The single responsibility principle is also close, when formulated as “A class should have only one reason to change“.

I’m happy my colleague made me aware of this particular way of thinking and that I could add this design tool to my intelectual toolbox. It’s proved very valuable since then.

Software Architecture

Debunking Object-Orientation

What is an Object? What is the essence of the object pardigm? How do objects differ from other abstractions? What are their benefits? What are their pitfalls? Can we encode objects with lower building blocks? Should we have objects all the way down?

Some people think they are clever to observe that OOP has no formal, universal definition. Democracy, love and intelligence don’t either. — Tweet from Allain de Boton

Some thoughts:

And for the haters:

Software Architecture

The Cost of Volatile

Assessing the scalability of programs and algorithms on multicore is critical. There is an important literature on locks and locking schemes, but the exact cost of volatile is less clear.

For the software composition seminar, Stefan Nüsch and I decided to look at this topic. Essentially, we devised a benchmark where multiple threads would access objects within a pool. Each thread has a set of objects to work with. To generate contention, the sets could be fully disjointed, have partial overlap, of have a full overlap. The ratio of reads and writes per thread was also configurable.

On an AMD 64 Dual Core, the graph looks as follows:

bench_amd64On a i7 Quad Core, the graph looks as follows:

bench_i7We clearly see that different architectures have different performance profiles.

In future work, we could try to reproduce false sharing and assess the impact of other forms of data locality.

More details about the benchmark and methodology can be found in his presentation. The code in on github.

Here a some links about the semantics of volatile, and mememory management in general.

Software Architecture

Natural Queries

Programming language research is a quest for expressivity. The aim it enable the expression of complex computations in concise and intuitive ways.

The problem is that conciseness and intuitivity are usually conflicting. Expressivity is enabled by higher-order constructs which are hard to reason about. On one hand, functional languages enable the expression of complex computations concisely, but their intuitivity is low. Integrated query languages can help, though. On the other hand, imperative languages are very intuitive, but their expressivity is low.

Let’s assume you have time series. A sentence like “pick the average of values by intervals of 5 seconds” describes a non-trivial computation. This sentence in a natural language is both intuitive and concise. Dealing with such natural queries is challenging, but feasible. This is what facebook does. An important aspect of the features is that the system gives a feedback to the user about how it understood the query. The user can then rephrase or refine the query.

The same could be integrated into development environments. Instead of expressing computations with functions, developers would first give a shot at a natural description. It would be translated into functional code by the environment. Sample data would be generated to exemplify the query, serving both as immediate feedback for the correctness of the query, and later for unit testing. If the generated code is incorrect, it is refined by the developer. The icing on the cake: the original natural query is kept as a code comment.

Software Architecture

Debuggers: Theory and Practice

In “Not on the shelves“, Greg Wilson writes reviews about non-existing books, including one called “Debuggers: Theory and Practice”. It’s an entertaining and insightful read.

It made me curious about how such a book could look like and I gathered a selection of interesting articles about debugging and tried to organize them in a few sections. I wish I were more knowledable on the topic and had enough references to split section III into one section “exploring executions” and another one “strategies for debugging”.

Part I: Foundation

Chapter 1: Failures, Errors, Faults
Chapter 2: What is Debugging?
Chapter 3: Debuggers are Reflective Programs

Part II: Reproducing Bugs (Reproducing Failures)

Chapter 1: Every bug is a test not yet written
Chapter 2: Record and Replay
Chapter 3: Execution Synthesis
Chapter 4: Reproducing Crashes with Recrash

Part III: Fixing Bugs (Identifying Faults)

Chapter 1: The Art of System.out
Chapter 2: Asking Why Questions with the Whyline
Chapter 3: Scriptable Time-Travel Debugging with First-Class Trace
Chapter 4: Back-in-Time Alias Debugging
Chapter 5: Object-centric Debugger
Chapter 6: Debugging Concurrent Programs

Software Architecture

Why Smalltalk?

This is a question is occasionally asked by students and here is the answer.

We are not religious. This choice is not dogmatic. We do both research in programming languages and tool support for software evolution. In both cases Smalltalk is handy:

  • Programming language — Smalltalk is extermely uniform. Experimenting with a language change is faster in Smalltak, than say, Java or Ruby. Their syntax and sets of rules are bigger, which implies more work.
  • Tool Support — If you want to extend the environment with more browsers/views/features, you can do it easily. Also, tool support and meta-programming go well together. You don’t have a separation between application code and environment code. This makes the whole system very malleable to experiement with.

There exist other research platforms out there to ease experimentations in either category. They don’t match however with the versatility of Smalltalk, which remains thus a very competitive choice to consider. Usually, we mature our project to Java or Eclipse only after initial success in Smalltalk.

Smalltalk Anthology

Software Architecture

Understanding the Visibility of Side-Effects

This entry is all about the Java Memory Model and the happens-before partial order it formalizes.

The official specification of the JMM is authoritative but unreadable. Fortunately, there are useful resources around that aim at making it more accessible:

Happens-Before

The JMM defines a partial order called happens-before on all actions in the program. Actions are reads and writes to variables, locks and unlocks of monitors etc. The rules for happens-before are as follows:

  • Program order rule. Each action in a thread happens-before every action in that thread that comes later in the program order.
  • Monitor lock rule. An unlock on a monitor lock happens-before every subsequent lock on that same monitor lock.
  • Volatile variable rule. A write to a volatile field happens-before every subsequent read of that same field.
  • Thread start rule. A call to Thread.start on a thread happens-before any other thread detects that thread has terminated, either by successfully return from Thread.join or by Thread.isAlive returning false.

The happens-before partial order provides clear guidance about what values are allowed to be returned when the data are read. In other words: it formalizes the visibility of side-effect across threads.

A read is allowed to return the value of a write 1) if that write is the last write to that variable before the read along some path in the happens-before order, or 2) if the write is not ordered with respect to that read in the happens-before order.

Instructions can be reordered as long as the happens-before order is preserved. The code below

t1 = 1;
t2 = 2;
t3 = t1+t2;
t4 = 2*t1;

can for instance be be reordered as follows

t2 = 2;
t1 = 1;
t4 = 2*t1;
t3 = t1+t2;

If two threads shared data without using any synchronization, writes of a thread are considered unordered with respect to the other thread; according to condition 2), the execution is not deterministic and the writes of a thread might or might not be visible to the other thread.

Let us consider the two threads below, and one given execution:

  T1        T2

s = s+1 

          s = s+1

s = s+1 

The second increment might or might not see the previous increment in T1. Similarly, the thrid increment might or might not see the side-effect of the second increment.

In improperly synchronized programs, a read will return the value of one the possible matching writes, according to conditions 1) and 2). This corresponds to data races. In properly synchronized programs, a read has one unique ancestor write.

  T1        T2

lock m
  |
s = s+1 
  |
unlock m  
          \  
          lock m
             |
          s = s+1
             |
          unlock m
         /
lock m
  |
s = s+1 
  |
unlock m                  

Implementing Happens-Before

Conditions 1) and 2) specify that side-effects might or might not be visible consistently to theads in improperly synchronized programs. They enable the implementation to not read the shared memory all the time, either using CPU caches or compiler optimization. The specification does however never speak of specific implementation choice like caching and optimizations.

For instance, the code

t2 = s+1
t3 = s*2

could be rewritten as by a compiler optimization

t = s
t2 = t+1
t3 = t*2

, where t caches the value of the read to s.

Typically, the compiler will emit memory barriers to flush the CPU caches. The JSR-133 Cookbook provides guidance about implementation issues.

Data Races

Failure to properly synchronize accesses to shared data is called a data race. Inversely, a program is data race free if all accesses to shared state are synchronized. But what does data race freedom exactly mean?

Is the program data race free if,

  1. accesses to shared data happen within critical section?
  2. shared data is declared volatile?
  3. accesses to shared data are never concurrent?

Issues about the memory model are typically discussed using the double-checked locking pattern, and the “pausable” thread pattern. They provide only partial answer to these questions.

Point 1 is true. If the accesses to shared data are protected by the same cricital section, there is no possible data race.

Point 2 is true also. If you define variables as volatile, the side effect will be made visible to the other thread and there will be no data race. But remember: data race freedom does not mean that the behavior is correct. Consider the trival example below:

counter = counter + 1;

Making the counter volatile won’t suffice to ensure all increments are recorded.

Point 3 holds, but requires some clarification of the underlying assumptions (Answers to my stackoverflow question failed be clear cut and authoritative). Let us consider the situation when multiple threads manipulate an object X that is plain data, but alternate their temporal execution (so that X is never accessed concurrently) via another object Y that rely on concurrency control (wait, notify, synchronize). Should fields of object X be volatile or not?

If we assume that threads are synchronized using at least one the concurrency control primitive — an not just temporal alternance thanks, say, to a well-time sleep statements — this implies the alternate acquisition of at least a lock m, as for instance in:

while(true) {
    synchronized(m) { wait(); }
    counter = counter + 1;
    synchronized(m) { notify(); }
}

There is a happens-before dependency between the increment statement and the release of the wait lock. By construction, when the lock is released, exactly one thread will acquire it and wait again. So exactly one increment will happen-after the release of the wait lock. By consequence the increment is guaranteed to see only the value of the previous increment–no need of volatile.

More

Software Architecture

Reflecting on Reflection

(A cheap title, I know)

Reflection is one of these concept that constantly move from “obvious” to “puzzling” in my head–you feel like you have a firm understanding of it, and then suddently it evades, you feel puzzled by certain aspects, and ultimately confused about the whole thing. Why?

Two Perspectives

One of the first source of confusion is that reflection can be apprehended with two perspective: code as data, and meta-objects.

The first one, “code as data”, corresponds to the ability to dynamically convert code of the running software into data, and to dynamically evaluate data representing code. The code and its representation are however not connected: modifications of the data have no impact on the running system until data are evaluated. This perspective is best represented with language of the lisp family.

The second one, “meta-objects”, corresponds to the ability to expose meta-objects that reifiy other aspects of the running system. Modifications of meta-objects impact the running system immediately since there is (ideally) a causal connection between the two. This perspective is best represented with language in the smalltalk family.

Understanding Reflection in Terms of Bindings

My take is that there are essentially two kinds reflective operations that can be understood in terms of bindings: (1) dynamic source code inspection and changes that reveal, update, or create bindings, and (2) dynamic code execution that exploit existing bindings.

Reflection can operate at two levels, the base and the interpreter level. The base level correspond to the program, and the interpreter-level to the execution of the program. (The interpreter-level is sometimes called meta-level) A program can reflect on its (a) own code and state, or (b) on the code of the interpreter and its state.

Category (1) corresponds to changes that could achieve by generating sources for the running software, persisting the state of the base and the meta level, modifing the source, restarting the software and restoring the state of the base and the meta level. Note that the state of the program might be transformed during the process. Category (2) corresponds to dynamic code execution that only exploit existing bindings. Unlike category 1, it can perform late binding using information known only at run-time, for which not source could be generated. Also, dynamic code execution can be used to jump across meta-level. Indeed, code at one level, is data for the level below. Note that when transfering data accross meta-level, data might be marshalled and unmarshalled.

Combining both categories (1)(2) and (a)(b) gives four kinds of reflective operations.

Both perspectives are equality powerfull, but each perspective represents a way of thinking about reflection that favors either (1) or (2).

Categorizing language features

Let us know walk through traditional reflective features and see how they can be categorized.

  • Enumerating fields — 1a
    The program inspects its own source code. For class-based languages, enumeration is usually performed with a first-class class that reifies the structure and behavior of a class. Special language construct could exist for enumaration, think for instance of  the for construct in Javascript.
  • Adding a field — 1a
    The program modifies its own source code. It is similar to enumeration.
  • Reflectively updating a field —  2a
    The program dynamically executes a statement that update an object, i.e. eval( "anObject.field = newValue"). The language might have special construst to do this, e.g. anObject at: "field" put: newValue in Smalltalk or might rely on first-class classes.
  • Reflective invocation of a method — 2a
    The program dynamically executes a state that invokes the method, i.e. eval("anObject.message(params)"). The language might have special constructs to do this, e.g. anObject perform: "method" with: arguments in Smalltalk or might rely on first-class classes.
  • #doesNotUnderstand trap — 1b
    The #doesNotUnderstand trap is a reification at the application level of code that run at the interpreter level and modify the semantics of message sends. This is conceptually equivalent to source code changes in the interpreter itself. Namely, instead of raising an error, message that can’t be delivered are for instance re-routed to another destination.
  • Method lookup — 1b
    Certain platform have other traps to customize method lookup and dynamic method dispatch, e.g. DLR, Java, Smalltalk/X. They are similar to #doesNotUnderstand.
  • thisContext meta-object — 2b
    the interpreter’s stack is reified at the applicative level via a meta-object. It corresponds conceptually to application code being evaluated at the interpreter level, so that it can inspect or modifies the internal state of the interpreter. The code of the application correspond to data that are evaluated one level below.
  • Continuations — 2b
    Continuations are similar to thisContext reification. The interpreter evaluates code which can access its internal state, and returns a data structure (the continuation) to the application; or it evaluates code that consume a data structure (the continuation) that is used to update its internal state.
  • First-class function — 2a
    First-class functions are gloryfied dynamic reflective invocations. A method, block, closure, function represents code. When invoked, it creates a new activation frame on the stack. Regular methods can be reified to be passed around for reflective invocations, e.g. aMethod.invoke( target, param ). Methods can also be simply reified as strings: target.perform( methodName, param ) or eval( target + "." + methodName + "(param)" ). A function that does not close over any variable is mostly an anonymous method. The main difference is that its reification as a first-class object already binds it to a given target, e.g. aBlock.value( params ). Functions with bound variables refer additionally to their outer context which is an activation frame.
  • Modification of behavior — 1a
    Modifying or addition behavior to existing objects correspond to source code change. New behavior can be loaded by evaluation code that return first-class function, e.g. eval( "[ 40+2 ]" ). Behavior can be added or modified by changing the corresponding reified entity such as method dictionary via first-class classes. The whole process might be exposed via other interfaces. For instance, Java’s Hotspot accept raw bytecode to replace a method.
  • Dynamic class loading — 1a
    Clearly, it correspond to dynamic source code changes. Dynamic class loading can be see as a one shot operation, or split into class creation, and incremental addition of structure and behavior. Class loading is a reflective operation that might be exposed via first-class classes (e.g. Smalltalk’s Class>>subclass:name:fields), or via specific interfaces (e.g. class loader).
  • Query all instances of a class — nothing
    If the class is provided as a literal, e.g. MyClass.class, there’s nothing really reflective going on. It could be considered as reflective if it is eposed via first-class classes, and reifies internal information of the interpreter.
  • Eval — 1a and 1b
    Since reflection is all about treating code as data, eval is the one superpower.  We have shown in the list above several eval of types 1a and 1b. Its type depends on the data being evaluated. In its unrestricted form, it can be a mix of both.

Structural and Behavioral Reflection

Reflection is sometimes split into structural and behavioral. Structural reflection deals with reifying structure (classes and methods as objects), while behavioral reflection deals with reifying execution (#doesNotUnderstand, thisContext). Behavioral reflection map to category (b) and structural reflection to category (a).

Correlated use of Reflection

Interestingly, if an application does not leverage operations of kind 1a, it does not need 2a neither.  Use of reflection (1a) and (2a) are correlated. Indeed, if reflection 1a is never leveraged, source never change, which means the entites are all known statically. While it might be usefull for consiceness to rely on operation of type 2a, such operation could be translated in an equivalent forms with non-reflective code. For instance, if methods are never added to a system, dynamic reflective invocations could be avoided with proper use interfaces, and exhaustive if-else cases (if( action="doIt" ) { doIt() } else if (action ="doThat" ) { doThat() } ...).

Conclusion

We tried to make sense of reflection and categorize existing features in a simple framework, and tried to relate two perspectives about reflection: code as data, and meta-objects. Going through a list of typcial features shows the advantage and disadvantage of both perspectives. For instance, reflective invocations are best understood in term of code as data, but stack reification is more easily though in term of meta-object. Ultimately, features can be explained in term of both perspectives, possibly with some mind twists.

references

my citeulike #reflection tag

Software Architecture

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