Faculty of Information Technology, BUT

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

Czech

Completion

Examination (written+oral)

Time span

39 hrs lectures

Assessment points

Department

Lecturer

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.

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

discussion on the doctoral lectures, assembling of a report

Controlled instruction

lectures only

Course inclusion in study plans

Back to top