====== Tarea 1 ======

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

===== (2.0) Programación funcional =====

  - (0.5) Implemente la función ''%%(repeat lst k)%%'' que repite los elementos de una lista k veces usando ''%%foldr%%'', ''%%map%%'' y la función ''%%range%%'' vista en la Auxiliar 1. Ejemplo: <code scheme>
> (repeat '(a b c) 3)                       
'(a a a b b b c c c)
</code>
  - (0.7) Defina una función ''%%(groupby selector lst)%%'' que permita agrupar los elementos de una lista basado en un criterio de selección. Ejemplos: <code scheme>
> (groupby cdr 
           '(("Scorsese" . 72 ) 
             ("Tarantino" . 53)
             ("John" . 19)
             ("Peter" . 72)
             ("Robert" . 19)))                   
'((72 ("Scorsese" . 72) ("Peter" . 72))
  (53 ("Tarantino" . 53))
  (19 ("John" . 19) ("Robert" . 19)))

> (groupby (λ (x) (modulo (string->number x) 3))
           '("21" "5" "34" "5" "89" "47" "28"))                    
'((0 "21") (2 "5" "5" "89" "47") (1 "34" "28"))
</code>
  - (0.8) Utilizando la función ''%%(apply fun args)%%''  de Racket,  implemente la función ''%%(curry-n f)%%'' que dado una función ''f'' retorna su versión currificada. Para determinar la cantidad de parámetros que espera la función ''%%f%%'', utilice la función ''%%procedure-arity%%'' provista en Racket (puede asumir que la función ''%%f%%'' recibe un número fijo de parámetros). Ejemplos: <code scheme>
> (define f (curry-n (λ (x y z) (+ x y z))))                                                  
> (((f 2) 5) 20)
27

> (define g (curry-n (λ (x) (* x x))))
> (g 3)
9

> (define y (curry-n (λ () (* 20 5))))
> (y)
100
</code>
//Nota: obviamente, no pueden usar la función ''curry'' de Racket!//
===== (4.0) Lenguaje Imperativo =====

Considere un lenguaje imperativo en el cual un programa es una lista de instrucciones. Las instrucciones son:

  * ''%%{var id e}%%'': Define la variable global de nombre ''id'' y le asocia el valor de la expresion ''e''. Si la variable que se está intentando definir ya fue previamente definida por una instrucción ''var'', se debe arrojar el error "variable already defined".
  * ''%%{set id e}%%'': Reasigna la variable de nombre ''id'' con el valor de la expresión ''e''. Si se realiza una asignación a una variable que no haya sido previamente definida por una instrucción ''var'', se debe arrojar el error "free variable".
  * ''%%{while e exprs}%%'': Ejecuta ''exprs'' siempre y cuando el valor de la expresión ''e'' no sea cero.
  * ''%%{return e}%%'': Instrucción que detiene la ejecución y retorna el valor de la expresión ''e''. En todo programa la última expresión debe ser ''return'', en caso contrario se debe arrojar el error "no return expression found".

Considere que los programas tienen una memoria global mutable que es implementada con una tabla de hash donde cada ''id'' se asocia a un valor. Refierase al [[http://docs.racket-lang.org/reference|manual de Racket]] para obtener información acerca de cómo utilizar tablas de hash en Racket. 

A modo de ejemplo, considere los siguientes programas implementados en nuestro lenguaje imperativo:

<code scheme>
> (run '{{var X 10}
         {var Y {+ 5 X}}
         {return {+ X Y}}})
25

> (run '{{var X (+ 2 8)}
         {var Y 1}
         {var Z X}
         {while Z
           {{set Y {* Y Z}}
            {set Z {- Z 1}}}}
         {return Y}})
3628800
</code>
  - (0.5) Defina la gramática BNF del lenguaje, realizando una clara distinción entre programas (''Prog''), instrucciones (''Instr'') y expresiones (''Expr''). Considere las siguientes operaciones aritméticas: + - *.
  - (0.5) Defina (usando ''deftype'') las estructuras de datos necesarias para poder construir una representación de la sintaxis abstracta de un programa.
  - (0.5) Defina un parser para el lenguaje.
  - (1.0) Defina un interprete para el lenguaje, usando una tabla de hash global para manejar el estado de las variables. 
  - (0.5) Defina la función ''run :: Prog → Num'' que ejecuta un programa y retorna el valor de una expresión ''return'', o un error si corresponde.
  - (1.0) Para evitar errores de variables ya definidas y/o no definidas, defina una función ''var-check :: Prog → List[string]'' que analiza un programa (sin ejecutarlo!), y retorna una lista de los errores de variables presentes en el programa. Si el programa no contiene errores, retorna la lista vacía.
//Nota: recuerden que para definir una función que procesa una estructura compuesta, tienen que usar funciones auxiliares para los sub-componentes (en el contexto de la tarea: programas, instrucciones, expresiones).//