Functional Programming

VU 2   SS 2007   LVA 703246

Course material

Slides and notes

These notes are sometimes rewritten and/or extended. Please check if you have the latest version.

• Week 1
• Week 2
• No slides were used in week 3.
• Week 4
• Week 5
• The picture about AVL tree restructuring in PDF
• On proving Equivalence
• Slides of 16.5.
• The UNIX shell script ocamltry.
• Some notes on combinatorics
• Slides of 23.5.
• OCaml code for LazyList module.
• Short note on lazy lists
• Type checking and type inference for an OCaml-like language: pdfwith one extra note.
• The interpreter: slides and code.

These slides are 1 per page, convenient for viewing on a screen. To print multiple pages per sheet, the print menu of acrobat reader offers a section Page Handling, where Page Scaling can be set to multiple pages per sheet.

Examples

• Solution for the n-queens problem

Homework (practice/no grading)

March 14

• Read chapters 1-5 of Jason Hickey's book.
• Try a few examples from those chapters using the interpreter.

March 21

• Read chapters 6-7 of Jason Hickey's book.
• Write the functions specified in this file. The answers are here

April 25

• A few exercises with substitutions: PDF

May 16

• The exercise from the notes on proving equivalence.

June 6

• Combinatorics
• Aux, Map(header), Map and Types

June 27

• Example of a final exam in PDF

Homework (graded)

Rules

• You need to hand in at least two exercises to pass.
• You can never receive more than 50 points total for the exercises.

Ordered Trees (17 points)

• As back ground material, chapter 9 from Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, second edition, is available for registered students on on e-campus.
• Code fragments for AVL trees and (2,4) trees
• The old version (here) is too difficult. A new version will appear. This new version will be about AVL trees only ((2,4) trees are too much work and Red-Black trees are not known.)

Type Inference (17 points)

• The files map.mli, map.ml, aux.ml, types.ml, expr.ml, inference.ml and meta.ml contains the start of an implementation of a type inference system.
• The task is to complete the implementation:
  • implement unification
  • implement fresh variable generator
  • add cases for constructors and pattern matching
  • add type checking for expressions
• The deadline for handing in your solution by email is 27.07.2007.

Combinator Parsers (17 points)

• The files aux.ml, parser.mli, parser.ml and parserExamples.ml contain an implementation of parser combinators and a few examples of how to use them.
• The task is to implement a parser for our small language (see types.ml, expr.ml). To do that it might be a good idea to implement auxiliary parser combinators, such as seq3, which perform the same task as seq except for three parsers instead of 2. This cleans up sequences of three a lot. For example:

  seq3 (fun _ x _ -> x) (atom'(') expr (atom')')
  

  is much easier to read than

  seq (fun _ x -> x) (atom'(') (seq (fun x _ -> x) expr (atom')'))
  

• The deadline for handing in your solution by email is 27.07.2007.

Sudoku (17 points)

• Write a Sudoku solver.
• A suggestion of how to do it is written in the notes on combinatorics and bits of code are given as nqueens.ml and sudoku.ml.
• The deadline for handing in your solution by email is 27.07.2007.

Other Projects

If you want to replace one (or more) of the tasks above by a project of your own invention then we can discuss how many points it is worth.

OCaml availability

OCaml is installed on the ZID linux systems. The status on ZID windows is unknown. For home linux systems check your distribution first: for example, OCaml is part of Fedora Core. If that doesn't work try downloading a pre-compiled version from the OCaml home page.

On line resources

• The OCaml reference manual can be found on the OCaml home page or as a local copy
• Jason Hickey, An Introduction to the Objective Caml Programming Language can be found on his publications page or as a local copy