Skip to Content

This blog series champions the application of essential model theoretic concepts to computers and computation and tries to show some surprising consequences.

It is one of the great achievements of model theory to present a concise approach how to distinguish between the description and the described and to define the precise relation between both as interpretation.  A description in a model theoretic sense consists of a finte sequence of characters from an alphabet. The interpretation maps the characters of the description onto the entities which are described: the model. Model theory thereby provides a precise definition of semantics: Meaning is attributed to descriptions by interpretation, which is to be performed by an interpreter. Models thereby exist only internally within some interpreter. In other words, the essence of model theory is that descriptions have no meaning per se, there is no meaning as such and meaning cannot be transported like energy or matter but meaning is awarded to descriptions by interpreters.

Simple as it sounds, this view provides at least 4 surprises for software developement.

  1. “modelling” is synonymous with “describing”.
  2. We can have both, different descriptions which are mapped by different interpretations onto identical entities, as well as identical descriptions which are mapped by different interpretations onto different entities.
  3. A computer, described as processing a program description, has to be described as an interpreter in this sense, attributing meaning to descriptions.
  4. To be of pragmatic value, models often need only to be “good enough”. So we have to face the fact that relevant requirements generally heavily underspecify our application design, leading to different implemented models even of identically specified applications. We thus have to learn to what extend it is necessary to share a common model for the different types of cooperations. 

The first two surprise will be dealt with in this blog, the next ones will be tackled in the following ones.

“modelling” is synonymous with “describing”

Let us assume, we have two different ways to describe program structures: From a model theoretic perspective both describe exactly the same entities, if both descriptions could be interpreted by the same interpreter, mapping both descriptions onto the same entities.  Just to give an example: We could use both, a programming language ProgLang and a graphical ‘modelling’ language GML do describe some class structures. If they describe the same entities, it would not matter, which description our interpreter would use to create its (internal) model. A good example would be the Specification and Description Language SDL of the CCITT

To us, graphical diagrams may be much better suited to present topological representable relations although they often represent only certain aspects. On the contrary, programs may not be as easily comprehensible, but usually claim to be complete. But both are descriptions of our application structure. If we say with GML “we model” and with ProgLang “we describe”, then we use the terms “to model” and “to describe” as logical synonyms, i.e. we can replace them by each other without changing the semantics of our sentence in a logical sense. The transformation between ProgLang and GML therefore is a translation.

If we do not distinguish clearly between descriptions and models, the chances are high, that we will soon talk about meta models and meta meta models, etc, without being capable of really expressing what we meant in the very beginning.

The necessity for formal semantics

The second surprise, directly motivates the necessity for formal semantics. Because the meaning of a description is the result of the interpretation function, we can be sure to have a well defined meaning only if the function of interpretation is well defined. This is the essence of formalizing semantics.

A textbook example of identical descriptions, carrying different semantics are sentences of colloquial language as well as graphical diagrams without formalized semantics. The high intuitiveness of graphical representations entails the substantial risk, that we interpret them as we interpret colloquial language, namely every reader applies a different interpreting function.

Take for example the famous ISO/OSI 7 layer model, which is supposed to represent software layers created by well defined interface. There are plenty of diagrams, which illustrate these levels quite demonstratively. However, have you ever asked yourself, why this “model” did never find widespread acceptance in application design? Instead, for example the TCP/IP stack realizes only 4 layers.  Wouldn’t it be a good explanation if the 7 ISO/OSI layers just do not represent good application architecture? For example, the usual relation between the  “application” part and the “presentation” part of a well structured application is just not a layered one in the ISO/OSI sense.

Now, why is it so important to express what we want a computer to do in a language with formalized semantics? Because the most relevant interpreter for our description is the computer and not the programmer. The computer does what the programmer describes with respect to its own interpretation, and not with respect to the programmer’s intention. In a nutshell, the computer does what the programmer describes but not what he means.

To report this post you need to login first.

3 Comments

You must be Logged on to comment or reply to a post.

  1. David Halitsky
    You make a very interesting general point, and I have commented on a particular example of your observation here:

    Recursion Nodes that  “Repeat” Tree Nodes with Embedded Tables (in WD-ABAP). NOT!

    In WDA (WebDynproABAP), we are provided with the notion of a recursion node.  Furthermore, we are allowed to define recursion nodes as recursions of “tree_with_table” nodes.  No compile or run-time errors.

    But when we actually run our app, we find that out that the table in any of our “tree_with_table” nodes will fill correctly, but that the table in any of our “recursion nodes” will not.

    So, the WDA Editor has an inconsistency between description and meaning.  The program behind this editor is written so that it “describes” a situation in which a “tree_with_table” node can be “recursed” by a recursion node.

    But as you point out, the WDA compiler has the final word: it assigns its own meaning or interpreation to the description created by the editor. And in this interpretation made by the compiler, the “tree_with_table” node cannot really be “recursed” by a recursion node – the WDA application won’t blow-off, but the tables won’t fill.

    Another classic case of your observation involves native database optimizers, which I have commented on in these two posts:

    Anyone Got Some Real Benchmark Stats on “For all Entries”???

    “Yes, Virginia, the check is in the mail” (or, why you can’t trust SQL)

    The ABAP developer creates a description in an OpenSQL SELECT statement, but the native DB optimizers again have the final word on this statement: they interpret what the programmer meant.

    These two examples show onr reason why your way of looking at things is so very important.

    But there is a more important reason that has to do with whether IT semantics can ever be really separated from IT syntax (this is the question I raised here:

    BPEL and the “Generative Wars” of the Last Century: A Cautionary Tale

    in response to Alan’s/Ivana’s post here:

    BPEL Glossary for Developers

    BPEL in a Nutshell

    So I look forward to reading the remainder of your series to see what your final conclusion is concerning the separability of syntax and semantics.

    (0) 
    1. Johannes Reich Post author
      Hi David,
      thanks for your prompt feedback. I am not an expert of WebDynproABAP, but what you describe seems to be more like bugs. That’s an additional issue: the interpretation function of the computer does not work as specified. I would describe this as a mismatch between the actual semantics provided by the computer and the semantics as it is supposed (by us) to be. It could well be that a bug destroys the welldefinedness of the computer’s interpretation function and introduces interpretational non determinism.

      Here is an additional example of different – non buggy – semantics of the same syntax. Execution of the code fragment 

      var b = “30”;
      var c = 12;
      a = b + c;

      leads to a = 42 in VisualBasic and to a = “3012” in JavaScript, because both languages follow different implicit typing rules.

      (0) 
      1. David Halitsky
        but I’m not sure that the DB optimizer cases qualify as bugs.

        1.  ABAP Recursion Case.

        With respect to recursion on “tree with table nodes”, I suspect that this may have resulted from a deadline which did not allow the recursive node construct to be implemented completely.  So this may not be so much as “bug” as “unfinished” work.

        2.  DB Optimizers.

        I don’t think that the issue here is a bug, really (except perhaps a bug in the design of SQL, which no less an expert than Gio Wiederhold has called a “mistake we have to live with”.)

        The optimizers in the standard “relational” databases are not even “80/20” solutions – they’re more like 60/40 solutions.

        So they may be classic case of human inability to implement everything we can conceive.

        ***

        In any event, this further discussion re-inforces my opinion that you made a very important post.  I hope that some academic(s) develop a typology of “mis-matches” between what might be generically called “design” and “implementation” mismatches: a) bugs; b) misinterpretations; c) insufficiencies, etc.

        If any academic ever does this, I hope you are sufficiently credited.

        Regards
        David

        (0) 

Leave a Reply