Denotational engineering of programming languages

elective monographs

Foundations of mathematics 1000-211bPM
Languages, automata and computations 1000-214bJAO

Introductory course in programming, for instance Introductory programming (imperative approach) or Introductory programming (functional approach)

A. Techniques of defining (designing) programming languages for sequential programming (no concurrency) based on the models of denotational semantics and many-sorted algebras. Languages are developed from denotations to syntax, which guarantees the existence of a denotational semantics as a homomorphism from an algebra of syntax into an algebra of denotations.

B. Techniques of defining correct-program constructors for languages with a denotational semantics. Program correctness is understood as in Hoare’s logic but also covers so-called “clean termination”, which means a termination without an error message. Both techniques (i.e. of designing and using a programming language) are illustrated on an example of a virtual programming language Lingua.

C. Practical learning of self-organization of work in an innovative TI startup.

1. Tools

1.1. A metalanguage MetaSoft ― basic notational conventions

1.2. Fixed-point equations in chain-complete partially-ordered sets (CPS)

1.3. Equational grammars in a CPS of formal languages

1.4. A CPS of binary relations

1.5. A CPS of denotational domains

1.6. Abstract errors

1.7. Three-valued predicate calculus

1.8. Many-sorted algebras in denotational models of programming languages

2. Semantic correctness of programs

2.1. Partial correctness

2.2. Total correctness with clean termination

3. Denotational models of programming languages

3.1. The idea of the method

3.2. Expressions ― data and their types

3.3. Instructions without procedures

3.4. Imperative and functional procedures

4. The construction of correct programs

4.1. Construction rules

4.2. Transformation rules

1. Basic sources: mathematics and computer science

1.1. A. Blikle, Denotational Engineering of Programming Languages, preprint

1.2. Papers listed in the “Literature” section of this book

2. Supplementary sources: work organization

2.1. A.Blikle, Doktryna Jakości – wydanie II turkusowe (hardcopy and pdf)

2.2. A. Blikle, A Teal Doctrine of Quality, preprint

2.3. Papers listed in the “Literature” section of this book

Both books are freely available in PDF versions (updated regularly) on Andrzej Blikle’s site: www.moznainaczej.com.pl.

The listeners will be encouraged to submit their comments, corrections, and additions to both materials described above.

Knowledge ― the student knows and understands:

1. basic components of a denotational model of programming languages that include three algebras ― of denotations, of abstract syntax and of concrete syntax,

2. the techniques of building an algebra of denotations, and of deriving from it the algebras of abstract and concrete syntax as well as the introduction of so-called colloquialisms.

Skills ― the student can:

1. design a simple programming language with a full denotational model and with rules of the construction of correct programs,

2. acquire information from literature, knowledge databases, Internet, and other reliable sources, to integrate them, interpret them, draw conclusions, and formulate opinions [K_U02],

3. plan and implement their own lifelong learning [K_U09].

Social competence ― the student can:

1. Perform research and development tasks in collaborative teamwork.

2. Knows the basic rules of organizing teamwork in relational mode (building partnerships) rather than supervising-transactional mode (executing commands and the principle of "something for something"). More on this in the "Assumptions" section.

We will look at the community of listeners and instructors as an innovative startup whose task is to pre-master and implement new technologies for building programming languages and constructing correct programs. The working principles of the startup correspond to modern methods of organizing work and in particular the work of IT teams (Agile, TQM, teal, etc.)

The substantive startup work will be implemented in the project teams selected during the initial training period.

The division into teams and the determination of the theme of projects will be made by the entire startup team. "Open space technology" can be used to create design teams. The themes of the projects can be theoretical, implementational, or mixed. Teams should include at least two listeners, and each listener should belong to at least one team. The teams agree on the cooperation rules, including ― perhaps ― the sharing of tasks and the definition of the vendor-receiver relationship (the company's process structure).

The work in each of the project teams will be carried out in two stages:

1. presentation and acceptance of topics and project execution plan,

2. presentation of results of project implementation.

The evaluation of each stage will have a seminar mode involving the whole startup team. Rating Scale: Rejected (2), Basic (3), Good (4), very good (5), outstanding (6).