sábado, marzo 29, 2008

En 100 años?

Hace poco leí un ensayo de Paul Graham llamado "The Hundred-Year Language" Me pareció muy interesante.

Una de las cosas que quisiera discutir es ésta:

I think that, like species, languages will form evolutionary trees, with dead-ends branching off all over. We can see this happening already. Cobol, for all its sometime popularity, does not seem to have any intellectual descendants. It is an evolutionary dead-end-- a Neanderthal language.

I predict a similar fate for Java. People sometimes send me mail saying, "How can you say that Java won't turn out to be a successful language? It's already a successful language." And I admit that it is, if you measure success by shelf space taken up by books on it (particularly individual books on it), or by the number of undergrads who believe they have to learn it to get a job. When I say Java won't turn out to be a successful language, I mean something more specific: that Java will turn out to be an evolutionary dead-end, like Cobol.


Porqué habría de ser Java un Dead-End Evolutivo? La respuesta es:

Java cambia muy lentamente!

No se trata de los problemas inherentes al boilerplate para pasar una función por parámetro. No se trata de que los namespaces sean incómodas carpetas ni tampoco que no haya inferencia de tipos.

Se trata de que estos problemas no se solucionan. Se toman años en aprobar una JSR, pero entonces?

Que pasará con Java en los próximos 100 años? Cuantos años nos aguardan, antes de que Java quede confinado a los cores de "las grandes compañías", que en algún momento pensaron que Cobol y RPG eran los mejores lenguajes?

Mas interesante aún! Cual será la sucesión de lenguajes de los próximos 100 años? Que nos espera después de Java?

Muchas preguntas, no?

Precisamente, otro artículo de Paul Graham (creo que es realmente una cita) da una buena herramienta de como pensar sobre la siguiente sucesión.

Empecemos a Especular!

Hay como dos lados, por uno creo que se dió un estilo de transición de la forma:

Arreglemos el "noun oriented thinking" del lenguaje de programación X

(Donde X es Java, C#)

Con C# ya medio se arreglo con la inclusión de lambdas (aunque con muchas limitantes) y en Java ahí está la propuesta. Los lenguajes que superen esta prueba tal vez continúen siendo ramas gruesas dentro de el árbol evolutivo.

Él otro lado tiene mucho que ver con los lenguajes dinámicos. Creo que el próximo lenguaje de entre toda esa familia (Groovy, Ruby) será uno que mejore el performance de estos. De hecho, los primeros esfuerzos se comienzan a observar con el montón de implementaciones para la CLR, DLR y la JVM.

Creo que la posibilidad de integración de DSL's jugará un papel importante. En el momento se que Ruby por ejemplo trata de acomodar su sintaxis para hacer mini-DSL's, muy al estilo de usar nombres de métodos dicientes y literales de la forma conveniente como en SmallTalk, pero le hacen falta capacidades reflexión sobre sus construcciones sintácticas. C# intenta hacer algo sobre esto, limitado a "expresion trees" sobre sus lambdas. F#, pese a estar lejos de ser un First Class Citizen en .Net tiene algunas posibilidades en este aspecto, pero hace falta una función Compile (como lo hay en los expresion Trees). No hablemos de Java, éste no posee nada de esto.

No se hasta donde nos pueda llevar la teoría de tipos, pero de algo estoy seguro. Creo que algunos lenguajes imperativos tendrán clases de tipos como Haskell y una buena inferencia que haga generalización automática. Construcciones para manejar paralelismo, etc...

Lo mas interesante de todo ésto es que todas estas ideas ya existen desde Lisp. Será que surge algo Realmente nuevo?

lunes, marzo 17, 2008

Nuevo Blog

Abrí un Blog para contar mis aventuras de Viaje:

El link está a la derecha y ésta es la dirección:

http://diegoechevagyok.blogspot.com/

martes, marzo 11, 2008

Tail Recursion y Continuations

Pues en el post anterior mostré como se puede traducir un código recursivo a uno iterativo por medio de optimización de recursión de Cola. Ésta técnica es muy importante en lenguajes funcionales ya que este depende enormemente de la recursión.

En F# es importante tener en cuenta cuando se realiza alguna función recursiva, que efectivamente la última llamada sea a la función. Sin embargo en algunos casos no es tan fácil realizar ésto. Por ejemplo veamos el caso "naive" de Fibonacci sin recursión de cola.


   14 let rec fibNonTR n

   15     match n with

   16     | 0 -> 1

   17     | 1 -> 1

   18     | n -> fibNonTR (n - 1) + fibNonTR (n - 2)



Como puede uno tener una definición que haga una sola llamada a la función de Fibonacci si esta es en si misma contiene 2 llamadas? La opción es usar un "acumulador" que tiene la particularidad de ir armando una función (Continuation) que calcule Fibonacci:


    3 let fibTR n

    4     let rec fibCont n cont =

    5         match n with

    6         | 0 -> cont 1

    7         | 1 -> cont 1

    8         | n -> fibCont (n-1) (fun n1 ->

    9                fibCont (n-2) (fun n2 ->

   10                (cont (n1 + n2) )))

   11     fibCont n (fun x -> x)



Veamos los casos triviales:


   36 fibCont 0 x->x = (fun x -> x) 1

   37 1

   38 

   39 fibCont 1 x->x = (fun x -> x) 1

   40 1



Ahora entendamos como se arma la función (parece magia :P)

El caso de fib 2:


   42 fibCont 2 x->x =

   43 fibCont 1 (fun n1 -> fibCont 0 (fun n2 -> (fun x -> x) (n1 + n2) ))

   44 fibCont 1 (fun n1 -> fibCont 0 (fun n2 -> (n1 + n2)))

   45 fibCont 1 (fun n1 -> (n1 + 1)))

   46 (1 + 1)

   47 2



fib 3:


   49 fibCont 3 x->x =

   50 fibCont 2 (fun n1 -> fibCont 1 (fun n2 -> (fun x -> x) (n1 + n2)))

   51 fibCont 2 (fun n1 -> fibCont 1 (fun n2 -> (n1 + n2)))

   52 fibCont 2 (fun n1 -> (n1 + 1))

   53 fibCont 1 (fun n1' -> fibCont 0 (fun n2' -> (fun n1 -> n1 + 1) (n1' + n2')))

   54 fibCont 1 (fun n1' -> fibCont 0 (fun n2' -> (n1' + n2') + 1))

   55 fibCont 1 (fun n1' -> (n1' + 1 ) + 1)

   56 ((1 + 1 ) + 1)

   57 3




Cuestión de Rendimiento

Pese a que se elimina la utilización de la pila... ¿Es mas eficiente?
Pues hagamos una prueba:


   20 let benchmark (f:'a lazy) =

   21     let before = System.DateTime.Now

   22     f.Force() |> ignore

   23     printfn "%A"  (System.DateTime.Now - before)

   24 

   25 let list = [0..40]

   26 

   27 benchmark (lazy List.map fibTR list)

   28 

   29 benchmark (lazy List.map fibNonTR list)

   30 



Ésto da como resultado:

//Tail Recursive
00:02:58.6250000
//Non Tail Recursive
00:00:19.0312500

Porque el que tiene la "optimización" es mas "lento"?

La continuación que estamos pasando es realmente una referencia a una función. Las funciones en F# son alojadas en Heap. Ésto quiere decir que se hacen continuas llamadas a sistema para alojar en memoria dichas estructuras. Alojar en Heap es mucho mas costoso que usar la pila.

lunes, marzo 03, 2008

Tail Recursion

Pues bien. Tail Recursion es una técnica común de optimización para las llamadas recursivas. Básicamente lo que intenta hacer es eliminar los continuos llamados a la función (call) y mas bien los reemplaza con saltos. Para entender ésto comencemos con un ejemplo:

unsigned int
factorial(unsigned int n){
if (n != 0)
return (n * factorial(n-1));
else
return 1;
}


El factorial recursivo de toda la vida... cierto?

Miremos el ensamblador:


_factorial:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
cmpl $0, 8(%ebp)
je L2
movl 8(%ebp), %eax
decl %eax
movl %eax, (%esp)
call _factorial
imull 8(%ebp), %eax
movl %eax, -4(%ebp)
jmp L1
L2:
movl $1, -4(%ebp)
L1:
movl -4(%ebp), %eax
leave
ret

Éste pedazo es lo que se encarga de mantener los registros de la pila. Cada llamada a una función debe hacer ésto. Crear un nuevo marco para preservar el "contexto".


_factorial:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
...
L1:
movl -4(%ebp), %eax
leave
ret


Si la profundidad de la recursión es muy grande, corremos el riesgo de quedarnos sin pila dado que cada marco utiliza su propia fracción de la pila. Además... gastamos algunos ciclos en las operaciones para preservar el contexto.

Ahora bien... en el caso del factorial, pensar un código iterativo equivalente que no utilice pila resulta fácil. Mejor aún, es posible garantizar que para ciertos tipos de recursión se pueda hacer ésta traducción en forma automática. Las recursiones que se pueden traducir son llamadas Tail Recursions o Recursiones de cola y deben cumplir una sencilla condición. En el bloque que suceda la llamada, no debe haber trabajo extra... Es decir, el bloque donde suceda la llamada a la función solo debe estar ésta.

Siendo así él código en C, debe ser modificado: Una forma usual de hacer ésto es utilizar un acumulador para hacer la multiplicación:

unsigned int
factorial(unsigned int n, unsigned int accum){
if (n != 0)
return factorial(n-1, accum * n);
else
return accum;
}


Ésto nos genera:


_factorial:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
cmpl $0, 8(%ebp)
je L2
movl 12(%ebp), %eax
imull 8(%ebp), %eax
movl %eax, 4(%esp)
movl 8(%ebp), %eax
decl %eax
movl %eax, (%esp)
call _factorial
movl %eax, -4(%ebp)
jmp L1
L2:
movl 12(%ebp), %eax
movl %eax, -4(%ebp)
L1:
movl -4(%ebp), %eax
leave
ret


Y con una simple modificación podemos evitarnos el overhead de cada llamada a la función y nos evitamos el gasto de memoria de pila:

Es cuestión de copiar los parámetros en donde estaban los antiguos, reemplazar el call por un salto al lugar justamente posterior que se encarga de mantener el marco de pila. Y se puede eliminar el código inalcanzable.


_factorial:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
_tail:
cmpl $0, 8(%ebp)
je L2
movl 12(%ebp), %eax
imull 8(%ebp), %eax
movl %eax, 12(%ebp)
movl 8(%ebp), %eax
decl %eax
movl %eax, 8(%ebp)
jmp _tail
L2:
movl 12(%ebp), %eax
movl %eax, -4(%ebp)
movl -4(%ebp), %eax
leave
ret