Linguaggi e Modelli Computazionali L-M 2011/2012

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.

• 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 interpretation of 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.

• Slides projected during lectures
• Bibliographic references provided throughout

• Lessons in classroom
• Exercises in lab

• Written exam with exercises
• Practice exam, either:
  • discussing a project
  • discussion with the teacher

• 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/)