Action semantics

Last updated

Action semantics is a framework for the formal specification of semantics of programming languages invented by David Watt and Peter D. Mosses in the 1990s. It is a mixture of denotational, operational and algebraic semantics.

Contents

Action semantics aim to be pragmatic, and action-semantic descriptions (ASDs) are designed to scale up to handle realistic programming languages. This is aided by the extensibility and modifiability of ASDs. This helps to ensure that extensions and changes do not require too many changes in the description. This is in contrast to the typical case when extending denotational or operational semantics, which may require reformulation of the entire description.

The action semantics framework was originally developed at the University of Aarhus and the University of Glasgow. Groups and individuals around the world have since contributed further to the approach.

Semantic entities

An important part of action semantics that gives it a modularity not seen in previous programming language semantics is the use of first-order semantic entities. First-order refers to how, unlike in denotational semantics, where a semantic function can be applied to another semantic function, in action semantics, a semantic entity cannot be applied to another semantic entity of its kind. [1] Furthermore, the semantic entities utilized by action semantics broaden the framework’s ability to describe a programming language’s constructs by serving to denote both program behavior that is independent of any particular implementation and the way in which parts of a program influence the overall performance of the whole. The appropriately named action notation is employed to express the three types of semantic entities found in action semantics: actions, data, and yielders. The central semantic entity in this framework is actions, with data and yielders occupying supplementary roles. [2] More specifically, actions are the mechanisms through which yielders and data are processed. [1] An action, which can occur within another action, is a step-by-step representation of program behavior, where each step accesses current information, changes current information, or does both. Yielders appear within actions and only access current information. A yielder entity is capable of being evaluated, and when it is, the product is a datum entity. [2]

Action entities

Action entities can directly represent programs’ semantics by describing possible program behaviors or represent, in a more indirect way, the impact that individual pieces of a program, like statements or expressions, have on the semantics of the program as a whole. [2] They model computational behavior by indicating changes in state through their generation of new values from passed values. Specifically, an action accepts data passed to it via the current information — the transient data given to it, the bindings received by it, and the current state of storage — and, from this, gives new transient data, creates new bindings, updates the state of storage, or any combination of these. [1] An action entity can culminate in four possible ways. It can: complete (terminate normally), escape (terminate in an exception), fail (alternative is discarded), or diverge (not terminate). [2]

There are four categories of information that are processed by action performance. Transient information corresponds to intermediate results and is accessible for immediate use by the action. [2] The data that comprises transient information encompasses the values given by expressions. If these values are not immediately used, they are lost. [1] Scoped information corresponds to symbol tables and can be referenced from anywhere within the action and its sub-actions. [2] It is also possible for such information to be hidden within a sub-action, via the creation of an inner scope, in which case it would be only locally accessible within that scope, to that sub-action. [1] Stable information corresponds to values assigned to variables and can be modified in the action performance. [2] Because alterations to storage during the performance of an action are persistent, only explicit actions can cause such modifications. [1] In accordance with this, stable information is available until it is explicitly destroyed. And, unlike scoped information, it cannot be hidden. Permanent information corresponds to data exchanged between actions and can be extended but not modified. Transient information is produced only when an action completes or escapes, and scoped information is produced only when an action completes. The modification of stable information and the extension of permanent information must take place during action performance. [2]

An action entity has five different facets, one for processing that does not rely on information, and four for processing each of the four different types of information. The basic facet, an example of which would be control flows, is not tied to information of any kind. The functional facet deals with the processing of transient information and is characterized by actions giving and accepting data. The declarative facet deals with the processing of scoped information and is characterized by actions creating and receiving bindings. The imperative facet deals with the processing of stable information and is characterized by actions allocating and freeing storage cells, and fetching and modifying the data stored in them. The communicative facet deals with processing permanent information and is characterized by actions sending and receiving messages and “offer[ing] contracts to agents.” [2] There are two different kinds of actions in terms of their effect on the information in each facet. Primitive actions only affect the information in one facet. Action combinators permit actions that involve multiple facets, governing how control and information flows for each facet involved in a combined action. [2] In combining actions, action combinators governor the sequencing of sub-action performances and the incoming and outgoing flows of data for each sub-action. [1]

Data entities

Data entities are the items that comprise the information processed in action entities. The data is arranged into structures known as sorts. Sorts are sets of mathematical objects, include operations that can be performed on those objects, and are defined according to algebraic criteria. [1] These structures allow access to each individual entity. Examples of data entities can include concrete elements like maps, lists, sets, strings, characters, numbers, and truth values, more abstract elements used solely for the purpose of some computational operation, namely data access, like agents, cells corresponding to memory locations, and tokens, or elements like contracts and messages that are a composite of data components. [2] An abstraction is a data entity that encapsulates an action entity, in which case enacting the abstraction results in the action being performed. This is the technique by which action semantics represents the declaring and invoking of subprograms. [1]

Yielder entities

Yielder entities consist of unevaluated quantities of data. The values of these quantities are contingent on the current information and state of computation. Yielders draw on transient data, bindings, and storage to select the information to be processed by actions. [1] It is during action performance that yielders are evaluated, and their evaluation results in data entities. While the current information can influence the data produced by the evaluation of a yielder entity, the evaluation cannot influence the current information. If data operations are employed on yielder entities, compound yielder entities may be formed as a result. [2]

Action notation

Regular English words serve as the symbols of action notation. Action notation is designed to simulate natural language, which is illustrated in the parts of speech used to denote semantic entities. Action entities are represented by verb phrases and data and yielder entities by noun phrases. The result of this choice of symbols is a framework that is highly readable and no less formal than other frameworks since it remains precisely defined. [2]

Other key aspects

Action semantics embodies a level of abstraction that increases its comprehensibility. The specifics of the control and data flows that an action involves are implicitly incorporated in the action, as opposed to being explicitly expressed as the details of semantic functions are in denotational semantics. When an action is performed, most information processing and manipulation occurs automatically. [1]

Program phrases are mapped to actions when constructing a definition of a programming language’s meaning in action semantics. The execution of a programming phrase corresponds to the performance of the action to which it maps. [1]

The programming language specification generated from the application of action semantics can be broken down into a lower level (microsemantics) and an upper level (macrosemantics). The lower level consists of defining the meaning of action notation, while the upper level consists of defining the meaning of a programming language, using action notation to do so. [1]

Related Research Articles

<span class="mw-page-title-main">Semantics</span> Study of meaning in language

Semantics is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and computer science.

<span class="mw-page-title-main">Semantic Web</span> Extension of the Web to facilitate data exchange

The Semantic Web, sometimes known as Web 3.0, is an extension of the World Wide Web through standards set by the World Wide Web Consortium (W3C). The goal of the Semantic Web is to make Internet data machine-readable.

The Resource Description Framework (RDF) is a World Wide Web Consortium (W3C) standard originally designed as a data model for metadata. It has come to be used as a general method for description and exchange of graph data. RDF provides a variety of syntax notations and data serialization formats, with Turtle currently being the most widely used notation.

In computer science, denotational semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects that describe the meanings of expressions from the languages. Other approaches providing formal semantics of programming languages include axiomatic semantics and operational semantics.

<span class="mw-page-title-main">Data model</span> Model that organizes elements of data and how they relate to one another and to real-world entities.

A data model is an abstract model that organizes elements of data and standardizes how they relate to one another and to the properties of real-world entities. For instance, a data model may specify that the data element representing a car be composed of a number of other elements which, in turn, represent the color and size of the car and define its owner.

Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object—a resource—is created in a system as a proxy for a non computable/addressable object. By means of reification, something that was previously implicit, unexpressed, and possibly inexpressible is explicitly formulated and made available to conceptual manipulation. Informally, reification is often referred to as "making something a first-class citizen" within the scope of a particular system. Some aspect of a system can be reified at language design time, which is related to reflection in programming languages. It can be applied as a stepwise refinement at system design time. Reification is one of the most frequently used techniques of conceptual analysis and knowledge representation.

A modeling language is any artificial language that can be used to express data, information or knowledge or systems in a structure that is defined by a consistent set of rules. The rules are used for interpretation of the meaning of components in the structure Programing language.

In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and often crosses over with, the semantics of mathematical proofs.

<span class="mw-page-title-main">Entity–relationship model</span> Model or diagram describing interrelated things

An entity–relationship model describes interrelated things of interest in a specific domain of knowledge. A basic ER model is composed of entity types and specifies relationships that can exist between entities.

<span class="mw-page-title-main">Data modeling</span> Creating a model of the data in a system

Data modeling in software engineering is the process of creating a data model for an information system by applying certain formal techniques. It may be applied as part of broader Model-driven engineering (MDD) concept.

In computer programming, operators are constructs defined within programming languages which behave generally like functions, but which differ syntactically or semantically.

<span class="mw-page-title-main">Business Process Model and Notation</span> Graphical representation for specifying business processes

Business Process Model and Notation (BPMN) is a graphical representation for specifying business processes in a business process model.

<span class="mw-page-title-main">IDEF1X</span>

Integration DEFinition for information modeling (IDEF1X) is a data modeling language for the development of semantic data models. IDEF1X is used to produce a graphical information model which represents the structure and semantics of information within an environment or system.

Semantic integration is the process of interrelating information from diverse sources, for example calendars and to do lists, email archives, presence information, documents of all sorts, contacts, search results, and advertising and marketing relevance derived from them. In this regard, semantics focuses on the organization of and action upon information by acting as an intermediary between heterogeneous data sources, which may conflict not only by structure but also context or value.

<span class="mw-page-title-main">Semantic technology</span> Technology to help machines understand data

The ultimate goal of semantic technology is to help machines understand data. To enable the encoding of semantics with the data, well-known technologies are RDF and OWL. These technologies formally represent the meaning involved in information. For example, ontology can describe concepts, relationships between things, and categories of things. These embedded semantics with the data offer significant advantages such as reasoning over data and dealing with heterogeneous data sources.

Entity Framework (EF) is an open source object–relational mapping (ORM) framework for ADO.NET. It was originally shipped as an integral part of .NET Framework, however starting with Entity Framework version 6.0 it has been delivered separately from the .NET Framework.

A triplestore or RDF store is a purpose-built database for the storage and retrieval of triples through semantic queries. A triple is a data entity composed of subject–predicate–object, like "Bob is 35" or "Bob knows Fred".

Business semantics management (BSM) encompasses the technology, methodology, organization, and culture that brings business stakeholders together to collaboratively realize the reconciliation of their heterogeneous metadata; and consequently the application of the derived business semantics patterns to establish semantic alignment between the underlying data structures.

Knowledge extraction is the creation of knowledge from structured and unstructured sources. The resulting knowledge needs to be in a machine-readable and machine-interpretable format and must represent knowledge in a manner that facilitates inferencing. Although it is methodically similar to information extraction (NLP) and ETL, the main criterion is that the extraction result goes beyond the creation of structured information or the transformation into a relational schema. It requires either the reuse of existing formal knowledge or the generation of a schema based on the source data.

Formal semantics is the study of grammatical meaning in natural languages using formal tools from logic, mathematics and theoretical computer science. It is an interdisciplinary field, sometimes regarded as a subfield of both linguistics and philosophy of language. It provides accounts of what linguistic expressions mean and how their meanings are composed from the meanings of their parts. The enterprise of formal semantics can be thought of as that of reverse-engineering the semantic components of natural languages' grammars.

References

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 Slonneger, Kenneth; Kurtz, Barry L. (1995). Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach. Reading, MA: Addison-Wesley.
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 Peter D. Mosses (1996) Theory and Practice of Action Semantics. Publication. Aarhus, DK: University of Aarhus, 1996. BRICS Report Series RS9653.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.