Home

Back

Fall 2009 - Specialization Course for Tommaso Pimpo

Teacher: Andrea Valente (aaue.dk/~av)

Schedule: decided with Tommaso.

Course plan:

Lecture nr: Topic: Literature: Comments:

1 Syntax
Introduction to the course. Sets, Strings and Languages. Deterministic Finite Automata. Chapter 0 and Chapter 1.1 [TC] and JFlap. Notes(PDF) Remember to get a copy of the booklet with selected material from:
Introduction to the theory of computation, by M. Sipser
The booklet will be referred to as [TC]

Syntax
Nondeterministic Automata. Relationships with DFA. Chapter 1.2 [TC], Notes(PDF)

Syntax
Regular expressions and finite automata. Chapter 1.3 [TC] Notes(PDF)

2 Syntax
Non-regular languages. Chapter 1.4 [TC] Notes(PDF)

Syntax
Context-free languages and grammars. Chapter 2.1 [TC] Notes(PDF)

Syntax
Pushdown automata. Relationships with context-free grammars. Chapter 2.2 [TC] Notes(PDF)

3 Syntax
Non-CF languages. What else is there? Chapter 2.3 [TC] and whatElse
parsing, interpreter pattern slides and code

XTRA
Write an OO intepreter in minutes!
A general technique (with a working example) of how to build an interpreter for an imperative programming language, starting with its grammar and its semantics. While interpreter

4 Semantics
Introduction to the formal semantics of programming languages. slides8 and Chapter 1 [SA], example of semantics functions in javascript. Get a copy of the online book:
Hanne Riis Nielson, Flemming Nielson - Semantics with Applications: A Formal Introduction. (PDF)
This book will be referred to as [SA]

Semantics
Natural and structural operational semantics for the language While.
Abstract machine for While. slides9 and Chapter 2.1,2.2,2.3 [SA] Alternative discussion: Matthew Hennessy
Structural Operational Semantics is The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics (PS)

Semantics
Relationships between natural and structural operational semantics for While.
Interpreters: their construction. Meta-circulat intepreters (here) slides10

5 Semantics
Operational semantics for extensions of While. Chapter 2.4 [SA]

Semantics
Natural semantics for blocks and procedures (While). blocks_procedures and Chapter 2.5 [SA]

Semantics
Axiomatic semantics. Partial correctness of programs. Loop invariants. axiomatic semantics and Chapter 6,6.1,6.2,6.3 [SA]

Semantics Denotational semantics, fixed-point theory (short intro). Chapter 4.1 [SA] and this handout (from here)

6 CCS and Pi-calculus CCS, PI-Calculus . Introduction to the PI-Calculus.
. The polyadic PI-Calculus
. Labelled transition systems, CCS, and the MobilityWorkbench
. Implementing the pi-calculus Uniprocessor Abstract Machine
. FAQ on pi-calculus
. PiLib- A Hosted Language for Pi-Calculus Style Concurrency

7 Multi-core programming . Big Fast Crowds on PS3
. Agent Based GPU, a Real-time 3D Simulation and Interactive Visualisation Framework for Massive Agent Based Modelling on the GPU

Department for Software, Electronics og Mediatechnology - Aalborg University Esbjerg - Niels Bohrs Vej 8 - 6700 Esbjerg - Denmark
Phone: +45 7912 7666 - Fax: +45 7912 7710

Lecture nr:	Topic:	Literature:	Comments:
1	Syntax Introduction to the course. Sets, Strings and Languages. Deterministic Finite Automata.	Chapter 0 and Chapter 1.1 [TC] and JFlap. Notes(PDF)	Remember to get a copy of the booklet with selected material from: Introduction to the theory of computation, by M. Sipser The booklet will be referred to as [TC]
	Syntax Nondeterministic Automata. Relationships with DFA.	Chapter 1.2 [TC], Notes(PDF)
	Syntax Regular expressions and finite automata.	Chapter 1.3 [TC] Notes(PDF)
2	Syntax Non-regular languages.	Chapter 1.4 [TC] Notes(PDF)
	Syntax Context-free languages and grammars.	Chapter 2.1 [TC] Notes(PDF)
	Syntax Pushdown automata. Relationships with context-free grammars.	Chapter 2.2 [TC] Notes(PDF)
3	Syntax Non-CF languages. What else is there?	Chapter 2.3 [TC] and whatElse parsing, interpreter pattern slides and code
3	XTRA Write an OO intepreter in minutes! A general technique (with a working example) of how to build an interpreter for an imperative programming language, starting with its grammar and its semantics.	While interpreter
4	Semantics Introduction to the formal semantics of programming languages.	slides8 and Chapter 1 [SA], example of semantics functions in javascript.	Get a copy of the online book: Hanne Riis Nielson, Flemming Nielson - Semantics with Applications: A Formal Introduction. (PDF) This book will be referred to as [SA]
	Semantics Natural and structural operational semantics for the language While. Abstract machine for While.	slides9 and Chapter 2.1,2.2,2.3 [SA]	Alternative discussion: Matthew Hennessy Structural Operational Semantics is The Semantics of Programming Languages: An Elementary Introduction Using Structural Operational Semantics (PS)
	Semantics Relationships between natural and structural operational semantics for While. Interpreters: their construction. Meta-circulat intepreters (here)	slides10
5	Semantics Operational semantics for extensions of While.	Chapter 2.4 [SA]
	Semantics Natural semantics for blocks and procedures (While).	blocks_procedures and Chapter 2.5 [SA]
	Semantics Axiomatic semantics. Partial correctness of programs. Loop invariants.	axiomatic semantics and Chapter 6,6.1,6.2,6.3 [SA]
	Semantics Denotational semantics, fixed-point theory (short intro).	Chapter 4.1 [SA] and this handout (from here)
6	CCS and Pi-calculus	CCS, PI-Calculus	. Introduction to the PI-Calculus. . The polyadic PI-Calculus . Labelled transition systems, CCS, and the MobilityWorkbench . Implementing the pi-calculus Uniprocessor Abstract Machine . FAQ on pi-calculus . PiLib- A Hosted Language for Pi-Calculus Style Concurrency
7	Multi-core programming		. Big Fast Crowds on PS3 . Agent Based GPU, a Real-time 3D Simulation and Interactive Visualisation Framework for Massive Agent Based Modelling on the GPU