\input{header.tex}
\title{Principles of Programming Languages (Sheet \#1)}
\author{Marius Gavrilescu}
\date{}
\maketitle
\begin{enumerate}
\setcounter{enumi}{1}
\item % 2.
\begin{enumerate}
\item % (a)
\begin{verbatim}
index x [] = -1
index x (y:ys) =
if x == y then
0
else
let ans = index x ys in
if ans == -1 then
-1
else
ans + 1
-- or without examining the result of a recursive call:
helper x [] n = -1
helper x (y:ys) n =
if x == y then
n
else
helper x ys (n+1)
index x ys = helper x ys 0
\end{verbatim}
\item % (b)
\begin{verbatim}
rec helper (x, ys, n) =
if ys = nil then
-1
else if x = head(ys) then
n
else
helper(x, tail(ys), n+1)
;;
rec index(x, ys) = helper(x, ys, 0);;
\end{verbatim}
\item % (c)
\begin{verbatim}
index x ys =
let n = length ys in
let zs = zip ys [0..(n - 1)] in
let is_x (y, _idx) = x == y in
let found = filter is_x zs in
if null found then
-1
else
snd (head found)
\end{verbatim}
\end{enumerate}
\clearpage
\setcounter{enumi}{0}
\item % 1.
\begin{verbatim}
rec foldl(f, e, xs) =
if xs = nil then e else f(head(xs), foldl(f, e, tail(xs)));;
rec foldr(f, e, xs) =
if xs = nil then e else foldr(f, f(head(xs), e), tail(xs));;
rec map(f, xs) =
foldl(lambda(x, acc) f(x):acc, nil, xs);;
\end{verbatim}
\setcounter{enumi}{2}
\item % 3.
\texttt{x+3} is \texttt{Apply (Variable '+') [(Variable 'x'), (Number 3)]}.
\texttt{let val x = 2 in x+3} is\\ \texttt{Let (Val (Variable 'x') (Number 2))}\\\texttt{(Apply (Variable '+') [(Variable 'x'), (Number 3)])}.
\texttt{f(g(x))} is \texttt{Apply (Variable 'f') [Apply (Variable 'g') [Variable 'x']]}
\item % 4.
Legal. To evaluate each let we convert the lambda on the RHS into a
Function, which is then added to the environment using
Environment.define. Note that function bodies are only evaluated when
we call them, not when we define or add them to the environment.
With this arhitecture we do not need to handle references
intelligently: when we need to evaluate g's body we know x will be in
the environment, so we can simply pull it from there.
Therefore, to evaluate the entire expression we'll first convert the
body of f to a Function (without evaluating the body at all) and then
add it to the environment.
Then we will want to evaluate f(3), which means we'll add $x\mapsto 3$
to the environment and evaluate the body of f.
Now to evaluate the body of f, we will first convert the body of g to
a Function and add it to the environment.
Then we will want to evaluate g(2), which means we'll add $y\mapsto 2$ to the environment and evaluate the body of g.
Now to evaluate the body of g all we need to do is evaluate
the \texttt{Apply (Variable '+') [(Variable 'x'), (Variable 'y')]}
which is easy because we already have x and y in the environment.
\item % 5.
Legal, f(7) defines g(y) = y + 7, h(x) = g(x + 3) = x + 10, so h(14)
is 24.
\item % 6.
When we say \texttt{val x = 4} this creates a new variable named x
with value 4 which shadows the old variable named x. This does not
change the value of the old variable, which is used in the definition
of f.
\clearpage
\item % 7.
Environment.defargs raises an error in this case. Were this not the
case, due to the \texttt{zip} function used in defargs we'd ignore
extra arguments (if there are too many) or fail to bind missing
arguments (therefore we'd get an error in Environment.find if those
arguments are used by the function).
If the same name is reused then only the rightmost parameter with a
given name will have effect, with other parameters with that name
being ignored. This behaviour is also present in OCaml. In my opinion
this is suprising behaviour, violating the principle of least
astonishment.
This trait of the language enables us to ignore unused arguments (as
in the common\\ Haskell/OCaml idiom of naming unused arguments ``\_'').
There is no obvious class of bugs that would be enabled by this trait.
Notably, misspellings are NOT an issue, because if we misspell a
parameter and then go on to use its correct spelling we will simply
get a runtime error when that variable is evaluated (so, assuming our
unit tests have sufficient coverage, we should catch this problem.
Failing that, we can easily introduce a static check that catches it).
I personally prefer the Haskell way of only allowing repeating
parameters when their name is exactly ``\_'' (thus allowing us to
ignore parameters while raising an error if we name two parameters the
same). The behaviour exhibited by Fun looks more like an accident than
intentional design.
\item % 8.
\begin{verbatim}
eval (Apply (Lambda [x] e2) [e1]) env
= { definition of eval }
apply (eval (Lambda [x] e2) env) [eval e1 env]
= { definition of eval }
apply (abstract [x] e2 env) [eval e1 env]
= { definition of apply + abstract }
eval e2 (defargs env [x] [eval e1 env])
= { definition of defargs }
eval e2 (define env x (eval e1 env))
= { definition of elab }
eval e2 (elab (Val x e1) env)
= { definition of eval }
eval (Let (Val x e1) e2) env
\end{verbatim}
\clearpage
\item % 9.
\begin{enumerate}
\item % (a)
Change \texttt{Val Ident Expr} in the abstract syntax definition
of \texttt{data Defn} to \texttt{Val [Ident] [Expr]}.
Change \texttt{elab (Val x e) env} to:
\begin{verbatim}
elab (Val xs es) env =
defargs env xs (map ev es)
where ev e1 = eval e1 env
\end{verbatim}
\item % (b)
This requires no changes to the abstract syntax. Just change the
parser to understand the new concrete syntax and rewrite it into
nested let statements.
\item % (c)
Change \texttt{Rec Ident Expr} in the abstract syntax definition
of \texttt{data Defn} to \texttt{Rec [Ident] [Expr]}.
Change \texttt{elab (Rec x (Lambda xs e1)) env} to:
\begin{verbatim}
onlyLambda (Lambda xs e1) = (xs, e1)
onlyLambda _ = error "RHS of let rec must be a lambda"
elab (Rec xs es) env =
let es = map onlyLambda es in
let pairs = zip xs es in
env'
where env' =
foldr (\ (x, (xs, e1)) acc ->
define acc x (abstract xs e1 env')
\end{verbatim}
\end{enumerate}
\item % 10.
Since arrays are not (yet) implemented in this week's version of Fun,
we do not use the BRA and KET tokens for anything. Thus we can change
our parser to interpret BRA the same as the sequence IDENT ID list
followed by LPAR, and KET as RPAR. This can most easily be achieved
with another pass on the output of the lexer which makes these
substitutions before it is passed to the parser.
This means [...] will behave the same as list(...). This even supports
nested lists. The significant advantage is ease of implementation.
It still relies on a ``list'' primitive being available in the
environment (easy) and introduces problems when we will later add
arrays (needs working around; simply replacing BRA and KET is not
sufficient). Of course, a simple workaround for the post-array world
is to use different syntax for arrays, such as
OCaml's \texttt{arr.(index)} instead of \texttt{arr[index]}.
\end{enumerate}
\end{document}