Segundo Parcial Especial 2do Cuat 2007 (Paradigmas)

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

Ejercicio 1: Programación Lógica[editar]

Implementar los siguientes predicados respetando la instanciacion pedida. No utilizar cut (!) ni predicados de alto orden (como setof). La unica excepcion es el not, que esta permitido.

Item A[editar]

Escribir el predicado perm(+Lista,-Perm) que dice si Perm tiene exactamente los elementos de Lista, en algun orden. No se deben devolver soluciones repetidas si la lista no tiene elementos repetidos.

Respuesta 1

perms([], []).
perms([X|Xs], Ps) :-
    perms(Xs, PXs),
    length(Xs, L),
    between(0, L, N),
    insert(X, PXs, N, Ps).

insert(X, Xs, 0, [X|Xs]).
insert(X, [X0|Xs], N, [X0|I]) :-
    N > 0,
    N1 is N-1,
    insert(X, Xs, N1, I).

Otra manera de implementar insert es:

insert(X, Xs, N, IXs) :-
    append(Head, Tail, Xs),
    length(Head, N),
    append(Head, [X|Tail], IXs).

Respuesta 2

perm(L, R) :-
    length(L, N),
    length(R, N),
    incluido(L, R),
    incluido(R, L).

incluido([], L) :- is_list(L).
incluido([X|XS], L) :- member(X, L), incluido(XS, L).

Item B[editar]

Si se permitiera usar predicados de alto orden, ¿como se podrıa evitar generar soluciones repetidas en el item anterior aun cuando la lista tuviera elementos repetidos?

Respuesta

setperms(X,P) :- setof(Y, perms(X,Y), Ps), member(P,Ps).

Item C[editar]

Escribir el predicado mismasRamas(+Arbol1,-Arbol2) que indica si el multiconjunto de ramas de ambos arboles binarios es igual. Los arboles se representaran como:

esArbol(nil).
esArbol(bin(I,_,D)):-esArbol(I),esArbol(D).
esRama([],nil).
esRama([X | Xs],bin(I,X,_)):-esRama(Xs,I).
esRama([X | Xs],bin(_,X,D)):-esRama(Xs,D).

La definicion de rama esta dada por el predicado esRama. No se deben devolver soluciones repetidas. Considerar usar el ıtem anterior.

Asumir dado el predicado agregarATodas(-Elemento,-Listas,-Resultado) que tiene exito si Listas es una lista de listas y Resultado es el resultado de agregar Elemento al comienzo de cada una de las listas. Notar que este predicado es reversible.

Item D[editar]

Escribir el predicado inorder(-Arbol,-Lista) que dice si la lista representa el recorrido inorder de los nodos del arbol, el cual consiste en recorrer primero el subarbol izquierdo, luego la raız y luego el subarbol derecho. Notar que inorder debe ser totalmente reversible, y recordar que append(-Ll,-Lr,-L) lo es.

Respuesta

inorder(nil,[]).
inorder(bin(I,X,D), L) :-
    append(LI, [X|LD], L),
    inorder(I, LI),
    inorder(D, LD).


Ejercicio 2: Resolución[editar]

Sean s una funcion unaria que representa el sucesor, N un predicado unario que representa ser natural y M un predicado binario que representa la relacion mayor o igual.

Dados los siguientes axiomas usuales:

  1. El sucesor de todo numero natural es un natural.
  2. El sucesor de x es mayor o igual que el sucesor de y si y solo si x es mayor o igual que y.
  3. Ningun natural es mayor o igual que su sucesor.

Item a[editar]

Escribir los axiomas como formulas de primer orden y pasarlas a forma clausal.
















Item b[editar]

Demostrar usando el metodo de resolucion general que no existe un maximo numero natural (o sea, un numero que sea mayor o igual que todo el resto).

En primer orden:
Negada:












De
Con
Agrego

De
Con
Agrego

De
Con
Agrego


Ejercicio 3: Herencia[editar]

Sea A una clase de smalltalk y B y C dos clases, ambas hijas de A. Sean a, b y c la cantidad de mensajes que entienden A, B y C respectivamente. Indicar para cada ıtem si es necesariamente verdadero, necesariamente falso o puede ser verdadero o falso segun el caso. De ser este ultimo caso, mostrar informalmente un ejemplo donde se haga verdadero y uno donde se haga falso.

Item A[editar]

a < b: Es verdadero sii B define algun metodo nuevo.

Item B[editar]

b <= c: Puede ser falso o verdadero, no hay relacion entre ellas. Es verdadero sii c define mas metodos nuevos que b.

Item C[editar]

a <= c: Siempre verdadero, una clase hija tiene por lo menos los mismos metodos que su padre.

Item D[editar]

super do; ejecuta el mismo codigo si se llama desde B o C: Siempre verdadero, el super hace un bind estatico a la clase padre (A en este caso), con lo que siempre ejecutara el mismo metodo.

Cabe destacar también que si en el mensaje "do" de la clase "A" se usa "self" para realizar alguna llamada el código ejecutado no sería el mismo.

Item E[editar]

(super yourself) do; ejecuta el mismo código si se llama desde B o C: Idem anterior, el mensaje yourself devuelve el objeto receptor, en este caso es estaticamente super.

En realidad, (super yourself) devuelve lo mismo siempre a menos que se redefina el mensaje yourself de la clase Object. Es decir que por lo general, (super yourself)do será equivalente a self do, y lo que haga esto dependerá de si B o C redefinieron este método.

Ejercicio 4: Colecciones[editar]

Item A[editar]

Extender la clase Collection para que soporte un mensaje select: selBlock where: whBlock groupBy: gbBlock having: hvBlock cuyos 4 parametros son bloques con la siguiente semantica:

  1. whBlock lleva un parametro y al ser evaluado en cada elemento contenido en la coleccion receptora devuelve un booleano. Aquellos elementos para los cuales el bloque devuelva falso deben ser ignorados por completo y el resto considerados en lo que sigue.
  2. gbBlock lleva un parametro que al ser evaluado en los elementos de la coleccion receptora devuelve un identificador de grupo. Todos los elementos que pasaron el where deben ser agrupados con los que tengan su mismo identificador. Cada grupo consistira en una coleccion del mismo tipo de la receptora del mensaje con los elementos originales agregados en el orden relativo en el que estaban.
  3. hvBlock lleva dos parametros y al ser evaluado en cada grupo (el primer parametro es el identificador del grupo y el segundo la coleccion con los elementos del grupo) devuelve un boolean que indica si el grupo se debe dar como resultado o no.
  4. selBlock lleva dos parametros y al ser evaluado en cada grupo no descartado devuelve un elemento que se debe agregar a la coleccion resultado. La coleccion resultado tambien es del mismo tipo que la receptora.

El orden del resultado no tiene importancia.

Ejemplo: sea oC la OrderedCollection con los elementos: (2 1 10 3 5 0 6 9 4 1)

oC select: [:c :x|x] where: [:x | x ∼=3] groupBy: [:x | x rem: 5] having: [:c :x | true] 

devuelve:

OrderedCollection (OrderedCollection (10 5 0) OrderedCollection (1 6 1) OrderedCollection (2) OrderedCollection (9 4)) 

Nota: se puede asumir que los identificadores de grupo pueden ser comparados entre ellos con =. Asumir que la coleccion acepta el mensa je add:.

Respuesta

select: sel where: wh groupBy: gb having: hv
    | filtrados grupos gpf res |
    filtrados := self select: wh.
    grupos := Dictionary new.
    filtrados do: [:e |
        |k|
        k := gb value: e.
        (grupos includesKey:k) ifTrue:[(grupos at:k) add: e]
        ifFalse:[
            |l| l:= self class new.
            l add: e.
            grupos at:k put:l.
        ].
    ].
    gpf := Dictionary new.
    grupos keysAndValuesDo: [:k :v | (hv value:k value:v) ifTrue:[gpf at:k put:v]].
    res := self class new.
    gpf keysAndValuesDo: [:k :v | res add:(sel value:k value:v)].
    ^res

Test Case

|oc| oc := OrderedCollection new. 
oc addAll: #(2 1 10 3 5 0 6 9 4 1).
oc select: [:k :v | v] where: [:e | e ~= 3] groupBy: [:e | e rem: 5] having: [:k :v | true].

Item B[editar]

Usando el item (a) extender con el mensaje sinRepetidos la clase Collection. Este mensa je no toma ningun parametro y devuelve una coleccion igual a la receptora pero sin elementos repetidos. El orden de los elementos del resultado no tiene importancia.

Respuesta

sinRepetidos
^self select: [:k :v | k] where: [:e | true] groupBy: [:e | e] having: [:k :v | true]

Item C[editar]

Usando el item (a) extender con el mensa je cantApariciones la clase Collection. Este mensaje toma una coleccion como parametro y devuelve una colecci´on del mismo tipo que la receptora con 2 elementos: la cantidad de elementos en comun con el parametro y la cantidad de elementos de la receptora que no aparecen en el parametro.

Respuesta

cantApariciones: col
^self select: [:k :v | v size] where: [:e | true] groupBy: [:e | col includes: e] having: [:k :v | true].


Ejercicio 5: Subtipado[editar]

En general los elementos de cierto conjunto pueden ser vistos tambien como una funcion constante que va hacia dicho conjunto. Por ejemplo, el numero 3 puede ser visto como el numero 3 o como la funcion constante que siempre devuelve 3. Para reflejar esto, agregaremos a los axiomas de subtipado el siguiente:

Encontrar en este nuevo contexto, la cantidad de tipos X que cumplen las siguientes expresiones, considerando la desigualdad estricta (o sea, X no es igual a ninguna de sus cotas) y las permutaciones de registros como el mismo tipo.

Item A[editar]

Respuesta

El primer problema que nos encontramos es el de poner los paréntesis en . Vemos que no puede ser ya que para que se cumpla la desigualdad que nos plantean deberia darse:

  1. (que se cumple)
  2. (que no se cumple, de hecho la nueva regla indica que la desigualdad es al revés)

Intentamos asociando , veamos que la desigualdad inicial se cumple:

  1. Si tratamos de usar la regla de la función nos quedaría que debe cumplirse que cosa que no es cierta por lo tanto la desigualdad no se cumple por ese lado.
  2. Si usamos la nueva regla obtenemos que y luego aplicando la regla de la función obtenemos que era lo que necesitábamos.

Ahora veamos los posibles candidatos para X:

  1. Aquellos válidos por las reglas originales del tipo función, o sea, de la forma
  2. Aquellos que usan la nueva regla, o sea, subtipos de la forma

Los tipos de la forma 1 tienen que cumplir , y que . Como Float no tiene supertipos se llega a que un tipo posible es .

Para los tipos de la forma 2 podemos ver que deben cumplir que usando la regla 2 llegamos a que T puede ser .

Con esto concluimos que X puede ser

Item B[editar]

Respuesta

La cantidad de tipos X posibles es infinita por lo siguiente:

Cualquier tipo de la forma es subtipo de y si además es supertipo de , entonces es supertipo de , siendo un X valido. Como con la regla nueva agregada hay infinitos supertipos de :

Nat->(Nat->Bool)
(Nat->Nat)->(Nat->Bool)
(cualquier tipo)->(Nat->Bool)
...

Entonces hay infinitos tipos que se pueden usar para obtener infinitos X válidos distintos.