MFC/p3/memoria.tex

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{listings}

\title{Laboratorio 3 - Maude}
\author{Carlos Santiago Galindo Jiménez}

\lstset{basicstyle=\ttfamily}

\begin{document}
	\maketitle
	\section{Ejercicios básicos}
	\subsection{Sumatorio}
	Para realizar un sumatorio simplemente necesitamos una función binaria que compruebe si ambos argumentos son iguales, en un caso con una llamada recursiva y en el otro devolviendo cualquiera de los argumentos.
	\begin{lstlisting}
f (x, y) = if x == y
     then y
     else x + f(x + 1, y)
	\end{lstlisting}
	Para llamar a esta función, podemos ejecutar la siguiente sentencia:
	\begin{lstlisting}
eval(let rec f(x,y) = if x == y
             then y
             else x + f(x + 1, y)
	in f(1,5)) .
	\end{lstlisting}
	Y Maude devolvería \texttt{int(15)}, que es el resultado de $\sum_{i=1}^5 i$.
	
	\subsection{Máximo}
	\begin{lstlisting}
f(a, b) = if a >= b
    then a
    else b
	\end{lstlisting}
	Y la ejecución sería similar al ejercicio anterior, aunque no es necesaria la palabra clave \texttt{rec}.
	
	\subsection{Factorial}
	\begin{lstlisting}
f(x) = if x == 0
       then 1
       else x * f(x - 1)
	\end{lstlisting}
	En este caso sí que es necesario que la definición sea recursiva.
	
	\section{Ejercicios sobre tipos listas}
	\subsection{Contar occurrencias en una lista}
	\begin{lstlisting}
f(x,l) = if null?(l)
         then 0
         else if car(l) == x
              then 1 + f(x, cdr(l))
              else f(x, cdr(l))
	\end{lstlisting}
	\subsection{Reemplazar ocurrencias de \texttt{a} por otro elemento \texttt{b}}
	\begin{lstlisting}
f(a,b,l) = if null?(l)
           then []
           else if car(l) == a
                then cons(b, f(a,b,cdr(l)))
                else cons(car(l), f(a,b,cdr(l)))
	\end{lstlisting}
	\subsection{Extraer de una lista los menores que un número \texttt{n}}
	\begin{lstlisting}
f(n,l) = if null?(l)
         then []
         else if (car(l) <= n) and (not(car(l) == n))
              then cons(car(l), f(n,cdr(l)))
              else f(n,cdr(l))
	\end{lstlisting}
	Y para extenderlo a cualquier función que tome como argumento 2 números y devuelva un booleano:
	\begin{lstlisting}
f(n,l,g) = if null?(l)
           then []
           else if g(car(l), n)
                then cons(car(l), f(n,cdr(l),g))
                else f(n,cdr(l),g)
	\end{lstlisting}
	Y la llamada se podría realizar del siguiente modo:
	\begin{lstlisting}
reduce in FUN-TEST : eval(
  let h(a,b) = (a <= b) and (not (a == b))
  in
    let rec f(n,l,g) = if null?(l)
                       then []
                       else if g(car(l), n)
                            then cons(car(l), f(n,cdr(l),g))
                            else f(n,cdr(l),g)
    in f(5, [1, 5, 2, 6, 3], h)
) .
	\end{lstlisting}
	\section{Ejercicios con punteros}
	El fichero modificado extendiendo el lenguaje funcional con punteros está adjunto y también en el anexo \ref{anexo}. Las líneas modificadas son: 100-103, 107, 139, 440-451 y 474.
	\subsection{Swap entre punteros}
	\begin{lstlisting}
f(a, b) = let c = * a
          in { * a := * b ; * b := c }
	\end{lstlisting}
	Para ejecutarlo, tenemos que crear dos variables y darles un valor, y al final mostrar una de ellas para comprobar su estado:
	\begin{lstlisting}
reduce in FUN-TEST : eval(
  let x = 2 and y = 1
  and f(a,b) = let c = * a
               in { * a := * b ; * b := c }
  in { f(& x, & y) ; [x,y] }
) .
	\end{lstlisting}
	Y el resultado sería $[1, 2]$.
	
	\subsection{Extraer mínimo y máximo de una lista}
	A la función se le pasan 3 parámetros: la lista y dos referencias al máximo y el mínimo hasta el momento. Para inicializar estos dos valores se emplea el primer elemento de la lista, puesto que no existe una constante que denote el mayor o menor número posible. También se podría emplear una variable auxiliar que denote si el primer elemento de la lista ha sido leído. Como prerrequisito, es necesario que la lista tenga al menos un elemento.
	\begin{lstlisting}
reduce in FUN-TEST : eval(
  let rec a = 0 and b = 0
  and m(l, x, y) = {
    * x := car(l) ;
    * y := car(l) ;
    f(cdr(l), x, y)
  } and f(l, x, y) =
    if not null?(l) then {
      if car(l) <= * x then
        * x := car(l)
      else (if car(l) >= * y then
        * y := car(l)
      else { } ) ;
      f(cdr(l), x, y)
    } else { }
  in { f([1, 2, 3, 4, 5], & a, & b) ; [a,b] }
) .
	\end{lstlisting}
	
	\newpage
	\appendix
	\section{Extensión del lenguaje funcional: Punteros}
	\label{anexo}
	\lstinputlisting[basicstyle=\footnotesize\ttfamily,numbers=left,stepnumber=1]{funcional_con_punteros.maude}
\end{document}