Interpreter for FLIZ
In this lab, you are going to build an interpreter for a simple functional programming language, which we call FLIZ. The interpreter is interactive and prompts the user to enter statements to be evaluated.
You are given source code for the implementation of FIZ, a similar language. The code includes comments in order to understand how to use Lex and Yacc to implement such a language interpreter. You can use any part of the source code in your implementation of FLIZ. While not recommended, you can also start from scratch, and make design decisions different from those made in the provided source code for FIZ. Four test files are provided. Your implementation should handle programs such as those in the test files. Binary code of a reference implementation is also provided.
The lab has been divided into several parts:
- Part 1: Programming in FIZ.
- Part 2: Support constant expressions.
- Part 3: Adding support for FLIZ’s built-in functions
- Part 4: Supporting user-defined functions, and programming in FLIZ.
The Skeleton
Login to data and type
cd
cd cs252
git clone /homes/cs252/sourcecontrol/work/$USER/lab2-src.git
cd lab2-src
Important: You have to be in data when you run the git clone command.
You will have to login to data or any of the lab machines to work on your lab. Also note that, When you create a new directory for fliz implementation you have to run “git add directoryname” before running make. And when you add a new Makefile for your fliz implementation do not forget to add the git-commit block by copying it from the Makefile in fiz directory.
Part 1: Programming with FIZ
In order to help you, we provided the implementation for a FIZ, a language similar to FLIZ. Under the ./fiz directory, you can find Makefile, fliz.l, fliz.y, and two test files: test1.f and test2.f.
You are asked to write some programs with FIZ, both to help with understanding of recursive programming in FIZ and FLIZ, and to help you understand the provided FIZ implementation.
The FIZ Language
The FIZ language has the following features. The core concept in the language is that of expressions. In FLIZ, all expressions should evaluate to non-negative integer values. There are four basic types of expressions:
- A non-negative integer, which evaluates to its value
- (inc [expr]) ; which evaluates to value of [expr] + 1
- (dec [expr]) ; which evaluates to the value of [expr] - 1; however, if the result is less than 0, then the interpreter prints an error message and exits.
- (ifz [expr] [expr] [expr]) ; evaluates the first [expr], if it is zero, then evaluates the second [expr] and returns its value; otherwise evaluates the third [expr] and returns its value.
The power of the language comes from the ability to define new functions, using the following syntax:
(define (function-name arguments) function-body )
Examples (texts from ';' to end of line are comments):
(define (add x y) ; addition of x and y
(ifz y x (add (inc x) (dec y))))
(define (mul x y) ; multiplication of x and y
(ifz y 0 (add x (mul x (dec y)))))
With new functions, an additional form of expressions is of the form:
- (function-name [expr] [expr])
This is a function application. One can roughly view (inc [expr]), (dec [expr]), and (ifz [expr] [expr] [expr]) as special cases of function applications, and thus treat inc, dec, and ifz as built-in functions.
Todos for this part
- Build the provided fiz interpreter. Run the resulting binary ./fiz. Type help to see the statements/comments. Use the “import” command to load the test files (i.e., import test1.f). Turn “tracing on” and run some defined functions with small numbers as input arguments, to see and understand how these function are executed.
- Tries to implement addition, multiplication, division, remainder, and gcd (greatest common divisors) in FIZ. If you are unable to do it after spending significant period of time, you can consult the two test files.
- Implement (lcm x y), which computes the least common multiple of x and y.
- Implement (sroot z), which gives the largest positive integer y such y^2 ≤ z.
- Implement (minv x z), which gives the smallest positive integer y such that xy % z=1. (Dividing xy with z results in a remainder of 1.) (minv x z) exists only when gcd(x,z)=1. When gcd(x,z) does not equal 1, just use (halt) to quite the interpreter.
- You are required to write the implementation to a file named ‘fizcode.f’ and push this part of the project into your git repository before 11:59 pm on 02/08/2017.
- The “fizcode.f” file should include all helper functions you will need. You can copy some functions from the given test files. You are likely need to write new helper functions. Grading is based only on correctness and does not consider efficiency.
Part 2: Support constant expressions
In this part, you are to support constant expressions. In FLIZ, a constant expression takes the following form:
- 123 ; a non-negative number
- [] ; An empty list
- [ [c] ] ; A list with a single constant expression
- [ [c] [c] ] ; A list with two or more expressions
Note that the above definition is recursive, so a list can include other lists. That is, the followings are legitimate lists.
Todos for this part
- You probably want to start by copying from the provided code for FIZ. You do not need to implement tracing, so the code supporting them are not needed. You are also not required to eliminate memory leakage, so the code freeing unnecessary memory is not needed either.
- If you want to start by modifying existing FIZ code, you should make a copy of the files first. You files implementing FLIZ should be called fliz.l and fliz.y.
- You need to define the grammar rules to handle a constant expression, creating associated data structures as you go, and then printing out such a list.
- The main work lies in defining a data structure to support possibly nested lists. Note that any element of a list can also be a list. When parsing a list expression, you can build up the data structure. Your code should not have a fixed limit on the length of the list. In FIZ, every value is an integer. However, in FLIZ, a value can be a list or an integer. This means that many places where the FIZ code uses int, you should need to replace it with your newly defined data type.
- When a constant list is entered at the prompt, you should print out the evaluated list. The printed list should be such that there is exactly one space between any pair among [, ], and list elements.
- Use tf1.f to test your implementation. See the content of the file, it comments indicate what outputs is expected.
Part 3: Support built-in functions
The FLIZ language has the following built-in functions
- (head [expr]) ; Evaluates to the first element of the list that [expr] evaluates to
- (tail [expr]) ; Evaluates to the list obtained by removing the first element from the list that [expr] evaluates to.
- (list [expr] [expr]) ; Evaluates to a list with the first [expr] being the head, and the second [expr] being the rest of list
- (ifn [expr] [expr] [expr]) ; If the first [expr] evaluates to a null list, then evaluates to the result of evaluating the second [expr], otherwise evaluates to the result of evaluating the third [expr]
- (ifa [expr] [expr] [expr]) ; if the first [expr] evaluates to an atomic (i.e. non-list) constant (i.e., when [expr] evaluates to a number), then evaluates to the result of evaluating the second [expr]; otherwise evaluates to the result of evaluating the third [expr]
You need to implement these functions.
Todos for this part
- You can check how (inc …), (dec …), (ifz …) are implemented in the provided code, and follow a similar strategy.
- Use the test file tf2.f to check your implementation.
Part 4: Supporting user-defined functions
In this part, you need to ensure that user-defined functions are supported. For this, you can use the provided code in FIZ with almost no change. That is, if you do it the right way, then after finishing Part 2 and Part 3, you do not need to add anything. However, if you have not integrated the function-handling code, then this is the time to do it.
Todos for this part
- Support for defining new functions already exist in FIZ. The same code also works for
FLIZ. - Use the test files tf3.f and tf4.f to check your implementation.
- Implement the following functions in FLIZ. If your own interpreter is not fully functional, you can use the provided binary rfliz to do so.
- (intlist x) ; evaluates to 0 if x is a simple list of integers (no nested lists), and to 1 otherwise.
- (reverse x) ; reverse the elements in x
- (recreverse x) ; recursively inverse elements in x, that is, any nested lists are also reversed.
- These implementation should be put into a file called flizcode.y.