Tuesday, July 17, 2007

forth en lisp

estaba aburrido en mi clase de física y me puse a escribir algo que se me ocurrió el otro día: hacer que lisp pueda usarse tipo forth.

forth, por si no lo saben, es un lenguaje stack-based. podriamos decir que carece de sintaxis: es una sucesion de palabras que se lee de izquierda a derecha, y se comunican por una pila o stack. algo así:

2 3 + dup +

Las palabras son "2", "3", "+" y "dup".
"2" y "3" ponen, respectivamente un 2 y un 3 en la pila.
"+" toma los dos primeros elementos de la pila, los suma, y lo pone encima de la pila.
"dup" mira el primer elemento de la pila, y lo vuelve a poner encima de la pila.

El programa se ejecuta así

inicio -- pila: (vacía)
2 -- pila: 2
3 -- pila: 3 2
+ -- pila: 5
dup -- pila: 5 5
+ -- pila: 10

Este estilo de programacion carece de sintaxis, y es muy legible para algunos. Para mi es un quilombo, pero no importa, quise hacer un forth en lisp.

La idea es simple: represento la pila con una lista. Defino funciones comunes de lisp, que reciban la pila/lista, y devuelvan la lista modificada. Luego, para combinar las funciones, las compongo.

En realidad, forth y sus derivados suelen tener otra pila auxiliar, y aca no hay. Otra opcion sería usar dos pilas. En lugar de como hice acá, usar &rest y demases, quiza convenga pasar la lista como un parametro cualquiera, y direcamente pasamos dos listas, o hacer alguna tramoya rara con connect (se podria hacer).

La idea aqui presentada podria expandirse, pero francamente no tengo ganas.

El codigo:

(defun dup (f &rest rest)
    (cons f (cons f rest)))
(defun swap (a b &rest rest)
    (cons b (cons a rest)))
(defun fdrop (a &rest rest)
    rest)
(defmacro if0 (test &body b)
    `(if (= ,test 0) ,@b))
(defun fconnect (f &rest list)
    (if0 (length list)
        f
        (lcompose (apply #'fconnect list) f)))
(defun lcompose (f g)
    (lambda (&rest args)
        (apply f (apply g args))))
        
(defmacro lisp-forth (lispf forthf comb length)
    `(defun ,forthf (&rest list)
        (,comb (apply #',lispf 
                (
take ,length list)) 
                  (drop ,length list))))
(defun take (len list)
    (loop for i from 1 to len
          for e in list
          collect e))
(defun drop (len list)
    (if0 len
         list
         (drop (- len 1) (cdr list))))

(defmacro connect (&rest list)
    `(fconnect ,@(mapcar #'asfunction list)))

(defun asfunction (e)
    (cond ((symbolp e) `(function ,e))
          ((or (numberp e) (eq (car e) 'quote)) 
                `(push-identity ,e))))
(defun push-identity  (e)
    (lambda (&rest list) (cons e list)))
          
(defmacro define-forth (f &rest definition)
    `(defun ,f (&rest args)
        (apply (connect ,@definition) args)))
        
(lisp-forth + f+ cons 2)
(lisp-forth - f- cons 2)
(define-forth lolfun dup f+ 2 f+ 3 swap f-)

(defun lolfun2 (n) ((+ n n 2) 3))

explico rápidamente que hace cada cosa:

dup, swap, y fdrop, hacen lo mismo que en forth.
if0 es una simple comparacion con 0 que uso a veces.
fconnect es una funcion que recibe una lista de funciones estilo forth, y las compone recursivamente. lcompose es como una composicion de funciones normal, pero la diferencia es que lo que devuelve la segunda funcion no es el parametro unico de la primera funcion, sino que es aplicado (funcall vs. apply).

lisp-forth es una macro para definir funciones estilo forth a partir de funciones lisp. damos el nombre de la funcion lisp, el nombre de la funcion que queremos definir, con que vamos a combinar el resultado de la funcion comun con el resultado de la pila, y cuantos elementos de la pila le vamos a pasar como parametro.

connect es una macro que agrega los #' a las funciones y cambia los numeros y cosas quoteadas (simbolos, listas, etc) por funciones que colocan esos objetos en la pila (funciones armadas con push-identity), mediante la funcion asfunction (asfunction podria tener mas opciones pero por ahora, esas).

define-forth es, finalmente, lo que nos permite armar funciones tipo forth en base a otras funciones tipo forth.

espero que les haya gustado, mis dos o tres lectores que seguramente no saben lisp y no van a entender este post (posible excepcion: CC)!

Sunday, July 15, 2007

ETIQUETAS. MUCHAS ETIQUETAS

ahora los posts tienen etiquetas. tuve que reetiquetar todos los posts previos. Esto es para organizar un poco los contenidos de este blog. Espero que se entiendan, mis dos o tres lectores.

reduce, foldl, inject, accum, etcetera

Guido Van Rossum, el diseñador de Python, dice que no le gusta la funcion reduce, tambien conocida como foldl, inject o accum. Le parece complicada, y dice que cada vez que la ve haciendo algo mas o menos complicado, tiene que agarrar lapiz y papel para darse cuenta de lo que esta haciendo.

Francamente no entiendo por que, ya que es una funcion sencilla, solo hay que encararla correctamente. Así que, voy a explicarles como usar reduce, así ya se disipa el misticismo.

En primer lugar, vamos a definir reduce. Voy a usar una sintaxis tipo javascript, que es como la de C. Alcanza con que sepan lo siguiente de la sintaxis, que lo diferencia de C, Java, C# y demases: Primero, que no hay tipos en las variables.

function (arg1, arg2, ...) { declaraciones } en javascript.

Aunque ausente de muchos lenguajes como Java o C++, en lenguajes como Python, Ruby, Lisp, Haskell, Smalltalk, Javascript, etc; las funciones son valores como cualquier otro, se pueden asignar a variables, pasar como parametros, devolverse, etc. Toda funcion que reciba una funcion por parametro o devuelva una funcion se llama "funcion de orden superior". Entonces

function (x) { return x + x; }

es una funcion dado un valor, devuelve el doble. Aclaro que cuando en javascript ponemos

function nombre (x) { etc... }

escribir eso en javascript es equivalente a escribir

var nombre = function (x) { etc...}

Vamos a definir reduce, sin más. Reduce recibe tres argumentos, un valor inicial "vi", una funcion "f", y una lista/vector/coleccion/etc "lista". La funcion "f" recibe dos valores, un valor acumulado y un elemento de la lista "lista", y devuelve otro valor. reduce aplica la "f" al primer elemento de la lista, pasandole como valor acumulado el valor inicial "vi". Lo que devuelve "f" se convierte en el nuevo valor acumulado, y asi hasta pasar por todos los elementos de la lista.

algo así:


function reduce(vi,f,lista)
{
for(var i = 0, var accum = vi; i < lista.length; i++)
{
accum = f(accum, lista[i]);
}
return accum;
}



Entonces, veamos que hace esta funcion, graficamente hablando:



Entonces, podemos ver, suponiendo que lista tenga los elementos 1, 2 y 3.

reduce llama a la funcion, totalAcumulado vale el valor inicial, 0, y elem, 1. La funcion devuelve la suma de 0 + 1, entonces la funcion devuelve 1. Este valor pasa a ser el nuevo totalAcumulado. Ahora, reduce llama a la funcion de nuevo, pero ahora, totalAcumulado vale 1, y elem vale 2. La funcion devuelve la suma de los elementos, entonces totalAcumulado pasa a ser 3 y elem pasa a ser 3, y la suma devuelve 9. como no hay mas elementos en la lista, reduce devuelve 6, que es la sumatoria de todos los elementos de la lista.

Expresado en una tablita:



como podemos ver, lo que devuelve la funcion pasa a ser el nuevo total acumulado.

Por cierto, aca podemos ver cierta recursividad, fijense como podemos decir que el resultado de la funcion pasa a ser el nuevo valor inicial. Una definicion recursiva de reduce vendria a ser:

function reduce(vi, f, lista)
{
if(lista.length == 0) return vi;
return reduce(f(vi, first(lista)), rest(lista));
}


donde first(lista) devuelve el primer elemento de la lista, y rest(lista) devuelve una nueva lista sin el primer elemento.

si tantos parentesis les marean, veanlo de vuelta así

function reduce(vi, f, lista)
{
/* si la lista esta vacía, devuelvo vi */
if(lista.length == 0) return vi;
/* primer elemento de la lista */
var pri = first(lista);
/* primer elemento de la lista */
var resto = rest(lista);
/* nuevo valor inicial, vi es el total acumulado, pri es el valor de la lista */
var nuevoVI = f(vi, pri);
return reduce(nuevoVI, f, resto);
}

repitiendo el ejemplo de antes, estamos diciendo que (imaginemos por un momento que javascript tiene una sintaxis para las listas/vectores del tipo [elemento1, elemento2, elemento3, ...]:

var f = function (totalAcumulado, elem) { return totalAcumulado + elem; };
reduce(0, f, [1,2,3]);

devuelve

reduce(f(0,1), f, [2,3]);

(y como f(0,1) = 1, devuelve)

reduce(f(1,2), f, [3]);

(y como f(1,2) = 3, devuelve)

reduce(f(3,3), f, []);

(y como f(3,3) = 6, y la lista esta vacia, devuelve el valor inicial, que es 6).

En general, cada ves que vemos

reduce(vi, function(total, elem) { return expresion }, lista)

podemos suponerlo aproximadamente equivalente a

total = vi;
for(elem in lista)
{
    total = expresion;
}
return total;


resumiendo este embole, es claro ver que hay una redundacia de elementos al escribir el algoritmo entero. Realmente se gana claridad por sobre reduce?

Por ultimo, y ya que guido van rossum dice que todo uso de reduce mas alla de reduce(0, +, listaDeNumeros) o reduce(1, *, listaDeNumeros) es complicado, piensen que hacen estas funciones

reduce(-1, function(total, elem) { return total > elem ? total : elem; }, listaDeNumeros);

reduce(0, function(total, elem) { return total + elem.length; }, listaDeStrings);

(recuerden que aca "total" se refiere no al total completo, sino el total computado hasta el momento).

Monday, July 09, 2007

nieve

Nieve,
nieve,
nieve,
nieve,
nieve,
nieve.

Friday, July 06, 2007

titulares engañosos

Gran Bretaña: según un estudio, en 2020 la tecnología de punta consumirá casi la mitad de la energía
"lol la mitad de la energía wtf... asumo tacitamente que la energia se refiere al total de la energia consumida"
El informe explica que dispositivos como los televisores de pantalla plana y las radios digitales demandarán el 45% de la electricidad.
"OMG LET'S KEEP READING"
Las tecnologías de punta, como los televisores de pantalla plana y las radios digitales, consumirán el 45% de la electricidad de los hogares británicos
"AHHH, DE LOS HOGARES. FORRO. Igual abramos el pdf con el articulo"
Mientras el resto de los aparatos cada vez consume menos (...)
"O sea, van a consumir el 45% de la electricidad hogareña, porque consumen mucho... O PORQUE TODO EL RESTO DE LOS APARATOS ESTAN CONSUMIENDO MENOS??!?! FORRO HIJO DE REMIL PUBLICIDAD ENGAÑOSA"
sobame la quena

http://www.clarin.com/diario/2007/07/05/um/m-01451325.htm