Programming Languages and Environments
Objectives
To Know
1. The origins and structure of programming languages (Lambda Calculus, paradigms, interpreters, and compilers).
2. Key concepts in functional programming, including expression-based languages and polymorphic types.
3. Recursive algorithms, inductive reasoning, and their correctness.
4. The role of higher-order functions and their significance in functional programming.
5. The principles of modularity, concurrency, and state management
6. Understand the potential of programming without side effects, referential transparency, and functional data structures
To Do
7. Implement functional programs using OCaml, applying effect-free techniques and polymorphic types.
8. Write recursive algorithms and prove their correctness using inductive reasoning.
9. Use higher-order functions, such as function composition and partial evaluation, in practical programming.
10. Work with structured data (tuples, lists, algebraic data types) and iterate over data structures using Map and Fold.
11. Decompose, Design and implement modular and concurrent programs, handling state, memoization, and asynchronous operations.
General characterization
Code
8147
Credits
6.0
Responsible teacher
João Ricardo Viegas da Costa Seco
Hours
Weekly - 5
Total - 73
Teaching language
Português
Prerequisites
Available soon
Bibliography
- "OCaml programming: Correct + Efficient + Beautiful" de Michael R. Clarkson et al.
Teaching method
In the lectures, the concepts are presented, discussed and exemplified. Many of the concepts that appear in the syllabus are conveniently presented and discussed at the time of the study of specific languages (e.g. type inference in OCaml, prototype based programming). Other concepts are better discussed in an independent manner, making use of the previously studied languages for illustrative purposes (e.g. bindings, type systems, the polymorphism nomenclature of Cardelli).
In the lab classes, the students solve small problems, applying the concepts and techniques learned. Some of these problems are theoretical, but most are programming problems.
The projects are mainly developed outside the classes.
Evaluation method
Assessment Components
The assessment consists of two components: the laboratory component and the theoretical-practical component.
Laboratory Component and "Frequência"
The laboratory component is composed of three assignments. Each assignment involves designing, implementing, and validating functional programs to solve a given set of problems. It also includes the preparation of a report and an oral discussion. Even if the first two parts of the assignment (programs and reports) are carried out in groups of two students; the discussion is individual. The submission and acceptance method is described in the project assignment.
The discussions (to assess the student’s understanding of the work they submitted) are mandatory, in-person, and individual. The discussion of an assignment consists of making changes to the submitted code so that the new program solves a variation of the original problem, as defined in the discussion instructions, which differs slightly from the problem solved in the assignment. The grades for discussions and their criteria are as follows:
20: the change is globally correct;
16: the change is confusing or very incomplete, but the approach could be correct;
12: the change is incorrect, with "some things right and others very wrong";
4: "no changes were made" or "the changes made are minimal" or "the changes made do not make sense."
Generally, a student''s grade for an assignment is the lower of the grade for the submitted work (done in a group) and their grade in the discussion of that work (which is zero if the student is absent). A student’s grade for an assignment may be lower than that determined by the previous rule if their group partner’s performance in the discussion of all assignments is very poor (graded with 4). Consequently, the grades of the two group members can differ (and range between 0 and the grade of the assignment).
The laboratory component grade (CompL) is the average of the student''s grades on the three assignments (P1, P2, and P3), with weights of 0.25, 0.25, and 0.5, respectively.
The formula is as follows:
CompL = 0.25 x P1 + 0.25 x P2 + 0.5 x P3.
To qualify for "Frequência", CompL must be >= 9.5.
The discussion of the first assignment is held on the day of the first test, and the discussions for the second and third assignments are conducted on the day of the second test.
Theoretical-Practical Component
The theoretical-practical component consists of two tests (during the semester) or an indivisible exam (during the resit period). All three tests are individual, face-to-face, written, and without consultation. No electronic devices (e.g., calculators, mobile phones, smartwatches, tablets, laptops) are allowed.
Pre-registration for the tests is required.
The grade for the theoretical-practical component (CompTP) is the weighted average of the test scores (T1 and T2) or the exam score (Ex):
CompTP = 0.4*T1 + 0.6*T2 or CompTP = Ex.
To pass, CompTP must be >= 9.5.
Final Grade
The final grade (F) for students with "Frequência" is:
F = CompTP, if CompTP < 9.5;
F = 0.3 * CompL + 0.7 * CompTP, if CompTP >= 9.5.
All grades (P1, P2, P3, T1, T2, Ex, CompL, and CompTP) are rounded to one decimal place, except the final grade (F), which is rounded to the nearest whole number.
"Frequência" and Grades from Previous Years
In accordance with the current assessment regulations, "Frequência" from 2 previous years remains valid, as do their grades. Older results are not kept and used.
Open Book and AI Tools
The use of online resources and AI tools (such as ChatGPT or Copilot) is allowed for projects and class exercises but is prohibited during written tests and discussions. The use of AI tools must be explicitly mentioned in the code and report submitted. A student who uses these tools during an evaluation or project and fails to mention their use is considered to have committed plagiarism.
Fraud and Plagiarism
Issues of fraud and plagiarism will be dealt with according to NOVA FCT''s Evaluation Regulations.
Students may discuss assignments with colleagues and exchange ideas, but they may not share code (even "a few lines") under any circumstances, either orally or in writing. Writing code must be an individual task or internal to each group, depending on the evaluation element. For example, it is not permitted to show code on a screen, dictate code, send files with code, or post them in places accessible to third parties.
It is assumed that all parties involved act with common sense and that everyone is reasonable. It is expected that when students work in groups, they do so fairly and equitably, work by work. The contribution of each group member is the group''s collective responsibility. The various assignments throughout the semester do not have to be completed by the same groups of students.
In summary, the following are considered fraudulent:
a group that gives or receives code commits fraud;
a group in which only one member does the work commits fraud;
students who work in larger groups, sharing code, commit fraud.
The use of AI tools (such as ChatGPT or Copilot) must be explicitly mentioned in the code. A group that uses these tools during an assignment and fails to mention their use is considered to have committed plagiarism.
Ban on the Use of Electronic Devices During Assessments
During an assessment, a student may not have any electronic devices capable of accessing the internet or with Bluetooth connectivity (e.g., smartphones, smartwatches, smartglasses, tablets, laptops) with them, even if they are turned off.
Violation of this rule results in immediate failure of the curricular unit by exclusion and will be reported to the Scientific Committee of the respective program.
Subject matter
1. The history and structure of programming languages
1.1 The origins of programming languages: The Lambda Calculus
1.2 The main concepts of programming languages
1.3 Programming paradigms
1.4 Interpreters and Compilers (introduction)
2. Expressions, Values, Functions and types
2.1 The OCaml programming language
2.2 Expression and Statement based programming languages
2.3 Values and Types
2.3 Name binders: (Mathematical) variables (let) and functions (fun)
2.4 Polymorphic types and type inference
2.5 Library Functions
2.6 Input/Output
3. Recursion and Induction
3.1 Recursive algorithms on natural numbers
3.2 Inductive reasoning
3.3 Correctness of inductive reasoning
3.4 Tail recursion
3.5 Comparison with imperative algorithms
4. Higher-Order functions Composition,
4.1 Functions as values
4.2 Partial evaluation
4.3 Function composition
5. Structured Data
5.1 Tuples and Lists
5.2 Algaebric Data Types
5.2 Inductive types and algorithms
5.3 Using Map and Fold to iterate data structures
6. Modules, Interfaces and Functors
6.1 OCaml Module System
6.2 Modularity mechanisms in other programming languages
7. State, Asynchrony and Concurrency
7.1 The use of state in functional programming
7.2 Memoization
7.3 Asynchronous computation and I/O (Promises)
7.4 Concurrent programming in OCaml
8. Machines, Interpreters and Compilers
8.1 Stack-based and Register based machines
8.2 The structure of programming languages
8.3 Compositionality of semantic constructs
8.4 Interpreting and compiling functions