460-4022/01 – Programming Paradigms (PP)
Gurantor department | Department of Computer Science | Credits | 6 |
Subject guarantor | Ing. Marek Běhálek, Ph.D. | Subject version guarantor | Ing. Marek Běhálek, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | 1 | Semester | summer |
| | Study language | Czech |
Year of introduction | 2010/2011 | Year of cancellation | 2019/2020 |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
The course should provide both theoretical and practical knowledge of declarative programming languages. The students will deal with programming techniques based on recursive data structures and general recursive specification. Both logic programming and functional programming is dealt with.
Logic programming in Prolog and functional programming in Haskell.
Teaching methods
Lectures
Tutorials
Summary
Students will get knowledge of logic programming, Prolog specifically, a functional programming language Haskell.
Compulsory literature:
The materials are continuously published on: http://www.cs.vsb.cz/behalek/education/pp/
Recommended literature:
Materials for programming language Haskell from: http://www.haskell.org
Materials for programming language Prolog from: http://www.swi.psy.uva.nl/projects/SWI-Prolog/
Simon Thompson: Haskell: The Craft of Functional Programming, Addison-Wesley Professional; 3 edition (October 2, 2011), English, ISBN-10: 0201882957
Way of continuous check of knowledge in the course of semester
Conditions for credit:
At least 21 points required. Students obtain points based on solution of two projects.
E-learning
Other requirements
Additional requirements are placed on the student.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Lectures:
Introduction:
Goals and contents of the course, requirements, organization, resources. Programming languages classification. Usage and applications of compilers. Source and target languages.
History of programming languages and compilers:
theoretical aspects, first programming languages and compilers, high-order programming languages, structured programming, modular languages, object-oriented languages, scripting languages.
Functional and logic programming languages: Declarative style of programming, advantages and disadvantages of this approach, basics of Lambda Calculus, implementation of practical examples in Haskell.
Scripting languages: description of differences between traditional languages and scripting languages, description of some representatives of scripting languages, practical examples, overview of PHP.
Imperative programming languages: basic principles, imperative programming languages. Examples of different programming paradigms.
Object-oriented programming: basic principles, less known object-oriented programming languages.
Structure and functions of a compiler:
Source code models, transformations. Compiler organization - phases, passes. One-pass and optimising compilers. Utility programs. Testing and maintenance of a compiler.
Lexical analysis:
Function of a scanner, symbol representation. Regular languages, finite automaton, regular expression. Scanner implementation.
Parsing:
Goals and methods of the syntactic analysis. Top-down and Bottom-up analysis. LL(1) grammars, FIRST and FOLLOW set computation. Parsing table.
Parser implementation:
Pushdown automaton for LL(1) languages. Recursive descent analysis.
Syntax directed translation:
Translation grammar, attribute translation grammar. Implementation of attribute translation during top-down parsing. Compiler Compiler JavaCC.
Symbol table:
Basic notions - binding, range, visibility, life time. Functions of symbol table. Programming language model. Organization of symbol table. Block structured symbol table. Implementation.
Internal representation of program:
Formats of internal representation - graph, stack code, three-address code. Implementation of three-address code. Translation of expressions. Array items addressing. Translation of Boolean expressions. Generation of stack code as attribute translation.
Run-time program structure:
Run-time system. Subroutines - activation, static and dynamic structure, activation record. Memory organization, memory allocation for activation records, access pointers. Parameter passing.
Projects:
There will be two projects in this course. Firs will be an implementation of some task in less known programming language. Second will be a simple compiler.
Computer labs:
Examples of different programming paradigms.
Examples of declarative style of programming. Practical implementation of some simple tasks in Haskell.
Implementation of some tasks in Haskell.
Scripting languages: Implementation of simple task in PHP.
Imperative and object oriented languages. Examples of programs written in some less known languages.
Work on firs project.
Implementation in simple filters and lexical analyzers.
Practical realization of grammars for a basic constructions common in programming languages.
Implementation of algorithms for a computation of sets FIRST a FOLLOW.
Demonstration of LL(1) a LR(1) based syntactic analyzers. Implementation of a syntactic analyzer using recursive descent.
Implementation of a simple compiler using compiler compiler JavaCC.
Work on second project.
Conditions for subject completion
Conditions for completion are defined only for particular subject version and form of study
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction