Primer Parcial 1er Cuat 2007 (Paradigmas)

Ejercicio 1: Programación funcional

a) 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

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

c) 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

d) 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.

e) 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 _ = []

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

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

h) 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)

i) 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).

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}