Translator Pattern

This is an attempt to present ThomasKuehne's Translator pattern in a simplified form. You can get the real version from: http://homepages.mcs.vuw.ac.nz/~tk/publications/papers/translator.pdf

See FunctionalPatternSystemForObjectOrientedDesign

Often objects are organized into complex data structures such as trees or graphs in order to represent a system of relationships between the objects. Many times one of these structures will be useful in more than one context. For instance an abstract syntax tree would be useful in either a compiler or a pretty printer. In these cases the behavior of the structure and its components is extrinsic rather than intrinsic. That is to say that the behavior of each object in the structure has more to do with how the object is viewed by the context than with the nature of the object itself. When this situation occurs the symptoms include: relationships and behaviors that are correct for one context but not for another, polymorphic methods on the nodes that serve only a narrow subset of clients, overly complex traversal mechanisms that are intrusive or that require excessive book keeping. Ordinarily it is impossible to remedy this problem without violating the OpenClosedPrinciple because the definition of each object must change in response to its use in a new context.

Therefore:

Define a recursive traversal of the structure starting from some root node. Define a GenericFunction that takes a node of the structure as a parameter and recursively translates that node, all of its sub-nodes and all of the edges between them to an equivalent structure in the new context. A one to one correspondence between the elements of the original structure and elements in the resulting structure need not be maintained, but the translation must be localized to each node and be composable (i.e. a node should be able to implement its translation in terms of translations on its sub-nodes.) Implement the elements in the resulting structure so that the system of relationships that it contains is capable of supplying the desired services. Finally, perform the desired operation by traversing the new structure and calling the appropriate method(s) on each node.

Resulting context:

This two-part process has several advantages.

  1. Most importantly, the original structure and it's elements need not change. The use of ExternalPolymorphism (via the GenericFunction) requires only that the dynamic type of an object be obtainable at run-time. This advantage makes this approach desirable in situations where the VisitorPattern (which solves the same problem) is difficult or impossible to implement.
  2. The elements of the generated structure can be customized to the specific task. The elements of the new structure can be of completely new types (indeed this is desirable) and the relationships between them can be modified in ways that suit the new context even if they would be inappropriate for the old one so long as there is a two-way mapping between the two structures.
  3. Since the new structure is separate from the original its elements can be altered by the operation without harming the clients of the original.
  4. The use of HomomorphicMapping makes it possible to update the second structure and the results of operations on it in response to changes in the original structure.
  5. There is no dependence of the original structure on any part of the implementation of the new operation.
  6. The use of ExternalPolymorphism makes it easy to add new functions as needed without disturbing existing classes.

There are of course disadvantages:
  1. GenericFunctions are difficult to setup and maintain without direct language support.
  2. As with all functional patterns for object oriented programming this approach is not idiomatic and will not be recognised or appreciated by most OO practitioners. This is not an OO approach -- it is a functional approach designed to allow multi-paradigm programming in an OO environment.
  3. The use of ExternalPolymorphism makes it difficult to add new classes because all of the relevant functions will have to be updated.

Objection: wouldn't a dispatch table allow one to work around this? AnswerMe

There may be an answer in the detailed discussion in the thesis. See ObjectFunctionalImplementation for discussion of attempts to implement the ideas. -- JohnFletcher

Compare with: VisitorPattern

Discussion:

Notes from ThomasKuehne

The Translator pattern is about translating one structure (e.g., an internal graph representation) into another structure (e.g., a data structure suitable for displaying aspects of the graph to a screen).

The main case for the TranslatorPattern is the observation that there is

The assumption is that it is not reasonable to pack all potential extrinsic behavior into object methods, as their number is unbounded.

Now, the TranslatorPattern realizes ExternalPolymorphism with a few interesting properties:

1. External behavior definition is completely non-intrusive with regard to elements.

2. There is an intermediate step before behavior is defined:

As a result, it is then easy to define behavior through methods (methods of the target structure objects!) again. Remote clients may see only--and work locally on--their requested interpretation (the translated target structure) of an otherwise encapsulated, hidden data structure.

3. The translation scheme (HomomorphicMapping), uses local composable translations. These scheme makes it particularly easy to implement incremental evaluation of the target structure, i.e., quick recalculation of the external behavior in case only a small part of the source changed.

-- ThomasKuehne (edited for length by PhilGoodwin)

Grain of language

Disadvantage:

Some languages don't have GenericFunctions (or PatternMatching), so the programmer has to simulate them. AndrewAppel's Modern Compiler Implementation in Java recommends something similar to the above description of TranslatorPattern, but requiring the following sort of code for each `generic function': 

  translate(Expression node) {
    if(node instanceof ConstantExpression?) 
      return translate (ConstantExpression? node)
    else if ...
    // additional clauses for each expression type
  }
GenericFunctions actually use a map to do their dispatching, but the argument is still valid. TranslatorPattern may look odd and feel clumsy (even though it is a good solution to a real problem) in a traditional OO language. The TranslatorPattern is really a ProtoPattern (an invented rather than discovered solution) that is part of a pattern language invented by ThomasKuehne for the purpose of extending OO languages with functional concepts. Ultimately constructs like this would be supported more or less directly by a multi-paridigm functional/object oriented language. There is a growing trend toward looking to free functions in OO languages that support them (like C++). It is my opinion that such trends will ultimately lead to the adoption of a multi-paradigm approach such as the one that Thomas suggests. -- PhilGoodwin

The problem here seems to be the Java overloading semantics rather than lack of free functions. Java insists on resolving overloading at compile time. I seem to remember that CLOS would select the most specific applicable function at run time.

Does Smalltalk suffer from this? If memory serves, overloading isn't supported, and they get away with it due to the loose typing... it seems sometimes that however useful it may be, sometimes static typing just gets in the way :)

Is NiceLanguage the ultimate answer? No, although it does provide multimethods / generic functions & classes in a statically checked language.

It is possible to implement either the if-else version or the map version of the selector function using CeePlusPlus. See ObjectFunctionalImplementation. The map version is achieved using FunctoidsInCpp to make callable objects from the member functions to be called. It is also possible to implement a different version using the implementation of AcyclicVisitor described in ModernCeePlusPlusDesign. -- JohnFletcher

This may be a case of GreencoddsTenthRuleOfProgramming. If you have to keep re-writing data structures for different purposes, then perhaps a database is in order. --top

Perhaps in some cases, but not necessarily. TranslatorPattern is justified where a data structure that may be appropriate in one context is not appropriate in another, but both are needed simultaneously. (Note that I wrote "data structure", not "database". A "database" is built from data structures, and typically implies more than just data representation, such as persistence, ad-hoc querying and transactions.) For example, a game may maintain a data structure of game objects to support planning in the AI subsystem, but also needs to render the game objects to a graphical display device. What the graphical rendering engine expects as a data structure may be fundamentally different from what the AI subsystem expects -- which may be different yet again from how the overall gameplay logic expects to manipulate the objects. Use of TranslatorPattern makes it possible to maintain the game objects in one data structure, whilst making it simultaneously appear to be data structures appropriate to gameplay logic, graphical rendering, and AI planning. There is no database system that would efficiently support the manipulations typically performed by gameplay logic, graphical rendering, and AI planning, and the typical facilities of a database system -- persistence and caching, ad-hoc querying, transactions -- would represent needless overhead.

Discussion continued at GameModelingDatabase

CategoryObjectFunctionalPatterns, CategoryGameProgramming

EditText of this page (last edited July 23, 2014) or FindPage with title or text search