martes, 1 de septiembre de 2009

recursividad, perl, memoize, OOP, Borges y haskell

Hola, este post solo es un reminder a todo el que lea esto (unos 20), que hay vida en el intertubez . Esta tarde, he estado charlando con rbistolfi sobre lo 'usual': Programación, filosofia, i software. Hemos charlado sobre memoización (un tipo de programación dinámica).

Pensaba arreglar un poco el code, y hacerlo en forma de post, pero como me gusta tanto el rollo de la conversación, y como derivamos de un sitio a otro, os posteo el churro entero de texto (lo mejor formateado que se)





*** You have joined channel #vectorlinux-es [16:03]
*** Users on #vectorlinux-es: kidd_ rbistolfi T800
*** #vectorlinux-es modes: +tnc [16:04]
*** #vectorlinux-es was created on Tuesday 2009/08/18 04:01:26 PM
*** rbistolfi_ (n=rbistolf@190.48.115.68) has joined channel #vectorlinux-es
[kidd_] wb rbistolfi_
[rbistolfi_] ty kidd_ [16:39]
[rbistolfi_] bon dia
[kidd_] buenas
[kidd_] que hay tio
[rbistolfi_] hey buena idea la de wikipedia
[rbistolfi_] la niña me ha atrapao en una casita que le regalamos toda la
mañana [16:40]
[kidd_] si, verdad? Ahi podemos editar todos? o tienes que estar registrado?
[rbistolfi_] :D
[kidd_] jajaja
[rbistolfi_] kidd_: creo que tienes que estar registrado
[kidd_] oh :( bueno...
[kidd_] no se si nos dejaran registrar y meter links en el mismo dia [16:41]
[kidd_] (ya me entiendes, no somos los primeros)
[rbistolfi_] seguro que no lo somos
[rbistolfi_] pues en un rato pruebo aver que pasa
[rbistolfi_] anoche me puse a leer un poco sobre recursion :) [16:42]
[rbistolfi_] me dormi a las 3am
[kidd_] lol
[kidd_] donde lo leiste? [16:43]
[kidd_] yo ayer estuve leyendo cositas raras tb
[rbistolfi_] "How to think like a computer scientist"
[kidd_] aps, no lo conozco
[rbistolfi_] es bastante guay
[rbistolfi_] muy facil al principio, pero avanza rapido [16:44]
[kidd_] como PLAI
[rbistolfi_] sips
[rbistolfi_] luego me puse a navegar algunos de los temas, y di con esta
funcion
[rbistolfi_] def fibonacci(n):
[rbistolfi_] "Return the nth fibonacci number."
[rbistolfi_] if n in (0, 1):
[rbistolfi_] return n
[rbistolfi_] return fibonacci(n-1) + fibonacci(n-2) [16:45]
[kidd_] sips, es la clasica recursiva, junto con el factorial
[rbistolfi_] yap
[kidd_] esta serie tiene muchas particularidades
[rbistolfi_] es insane
[rbistolfi_] :D
[kidd_] esta relacionada con la proporcion aurea
[rbistolfi_] pues el flujo de esa funcion es una locura :D [16:46]
[kidd_] ¿?
[kidd_] el flujo?
[rbistolfi_] el flow, digamos
[kidd_] ah, la ejecucion.
[rbistolfi_] va agregando istancias de si misma al stack [16:47]
[kidd_] jaj, claro... esta funcion es memoizable 100%
[rbistolfi_] si, la encontre con un ejemplo de memoize
[rbistolfi_] http://wiki.python.org/moin/PythonDecoratorLibrary
[kidd_] pq para calcular fib(n-1), tiene que calcular fib(n-2) y fib(n-3) ,
pero fib(n-2) ya esta siendo calculada como 'hermana' de fib(n-1)
[rbistolfi_] /Memoize
[rbistolfi_] claro [16:48]
[kidd_] veo que python hace un objeto para memoizar [16:49]
[kidd_] en perl, la cosa va a nivel funcion (y de hecho, una funcion no es un
objeto en perl...) [16:50]
[rbistolfi_] se puede hacer con una funcion tambien
[kidd_] ah
[kidd_] esque creia que en python, las closures eran un poco .... feas
[rbistolfi_] pues no se si son feas, pero normalmente python ofrece un idioma
para lo que quieras hacer en lugar de la closure [16:51]
[rbistolfi_] y ademas un objeto provee ya la persistencia que logras en muchas
de las closures de functional programming
[kidd_] ya... nose donde lo leí esto de python [16:52]
[rbistolfi_] pero por lo que he visto, en la mayoria de los casos la closure
se puede reemplazar con un generator o un decorator
[rbistolfi_] pues no es un idioma comun, eso seguro
[rbistolfi_] kidd_: pero cuentame como se implementa en perl :) [16:53]
[kidd_] jej. en perl, las closures son tan faciles como meter un bloque que
este por fuera la funcion [16:54]
[kidd_] p.ejemplo
[kidd_] { my $a=0 sub counter{ ++$a} }
[kidd_] counter; #1
[kidd_] counter; #2
[kidd_] .... [16:55]
[kidd_] ok?
[rbistolfi_] sips
[kidd_] ok, ahora un poco mas complicado. quiero hacer una funcion que genere
counters, dando puntos de partida
[kidd_] [16:57]
[kidd_] sub countGen{
[kidd_] my $a = shift;
[kidd_] return sub {
[kidd_] ++$a;
[kidd_] };
[kidd_] }
[kidd_]
[kidd_] my $fun_ref= countGen(5);
[kidd_] $fun_ref->(); #6
[kidd_] $fun_ref->(); #7
[kidd_] ...
[rbistolfi_] okis [16:58]
[kidd_] pues si a esto le metes lo de poder entrar funciones como args
[kidd_] haces un meta-wrapper que inserta la logica de inicializar un hash, y
devolver una funcion wrapeada que hace la comprovacion de si los
params estan en el hash y si estan devuelve el valor. sino, ejecuta y
guarda el valor en el hash [16:59]
[kidd_] me explico? es como el ultimo ejemplo , pero anidado una vez mas
[rbistolfi_] wow, que chulo
[rbistolfi_] sips
[kidd_] en perl, ademas, puedes cambiar la tabla de simbolos [17:00]
[kidd_] osea, que la misma funcion memoize('mifun'); busca en la tabla de
simbolos mifun
[kidd_] ejecuta el meta-wrapper, y la wrappeada la llama temporalmente
mifun_XYZ
[kidd_] entonces a la mifun le llama mifun_dentro [17:01]
[kidd_] y cambia finalmente mifun_XYZ por mifun, que llama a mifun_dentro
[kidd_] (el tipico swap)
[kidd_] total, que tu programa sigue llamando a mifun
[kidd_] y no tienes que cambiar nada en absoluto
[rbistolfi_] ya, se van pasando la funcion internamente [17:02]
[kidd_] otra de las ventajas de que se hace en tiempo de ejecucion, es que
puedes memoizar solo las funciones que se llaman mucho
[rbistolfi_] claro
[kidd_] mantener contadores (con closures) para saber cuanto has llamado a una
fun
[kidd_] y hacer un wraper general que diga que de una lista de funciones puras
que tu le dices, memoice a partir de las 1000 llamadas [17:03]
[kidd_] como ves, es mucho mas home_made, pero tienes todo el poder en tus
manos
[kidd_] es lo que tiene perl (en general)
[rbistolfi_] pfff que bonito
[rbistolfi_] pues si, es meta-codigo inteligente :D
[kidd_] el libro higher order perl habla de esto exactamente
[kidd_] y no es necesario saber mucho perl para estas partes [17:04]
[kidd_] si quieres un dia lo repasamos
[kidd_] pq es muy bonito
[rbistolfi_] ya, es solo el concepto este de pasar bloques o subs como args
[rbistolfi_] guay sisi
[rbistolfi_] estaria muy bien
[kidd_] y tb sera una excusa para volver a HOP [17:05]
[kidd_] que lo abandoné hace tiempo
[rbistolfi_] jej no esta mal repasar un pco
[rbistolfi_] ah, cual era el asuto de OOP de anoche? [17:06]
[rbistolfi_] *asunto
[kidd_] ah, esque era una movida... sin el code no se si lo sabre explicar
(tengo el code del Mastermind en el lappy)
[rbistolfi_] ah np [17:07]
[kidd_] imagina tengo unas clases: juego, tablero, jugada, jugador ,
[kidd_] la idea es que el tablero es un array de jugadas
[rbistolfi_] sips
[kidd_] el juego tiene como attrs un tablero y 2 jugadores
[rbistolfi_] nice [17:08]
[kidd_] pues bien, el juego tiene una funcion run, que hace que vayan jugando
los 2 players
[kidd_] y va comprobando si el juego ha acabado o no
[kidd_] pues bien, desde el juego hago $self->jugador1->juega
[kidd_] pero el jugador no sabe donde tiene que jugar
[kidd_] pq no tiene relacion con el tablero, ni con la jugada. solo con el
juego mismo, pero el no puede llegar [17:09]
[kidd_] una manera es llamarlo como $self->jugador1-juega($self)
[kidd_] pasando el propio juego por parametro
[rbistolfi_] claro
[kidd_] pero nose... no se si esta era la manera de hacerlo
[rbistolfi_] lindo problem [17:10]
[rbistolfi_] yo diria que la dependencia logica es de tablero
[kidd_] tb podria hacer que el jugador tenga como atributo el juego al que
pertenece
[rbistolfi_] la jugada depende del estado de tablero
[kidd_] osea, mandarlo asi [17:11]
[rbistolfi_] esa ultima parece ser la mas indicada desde el punto de vista
formal al menos
[kidd_] $self->jugador1-juega->($self->tablero)
[kidd_] sips
[kidd_] puede ser
[kidd_] pero nose... normalmente no hay estas relaciones cruzadas [17:12]
[rbistolfi_] claro
[kidd_] pq los objetos son datos más que nada
[kidd_] pero cuando los tratas como 'actores'
[rbistolfi_] exacto
[kidd_] para conversar, necesitan conocerse los dos
[kidd_] o tener alguien que llama explicitamente a cada funcion de cada uno,
con el parametro adecuado [17:13]
[rbistolfi_] ya, aparece la situacion, o el estado general
[kidd_] sips
[rbistolfi_] porque cada jugador debera derivar su jugada de tablero, pero si
lo piensas profundamente, esa dependencia transforma
probablemente a jugador en atributos de tablero [17:14]
[rbistolfi_] al final, el juego desarrolla su logica sin jugador xD
[kidd_] claro, esque son 2 formas de enfocarlo distintas
[kidd_] pero hay una en la que desaparece el jugador, pq en el fondo es el
propio juego que cambia de estado
[rbistolfi_] exacto [17:15]
[kidd_] pero entonces necesitas que el propio juego se rija el mismo, y se
haga avanzar
[kidd_] esta es la manera 'normal' de un programa
[rbistolfi_] como en la peli
[rbistolfi_] la que la compu declara la guerra y debe aprender
[kidd_] pero si lo quiero hacer interactivo, y con jugadores e interficies
intercambiables
[rbistolfi_] como se llama?
[kidd_] ¿?
[kidd_] no se [17:16]
[rbistolfi_] no importa :D
[kidd_] nada, pues eso... que estoy con esas cosas
[rbistolfi_] ya, el juego requiere jugador1 y jugador2
[kidd_] como son toy projects, no da miedo cagarla, pero siempre gusta hacerlo
bien
[kidd_] sips
[rbistolfi_] pues claro
[kidd_] de hecho, uno es Player::Master y el otro Player::Guesser
[rbistolfi_] si jugador1 y jugador2 son impresindibles, entonces son
observadores de tablero [17:17]
[rbistolfi_] que es la representacion natural del juego
[kidd_] y el juego tiene un metodo run, y attrs jug1, jug2, tablero
[rbistolfi_] ta, juego tiene que notificar a los players del cambio en el
tablero [17:18]
[kidd_] bueno, al ser por turnos, si el metodo jugar recibe el tablero como
attr
[kidd_] ya no hay problema
[kidd_] no es a tiempo real
[kidd_] si tuviera que hacer observers... esto seria otro rollo [17:19]
[rbistolfi_] claro, entonces tendrias un tablero en el scope de juego, que lo
puedes pasar a cualquiera de los players segun el turno
[kidd_] bueno, lo que tengo es esto. un tablero que lo paso a los players
cuando les toca [17:20]
[kidd_] lo del observer seria que los jugadores vieran los cambios aunque no
fuera su turno
[kidd_] osea, imagina un juego de 4 players
[kidd_] una aproximacion es a cada turno le paso al player i el tablero actual
[17:21]
[rbistolfi_] exacto, 4 no solo ve la jugada de 3, sino de 2 y de 1
[rbistolfi_] pues si
[kidd_] la otra (con observers) es : cada vez que un player toca el tablero,
todos los demas se enteran (no solo el i+1) y pueden estar pensando
estrategias a hacer con este estado [17:22]
[kidd_] si solo hay 2 players no tiene mucho sentido, aunque seria un buen
ejercicio
[rbistolfi_] pues es interesante, aunque ya la implementacion requiere un poco
mas
[rbistolfi_] pero si, estaria muy chulo
[rbistolfi_] que se puede leer sobre el asunto :) [17:23]
[rbistolfi_] hace rato que quiero leer algo mas abstracto
[rbistolfi_] tipo... patrones de diseño
[kidd_] si llegados a un punto, puedo hacer que el que lleve el juego sea un
controller, y 'juego' solo tenga funciones para modificar el estado
del tablero y devolverlo, podriamos jugar con jugadores via socket
[kidd_] o hacer una vista tipo web
[rbistolfi_] guaaaaaaaay [17:24]
[kidd_] rbistolfi_: tengo el libro de design patterns
[kidd_] ya te lo pasare
[kidd_] pero es un poco toston de leer
[rbistolfi_] me lo imagino
[kidd_] yo no me he leido mas de 10 pags seguidas
[kidd_] y no es agradable
[kidd_] es como un manual de ref
[rbistolfi_] es "el" libro de design patterns no?
[kidd_] sips
[kidd_] el de los 'gang of four' [17:25]
[rbistolfi_] ya
[kidd_] dicen que esta esto de los patrones estan inspirados en la
arquitectura
....
[kidd_] tio, has visto el ritmo de updates de #squeak?
[kidd_] altisimo
[rbistolfi_] sisi, el bot ya esta con la lengua afuera
[kidd_] lol
[rbistolfi_] se ve que se viene la release [17:30]
[kidd_] sips. hoy he mirado la pag de pharo
[kidd_] estan en beta ya
[rbistolfi_] me estuve pensando el otro dia en la discusion
[rbistolfi_] y me parece que el merge, o la migracion total de squeak a pharo
es inevitable [17:31]
[rbistolfi_] si como dice Randal, se ha aceptado la critica de los pharistas
[rbistolfi_] y el goal hacia 4.0 es "limpiar" el kernel y modularizar todo lo
que sea "accesorio"
[rbistolfi_] en un momento squeak y pharo van a superponerse [17:32]
[kidd_] ya, osea que squeak tenia previsto ser pharo, pero de aqui a un tiempo
[kidd_] osea que el camino es el mismo
[rbistolfi_] eso quiere decir que el asunto dejara de ser tecnico para ser
politico
[rbistolfi_] ya
[rbistolfi_] solo queda decidir quien es el lider, si el board de pharo o el
de squeak [17:33]
...
[rbistolfi_] me acorde de unos versos de Borges, por el tema del juego [17:36]
[rbistolfi_] lo tendras que citar en el doc
[rbistolfi_] "Dios mueve al jugador y el jugador a la pieza / [17:37]
[kidd_] ok. hecho
[rbistolfi_] Que dios detras de dios la trama empieza?"
[rbistolfi_] es de un poema que se llama "Ajedrez"
[rbistolfi_] muy pertinente
[rbistolfi_] es la misma pregunta que nos hemos hecho :D [17:38]
[rbistolfi_] si hay jugador, o solo tablero
[kidd_] joer, si??
[rbistolfi_] ese es el final "Dios mueve al jugador, y el jugador a la pieza,
que dios detras de dios la trama empieza, de polvo tiempo, sueño
y agonia?" [17:39]
[rbistolfi_] http://www.metajedrez.com.ar/borges.htm [17:40]
[kidd_] joer, demasiao pa mi :)
[kidd_] ah, thx
[rbistolfi_] ya, es rebuscao el poema [17:41]
[kidd_] todo lo meta me mola :) [17:43]
[rbistolfi_] pues si :)
[kidd_] el otro dia volví a hablar de Gödel , Escher Bach con un colega y en
breve lo volveré a pillar
[kidd_] a ver si lo encuentras en alguna biblio o algo
[kidd_] pq vas a alucinar [17:44]
[rbistolfi_] es que es muy dificil no enrollarse con estas cosas
[rbistolfi_] ya, lo tengo que buscar
[rbistolfi_] lo encontre en una lib por aqui, pero eran como 200€
[kidd_] ¿?!!!
[rbistolfi_] un edicion preciosa, eso si :D
[kidd_] joder!
[rbistolfi_] tusquets me parece
[kidd_] sips.
[rbistolfi_] hay uno de bolsillo que es mas barato, pero aun no lo he visto
[17:45]
[rbistolfi_] por aca
[kidd_] ah, esque como celebraron los 20 años, igual hicieron alguna edicion
Edicion 'golden'
[kidd_] sip, esta de bolsillo yo la vi por 17 Euros
[kidd_] los mejores 17 euros en mucho tiempo. palabra [17:46]
[rbistolfi_] joder, 17€ [17:47]
[rbistolfi_] es cierto que lo mas valioso no tiene precio
[kidd_] como ya decíamos ayer
[kidd_] :)
[rbistolfi_] hace un tiempo pense en ello, porque encontre una edicion de la
iliada en un cajon de la basura
[rbistolfi_] quien puede tirar la iliada a la basura [17:48]
[rbistolfi_] eso prueba que estamos involucionando hacia el mono
[rbistolfi_] :D
[kidd_] jaj
[rbistolfi_] kidd_: tio, parece que gambas no tiene namespaces ni nada 0.o
[17:56]
[rbistolfi_] no puedes importar modulos escritos en gambas [17:57]
[kidd_] jaj
[kidd_] me lo creo
[kidd_] son lenguajes hechos a im. i sem de VB
[rbistolfi_] eso quiere decir que m0e tiene que pasar el estado del installer
a la siguente etapa del wizard cada vez :/
[kidd_] como? no t pillo [17:58]
[kidd_] ooooostia!
[kidd_] ahora t pillo
[rbistolfi_] hay step1.gambas
[rbistolfi_] para que step2.gambas sepa de step1
[rbistolfi_] ya me lo pillaste [17:59]
[kidd_] y la info se tiene que ir pasando , pq no mantiene viva la info de
step1
[rbistolfi_] claro
[kidd_] pero esto no es de namespaces....
[kidd_] bueno si... a menos que llames a todo de forma diferente
[rbistolfi_] ya, no es directamente de namespaces
[kidd_] pero son colisiones generales [18:00]
[kidd_] que todo son vars globales
[rbistolfi_] exactly
[kidd_] y no puedes mantener el estado de un objeto
[kidd_] pfff
[rbistolfi_] al menos eso es lo desprendo de lo que dice M0E
[kidd_] joer, comparando esto con las cosas superteoricas de PLAI (me lo
estuve mirando ayer...) [18:01]
[kidd_] da pena que contemporaneamente se programe en gambas y en haskell
[rbistolfi_] ya, es increible
[kidd_] puess rbistolfi_ , si el rollo de la recursividad te esta gustando,
mira la manera de definir funs en haskell
[rbistolfi_] fue una mala eleccion
[kidd_] len [] = 0
[kidd_] len (x:s) = 1 + len s
[kidd_]
[rbistolfi_] me lo voy a mirar
[kidd_] esta es la funcion len
[rbistolfi_] 0.o [18:02]
[kidd_] [] = lista vacia
[kidd_] osea, le dices len de lista vacia , devuelve 0
[kidd_] (caso base)
[rbistolfi_] ya
[kidd_] y len de una lista, donde el primer elem lo llamo x y el resto s
(car, cdr)
[kidd_] devuelve 1 mas len de el cdr [18:03]
[rbistolfi_] :)
[kidd_] eso tb es poesia
[rbistolfi_] totalmente
[kidd_] listCopy [] = []
[kidd_] listCopy (x:s) = x : listCopy s
[kidd_]
[kidd_] otra igual [18:04]
[kidd_] fijate que haskell es fuertente tipado, pero puedes picar sin tipos
[kidd_] pq tiene inferencia de tipos con polimorfismo
[kidd_] osea, que el presupone cosas
[rbistolfi_] pero una vez efinido un tipo lo tienes que respetar [18:05]
[kidd_] y mientras vayan cumpliendose, pues no pasa nada, y a la que no se
cumplen, el tio mira si las 2 vars tienen un tipo antecesor comun
[kidd_] si es así, pues presupone aquel tipo mas generico
[rbistolfi_] nice
[rbistolfi_] tenemos que empaquetar haskell [18:06]
[rbistolfi_] VL7.0 va a estar guay :D
[kidd_] jej
[rbistolfi_] lo pillaremos desde el ppio [18:07]
[rbistolfi_] bueno tio, me voy a comer y luego al curro
[kidd_] oki
[kidd_] hablamos
[rbistolfi_] laters

Esto ha sido todo... espero que os hayais enterado de algo... si necesitáis referencias, pues las pedís por los comments, y así sé si alguien lee esto.

No hace falta decir que estais invitados a #vectorlinux-es en irc freenode.

Gracias a rbistolfi por colaborar en el 50% del articulo