Are there any design patterns that are possible only in dynamically typed languages like Python?

Question

I've read a related question Are there any design patterns that are unnecessary in dynamic languages like Python? and remembered this quote on Wikiquote.org

The wonderful thing about dynamic typing is it lets you express anything that is computable. And type systems don’t — type systems are typically decidable, and they restrict you to a subset. People who favor static type systems say “it’s fine, it’s good enough; all the interesting programs you want to write will work as types”. But that’s ridiculous — once you have a type system, you don’t even know what interesting programs are there.

--- Software Engineering Radio Episode 140: Newspeak and Pluggable Types with Gilad Bracha

I wonder, are there useful design patterns or strategies that, using the formulation of the quote, "don't work as types"?

Answer 1

First-class types

Dynamic typing means that you have first-class types: you can inspect, create and store types at runtime, including the language's own types. It also means that values are typed, not variables.

Statically typed language may produce code that relies on dynamic types too, like method dispatch, type classes, etc. but in a way that is generally invisible to the runtime. At best, they give you some way to perform introspection. Alternatively, you could simulate types as values but then you have an ad-hoc dynamic type system.

However, dynamic type systems rarely have only first-class types. You can have first-class symbols, first-class packages, first-class .... everything. This is in contrast to the strict separation between the compiler's language and the runtime language in statically typed languages. What the compiler or interpreter can do the runtime can do, too.

Now, let's agree that type inference is a good thing and that I like to have my code checked before running it. However, I also like being able to produce and compile code at runtime. And I love to precompute things at compile-time too. In a dynamically typed language, this is done with the same language. In OCaml, you have the module/functor type system, which is different from the main type system, which is different from the preprocessor language. In C++, you have the template language which has nothing to do with the main language, which is generally ignorant of types during execution. And that's fine in those language, because they don't want to provide more.

Ultimately, that does not change really what kind of software you can develop, but the expressivity changes how you develop them and whether it is hard or not.

Patterns

Patterns that rely on dynamic types are patterns which involve dynamic environments: open classes, dispatching, in-memory databases of objects, serialization, etc. Simple things like generic containers work because a vector does not forget at runtime about the type of objects it holds (no need for parametric types).

I tried to introduce the many ways code is evaluated in Common Lisp as well as examples of possible static analyses (this is SBCL). The sandbox example compiles a tiny subset of Lisp code fetched from a separate file. In order to be reasonably safe, I change the readtable, allow only a subset of standard symbols and wrap things with a timeout.

;;
;; Fetching systems, installing them, etc. 
;; ASDF and QL provide provide resp. a Make-like facility 
;; and system management inside the runtime: those are
;; not distinct programs.
;; Reflexivity allows to develop dedicated tools: for example,
;; being able to find the transitive reduction of dependencies
;; to parallelize builds. 
;; https://gitlab.common-lisp.net/xcvb/asdf-dependency-grovel
;;
(ql:quickload 'trivial-timeout)

;;
;; Readtables are part of the runtime.
;; See also NAMED-READTABLES.
;;
(defparameter *safe-readtable* (copy-readtable *readtable*))
(set-macro-character #\# nil t *safe-readtable*)
(set-macro-character #\: (lambda (&rest args)
                           (declare (ignore args))
                           (error "Colon character disabled."))
                     nil
                     *safe-readtable*)

;; eval-when is necessary when compiling the whole file.
;; This makes the result of the form available in the compile-time
;; environment. 
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defvar +WHITELISTED-LISP-SYMBOLS+ 
    '(+ - * / lambda labels mod rem expt round 
      truncate floor ceiling values multiple-value-bind)))

;;
;; Read-time evaluation #.+WHITELISTED-LISP-SYMBOLS+
;; The same language is used to control the reader.
;;
(defpackage :sandbox
  (:import-from
   :common-lisp . #.+WHITELISTED-LISP-SYMBOLS+)
  (:export . #.+WHITELISTED-LISP-SYMBOLS+))

(declaim (inline read-sandbox))

(defun read-sandbox (stream &key (timeout 3))
  (declare (type (integer 0 10) timeout))
  (trivial-timeout:with-timeout (timeout)
    (let ((*read-eval* nil)
          (*readtable* *safe-readtable*)
          ;;
          ;; Packages are first-class: no possible name collision.
          ;;
          (package (make-package (gensym "SANDBOX") :use '(:sandbox))))
      (unwind-protect
           (let ((*package* package))
             (loop
                with stop = (gensym)
                for read = (read stream nil stop)
                until (eq read stop)
                ;;
                ;; Eval at runtime
                ;;
                for value = (eval read)
                ;;
                ;; Type checking
                ;;
                unless (functionp value)
                do (error "Not a function")
                ;; 
                ;; Compile at run-time
                ;;
                collect (compile nil value)))
        (delete-package package)))))

;;
;; Static type checking.
;; warning: Constant 50 conflicts with its asserted type (MOD 11)
;;
(defun read-sandbox-file (file)
  (with-open-file (in file)
    (read-sandbox in :timeout 50)))

;; get it right, this time
(defun read-sandbox-file (file)
  (with-open-file (in file)
    (read-sandbox in)))

#| /tmp/plugin.lisp
(lambda (x) (+ (* 3 x) 100))
(lambda (a b c) (* a b))
|#

(read-sandbox-file #P"/tmp/plugin.lisp")

;; 
;; caught COMMON-LISP:STYLE-WARNING:
;;   The variable C is defined but never used.
;;

(#<FUNCTION (LAMBDA (#:X)) {10068B008B}>
 #<FUNCTION (LAMBDA (#:A #:B #:C)) {10068D484B}>)

Nothing above is "impossible" to do with other languages. The plug-in approach in Blender, in music software or IDEs for statically compiled languages which do on-the-fly recompilation, etc. Instead of external tools, dynamic languages favor tools which make use of information that is already there. All the known callers of FOO? all the subclasses of BAR? all methods that are specialized by class ZOT? this is internalized data. Types are just another one aspect of this.

---

(see also: CFFI)

Answer 2

Short answer: no, because Turing equivalence.

Long answer: This guy's being a troll. While it's true that type systems "restrict you to a subset," the stuff outside that subset is, by definition, stuff that does not work.

Anything you're able to do in any Turing-complete programming language (which is language designed for general-purpose programming, plus plenty that aren't; it's a pretty low bar to clear and there are several examples of a system becoming Turing-complete unintentionally) you are able to do in any other Turing-complete programming language. This is called "Turing equivalence," and it only means exactly what it says. Importantly, it does not mean that you can do the other thing just as easily in the other language--some would argue that that's the entire point of creating a new programming language in the first place: to give you a better way of doing certain things that existing languages suck at.

A dynamic type system, for example, can be emulated on top of a static OO type system by just declaring all variables, parameters, and return values as the base Object type and then using reflection to access the specific data within, so when you realize this you see that there's literally nothing you can do in a dynamic language that you can't do in a static language. But doing it that way would be a huge mess, of course.

The guy from the quote is correct that static types restrict what you can do, but that's an important feature, not a problem. The lines on the road restrict what you can do in your car, but do you find them restrictive, or helpful? (I know I wouldn't want to drive on a busy, complex road where there's nothing telling the cars going the opposite direction to keep to their side and not come over where I'm driving!) By setting up rules that clearly delineate what's considered invalid behavior and ensuring that it won't happen, you greatly decrease the chances of a nasty crash occurring.

Also, he's mischaracterizing the other side. It's not that "all the interesting programs you want to write will work as types", but rather "all the interesting programs you want to write will require types." Once you get beyond a certain level of complexity, it becomes very difficult to maintain the codebase without a type system to keep you in line, for two reasons.

First, because code with no type annotations is hard to read. Consider the following Python:

def sendData(self, value):
   self.connection.send(serialize(value.someProperty))

What do you expect the data to look like that the system at the other end of the connection receives? And if it's receiving something that looks completely wrong, how do you figure out what's going on?

It all depends on the structure of value.someProperty. But what does it look like? Good question! What's calling sendData()? What is it passing? What does that variable look like? Where did it come from? If it's not local, you have to trace through the entire history of value to track down what's going on. Maybe you're passing something else that also has a someProperty property, but it doesn't do what you think it does?

Now let's look at it with type annotations, as you might see in the Boo language, which uses very similar syntax but is statically typed:

def SendData(value as MyDataType):
   self.Connection.Send(Serialize(value.SomeProperty))

If there's something going wrong, suddenly your job of debugging just got an order of magnitude easier: look up the definition of MyDataType! Plus, the chance of getting bad behavior because you passed some incompatible type that also has a property with the same name suddenly goes to zero, because the type system won't let you make that mistake.

The second reason builds on the first: in a large and complex project, you've most likely got multiple contributors. (And if not, you're building it yourself over a long time, which is essentially the same thing. Try reading code you wrote 3 years ago if you don't believe me!) This means that you don't know what was going through the head of the person who wrote almost any given part of the code at the time they wrote it, because you weren't there, or don't remember if it was your own code a long time ago. Having type declarations really helps you understand what the intention of the code was!

People like the guy in the quote frequently mischaracterize the benefits of static typing as being about "helping the compiler" or "all about efficiency" in a world where nearly unlimited hardware resources make that less and less relevant with each passing year. But as I've shown, while those benefits certainly do exist, the primary benefit is in the human factors, particularly code readability and maintainability. (The added efficiency is certainly a nice bonus, though!)

Answer 3

I'm going to side-step the 'pattern' part because I think it devolves into the definition of what is or isn't a pattern and I've long lost interest in that debate. What I will say is that there are things you can do in some languages that you can't do in others. Let me be clear, I'm not saying there are problems you can solve in one language that you can't solve in another. Mason has already pointed out Turing completeness.

For example, I've written a class in python that takes wraps a XML DOM element and makes it into a first class object. That is, you can write the code:

doc.header.status.text()

and you have the contents of that path in from a parsed XML object. kind of neat and tidy, IMO. And if there isn't a head node, it just returns a dummy objects that contain nothing but dummy objects (turtles all the way down.) There's no real way to do that in, say, Java. You'd have to have compiled a class ahead of time that based on some knowledge of the structure of the XML. Putting aside whether this is a good idea, this kind of thing really does change the way you solve problems in a dynamic language. I'm not saying it changes in a way that is necessarily always better, however. There are some definite costs to dynamic approaches and Mason's answer gives a decent overview. Whether they are a good choice depends on many factors.

On a side note, you can do this in Java because you can build a python interpreter in Java. The fact that solving a specific problem in a given language may mean building an interpreter or something akin to it is often overlooked when people talk about Turing completeness.

Answer 4

The quote is correct, but also really disingenuous. Let's break it down to see why:

The wonderful thing about dynamic typing is it lets you express anything that is computable.

Well, not quite. A language with dynamic typing lets you express anything as long as it's Turing complete, which most are. The type system itself does not let you express everything. Let's give him the benefit of the doubt here though.

And type systems don’t — type systems are typically decidable, and they restrict you to a subset.

This is true, but notice we are now firmly talking about what the type system allows, not what the language that uses a type system allows. While it is possible to use a type system to calculate stuff at compile time, this in generally not Turing complete (as the type system is generally decidable), but almost any statically typed language is also Turing complete in its runtime (dependently typed languages are not, but I don't believe we are talking about them here).

People who favor static type systems say “it’s fine, it’s good enough; all the interesting programs you want to write will work as types”. But that’s ridiculous — once you have a type system, you don’t even know what interesting programs are there.

The trouble is that dynamically types languages do have a static type. Sometimes everything is a string, and more commonly there is some tagged union where every thing is either a bag of properties or a value like an int or a double. The trouble is that static languages can do this as well, historically it was a bit clunkier to do this, but modern statically typed languages make this pretty much as easy to do as using a dynamically types language, so how can there be a difference in what the programmer can see as an interesting program? Static languages have exactly the same tagged unions as well as other types.

To answer the question in the title: No, there are no design patterns that can't be implemented in a statically typed language, because you can always implement enough of a dynamic system to get them. There may be patterns that you get for 'free' in a dynamic language; this may or may not be worth putting up with the downsides of those languages for YMMV.

Answer 5

There are surely things you can only do in dynamically typed languages. But they wouldn't necessarily be good design.

You might assign first an integer 5 then a string 'five', or a Cat object, to the same variable. But you're only making it harder for a reader of your code to figure out what's going on, what's the purpose of every variable.

You might add a new method to a library Ruby class and access its private fields. There might be cases where such a hack can be useful but this would be a violation of encapsulation. (I don't mind adding methods only relying on the public interface, but that's nothing that statically typed C# extension methods can't do.)

You might add a new field to an object of somebody else's class to pass some extra data around with it. But it's better design to just create a new structure, or extend the original type.

Generally, the more organized you want your code to stay, the less advantage you should take from being able to dynamically change type definitions or assign values of different types to the same variable. But then your code is no different from what you could achieve in a statically typed language.

What dynamic languages are good at is syntactic sugar. For example, when reading a deserialized JSON object you may refer to a nested value simply as obj.data.article[0].content - much neater than say obj.getJSONObject("data").getJSONArray("article").getJSONObject(0).getString("content").

Ruby developers especially could talk at lengths about magic that can be achieved by implementing method_missing, which is a method allowing you to handle attempted calls to undeclared methods. For example, ActiveRecord ORM uses it so that you could make a call User.find_by_email('joe@example.com') without ever declaring find_by_email method. Of course it's nothing that couldn't be achived as UserRepository.FindBy("email", "joe@example.com") in a statically typed language, but you can't deny it its neatness.

Answer 6

The Dynamic Proxy pattern is a shortcut for implementing proxy objects without needing one class per type you need to proxy.

class Proxy(object):
    def __init__(self, obj):
        self.__target = obj

    def __getattr__(self, attr):
        return getattr(self.__target, attr)

Using this, Proxy(someObject) creates a new object that behaves the same as someObject. Obviously you'll also want to add additional functionality somehow, but this is a useful base to begin from. In a complete static language, you'd need to either write one Proxy class per type you want to proxy or use dynamic code generation (which, admittedly, is included in the standard library of many static languages, largely because their designers are aware of the problems not being able to do this cause).

Another use case of dynamic languages is so-called "monkey patching". In many ways, this is an anti-pattern rather than a pattern, but it can be used in useful ways if done carefully. And while there's no theoretical reason monkey patching couldn't be implemented in a static language, I've never seen one that actually has it.

Answer 7

Yes, there are many patterns and techniques which are only possible in a dynamically typed language.

Monkey patching is a technique where properties or methods are added to objects or classes at runtime. This technique not possible in a statically typed language since this means types and operations cannot be verified at compile time. Or to put it another way, if a language supports monkey-patching it is by definition a dynamic language.

It can be proven that if a language supports monkey patching (or similar techniques to modify types at runtime), it cannot be statically type checked. So it is not just a limitation in currently existing languages, it is a fundamental limitation of static typing.

So the quote is definitely correct - more things are possible in a dynamic language than in a statically typed language. On the other hand, certain kinds of analysis is only possible in a statically typed language. For example you always know which operations are allowed on a given type, which allows you to detect illegal operations at compile type. No such verification is possible in a dynamic language when operations can be added or removed at runtime.

This is why there is no obvious "best" in the conflict between static and dynamic languages. Static languages give up certain power at runtime in exchange for a different kind of power at compile time, which they believe reduces the number of bugs and makes development easier. Some believe the trade-off is worth it, others doesn't.

Other answers have argued Turing-equivalence means anything possible in one language is possible in all languages. But this does not follow. To support something like monkey-patching in a static language, you basically have to implement a dynamic sub-language inside the static language. This is of course possible, but I would argue you are then programming in a embedded dynamic language, since you also lose the static type checking which exist in the host language.

C# since version 4 have supported dynamically typed objects. Clearly the language designers see benefit in having both kind of typing available. But it also shows you can't have your cake and eat i too: When you use dynamic objects in C# you gain the ability do something like monkey patching, but you also lose static type verification for interaction with these objects.

Answer 8

I wonder, are there useful design patterns or strategies that, using the formulation of the quote, "don't work as types"?

Yes and no.

There are situation in which the programmer knows the type of a variable with more precision then a compiler. The compiler may know that something is an Object, but the programmer will know (due the invariants of the program) that it is actually a String.

Let me show some examples of this:

Map<Class<?>, Function<?, String>> someMap;
someMap.get(object.getClass()).apply(object);

I know that someMap.get(T.class) will return a Function<T, String>, because of how I constructed someMap. But Java is only sure that I've got a Function.

Another example:

data = parseJSON(someJson)
validate(data, someJsonSchema);
print(data.properties.rowCount);

I know that data.properties.rowCount will be a valid reference and an integer, because I've validated the data against a schema. If that field were missing, an exception would have been thrown. But a compiler would only know that is either throwing an exception or return some sort of generic JSONValue.

Another example:

x, y, z = struct.unpack("II6s", data)

The "II6s" defines the way that data encode three variables. Since I've specified the format, I know which types will be returned. A compiler would only know that it returns a tuple.

The unifying theme of all these examples is that the programmer knows the type, but a Java level type system won't be able to reflect that. The compiler won't know the types, and thus a statically typed language won't let me call them, whereas a dynamicly typed language will.

That's what the original quote it getting at:

The wonderful thing about dynamic typing is it lets you express anything that is computable. And type systems don’t — type systems are typically decidable, and they restrict you to a subset.

When using dynamic typing I can use the most derived type I know about, not simply the most derived type my language's type system knows. In all the cases above, I have code which is semantically correct, but will be rejected by a static typing system.

However, to return to your question:

I wonder, are there useful design patterns or strategies that, using the formulation of the quote, "don't work as types"?

Any of the above examples, and indeed any example of dynamic typing can be made valid in static typing by adding appropriate casts. If you know a type your compiler doesn't, simply tell the compiler by casting the value. So, at some level, you aren't going to get any additional patterns by using dynamic typing. You just might need to cast more to get working staticly typed code.

The advantage of dynamic typing is that you can simply use these patterns without fretting about the fact that its tricky to convince your type system of their validity. It doesn't change the patterns available, it just possibly makes them easier to implement because you don't have to figure out how to make your type system recognize the pattern or add casts to subvert the type system.

Answer 9

Here are a few examples from Objective-C (dynamically typed) which are not possible in C++ (statically typed):

• Putting objects of several distinct classes into the same container.
  Of course, this requires runtime type inspection to subsequently interpret the contents of the container, and most friends of static typing will object that you shouldn't be doing this in the first place. But I have found that, beyond the religious debates, this can come in handy.

• Expanding a class without subclassing.
  In Objective-C, you can define new member functions for existing classes, including language defined ones like NSString. For example, you can add a method stripPrefixIfPresent:, so that you can say [@"foo/bar/baz" stripPrefixIfPresent:@"foo/"] (note the use of the NSSring literals @"").

• Use of object-oriented callbacks.
  In statically typed languages like Java and C++, you have to go to considerable lengths to allow a library to call an arbitrary member of a user-supplied object. In Java, the workaround is the interface/adaptor pair plus an anonymous class, in C++ the workaround is usually template based, which implies that library code has to be exposed to user code. In Objective-C, you just pass the object reference plus the selector for the method to the library, and the library can simply and directly invoke the callback.