Logic and Functional Programming
Lecture is addressed to second year students, English.
Organizatorial items
- Lecturer and Teaching Assistant: Mircea Marin
- Schedule: 14 lectures and labs, every week,
- Lecture: Monday, 11:20-12:50
- Labs: Monday (sgrs. 1,4,6) and Tuesday (sgrs. 2,3,5)
Topics
- Introduction to Functional Programming (7 weeks):
programming in Racket and Haskell
- theoretical aspects: lambda calculus, etc.
- Introduction to logic programming (7 weeks):
- logical foundations, computational model
- practical programming in Prolog: programming techniques;
selected examples; efficiency issues
Grading
- 20%: in-class quizzes, individual assignments
- 25%: partial exam (quiz) from functional programming
-- week 8, on the e-learning platform of WUT
- 25%: partial exam (quiz) from logic programming
-- week 14, on the e-learning platform of WUT
- 30%: written exam (session)
Links to lecture notes and labworks
- Lecture 1: Introduction: Programming paradigms. Characteristics of functional programming.
- Lecture 2: Theoretical foundations. The lambda calculus.
- Lecture 3: Environment-based computations. Functions as values. Tail recursion. Structural recursion.
- Lecture 4: Advanced uses of functions. Local definitions; functions with local state; variadic functions; problem solving strategies.
- Lecture 5: Lazy evaluation. Introduction to Haskell.
- Lab 5: A crash course to Haskell (pdf)
- Lecture 6: Haskell. Overloading and type classes. Algebraic types.
- Lab 6
- ASSIGNMENT: Exercises from sect. 6.2 and 6.3 from here.
Answers to Haskell exercises.
- Lecture 7: Type Checking and Type Inference in Haskell. Simulating lazy evaluation in Racket.
- Lab 7: Review of material about Functional Programming (See pdf file).
Answers to miniproject about power series.
- Lecture 8: Logic, Logic Programming, and Prolog.
- Lecture 9: Foundations of Logic Programming. Unification, SLD-resolution, SLDNF-resolution.
- Lab 9: Warmup exercises (pdf).
Answers to warmup exercises.
- Lecture 10: Recursion in Prolog
- Lab 10
- ASSIGNMENT: Exercises
- Solutions to proposed exercises (pdf)
- Lecture 11: Efficiency issues in Prolog. Declarative and procedural thinking.
Controlling the search for answers with cut (!) and fail.
Tail recursion. Techniques to write efficient code.
- Lecture 12: Working with lists. Difference lists: applications. The maze problem.
Lab 12: working with difference lists
- Proposed exercises (pdf).
- Prolog program with auxiliary definitions: ListApps.pl
- Solutions to the proposed exercises: ListAppsCompleted.pl
- Lecture 13: Special applications of Logic Programming (Prolog code)
- Lecture 14:
Recommended bibliography:
For functional programming
- H. Abelson, G. J. Sussman, and J. Sussman: Structure and Interpretation of Computer Programs. MIT Press, second edition, 1996.
- M. Felleisen, R. B. Findler, M. Flatt, and S. Krishnamurthi: How to Design Programs: An Introduction to Programming and Computing. MIT Press, Cambridge, MA, USA, First edition, 2001. Available online here.
- M. Marin, V. Negru, I Dramnesc: Principles and Practice of Functional Programming. Editura UVT. 2016.
- Simon Thompson: Haskell: The Craft of Functional Programming. Second edition. Pearson Addison Wesley.
1999.
- Paul Hudak: The Haskell School of Expression. Learning Functional Programming through Multimedia. Cambridge University Press. 2007 (8th printing).
- Haskell tutorialss
For logic programming
- W.F. Clocksin and C.S. Mellish: Programming in Prolog. Fifth edition. Springer. 2003.
- M.A. Covington et al: Coding Guidelines for Prolog. Theory and
Practice of Logic Programming. 12(6): 889-927 (2012) (Highly recommended).
- P. Gloess. Constraint Logic Programming (PowerPoint format).