Course details
Programming Language Theory
TJD Acad. year 2007/2008 Winter semester
Importance of rewriting systems in the computer science. Basic isues of the rewriting systems. The rewriting systems as the means of definition. The theory of rewriting systems. Limited and unambigously normalising systems, crtical pairs, confluent rewriting systems. Knuth-Bendix completing algorithm. Equational systems, functional languages, logic languages. Algebraic specification. The synthesis of functional programs from algebraic specifications. Graph rewriting systems. Graph rewriting, algebraic approach, expressional approach. Rooted graphs and their rewriting. Specification languages for graph rewriting systems (Lean, Dactl). Semigraph grammars as the translation model. Denotational semantic. Kinds of the formal sematic definition. Domens, the types of domain specification and the typical program construction modelling. Principles of object-oriented programming languages. Implementation techniques.
Guarantor
Language of instruction
Completion
Time span
- 39 hrs lectures
Department
Subject specific learning outcomes and competences
The ability to define formally and th use the definition of the programming language semantic.
Learning objectives
To obtain wide knowledge of the programming language semantic based on the rewriting systems. To obtain the ability to specify formally the programming language semantic using the denotational method.
Prerequisite knowledge and skills
There are no prerequisites
Study literature
- Peyton Jones S., L.: The Implementation of functional programming languages, Prentice Hall 1986
- Sethi R.: Programming Languages Concepts, Addison Wesley 1989
- Nilson U. - Matuszynski J.: Logic, Programming and Prolog, John Wiley 1990
- Nielson R.,H. - Nielson F.: Semantics with Applications - A Formal Introduction, John Wiley 1992
Fundamental literature
- Aho, V. A. - Sethi, R. - Ullmann, J. D. : Compilers - Principles, Techniques, and Tools, Addison - Wesley Publishing Company 1987
- Gordon, J., C.: Programming language Theory and its Implementation, Prentice Hall 1988
- Bird, R. - Walder, P.: Introduction to Functional Programming, Prentice Hall 1988
- Tennent, R., D.: Principles of programming languages, Prentice Hall 1981
Syllabus of lectures
- Importance of rewriting systems in the computer science. Basic isues of the rewriting systems.
- The rewriting systems as the means of definition.
- The theory of rewriting systems. Limited and unambigously normalising systems, crtical pairs, confluent rewriting systems.
- Knuth-Bendix completing algorithm.
- Equational systems, functional languages, logic languages.
- Algebraic specification. The synthesis of functional programs from algebraic specifications.
- Graph rewriting systems. Graph rewriting, algebraic approach, expressional approach.
- Rooted graphs and their rewriting.
- Specification languages for graph rewriting systems (Lean, Dactl).
- Semigraph grammars as the translation model.
- Denotational semantic. Kinds of the formal sematic definition.
- Domains, the types of domain specification and the typical program construction modelling.
- Principles of object-oriented programming languages. Implementation techniques.
Progress assessment
Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.
Controlled instruction
lectures only