Course details

Programming Language Theory

TJD Acad. year 2006/2007 Winter semester

Current academic year

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

Hruška Tomáš, prof. Ing., CSc. (DIFS)

Language of instruction

Czech, English

Completion

Examination

Time span

  • 39 hrs lectures

Department

Department of Information Systems (UIFS)

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

Back to top