Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Wintersemester10/11 Vorlesungen Programming Languages login

Programming Languages

Ort/Zeit:Thursdays 12.15-1.45pm in Lecture Hall 3
Beschreibung:    We are discussing various programming paradigms illustrated by a number of real programming languages such as e.g. Haskell, Prolog, and others.


  • Exam results updated
    • please check on campus.tum.de
    • grades published according to list below (where the passing threshold is 16 instead of 17)
    • inspection: March 14, 14-15pm, room 02.07.034
    • there will be no resit (Wiederholungsklausur)
    • statistics
      • average: 25, median: 26.75
      • preliminary grades (incl. bonus): 12x 1.0-1.3; 9x 1.7-2.3; 8x 2.7-3.3; 8x 3.7-4.0; 7 fails 
      • average preliminary grade: 2.6
  • Exam with sample solutions: exam_sol.pdf
  • the results of the mini tests and programming assignments were published via TumOnline
    • in the mini test there were 28 points available
    • between 14 and 20 points you were awarded 1 bonus point (incl. rounding)
    • at least 21 points were rewarded by 2 bonus points
    • in the programming assignment you could obtain at most 4 bonus points, 1 for each task (a)-(d)
    • complaints about the above results should be directed to Andrea or Joerg asap


Lectures: Thursdays 12:15pm-2pm in Lecture Hall 3 (FMI, Boltzmannstr. 3)

Tutorial: Thursdays 2pm-3.30pm in the IMETUM Lecture Hall (there is only one in that building)

Exam: Feb 17, 2011, PH1 (large lecture hall in physics building), 11:30-13:00

Exam Inspection: March 14, 2011, room 02.07.014



Type Inference Examples:

  • inference for expression let app = \f -> \x -> f x in let inc = \x -> x + 1 in app inc: here
  • inference for expression \x -> \y -> let z = (,) y in [z y] == x: here

  • Without further notice we assume standard type and instance environments
  • e.g.: (+) : forall a. Num a => a -> a -> a; ([]): forall a. a -> [a]; 1: forall a. Num a => a; (==): forall a. Eq a => a -> a -> Bool
  • e.g. instances: forall a. Eq a => Eq [a]; forall a,b. <Eq a, Eq b> => Eq (a,b)
  • read the inferences from bottom to top following the red squared numbers 1,2,3,..
  • to check (==) and (+) I used a slightly more general version of [C-App]
  • some steps are left out in unifications
  • type variables from contexts that do not occur in actual types are omitted in the first example
  • applications of rule [C-Var] are abbreviated

Slides and Exercises:

Date Topic Material Exercise
Oct 21 Introduction to Programming Languages and Haskell lecture1.ppsx, lecture1.pdf sheet1.pdf, e1.hs, fold.pdf
Oct 28 Data and type constructors, bindings and scope lecture2.pdf, Haskell code, worksheet, worksheet (solution) sheet2.pdf, e2.hs, ihp.hs
Nov 4 Patterns, type classes lecture3.pdf, ghci transcript, Haskell code sheet3.pdf, e3.hs, l3.pdf
Nov 11 Thunks, closures lecture4.pdf, mini test 1, cbn.hs, tree.hs sheet4.pdf, e4.hs, cbn.hs, call_by.pdf
Nov 18 Kinds, types, type inference lecture5.pdf, mini test 2 sheet5.pdf, liquid_types.pdf
Nov 25 Hindley-Milner type inference with type classes lecture6.pdf, handout.pdf, worksheet.pdf, worksheet_solutions.pdf sheet6.pdf, solutions 6
Dec 9 Continuations lecture7.pdf, regular expression matching Haskell program sheet7.pdf, type inference scans and photographs, solutions 7
Dec 16 Equational Reasoning lecture8.pdf, mss.hs, mini test 3, sol mini test 3  
Dec 23 Lambda Calculus   sheet8.pdf, sol8.pdf, sol8.hs
Jan 13 Side-Effects lecture10.pdf, interpreter.zip sheet9.pdf, io.hs, maybe.hs
Jan 20 Prolog Introduction lecture11.pdf, snape.hs, snape.pl,ex4.pdf,sol_ex4.pdf sheet10.pdf, l10.pl, monkey.pdf, monkey.pl
Jan 27 Unification, Backtracking, Cuts lecture12.pdf, observations.pl sheet11.pdf, l11.pl
Feb 3 Databases lecture13.pdf, Prolog code, mini test 5 (solution) sheet12.pdf, l12.pl
Feb 10 Constraint Programming Prolog code, Haskell code  


Captain's Log:

  1. learning goals, factorial ad nauseam, declarative vs imperative, 
  2. data constructors, type constructors, arity, (:), (,), types and kinds, DATA declaration, binding occurrences, list comprehensions, free variables, local and global scope, shadowing
  3. assignments vs bindings, patterns: wildcard, variable, as, lazy (irrefutable) patterns, constructor patterns, infinite lists (Fibonacci, ones, even/odd), intro to type classes, ad-hoc vs parametric polymorphism vs subtyping, superclasses, instances
  4. closures, type classes and paterns formalized, thunks, summary and outlook, mini-test 1, muddiest point
  5. rebuttal muddiest point, motivation for types, types and kinds formally defined, mini test 2, Who want's to be a millionaire-style intuitive introduction to type inference
  6. simple expression language, inference rules, subsitution, type inference by constraint generation and subsequent solving; solving involves generalization which consists of unification and instance checking
  7. Continuation passing style: continuations as a powerful mechanism to manipulate control-flow; example: stateful HTTP, Stackless Python, Perl Continuity; introdcutort CPS examples in Haskell, regular expression pattern matcher using continuations
  8. Lambda Calculus and Equational Reasoning
  9. Side-Effects: distinguishing between mathematical functions and procedures having side-effects; mechanism of monads: using an additiional level of indirection; example: IO; enriching an interpreter with exceptions and state;
  10. Prolog: overview; Prolog syntax: facts, rules, terms queries; Harry Potter puzzle
  11. Prolog: unification, resoltuion, different kinds of equality, backtracking, cuts for controlling backtracking
  12. Databases, term manipulations, self-modifying code, assert, retract, =.., Fibonacci, dynamic programming
  13. Constraint logic programming: lucky numbers, Sudoku; summary of the whole lecture


This lecture is about different concepts found across
all programming paradigms. Examples of such concepts
are types, values, control-flow, modularization,
concurrency, or data abstractions. We will focus on
the functional and logical paradigm.

We will see instances of the concepts in these
programming languages. We learn how to choose an
appropriate language for a given programming task and
how to evaluate the strengths and weaknesses of various
languages. Participants will be able to easily adapt
to new languages and they will know the basics of language design.

Lectures will be given in English.


Learning Goals

A link to John Reynold's paper on teaching programming and programming languages.

Prolog resources:

Haskell resources:


Grades are determined based on your result in a written exam. In the exam you can reach up to 40 points corresponding to the following grades.

  • [0,5) points: 5,0
  • [5,11) points: 4,7
  • [11,16) points: 4,3
  • [16,19] points: 4,0
  • (19,22] points: 3,7
  • (22,24] points: 3,3
  • (24,26] points: 3,0
  • (26,28] points: 2,7
  • (28,30] points: 2,3
  • (30,32] points: 2,0
  • (32,34] points: 1,7
  • (34,36] points: 1,3
  • (36,40] points: 1,0

You can get up to 4 bonus points for a programming project.

You can get up to 2 bonus points for successful participations in our mini tests (during lectures).



TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 16 ms