Edición de «Final 20/12/2007 (Paradigmas)»

{{Back|Paradigmas de Lenguajes de Programación}}

= Ejercicio 1 =

Considere la siguiente representacion de expresiones regulares:
 data RE = Const Char | WildCard | Plus RE | Seq RE RE | Union RE RE
Const c representa la letra c, Wildcard representa cualquier caracter, Plus re representa 1 o mas copias de re, Seq re1 re2 representa una cadena de la forma re1 seguido de una de la forma re2, Union re1 re2 representa una cadena de la forma re1 o re2.

a) Dar el esquema de recursion (fold) para este tipo de datos.

b) Definir la funcion match :: RE -> [Char] -> Answer que dada una expresion regular re y una lista de caracteres cs retorna Fail si la lista no corresponde al patron o Ok ds con ds un sufijo de cs tal que el prefijo determinado corresponde con el patron re.

 data Answer = Fail | Ok [Char]

Observaciones relevantes:
* El match de Const c y Wildcard respecto a la lista vacia debe retornar Ok [].
* Plus re debe consumir el maximo prefijo posible.
* En el caso de Union re1 re2, si existe un prefijo que hace match con re1 puede ignorarse re2.

c) Reescribir la funcion anterior usando el esquema de recursion.

'''Respuesta 1'''

'''a)'''
 
 data RE = Const Char | WildCard | Plus RE | Seq RE RE | Union RE RE
 
 foldRE :: (a -> a) -> (a -> a -> a) -> (a -> a -> a) -> (Char -> a) -> a -> RE -> a
 foldRE fplus fseq funion fconst fwild re = 
     case re of
         Plus r1 -> fplus (thisFold r1)
         Seq r1 r2 -> fseq (thisFold r1) (thisFold r2)
         Union r1 r2 -> funion (thisFold r1) (thisFold r2)
         Const c -> fconst c
         WildCard -> fwild
     where thisFold = foldRE fplus fseq funion fconst fwild


'''b)'''         
 data Answer = Fail | Ok [Char]
  		
 match :: RE -> [Char] -> Answer
 match = matchaux 0
 
 matchaux :: Int -> RE -> [Char] -> Answer
 
 matchaux reps re cs = case re of
 				
 				Plus r1 -> 
 					let ans = matchaux 0 r1 cs in
 						case ans of 
 							Fail -> if reps > 0 then (Ok cs) else Fail
 							Ok ms -> matchaux (reps+1) re ms
 							
 				Seq r1 r2 ->
 					let ans1 = matchaux reps r1 cs in
 						case ans1 of
 							Fail -> Fail
 							Ok ms -> matchaux reps r2 ms
 							
 				Union r1 r2 ->
 					let ans1 = matchaux reps r1 cs in
 						case ans1 of
 							Fail -> matchaux reps r2 cs
 							Ok ms -> Ok ms
 							
 				Const c ->
 					case cs of
 						[] -> Ok []
 						(x:xs) -> if x == c then (Ok xs) else Fail
 						
 				WildCard ->
 					case cs of
 						[] -> Ok []
 						(x:xs) -> Ok xs

'''Respuesta 2'''
 data RE = Const Char | WildCard | Plus RE | Seq RE RE | Union RE RE
 data Answer = Fail | Ok [Char] deriving Show
 
 -- observadores de Answer
 isOk :: Answer -> Bool
 isOk Fail = False
 isOk (Ok _) = True
 okStr (Ok str) = str


'''a)'''
 -- fold para expresiones regulares
 foldRE :: (a -> a) -> (a -> a -> a) -> (a -> a -> a) -> (Char -> a) -> a -> RE -> a
 foldRE fplus fseq funion fconst fwild re = 
     case re of
         Plus r1 -> fplus (rec r1)
         Seq r1 r2 -> fseq (rec r1) (rec r2)
         Union r1 r2 -> funion (rec r1) (rec r2)
         Const c -> fconst c
         WildCard -> fwild
     where rec = foldRE fplus fseq funion fconst fwild


'''b)'''
 -- funcion constante
 cf :: Char -> ([Char] -> Answer)
 cf _ [] = Ok []
 cf c (x:xs) = if (x == c) then (Ok xs) else Fail
 
 -- funcion wildcard
 wf :: [Char] -> Answer
 wf [] = Ok []
 wf (x:xs) = Ok xs
 
 -- funcion union
 uf :: ([Char] -> Answer) -> ([Char] -> Answer) -> ([Char] -> Answer)
 uf p1 p2 string = if (isOk resp1) then resp1 else
     (if (isOk resp2) then resp2 else Fail)
     where resp1 = p1 string
           resp2 = p2 string
 
 -- funcion sequencia
 sf :: ([Char] -> Answer) -> ([Char] -> Answer) -> ([Char] -> Answer)
 sf p1 p2 string = if (isOk resp1) then (p2 (okStr resp1)) else Fail
     where resp1 = p1 string
 
 -- funcion asterisco (usada por la funcion plus)
 -- acepta 0 o mas ocurrencias
 asterisk :: ([Char] -> Answer) -> ([Char] -> Answer)
 asterisk check [] = Ok []
 asterisk check string = if (isOk res) then (asterisk check (okStr res)) else (Ok string)
     where res = check string
 
 -- funcion plus
 pf :: ([Char] -> Answer) -> ([Char] -> Answer)
 pf check string = if (isOk res) then (asterisk check (okStr res)) else Fail
     where res = check string
 
 -- match
 match :: [Char] -> RE -> Answer
 match string re = (foldRE pf sf uf cf wf re) string
 
 -- prueba
 regexp1 = Union (Const 'a') (Const 'c')
 regexp2 = Plus regexp1
 regexp3 = Seq (Plus (Const 'F')) (Const 'c')
 regexp4 = Seq (Plus (Const 'Z')) (Plus regexp1)
 reAB = Seq (Const 'A') (Const 'B')
 regexp5 = Seq (Plus reAB) (Plus regexp1)
<br/>

= Ejercicio 2 =

Considerar la siguiente expresion:
 let doble = \f.\x.f(f(x))
     in (doble (\x:Nat.succ (succ x)) 1, doble (\x:Bool.x) true)

a) Mostrar que la inferencia de tipos falla para la expresion. Recordar que la regla de tipado de let es:

<math>\frac{\Gamma \triangleright N: \tau \; ; \; \Gamma ,x : \tau \triangleright M : \sigma }{\Gamma \triangleright let \; x = N \; in \; M : \sigma}</math>

'''Respuesta:'''

Efectivamente falla al tratar de unificar "doble" en ambas ramas de la tupla: la primera lo fuerza a ser de tipo (Nat -> Nat) -> Nat -> s; la segunda igual pero reemplazando Nat por Bool.

b) El problema es que nuestro algoritmo de inferencia no soporta polimorfismo. En la expresion hay dos usos de doble, cada uno con tipos diferentes. Una solucion posible es introducir polimorfismo let. La regla de tipado para let se modifica de la siguiente manera:

<math>\frac{\Gamma \triangleright N: \tau \; ; \; \Gamma \triangleright M \{ x / N \} : \sigma }{\Gamma \triangleright let \; x = N \; in \; M : \sigma}</math>

Observar que la primera condicion es simplemente para asegurar que N este bien
tipado (tener en cuenta que x puede no ocurrir en M). Extender el algoritmo de inferencia con esta nueva lectura de let.

'''Respuesta:'''

El algoritmo de inferencia se extiende de la siguiente manera:

<math>W(let \; x = U \; in \; V) = \Gamma \triangleright let \; x = N \; in \; M \; : \sigma</math>

suponiendo que:

<math>W(U) = \Gamma ' \triangleright N : \tau</math>
<br/><math>W(V \{ x / N \} ) = \Gamma \triangleright M : \sigma</math>

= Ejercicio 4 =

Consideremos la clase de puntos y puntos con color. El tipo para la representacion (i.e. el estado local o variables de instancia) y el tipo de los objetos instancia de esta clase son:

 PuntoRep = {x:Ref Nat, y:Ref Nat}
 Punto = {getx:Unit->Nat, gety:Unit->Nat,
         setx:Nat->Unit, sety:Nat->Unit,
         moveUp:Unit->Unit}

La clase se representa como una funcion, tal como se vio en clase:

 puntoClass =
  \r:PuntoRep.
   \self:Unit -> Punto.
    \_:Unit.
     {getx = \_:Unit.!(r.x),
      gety = \_:Unit.!(r.y),
      setx = \i:Nat.(r.x):=i,
      sety = \i:Nat.(r.y):=i,
      moveUp = \_:Unit.(r.x):=suc((self unit).getx unit)
     }

Por ejemplo, el siguiente codigo genera un punto con coordenadas x = 1 e y = 2, mueve el punto hacia arriba con moveUp y luego retorna el valor 2.

 let r={x=ref 1,y=ref 2}
  in let pto=fix (puntoClass r) unit
   in pto.moveUp unit;pto.getx unit

Se pide extender esa clase con una subclase puntoColorClass que le agrega color al punto (representado como un numero natural). El tipo para la representacion y el tipo de los objetos instancia de esta clase son:

 PuntoColorRep = {x:Ref Nat, y:Ref Nat, c:Ref Nat}
 PuntoColor = {getx:Unit->Nat, gety:Unit->Nat, getc:Unit->Nat,
               setx:Nat->Unit, sety:Nat->Unit, setc:Nat->Unit,
               moveUp:Unit->Unit}

Se pide definir la clase puntoColorClass donde el metodo moveUp debe, ademas de mover el punto reusando la implementacion de la clase punto sin color, cambiar el color (incrementandolo en uno).

'''Respuesta'''

Se setea super haciendo una llamada a la funcion de puntoClass, pasandole la representacion de puntoColor (que al ser un registro hereda de la representacion de punto), self como referencia a sí mismo, para que las llamadas a self invoquen correctamente los metodos override, y unit para obtener efectivamente el punto.

Si se omite el unit final super pasa a ser una funcion de unit en punto, lo que implicaria que cada vez que se lo quiera llamar hay que agregarle un unit, como sucede con self. Esto haria que la resolucion de super sea lazy ('''confirmar''').

 puntoColorClass =
  \r:PuntoColorRep.
   \self:Unit -> PuntoColor.
    \_:Unit.
     let super = puntoClass r self unit in
      {getx = super.getx,
       gety = super.gett,
       setx = super.setx,
       sety = super.sety,
       getc = \_:Unit.!(r.c),
       setc = \i:Nat.(r.c):=i,
       moveUp = \_:Unit.super.moveUp;(r.c):=suc((self unit).getc unit)
      }

[[Category:Finales]]