Homework Assignment #3 Solution

Assignment Objectives



Get acquainted with the notion of




sequential aspects of Erlang




Assignment Policies



Collaboration Policy. This homework may be done in individually or in pairs. Use of the Internet is allowed, but should not include searching for existing solutions.




Under absolutely no circumstances code can be exchanged between students. Excerpts of code presented in class can be used.




Assignments from previous offerings of the course must not be re-used. Violations will be penalized appropriately.




Late Policy. Late submissions are allowed with a penalty of 2 points per hour past the deadline.




Assignment



The aim of this assignment is to write an interpreter for a simple functional language called SFL.




SFL



4.1 Syntax




A program in SFL is called an expression and is defined by the following gram-mar:






1 < Exp := < Num




| <Id
| -( < Exp , < Exp )
| +( < Exp , < Exp )
| zero ?( < Exp )
6
|
if < Exp then
< Exp else
< Exp
7
|
let
i d e n t i f i e r
= < Exp in
< Exp
8
|
proc
( < Id ) < Exp


| < Exp ( < Exp )
| ( < Exp )



You will be supplied with a parser for SFL. As an example, the result of parsing the string "let y=3 in +(2,y)" is




{ok ,{ letExp ,{id ,1 , y} ,



{ numExp ,{ num ,1 ,3 }} ,
{ plusExp ,{ numExp ,{ num ,1 ,2 }} ,{ idExp ,{id ,1 , y }}}}}



For the possible values that you may get from the parser, please inspect




parser.yrl.




Note: In order to generate the lexer and the parser you must run these lines (ignore the shift/reduce and reduce/reduce conflicts).




32 leex : file ( lexer ).



2 {ok ," ./ lexer . erl "} 3 33 c ( lexer ).




4 {ok , lexer }




5 34 yecc : file ( parser ).




6 parser . yrl : Warning : c on f li c ts : 3 shift / reduce , 0 reduce / reduce 7 {ok ," parser . erl "}




8 35 c ( parser ).




9 {ok , parser }







4.2 Semantics




An expression can return three possible values: a number, a boolean or a closure. Here are some examples of expressions in SFL, collected in a module called tests. The runStr/1 function parses and evaluates an expression. It will be defined in another module (interp.erl).




- module ( tests ).



- export ([ start /0 ] ).



3




start () -



lists : map ( fun interp : runStr /1 , examples ()).



6




examples () -



8
[ ex1 () , ex2 () , ex3 () , ex4 () , ex5 () , ex6 () , ex7 () , ex8 () , ex9 () ].
9





ex1 () -



11
" let x=1 in let x=3 in +(x ,7) ".
12





ex2 () -



" +(2 ,3) ".



15




ex3 () -



" proc (x) +(x ,3) ".



18




ex4 () -



" let y=3 in proc (x) +(x,y)" .



21




22 ex5 () -






2















" let y=3 in +(2 ,y)".



24




ex6 () -



26
" let y= proc (x) +(x ,1) in y (5) ".
27





ex7 () -



" let x=1 in let y= proc (z) +(z,x) in y (6) ".



30




ex8 () -



" zero ?(7) ".



33




ex9 () -



" let x=1 in let f= proc (y) +(y,x) in let x=2 in f(3) ".



When we run these examples we get the following output:




16 c ( tests ).



2 {ok , tests }




3 17 tests : start ().




4 [{ num ,10 } ,




5 { num ,5 } ,




6 { proc ,x ,




{ plusExp ,{ idExp ,{id ,1 , x}} ,{ numExp ,{ num ,1 ,3 }}} ,
{ dict ,0 ,16 ,16 ,8 ,80 ,48 ,
{[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,... } ,
{{[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,... }}}} ,
{ proc ,x ,
{ plusExp ,{ idExp ,{id ,1 , x}} ,{ idExp ,{id ,1 , y}}} ,
{ dict ,1 ,16 ,16 ,8 ,80 ,48 ,
{[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,... } ,
{{[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[] ,[[ ... ]] ,[] ,... }}}} ,
{ num ,5 } ,
{ num ,6 } ,
{ num ,7 } ,
{ bool , false } ,
{ num ,4 }]



You can also parse and evaluate a program from a file using




- spec runFile ( string ()) - valType ().






The Interpreter



Your task is to build an interpreter for SFL. It should conform to the following type specification:




- spec valueOf ( expType () , envType ()) - valType ().



where these types are defined as follows (types.hrl):




- type envType () :: dict : dict ( atom () , valType ()).



2 - type expType () :: tuple ().




3










4
- type
n u m V a l T y p e ()
:: { num , integer () }.
5
- type
b o o l V a l T y p e ()
:: {
bool ,
boolean () }.
6
- type
p r o c V a l T y p e ()
:: {
proc ,
atom () , expType () , envType () }.
- type valType () :: n u m V a l T y p e () | b o o l V a l T y p e () | p r o c V a l T y p e ().






5.1 Summary




Modules to complete:






interp.erl: Implement valueOf.




env.erl: Implement the following operations (that just constitute wrappers




for the corresponding operations in dict, which you should look up).




- module ( env ).



- compile ( e x p o r t _ a l l ).
3 - include ( " types . hrl " ).




4




5




- spec new () - envType ().



7 new () -




8%% define




9




- spec add ( envType () , atom () , valType ()) - envType ().



add ( Env , Key , Value ) -
%% define



13




- spec lookup ( envType () , atom ()) - valType ().



lookup ( Env , Key ) -
%% define



You must make sure that your code passes the Dialyzer analysis (you may ignore the “Unknown functions” warning).




$ dialyzer interp . erl



2 Checking whether the PLT / Users / ebonelli /. d i a l y z e r _ p l t is up - to - date ... yes

P r o c e e d i n g with analysis ...
4 Unknown fu n ct io n s :




5env : add /3

6env : lookup /2

7env : new /0

8lexer : string /1

9parser : parse /1

done in 0 m1 .77 s
done ( passed s u c c e s s f u l l y )






Submission Instructions



Submit a zip file named Assignment3_<Surname.zip (where <Surname should be replaced by your surname) through Canvas containing all the files in the stub (which should have been completed).



















































4