Final 27/12/2007 (Paradigmas)

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

Ejercicio 1[editar]

La evaluación lazy consiste en garantizar que: ningún argumento de función es evaluado más de una vez y que no se duplican expresiones sin evaluar. Una formalización de esta semántica (en big-step) es la siguiente, donde los términos están dados por la gramática:

Estos son los términos usuales, salvo por el caso de la aplicación. Observar que los argumentos siempre son variables. Sin embargo, esto no nos hace perder generalidad dado que un término de la forma siempre puede escribirse como .

El juicio debe leerse, "la expresión en el entorno evalúa al resultado y entorno ". Los valores son las abstracciones. Los entornos son funciones que mapean variables en expresiones.

Final27.12.07.plp.png

a) Dar las reglas de semántica operacional small-step.

b) Implementar esta semántica como una función smallStep. Puede asumir:

  • la existencia de subst :: Term -> Variable -> Term -> Term
  • Stack es un TAD con funciones preexistentes para manipular pilas (ej. push, pop, top, etc).
  • Env es un TAD con funciones preexistentes para manipular entornos (ej. updateEnv, lookupEnv)

Ejercicio 2[editar]

Considere las siguientes aseveraciones de la clásica formulación de la parado- ja del barbero:

  • Todo barbero afeita a aquellos que no se afeitan a si mismos.
  • Ningun barbero afeita a aquellos que se afeitan a si mismos.

a) Codificarlas en terminos de formulas de primer orden, una fórmula por aseveración y asumiendo que b(X) es el predicado que indica que X es barbero y s(X,Y) que indica que X afeita a Y.

b) Utilizando resolución general, mostrar que como consecuencia de las aseveraciones no puede existir tal barbero.

Respuestas

Formulas:



Normalizacion:











Resolucion:

1. Regla
2. Regla
3. Goal negado
4. De 1 y 2:
5. De 3 y 4:


Ejercicio 3[editar]

Considerar la siguiente extension de lambda calculo tipado con excepciones. La expresion raise M evalua M a un numero natural y genera una excepcion con ese numero como parametro. El objetivo de ese numero es que el manejador lo utilice como dato para poder tratar ese error. La otra expresion que se agrega es try M with N. La semantica de esta expresion es que primero se evalua M, si genera una excepcion se pasa el control al manejador N, si no genera una excepcion se retorna el valor.

Observar que el conjunto de valores no se modifica dado que expresiones de la forma raise V no son considerados resultados validos de una computacion. En consecuencia, ahora una expresion puede arrojar un valor o una excepcion sin manejar.

Para las nuevas expresiones dar la semantica operacional small-step y las reglas de tipado.

Respuesta

Semantica operacional[editar]

Raise




Try with






Aplicacion




If then else



Numericas




Tipado[editar]


Ejercicio 4[editar]

Modelar las clases Persona, Estudiante y Docente en lambda calculo. Toda persona tiene una edad, un metodo setEdad y un metodo getEdad. Ademas, toda persona tiene una cadena de presentacion (asumir que se dispone del tipo String) con valor: "Soy una persona". Tambien responde al mensaje talk retornando la cadena de presentacion. Todo estudiante tiene un numero de estudiante noDeEstudiante y todo docente tiene un numero de legajo noDeLegajo.

Tanto docentes como estudiantes responden al mensaje id retornando su respectivo numero. El mensaje talk debe retornar "Soy un estudiante" o "Soy un docente" segun sea Estudiante o Docente quien responda.

Respuesta[editar]

Representación[editar]

La representación de las clases es común al resto de las respuestas.

PersonaRep = {e: ref Nat}

DocenteRep = {e: ref Nat, nroEst: ref Nat}

EstudianteRep = {e: ref Nat, nroLeg: ref Nat}

Self con Source[editar]

Clases usando la version de representacion de self con source. Se omite la clase docente por ser demasiado igual a estudiante, son libres de agregarla.

personaClass:: PersonaRep -> (Source Persona) -> Persona

personaClass = 
 \r: PersonaRep.
  \self: Source Persona.
   { getEdad = \_:Unit.!(r.x),
     setEdad = \i:Nat.(r.x) := i,
     talk = \_:Unit."Soy una persona" }

estudianteClass:: EstudianteRep -> (Source Estudiante) -> Estudiante

estudianteClass = 
 \r: EstudianteRep.
  \self: Source Estudiante.
   let super = personaClass r self
   { getEdad = super.getEdad,
     setEdad = super.setEdad,
     talk = \_:Unit."Soy un estudiante",
     id = \_:Unit.!(r.nroEst) }

Creador de personas

dummyPersona = {
 getEdad = \_: Unit.0,
 setEdad = \_: Nat.unit,
 talk = \_: Unit."nada"
}

newPersona = \_: Unit.
 let r = { e = ref 0 } in
 let inst = ref dummyPersona in
 (inst := PersonaClass r inst; !inst) 

Creador de estudiante

dummyEstudiante = {
 getEdad = \_: Unit.0,
 setEdad = \_: Nat.unit,
 talk = \_: Unit."nada",
 id = \_: Unit.0
}

newEstudiante = \_: Unit.
 let r = { e = ref 0, nroEst = ref 0 } in
 let inst = ref dummyEstudiante in
 (inst := EstudianteClass r inst; !inst) 

Self con fix[editar]

Lo mismo de arriba, pero usando fix en lugar de source para la referencia a self.

personaClass:: PersonaRep -> (Unit -> Persona) -> (Unit -> Persona)

personaClass = 
 \r: PersonaRep.
  \self: Unit -> Persona.
   \_:Unit.
    { getEdad = \_:Unit.!(r.x),
      setEdad = \i:Nat.(r.x) := i,
      talk = \_:Unit."Soy una persona" }

estudianteClass:: EstudianteRep -> (Unit -> Estudiante) -> (Unit -> Estudiante)

estudianteClass = 
 \r: EstudianteRep.
  \self: Unit -> Estudiante.
   \_:Unit.
    let super = personaClass r self unit in
     { getEdad = super.getEdad,
       setEdad = super.setEdad,
       talk = \_:Unit."Soy un estudiante",
       id = \_:Unit.!(r.nroEst) }

Creador de personas

newPersona = \_: Unit.
 let r = { e = ref 0 } in
 fix (PersonaClass r) unit;

Creador de estudiantes

newEstudiante = \_: Unit.
 let r = { e = ref 0, nroEst = ref 0 } in
 fix (EstudianteClass r) unit;

Otra posibilidad hubiese sido guardar la cadena de presentacion como un field mas cuyo valor se seteara en el constructor; o que en lugar de ser una referencia sea un String constante.