Lehrstuhl Informatik II

Sprachen und Beschreibungsstrukturen

Sprachen und Beschreibungsstrukturen

## Programming Languages
## News- 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
## Dates:Lectures: Tutorial: Exam: Feb 17, 2011, Exam Inspection: March 14, 2011, room 02.07.014
## Assignment:- Implementing an Interpreter in Haskell: assign.pdf
- Program specification: Program.hs
- Interpreter: Interpreter.hs
- Some Test Cases: Test.hs
## 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:
## Captain's Log:- learning goals, factorial ad nauseam, declarative vs imperative,
- data constructors, type constructors, arity, (:), (,), types and kinds, DATA declaration, binding occurrences, list comprehensions, free variables, local and global scope, shadowing
- 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
- closures, type classes and paterns formalized, thunks, summary and outlook, mini-test 1, muddiest point
- 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
- simple expression language, inference rules, subsitution, type inference by constraint generation and subsequent solving; solving involves generalization which consists of unification and instance checking
- 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
- Lambda Calculus and Equational Reasoning
- 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;
- Prolog: overview; Prolog syntax: facts, rules, terms queries; Harry Potter puzzle
- Prolog: unification, resoltuion, different kinds of equality, backtracking, cuts for controlling backtracking
- Databases, term manipulations, self-modifying code, assert, retract, =.., Fibonacci, dynamic programming
- Constraint logic programming: lucky numbers, Sudoku; summary of the whole lecture
## Overview:This lecture is about different concepts found across
## Learning GoalsA link to John Reynold's paper on teaching programming and programming languages. ## Prolog resources:- Ivan Bratko, PROLOG: Prgogramming for Artificial Intelligence
- SWI Prolog Manual
## Haskell resources:- Real World Haskell book
- Haskell website
- Evolution of a Haskell programmer
- free online PL book
- Haskell gentle introduction
## Grading:Grades are determined based on your result in a - [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 You can get up to ## Contact:kreiker@in.tum.deflexeder@in.tum.de |