Modeling, Models, Notations:
  • Modeling (levels of meta)
  • e.g. modeling reality: physics
  • e.g. modeling reality: what the system is about
  • Abstraction (levels of abs. | conceptual m.)
  • System Modeling: the paradigms
  • e.g. programs - descriptions of computation
  • e.g. models of computation
  • system properties: state
  • system properties: architecture
  • system models (dynamics graphs)
  • information models: spatial
  • associative networks
    		•  

      Models of Computation

      Location http://www.cs.mun.ca/~ulf/mod/moc.html.
    Written 100304 by Ulf Schünemann.
    Copyright (C) 2004 Ulf Schünemann.

    back to: software objects | prog. lang. paradigms | MOC-extending features

    TODO: Actor Systems with causal model: scripts and replacement behavior
    «[I]t is helpful to think of a programming paradigm as an ontology. An ontology is concerned with that which populates a world of interest and it is concerned with the relationships among the existents of this world. Thus within any given ontology only certain kinds of things and relationships are assumed to exist. When viewed in this way a programming paradigm can be defined as a model or approach used in solving a problem. It is a model in the sense that is supports a particular way of modeling a problem domain. It is an approach in the sense that it defines a certain way of thinking about a problem and its solution» [G 244].

    There are different ways of conceptualizing computation in computational systems: A paradigm or model of computation (MOC) is a meta-model[^] or "ontology", which specifies what kinds of entities, relationships, and events (software objects[^]) there are (to be modeled, described, specified) in any particular (existing or to-be-developed) computational system. Chosing a particular MOC for modeling computations therefore means to subscribe to a particular way of conceptualizing computation, and thus predetermines what the program can talk about, and according to what a program can be partitioned.

    A model of computation can be understood as a glas-box or as a grey-box theory of computation (on the programmed computer). See system modeling: the paradigms.

    MOCs are abstract models, which are abstract in several ways:

    1. They not physical objects (concrete models), but exist only in descriptions or as abstractions from many concrete objects.
    2. They are independent of the concrete computer, program processor[^] which actually performs the computation.
    3. They are independent of the linguistic representation of the computation in a particular programming language.

    There can be different levels of detail:
    1. Phenomenological vs. causal MOCs. Phenomenological MOCs provide for describing what happens (a sequence of events), but not why. Causal MOCs provide for the description of why a certain sequence of events occurs. Typically the explanation is that a computational agent executes a certain subprogram, interprets a method, follows a script, etc.
    2. Abstract vs. concrete MOCs. Cf. Snyder on object models (object-oriented MOCs): «The abstract object model is a partial description of the behavior of a computational system. To model a particular system (such as C++), one defines a concrete object model for that system. It may elaborate the abstract object model by making it more specific, for example, by defining the form of request parmeters or the language used to specify types. It may populate the model by introducing specific instances of entities defined by the model, for example, specific objects, specific operations, or specific types. It may also restrict the model by eliminating entities or placing additional restrictions on their use» [MCOM 5].

    The following some important abstract models of computation, where I tried to keep their phenomenological and causal aspects separate.

     

    A. "Impersonal" models of computation, with no explicit agent causing the events (they are caused by "the computer", which is not explicitly modeled).

    Incremental Update MOC or Imperative MOC - the imperative paradigm's model of computation
    PHENOMENOLOGICAL «The imperative paradigm is often viewed as the "traditional" model of computation. The imperative model closely matches the actual execution of the computer on the underlying hardware. Computation is viewed as a task being performed by a "processing unit," which manipulates and modifies "memory." Memory can be envisioned as a sequence of boxes, or pigeon-holes, in which values are stored. ... The computer itself is a data manager; it follows a pattern of instructions, each instruction causing the computer to extract certain values from memory, transform them in some fashion, the place results back into memory locations. ...
    The imperative model is often described using the phrase "incremental changes to state." ... As computation preceeds the boxes remain fixed, but the contents continually change. A large structure, such as an array, is manipulated by modifying each individual element one-by-one. Thus, computation proceeds by modifying large structures a little at a time, until finally the intended result is achieved.» [Leda 9f]

    Procedural abstraction in this MOC is the combination of elementary updates (affecting one memory location/variable each) to one composite update (affecting an entire memory area). The basic imperative MOC contains nothing as which this procedural abstraction could be reified.

  • Restriction: The von-Neumann MOC
    • a strictly sequential, single-threaded imperative model

    		CAUSAL
    entity:
    Variable
    |
    |
    current
    |
    \|/
    entity:
    Value
    (1st class)
    		<<-
     
    event:
    update
     
    event
    //\\
    |
    causes
    |
    agent:
    The
    Computer
    |
    follows
    |
    \|/
    instructions

    Applicative Model of Computation
    PHENOMENOLOGICAL «We are taught very early that computers do operations on operands, and this computational model is preserved through everything we learn subsequently. Once we know that larger operators can be built out of stored sequences of operators, our progress as programmers becomes a matter of increasing the number of different operators we know ... We think of the computer as two disjoint compartments, one containing operators and the other operands, and we express our intentions by selecting what operators are to be applied and to what operands in what order.» [p 152 in Brad J. Cox: Message/Object Programming: An Evolutionary Change in Programmming Technology; IEEE Software 1/1 1984] [quoted from Quib 97].

    Procedural abstraction in this MOC is the combination of primitive operation applications. The programmer can reify the result in his software system as a new, composite operation. Its operands are the primitive operations' operands minus those which the results of other applications in the composite operation.

    Note that the applicative MOC supports operand-modifying operations (mutators). But in the applicative MOC it is ontologically impossible that the application of an operation modifies something that is not operand in the application. (If something is modified through the application then in the applicative MOC this implies that it is de-facto an operand.)

    		CAUSAL
    entity:
    Operand
    (abstract)
    //\\
    |
    event:
    apply
    |
    entity:
    Operation
    		For an causal model of computation, it remains to explain how it is determined which operations to apply to which operands and in which order.
  • Restriction: Pure Functional Model
    • The operations do not modify the operands to which they are applied, but they yield results, which can be used as operands for the next operation.

  • Elaboration: Relational Model
    • operands: relations
    operators: selection, projection, union, product, difference
    «The relational paradigm is based on a world of relations which in turn may be thought of as tables. Operations provided in this world of relations operate on existing tables in order to create new tables. The relational model has become an important model for database systems. ... The five primitive operations essential to relational completeness are selection, projection, union, product and difference.» [G 249, <>]

    /|\
    |
    after each application of an operation, the yielded result
    can be used as operand to a different operation
    (determined in the causal model)
    the channel structure fixes whose operations' output data
    flows as input data to which other operations
    |
    \|/

    B. Models of computation with different, explicitly modeled agents that cause the events. Therefore we can now talk of the model as a "system".

    Dataflow MOC / Systems
    PHENOMENOLOGICAL
    System Architecture: pipes-and-filters[^]:
  • components (computational agents) = "processors"
  • interaction = "flow" of data between processors
  • connectors = "channels"(?), transport the data
    • Computation is the flow of data packages between processing units (service providers) through connectors. The data packages are FIFO-buffered between production and consumption (we can model the buffering as taking place in the connectors, or in explicit input ports).

    Procedural abstraction in this MOC is a combination of consume and produce events on certain channels. The programmer can reify the result in his dataflow system as a new processor appropriately connected with the channels (channels from which data is consumed are connected to input ports, channels onto which data is produced are connected to output ports).

    		CAUSAL
    agent:
    Processor
    Port
    (in/out)
    /|\
    |
    connects
    |
    |     		  For an causal model of computation, we cannot take the processors as black-boxes, but have to look into them and say how they determine which consume events and produce events to cause and in which order.
    navigation bar: Dataflow
  • agent/thing relation
  • dataflow system models
  • dataflow models of computation
  • pipes & filters architecture
    • connector:
    Channel?
    |
    |
    buffers
    |
    \|/
    entity:
    Data
    		<<-
    event:
    produce/
    consume
    For examples of dataflow systems, see
    • how summing up the squares of a tree's odd leaves, and the calculation of Fibonacci numbers can be conceptualized as signals flowing through a cascade of stages;
    • how to find all pairs of i and j such that i + j is prime by filtering sequences (``sequence paradigm'').
    • how the stream of integers in an interval is filtered for prime numbers which are then summed up, using delayed lists as streams.
    • how the stream of all integers is recursively filtered to the infinite stream of prime numbers (c.f. the sieve of Eratosthenes).
    • how a stream of random numbers is converted into a stream of outcomes of the Cesàro experiment on consecutive random numbers, then into a stream of estimates of probabilities, and then into a stream of approximations to pi
    /|\
    |
        single service agents (processing the next set of data),    
    output producers do not know the consumer,
    multiple input ports
        agents offer multiple services,    
    directed: message sender specifies receiver,
    single message input queue
    |
    \|/
    navigation bar: Message Passing
  • message passing diagrams
  • client-server architecture
  • object systems (model of computation)
  • message filtering systems
  • message passing meta-programming
    • Object-based MOC, Object Systems or Message Passing Systems - the object paradigm's model of computation [MCOM, Quib 99-104]
    PHENOMENOLOGICAL
    CAUSAL

    The course of the computation is determined inside of the clients and objects:

    event:
    request
    //\\
    |
    causes
    |
    agent:
    client
    Causing a request. «A client issues a request by evaluating a request form; each evaluation of a request form results in a new request. The mapping of a request form to a request is called spelling.» «An operation is named in a request form using an operation name» [MCOM 5f].

    Reaction to Request. «A request is performed by transforming it into a method invocation. This transformation is called binding. A method invocation identifies a method [a program], a collection of method parameters, and an execution engine [=object?]. ... The execution engine interprets the method in a dynamic context containing the method parameters; upon completion, a result is returned to the client.
    ... Spelling and binding serve distinct purposes. Spelling is a convenience for clients: it provides flexibility in how things are written. Binding is a fundamental property of the object system: the provision of multiple implementations for a single semantic abstraction» [MCOM 6].

    «The application of object-oriented design methods leads to an object-oriented decomposition, in which we view the world as a collection of objects that cooperate with one another to achieve some desired functionality» [Booch, 1991, p 516, quoted from [Quib: glossary: funktionale Dekomposition]].
    «Computation is performed by objects communicating with each other, requesting that other objects perform actions. Objects communicate by sending and receiving messages. A message is a request for action bundled with whatever arguments may be necessary to complete the task.» [Leda 11]
    System Architecture at the basic model level: client-server interacting-components[^]
  • components (computational agents) = "objects"
  • interaction = client object sends service-request "messages" to a specific receiver object (service provider), and receiver sends reply messages back to the sender
  • connectors = "object references", transport the messages
  • Relaxation: Impure Object Model - allow clients other than objects
    • «The abstract object model postulates a set of clients that issue requests for service and a set of objects that perform services. (An object can be a client, but clients need not be objects.)» [MCOM 6]. The same object can provide for several services.
  • Elaborations wrt. implementation inheritance:
    the monolithic model vs. the multi-object model
    • «The disadvantage of the monolithic object model is that it fails to handle» the case of repeated inheritance «where an object visibly contains more than one base component of the same type. Clearly, multiple base components of the same type cannot be distinguished by type, but only by value» [MCOM 5].
    entity:
    State
    		   
    /|\
    |
    current
    |
    |     		<<-
     
    event:
    update
    agent:
    Object
    methods
    message queue
    		<<-
     
     
     
    event:
    create
     
     
    /|\
    |
    arguments
    |    		 \ sender (from),
      \ receiver (to)
        \
          \
    entity:
    Message
    |
    identifies
    |
    \|/
    entity:
    Operation
    		 
    ____
    event:
    request
    Evaluation:

    (+) «[O]rganizing a loose collection of autonomous but interacting units, resonates with problem solving skills from other domains. People are used to thinking about the organization of individuals, such as on a committee, or solving problems by piecing together the services provided by many different vendors. Thus, unlinke the situation with imperative programming, the metaphor applied in the object-oriented approach is more natural to human problem solvers» [Leda, 12].

    (-) Inappropriate for arithmetics: «For most people, it is natural to think of arithmetic in terms of expressions that state "do something to the following numbers." It is less natural to think of arithmetic as being performed by one number ... upon the rest. But in Smalltalk, the expression 4 + 5 is to be understood not as "apply the plus operation to 4 and 5," but instead as "send a message to the object 4 asking it to add the value of the object 5 to its own value." ... This will strike many people as a strange and artificial way to think about arithmetic and about integers» [PLing, 246].

    «The model is based on the following concepts we deem the essential concepts of objects ...:

    Request. «A request is an event: a unique occurence during the execution of the computational system. A request has associated information, which consists of an operation and zero or more parameter values. A value may identify an object; ... The operation identifies the service to be performed; the parameters provide the additional information needed to specify the intended behavior.» [MCOM 5f].
    Operation. «... An operation is simply an identifiable entity. Its purpose is to characterize sets of requests with similar intended semantics. To allow operations to have asssociated sematics in a computation system, we believe it is necessary to allow developers to create operations (i.e., uniquely allocate an operation for a particular use).» [MCOM 5f]. A generic operation «is implemented by multiple programs, from which a single program is selected dynamically for each request» [MCOM 6].

    Procedural abstraction in this MOC is a combination of request, update, and create events. (_If_) the sender of all requests and the object of all updates is the same object o then the programmer can reify the result of the procedural abstraction in his object system as a method of o. Other cases would require an extension of the message passing MOC. A few proposals exit. For example, Christensen's activities [TODO].

    Extension: different Message Filtering MOCs / Systems
    /|\
    |
    unicast to explicit receiver
    through object references
        multicast to implicit receivers    
    (implicit transmission infrastructure)
    |
    \|/     		    
    agent:
    Object
    methods
    m-queue
    m-filters
    |    |
    controls
    navigation bar: Message Passing
  • message passing diagrams
  • client-server architecture
  • object systems (model of computation)
  • message filtering systems
  • message passing meta-programming
  • In (a) the composition filters object model and (b) the layered object model, an object can control other objects ("internal objects") and define filters for messages sent, respectively, to these objects, or to and from these objects. For details see the programming systems Sina and LayOM, respectively.

  • Another possibility is to have filters associated with the connectors between objects which transport the messages. For example in the programming systems FLO.
    •  
    Multiagent MOC / Systems or Event-driven Systems
    PHENOMENOLOGICAL «The multiagent model structures an interactive system into a collection of specialized agents that produce and react to events. An agent is a complete information processing system: it includes event receivers and event transmitters, a memory to maintain a state, and a processor that cyclically processes input events, updates its own state, and may produce events or change its interest in input event classes. Agents communicate with other agents, including the operator [computer user]. ...» [DevSWforUI, p 169]
    An event is characterized by its event class and, depending on the event class, arguments.

    System Architecture at the basic model level: event-driven interacting-components[^]
  • components (computational agents) = "agents"
  • interaction = broadcast of "events" to all agents in the system (which may process or ignore them)
  • connector = the implicit broadcasting infrastructure

    • Procedural abstraction in this MOC is a combination of update and broadcast events. The phenomenological part of the multiagent MOC contains no entities which could directly reify this procedural abstraction. But the causal model might contain entities in its explanation of agents' behavior which could reify the procedural abstraction ... [TODO]

    		CAUSAL
    entity:
    State
    		     
    /|\
    |
    current
    |
    |     		<<-
    event:
    update
    		For an causal model of computation, it remains to explain how the agent determins which events to broadcast and how to update its state, and in which order.
    agent:
    Agent
    transmitters
    receivers
    |
    event:
    broadcast
    |
    \|/
    entity:
    Event
    event-class
    arguments
    		   
    /|\
    |
    semi-explicit (and explicit) interaction:
        agent explicitly causes event broadcast (or message sending to explicit receiver)    
    entirely implicit interaction
    |
    \|/
    navigation bar: Coupling
  • coupling relations / bonds
  • quantity-dependency system view
  • object change propagation systems
  • object constraint programming
    • Object Change Propagation MOC / Systems
    PHENOMENOLOGICAL
    System Architecture:
  • components = "objects", "entities" ...
  • interaction = propagation of state change
  • connectors = change propagating relationships
    • «By changing its own state or behavior, the entity may cause changes in other entities. Naturally, this is impossible if this entity is totally isolated from others; the saying presumes that:
    • each entity has many relationships with other entities,
    • these relationships can propagate changes in one entity to the others without explicit communication (be it command-style, or negotiation-style communication).»
    [I Bider, M Khomyakov: If You Wish to Change the World, Start with Yourself: An Alternative Metaphor for Objects Interaction; The Journal of Conceptual Modeling; Issue Number 18; February, 2001.

    For examples and CAUSAL MODELS see different kinds of constraint slots in objects.

    entity:
    State
    /|\
    |
    current
    |
    |
    agent???
    Object
    constraints
    		<<-
     
    event:
    update
     
    		----.
    <<-'
     
     
    Procedural abstraction in this MOC is a combination of update events. A reification of this procedural abstraction in the software system (as an operation or so) is not in the spirit of the object change propagation MOC. But hybrid MOCs, eg., change propagation + message passing, may accommodate for such procedural abstractions ... [TODO]