Logic and Functional Programming

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

1. 20%: in-class quizzes, individual assignments
2. 25%: partial exam (quiz) from functional programming
   -- week 8, on the e-learning platform of WUT
3. 25%: partial exam (quiz) from logic programming
   -- week 14, on the e-learning platform of WUT
4. 30%: written exam (session)

Links to lecture notes and labworks

1. Lecture 1: Introduction: Programming paradigms. Characteristics of functional programming.
   • Lab 1: Introduction to Racket
     installation instructions.
     ASSIGNMENT: labwork 1.
     Answers to assigned exercises.
2. Lecture 2: Theoretical foundations. The lambda calculus.
   • Lab 2.
     A crash course to Racket (pdf)
     • Composite datatypes and local definitions (slides)
     Functions and datatypes: recursive definitions.
     Recommended exercises.
     Answers to recommended exercises.
3. Lecture 3: Environment-based computations. Functions as values. Tail recursion. Structural recursion.
   • Lab 3.
     ASSIGNMENT: labwork 3.
     Answers to labwork 3.
4. Lecture 4: Advanced uses of functions. Local definitions; functions with local state; variadic functions; problem solving strategies.
• Lab 4
• ASSIGNMENT: labwork 4.
  Answers to labwork 4.
5. Lecture 5: Lazy evaluation. Introduction to Haskell.
   • Lab 5: A crash course to Haskell (pdf)
6. 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.
7. 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.
8. Lecture 8: Logic, Logic Programming, and Prolog.
   • Review exercises.
9. Lecture 9: Foundations of Logic Programming. Unification, SLD-resolution, SLDNF-resolution.
   • Lab 9: Warmup exercises (pdf).
     Answers to warmup exercises.
10. Lecture 10: Recursion in Prolog
    • Lab 10
    • ASSIGNMENT: Exercises
    • Solutions to proposed exercises (pdf)
11. 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.
    • Lab 11: preliminary considerations for miniproject (pdf).
    • Miniproject: requirements (pdf), template files (t3.pl, t3t.pl, readme.txt)
    • Solution + implementation in Prolog
12. 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
13. Lecture 13: Special applications of Logic Programming (Prolog code)
    Lab 13
14. Lecture 14:
    Lab 14

Recommended bibliography:

For functional programming

1. H. Abelson, G. J. Sussman, and J. Sussman: Structure and Interpretation of Computer Programs. MIT Press, second edition, 1996.
2. 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.
3. M. Marin, V. Negru, I Dramnesc: Principles and Practice of Functional Programming. Editura UVT. 2016.
4. Simon Thompson: Haskell: The Craft of Functional Programming. Second edition. Pearson Addison Wesley. 1999.
5. Paul Hudak: The Haskell School of Expression. Learning Functional Programming through Multimedia. Cambridge University Press. 2007 (8th printing).
6. Haskell tutorialss

For logic programming

1. W.F. Clocksin and C.S. Mellish: Programming in Prolog. Fifth edition. Springer. 2003.
2. M.A. Covington et al: Coding Guidelines for Prolog. Theory and Practice of Logic Programming. 12(6): 889-927 (2012) (Highly recommended).
3. P. Gloess. Constraint Logic Programming (PowerPoint format).