Table of Contents

Tarea 3 (Entrega: 1ro de julio de 2019)

Esta tarea se distribuye con un archivo zip ( base) que contiene 2 archivos: main.rkt y tests.rkt. Los archivos main.rkt y tests.rkt están incompletos, y en ellos tienen que implementar lo que se solicita en las preguntas siguientes.

Deben entregar via U-cursos un archivo .zip que contenga los archivos main.rkt y tests.rkt.

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101

¡Los tests, los contratos y las descripciones forman parte de su evaluación!

Resumen

El objetivo de la tarea es extender el lenguaje MiniScheme (implementado en el fichero main.rkt) con clases de predicados y métodos por defecto.

La tarea está dividida en 4 secciones, las cuales se describen a continuación:

- Polimorfismo Ad-Hoc: En esta sección se brinda una breve descripción del polimorfismo “ad-hoc”, característica presente en el lenguaje Haskell.

- Clases de predicados: En esta sección se explica en detalle una alternativa al polimorfismo “ad-hoc” presente en Haskell, pero para un lenguaje dinámico.

- MiniScheme con clases de predicados: El objetivo de esta sección es extender el lenguaje MiniScheme con clases de predicados. Para cumplir con este objetivo se le pide definir un conjunto de funcionalidades, las cuales tiene que comprender cómo utilizarlas para completar esa sección.

- Implementaciones de métodos por defecto: En esta sección vamos a agregar al lenguaje métodos por defecto, los cuales se definen en la declaración de las clases, y son utilizados o sobrescritos en sus instancias.

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 y recibe como argumento el primer parámetro del método. Esto significa que si usamos predicados de tipo como number?, bool? o string?, obtenemos algo muy similar a las clases de tipos de Haskell (salvo que la resolución de métodos se hace dinámicamente):

>(run '{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:

>(run '{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:

>{run '{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"}}]}
             {define-class Size size}
             {define-instance Size number?
               [size {fun {x} x}]}
             {define-instance Size string?
               [size string-length]}
             {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!!"

(4.0) MiniScheme con clases de predicados

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

(1.5) Defina tipos de datos necesarios para manipular clases, instancias y sus métodos. Defina además las siguientes funciones:

(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 está 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 1}}]}
              {define-instance Size bool?
                [size {fun {x} 1}]}}
        {+ {size {size #t}}
           {local {{define size {fun {x} 0}}}
             {size 5}}}})
2

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.

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

> (run '{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

Cuando no se encuentra una instancia activa se debe emitir el siguiente error:

> (run '{local {{define-class Size size}
              {define-instance Size number?
                [size {fun {x} {x}}]}}
        {size #t}})
"error: no existe instancia activa de la clase Size"        

(2.0pt) 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?:

>(run '{local {{define-class Comp 
                same? 
                smaller?
                [greater? {fun {a b} {and {not {smaller? a b}}
                                          {not {same? a b}}}}]} 
              {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

Así, las instancias de Comp no necesitan volver a implementar greater?. 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.