====== Tarea 4 ======
Esta tarea se distribuye con dos ficheros start.rkt y tests.rkt (mediante U-Cursos). 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.

En esta tarea se le provee el lenguaje MiniScheme+, que corresponde a un intérprete extendido con estructuras de primera clase y pattern matching((MiniScheme+ usa un ambiente mutable que permite definir funciones recursivas con ''%%define%%''.)). Además, MiniScheme+ incorpora el uso de primitivas((Para entender el concepto de funciones primitivas, vea http://pleiad.cl/teaching/primitivas.)). A continuación se presenta un breve tour de las características de MiniScheme+:
  -// Funciones de primera clase con argumentos múltiples//: las funciones y las expresiones ''%%with%%'' pueden tener 0 o más argumentos, por ejemplo: <code scheme>
> (run '{{fun {x y z} {+ x y z}} 1 2 3})
6
> (run '{with {{x 1} {y 2} {z 3}} {+ x y z}})
6
> (run '{with {} {{fun {} 42}}})
42
</code>
  - //Definiciones usando ''%%local%%'', ''%%define%%'' y ''%%datatype%%''//: la expresión ''%%local%%'' permite realizar definiciones de identificadores y de estructuras de datos, usando ''%%define%%'' y ''%%datatype%%'' respectivamente. Por ejemplo: <code scheme>
> (run '{local {{define x 1} 
                {define y 2}} 
           {+ x y}})
3
> (run '{local {{datatype List 
                  {Empty} 
                  {Cons a b}}}
          {List? {Empty}}})
#t
> (run '{local {{datatype List 
                  {Empty} 
                  {Cons a b}}}
           {match {Cons 1 {Cons 2 {Empty}}}
             {case {Cons a b} => a}}})
1
</code>
Observe que ''%%define%%'' y ''%%datatype%%'' sólo pueden usarse en la zona de declaraciones de una expresión ''local''. Al declarar una estructura, la implementación extiende el ambiente usado en el cuerpo de ''local'' con las funciones constructoras de cada variante; y con predicados para determinar si un valor corresponde a la estructura (en general, y para cada variante). Para más detalles, consulte la implementación y tests que le serán provistos.

===== Listas =====
(1.0) Con el objetivo de no tener que introducir la estructura de datos Lista en cada ejemplo extenderemos el lenguaje para que la soporte de manera predeterminda:
  - Extienda la función ''run'' para que evalué la expresión en un ambiente donde se tiene la definición de ''Lista'' de los ejemplos anteriores. <code scheme>
> (run '{List? {Empty}})
#t
</code>
  - Implemente la función ''(make-list l)'' que dada una lista de enteros de Scheme retorna una expresión de MiniScheme+ que representa la lista dada, usando la definición del ''datatype List'' <code scheme> 
> (make-list (list 1 2 3 4))
'(Cons 1 (Cons 2 (Cons 3 (Cons 4 (Empty)))))
</code>
  - Extienda el lenguaje para soportar una sintaxis para crear listas de entero similar a la de Scheme <code scheme>
> (run '{match {list 1 2}
          {case {Cons h r} => h}
          {case _ => 2}})
1
> (run '{Cons? {list 1 2}})
#t
</code> Para hacer esta modificación no necesita modificar el intérprete
===== Evaluación Perezosa =====
MiniScheme+ usa call-by-value como semántica de aplicación de funciones. Sin embargo, es posible agregar evaluación usando call-by-need para casos específicos.
  - (1.0) Agregue el keyword ''lazy'' para indicar que el argumento de una función debe ser evaluado usando call-by-need. Además, ''lazy'' puede ser usado en la declaración de estructuras para determinar la semántica de las funciones constructoras. Asegúrese de obtener semántica call-by-need, y no call-by-name! Ejemplos: <code scheme>
> (run '{{fun {x  {lazy y}} x} 1 {/ 1 0}})
1
> (run '{{fun {x  y} x} 1 {/ 1 0}})
"/: division by zero"
> (run '{local {{datatype Foo {Lazy {lazy a }}}
                {define x  {Lazy {/ 1 0}}}}
          {Foo? x}})
#t
> (run '{local {{datatype Foo {Lazy {lazy a}}}
                {define x  {Lazy {/ 1 0}}}}
          {match x
            {case {Lazy a} => a}}})
"/: division by zero"
</code>
  - En Haskell vimos que gracias a la evaluación perezosa es posible construir listas infinitas. Un stream es una estructura infinita compuesta por una cabeza ''hd'' y una cola ''tl'', al igual que las listas. Un stream puede emular una lista infinita si se evita evaluar la cola del stream hasta que sea estrictamente necesario. Realice lo siguiente en MiniScheme+ extendido con el keyword ''lazy'':
    * (0.5) Defina una estructura ''Stream'' que evite evaluar su cola a menos que sea estrictamente necesario. <code scheme>
(def stream-data '{datatype Stream ...})
</code>
    * (0.5) Defina la función ''(make-stream hd tl)'' que construye un stream basado en la estructura anterior. Ejemplo: <code scheme>
(def make-stream '{define make-stream  {fun ...}})
; Stream infinito de 1s
(def ones '{define ones {make-stream 1 ones}}
</code>
===== Trabajando con Streams =====
//Nota: Todas las definiciones que se le piden a continuación deben realizarse en el lenguaje MiniScheme+ con las extensiones hasta este punto de la tarea.//

 Observe que para fines de presentación y de corrección, el intérprete define una conversión entre estructuras ''List'' de MiniScheme+ y listas de Racket.
  - (0.6) Defina las funciones ''stream-hd'' y ''stream-tl'' para obtener la cabeza y la cola de un stream. Por ejemplo: <code scheme>
(def stream-hd ...)
(def stream-tl ...)
> (run `{local {,stream-data ,make-stream ,stream-hd ,ones}
{stream-hd ones}})
1
> (run `{local {,stream-data ,make-stream
                             ,stream-hd ,stream-tl ,ones}
          {stream-hd {stream-tl ones}}})
1
</code>
Observe el uso de //quasi-quoting// para definir individualmente las funciones pedidas, así como el stream ones. Sus respuestas deben definirse como fragmentos de programa que luego serán compuestos de la forma que aquí se ilustra.
  - (0.6) Implemente la función ''(stream-take n stream)'' que retorna una lista con los primeros n elementos de stream. Ejemplo: <code scheme>
(def stream-take ...)
> (run `{local ,stream-lib
          {local {,ones ,stream-take}
            {stream-take 10 ones}}})
'(1 1 1 1 1 1 1 1 1 1)
</code>
Considere usar la siguiente definición de ''stream-lib'' en los próximos ejercicios para que no tenga que volver a definir todas las funciones para cada ejercicio: <code scheme>
(def stream-lib (list stream-data
                        make-stream
                        stream-hd
                        stream-tl
                        stream-take))
</code>
  - (0.6) Implemente la función ''stream-zipWith'' que funciona de manera análoga a ''zipWith'' para listas. Ejemplo: <code scheme>
(def stream-zipWith ...)

> (run `{local ,stream-lib
          {local {,ones ,stream-zipWith}
            {stream-take 10
                         {stream-zipWith
                          {fun {n m}
                               {+ n m}}
                          ones
                          ones}}}})
'(2 2 2 2 2 2 2 2 2 2)
</code>
  - (0.6) Implemente el stream fibs, de todos los números de Fibonacci. <code scheme>
(def fibs ...)

> (run `{local ,stream-lib
          {local {,stream-zipWith ,fibs}
            {stream-take 10 fibs}}})
'(1 1 2 3 5 8 13 21 34 55)
</code>
  - (0.6) Implemente el stream merge-sort, que dados dos Stream ordenados retorna un Stream con la mezcla ordenada <code scheme>
(def merge-sort ...)

> (run `{local ,stream-lib
               {local {,stream-take ,merge-sort ,fibs ,stream-zipWith}
                 {stream-take 10 {merge-sort fibs fibs}}}})
(1 1 1 1 2 2 3 3 5 5)
</code>