Concurrencia en Erlang parte 7

Probemos algo con la ayuda del comando pid(A,B,C), que nos permite convertir los 3 números enteros A, B y C en un pid. Aquí le daremos deliberadamente a kitchen:take/2 uno falso:

20> kitchen:take(pid(0,250,0), dog).

Ups. El shell está congelado. Esto sucedió debido a la forma en que se implementó take/2. Para entender lo que sucede, primero revisemos lo que sucede en el caso normal:

1. Un mensaje para tomar comida se envía desde el shell al proceso del refrigerador;
2. Su proceso cambia al modo de recepción y espera un nuevo mensaje;
3. El refrigerador retira el artículo y lo envía a su proceso;
4. Su proceso lo recibe y continúa con su vida.

Y esto es lo que sucede cuando el shell se congela:

1. Un mensaje para tomar comida se envía desde el shell a un proceso desconocido;
2. Su proceso cambia al modo de recepción y espera un nuevo mensaje;
3. El proceso desconocido no existe o no espera tal mensaje y no hace nada con él;
4. Su proceso de shell está bloqueado en modo de recepción.

Eso es molesto, especialmente porque no hay manejo de errores posible aquí. No sucedió nada ilegal, el programa solo está esperando. En general, cualquier cosa que tenga que ver con operaciones asincrónicas (que es como se hace el paso de mensajes en Erlang) necesita una forma de abandonar el proceso después de un cierto período de tiempo si no obtiene señales de recibir datos. Un navegador web lo hace cuando una página o imagen tarda demasiado en cargarse, usted lo hace cuando alguien tarda demasiado en responder el teléfono o llega tarde a una reunión. Erlang ciertamente tiene un mecanismo apropiado para eso, y es parte de la construcción de recepción:

receive

    Match -> Expression1

after Delay ->

    Expression2

end.

La parte entre recibir y después es exactamente la misma que ya conocemos. La parte después se activará si se ha pasado tanto tiempo como Delay (un entero que representa milisegundos) sin recibir un mensaje que coincida con el patrón Match. Cuando esto sucede, se ejecuta Expression2.

Escribiremos dos nuevas funciones de interfaz, store2/2 y take2/2, que actuarán exactamente como store/2 y take/2 con la excepción de que dejarán de esperar después de 3 segundos:

store2(Pid, Food) ->

    Pid ! {self(), {store, Food}},

    receive

        {Pid, Msg} -> Msg

    after 3000 ->

        timeout

    end.

take2(Pid, Food) ->

    Pid ! {self(), {take, Food}},

    receive

        {Pid, Msg} -> Msg

    after 3000 ->

        timeout

    end.

Ahora puedes descongelar el shell con ^G y probar las nuevas funciones de la interfaz:

User switch command

 --> k 

 --> s

 --> c

Eshell V5.7.5  (abort with ^G)

1> c(kitchen).

{ok,kitchen}

2> kitchen:take2(pid(0,250,0), dog).

timeout

Y ahora funciona.

After no solo toma milisegundos como valor, en realidad es posible usar el átomo infinito. Si bien esto no es útil en muchos casos (podría simplemente eliminar la cláusula after por completo), a veces se usa cuando el programador puede enviar el tiempo de espera a una función donde se espera recibir un resultado. De esa manera, si el programador realmente quiere esperar eternamente, puede hacerlo.

Existen usos para estos temporizadores además de darse por vencidos después de demasiado tiempo. Un ejemplo muy simple es cómo funciona la función timer:sleep/1 que hemos usado antes. Aquí se muestra cómo se implementa (pongámosla en un nuevo módulo multiproc.erl):

sleep(T) ->

    receive

    after T -> ok

    end.

En este caso específico, nunca se encontrará ningún mensaje en la parte de recepción de la construcción porque no hay ningún patrón. En cambio, se llamará a la parte posterior de la construcción una vez que haya transcurrido el retraso T.

Otro caso especial es cuando el tiempo de espera es 0:

flush() ->

    receive

        _ -> flush()

    after 0 ->

        ok

    end.

Cuando esto sucede, la máquina virtual Erlang intentará encontrar un mensaje que se ajuste a uno de los patrones disponibles. En el caso anterior, todo coincide. Mientras haya mensajes, la función flush/0 se llamará a sí misma de forma recursiva hasta que el buzón esté vacío. Una vez hecho esto, se ejecuta la parte after 0 -> ok del código y la función retorna.

Concurrencia en Erlang parte 6

Algo molesto del ejemplo del post anterior es que el programador que va a utilizar el frigorífico tiene que conocer el protocolo que se ha inventado para ese proceso. Es una carga inútil. Una buena forma de solucionarlo es abstraer los mensajes con la ayuda de funciones que se ocupen de recibirlos y enviarlos:

store(Pid, Food) ->

    Pid ! {self(), {store, Food}},

    receive

        {Pid, Msg} -> Msg

    end.

take(Pid, Food) ->

    Pid ! {self(), {take, Food}},

    receive

        {Pid, Msg} -> Msg

    end.

Ahora la interacción con el proceso es mucho más limpia:

9> c(kitchen).

{ok,kitchen}

10> f().

ok

11> Pid = spawn(kitchen, fridge2, [[baking_soda]]).

<0.73.0>

12> kitchen:store(Pid, water).

ok

13> kitchen:take(Pid, water).

{ok,water}

14> kitchen:take(Pid, juice).

not_found

Ya no tenemos que preocuparnos por cómo funcionan los mensajes si se necesita enviar self() o un átomo preciso como take o store: todo lo que se necesita es un pid y saber qué funciones llamar. Esto oculta todo el trabajo sucio y facilita la creación del proceso de la nevera.

Una cosa que queda por hacer sería ocultar toda esa parte sobre la necesidad de generar un proceso. Nos ocupamos de ocultar los mensajes, pero aún esperamos que el usuario se encargue de la creación del proceso. Veamos la siguiente función start/1:

start(FoodList) ->

    spawn(?MODULE, fridge2, [FoodList]).

Aquí, ?MODULE es una macro que devuelve el nombre del módulo actual. No parece que haya ventajas en escribir una función de este tipo, pero realmente las hay. La parte esencial sería la coherencia con las llamadas a take/2 y store/2: todo lo relacionado con el proceso de refrigerador ahora lo maneja el módulo de cocina. Si tuviera que agregar un registro cuando se inicia el proceso de refrigerador o iniciar un segundo proceso (por ejemplo, un congelador), sería muy fácil hacerlo dentro de nuestra función start/1. Sin embargo, si se deja que el usuario realice la generación a través de spawn/3, entonces cada lugar que inicie un refrigerador ahora debe agregar las nuevas llamadas. Eso es propenso a errores y los errores son una mierda.

Veamos cómo se usa esta función:

15> f().

ok

16> c(kitchen).

{ok,kitchen}

17> Pid = kitchen:start([rhubarb, dog, hotdog]).

<0.84.0>

18> kitchen:take(Pid, dog).

{ok,dog}

19> kitchen:take(Pid, dog).

not_found

¡Hurra! ¡El perro ha salido del frigorífico y nuestra abstracción es total!

Concurrencia en Erlang parte 5

No hay una gran ventaja para los procesos y actores si son solo funciones con mensajes. Para solucionar esto, tenemos que poder mantener el estado en un proceso.

Primero, creemos una función en un nuevo módulo kitchen.erl que permitirá que un proceso actúe como un refrigerador. El proceso permitirá dos operaciones: almacenar alimentos en el refrigerador y sacar alimentos del refrigerador. Solo debería ser posible sacar alimentos que se hayan almacenado de antemano. La siguiente función puede actuar como base para nuestro proceso:

-module(kitchen).

-compile(export_all).

fridge1() ->

    receive

        {From, {store, _Food}} ->

            From ! {self(), ok},

            fridge1();

        {From, {take, _Food}} ->

            %% uh....

            From ! {self(), not_found},

            fridge1();

        terminate ->

            ok

    end.

Algo anda mal. Cuando pedimos almacenar la comida, el proceso debería responder ok, pero no hay nada que almacene la comida; se llama a fridge1() y luego la función comienza desde cero, sin estado. También puedes ver que cuando llamamos al proceso para sacar comida del refrigerador, no hay estado del cual sacarla y, por lo tanto, lo único que se debe responder es not_found. Para almacenar y sacar alimentos, necesitaremos agregar estado a la función.

Con la ayuda de la recursión, el estado de un proceso puede entonces mantenerse completamente en los parámetros de la función. En el caso de nuestro proceso de refrigerador, una posibilidad sería almacenar toda la comida como una lista y luego buscar en esa lista cuando alguien necesite comer algo:

fridge2(FoodList) ->

    receive

        {From, {store, Food}} ->

            From ! {self(), ok},

            fridge2([Food|FoodList]);

        {From, {take, Food}} ->

            case lists:member(Food, FoodList) of

                true ->

                    From ! {self(), {ok, Food}},

                    fridge2(lists:delete(Food, FoodList));

                false ->

                    From ! {self(), not_found},

                    fridge2(FoodList)

            end;

        terminate ->

            ok

    end.

Lo primero que hay que notar es que fridge2/1 toma un argumento, FoodList. Puedes ver que cuando enviamos un mensaje que coincide con {From, {store, Food}}, la función agregará Food a FoodList antes de continuar. Una vez que se realiza esa llamada recursiva, será posible recuperar el mismo elemento. De hecho, lo implementé allí. La función usa lists:member/2 para verificar si Food es parte de FoodList o no. Dependiendo del resultado, el elemento se envía de vuelta al proceso de llamada (y se elimina de FoodList) o se envía not_found de vuelta en caso contrario:

1> c(kitchen).

{ok,kitchen}

2> Pid = spawn(kitchen, fridge2, [[baking_soda]]).

<0.51.0>

3> Pid ! {self(), {store, milk}}.

{<0.33.0>,{store,milk}}

4> flush().

Shell got {<0.51.0>,ok}

ok

Parece que almacenar los alimentos en el frigorífico funciona. Probaremos con más cosas y luego intentaremos sacarlas del frigorífico.

5> Pid ! {self(), {store, bacon}}.

{<0.33.0>,{store,bacon}}

6> Pid ! {self(), {take, bacon}}.

{<0.33.0>,{take,bacon}}

7> Pid ! {self(), {take, turkey}}.

{<0.33.0>,{take,turkey}}

8> flush().

Shell got {<0.51.0>,ok}

Shell got {<0.51.0>,{ok,bacon}}

Shell got {<0.51.0>,not_found}

ok

Como era de esperar, podemos sacar el tocino del frigorífico porque lo hemos puesto allí primero (junto con la leche y el bicarbonato de sodio), pero el proceso del frigorífico no encuentra ningún pavo cuando lo solicitamos. Por eso recibimos el último mensaje {<0.51.0>,not_found}.

Concurrencia en Erlang parte 4

Vamos a ver las tres primitivas necesarias para la concurrencia en Erlang: generar nuevos procesos, enviar mensajes y recibir mensajes. En la práctica, se requieren más mecanismos para crear aplicaciones realmente confiables, pero por ahora esto será suficiente.

Me he saltado mucho el tema y todavía tengo que explicar qué es realmente un proceso. De hecho, no es más que una función. Eso es todo. Ejecuta una función y, una vez que termina, desaparece. Técnicamente, un proceso también tiene algún estado oculto (como un buzón para mensajes), pero las funciones son suficientes por ahora.

Para iniciar un nuevo proceso, Erlang proporciona la función spawn/1, que toma una sola función y la ejecuta:

1> F = fun() -> 2 + 2 end.

#Fun<erl_eval.20.67289768>

2> spawn(F).

<0.44.0>

El resultado de spawn/1 (<0.44.0>) se denomina Identificador de proceso, que la comunidad suele escribir simplemente PID, Pid o pid. El identificador de proceso es un valor arbitrario que representa cualquier proceso que exista (o pueda haber existido) en algún momento de la vida de la máquina virtual. Se utiliza como una dirección para comunicarse con el proceso.

Notarás que no podemos ver el resultado de la función F. Solo obtenemos su pid. Esto se debe a que los procesos no devuelven nada. ¿Cómo podemos ver entonces el resultado de F? Bueno, hay dos formas. La más fácil es simplemente mostrar lo que obtenemos:

3> spawn(fun() -> io:format("~p~n",[2 + 2]) end).

4

<0.46.0>

Esto no es práctico para un programa real, pero es útil para ver cómo Erlang distribuye los procesos. Afortunadamente, usar io:format/2 es suficiente para permitirnos experimentar. Iniciaremos 10 procesos muy rápido y pausaremos cada uno de ellos por un tiempo con la ayuda de la función timer:sleep/1, que toma un valor entero N y espera N milisegundos antes de reanudar el código. Después del retraso, se muestra el valor presente en el proceso.

4> G = fun(X) -> timer:sleep(10), io:format("~p~n", [X]) end.

#Fun<erl_eval.6.13229925>

5> [spawn(fun() -> G(X) end) || X <- lists:seq(1,10)].

[<0.273.0>,<0.274.0>,<0.275.0>,<0.276.0>,<0.277.0>,

 <0.278.0>,<0.279.0>,<0.280.0>,<0.281.0>,<0.282.0>]

2   

1   

4   

3   

5   

8   

7   

6   

10  

9   

El orden no tiene sentido. Bienvenido al paralelismo. Debido a que los procesos se ejecutan al mismo tiempo, el orden de los eventos ya no está garantizado. Esto se debe a que la máquina virtual Erlang utiliza muchos trucos para decidir cuándo ejecutar un proceso u otro, asegurándose de que cada uno tenga una buena parte del tiempo. Muchos servicios de Erlang se implementan como procesos, incluido el shell en el que está escribiendo. Sus procesos deben equilibrarse con los que necesita el propio sistema y esta podría ser la causa del orden extraño.

Los resultados son similares independientemente de si el multiprocesamiento simétrico está habilitado o no. Para comprobarlo, puede probarlo iniciando la máquina virtual Erlang con $ erl -smp disable

Para ver si su máquina virtual Erlang se ejecuta con o sin soporte SMP en primer lugar, inicie una nueva máquina virtual sin ninguna opción y busque la salida de la primera línea. Si puede ver el texto [smp:2:2] [rq:2], significa que está ejecutando con SMP habilitado y que tiene 2 colas de ejecución (rq o programadores) ejecutándose en dos núcleos. Si solo ve [rq:1], significa que está ejecutando con SMP deshabilitado.

Si desea saberlo, [smp:2:2] significa que hay dos núcleos disponibles, con dos programadores. [rq:2] significa que hay dos colas de ejecución activas. En versiones anteriores de Erlang, podía tener varios programadores, pero con solo una cola de ejecución compartida. Desde R13B, hay una cola de ejecución por programador de manera predeterminada; esto permite un mejor paralelismo.

Para demostrar que el shell en sí está implementado como un proceso regular, usaré el BIF self/0, que devuelve el pid del proceso actual:

6> self().

<0.41.0>

7> exit(self()).

** exception exit: <0.41.0>

8> self().

<0.285.0>

Y el pid cambia porque el proceso se ha reiniciado. Los detalles de cómo funciona esto se verán más adelante. Por ahora, hay cosas más básicas que cubrir. La más importante en este momento es averiguar cómo enviar mensajes, porque nadie quiere quedarse atascado con la salida de los valores resultantes de los procesos todo el tiempo y luego ingresarlos manualmente en otros procesos (al menos yo sé que no).

El siguiente primitivo necesario para realizar el paso de mensajes es el operador !, también conocido como el símbolo bang. En el lado izquierdo toma un pid y en el lado derecho toma cualquier término de Erlang. Luego, el término se envía al proceso representado por el pid, que puede acceder a él:

9> self() ! hello.

hello

El mensaje se ha colocado en el buzón del proceso, pero aún no se ha leído. El segundo saludo que se muestra aquí es el valor de retorno de la operación de envío. Esto significa que es posible enviar el mismo mensaje a muchos procesos haciendo lo siguiente:

10> self() ! self() ! double.

double

Lo cual es equivalente a self() ! (self() ! double). Una cosa a tener en cuenta sobre el buzón de un proceso es que los mensajes se guardan en el orden en que se reciben. Cada vez que se lee un mensaje, se saca del buzón. 

Para ver el contenido del buzón actual, puede usar el comando flush() mientras está en el shell:

11> flush().

Shell got hello

Shell got double

Shell got double

ok

Esta función es simplemente un atajo que muestra los mensajes recibidos. Esto significa que todavía no podemos vincular el resultado de un proceso a una variable, pero al menos sabemos cómo enviarlo de un proceso a otro y verificar si se ha recibido.

Enviar mensajes que nadie leerá es tan útil como escribir poesía emo; no mucho. Por eso necesitamos la declaración de recepción. En lugar de jugar demasiado tiempo en el shell, escribiremos un programa corto sobre los delfines para aprender sobre ellos:

-module(dolphins).

-compile(export_all).

dolphin1() ->

    receive

        do_a_flip ->

            io:format("How about no?~n");

        fish ->

            io:format("So long and thanks for all the fish!~n");

        _ ->

            io:format("Heh, we're smarter than you humans.~n")

    end.

Como puede ver, la sintaxis de receive es similar a la de case ... of. De hecho, los patrones funcionan exactamente de la misma manera, excepto que vinculan variables que provienen de mensajes en lugar de la expresión entre caso y de. Los patrones de recepción también pueden tener guards:

receive

    Pattern1 when Guard1 -> Expr1;

    Pattern2 when Guard2 -> Expr2;

    Pattern3 -> Expr3

end

Ahora podemos compilar el módulo anterior, ejecutarlo y comenzar a comunicarnos con los delfines:

11> c(dolphins).

{ok,dolphins}

12> Dolphin = spawn(dolphins, dolphin1, []).

<0.40.0>

13> Dolphin ! "oh, hello dolphin!".

Heh, we're smarter than you humans.

"oh, hello dolphin!"

14> Dolphin ! fish.                

fish

15> 

Aquí presentamos una nueva forma de generar con spawn/3. En lugar de tomar una sola función, spawn/3 toma el módulo, la función y sus argumentos como sus propios argumentos. Una vez que la función se está ejecutando, ocurren los siguientes eventos:

1. La función llega a la declaración de recepción. Dado que el buzón del proceso está vacío, nuestro delfín espera hasta que recibe un mensaje;
2. Se recibe el mensaje "oh, hello dolphin!". La función intenta hacer coincidir el patrón con do_a_flip. Esto falla, por lo que se intenta el patrón fish y también falla. Finalmente, el mensaje cumple con la cláusula catch-all (_) y coincide.
3. El proceso genera el mensaje "Heh, we're smarter than you humans.".

Entonces, debe notarse que si el primer mensaje que enviamos funcionó, el segundo no provocó ninguna reacción del proceso <0.40.0>. Esto se debe al hecho de que una vez que nuestra función generó "Heh, we're smarter than you humans.", finalizó y también lo hizo el proceso. Necesitaremos reiniciar el delfín:

8> f(Dolphin).    

ok

9> Dolphin = spawn(dolphins, dolphin1, []).

<0.53.0>

10> Dolphin ! fish.

So long and thanks for all the fish!

fish

Y esta vez el mensaje fish funciona. ¿No sería útil poder recibir una respuesta del delfín en lugar de tener que usar io:format/2? Por supuesto que sí (¿por qué lo pregunto?). La única manera de saber si un proceso ha recibido un mensaje es enviar una respuesta. Nuestro proceso delfín necesitará saber a quién responder. Esto funciona como lo hace con el servicio postal. Si queremos que alguien sepa que debe responder a nuestra carta, necesitamos agregar nuestra dirección. En términos de Erlang, esto se hace empaquetando el pid de un proceso en una tupla. El resultado final es un mensaje que se parece un poco a {Pid, Message}. Creemos una nueva función delfín que acepte dichos mensajes:

dolphin2() ->

    receive

        {From, do_a_flip} ->

            From ! "How about no?";

        {From, fish} ->

            From ! "So long and thanks for all the fish!";

        _ ->

            io:format("Heh, we're smarter than you humans.~n")

    end.

Como puede ver, en lugar de aceptar do_a_flip y buscar mensajes, ahora necesitamos una variable From. Ahí es donde irá el identificador del proceso.

11> c(dolphins).

{ok,dolphins}

12> Dolphin2 = spawn(dolphins, dolphin2, []).

<0.65.0>

13> Dolphin2 ! {self(), do_a_flip}.          

{<0.32.0>,do_a_flip}

14> flush().

Shell got "How about no?"

ok

Parece funcionar bastante bien. Podemos recibir respuestas a los mensajes que enviamos (necesitamos agregar una dirección a cada mensaje), pero aún necesitamos iniciar un nuevo proceso para cada llamada. La recursión es la forma de resolver este problema. Solo necesitamos que la función se llame a sí misma para que nunca finalice y siempre espere más mensajes. Aquí hay una función dolphin3/0 que pone esto en práctica:

dolphin3() ->

    receive

        {From, do_a_flip} ->

            From ! "How about no?",

            dolphin3();

        {From, fish} ->

            From ! "So long and thanks for all the fish!";

        _ ->

            io:format("Heh, we're smarter than you humans.~n"),

            dolphin3()

    end.

Aquí, la cláusula catch-all y la cláusula do_a_flip se repiten con la ayuda de dolphin3/0. Tenga en cuenta que la función no hará estallar la pila porque es recursiva de cola. Mientras solo se envíen estos mensajes, el proceso dolphin se repetirá indefinidamente. Sin embargo, si enviamos el mensaje fish, el proceso se detendrá:

15> Dolphin3 = spawn(dolphins, dolphin3, []).

<0.75.0>

16> Dolphin3 ! Dolphin3 ! {self(), do_a_flip}.

{<0.32.0>,do_a_flip}

17> flush().

Shell got "How about no?"

Shell got "How about no?"

ok

18> Dolphin3 ! {self(), unknown_message}.     

Heh, we're smarter than you humans.

{<0.32.0>,unknown_message}

19> Dolphin3 ! Dolphin3 ! {self(), fish}.

{<0.32.0>,fish}

20> flush().

Shell got "So long and thanks for all the fish!"

ok

Y eso debería ser todo para dolphins.erl. Como puede ver, respeta nuestro comportamiento esperado de responder una vez por cada mensaje y seguir adelante después, excepto por el llamado con el mensaje fish. El delfín se hartó de nuestras locas payasadas humanas y nos dejó para siempre.

Concurrencia en Erlang parte 3

La dificultad de obtener un escalado lineal no se debe al lenguaje en sí, sino a la naturaleza de los problemas a resolver. A menudo se dice que los problemas que escalan muy bien son vergonzosamente paralelos. Si buscas problemas vergonzosamente paralelos en Internet, es probable que encuentres ejemplos como el trazado de rayos (un método para crear imágenes en 3D), búsquedas de fuerza bruta en criptografía, predicción meteorológica, etc.

De vez en cuando, aparecen personas en canales de IRC, foros o listas de correo preguntando si Erlang podría usarse para resolver ese tipo de problema, o si podría usarse para programar en una GPU. La respuesta es casi siempre "no". La razón es relativamente simple: todos estos problemas suelen tratarse de algoritmos numéricos con mucho procesamiento de datos. Erlang no es muy bueno en esto.

Los problemas vergonzosamente paralelos de Erlang están presentes en un nivel superior. Por lo general, tienen que ver con conceptos como servidores de chat, conmutadores telefónicos, servidores web, colas de mensajes, rastreadores web o cualquier otra aplicación donde el trabajo realizado se pueda representar como entidades lógicas independientes (actores). Este tipo de problema se puede resolver de manera eficiente con un escalamiento casi lineal.

Muchos problemas nunca mostrarán tales propiedades de escalamiento. De hecho, solo se necesita una secuencia centralizada de operaciones para perderlo todo. Su programa paralelo solo va tan rápido como su parte secuencial más lenta. Un ejemplo de ese fenómeno se puede observar cada vez que va a un centro comercial. Cientos de personas pueden estar comprando a la vez, sin que rara vez interfieran entre sí. Luego, una vez que llega el momento de pagar, se forman colas tan pronto como hay menos cajeros que clientes listos para irse.

Sería posible agregar cajeros hasta que haya uno para cada cliente, pero luego necesitaría una puerta para cada cliente porque no podrían entrar o salir del centro comercial todos a la vez.

Dicho de otro modo, aunque los clientes pudieran elegir cada uno de sus artículos en paralelo y básicamente tardar tanto tiempo en comprar como si estuvieran solos o miles en la tienda, igualmente tendrían que esperar para pagar. Por lo tanto, su experiencia de compra nunca puede ser más corta que el tiempo que les lleva esperar en la cola y pagar.

Una generalización de este principio se denomina Ley de Amdahl. Indica cuánta aceleración puede esperar que tenga su sistema cada vez que le añada paralelismo, y en qué proporción:

Según la Ley de Amdahl, el código que es 50% paralelo nunca puede volverse más rápido que el doble de lo que era antes, y teóricamente se puede esperar que el código que es 95% paralelo sea aproximadamente 20 veces más rápido si se añaden suficientes procesadores. Lo interesante es que deshacerse de las últimas partes secuenciales de un programa permite una aceleración teórica relativamente grande en comparación con la eliminación de la misma cantidad de código secuencial en un programa que no es muy paralelo para empezar.

El paralelismo no es la respuesta a todos los problemas. En algunos casos, el uso del paralelismo incluso ralentizará su aplicación. Esto puede suceder siempre que su programa sea 100% secuencial, pero aún utilice múltiples procesos.

Uno de los mejores ejemplos de esto es el benchmark de anillo. Un benchmark de anillo es una prueba en la que muchos miles de procesos pasarán un fragmento de datos uno tras otro de manera circular. Piense en ello como un juego de teléfono si lo desea. En este benchmark, solo un proceso a la vez hace algo útil, pero la máquina virtual Erlang aún dedica tiempo a distribuir la carga entre los núcleos y a darle a cada proceso su parte de tiempo.

Esto juega en contra de muchas optimizaciones de hardware comunes y hace que la máquina virtual dedique tiempo a hacer cosas inútiles. Esto suele provocar que las aplicaciones puramente secuenciales se ejecuten mucho más lentamente en muchos núcleos que en uno solo. En este caso, deshabilitar el multiprocesamiento simétrico ($ erl -smp deshabilitar) puede ser una buena idea.

Concurrencia en Erlang parte 2

En su día, el desarrollo de Erlang como lenguaje fue extremadamente rápido y recibía comentarios frecuentes de los ingenieros que trabajaban en los conmutadores telefónicos de Erlang. Estas interacciones demostraron que la concurrencia basada en procesos y el paso asincrónico de mensajes eran una buena forma de modelar los problemas a los que se enfrentaban. Además, el mundo de la telefonía ya tenía cierta cultura que favorecía la concurrencia antes de que Erlang existiera. Esto se heredó de PLEX, un lenguaje creado anteriormente en Ericsson, y de AXE, un conmutador desarrollado con él. Erlang siguió esta tendencia e intentó mejorar las herramientas disponibles anteriormente.

Erlang tenía algunos requisitos que satisfacer antes de ser considerado bueno. Los principales eran poder escalar y dar soporte a muchos miles de usuarios en muchos conmutadores, y luego lograr una alta confiabilidad, hasta el punto de no detener nunca el código.

Escalabilidad: Me centraré primero en la escalabilidad. Algunas propiedades se consideraron necesarias para lograr la escalabilidad. Como los usuarios se representarían como procesos que solo reaccionan ante ciertos eventos (por ejemplo, recibir una llamada, colgar, etc.), un sistema ideal soportaría procesos que realizan pequeños cálculos y cambian entre ellos muy rápidamente a medida que se producen los eventos. Para que sea eficiente, tenía sentido que los procesos se iniciaran muy rápidamente, se destruyeran muy rápidamente y se pudieran cambiar realmente rápido. Para lograr esto era obligatorio que fueran livianos. También era obligatorio porque no querías tener cosas como grupos de procesos (una cantidad fija de procesos entre los que dividir el trabajo). En cambio, sería mucho más fácil diseñar programas que pudieran usar tantos procesos como necesiten.

Otro aspecto importante de la escalabilidad es poder eludir las limitaciones de tu hardware. Hay dos formas de hacer esto: mejorar el hardware o agregar más hardware. La primera opción es útil hasta cierto punto, después del cual se vuelve extremadamente costosa (por ejemplo, comprar una supercomputadora). La segunda opción suele ser más barata y requiere que agregues más computadoras para hacer el trabajo. Aquí es donde puede ser útil tener la distribución como parte de tu lenguaje.

De todos modos, para volver a los procesos pequeños, debido a que las aplicaciones de telefonía necesitaban mucha fiabilidad, se decidió que la forma más limpia de hacer las cosas era prohibir que los procesos compartieran memoria. La memoria compartida podía dejar las cosas en un estado inconsistente después de algunos fallos (especialmente en los datos compartidos entre diferentes nodos) y tenía algunas complicaciones. En cambio, los procesos deberían comunicarse enviando mensajes donde se copian todos los datos. Esto podría ser más lento, pero más seguro.

Tolerancia a fallos: Esto nos lleva al segundo tipo de requisitos para Erlang: la fiabilidad. Los primeros escritores de Erlang siempre tuvieron en cuenta que los fallos son comunes. Puedes intentar evitar los errores todo lo que quieras, pero la mayoría de las veces algunos de ellos seguirán ocurriendo. En el caso de que los errores no ocurran, nada puede detener los fallos de hardware todo el tiempo. La idea es, por tanto, encontrar buenas formas de manejar los errores y los problemas en lugar de intentar evitarlos todos.

Resulta que adoptar el enfoque de diseño de múltiples procesos con paso de mensajes fue una buena idea, porque el manejo de errores se podía incorporar en él con relativa facilidad. Tomemos como ejemplo los procesos livianos (creados para reinicios y apagados rápidos). Algunos estudios demostraron que las principales fuentes de tiempo de inactividad en sistemas de software a gran escala son errores intermitentes o transitorios (fuente). Luego, existe un principio que dice que los errores que corrompen los datos deben hacer que la parte defectuosa del sistema muera lo más rápido posible para evitar propagar errores y datos incorrectos al resto del sistema. Otro concepto aquí es que existen muchas formas diferentes para que un sistema termine, dos de las cuales son apagados limpios y fallas (que terminan con un error inesperado).

Aquí, el peor caso es obviamente la falla. Una solución segura sería asegurarse de que todas las fallas sean iguales a los apagados limpios: esto se puede hacer a través de prácticas como la no compartición de datos y la asignación única (que aísla la memoria de un proceso), evitar bloqueos (un bloqueo podría no desbloquearse durante una falla, lo que evitaría que otros procesos accedan a los datos o dejaría los datos en un estado inconsistente) y otras cosas que no cubriré más, pero que eran todas parte del diseño de Erlang. La solución ideal en Erlang es, por tanto, matar los procesos lo más rápido posible para evitar la corrupción de datos y los errores transitorios. Los procesos ligeros son un elemento clave en esto. Otros mecanismos de manejo de errores también forman parte del lenguaje para permitir que los procesos monitoreen otros procesos, con el fin de saber cuándo mueren los procesos y decidir qué hacer al respecto.

Suponiendo que reiniciar los procesos muy rápido sea suficiente para lidiar con los fallos, el siguiente problema que se presenta son los fallos de hardware. ¿Cómo se asegura de que su programa siga funcionando cuando alguien patea la computadora en la que se está ejecutando?  La idea es simplemente que el programa se ejecute en más de una computadora a la vez, algo que era necesario para escalar de todos modos. Esta es otra ventaja de los procesos independientes sin canal de comunicación fuera del paso de mensajes. Puedes hacer que funcionen de la misma manera ya sea que estén en una computadora local o en otra, lo que hace que la tolerancia a fallas a través de la distribución sea casi transparente para el programador.

El hecho de estar distribuido tiene consecuencias directas en cómo los procesos pueden comunicarse entre sí. Uno de los mayores obstáculos de la distribución es que no puedes asumir que, porque un nodo (una computadora remota) estaba allí cuando realizaste una llamada de función, seguirá estando allí durante toda la transmisión de la llamada o que incluso la ejecutará correctamente. Si alguien se tropieza con un cable o desenchufa la máquina, tu aplicación se quedará colgada. O tal vez se bloqueará. ¿Quién sabe?

Bueno, resulta que la elección del paso de mensajes asincrónico también fue una buena elección de diseño. En el modelo de procesos con mensajes asincrónicos, los mensajes se envían de un proceso a otro y se almacenan en un buzón dentro del proceso receptor hasta que se extraen para leerlos. Es importante mencionar que los mensajes se envían sin siquiera verificar si el proceso receptor existe o no, porque no sería útil hacerlo. Como se implica en el párrafo anterior, es imposible saber si un proceso se bloqueará entre el momento en que se envía y se recibe un mensaje. Y si se recibe, es imposible saber si se actuará en consecuencia o, nuevamente, si el proceso receptor morirá antes de eso. Los mensajes asincrónicos permiten llamadas de funciones remotas seguras porque no se supone qué sucederá; el programador es quien debe saberlo. Si necesita tener una confirmación de entrega, debe enviar un segundo mensaje como respuesta al proceso original. Este mensaje tendrá la misma semántica segura, y también la tendrá cualquier programa o biblioteca que cree sobre este principio.

Implementación: Bien, se decidió que los procesos livianos con paso de mensajes asincrónicos eran el enfoque a adoptar para Erlang. ¿Cómo hacer que esto funcione? En primer lugar, no se puede confiar en el sistema operativo para que se encargue de los procesos. Los sistemas operativos tienen muchas formas diferentes de gestionar los procesos y su rendimiento varía mucho. La mayoría, si no todos, son demasiado lentos o demasiado pesados ​​para lo que necesitan las aplicaciones estándar de Erlang. Al hacer esto en la máquina virtual, los implementadores de Erlang mantienen el control de la optimización y la fiabilidad. Hoy en día, los procesos de Erlang ocupan unas 300 palabras de memoria cada uno y se pueden crear en cuestión de microsegundos, algo que no se puede hacer en los principales sistemas operativos de la actualidad.

Las colas de ejecución de Erlang en los núcleos: Para gestionar todos estos procesos potenciales que podrían crear sus programas, la máquina virtual inicia un hilo por núcleo que actúa como programador. Cada uno de estos programadores tiene una cola de ejecución, o una lista de procesos de Erlang en los que dedicar una parte del tiempo. Cuando uno de los programadores tiene demasiadas tareas en su cola de ejecución, algunas se migran a otra. Es decir, cada máquina virtual de Erlang se encarga de realizar todo el equilibrio de carga y el programador no tiene que preocuparse por ello. Se realizan otras optimizaciones, como limitar la velocidad a la que se pueden enviar mensajes en procesos sobrecargados para regular y distribuir la carga.

Todo el material pesado está ahí, administrado. Eso es lo que hace que sea fácil trabajar en paralelo con Erlang. Trabajar en paralelo significa que el programa debería funcionar el doble de rápido si agrega un segundo núcleo, cuatro veces más rápido si hay 4 más y así sucesivamente, ¿cierto? Depende. Este fenómeno se denomina escalamiento lineal en relación con la ganancia de velocidad en comparación con la cantidad de núcleos o procesadores. En la vida real, no existe nada gratis.

Concurrencia en Erlang

Antes que nada, creo que es importante definir la diferencia entre concurrencia y paralelismo. En muchos lugares, ambas palabras se refieren al mismo concepto. A menudo se usan como dos ideas diferentes en el contexto de Erlang. Para muchos erlangeros, la concurrencia se refiere a la idea de tener muchos actores ejecutándose de forma independiente, pero no necesariamente todos al mismo tiempo. El paralelismo es tener actores ejecutándose exactamente al mismo tiempo. Diré que no parece haber ningún consenso sobre tales definiciones en varias áreas de la informática, pero las usaré de esta manera en este texto. No se sorprenda si otras fuentes o personas usan los mismos términos para referirse a cosas diferentes.

Esto quiere decir que Erlang tenía concurrencia desde el principio, incluso cuando todo se hacía en un procesador de un solo núcleo en los años 80. Cada proceso de Erlang tenía su propio tiempo para ejecutarse, de forma muy similar a las aplicaciones de escritorio antes de los sistemas multinúcleo.

El paralelismo todavía era posible en ese entonces; todo lo que se necesitaba hacer era tener una segunda computadora ejecutando el código y comunicándose con la primera. Incluso entonces, solo se podían ejecutar dos actores en paralelo en esta configuración. Hoy en día, los sistemas multinúcleo permiten el paralelismo en una sola computadora (algunos chips industriales tienen muchas docenas de núcleos) y Erlang aprovecha al máximo esta posibilidad.

La distinción entre concurrencia y paralelismo es importante, porque muchos programadores creen que Erlang estaba listo para las computadoras multinúcleo años antes de que realmente lo estuviera. Erlang se adaptó al multiprocesamiento simétrico verdadero recién a mediados de la década de 2000 y recién logró implementar la mayor parte de la información correctamente con la versión R13B del lenguaje en 2009. Antes de eso, a menudo era necesario deshabilitar SMP para evitar pérdidas de rendimiento. Para obtener paralelismo en una computadora multinúcleo sin SMP, se debían iniciar muchas instancias de la máquina virtual.

Un hecho interesante es que, debido a que la concurrencia de Erlang se basa en procesos aislados, no fue necesario ningún cambio conceptual a nivel de lenguaje para lograr un paralelismo verdadero en el lenguaje. Todos los cambios se realizaron de manera transparente en la máquina virtual, fuera de la vista de los programadores.

Colas en Erlang

 

El módulo de queue implementa una cola FIFO (First In, First Out) de dos extremos.

El módulo de queue básicamente tiene diferentes funciones en una separación mental en 3 interfaces (o API) de complejidad variable, llamadas API original, API extendida y API de Okasaki:

La API original contiene las funciones en la base del concepto de colas, incluyendo: new/0, para crear colas vacías, in/2, para insertar nuevos elementos, out/1, para eliminar elementos, y luego funciones para convertir a listas, invertir la cola, ver si un valor particular es parte de ella, etc.

La API extendida principalmente agrega algo de poder de introspección y flexibilidad: le permite hacer cosas como mirar el frente de la cola sin eliminar el primer elemento (ver get/1 o peek/1), eliminar elementos sin preocuparse por ellos (drop/1), etc. Estas funciones no son esenciales para el concepto de colas, pero aún así son útiles en general.

La API de Okasaki es un poco rara. Se deriva de las estructuras de datos puramente funcionales de Chris Okasaki. La API proporciona operaciones similares a las que estaban disponibles en las dos API anteriores, pero algunos de los nombres de las funciones están escritos al revés y todo el asunto es relativamente peculiar. A menos que sepas que quieres esta API, no me molestaría en usarla.

Generalmente querrás usar colas cuando necesites asegurarte de que el primer elemento ordenado sea de hecho el primero en procesarse.

veamos un ejemplo: 

-module(queue_demo).

-export([demo/0]).

demo() ->

    % Crear una cola vacía

    Q0 = queue:new(),

    io:format("Cola inicial: ~p~n", [Q0]),

    % Agregar elementos a la cola

    Q1 = queue:in(1, Q0),

    Q2 = queue:in(2, Q1),

    Q3 = queue:in(3, Q2),

    io:format("Cola después de agregar elementos: ~p~n", [Q3]),

    % Sacar un elemento de la cola

    {ok, Element, Q4} = queue:out(Q3),

    io:format("Elemento removido: ~p~n", [Element]),

    io:format("Cola después de remover un elemento: ~p~n", [Q4]),

    % Revisar el elemento al frente sin sacarlo

    {value, PeekElement} = queue:peek(Q4),

    io:format("Elemento al frente de la cola: ~p~n", [PeekElement]),

    % Verificar si la cola está vacía

    IsEmpty = queue:is_empty(Q4),

    io:format("¿La cola está vacía? ~p~n", [IsEmpty]),

    % Obtener el tamaño de la cola

    QueueSize = queue:len(Q4),

    io:format("Tamaño de la cola: ~p~n", [QueueSize]),

    % Convertir la cola a una lista

    ListRepresentation = queue:to_list(Q4),

    io:format("Cola como lista: ~p~n", [ListRepresentation]),

    % Agregar un elemento al frente de la cola

    Q5 = queue:in_r(0, Q4),

    io:format("Cola después de agregar al frente: ~p~n", [Q5]).

Y si ejecutamos esto vamos a tener este resultado: 

Cola inicial: {[], []}

Cola después de agregar elementos: {[], [3,2,1]}

Elemento removido: 1

Cola después de remover un elemento: {[], [3,2]}

Elemento al frente de la cola: 2

¿La cola está vacía? false

Tamaño de la cola: 2

Cola como lista: [2,3]

Cola después de agregar al frente: {[0], [3,2]}

Grafos dirigidos en Erlang

Los grafos dirigidos en Erlang se implementan como dos módulos, digraph y digraph_utils. El módulo digraph básicamente permite la construcción y modificación de un grafo dirigido: manipular aristas y vértices, encontrar caminos y ciclos, etc. Por otro lado, digraph_utils permite navegar por un grafo (postorder, preorder), probar ciclos, arborescencias o árboles, encontrar vecinos, etc.

En Erlang, los grafos dirigidos se implementan utilizando los módulos digraph y digraph_utils, que forman parte de la librería estándar. Aquí tienes ejemplos de cómo usarlos:

El módulo digraph permite crear y manipular grafos. Veamos un ejemplo básico:

-module(digraph_example).

-export([create_graph/0, add_nodes_and_edges/1, print_graph/1]).

create_graph() ->

    digraph:new().

add_nodes_and_edges(Graph) ->

    % Agregar nodos

    Node1 = digraph:add_vertex(Graph, node1, "Nodo 1"),

    Node2 = digraph:add_vertex(Graph, node2, "Nodo 2"),

    Node3 = digraph:add_vertex(Graph, node3, "Nodo 3"),

    

    % Agregar aristas dirigidas

    digraph:add_edge(Graph, Node1, Node2),

    digraph:add_edge(Graph, Node2, Node3),

    digraph:add_edge(Graph, Node1, Node3),

    Graph.

print_graph(Graph) ->

    Vertices = digraph:vertices(Graph),

    Edges = digraph:edges(Graph),

    io:format("Nodos: ~p~n", [Vertices]),

    io:format("Aristas: ~p~n", [Edges]).

Veamos como podemos usarlo: 

1> c(digraph_example).

2> Graph = digraph_example:create_graph().

3> Graph = digraph_example:add_nodes_and_edges(Graph).

4> digraph_example:print_graph(Graph).

Nodos: [#Ref<0.0.0.247>,#Ref<0.0.0.248>,#Ref<0.0.0.249>]

Aristas: [#Ref<0.0.0.250>,#Ref<0.0.0.251>,#Ref<0.0.0.252>]

El módulo digraph_utils provee funciones para analizar y transformar grafos, como encontrar caminos, ciclos, o calcular componentes conexas.

find_path_example() ->

    Graph = digraph:new(),

    Node1 = digraph:add_vertex(Graph, node1),

    Node2 = digraph:add_vertex(Graph, node2),

    Node3 = digraph:add_vertex(Graph, node3),

    digraph:add_edge(Graph, Node1, Node2),

    digraph:add_edge(Graph, Node2, Node3),

    Path = digraph_utils:path(Graph, Node1, Node3),

    io:format("Camino de Node1 a Node3: ~p~n", [Path]),

    digraph:delete(Graph).

1> c(digraph_example).

2> digraph_example:find_path_example().

Camino de Node1 a Node3: [node1,node2,node3]

Para detectar ciclos en un grafo dirigido:

detect_cycle_example() ->

    Graph = digraph:new(),

    Node1 = digraph:add_vertex(Graph, node1),

    Node2 = digraph:add_vertex(Graph, node2),

    digraph:add_edge(Graph, Node1, Node2),

    digraph:add_edge(Graph, Node2, Node1),

    Cycles = digraph_utils:strong_components(Graph),

    io:format("Ciclos detectados: ~p~n", [Cycles]),

    digraph:delete(Graph).

1> digraph_example:detect_cycle_example().

Ciclos detectados: [[node1,node2]]

digraph es eficiente para representar grafos con un gran número de nodos y aristas.

digraph_utils complementa digraph con funciones analíticas, como encontrar componentes fuertes o caminos mínimos.

Debido a que los grafos dirigidos están estrechamente relacionados con la teoría de conjuntos, el módulo sofs contiene algunas funciones que permiten convertir familias en dígrafos y dígrafos en familias.

Set en Erlang

Hay 4 módulos principales para tratar con conjuntos en Erlang. Esto es un poco raro al principio, pero tiene más sentido una vez que te das cuenta de que se debe a que los implementadores acordaron que no había una "mejor" manera de construir un conjunto. Los cuatro módulos son ordsets, sets, gb_sets y sofs (conjuntos de conjuntos):

ordsets

Los ordsets se implementan como una lista ordenada. Son principalmente útiles para conjuntos pequeños, son el tipo de conjunto más lento, pero tienen la representación más simple y legible de todos los conjuntos. Hay funciones estándar para ellos como ordsets:new/0, ordsets:is_element/2, ordsets:add_element/2, ordsets:del_element/2, ordsets:union/1, ordsets:intersection/1, y muchas más.

sets

Sets (el módulo) se implementa sobre una estructura muy similar a la que se usa en dict. Implementan la misma interfaz que ordsets, pero se escalarán mucho mejor. Al igual que los diccionarios, son especialmente buenos para manipulaciones de lectura intensiva, como verificar si algún elemento es parte del conjunto o no.

gb_sets

Los gb_sets en sí se construyen sobre una estructura de árbol general equilibrado similar a la que se usa en el módulo gb_trees. gb_sets es a los conjuntos lo que gb_tree es a dict; una implementación que es más rápida al considerar operaciones diferentes a la lectura, lo que le permite tener más control. Si bien gb_sets implementa la misma interfaz que sets y ordsets, también agrega más funciones. Al igual que gb_trees, tiene funciones inteligentes contra ingenuas, iteradores, acceso rápido a los valores más pequeños y más grandes, etc.

sofs

Los conjuntos de conjuntos (sofs) se implementan con listas ordenadas, pegadas dentro de una tupla con algunos metadatos. Son el módulo que se debe usar si desea tener control total sobre las relaciones entre conjuntos, familias, imponer tipos de conjuntos, etc. Son realmente lo que desea si necesita un concepto matemático en lugar de "solo" grupos de elementos únicos.

Si bien tal variedad puede verse como algo grandioso, algunos detalles de implementación pueden ser francamente frustrantes. Como ejemplo, gb_sets, ordsets y sofs usan el operador == para comparar valores: si tiene los números 2 y 2.0, ambos terminarán siendo vistos como el mismo.

Sin embargo, sets (el módulo) utiliza el operador =:=, lo que significa que no necesariamente puedes cambiar de implementación como desees. Hay casos en los que necesitas un comportamiento preciso y, en ese punto, puedes perder el beneficio de tener múltiples implementaciones.

Es un poco confuso tener tantas opciones disponibles. Björn Gustavsson, del equipo Erlang/OTP y programador de Wings3D, sugiere principalmente usar gb_sets en la mayoría de las circunstancias, usar ordset cuando necesitas una representación clara que quieres procesar con tu propio código y 'sets' cuando necesitas el operador =:= (fuente).

En cualquier caso, al igual que para los almacenes de valores clave, la mejor solución suele ser realizar una evaluación comparativa y ver qué se adapta mejor a tu aplicación.

Matrices en erlang

Pero, ¿qué sucede con el código que requiere estructuras de datos con nada más que claves numéricas? Bueno, para eso, existen las matrices. Permiten acceder a elementos con índices numéricos y plegar toda la estructura, ignorando posiblemente las ranuras no definidas.

Las matrices de Erlang, al contrario de sus contrapartes imperativas, no pueden tener cosas como inserción o búsqueda en tiempo constante. Debido a que suelen ser más lentas que las de los lenguajes que admiten la asignación destructiva y que el estilo de programación realizado con Erlang no se presta necesariamente demasiado bien a las matrices y matrices, rara vez se utilizan en la práctica.

En general, los programadores de Erlang que necesitan realizar manipulaciones de matrices y otros usos que requieren matrices tienden a utilizar conceptos llamados Puertos para dejar que otros lenguajes hagan el trabajo pesado, o C-Nodos, Linked in drivers y NIF (Experimental, R13B03+).

Las matrices también son extrañas en el sentido de que son una de las pocas estructuras de datos que tienen un índice 0 (al contrario de las tuplas o listas), junto con el índice en el módulo de expresiones regulares.

Veamos un ejemplo: 

  %% Create a fixed-size array with entries 0-9 set to 'undefined'

  A0 = array:new(10).

  10 = array:size(A0).

 

  %% Create an extendible array and set entry 17 to 'true',

  %% causing the array to grow automatically

  A1 = array:set(17, true, array:new()).

  18 = array:size(A1).

 

  %% Read back a stored value

  true = array:get(17, A1).

 

  %% Accessing an unset entry returns the default value

  undefined = array:get(3, A1).

 

  %% Accessing an entry beyond the last set entry also returns the

  %% default value, if the array does not have fixed size

  undefined = array:get(18, A1).

 

  %% "sparse" functions ignore default-valued entries

  A2 = array:set(4, false, A1).

  [{4, false}, {17, true}] = array:sparse_to_orddict(A2).

 

  %% An extendible array can be made fixed-size later

  A3 = array:fix(A2).

 

  %% A fixed-size array does not grow automatically and does not

  %% allow accesses beyond the last set entry

  {'EXIT',{badarg,_}} = (catch array:set(18, true, A3)).

  {'EXIT',{badarg,_}} = (catch array:get(18, A3)).

Estructura Key-Value en Erlang

Para pequeñas cantidades de datos, básicamente hay dos estructuras de datos que se pueden usar. La primera se llama proplist. Una proplist es cualquier lista de tuplas de la forma [{Key,Value}]. Son un tipo de estructura extraño porque no hay otra regla que esa. De hecho, las reglas son tan relajadas que la lista también puede contener valores booleanos, números enteros y lo que quieras. Sin embargo, nos interesa más la idea de una tupla con una clave y un valor en una lista. Para trabajar con proplists, puedes usar el módulo proplists. Contiene funciones como proplists: delete/2, proplists:get_value/2, proplists:get_all_values/2, proplists:lookup/2 y proplists:lookup_all/2.

Notarás que no hay ninguna función para agregar o actualizar un elemento de la lista. Esto muestra cuán vagamente definidas están las proplists como estructura de datos. Para obtener estas funcionalidades, debes construir  tu elemento manualmente ([NewElement|OldList]) y usar funciones como lists:keyreplace/4. Usar dos módulos para una pequeña estructura de datos no es lo más claro, pero debido a que las proplists están definidas de manera tan vaga, a menudo se usan para tratar con listas de configuración y descripciones generales de un elemento determinado. Las proplists no son exactamente estructuras de datos completas. Son más bien un patrón común que aparece cuando se usan listas y tuplas para representar algún objeto o elemento; el módulo proplists es una especie de caja de herramientas para este patrón.

Si desea un almacén de clave-valor más completo para pequeñas cantidades de datos, el módulo orddict es lo que necesita. Los orddicts (diccionarios ordenados) son proplists con un gusto por la formalidad. Cada clave puede estar allí una vez, la lista completa está ordenada para una búsqueda promedio más rápida, etc. Las funciones comunes para el uso de CRUD incluyen orddict:store/3, orddict:find/2 (cuando no sabe si la clave está en los diccionarios), orddict:fetch/2 (cuando sabe que está allí o que debe estar allí) y orddict:erase/2.

Los orddicts son un compromiso generalmente bueno entre complejidad y eficiencia hasta aproximadamente 75 elementos. Después de esa cantidad, deberías cambiar a diferentes almacenes de clave-valor.

Básicamente, existen dos estructuras/módulos de clave-valor para manejar mayores cantidades de datos: dicts y gb_trees. Los diccionarios tienen la misma interfaz que los orddicts: dict:store/3, dict:find/2, dict:fetch/2, dict:erase/2 y todas las demás funciones, como dict:map/2 y dict:fold/2 (¡bastante útiles para trabajar en toda la estructura de datos!). Por lo tanto, los dicts son muy buenas opciones para escalar los orddicts cuando sea necesario.

Los árboles balanceados generales, por otro lado, tienen muchas más funciones que te dejan un control más directo sobre cómo se debe usar la estructura. Básicamente, existen dos modos para gb_trees: el modo en el que conoces tu estructura al dedillo (lo llamo el "modo inteligente") y el modo en el que no puedes asumir mucho sobre ella (lo llamo el "modo ingenuo"). En el modo ingenuo, las funciones son gb_trees:enter/3, gb_trees:lookup/2 y gb_trees:delete_any/2. Las funciones inteligentes relacionadas son gb_trees:insert/3, gb_trees:get/2, gb_trees:update/3 y gb_trees:delete/2. También existe gb_trees:map/2, que siempre es una buena opción cuando la necesitas.

La desventaja de las funciones "ingenuas" sobre las "inteligentes" es que, como los gb_trees son árboles equilibrados, siempre que insertes un nuevo elemento (o elimines un montón), es posible que el árbol deba equilibrarse a sí mismo. Esto puede llevar tiempo y memoria (incluso en comprobaciones inútiles solo para asegurarse). Todas las funciones "inteligentes" suponen que la clave está presente en el árbol: esto te permite omitir todas las comprobaciones de seguridad y da como resultado tiempos más rápidos.

¿Cuándo deberías usar gb_trees en lugar de diccionarios? Bueno, no es una decisión clara. Como lo mostrará el módulo de referencia que he escrito, gb_trees y dicts tienen rendimientos algo similares en muchos aspectos. Sin embargo, la referencia demuestra que dicts tienen las mejores velocidades de lectura mientras que gb_trees tienden a ser un poco más rápidos en otras operaciones. Puede juzgar en función de sus propias necesidades cuál sería el mejor.

Ah, y otra cosa a tener en cuenta que mientras que dicts tienen una función de plegado, gb_trees no: en su lugar, tienen una función de iteración, que devuelve un fragmento del árbol en el que puede llamar a gb_trees:next(Iterator) para obtener los siguientes valores en orden. Lo que esto significa es que necesita escribir sus propias funciones recursivas sobre gb_trees en lugar de usar un genric fold. Por otro lado, gb_trees te permite tener un acceso rápido a los elementos más pequeños y más grandes de la estructura con gb_trees:smallest/1 y gb_trees:largest/1.

Por lo tanto, diría que las necesidades de tu aplicación son las que deberían determinar qué almacén de clave-valor elegir. Diferentes factores, como la cantidad de datos que tienes que almacenar, lo que necesitas hacer con ellos y demás, tienen su importancia. Mide, perfila y compara para asegurarte.

Existen algunos almacenes de clave-valor especiales para manejar recursos de diferentes tamaños. Estos almacenes son las tablas ETS, las tablas DETS y la base de datos mnesia. Sin embargo, su uso está fuertemente relacionado con los conceptos de múltiples procesos y distribución. 

A partir de la versión 17.0, el lenguaje admite un nuevo tipo de datos de clave-valor nativo, descrito en Postscript: Maps. 

Registros en Erlang

Los record de Erlang son muy parecidos a las struct en C.

Se declaran como atributos de módulo de la siguiente manera:

-module(records).

-compile(export_all).

-record(robot, {name,

                type=industrial,

                hobbies,

                details=[]}).

Aquí tenemos un registro que representa robots con 4 campos: nombre, tipo, pasatiempos y detalles. También hay un valor predeterminado para el tipo y los detalles, industrial y [], respectivamente. A continuación, se muestra cómo declarar un registro en el módulo records:

first_robot() ->

    #robot{name="Mechatron",

           type=handmade, 

           details=["Moved by a small man inside"]}.

Y ejecutando el código:

1> c(records).

{ok,records}

2> records:first_robot().

{robot,"Mechatron",handmade,undefined,

       ["Moved by a small man inside"]}

Los registros de Erlang son simplemente azúcar sintáctico sobre tuplas. Afortunadamente, hay una forma de mejorarlo. El shell de Erlang tiene un comando rr(Module) que le permite cargar definiciones de registros desde Module:

3> rr(records).

[robot]

4> records:first_robot().         

#robot{name = "Mechatron",type = handmade,

       hobbies = undefined,

       details = ["Moved by a small man inside"]}

Esto hace que sea mucho más fácil trabajar con registros de esa manera. Notarás que en first_robot/0, no habíamos definido el campo de pasatiempos y no tenía un valor predeterminado en su declaración. Erlang, por defecto, establece el valor como indefinido.

Para ver el comportamiento de los valores predeterminados que establecimos en la definición del robot, compilemos la siguiente función:

car_factory(CorpName) ->

    #robot{name=CorpName, hobbies="building cars"}.

Y ejecutalo:

5> c(records).

{ok,records}

6> records:car_factory("Jokeswagen").

#robot{name = "Jokeswagen",type = industrial,

       hobbies = "building cars",details = []}

Y tenemos un robot industrial al que le gusta pasar el tiempo construyendo coches.

La función rr() puede tomar más que un nombre de módulo: puede tomar un comodín (como rr("*")) y también una lista como segundo argumento para especificar qué registros cargar.

Hay algunas otras funciones para manejar registros en el shell: rd(Name, Definition) le permite definir un registro de una manera similar a la función -record(Name, Definition) utilizada en nuestro módulo. Puede usar rf() para "descargar" todos los registros, o rf(Name) o rf([Names]) para deshacerse de definiciones específicas.

Puede usar rl() para imprimir todas las definiciones de registros de una manera que pueda copiar y pegar en el módulo o usar rl(Name) o rl([Names]) para restringirlo a registros específicos.

Por último, rp(Term) le permite convertir una tupla en un registro (siempre que exista la definición).

Escribir registros por sí solo no hará mucho. Necesitamos una manera de extraer valores de ellos. Básicamente, hay dos maneras de hacer esto. El primero tiene una "sintaxis de punto" especial. Suponiendo que tiene cargada la definición de registro para robots:

5> Crusher = #robot{name="Crusher", hobbies=["Crushing people","petting cats"]}. 

#robot{name = "Crusher",type = industrial,

       hobbies = ["Crushing people","petting cats"],

       details = []}

6> Crusher#robot.hobbies.

["Crushing people","petting cats"]

No es una sintaxis muy bonita. Esto se debe a la naturaleza de los registros como tuplas. Como son solo una especie de truco del compilador, tienes que mantener las palabras claves para definir qué registro va con qué variable, de ahí la parte #robot de Crusher#robot.hobbies. Es triste, pero no hay forma de evitarlo. Peor aún, los registros anidados se vuelven bastante feos:

7> NestedBot = #robot{details=#robot{name="erNest"}}.

#robot{name = undefined, type = industrial,

       hobbies = undefined,

       details = #robot{name = "erNest",type = industrial,

                        hobbies = undefined,details = []}}

8> (NestedBot#robot.details)#robot.name. 

"erNest"

Para mostrar aún más la dependencia de los registros en las tuplas, veamos :

9> #robot.type.

3

Lo que esto genera es qué elemento de la tupla subyacente es.

Una característica de ahorro de los registros es la posibilidad de usarlos en los encabezados de funciones para hacer coincidir patrones y también en los guards. Declare un nuevo registro de la siguiente manera en la parte superior del archivo y luego agregue las funciones debajo:

-record(user, {id, name, group, age}).

%% use pattern matching to filter

admin_panel(#user{name=Name, group=admin}) ->

    Name ++ " is allowed!";

admin_panel(#user{name=Name}) ->

    Name ++ " is not allowed".

%% can extend user without problem

adult_section(U = #user{}) when U#user.age >= 18 ->

    %% Show stuff that can't be written in such a text

    allowed;

adult_section(_) ->

    %% redirect to sesame street site

    forbidden.

Esto nos permite ver que no es necesario hacer coincidir todas las partes de la tupla o incluso saber cuántas hay al escribir la función: solo podemos hacer coincidir la edad o el grupo si es lo que se necesita y olvidarnos del resto de la estructura. Si utilizáramos una tupla normal, la definición de la función podría tener que parecerse un poco a function({record, _, _, ICareAboutThis, _, _}) -> .... Entonces, cada vez que alguien decida agregar un elemento a la tupla, alguien más (probablemente enojado por todo esto) tendría que ir y actualizar todas las funciones donde se usa esa tupla.

La siguiente función ilustra cómo actualizar un registro (de lo contrario, no serían muy útiles):

repairman(Rob) ->

    Details = Rob#robot.details,

    NewRob = Rob#robot{details=["Repaired by repairman"|Details]},

    {repaired, NewRob}.

Y luego:

16> c(records).

{ok,records}

17> records:repairman(#robot{name="Ulbert", hobbies=["trying to have feelings"]}).

{repaired,#robot{name = "Ulbert",type = industrial,

                 hobbies = ["trying to have feelings"],

                 details = ["Repaired by repairman"]}}

Y puedes ver que mi robot ha sido reparado. La sintaxis para actualizar registros es un poco especial aquí. Parece que estamos actualizando el registro en su lugar (Rob#robot{Field=NewValue}) pero todo es un truco del compilador para llamar a la función subyacente erlang:setelement/3.

Una última cosa sobre los registros. Debido a que son bastante útiles y la duplicación de código es molesta, los programadores de Erlang comparten registros con frecuencia entre módulos con la ayuda de archivos de encabezado. Los archivos de encabezado de Erlang son bastante similares a su contraparte de C: no son más que un fragmento de código que se agrega al módulo como si estuviera escrito allí en primer lugar. Crea un archivo llamado records.hrl con el siguiente contenido:

%% this is a .hrl (header) file.

-record(included, {some_field,

                   some_default = "yeah!",

                   unimaginative_name}).

Para incluirlo en records.erl, simplemente agregue la siguiente línea al módulo:

-include("records.hrl").

Y luego la siguiente función para probarlo:

included() -> #included{some_field="Some value"}.

Ahora, pruébalo como siempre:

18> c(records).

{ok,records}

19> rr(records).

[included,robot,user]

20> records:included().

#included{some_field = "Some value",some_default = "yeah!",

          unimaginative_name = undefined}

Eso es todo sobre los registros; son feos pero útiles. Su sintaxis no es bonita, no son gran cosa, pero son relativamente importantes para la capacidad de mantenimiento de su código.

A menudo verá software de código abierto que utiliza el método que se muestra aquí de tener un archivo .hrl para todo el proyecto para los registros que se comparten entre todos los módulos. Si bien me sentí obligado a documentar este uso, recomiendo enfáticamente que mantenga todas las definiciones de registros locales, dentro de un módulo. Si desea que algún otro módulo observe las entrañas de un registro, escriba funciones para acceder a sus campos y mantenga sus detalles lo más privados posible. Esto ayuda a prevenir conflictos de nombres, evita problemas al actualizar el código y, en general, mejora la legibilidad y la capacidad de mantenimiento de su código.

Elixir: Concurrencia Hecha Sencilla

Elixir, basado en la máquina virtual de Erlang (BEAM), utiliza el modelo de actores como su paradigma de concurrencia. Este modelo permite manejar múltiples procesos de manera eficiente y segura, lo que lo hace ideal para sistemas distribuidos y concurrentes.

El modelo de actores es un paradigma de concurrencia en el que las entidades llamadas actores:

• Son unidades independientes de ejecución.
• Tienen su propio estado y no comparten memoria con otros actores.
• Se comunican mediante el envío de mensajes.

En Elixir, los procesos son implementaciones del modelo de actores y son extremadamente ligeros gracias a la eficiencia de la VM de Erlang.

En Elixir, los actores se implementan utilizando módulos como GenServer. Vamos a crear un ejemplo básico de un contador que incrementa su valor en respuesta a mensajes.

   defmodule Counter do

     use GenServer

     # Inicio del actor con un estado inicial

     def start_link(initial_value) do

       GenServer.start_link(__MODULE__, initial_value, name: __MODULE__)

     end

     # Callbacks

     def init(initial_value) do

       {:ok, initial_value}

     end

     # Manejar el mensaje para incrementar el contador

     def handle_call(:increment, _from, state) do

       {:reply, state + 1, state + 1}

     end

     def handle_call(:get, _from, state) do

       {:reply, state, state}

     end

   end

   # Iniciar el actor con un valor inicial de 0

   {:ok, _pid} = Counter.start_link(0)

   # Incrementar el contador

   Counter.call(:increment) # Devuelve 1

   Counter.call(:increment) # Devuelve 2

   # Obtener el valor actual

   Counter.call(:get) # Devuelve 2

Ahora crearemos múltiples actores que se comuniquen entre sí. Supongamos que tenemos un sistema donde un actor recopila datos y otro los procesa.

   defmodule DataCollector do

     use GenServer

     def start_link(processor_pid) do

       GenServer.start_link(__MODULE__, processor_pid, name: __MODULE__)

     end

     def init(processor_pid) do

       {:ok, processor_pid}

     end

     def handle_cast({:collect, data}, processor_pid) do

       send(processor_pid, {:process, data})

       {:noreply, processor_pid}

     end

   end

 

   defmodule DataProcessor do

     use GenServer

     def start_link(_) do

       GenServer.start_link(__MODULE__, [], name: __MODULE__)

     end

     def init(_) do

       {:ok, []}

     end

     def handle_info({:process, data}, state) do

       IO.puts("Procesando: #{data}")

       {:noreply, [data | state]}

     end

   end

   {:ok, processor_pid} = DataProcessor.start_link([])

   {:ok, collector_pid} = DataCollector.start_link(processor_pid)

   GenServer.cast(collector_pid, {:collect, "dato1"})

   GenServer.cast(collector_pid, {:collect, "dato2"})

DataCollector recopila datos y los envía a DataProcessor. DataProcessor procesa los datos recibidos y los guarda en su estado.

Como ventaja del modelo de actores tenemos:

Aislamiento Total: Los actores no comparten memoria, eliminando condiciones de carrera.

Escalabilidad: Los procesos son livianos y se ejecutan de manera concurrente.

Resiliencia: Si un actor falla, el sistema no se detiene; los supervisores pueden reiniciarlo.

El modelo de actores de Elixir proporciona una forma poderosa, segura y eficiente de manejar concurrencia. Al entender cómo implementar actores y supervisarlos, puedes construir sistemas robustos que escalen sin problemas.

De Heathrow a Londres con Erlang

Estás en un avión que aterrizará en el aeropuerto de Heathrow en las próximas horas. Tienes que llegar a Londres lo más rápido posible; tu tío rico se está muriendo y quieres ser el primero en llegar para reclamar su herencia.

Hay dos carreteras que van de Heathrow a Londres y un montón de calles más pequeñas que las unen. Debido a los límites de velocidad y al tráfico habitual, algunas partes de las carreteras y calles más pequeñas requieren más tiempo que otras. Antes de aterrizar, decides maximizar tus posibilidades encontrando el camino óptimo hacia su casa. Aquí tienes el mapa que has encontrado en tu portátil:

Un pequeño mapa con una carretera principal 'A' con 4 segmentos de longitud 50, 5, 40 y 10, B con 4 segmentos de longitud 10, 90, 2 y 8, donde cada uno de estos segmentos está unido por caminos 'X' de longitud 30, 20, 25 y 0.

Para que te resulte más fácil trabajar con el mapa, ingresas los datos de la siguiente manera en un archivo llamado road.txt:

50

10

30

5

90

20

40

2

25

10

8

0

La carretera está trazada según el siguiente patrón: A1, B1, X1, A2, B2, X2, ..., An, Bn, Xn, donde X es una de las carreteras que une el lado A con el lado B del mapa. Insertamos un 0 como último segmento X, porque no importa lo que hagamos, ya estamos en nuestro destino. Los datos probablemente se puedan organizar en tuplas de 3 elementos (triples) de la forma {A,B,X}.

Al escribir una función recursiva, lo primero que hay que hacer es encontrar nuestro caso base. Para nuestro problema en cuestión, esto sería si tuviéramos solo una tupla para analizar, es decir, si solo tuviéramos que elegir entre A, B (y cruzar X, que en este caso es inútil porque estamos en el destino)

Entonces la elección es solo entre elegir cuál de los caminos A o B es el más corto. Si has aprendido bien la recursión, sabes que debemos intentar converger hacia el caso base. Esto significa que en cada paso que daremos, querremos reducir el problema a elegir entre A y B para el siguiente paso.

Extendamos nuestro mapa y comencemos de nuevo:

Camino A: 5, 10. Camino B: 1, 15. Camino de cruce X: 3.

¡Ah! ¡Se pone interesante! ¿Cómo podemos reducir la triple {5,1,3} a una elección estricta entre A y B? Veamos cuántas opciones son posibles para A. Para llegar a la intersección de A1 y A2 (lo llamaré el punto A1), puedo tomar la carretera A1 directamente (5), o venir desde B1 (1) y luego cruzar X1 (3). En este caso, la primera opción (5) es más larga que la segunda (4). Para la opción A, el camino más corto es [B, X]. Entonces, ¿cuáles son las opciones para B? Puedes proceder desde A1 (5) y luego cruzar X1 (3), o tomar estrictamente el camino B1 (1).

Lo que tenemos es una longitud 4 con el camino [B, X] hacia la primera intersección A y una longitud 1 con el camino [B] hacia la intersección de B1 y B2. Entonces tenemos que decidir qué elegir entre ir al segundo punto A (la intersección de A2 y el punto final o X2) y al segundo punto B (intersección de B2 y X2). Para tomar una decisión, sugiero que hagamos lo mismo que antes. 

Todos los caminos posibles a tomar en este caso se pueden encontrar de la misma manera que en el caso anterior. Podemos llegar al siguiente punto A tomando el camino A2 desde [B, X], que nos da una longitud de 14 (14 = 4 + 10), o tomando B2 y luego X2 desde [B], que nos da una longitud de 16 (16 = 1 + 15 + 0). En este caso, el camino [B, X, A] es mejor que [B, B, X].

El mismo dibujo que el anterior, pero con los caminos dibujados encima.

También podemos llegar al siguiente punto B tomando el camino A2 desde [B, X] y luego cruzando X2 por una longitud de 14 (14 = 4 + 10 + 0), o tomando la carretera B2 desde [B] por una longitud de 16 (16 = 1 + 15). Aquí, el mejor camino es elegir la primera opción, [B, X, A, X].

Entonces, cuando todo este proceso está hecho, nos quedan dos caminos, A o B, ambos de longitud 14. Cualquiera de ellos es el correcto. La última selección siempre tendrá dos caminos de la misma longitud, dado que el último segmento X tiene una longitud 0. Al resolver nuestro problema de forma recursiva, nos hemos asegurado de obtener siempre el camino más corto al final. No está mal, ¿verdad?

Teníamos listo el archivo que vamos a introducir como entrada. Para realizar manipulaciones de archivos, el módulo de archivos es nuestra mejor herramienta. Contiene muchas funciones comunes a muchos lenguajes de programación para trabajar con los archivos (establecer permisos, mover archivos, renombrarlos y eliminarlos, etc.)

También contiene las funciones habituales para leer y/o escribir desde archivos, como: file:open/2 y file:close/1 para hacer lo que dicen sus nombres (¡abrir y cerrar archivos!), file:read/2 para obtener el contenido de un archivo (ya sea como cadena o binario), file:read_line/1 para leer una sola línea, file:position/3 para mover el puntero de un archivo abierto a una posición determinada, etc.

También hay un montón de funciones de acceso directo, como file:read_file/1 (abre y lee el contenido como binario), file:consult/1 (abre y analiza un archivo como términos de Erlang) o file:pread/2 (cambia una posición y luego lee) y pwrite/2 (cambia la posición y escribe el contenido).

Con todas estas opciones disponibles, será fácil encontrar una función para leer nuestro archivo road.txt. Como sabemos que nuestra carretera es relativamente pequeña, llamaremos a file:read_file("road.txt").':

1> {ok, Binary} = file:read_file("road.txt").

{ok,<<"50\r\n10\r\n30\r\n5\r\n90\r\n20\r\n40\r\n2\r\n25\r\n10\r\n8\r\n0\r\n">>}

2> S = string:tokens(binary_to_list(Binary), "\r\n\t ").

["50","10","30","5","90","20","40","2","25","10","8","0"]

Tenga en cuenta que en este caso, agregué un espacio (" ") y una tabulación ("\t") a los tokens válidos, por lo que el archivo también podría haberse escrito en el formato "50 10 30 5 90 20 40 2 25 10 8 0". Dada esa lista, necesitaremos transformar las cadenas en números enteros. Usaremos un método similar al que usamos en nuestra calculadora RPN:

3> [list_to_integer(X) || X <- S].

[50,10,30,5,90,20,40,2,25,10,8,0]

Comencemos un nuevo módulo llamado road.erl y escribamos esta lógica:

-module(road).

-compile(export_all).

main() ->

    File = "road.txt",

    {ok, Bin} = file:read_file(File),

    parse_map(Bin).

parse_map(Bin) when is_binary(Bin) ->

    parse_map(binary_to_list(Bin));

parse_map(Str) when is_list(Str) ->

    [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")].

La función main/0 es aquí la responsable de leer el contenido del archivo y pasarlo a parse_map/1. Debido a que utilizamos la función file:read_file/1 para obtener el contenido de road.txt, el resultado que obtenemos es un binario. Por este motivo, he hecho que la función parse_map/1 coincida tanto con listas como con binarios. En el caso de un binario, simplemente llamamos a la función nuevamente con la cadena convertida en una lista (nuestra función para dividir la cadena funciona solo con listas).

El siguiente paso para analizar el mapa sería reagrupar los datos en la forma {A,B,X} descrita anteriormente. Lamentablemente, no existe una forma genérica simple de extraer elementos de una lista de a 3 por vez, por lo que tendremos que hacer una coincidencia de patrones en una función recursiva para hacerlo:

group_vals([], Acc) ->

    lists:reverse(Acc);

group_vals([A,B,X|Rest], Acc) ->

    group_vals(Rest, [{A,B,X} | Acc]).

Esa función funciona de manera recursiva estándar; no hay nada demasiado complejo en juego aquí. Solo tendremos que llamarla modificando un poco parse_map/1:

parse_map(Bin) when is_binary(Bin) ->

    parse_map(binary_to_list(Bin));

parse_map(Str) when is_list(Str) ->

    Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],

    group_vals(Values, []).

Si intentamos compilarlo todo, ahora deberíamos tener una carretera que tenga sentido:

1> c(road).

{ok,road}

2> road:main().

[{50,10,30},{5,90,20},{40,2,25},{10,8,0}]

Ah, sí, eso parece correcto. Obtenemos los bloques que necesitamos para escribir nuestra función que luego encajará en un pliegue. Para que esto funcione, es necesario encontrar un buen acumulador.

Para decidir qué usar como acumulador, el método que me parece más fácil de usar es imaginarme a mí mismo en medio del algoritmo mientras se ejecuta. Para este problema específico, imaginaré que actualmente estoy tratando de encontrar el camino más corto del segundo triple ({5,90,20}). Para decidir cuál es el mejor camino, necesito tener el resultado del triple anterior. Afortunadamente, sabemos cómo hacerlo, porque no necesitamos un acumulador y ya tenemos toda esa lógica. Entonces, para A:

Y tomemos el más corto de estos dos caminos. Para B, fue similar:

Ahora sabemos que el mejor camino actual que viene de A es [B, X]. También sabemos que tiene una longitud de 40. Para B, el camino es simplemente [B] y la longitud es 10. Podemos usar esta información para encontrar los siguientes mejores caminos para A y B volviendo a aplicar la misma lógica, pero contando los anteriores en la expresión. El otro dato que necesitamos es el camino recorrido para poder mostrárselo al usuario. Dado que necesitamos dos caminos (uno para A y otro para B) y dos longitudes acumuladas, nuestro acumulador puede tomar la forma {{DistanciaA, CaminoA}, {DistanciaB, CaminoB}}. De esa manera, cada iteración del pliegue tiene acceso a todo el estado y lo construimos para mostrárselo al usuario al final.

Esto nos da todos los parámetros que necesitará nuestra función: los triples {A,B,X} y un acumulador de la forma {{DistanciaA,RutaA}, {DistanciaB,RutaB}}.

Para obtener nuestro acumulador, podemos introducir esto en el código de la siguiente manera:

shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->

    OptA1 = {DistA + A, [{a,A}|PathA]},

    OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},

    OptB1 = {DistB + B, [{b,B}|PathB]},

    OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},

    {erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.

Aquí, OptA1 obtiene la primera opción para A (pasando por A), OptA2 la segunda (pasando por B y luego por X). Las variables OptB1 y OptB2 reciben un tratamiento similar para el punto B. Finalmente, devolvemos el acumulador con las rutas obtenidas.

Sobre las rutas guardadas en el código anterior, tenga en cuenta que decidí usar la forma [{x, X}] en lugar de [x] por la sencilla razón de que podría ser bueno para el usuario saber la longitud de cada segmento. La otra cosa que estoy haciendo es que estoy acumulando las rutas hacia atrás ({x, X} viene antes de {b, B}). Esto se debe a que estamos en un pliegue, que es recursivo de cola: toda la lista se invierte, por lo que es necesario poner el último recorrido antes de los demás.

Finalmente, uso erlang:min/2 para encontrar la ruta más corta. Puede sonar extraño usar una función de comparación de este tipo en tuplas, pero recuerde que cada término de Erlang se puede comparar con cualquier otro. Como la longitud es el primer elemento de la tupla, podemos ordenarlos de esa manera.

Lo que queda por hacer es colocar esa función en un pliegue:

optimal_path(Map) ->

    {A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),

    {_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;

                      hd(element(2,B)) =/= {x,0} -> B

                   end,

    lists:reverse(Path).

Al final del pliegue, ambas rutas deberían terminar teniendo la misma distancia, excepto que una pasa por el segmento final {x,0}. El if observa el último elemento visitado de ambas rutas y devuelve el que no pasa por {x,0}. Elegir la ruta con la menor cantidad de pasos (comparar con length/1) también funcionaría. Una vez que se ha seleccionado la más corta, se invierte (se construyó de manera recursiva de cola; debe invertirla). Luego puede mostrarla al mundo o mantenerla en secreto y obtener la herencia de su tío rico. Para hacer eso, debe modificar la función principal para llamar a optimal_path/1. Luego se puede compilar.

main() ->

    File = "road.txt",

    {ok, Bin} = file:read_file(File),

    optimal_path(parse_map(Bin)).

¡Mira! ¡Tenemos la respuesta correcta! ¡Buen trabajo!

1> c(road).

{ok,road}

2> road:main().

[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]

O, para decirlo de forma visual:

El camino más corto, pasando por [b,x,a,x,b,b]

Pero, ¿sabes qué sería realmente útil? Poder ejecutar nuestro programa desde fuera del shell de Erlang. Tendremos que cambiar nuestra función principal nuevamente:

main([FileName]) ->

    {ok, Bin} = file:read_file(FileName),

    Map = parse_map(Bin),

    io:format("~p~n",[optimal_path(Map)]),

    erlang:halt().

La función principal ahora tiene una aridad de 1, necesaria para recibir parámetros desde la línea de comandos. También he añadido la función erlang:halt/0, que apagará la máquina virtual Erlang después de ser llamada. También he envuelto la llamada a optimal_path/1 en io:format/2 porque esa es la única forma de tener el texto visible fuera del shell de Erlang.

Con todo esto, tu archivo road.erl ahora debería verse así:

-module(road).

-compile(export_all).

main([FileName]) ->

    {ok, Bin} = file:read_file(FileName),

    Map = parse_map(Bin),

    io:format("~p~n",[optimal_path(Map)]),

    erlang:halt(0).

%% Transform a string into a readable map of triples

parse_map(Bin) when is_binary(Bin) ->

    parse_map(binary_to_list(Bin));

parse_map(Str) when is_list(Str) ->

    Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")],

    group_vals(Values, []).

group_vals([], Acc) ->

    lists:reverse(Acc);

group_vals([A,B,X|Rest], Acc) ->

    group_vals(Rest, [{A,B,X} | Acc]).

%% Picks the best of all paths, woo!

optimal_path(Map) ->

    {A,B} = lists:foldl(fun shortest_step/2, {{0,[]}, {0,[]}}, Map),

    {_Dist,Path} = if hd(element(2,A)) =/= {x,0} -> A;

                      hd(element(2,B)) =/= {x,0} -> B

                   end,

    lists:reverse(Path).

%% actual problem solving

%% change triples of the form {A,B,X}

%% where A,B,X are distances and a,b,x are possible paths

%% to the form {DistanceSum, PathList}.

shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->

    OptA1 = {DistA + A, [{a,A}|PathA]},

    OptA2 = {DistB + B + X, [{x,X}, {b,B}|PathB]},

    OptB1 = {DistB + B, [{b,B}|PathB]},

    OptB2 = {DistA + A + X, [{x,X}, {a,A}|PathA]},

    {erlang:min(OptA1, OptA2), erlang:min(OptB1, OptB2)}.

Y ejecutando el código:

$ erlc road.erl

$ erl -noshell -run road main road.txt

[{b,10},{x,30},{a,5},{x,20},{b,2},{b,8}]

¡Y sí, es correcto! Es prácticamente todo lo que necesitas hacer para que las cosas funcionen. Puedes crear un archivo bash/batch para encapsular la línea en un solo ejecutable, o puedes consultar el script para obtener resultados similares.