BSc Programs as data

News

14 February 2011: Der bliver reeksamen torsdag 10. marts 2011 kl 1430-1600 i lokale 4A30, som mundtlig eksamen. Eksaminanden trækker et tilfældigt af disse 11 spørgsmål og præsenterer så dette emne, uden yderligere forberedelse. Der vil blive stillet sidespørgsmål også i andre dele af pensum. Der er 30 minutter til hver eksaminand, inklusive votering.
28 January 2011: Der er givet karakterer: 3x00 + 1x01 + 3x4 + 6x7 + 9x10 + 5x12 = 7,6 i gennemsnit. Meget pænt!
5 January 2011: Exam questions with possible solutions
16 December 2010: The "spørgetime" (Q&A session) on Monday 3 January 2011 will be held in the Scrollbar at 1000-1200.
16 November 2010: We (that is, you) will use Monday 29 November morning on trying to do one of the old exams.
16 November 2010: There will be a "spørgetime" (Q&A session) on Monday 3 January 2011.
15 November 2010: There's now a pensumliste.
14 September 2010: The course newsgroup will be it-c.courses.SASP on the news.itu.dk news server. (The newsgroup actually belongs to a different course, but it runs in spring only). The news.itu.dk server requires SSL/TLS authentication. To set it up in Thunderbird, choose Tools > Account Settings > Account Actions > Add Other Account > Newsgroup account > ... > Newsgroup server: news.itu.dk; and then Server Settings > Connection security: SSL/TLS and check the box "Always require authentication...".
30 August 2010: Remember that exercise solutions must be submitted via email to sestoft@itu.dk as a zip-file named like BPRD-01-Ole-Madsen.zip where 01 is the course week number and Ole-Madsen should be replaced with your name.
29 August 2010: Here are the PLCSD lecture notes and most exercises for this course: Programming Language Concepts for Software Developers, version 0.50 (354 pages). Also in a paper-saving format (2-up) (179 pages).
27 August 2010: Lectures and exercises take place in room 2A14.

Lecture plan, preliminary

Course week ISO week Date Subject Materials Exercises After this week Your feedback
1 35 Mon 30 Aug F# as a meta language, abstract syntax, a simple expression language, direct interpretation of expressions in F# and C#, environments. PLCSD chapters 1 and 2 and Appendix A
and lecture01.pdf
and intro.zip 1.1, 1.2, 1.3, 1.5 (implement toString instead of eval) You have installed VS2010. You can use F# Interactive to write small functions, represent abstract syntax using F# datatypes, write evaluators and simpliers for simple expressions. Your feedback
2 36 Mon 6 Sep Interpreters and compilers, static checking of programs, postfix (reverse Polish) notation, a simple abstract machine with stack, Postscript. Concrete syntax, overview of lexing and parsing: from linear text to abstract syntax tree.
PLCSD chapter 2
and lecture02.pdf
and intcomp.zip 2.2, 2.3, 2.4, 2.8 no later than Tue 14 Sep You can write polymorphic functions and datatypes in F#. You can write and evaluate expressions in postfix notation, can distinguish an interpreter from a compiler, understand how to use a stack to store variables as well as intermediate results in very simple stack machine. Your feedback
3 37 Mon 13 Sep Lexing (scanning) and parsing using fslex and fsyacc. Scanner and parser specifications for the expression language and for micro-SQL. Lexer implementation: from regular expression to nondeterministic and deterministic finite automata. Parser implementation: From grammars to parsers; LR and LL grammars; bottom-up and top-down (recursive descent) parsers. PLCSD chapter 3
and Mogensen 2010 sections 2.1-2.7 except 2.6.1, 2.9
and Mogensen 2010 sections 3.1-3.6
and lecture03.pdf
and expr.zip
and usql.zip 3.2, 3.3, 3.4, 3.5, 3.6, 3.7 no later than Tue 21 Sep You can explain the concepts lexer, lexer generator, regular expression, nondeterministic and deterministic finite automata (NFA and DFA); can construct an NFA from a regular expression and construct a corresponding DFA; can modify a lexer specification and a parser specification to recognize new source syntax, and can use fslex and fsyacc to construct and use the corresponding lexers and parsers. Your feedback
4 38 Mon 20 Sep Interpretation of a first-order functional language: arithmetic and logical expressions, non-assignable variables, if-then-else expressions, function calls (without explicit evaluation stack), and recursive closures. Explicit monomorphic types; type rules; monomorphic type checking. Mogensen 2010 sections 3.12, 3.17
and PLCSD chapter 4
and lecture04.pdf
and fun1.zip
and typedfun.zip 4.1, 4.2, 4.3, 4.4, 4.5 no later than Tue 28 Sep You understand how an LR parser automaton works in collaboration with the parser stack; you can hand-write a simple LL (recursive descent) parser; you can explain the effect of static scope and dynamic scope of variables; you can explain why closures are needed for static scope; you can extend a simple type checker for an explicitly typed functional language. Your feedback
5 39 Mon 27 Sep Higher-order functions in F# and C# and Java. Google MapReduce. PLCSD sections 5.1-5.5 and A.11
and Google MapReduce paper
and lecture05.pdf 5.1, 5.3, 5.4, 5.5 no later than Tue 5 Oct You can read type rules for an explicitly typed language and relate them to a type checker in F#; you can modify an interpreter for a simple higher-order functional language; you can define higher-order functions in F# and Java; you can explain how higher-order functions may be used to describe MapReduce and parallel-for operations. Your feedback
6 40 Mon 4 Oct Hannes: A higher-order functional language. Parametric polymorphic types. Polymorphic type inference. Parametric polymorphism (generics) in Java and C#. PLCSD chapter 6
and lecture06.pdf
and fun2.zip 6.1, 6.2, 6.3, 6.4 and 6.5 no later than Tue 12 Oct Your feedback
7 41 Mon 11 Oct Modelling an imperative language: assignable variables, arithmetic and logical expressions, variable declarations, assignment, loops, output; expressions and statements; lvalues and rvalues; environment and store; parameter passing mechanisms; modelling pointers, pointer arithmetics and arrays. PLCSD chapter 7
and Fundamental Concepts (PDF)
and lecture07.pdf
and imp.zip
and microc.zip 7.1, 7.2, 7.3, 7.4 and 7.5 no later than Tue 26 Oct Your feedback
42 Fall break
8 43 Mon 25 Oct An abstract machine with program counter, explicit evaluation stack, and instructions for arithmetics, jumps, conditional jumps, function call, return etc. Compilation of the imperative language micro-C to a sequence of abstract machine instructions, whose store is a collection of numbered storage cells. PLCSD chapter 8
and lecture08.pdf 8.1, 8.3, 8.4, 8.5 and 8.6 no later than Tue 2 Nov Your feedback
9 44 Mon 1 Nov Real-world abstract machines such as the Java Virtual Machine (JVM) and the Common Language Infrastructure (CLI, .NET); a comparison of JVM and CLI. A comparison of JVM implementations. Just-in-time compilation. Garbage collection techniques (reference counting, mark-sweep, stop-and-copy, generational), stack, and heap. List-C, a version of Micro-C with cons cells. PLCSD chapters 9 and 10
and Memory Management in HotSpot
and Realtime Garbage Collection
and lecture09.pdf
and virtual.zip
and listc.zip 9.1 and 9.2 no later than Tue 9 Nov Your feedback
10 45 Mon 8 Nov Hannes: Continuations; a continuation-based interpreter for a functional language; exception-free modelling of exceptions; continuation-based interpreter for micro-Icon, a language with backtracking. PLCSD chapter 11
and lecture10.pdf
and cont.zip 11.1, 11.2, 11.3, 11.4, 11.8 no later than Tue 16 Nov Your feedback
11 46 Mon 15 Nov Backwards (continuation-based) code generation for micro-C, one-pass compilation of boolean expressions into control flow code, avoid jumps to jumps, compile tail calls to execute in constant space. PLCSD chapter 12
and lecture11.pdf
and ex13-code.txt 12.1, 12.2, 12.3, 12.4 no later than Tue 23 Nov Your feedback
12 47 Mon 22 Nov Scala, a function/object-oriented language on the Java Virtual Machine platform. A Scala tutorial for Java programmers (2010) and An overview of the Scala programming language (2006)
and lecture12.pdf Your feedback
13 48 Mon 29 Nov Trial written exam (condensed to three hours).

Course week	ISO week	Date	Subject	Materials	Exercises	After this week	Your feedback
1	35	Mon 30 Aug	F# as a meta language, abstract syntax, a simple expression language, direct interpretation of expressions in F# and C#, environments.	PLCSD chapters 1 and 2 and Appendix A and lecture01.pdf and intro.zip	1.1, 1.2, 1.3, 1.5 (implement toString instead of eval)	You have installed VS2010. You can use F# Interactive to write small functions, represent abstract syntax using F# datatypes, write evaluators and simpliers for simple expressions.	Your feedback
2	36	Mon 6 Sep	Interpreters and compilers, static checking of programs, postfix (reverse Polish) notation, a simple abstract machine with stack, Postscript. Concrete syntax, overview of lexing and parsing: from linear text to abstract syntax tree.	PLCSD chapter 2 and lecture02.pdf and intcomp.zip	2.2, 2.3, 2.4, 2.8 no later than Tue 14 Sep	You can write polymorphic functions and datatypes in F#. You can write and evaluate expressions in postfix notation, can distinguish an interpreter from a compiler, understand how to use a stack to store variables as well as intermediate results in very simple stack machine.	Your feedback
3	37	Mon 13 Sep	Lexing (scanning) and parsing using fslex and fsyacc. Scanner and parser specifications for the expression language and for micro-SQL. Lexer implementation: from regular expression to nondeterministic and deterministic finite automata. Parser implementation: From grammars to parsers; LR and LL grammars; bottom-up and top-down (recursive descent) parsers.	PLCSD chapter 3 and Mogensen 2010 sections 2.1-2.7 except 2.6.1, 2.9 and Mogensen 2010 sections 3.1-3.6 and lecture03.pdf and expr.zip and usql.zip	3.2, 3.3, 3.4, 3.5, 3.6, 3.7 no later than Tue 21 Sep	You can explain the concepts lexer, lexer generator, regular expression, nondeterministic and deterministic finite automata (NFA and DFA); can construct an NFA from a regular expression and construct a corresponding DFA; can modify a lexer specification and a parser specification to recognize new source syntax, and can use fslex and fsyacc to construct and use the corresponding lexers and parsers.	Your feedback
4	38	Mon 20 Sep	Interpretation of a first-order functional language: arithmetic and logical expressions, non-assignable variables, if-then-else expressions, function calls (without explicit evaluation stack), and recursive closures. Explicit monomorphic types; type rules; monomorphic type checking.	Mogensen 2010 sections 3.12, 3.17 and PLCSD chapter 4 and lecture04.pdf and fun1.zip and typedfun.zip	4.1, 4.2, 4.3, 4.4, 4.5 no later than Tue 28 Sep	You understand how an LR parser automaton works in collaboration with the parser stack; you can hand-write a simple LL (recursive descent) parser; you can explain the effect of static scope and dynamic scope of variables; you can explain why closures are needed for static scope; you can extend a simple type checker for an explicitly typed functional language.	Your feedback
5	39	Mon 27 Sep	Higher-order functions in F# and C# and Java. Google MapReduce.	PLCSD sections 5.1-5.5 and A.11 and Google MapReduce paper and lecture05.pdf	5.1, 5.3, 5.4, 5.5 no later than Tue 5 Oct	You can read type rules for an explicitly typed language and relate them to a type checker in F#; you can modify an interpreter for a simple higher-order functional language; you can define higher-order functions in F# and Java; you can explain how higher-order functions may be used to describe MapReduce and parallel-for operations.	Your feedback
6	40	Mon 4 Oct	Hannes: A higher-order functional language. Parametric polymorphic types. Polymorphic type inference. Parametric polymorphism (generics) in Java and C#.	PLCSD chapter 6 and lecture06.pdf and fun2.zip	6.1, 6.2, 6.3, 6.4 and 6.5 no later than Tue 12 Oct		Your feedback
7	41	Mon 11 Oct	Modelling an imperative language: assignable variables, arithmetic and logical expressions, variable declarations, assignment, loops, output; expressions and statements; lvalues and rvalues; environment and store; parameter passing mechanisms; modelling pointers, pointer arithmetics and arrays.	PLCSD chapter 7 and Fundamental Concepts (PDF) and lecture07.pdf and imp.zip and microc.zip	7.1, 7.2, 7.3, 7.4 and 7.5 no later than Tue 26 Oct		Your feedback
	42		Fall break
8	43	Mon 25 Oct	An abstract machine with program counter, explicit evaluation stack, and instructions for arithmetics, jumps, conditional jumps, function call, return etc. Compilation of the imperative language micro-C to a sequence of abstract machine instructions, whose store is a collection of numbered storage cells.	PLCSD chapter 8 and lecture08.pdf	8.1, 8.3, 8.4, 8.5 and 8.6 no later than Tue 2 Nov		Your feedback
9	44	Mon 1 Nov	Real-world abstract machines such as the Java Virtual Machine (JVM) and the Common Language Infrastructure (CLI, .NET); a comparison of JVM and CLI. A comparison of JVM implementations. Just-in-time compilation. Garbage collection techniques (reference counting, mark-sweep, stop-and-copy, generational), stack, and heap. List-C, a version of Micro-C with cons cells.	PLCSD chapters 9 and 10 and Memory Management in HotSpot and Realtime Garbage Collection and lecture09.pdf and virtual.zip and listc.zip	9.1 and 9.2 no later than Tue 9 Nov		Your feedback
10	45	Mon 8 Nov	Hannes: Continuations; a continuation-based interpreter for a functional language; exception-free modelling of exceptions; continuation-based interpreter for micro-Icon, a language with backtracking.	PLCSD chapter 11 and lecture10.pdf and cont.zip	11.1, 11.2, 11.3, 11.4, 11.8 no later than Tue 16 Nov		Your feedback
11	46	Mon 15 Nov	Backwards (continuation-based) code generation for micro-C, one-pass compilation of boolean expressions into control flow code, avoid jumps to jumps, compile tail calls to execute in constant space.	PLCSD chapter 12 and lecture11.pdf and ex13-code.txt	12.1, 12.2, 12.3, 12.4 no later than Tue 23 Nov		Your feedback
12	47	Mon 22 Nov	Scala, a function/object-oriented language on the Java Virtual Machine platform.	A Scala tutorial for Java programmers (2010) and An overview of the Scala programming language (2006) and lecture12.pdf			Your feedback
13	48	Mon 29 Nov	Trial written exam (condensed to three hours).

General information

Lectures 0900-1200 and exercises 1300-1600 take place Mondays in room 2A14 at the IT University, starting Monday 30 August 2010 at 0900.
The teacher is Peter Sestoft, sestoft@itu.dk. Teaching assistants are Hannes Mehnert (hame@itu.dk) and Kasper Videbæk (kaspervidebaek@itu.dk).
Official course description.
There is a written (four hours, with books) exam, held on Wednesday 5 January 2011.
Teaching materials:
- Torben Mogensen: Basics of Compiler Design, DIKU 2010.
- Peter Sestoft: Programming Language Concepts for Software Developers, version 0.50, IT University 2010.
- Materials on F#, such as Smith: Programming F# (O'Reilly 2009), or Pickering: Beginning F# (Apress 2009).
- Additional papers and documents will be listed above under the individual lectures.
Some resources on the history of C:
- Dennis Ritchie's homepage has a lot of materials on early C and C's predecessors B and BCPL.
Materials on virtual machines:
- Java Virtual Machine (JVM) specification (second edition, HTML)
- The JVM instruction set is described in the body of chapter 6 of that document.
- .NET Common Language Infrastructure (CLI) abstract machine specification (in PDF). The CLI instruction set is described in Partition III, that is pages 319-462.
Some F# resources:
- http://fsharp.net/ alias http://msdn.microsoft.com/fsharp/: Download F#, documentation, news, ...
- F# Powerpack site. Choose Download, accept the licenses, and say yes to running the installer. It installs by default in C:\Program Files\FSharpPowerPack-2.0.0.0\
- To run fslex and fsyacc from the (Visual Studio) Command Prompt you must add the F# PowerPack bin directory to the Windows PATH environment variable. Use this sequence of incantations, and then open a new Command Prompt:
```
  Start > Control Panel > System > Advanced > Environment Variables
  > User variables > PATH > Edit 
  ...;C:\Program Files\FSharpPowerPack-2.0.0.0\bin 
  > OK > OK > OK
```
- F# library documentation online
- http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/: Research-oriented F# news at Microsoft Research
- http://www.ffconsultancy.com/products/fsharp_journal/
- http://cs.hubfs.net/
Lambda calculus reduction tool
The old 2009 course homepage.
Old exam questions (in Danish):
- januar 2011 with possible solutions
- januar 2010 with possible solutions
- Trial exam questions fall 2009 with possible solutions.
Some old exam questions from a similar course. That course used Standard ML instead of F#, so the examples look a little different, but all the problems can be solved with F# as well:
- June 2005 with solutions
- June 2004 with solutions
- June 2003 with solutions
- June 2002 with solutions
- Old trial exam questions
The system for continuous evaluation (Your feedback) was suggested and made by Kasper Videbæk and David Christiansen.
Humor, sort of: If programming languages were religions (aren't they?)

Peter Sestoft, Last update 2011-02-21