In this homework assignment, you will be representing System E in Haskell and writing functions to do type$-$checking, substitution$/$shifting$,$ the Progress theorem, and evaluation to a value.

First, download the file hw$1.$hs Download hw$1.$hs$.$ Working within this file, provide definitions for all functions currently returning undefined and test all your functions, creating several test expressions in your file and putting the test results in comments.

Turn in your edited and commented hw$1.$hs file here.

System

import Data.Char $($toupper$)$

$--.-$ Abstract Syntax, using de Bruijn indices $-.--$

Types

data Typ $=$ NumT $|$ StrT

Expressions

data Exp$=$ Var Int $|$ Num Int $|$ Str String

$|$ Plus Exp Exp $|$ Times Exp Exp $|$ Cat Exp Exp $|$ Len Exp

$|$ Let ExpExp

$--$ Contexts $($first element of list $=$ last element of ctx$).$ For example,

$--$ the context x:num, y:str$,$ z:str is represented as $[$StrT$,$ StrT$,$ NumT$].$

type Ctx Typ$]$

An example expression with free variable z

Concrete syntax:

$,$ let $x=str[abc]$

$,y=$len$(x)$

$,$ in $|x^{{?}^{?}}x|**(y+z)$

$--$ Abstract syntax:

$--,$let$(str[abc]$;$x*let(len(x)$;$y*(len(cat(x$;$x))$;plus$(y$;$z))))$

myexp : : Exp

myexp $=$ Let $($Str "abc"$)$

$($Let $($Len $($Var $0))$

$($Times $($Len $($Cat $($Var $1)($Var $1)))$

lus $(Var0)(Var2)--$ Create several more for your own testing

$----$ output format for abstract syntax, using variable names $--$

$--$ Variable names to use for printing terms, chosen in the given order;

$--$ free variables are printed as uppercase

vars :: string

vars $=$ "xyuvwabcdefghijklmnopqrst"

instance Show Typ where

show NumT $=$ "num"

show StrT $="$str$"$

instance Show Exp where

show e $=$ showvars e $0$ where

showvars $($Var $n)$ i $|n>=i=[$toupper $vars!!$(n-i)$

otherwise $!!(i-n-1)$

showvars $($Num $n)i=$ "num$["++$ show $n++"]"$

showvars $($Str s$)i="$str$["++$ s $++"]"$

showvars $($Plus e$1$ e$2)$ i $=$

"plus$("++$ showvars e$1$ i $++"$;$"++$ showvars e$2$ i $++")"$

showvars $($Times e$1$ e$2)i=$

"times$("++$ showvars e$1$ i $++"$;$"++$ showvars e$2$ i $++")"$

showvars $($Cat e$1$ e$2)$ i$=$"cat$("++$ showvars e$1$ i $++"$;$"++$ showvars e$2$ i $++")"$

showvars $($Len e$1)$ i $=$

"len$("++$ showvars e$1$ i $++")"$

showvars $($Let e$1$ e$2)i=$

"let$("++$ showvars e$1$ i $++"$;$"++$ vars $!!$ i : $"."++$

showvars e$2($i$+1)++")"$

Maybe$-$valued index lookup

look : : $[$a$]->$ Int $->$ Maybe a

look Nothing

look $[]=$ Nothing

look $(x$:$xs$ Just $x$

look $(x$:$xs$ look $xs(n-1)$

Closed terms

closed : : Exp $->$ Bool

closed $e=$ undefined

$--$ Type checking $($Nothing $=$ not well$-$typed, Just $t=$ has type $t)$

typof : : Ctx $->$ Exp $->$ Maybe Typ

typof $g$ e $=$ undefined

shift e $i=$ add $i$ to all free variables in $e$

shift :: Exp $->$ Int $->$ Exp

shift e $i=$ undefined

subst $ei{e}^{\text{'}}=$ substitute $e$ for $i$ in $e^{\text{'}}$

subst : : Exp $$ Int $$ Exp $$ Exp

subst e i e $e^{\text{'}}=$ undefined$----$ Eager progress

data ProgressR $=$ Value $|$ Step Exp deriving Show

Assumes input is a well$-$typed expression $($you don't need to check this$).$

Note: input might have free variables $($which are taken to be values$),$

so be careful with the associated de Bruin indices!

prog : : Exp $->$ ProgressR

prog e $=$ undefined

Step a well$-$typed expression using prog

step :: Exp $->$ Exp

step $e=$ case prog e of

Value $->$ e

Step e$\text{'}{e}^{\text{'}}{e}^{\text{'}}$

Step a well$-$typed expression to a value using prog

steps :: Exp $->$ Exp

steps $e=$ case prog e of

Value $$ e

Step e$\text{'}->$ steps e$\text{'}$

Big$-$step evaluation of well$-$typed terms

eval :: Exp $$ Exp

eval e $=$ undefined