Primer Parcial 1er Cuat 2008 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1: Programación Funcional[editar]

Durante todo este ejercicio no se puede usar recursion explıcita, a menos que se especifique explıcitamente lo contrario. Para resolver un ıtem pueden utilizarse como existentes las soluciones a todos los anteriores, mas alla de si fueron resueltos correctamente o no.

Definimos la funcion generate, que genera listas en base a un predicado y una funcion, de la siguiente manera:

generate :: ([a] -> Bool) -> ([a] -> a) -> [a]  
generate stop next = generateFrom stop next [] 

generateFrom:: ([a] -> Bool) -> ([a] -> a) -> [a] -> [a] 
generateFrom stop next xs | stop xs = xs 
                        | otherwise = generateFrom stop next (xs ++ [next xs]) 

Ejercicio A[editar]

Usando generate, escribir generateMaybe:: ([a] ->Maybe a) ->[a], que funciona de manera similar a generate, excepto que en lugar de recibir por separado el predicado y la funcion generadora, toma una funcion que devuelve un tipo Maybe. Si el resultado es Nothing, generateMaybe para de generar y si es Just a encola el elemento a y continua. Por ejemplo,

generateMaybe (\xs ->if (length xs) <3 then Just 1 else Nothing)

devuelve [1,1,1].

Respuesta

generateMaybe f = generate (\x -> isNothing (f x)) (\x -> fromJust (f x))
where isnothing x = (x == Nothing)
      fromJust (Just a) = a

Ejercicio B[editar]

Usando generate definir generateMult :: ([a] ->[a]) ->[a], que debe funcionar de manera similar a generate, excepto que toma una funcion f que devuelve una lista de elementos a ser encolados. Si la lista es vacia, el procedimiento se debe detener, si no, se deben encolar todos los elementos en el orden en el que fueron devueltos por f y continuar. Por ejemplo,

generateMult (\xs ->if (length xs) <3 then [1,2] else [])

devuelve [1,2,1,2].

Respuesta

generateMult f = juntar (generate stop next)
where stop xs = (f xs) == []
      next xs = f (juntar xs)
      juntar xs = foldr (++) [] xs

Ejercicio C[editar]

Definir iterateN :: Int ->(a ->a) ->a ->[a] utilizando alguno de los items anteriores. iterateN toma un entero n, una funcion f y un elemento inicial x y devuelve la lista [x, f x, f (f x), ..., f ( ...(f x) ...)] de longitud n.

Respuesta

iterateN n f x = generate stop next
where stop xs = (length xs) == n
      next xs = if (xs == []) then x else f (last xs)

Nota: last es una función del preludio.

Ejercicio D[editar]

Utilizando alguno de los items anteriores, reescribir la funcion del prelude de Haskell map :: (a ->b) ->[a] ->[b].

Respuesta

map f xs = generate stop next
where stop ys = (length xs) == (length ys)
      next ys = f (xs !! (length ys))

Ejercicio 2: Lambda cálculo tipado[editar]

En este ejercicio introduciremos pattern matching al calculo lambda tipado. Para eso nos basaremos en el calculo lambda con arboles binarios, como fue visto en clase, con el mismo conjunto de tipos:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \sigma ::= Bool \;|\; AB_\sigma \;|\; \sigma_1 \rightarrow \sigma_2}

Vamos a trabajar con el siguiente conjunto de términos M y patrones P :

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M ::= x \;|\; true \;|\; false \;|\; nil_\sigma \;|\; Bin(M_1, M_2, M_3) \;|\; \lambda x : \sigma.M \;|\; M_1\ M_2 \;|\; match\ M_1\ with\ P\ in\ M}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P ::= x \;|\; true \;|\; false \;|\; nil_\sigma \;|\; Bin(P_1, P_2, P_3)}

en donde Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M, M_1, M_2 \textrm{\ y\ } M_3} son terminos, x es una variable y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P, P_1, P_2 \textrm{\ y \ } P3} son patrones. Las reglas de tipado para los terminos usuales del calculo lambda (es decir, para cualquier termino distinto de match) son las vistas en clase, y vamos a usar esas mismas reglas para tipar a los patrones P . Ademas, un patron no puede tener variables repetidas, y esa restriccion se va a imponer en las reglas de tipado de la expresion match.

De forma equivalente al pattern matching de Haskell, si P es un patron, y M y N son términos, la construcción match M with P in N intenta hacer coincidir el valor de M con P. Esta construcción liga en N todas las ocurrencias de variables de P , asocia las variables de P con subexpresiones de M, y luego reemplaza en N las variables ligadas por P por las subexpresiones correspondientes. La idea es que un patrón de tipo σ coincida con términos de tipo σ. Los siguientes son ejemplos donde los patrones coinciden, y en donde se muestra la expresión a la que reducen:

  1. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ true\ with\ true\ in\ (\lambda x : Bool.x) \rightarrow \lambda x : Bool.x}
  2. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ Bin(nil_{Bool}, true, nil_{Bool})\ with\ Bin(x, y, z)\ in\ x \rightarrow nil_{Bool}}
  3. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ (\lambda x : AB_{Bool}.Bin(nil_{Bool}, true, x))\ nil_{Bool}\ with} Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Bin(x, y, nil_{Bool})\ in\ (\lambda x : Bool.x)\ y \rightarrow true}

Siguiendo con los ejemplos, la expresiones:

  1. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ false\ with\ true\ in\ (\lambda x : Bool.x)} no coincide (es decir, la expresion se indefine), aunque esta bien tipada
  2. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ nil_{Bool}\ with\ true\ in\ \lambda x : Bool.x} no esta bien tipada
  3. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ nil_{Bool}\ with\ Bin(x, x, x)\ in true} no esta bien tipada por tener variables repetidas en el patron
  4. Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle match\ Bin(nil_{Bool} , true, z )\ with\ Bin(x, true, y))\ in\ x} no reduce, porque M no es (ni reduce a) un valor.

Ejercicio A[editar]

Escribir las reglas de tipado necesarias para tipar la construccion match. Recordar que un patron no puede tener variables repetidas, y para imponer esa restriccion se puede suponer definido el predicado sinVarRepetidas(t), donde t es cualquier termino o patron del calculo lambda.

Respuesta

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\textrm{sinVarRep}(P) \;\;\; \Gamma \triangleright M_1:\alpha \;\;\; x_i:\sigma_i \triangleright P:\alpha \;\;\; \Gamma\cup\{x_i:\sigma_i\} \triangleright M_2:\tau}{\Gamma \triangleright \textrm{match}\ M_1\ \textrm{with}\ P\ \textrm{in}\ M_2:\tau}}

donde Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle x_i \in FV(P)} .

Ejercicio B[editar]

Decidir si los valores de este cálculo se ven modificados con respecto a los del cálculo original, y en ese caso dar formalmente su extensión. Definir las reglas semánticas de a un paso para la extensión propuesta, de manera tal que el calculo sea determinístico.

Respuesta

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{M_1 \rightarrow M_1'}{\textrm{match}\ M_1\ \textrm{with}\ P\ \textrm{in}\ M_2 \rightarrow \textrm{match}\ M_1'\ \textrm{with}\ P\ \textrm{in}\ M_2}}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{}{\textrm{match}\ V\ \textrm{with}\ x\ \textrm{in}\ M_2 \rightarrow M_2\{x \leftarrow V\} }}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{}{\textrm{match}\ T\ \textrm{with}\ T\ \textrm{in}\ M \rightarrow M}}

con Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T \in \{true,false,nil_\sigma\}}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\textrm{match}\ V_1\ \textrm{with}\ P_1\ \textrm{in}\ M_2 \rightarrow M_2}{\textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2 \rightarrow T'}}

con Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T' = \textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2'}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\forall x \in FV(P_1) \Rightarrow x\ \not\in\ FV(M_2) \;\;\; \textrm{match}\ V_2\ \textrm{with}\ P_2\ \textrm{in}\ M_2 \rightarrow M_2}{\textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2 \rightarrow T'}}

con Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T' = \textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2'}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\forall x \in FV(P_1), y \in FV(P_2) \Rightarrow x,y\ \not\in\ FV(M_2) \;\;\; \textrm{match}\ V_3\ \textrm{with}\ P_3\ \textrm{in}\ M_2 \rightarrow M_2}{\textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2 \rightarrow T'}}

con Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T' = \textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2'}


Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\forall x_i \in FV(P_i) \Rightarrow x_i\ \not\in\ FV(M_2)}{\textrm{match}\ Bin(V_1,V_2,V_3)\ \textrm{with}\ Bin(P_1,P_2,P_3)\ \textrm{in}\ M_2 \rightarrow M_2}}

Los valores no se modifican, se agregan formas normales que no son valores.

Ejercicio 3: Inferencia de tipos[editar]

La siguiente extension al calculo lambda soporta el manejo de listas de elementos. La sintaxis, el sistema de tipos y las reglas de tipado son los siguientes:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M ::= \dots \;|\; nil_\sigma \;|\; M:N \;|\; \textrm{case}\ M\ \textrm{of}\ \{nil \rightarrow P \;|\; x:y \rightarrow Q\}}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \sigma ::= \dots \;|\; [\sigma]}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{}{\Gamma \triangleright nil_\sigma : [\sigma]}}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\Gamma \triangleright M:\sigma \;\;\; \Gamma \triangleright N:[\sigma]}{\Gamma \triangleright M:N : [\sigma]}}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \frac{\Gamma \triangleright M:[\sigma] \;\;\; \Gamma \triangleright P:\tau \;\;\; \Gamma\cup\{x:\sigma,y:[\sigma]\} \triangleright Q:\tau}{\Gamma \triangleright\textrm{case}\ M\ \textrm{of}\ \{nil \rightarrow P \;|\; x:y \rightarrow Q\}:\tau}}

Se pide modificar el algoritmo de inferencia de tipos visto en clase para soportar el tipado del obser vador case y el constructor Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle nil_\sigma} . Suponer que el algoritmo ya esta correctamente extendido para el constructor M:N . Tener en cuenta que el algoritmo recibe como entrada una expresion sin anotaciones de tipos y debe devolver un juicio de tipado. Por ejemplo, al recibir nil debe devolver Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \emptyset \triangleright nil_s : [s]} , con s una variable de tipo.

Respuesta

Definimos:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbb{W}(nil) =_{def} \emptyset \triangleright nil_s:[s]}

Sean:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbb{W}(M) = \Gamma_1 \triangleright M':\alpha}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbb{W}(P) = \Gamma_2 \triangleright P':\beta}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbb{W}(Q) = \Gamma_3 \triangleright Q':\gamma}

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S = MGU\{\beta = \gamma\}\cup\{\alpha=[\tau]\}\cup C_1 \cup C_2 \cup C_3 \cup C_4}

donde

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle C_1 = \{\sigma_1=\sigma_2 \;|\; v:\sigma_1 \in \Gamma_i \;\wedge\; v:\sigma_2 \in \Gamma_j, 1 \leq i,j \leq 3, v \neq x, v \neq y\}}

siendo "v" una variable cualquiera de los conjuntos y "x" e "y" fijas.

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle C_2 = \{\sigma_1=\sigma_2 \;|\; x:\sigma_1 \in \Gamma_i \;\wedge\; x:\sigma_2 \in \Gamma_j\ \lor\ y:\sigma_1 \in \Gamma_i \;\wedge\; y:\sigma_2 \in \Gamma_j, 1 \leq i,j \leq 2\}}

siendo "x" e "y" fijas.

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle C_3 = \{\tau = \sigma \;|\; x:\sigma \in \Gamma_3\}}

siendo "x" fija.

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle C_4 = \{[\tau] = \sigma \;|\; y:\sigma \in \Gamma_3\}}

siendo "y" fija.

Entonces:

Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \mathbb{W}(\textrm{case}\ M\ \textrm{of}\ \{nil \rightarrow P \;|\; x:y \rightarrow Q\}) =_{def} } Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S\Gamma_1 \cup S\Gamma_2 \cup S(\Gamma_3 - \{x,y\}) \triangleright S(\textrm{case}\ M'\ \textrm{of}\ \{nil \rightarrow P' \;|\; x:y \rightarrow Q'\}):S\gamma}