Declarative Computational Model
Declarative Computation Model
Language syntax
The syntax of a language defines what are the legal programs, i.e., programs that can be successfully executed.At this stage we do not care what the programs are actually doing.
| Statement (Sentence) | Token (Word) |
|---|---|
| Sequence of Tokens (Words) | Sequence of Characters (Letters) |
Context-free and context-sensitive grammars
For most practical programming languages, there is usually no context-free grammar that generates all legal programs and no others.For example, in many languages a variable has to be declared before it is used. This condition cannot be expressed in a context-free grammar because the nonterminal that uses the variable must only allow using already-declared variables. This is a context dependency. A grammar that contains a nonterminal whose use depends on the context where it is used is called a context-sensitive grammar.
Language Semantics
The Kernel Language Approach
In this approach, all language constructs are defined in terms of translations into a core language known as the kernel language. The kernel language approach consists of two parts:
- First, define a very simple language, called the kernel language. This language should be easy to reason in and be faithful to the space and time efficiency of the implementation. The kernel language and the data structures it manipulates together form the kernel computation model.
- Second, define a translation scheme from the full programming language to the kernel language.Each grammatical construct in the full language is translated into the kernel language. The translation should be as simple as possible. There are two kinds of translation, namely linguistic abstraction and syntactic sugar.
Formal Semantics
There are four widely used approaches to language semantics:
- Operational Semantics
- Axiomatic Semantices
- Denotational Semantics
- Logical Semantics
Linguistic Abstraction
A "Liguistic Abstraction" is a way to extende a language's behaviour by building atop of its Kernel Language, by first:
- Defining a new grammatical construct.
- Define its translation into the kernel language.
Other Translation Approaches
The Interpreter Approach
The Single-Assignment Store
Declarative Variables
Once bound, a declarative variable stays bound throughout the computation and is indistinguishable from its value.
Value Store
A store where all variables are bound to values is called a value store.Another way to say this is that a value store is a persistent mapping from variables to values.A value is a mathematical constant.
Value Creation
The basic operation on a store is binding a variable to a newly created value.We will write this as xi=value.Here xi refers directly to a variable in the store (it is not the variable’s textual name in a program!) and value refers to a value, e.g., 314 or [1 2 3].
Value Identifiers
So far, we have looked at a store that contains variables and values, i.e., store entities, with which calculations can be done.It would be nice if we could refer to a store entity from outside the store.This is the role of variable identifiers.A variable identifier is a textual name that refers to a store entity from outside the store.The mapping from variable identifiers to store entities is called an environmen
Value Creation with Identifiers
Partial Value
Variable-Variable Binding
Dataflow Variables
Declarative variables that cause the program to wait until they are bound are called dataflow variables.The declarative model uses dataflow variables because they are tremendously useful in concurrent programming, i.e., for programs with activities that run independently.If we do two concurrent operations, say A=23 and B=A+1, then with the fifth case this will always run correctly and give the answer B = 24.
Kernel Language
The declarative model defines a simple kernel language.All programs in the model can be expressed in this language.We first define the kernel language syntax and semantics.
Syntax
Statement Syntax
Value Syntax
Kernel language semantics
Basic Concepts
The Abstract Machine
We define the semantics of the kernel language as an operational semantics, i.e., it defines the meaning of the kernel language through its execution on an abstract machine.We first define the basic concepts of the abstract machine: environments, semantic statement, statement stack, execution state, and computation