TP #1 IFT-2035 1 Overview This lab aims to improve the understanding of functional programming by using a functional programming language (Haskell) and writing a part of an interpreter for a functional programming language (in this case a kind of Lisp). The steps of this work are the following: 1. Improve your knowledge of Haskell. 2. Read and understand this data. This will probably take a significant portion of the total time. 3. Read, find, and understand the important parts of the provided code. 4. Complete the provided code. 5. Write a report. It should describe your experience during the previous points: problems encountered, surprises, choices you had to make, options you consciously rejected, etc. The report should not exceed 5 pages. This work is to be done in groups of two. The report, in LATEX format only (compilable on ens.iro) and the code are to be submitted by electronic submission before the indicated date. No delay will be accepted. Clearly indicate your name at the beginning of each file. Those who want to do this work alone must first obtain permission, and the evaluation of their work will not take it into account. Groups of 3 or more are excluded. e ::= n |x | (Axe) | (e0 e1 ... en) | (ref! e) |(get ! e) | (set! e1 e2) |+| - | * |/ Signed Decimal Integer A variable A function with an argument A curried function call Construction of a ref-cell Find the value of the ref-cell e Change the value of the ref-cell e1 Predefined arithmetical operations |< | > | = | <= | >= Boolean operations on integers | (if e1 e2 e3) If e1 then e2 else e3 |(let x e1 e2) Simple local declaration | (letrec ((x1 e1) ... (xn en)) e) Recursive local declarations Fig 1. Slip syntax 2 Slip: A kind of Lisp In this project, you will work on the implementation of a functional language whose syntax is inspired by the Lisp language. The syntax of this language is described in Figure 1. It is important to note that, as always with Lisp-style syntax, parentheses are significant. The let form is used to give a name to a non-recursive local definition. The letrec form is a more complex variant that allows for multiple simultaneous local definitions, which can also be recursive, including mutually recursive, as in the Haskell let. 2.1 Dynamic semantics Slip, like Lisp, is a dynamically typed language, meaning that its variables can contain values of any type. There is therefore no static semantics (typing rules). The values manipulated at runtime by our language are integers, functions, booleans, and references that point to ref-cells, which are memory cells whose contents can be modified (the rest of the values manipulated by Slip are immutable). A ref-cell is constructed with ref!(), which takes the initial value of the cell as an argument, allocates the cell somewhere in memory, and returns a reference (its address). The current value of the cell can then be retrieved with get!() and the value changed with set!(). (λ p (set! p (+ 1 (get! p)))) is a function that increments a cell by adding 1. The fundamental evaluation rules are as follows: ((Axe) v) (let x v e) هارد e[v/x] e[v/x] (letrec ((1 v1)... (In Un)) e) W e[v1, Un/1,, In] (eg €1 en) (eo) for + ((eo €1)... en) Co Where the notation e[v/x] represents the expression e in an environment where the variable x takes the value v. The use of v in the rules above indicates that it is indeed a value rather than an expression that has not yet been evaluated. For example, the v in the first rule indicates that when calling a function, the argument must be evaluated before entering the body of the function, i.e. we use call by value. In addition to the two ẞ rules above, the different arithmetic primitives behave as expected: ~ mi — m2 - n1—N2 (+ n₁ n₂) (- n₁ n₂) ~ (* n1 n₂) ← n1 x n2 ... So it is a variant of the X-calculus, no big surprise. The scope is static and the order of evaluation is by value. However, the reduction rules below do not take into account the presence of impure operations ref !, get !, and set !, which require the use of more complex reductions where we consider not only the expression to be reduced but also the state of the memory (also sometimes called the heap). More specifically, the rules above have the form ee' but should actually be of the form (M; e)(M; e'). Thus, the impure rules can be defined as follows: (M; (ref! v)) > (M, e 7⇒ v; e) e is a new address ~> (M; (get! )) (M; v) M(e) = v (M; (set ! & v)) ~> (M' ; v) M' = M, e 7 → v Haskell code remains pure and will therefore follow these semantic rules in a fairly straightforward way: the eval function will receive an argument that represents this M which will be modified in a pure way. 3 Implementation The implementation of the language works in several phases: 1. A first phase of lexical and syntactic analysis transforms the source code into a representation described below, called Sexp in the code. This is not yet a complete abstract syntax tree (it actually resembles XML). 2. A second phase, called s21, completes the syntactic analysis and begins compilation, by transforming this tree into a true abstract syntax tree in the representation called Lexp in the code. In a sense, this phase already begins compilation since the Lexp language is not identical to our source language. 3. Finally, an eval function proceeds to the evaluation of the expression by interpretation. A portion of the implementation is already provided: the first phase as well as various pieces of the others. Your task will be to fill in the gaps. 3.1 Lexical and syntactic analysis: Sexp The lexical and syntactic analysis is already implemented for you. It is more permissive than necessary and accepts any expression of the following form: e ::= n | × | '(' {e} )' n is a signed decimal integer. It is represented in the Haskell tree by: Snum n. x is a symbol that can be composed of any number of alphanumeric and/or punctuation characters. For example, '+' is a symbol, '<=' is a symbol, 'voiture' is a symbol, and 'a+b' is also a symbol. In the Haskell tree, a symbol is represented by: Ssym x. '('{e}')' is a list of expressions. In the Haskell tree, lists of expressions are represented by simply linked lists consisting of pairs Scons left right and the end marker Snil. left is the first element of the list and right is the rest of the list. For example, the parser transforms the expression (+ 2 3) into the following Haskell tree: Snode (Ssym "+") [Snum 2, Snum 3] The lexical analyzer considers that a ';' character starts a comment, which ends at the end of the line. 3.2 The Lexp intermediate representation This intermediate representation is a kind of abstract syntax tree. In this representation, +, -, ... are simply predefined variables. 3.3 The execution environment The provided code also defines the initial execution environment, which contains the predefined functions of the language such as addition, subtraction, etc. It is defined as a table that associates to each predefined identifier the value (of type Value) associated. 3.4 Evaluation The evaluator uses the initial environment to reduce an expression (of type Lexp) to a value (of type Value). It also takes an argument that represents the memory state M and which is returned (possibly modified) with the value resulting from the evaluation of the expression.