Final 28/09/2020 (Paradigmas)

Final multiple choice que se tomó a través de un cuestionario en el Campus Virtual. Tenías un límite de tiempo de 1.30hs y era a libro abierto. Las respuestas incorrectas restaban 1, las no respondidas sumaban 0 y las correctas sumaban 1. En los casos donde había más de una opción posible, se tomaba algún número intermedio. Se aprobaba con un 60%, para luego pasar a una instancia oral de diez minutos que consistía en alguna pregunta de objetos y repasar las preguntas mal respondidas.

1. Existe $M\in \lambda ^{b,n,fix}$ tal que $W(Erase(M))=\emptyset \vdash M':\sigma \rightarrow \rho$ y $\sigma \neq \rho$, pero $fix\ M$ tipa.

a) Verdadero

b) Falso

2. La fórmula $\{\{P(X,f(X))\},\{\lnot P(a,X)\}\}$ es insatisfactible.

a) Verdadero

b) Falso

3. Asumir que se cuenta con un programa en Haskell que define un tipo de dato recursivo paramétrico $D\ a$, un dato $unD::D\ Int$ y el esquema de recursión estructural para $D\ a$ cuyo tipo es:

$foldD::(a\rightarrow b\rightarrow b)\rightarrow D\ a\rightarrow b$

a) $foldD\ (+)\ unD$ está bien tipado y su evaluación termina independientemente de la definición de $unD$.

b) $foldD\ (+)\ unD$ no está bien tipado.

c) $foldD\ (+)\ unD$ está bien tipado, pero su evaluación termina independientemente de la definición de $unD$

4. Se propone extender $\lambda ^{b}$ con números enteros. Para ello, se extiende el lenguaje de tipos con $Int$ y se adopta como sintaxis de términos la misma que $\lambda ^{b,n}$. Las reglas de tipado son análogas a las reglas de $\lambda ^{b,n}$ (donde se usa el tipo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Int} en lugar de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Nat} ). Se extiende el conjunto de valores de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda^{b}} :

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V ::= \ ... \ | \ succ^{n}(0) \ | \ pred^{n}(0) }

donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle pred^{n}(0)} representa al entero negativo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle -n} .

Las reglas de reducción son todas las reglas de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda^{b, n}} menos (E-PredZero). Es decir, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle pred(0)} no reduce a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 0} .

Decir si el cálculo que se obtiene satisface progreso.

a) Sí

b) No

5. Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle P} un programa en Prolog que contiene una cláusula de definición Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A :- \ B_{1}, B_{2}, ..., B_{n}} . Si se cambia a la cláusula por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A :- \ !, B_{1}, B_{2}, ..., B_{n}} , entonces:

Seleccione una o más de una:

a) Ninguna de las restantes opciones.

b) El conjunto de soluciones no cambia para toda consulta ground.

c) El conjunto de soluciones no cambia para toda consulta no ground.

6. Sean $S_{0}$ y $S_{1}$ los resultados obtenidos de ejecutar dos veces el algoritmo de Unificación de Martelli-Montanari sobre un mismo conjunto de ecuaciones de unificación $C$. Se puede afirmar que:

a) $S_{i}$ es más general que $S_{1-i}$ para todo $i\in \{0,\ 1\}$.

b) $S_{0}=S_{1}$

c) Ninguna de las restantes opciones.

7. Considerando la noción de subtipado para registros vista en la materia (regla (S-Rcd)), el juicio de tipado

$\{f\ :\ Ref(Nat\rightarrow \{\})\}\vdash f:=\ \lambda x:Nat.\{l=x\}:Unit$

es derivable si la relación de subtipado para referencias se define de manera:

Seleccione una o más de una:

a) En ningún caso

b) Invariante

c) Contravariante

d) Covariante

8. Para todo programa $P$, el conjunto de soluciones para la consulta $not(G)$ coincide con el de las soluciones de $not(G),\ not(G)$

Seleccione una o más de una:

a) Si $G$ no es ground.

b) Ninguna de las restantes opciones.

c) Si $G$ es ground

9. Sea $P$ un conjunto de cláusulas de definición y $G$ un goal. El árbol SLD que explora Prolog

a) Ninguna de las restantes opciones.

b) Contiene todas las refutaciones SLD del conjunto $P\cup \{G\}$

c) Contiene sólo refutaciones lineales del conjunto $P\cup \{G\}$

d) Contiene todas las refutaciones lineales del conjunto $P\cup \{G\}$

Preguntas de objetos tomada en el oral:

1. Si habías visto Smalltalk, ¿en qué se parecen y diferencian block de la abstracción $\lambda$?
2. Si habías visto Cálculo Sigma, ¿cuál es la diferencia en la semántica operacional con Cálculo Lambda? (Hablar de small-step y big-step)