Primer Parcial 1er Cuat 2007 (Paradigmas)

Ejercicio 1: Programación funcional

Durante todo este ejercicio no se puede usar recursion explicita, a menos que se especifique explicitamente lo contrario. Para hacer un item pueden utilizarse como existentes las solucio- nes a todos los items anteriores, independientemente de si fueron resueltos correctamente o no.

Consideremos la siguiente representacion de intervalos de enteros:

data LimitVal = MenosInf | MasInf | Cte Int
type Inter = (LimitVal,LimitVal) 

que representa el conjunto de todos los enteros que estan entre la primer coordenada del par y la segunda, inclusive en los casos no degenerados. Si la primer coordenada es mayor a la segunda, se considerara el intervalo como vacio.

Ejercicio A

Escribir una funcion compare que dados dos LimitVal, devuelva una de las constantes LT, GT o EQ (todas del tipo Ordering) segun el primer parametro sea menor, mayor o igual que el segundo, respectivamente.

compare :: LimitVal → LimitVal → Ordering 

A partir de aqui se puede tomar LimitVal como perteneciente a las clases Eq y Ord, por lo cual tiene bien definidos los operadores <, <=, ==, >, >= y /= y todas las operaciones que requieren Eq u Ord son utilizables.

Respuesta

compare MenosInf MenosInf = EQ
compare MasInf MasInf = EQ
compare (Cte a) (Cte b) = compare a b
compare MenosInf _ = LT
compare MasInf _ = GT
compare _ MenosInf = GT
compare _ MasInf = LT

Ejercicio B

Escribir las funciones empty, que devuelve un intervalo vacio, isEmpty que determina si un intervalo es vacio e incl que dice si el primer parametro esta enteramente incluido (como conjunto) en el segundo.

empty :: Inter 
isEmpty :: Inter → Bool 
incl :: Inter → Inter → Bool 

Nota: Cuidar que incl funcione bien para todos los intervalos considerados vacios.

Respuesta

empty = (MasInf,MenosInf)
isEmpty (a,b) = (a==MasInf) | | (b==MenosInf) | | (a>b)
incl (a,b) (c,d) = (isEmpty (a,b)) | | ((a>=c) && (b<=d))

Ejercicio C

Escribir la funcion compress que dada una lista estrictamente ascendiente (sin repetidos) de enteros devuelve su respresentacion como union de la minima cantidad posible de intervalos. Se debe devolver una lista con dichos intervalos.

compress :: [Int] → [Inter] 

Ejemplo:

compress [-1,0,1,2,3,5,7,8,9,11] → [(Cte (-1),Cte 3),(Cte 5,Cte 5),(Cte 7,Cte 9),(Cte 11,Cte 11)] 

Respuesta

compress = foldr insert []
where insert e r =
if (length r > 0 && value (fst (head r)) == e+1) then
(Cte e,snd (head r)):(tail r)
else
(Cte e,Cte e):r

Ejercicio D

¿Funciona la funcion anterior asi como esta con listas infinitas? (es decir, ¿va devolviendo los intervalos a medida que los va reconociendo terminados?) ¿Seria posible hacer una que funcione? Si la respuesta es si, comentar como, si es no, justificar informalmente por que.

Respuesta

No funciona asi como esta, pero si es posible hacer una.

compress [] = []
compress [x] = [(Cte x,Cte x)]
compress (x:y:xs) = if (x<y-1) then ((Cte x,Cte x):(compress (y:xs)))
else (insert x (compress y:xs))

donde insert es la misma funcion de la solucion original.

Ejercicio E

Escribir la funcion expand que, dado un intervalo, devuelve el conjunto equivalente por extension como una lista (eventualmente infinita) de enteros. El orden de la lista no importa, pero se debe asegurar que todo miembro del conjunto aparece exactamente una vez.

Respuesta

expand (Cte a, Cte b) = [a..b]
expand (MenosInf,Cte a) = map (λx-> (-x)) [-a..]
expand (Cte a,MasInf) = [a..]
expand (MenosInf,MasInf) = 0:[x*s | x<-[1..],s<-[-1,1]]
expand _ = []

Ejercicio F

Escribir una funcion que dado un conjunto no vacio de intervalos por extension, devuelve la interseccion de todos ellos.

inters :: [Inter] → Inter

Ejemplo:

inters [(MenosInf,Cte 5),(Cte (-3),Cte 9),(Cte 0,MasInf)] → (Cte 0, Cte 5) 

Respuesta

inters = foldr1 inter2
where inter2 a b = (max (fst a) (fst b),min (snd a) (snd b))

Ejercicio G

Dado el tipo de los arboles binarios y un esquema de recursion (fold) para hacer funciones sobre ellos, escribir una funci´on que verifique si un arbol binario de inter- valos cumple con el invariante de heap, es decir, el intervalo de un nodo contiene a todos los intervalos de sus descendientes. El nodo raiz, por lo tanto, debe contener a todos los intervalos del arbol.

data ArbolBin a = Nil | Bin (ArbolBin a) a (ArbolBin a) 

foldBin :: (a → b → b → b) → b → (ArbolBin a) → b 
foldBin _ c Nil = c 
foldBin f c (Bin i a d) = f a (foldBin f c i) (foldBin f c d) 
esHeap :: (ArbolBin Inter) → Bool 

Respuesta

esHeap = snd.(foldBin heapInt (empty,True))
where heapInt h (i,b1) (d,b2) = (h,b1 && b2 && (incl i h) && (incl d h))

Ejercicio H

Se desea modelar expresiones aritmeticas de operaciones sobre intervalos, pero aun no se ha definido que funciones se van a utilizar, por lo que se tiene un tipo que permite modelar operaciones unarias y binarias cualesquiera. Este tipo representa las constantes mediante el constructor Const y las operaciones mediante los constructores Op1 y Op2 (para unarias y binarias respectivamente) que se acompanan de una funcion para indicar su comportamiento (aparte de las expresiones que toma como parametros). Se pide, entonces, escribir el esquema de recursion (fold) para este tipo. Para este ejercicio se puede, por supuesto, usar recursion explicita.

data Expr = Op1 (Inter → Inter) Expr | Op2 (Inter → Inter → Inter) Expr Expr | Const Inter 
foldExpr :: ((Inter → Inter) → b → b) → ((Inter → Inter → Inter) → b → b → b) → (Inter → b) → Expr → b 

Respuesta

foldExpr f1 f2 c (Const a) = c a
foldExpr f1 f2 c (Op1 f e) = f1 f (foldExpr f1 f2 c e)
foldExpr f1 f2 c (Op2 f e1 e2) = f2 f (foldExpr f1 f2 c e1) (foldExpr f1 f2 c e2)

Ejercicio I

Usando el esquema del punto anterior, sin recursion explicita ni pattern matching, escribir la funcion eval que dada una expresi´on devuelve el resultado de evaluarla.

eval :: Expr → Inter 

Respuesta

eval = foldExpr id id id

Ejercicio 2: Lambda cálculo tipado

Se cuenta con un lengua je de lambda calculo tipado extendido para soportar naturales (se tienen los terminos 0, pred(M), succ(M) e isZero(M) donde las constantes naturales notadas con n abrevian $succ^{n}(0)$ como fue visto en la teorica). Ejemplos: 0 y 2 son las constantes que representan el 0 y el 2 respectivamente. Se pueden asumir las reglas de tipado y semantica correctas para los enteros como fueron dados.

El objetivo del ejercicio es extender este lenguaje para soportar una estructura switch que sea el equivalente a if pero para naturales. La sintaxis sera similar a la que usan C y C++ para el switch. La sintaxis del lengua je, entonces, sera la siguiente:

$M::=...\;|\;switch(M)\{{\textrm {case\ }}n_{1}:N_{1}\;{\textrm {case\ }}n_{2}:N_{2}...{\textrm {case\ }}n_{k}:N_{k}\}$

Aquı los $n_{i}$ representan numeros naturales y k es un entero positivo. La idea del comportamiento del switch es que primero evalue su condicion (lo que esta entre parentesis) y luego el resultado de toda la expresion se decide seguun el case que matchee el valor al que se evaluo la expresion (parecido al comportamiento del if.then.else). Esta prohi- bido incluir dos case con igual constante y tambien no incluir ninguno (esto no se asume, sino que se debe forzar con las reglas que correspondan). Si ningun case matchea el valor evaluado, la expresion debe quedar indefinida.

Ejercicio A

Introducir las reglas de tipado para la extension propuesta.

Respuesta

No se bien como restringir los casos que piden, se me ocurrió esto:

${\frac {\Gamma \triangleright n_{i}:Int\;\;\;\Gamma \triangleright N_{i}:\sigma \;\;\;\Gamma \triangleright M:\alpha }{\Gamma \triangleright {\textrm {switch(M)}}\{{\textrm {case\ }}n_{1}:N_{1}\;...\;{\textrm {case\ }}n_{k}:N_{k}\}:\alpha \rightarrow \sigma }}$

para $k>1,i\neq j\Rightarrow n_{i}\neq n_{j}$

Ejercicio B

Indicar formalmente como se modifica el conjunto de valores.

Respuesta

Creo que funciona como el lambda:

$V::=...\;|\;{\textrm {switch(M)\ }}\{...\}$

Ejercicio C

Dar la semantica operacional de a un paso para la extension propuesta.

Respuesta

${\frac {M_{1}\rightarrow M_{1}'}{{\textrm {switch}}(M_{1})\{...\}\rightarrow {\textrm {switch}}(M_{1}')\{...\}}}(E-switch_{g})$

${\frac {M_{2}\rightarrow M_{2}'}{{\textrm {switch}}(V)\{{\textrm {case\ }}V:M_{2},...\}\rightarrow {\textrm {switch}}(V)\{{\textrm {case\ }}V:M_{2}',...\}}}(E-switch_{c})$

${\frac {}{{\textrm {switch}}(V_{1})\{{\textrm {case\ }}V_{1}:V_{2},...\}\rightarrow V_{2}}}(E-switch_{v})$

Ejercicio D

Decir si con las reglas introducidas existe un termino cerrado (sin variables libres) que este en forma normal y no sea un valor. Si lo hay, mostrar un ejemplo, y si no, justificar informalmente por que.

Respuesta

Creo que no hay porque todo switch introducido es un valor (por como definí los valores).

Para mi este no es valor: switch(2){case 1 : true}

Ejercicio E

Modificar la sintaxis, las reglas de tipado y de semantica operacional rea- lizadas para que se pueda incluir tambien opcionalmente un label def ault : que debe aparecer una sola vez al final de los case y se utiliza para dar valor a toda la expresion en caso de que ningun case matchee. Se pueden reutilizar cosas introducidas en los items anteriores, pero debe especificarse exactamente que reglas se mantienen (si alguna regla debe ser modificada aunque sea levemente, se ruega reescribirla entera a fin de no generar problemas de interpretacion al corregir).

Ejercicio F

Escribir isZero en funcion de la extension realizada en el punto anterior.

Respuesta

isZero x = switch(x) { case 0: true, default: false }

Ejercicio 3: Inferencia de tipos

a) λx. λy. (x y) (λz. x)
No tipa.

b) λx. λy. λz. x (y z)
(b -> c) -> (a -> b) -> a -> c
Toma dos funciones y devuelve su composicion.

c) λx. λy. (x y) (x y)
No tipa.

d) W(caseNat U of 0 -> V ; Succ(x) -> W) =def
SΓ1 U SΓ2 U SΓ3 |> S(caseNat M of 0 -> N ; Succ(x) -> O) : Sw donde
W(U) = Γ1 |> M : s
W(V) = Γ2 |> N : t
W(W) = Γ'3 |> O : v
Si x : p E Γ'3 entonces Γ3 = Γ'3 - {x : p},H = {p = Nat} sino Γ3 = Γ'3,H = Ø
S = MGU(H U {w = t, t = v, s = Nat} U {p1 = p2 | y : p1 E Γi, y : p2 E Γj , i <> j}