
\documentclass[9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}
%\documentclass[handout,9pt,xcolor=dvipsnames,unknownkeysallowed]{beamer}

\input{../Common/common}




\title % (optional, use only with long paper titles)
{02157 Functional Programming}

\subtitle
{Finite trees (II)\\
-- Interpreters for two simple languages} % (optional)

\date {MRH 7/11/2024}% (optional)


\begin{document}

\begin{frame}
  \titlepage


\end{frame}

\begin{frame}{Overview}



Finite trees: Two examples
\begin{itemize}
	\item An interpreter for a simple expression language
	\bigskip
	
	\item An interpreter for a simple while-language
	\medskip
	
\end{itemize}
 

	
\end{frame}


\begin{frame}

\begin{center}
	\LARGE\darkgreen Finite trees (II)
\end{center}
\end{frame}


\begin{frame}{Interpreters for two simple languages --- Purpose}

To show the power of a functional programming language, we present
a prototype for interpreters for a simple expression language with local declarations and a simple WHILE language.

\medskip


\begin{itemize} \item<2-> Concrete syntax: defined by a
contextfree grammar

\item<3-> Abstract syntax (parse trees): defined by algebraic
datatypes

\item<4-> Semantics, i.e.\ meaning of programs: inductively
defined following the structure of the abstract syntax
\end{itemize}
\pause[4] \hfill {\redbrown succinct programs, fast prototyping}

\bigskip
\pause[5]
The interpreter for the simple expression language is a higher-order function:
\[\blue eval : Program \to Environment \to Value \]

\medskip

The interpreter for a simple imperative programming
language is a higher-order function:
\[\blue I : Program \to State \to State \]
\end{frame}


\begin{frame}[fragile]\frametitle{Expressions with local declarations}

Concrete syntax:
\begin{alltt}\blue
a * (-3 + (let x = 5 in x + a))
\end{alltt}
\pause

The {\blue abstract syntax} is defined by an algebraic datatype:
\begin{alltt}\blue
type ExprTree = | Const of int
                | Ident of string
                | Minus of ExprTree
                | Sum   of ExprTree * ExprTree
                | Diff  of ExprTree * ExprTree
                | Prod  of ExprTree * ExprTree
                | Let of string * ExprTree * ExprTree;;
\end{alltt}

\pause
Example:
\begin{alltt}\blue
let et =
  Prod(Ident "a",
       Sum(Minus (Const 3),
           Let("x", Const 5, Sum(Ident "x", Ident "a"))));;
\end{alltt}

\end{frame}

\begin{frame}[fragile]\frametitle{Evaluation in Environments}

An {\em\redbrown environment} contains {\em\redbrown bindings} of
identifiers to values.

\medskip
\pause

A tree
$\blue \texttt{Let(} {\it s}\texttt{,} t_1 \texttt{,} t_2 \texttt{)}$
is evaluated in an environment {\it\blue  env}:
\begin{enumerate}
\item Evaluate $\blue t_1$ to value $\blue v_1$ in environment {\it\blue  env}.
\item Evaluate $\blue t_2$ in {\darkgreen{\it\blue env} extended with the binding of {\it s}
to $v_1$}.
\end{enumerate}

\medskip
\pause

An evaluation function
\begin{alltt}\blue
eval: ExprTree -> Map<string,int> -> int
\end{alltt}
is defined as follows:
\begin{alltt}\blue
let rec eval t env =
    match t with
    | Const n      -> n
    | Ident s      -> Map.find s env
    | Minus t      -> - (eval t env)
    | Sum(t1,t2)   -> eval t1 env + eval t2 env
    | Diff(t1,t2)  -> eval t1 env - eval t2 env
    | Prod(t1,t2)  -> eval t1 env * eval t2 env
    | Let(s,t1,t2) -> let v1   = eval t1 env
                      let env1 ={\darkgreen Map.add s v1} env
                      eval t2 env1;;
\end{alltt}



\end{frame}

\begin{frame}[fragile]\frametitle{Example}
Concrete syntax:
\begin{alltt}\redbrown
	a * (-3 + (let x = 5 in x + a))
\end{alltt}
\pause

\bigskip

\begin{alltt}\blue
let et =
  Prod(Ident "a", 
       Sum(Minus (Const 3),
           Let("x", Const 5, Sum(Ident "x", Ident "a"))));;
\end{alltt}	

\bigskip
\pause

\begin{alltt}\blue
let env = Map.add "a" -7 Map.empty;;
eval et env;;
\ett{val it : int = 35}
\end{alltt}

\end{frame}


\begin{frame}[fragile]\frametitle{Example: Imperative Factorial program}

An example of concrete syntax for a factorial program:

{\blue
\begin{alltt}
   y:=1 ;
   while !(x=0)
   do (y:= y*x;x:=x-1)
\end{alltt}
}

\bigskip
\pause

Typical ingredients
\begin{itemize}
\item<2-> Arithmetical expressions

\item<3-> Boolean expressions

\item<4-> Statements (assignments, sequential composition, loops,
$\ldots$
\end{itemize}

\end{frame}

\begin{frame}[fragile]\frametitle{Arithmetic Expressions}

\begin{itemize}

%\item Grammar:
%\[\blue  aExp\ ::-\ n\ |\ v\ |\ aExp + aExp\ | aExp \cdot aExp\ |\ aExp - aExp\ |\ ( aExp ) \]
%where {\blue $n$} is an integer and {\blue $v$} is a variable.

%\bigskip

\item<1-> A type the abstract syntax for Arithmetical Expressions  {\blue
\begin{verbatim}
type AExp =      (* Arithmetical expressions *)
   | N  of int             (* numbers        *)
   | V  of string          (* variables      *)
   | Add of AExp * AExp    (* addition       *)
   | Mul of AExp * AExp    (* multiplication *)
   | Sub of AExp * AExp;;  (* subtraction    *)
\end{verbatim}
}
\pause[2]

\bigskip
\begin{center}
You do not need parenthesis, precedence rules, etc.\\  
in the {\blue abstract syntax}\\[3mm] 
{\darkgreen you work directly on trees}.	
\end{center}


\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Semantics of Arithmetic Expressions}
\begin{itemize}
\item A {\darkgreen state} maps variables to integers {\blue
\begin{verbatim}
   type State = Map<string,int>;;
\end{verbatim}
}

\medskip

\item<2-> The meaning of an expression is a function: {\blue
\begin{verbatim}
   A: AExp -> State -> int
\end{verbatim}
}

\medskip

\pause[3] defined inductively on the
  structure of arithmetic expressions
{\blue
\begin{verbatim}
let rec A a s      =
   match a with
    | N n         -> n
    | V x         -> Map.find x s
    | Add(a1, a2) -> A a1 s + A a2 s
    | Mul(a1, a2) -> A a1 s * A a2 s
    | Sub(a1, a2) -> A a1 s - A a2 s;;
\end{verbatim}
}
\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Boolean Expressions}
\begin{itemize}
\item Abstract syntax {\blue
\begin{verbatim}
type BExp =          (* Boolean expressions *)
   | TT                     (* true         *)
   | FF                     (* false        *)
   | Eq of ....             (* equality     *)
   | Lt of ....             (* less than    *)
   | Neg of ....            (* negation     *)
   | Con of ....       ;;   (* conjunction  *)
\end{verbatim}
}


\item<2-> Semantics {\blue B : BExp $\to$ State $\to$ bool} {\blue
\begin{verbatim}
let rec B b s =
   match b with
   | TT       -> true
   | ....
\end{verbatim}
}
\end{itemize}

\end{frame}


\begin{frame}[fragile]\frametitle{Statements: Abstract Syntax}

{\blue
\begin{verbatim}
type Stm  =                     (* statements             *)
   | Ass of string * AExp       (* assignment             *)
   | Seq  of Stm list           (* sequential composition *)
   | ITE   of BExp * Stm * Stm  (* if-then-else           *)
   | While of BExp * Stm;;      (* while                  *)
\end{verbatim}}

\bigskip
\pause

Example of concrete syntax: {\blue \begin{verbatim}
   y:=1 ; while not(x=0) do (y:= y*x ; x:=x-1)
\end{verbatim}}

\bigskip

Abstract syntax {\redbrown ?}

\end{frame}



\begin{frame}[fragile]\frametitle{Update of states}

An imperative program performs a sequence of {\darkgreen state updates}.


\begin{itemize}
\item The expression
\[\redbrown \mathtt{update}\, y\, v\, s \] is the
state that is as {\redbrown $s$} except that {\redbrown $y$} is
mapped to {\redbrown $v$}.



\bigskip

\item<2-> Update is a synonym for $\blue\verb|Map.add|$:
{\blue
\begin{alltt}
let update x v s = Map.add x v s;;
\end{alltt}}

%\item<3->{\darkgreen Type?}
\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Interpreter for Statements}
\begin{itemize}
\item The meaning of statements is a function
\[\blue I: Stm \to State \to State
\]
that is defined by induction on the structure of statements:
{\blue
\begin{verbatim}
let rec I stm s =
    match stm with
    | Ass(x,a)         -> update x ( ... ) s
    | Seq stms         -> ...
    | ITE(b,stm1,stm2) -> ...
    | While(b, stm)    -> ... ;;
\end{verbatim}}
\end{itemize}
\end{frame}


\begin{frame}[fragile]\frametitle{Example: Factorial function}
\begin{alltt}
(* 
      y:=1 ; while !(x=0) do (y:= y*x;x:=x-1)
*)
\pause

let fac = Seq [Ass("y", N 1);
               While(Neg(Eq(V "x", N 0)),
                    Seq [Ass("y", Mul(V "x", V "y")) ,
                         Ass("x", Sub(V "x", N 1)) ])];;

\pause
(* Define an initial state                           *)
let s0 = Map.ofList [("x",4)];;
\ett{val s0 : Map<string,int> = map [("x", 4)]}

\pause
(* Interpret the program                             *)
let s1 = I fac s0;;
\ett{val s1 : Map<string,int> = map [("x", 1); ("y", 24)]}
\end{alltt}

\end{frame}

\begin{frame}


Interpreter will be available on Learn.	

\bigskip
	

\begin{itemize}

\item You may add the statements {\blue skip}, {\blue if-then} and {\blue repeat-until}.

\bigskip

\item Suppose that an expression of the form {\blue $inc(x)$} is
added. It adds one to the value of {\blue $x$} in the current
state, and the value of the expression is this new value of {\blue
$x$}.
\medskip

How would you refine the interpreter to cope with this construct?
\begin{itemize}
	\item  Analyse the problem and state the types for the refined interpretation functions
\end{itemize}

\end{itemize}
\end{frame}





\end{document}
