49778 - Computational Models and Languages LM

Learning outcomes

By the end of the course, the student will learn the basic knowledge concerning analysis and design of programming languages, specification of computational systems, and for understanding how to use computational models prevalently used in software engineering. In particular, the student will be able to: - design software based on the logic paradigm and Prolog; - design a simple programming language and develop an interpreter or translator; - specify syntactic and semantic aspects of a computational system; - understand the basic computational models proposed in scientific literature, and use them to analyse complex computational systems.

Course contents

• Main aspects of the theory of computation. Computation and interaction. Automata and expressiveness: the Turing machine. Goedel incompleteness. Algorithms. Abstract Data Types. Using MAUDE language to specify abstract data types and algorithms.
• The Prolog Language. Relational interpretationof Prolog, syntax, SLD tree, cut operator, programming examples, procedural interpretation. Metaprogramming and metainterpretation. The tuProlog technology: Java-Prolog integration.
• Logics. Propositional logics. First order logic. The logic interpretation of Prolog. Elements of other logics.
• Syntax, Grammars and Parsers. Formal grammars. Deriving a sentence. Chomsky classification. BNF and Extended BNF Grammars. Ambiguity. Translating Grammars. Regular Expressions. Finite state parsers. Imperative and logic parsers. Generating sentences. Parsers for type 2 Grammars. LL Grammars. Exercise in Java and Prolog. The JavaCC tool. Exercises on defining new languages.
• Operational semantics of languages. Simple examples. Formalisms. Petri Nets. using MAUDE for operational semantics and model-checking
  
• Advanced Models. Process algebras, Stochastic systems (SPIM , PRISM). A survey on existing models and tools proposed in literature.
  

Readings/Bibliography

Slides projected during lectures
Bibliografic references provided throughout 

Teaching methods

Lessons in classroom

Exercises in lab

Assessment methods

Written exam with exercises

Practice exam, either:

• discussing a project
• discussion with the teacher
  

Teaching tools

Slides projected during the lessons

Software:

• JDK 5.0 (or higher versions)
• tuProlog (http://tuprolog.sourceforge.net/)
• MAUDE (http://maude.cs.uiuc.edu/)
• SPIM (http://research.microsoft.com/en-us/projects/spim/)
• PRISM (http://www.prismmodelchecker.org/)
  

Links to further information

http://apice.unibo.it/xwiki/bin/view/MirkoViroli/Courses

Office hours

See the website of Mirko Viroli

See the website of Stefano Benedettini