Tarea 3

Esta tarea se distribuye con dos ficheros start.rkt y tests.rkt base-tarea3. Considere las definiciones del archivo start.rkt y escriba sus funciones en él. Escriba sus tests en el archivo tests.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación! Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

Polimorfismo Ad-Hoc

El polimorfismo paramétrico permite definir funciones que actúan igual sobre datos de distintos tipos. Por ejemplo, la función length hace lo mismo sea cual sea el tipo de los elementos de la lista.

Una forma complementaria de polimorfismo es el polimorfismo llamado “ad-hoc”. Este polimorfismo permite definir distintas versiones de una función (llamada método), donde el tipo de los argumentos influye sobre qué versión se ejecuta realmente. Por ejemplo, en Haskell, uno define una clase de tipo (type class), como Show:

class Show a where
   show :: a -> String

La definición de la clase especifica que el método show, dado un elemento de tipo a, retorna una String. Una definición de clase puede incluir varios métodos.

Luego, uno específica la implementación de una clase para ciertos tipos de datos a través de instancias, por ejemplo:

instance Show Expr where
   show (Id x) = "id(" ++ x ++ ")"
   show (Add e1 e2) = "add(" ++ show e1 ++ ", " ++ show e2 ++ ")"
 
instance Show (a -> b) where
   show x = "<procedure>"

Clases de predicados

En esta tarea, vamos a explorar una alternativa a las clases de tipos de Haskell, para un lenguaje dinámico.

La idea sigue siendo la misma: poder tener distintas implementaciones de una misma función (método). Pero en vez de elegir estáticamente en base al tipo estático de un argumento, vamos a basarnos en predicados evaluados dinámicamente. Vamos a tomar como base el lenguaje MiniScheme, sin tipos estáticos. El objetivo de la tarea es extender el lenguaje con la definición de clases de predicados, y sus instancias respectivas. Esto significa que extendemos la categoría de definiciones de MiniScheme:

‹def› ::= ‹id-def›
        | ‹class-def›
        | ‹instance-def›

La sintáxis para definir clases es la siguiente:

‹class-def› ::= (define-class ‹id› ‹id›+)

Por ejemplo, uno puede definir la clase Show, con su único método show:

(define-class Show show)

La sintáxis para definir instancias de clases es la siguiente:

‹instance-def› ::= (define-instance ‹id› ‹expr› [‹id›‹expr›]+)

Después del nombre de la clase a extender, viene una expresión cuyo valor debe ser un predicado (ie. una función de un argumento que retorna un booleano). Este predicado determina cuando la instancia es activa. Recibe como argumento, el primer parametro del metodo. Esto significa que si usamos predicados de tipo como number?, bool? y string?, obtenemos algo muy similar a las clases de tipos de Haskell (salvo que la resolución de metodos se hace dinámicamente):

>(local
    ((define-class Show show)
     (define-instance Show number?
       [show number->string])
     (define-instance Show string?
       [show (fun (x) x)])
     (define-instance Show bool?
       [show (fun (x) (if x "true" "false"))]))
  (string-append (show #t) " "
                 (show 1) " "
                 (show "hola")))
 
"true 1 hola"                

Otro ejemplo es definir una clase Size con el método size, y decidir que por ejemplo el tamaño de un número es el número mismo, y el tamaño de una string es su largo:

>(local
    ((define-class Size size)
     (define-instance Size number?
       [size (fun (x) x)])
     (define-instance Size string?
       [size string-length]))
  (+ (size 10) (size "hola")))
 
14

La ventaja de hacer esto dinámicamente, es que podemos usar cualquier predicado para decidir qué instancia es activa. Por ejemplo, podemos modificar la forma con la cual se muestran datos cuyo tamaño excede 100:

>(local
    ((define-instance Show (fun (v) (> (size v) 100)))
       [show (fun (x) "big data!!")])
  (string-append (show 200) (show "this is a very long string that should be longer than a hundred characters, so it should be a bit longer still")))
 
"big data!!big data!!"

(3.5) MiniScheme con clases de predicados

(0.5) Extienda la sintáxis de MiniScheme para definiciones de clases e instancias.

(1.0) Defina tipos de datos para clases e instancias, con las siguientes funciones:

  • (append-instance cls inst) que retorna una nueva clase cuya lista de instancias incluye inst.
  • (get-instance cname val env) para recuperar la instancia áctiva de la clase para el valor val (cname es el nombre de la clase, env es el ambiente en el cual cname está asociado a una clase).
  • (get-method inst name) que retorna la implementación del método name en la instancia inst.

(1.0) Extienda interp-def para procesar las definiciones de clases e instancias. La instancia de una clase debe implementar todos los métodos de la clase que esta instanciando.

(1.0) Extienda interp para procesar los métodos.

Indicaciones

Los métodos son entidades de primera clase. Por ejemplo:

 (run '(local ((define-class Show show)
               (define-instance Show number?
                 [show number->string]))
         ((fun (x) (x 4)) show)))
4  

Para entender el alcance de las clases y sus métodos, considere el siguiente ejemplo:

 > (run '(local ((define-class Size size)
                 (define-instance Size number?
                    [size (fun (x) x)]))
           (+ (size 5) 
              (local ((define size (fun (x) 1)))
                        (size 5)))))
6

Esto sugiere que los métodos viven en el ambiente. Sin embargo, los métodos no están directamente en el ambiente. Lo que está directamente en el ambiente, son las clases. Una clase tiene asociada sus métodos, y la posición en el ambiente determina la visibilidad de sus métodos. En el caso anterior, para la primera llamada a (size 5), en el ambiente se encuentra que hay una clase, Size, que tiene un método con el nombre buscado. Se aplica entonces este método (buscándolo de la primera instancia activa). En la segunda llamada a (size 5), la redefinición de size en el ambiente tiene precedencia sobre la clase Size, y por ende se usa dicha definición.

En conclusión, hay un único ambiente, en el cual conviven valores normales (funciones, números, strings, etc.) y clases, que sirven de representantes de sus métodos. Noten que en este lenguaje las clases no son de primera clase. Por ejemplo, no se pueden pasar clases como argumento de una función:

   (run '(local
    ((define-class Show show)
     (define-instance Show number?
       [show number->string]))
    ((fun (x) x) Show)))
"error: free identifier Show"    

Es decir, el nombre de la clase no es relevante al momento de buscar algo en el ambiente.

Las instancias viven exclusivamente dentro de las clases. Aplicar un método implica buscar la primera instancia de la clase que es activa (considerando el primer argumento de la aplicación). Note que por la forma en que se busca la implementación de un método, si una instancia implementa un método que no esta en la clase, entonces ese método no será accesible.

Asegúrese que los distintos ejemplos del enunciado funcionen como esperado, y entregue una batería de tests completa.

En particular, asegúrese que el scope de las instancias es local a un bloque local, lo que permite sobre-escribir una instancia localmente:

>(local ((define-class C foo bar)
         (define-instance C number?
           [foo (fun (x) (+ x 1))]
           [bar (fun (x) (- x 1))]))
  (+ (foo 3)
     (bar 4)
     (local ((define-instance C number?
               [foo (fun (x) (* x 2))]
               [bar (fun (x) (- x 2))]))
       (+ (foo 3)
          (bar 4)))
     (foo 3)))
 
19

(1.5pt) Implementaciones de métodos por defecto

Recuerden que una clase puede declarar varios métodos. En algunos casos, ciertos métodos pueden ser definidos en función de los demás métodos de la misma clase. Por ejemplo, en la clase Comp, el método greater? se puede definir directamente en función de smaller? y same?:

(local ((define-class Comp 
           same? 
           smaller?
           [greater? (fun (a b) (and (not (smaller? a b))
                                     (not (same? a b))))])
        ...

Así, las instancias de Comp no necesitan volver a implementar greater?:

        ...
        (define-instance Comp number?
          [same? equal?]
          [smaller? <])
 
        (define-instance Comp string?
          [same? equal?]
          [smaller? string<?]))
 
  (and (greater? "hola" "Hola")
       (same? "hola" "hola")
       (greater? 10 2)))
#t

Obviamente, si una instancia redefine greater?, dicha re-definición tiene precedencia sobre la implementación por defecto.

Extienda su lenguaje para soportar la definición de implementación por defecto de los métodos.

(1.0pt) Software adaptable al contexto

Las clases de predicados pueden ser usadas para hacer software adaptable a su contexto de ejecución. Por ejemplo, considere una clase Server con métodos service1 y service2:

(define-class Server service1 service2)
(define-instance Server (fun (x) #t)
  [service1 (fun (x) "serv1: full quality")]
  [service2 (fun (x) "serv2: ok")])
...

Cuando el servidor ejecuta en un contexto inseguro, la calidad del service1 se degrada, y se prohibe service2:

(define-instance Server (fun (x) (untrusted-ctx?))
  [service1 (fun (x) "serv1: low quality")]
  [service2 (fun (x) (error "serv2: denied"))])

Para esto, necesitamos extender el lenguaje con una forma de identificar computación insegura. Por ejemplo:

(define g (fun (x) (untrusted (f1 x))))

cuando aplicamos g, se activa el modo inseguro para la extensión dinámica de la evaluación de (f1 x) (es decir, hasta que (f1 x) retorne, se considera que estamos en un contexto inseguro).

La forma más conveniente de implementar esto es usando una variable dinámica, es decir, con alcance dinámico. Una variable dinámica en Racket se llama un parameter. Usando un parameter, extienda el lenguaje con untrusted y untrusted-ctx?. Notarán que no se requiere modificar mucho el interprete.

Para aprender a usar variables dinámicas en Racket, refierase a la documentación.