Final 20/12/2007 (Paradigmas)

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)

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:

${\frac {\Gamma \triangleright N:\tau \;;\;\Gamma ,x:\tau \triangleright M:\sigma }{\Gamma \triangleright let\;x=N\;in\;M:\sigma }}$

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:

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

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:

$W(let\;x=U\;in\;V)=\Gamma \triangleright let\;x=N\;in\;M\;:\sigma$

suponiendo que:

$W(U)=\Gamma '\triangleright N:\tau$
$W(V\{x/U\})=\Gamma \triangleright M:\sigma$

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