|
Lecturer(s)
|
-
Krupka Michal, doc. RNDr. Ph.D.
-
Bartl Eduard, doc. RNDr. Ph.D.
|
|
Course content
|
This course focuses on functional programming and related issues. In particular, the attention is paid to symbolic expressions and their evaluation, procedure application, and hierarchical data structures based on pairs. The Scheme language is used as a modeling language during the course. At the end of the course, principles of functional languages interpreters and their construction are introduced. After passing the course, the students should have gained an insight into functional programming and they should be able to adapt to any programming language with functional features. 1. Programming languages, their syntax and semantics. Functional paradigm, symbolic expressions, abstract interpreter of the Scheme language, language elements, procedures, special forms, and evaluation. 2. Creating abstractions with procedures. Lambda expressions, procedures, application of procedures, environments, lexical and dynamic scoping. High-order procedures, procedures vs. mathematical functions. Composition of procedures. Abstraction barriers. Internal definitions. Procedures as parameters and returning values of another procedures. 3. Hierarchical data. Pairs, construction of pairs. Lists. Quotation, list manipulation, mapping, appending, and generating of lists. Explicit application of procedures and evaluation of symbolic expressions, filtering, and solving problems using this techniques. Two viewpoints: program as data; data as program. 4. Induction and recursion. The induction principle. General recursion principle. Limit condition of recursion, recursion formula. Induction and soundness of recursive procedures. Y-combinator. Computation processes generated by recursive procedures. Computation processes, their types and phases. Computing efficiency of processes generated by recursive procedures. 5. Advanced list manipulation. Evaluation of postfix expressions, depth accumulation, traversing through nested lists in depth-first and breadth-first way. Representation of sets and relations by lists and high-order procedures. Combinatorics on lists, manipulation with symbolic expressions, sorting algorithms on lists. 6. Construction of a pure functional programming language. Type system and generic procedures, coercion. Data representation of the language elements. Implementation of the evaluation process. Initial environment.
|
|
Learning activities and teaching methods
|
|
Lecture, Work with Text (with Book, Textbook), Laboratory Work
|
|
Learning outcomes
|
This course aims at programming basics and focuses on functional programming.
2. Comprehension Identify proper ways to develop programs in functional paradigm.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Student performance
Throughout the course, students are required to develop several small programs. To pass the final examination students have to pass written test and develop final project.
|
|
Recommended literature
|
-
Bird R., Wadler P. (1988). Introduction to Functional Programming. Prentice Hall, Englewood Cliffs, New Jersey.
-
Dybvig, R. K. (1996). The Scheme Programming Language. Prentice Hall, A Simon and Schuster Company, Upper Saddle River, NJ.
-
Felleisen M., Findler R. B., Flatt M., Krishnamurthi S. (2001). How To Design Programs: An Introduction to Computing and Programming. The MIT Press, Cambridge, Massachusetts.
-
H. Abelson, G. J. Sussman. (1996). Structure and Implemantation of Computer Programs. Cambridge, Massachusetts.
-
Konečný, Vychodil. Paradigmata programování 1, díl A..
-
Konečný, Vychodil. Paradigmata programování 1, díl B..
-
Manis V. S., Little J. J. (1995). The Schematics of Computation. Prentice Hall, Englewood Cliffs, New Jersey.
-
Springer G., Friedman D.P. (1994). Scheme and the Art of Programming. The MIT Press, Cambridge, Massachusetts.
-
Yinong Chen. (2016). Introduction to Programming Languages: Programming in C, C++ Scheme, Prolog, C# and SOA. Kendall Hunt Pub Co.
|