Implementation of Programming Languages

Code:

CC4023

Acronym:

CC4023

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2019/2020 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~ricroc/aulas/1920/il
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	12	Study plan since 2014/2015	1	-	6	42	162
MI:ERS	0	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

Suitable for English-speaking students

Objectives

Introduction to the design principles and implementation techniques of declarative programming languages.

Learning outcomes and competences

The students should acquire the following competences: understand the principles used to implement functional languages (such as ML or Haskell) and logic languages (such as Prolog) on standard computer architectures, the technological problems associated with their design and the existing solutions.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Prerequisites: basic programming knowlege in one functional and logic language (e.g. Haskell and Prolog); programming knowlege in a low-level system language (e.g. C).

Program

Implementation of Functional languages:
Definition of a toy functional language by extension of the lambda-calculus. Strict vs non-strict semantics. Call-by-value and call-by-name reduction strategies. Implementation of higher-order functions using closures. The SECD abstract machine.
Call-by-need evaluation and graph reduction. The STG abstract machine. Using Haskell as a meta-language for specifying interpreters and compilers for a minimal functional language.

Implementation of Logic Languages:
SLD resolution and Prolog. The Warren's Abstract Machine (WAM): compilation, unification, execution stacks, environments, choice-points, backtracking and indexing. Tabling: basic execution model, table space, suspending/resuming the computation, compiling tabled predicates.

Mandatory literature

Ait-Kaci Hassan; Warren.s abstract machine. ISBN: 0-262-01123-9
S.L. Peyton Jones; The implementation of functional programming languages. ISBN: 0-13-453325-9
S.L. Peyton Jones; Implementing functional languages. ISBN: 0-13-721952-0

Teaching methods and learning activities

Lectures presenting concepts aided with illustrative examples of principles of language design and implementation.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	60,00
Trabalho laboratorial	40,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	84,00
Frequência das aulas	42,00
Trabalho laboratorial	36,00
Total:	162,00

Eligibility for exams

N/A

Calculation formula of final grade

Students are assessed by two practical assignments (graded for 4 points each out of 20) and a written examination in the end of the semester (graded for 12 points out of 20). The minimal grade on exam for aproval is 40%.

The rules above apply equally for classification improvment and special assessments.

Special assessment (TE, DA, ...)

The same rules for calculating the final grade apply.

Classification improvement

The same rules for calculating the final grade apply.