Type Inference

We extend the MicroCaml programming language in Assignment $5$ with an additional con$-$ struct called Pair. A pair $\{1,2\}$ consists of two elements $1$ and $2,$ each of which may have a different type.

typeop$=$Add$|$Sub$|...$

type var $=$ string

type expr $=$

$|$ Int of int

$|$ Bool of bool

$|$ String of string

$|$ ID of var

$|$ Fun of var $$ expr

$|$ Not of expr

$|$ Binop of op $$ expr $$ expr

$|$ If of expr $$ expr $$ expr

$|$ FunctionCall of expr $$ expr

$|$ Let of var $$ bool $$ expr $$ expr

$|$ Pair of exper $$ expr $($ Extend MicroCaml with Pair $)$

type typeScheme $=$

$|$ TNum $|$ TBool $|$ TStr $|$ T of string

$|$ TFun of typeScheme $$ typeScheme

$|$ TPair of typeScheme $$ typeScheme $($ Add pair types $)$

We assume the parser has also been extended so it can parse a pair in the syntax $\{1,2\}$ as an abstract syntax tree Pair$(1,2).$ For example, the extended MicroCaml language allows you to write a program as follows:

let rec f x y $=$ if x then $\{$f y$,$ y$\}$ else $\{$y$,$ f x$\}$

We also extended typeScheme to support pair types. A pair type for Pair$(1,2)$ is in the shape of $\{12\}$ where $1$ is the type of $1$ and $2$ is the type of $2.$ For example, the type of the expression $\{1,$ "hello"$\}$ is $\{$int $$ string$\}$ or TPair $($TNum$,$ TStr$).$

$($a$)(1$ point$)$ Provide a typing rule in a similar style as in the Assignment $5$ description for pairs $\{1,2\}.$

CS$314$

Final, Page $9$ of $1216$

th

Dec, $2023$

$($b$)(1$ point$)$ Consider the unify implementation in Assignment $5.$ What would you put in place for the blank such that unify can be applied for type inference of MicroCaml programs with pairs?

let rec unify $($ constraints : $($ typeScheme $$ typeScheme $)$ substitutions $=$

match constraints with

l i s t $)$ :

$||$

and

$[]>[]$

$($x$,$ y$)$ :: xs $>$

let t$2=$ unify xs in

let t$1=$ unify$\_$one $($apply t$2$ x$)($apply t$2$ y$)$ in t$1$ @ t$2$

unify$\_$one $($ t$1$ : typeScheme $)($ t$2$ : typeScheme $)$ : substitutions $=$

match t$1,$ t$2$ with

$|$ TNum, TNum $|$ TBool, TBool $|$ TStr$,$ TStr $>[]$

$|$ T$($x$),$ z $|$ z$,$ T$($x$)>[($x$,$ z$)]$

$|$ TFun$($a$,$ b$),$ TFun$($x$,$ y$)>$ unify $[($a$,$ x$)$; $($b$,$ y$)]($ Fill in the blank to complete unify for pairs $)|$ TPair $($a $,$ b$),$ TPair $($x $,$ y$)>\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$|\_>$ raise $($failwith "mismatched types"$)$

$($c$)(1$ point$)$ Write down the type of

let rec f x y $=$ if x then $\{$f y$,$ y$\}$ else $\{$y$,$ f x$\}$

$($d$)(1$ point$)$ Consider the following program:

let f $=$ fun x $>$ x in let y $=$ f $1$ in

f $"$ hello $"$

Is the type inference algorithm, as implemented in Assignment $5,$ capable of deducing the type of this program? If your response is negative, provide a rationale for your answer.