Functional Programming
Semestr: Summer
Range: 2P+2C
Completion:
Credits: 6
Programme type:
Study form: Fulltime
Course language: English
Summary:
This course introduces students into the techniques of functional programming, the advantages and disadvantages of this programming paradigm, and its use in practice. This approach is declarative in the sense that the programmer symbolically describes the problem to be solved, rather than specifying the exact sequence of operations required to solve it. It allows focusing on the essence of the solved problem and implementing even more complex algorithms compactly. Functional programming has notable advantages for parallelization and automated verification of algorithms, and the most useful functional programming concepts are increasingly often introduced to standard programming languages. Because of the focus of functional programming on symbols, rather than numbers, functional programming has been heavily used in in artificial intelligence fields, such as agent systems or symbolic machine learning. This course is also part of the inter-university programme prg.ai Minor. It pools the best of AI education in Prague to provide students with a deeper and broader insight into the field of artificial intelligence. More information is available at https://prg.ai/minor.
Keywords:
Course syllabus:
1. Introduction to declarative programming languages. Comparison to
classical imperative languages. Main principles and practical
applications of functional programming.
2. LISP: basic constructions of the language, atoms, lists, recursion
3. LISP: basic language idioms, atoms, lists, recursion
3. LISP: built-in functions, data structures, lambda abstraction
4. LISP: built-in high-order functions
5. LISP: infinite data structures, closures
6. Introduction to Lambda calculus, relation to functional programming
7. Equivalence of functional programming to Turing machine
8. Types in functional languages, their role and consequences to the
expressive power of the languages, typed Lambda calculus
9. Haskell: types, patterns, built-in functions, lambda abstraction
10. Haskell: lazy evaluation, partial function application
11. Haskell: monads
12. Automated optimizations in functional programming, formal
verification of functional programs
13. Functional programming and parallel computation
14. Functional constructs in popular programming languages and tools
Seminar syllabus:
1. Scheme. First look at Scheme and its environment. Program debugging. Basic examples.
2. Recursion. Accumulator.
3. Lambda abstraction.
4. Tail recursion. High-order function.
5. Haskell.
6. Prolog as a database. Facts, rules, queries.
7. Recursion. Program debugging.
8. Unificaton. List operations.
9. List, cut and negation operations.
10. Search algorithms, individual task assignment
11. Search algorithms
12. Constraint logic programming
13. Constraint logic programming
14. Credits
Literature:
Hudak, Paul, and Joseph H. Fasel. "A gentle introduction to Haskell." ACM Sigplan Notices 27.5 (1992): 1-52.
Harvey, Brian, and Matthew Wright. Simply Scheme: introducing computer science. Mit Press, 1999.