Practice for Scheme and ML

Answer.

$($a$)$ Consider the following Scheme expressions.

$($define x $\text{'}(($a b $)$ c d $($e f g $)))$

$($define y $\text{'}(12(34))$

Show the tree structure of the list resulting from $($append $xy).$

$($b$)$ Consider the following Scheme expressions.

$($define $x($cons $\text{'}$a $($cons $\text{'}$b $($cons $\text{'}$c $\text{'}()))))$

$($define y $($cons $($car x$)($cdr x$)))$

Show the memory allocation diagram for x and y $.($Note: cons allocates one cell$)$

Evaluate the following ML expressions using appropriate reduction rules.

For each, you should show the abstract syntax tree and inner$-/$outer$-$most reduction diagrams as requested.

$($a$)$ let val $x=3$ in let val $y=x+1$ in $x+y**y$ end end Please show the AST and outer$-$most reduction.

$($b$)$ let val $x=3$ in let val $x=x+1$ in $x+x**x$ end end Please show the AST and outer$-$most reduction.

$($c$)$ let val $x=3$ val $y=x+1$ in $x+y**y$ end Please show the AST and outer$-$most reduction.

$($d$)$ let val $x=$ let val $x=3$ in $x+1$ end in $x+x$ end Please show the AST and outer$-$most reduction.

$($e$)$ let fun sq $(x)=x**x$ val $x=3$ in $sq(x)$ end Please show the AST and inner$-$most reduction.

$($f$)$ let val $x=3$ fun $sq(x)=x^{**}x$ in $sq(x)$ end Please show the AST and inner$-$most reduction.

$($g$)$ let fun $f(x)=g(1,x)$ and $g(a,x)=x+$a val $x=3$ in $f(x)$ end Please show the AST and inner$-$most reduction.