Malbolge

Malbolge
Un programa eco en Malbolge
Ben Olmstead​
Información general
Extensiones comunes	.mal, .mb
Paradigma	Esotérico, imperativo, escalar, nivel de valor
Apareció en	1998
Diseñado por	Ben Olmstead​
Influido por	Brainfuck, INTERCAL (Tri-INTERCAL), Befunge
Ha influido a	Dis, Malbolge Unshackled

Malbolge ( /mælˈboʊldʒ/) es un lenguaje de programación esotérico de dominio público desarrollado por Ben Olmstead en 1998. Se llamó así por el octavo círculo del infierno en La Divina Comedia, escrito por Dante.

Malbolge es peculiar porque se diseñó para ser el lenguaje más difícil, a través de una 'operación loca' contraria a la intuición, aritmética de base tres y código autoalterable​. Sin embargo, varios de los trucos utilizados para hacerlo difícil de entender pueden ser evitados y generar programas útiles en el.

Programación en Malbolge

Malbolge fue muy difícil de entender cuando llegó. Pasaron dos años hasta que apareció el primer programa de Malbolge. El propio autor nunca ha escrito un programa de Malbolge. El primer programa no fue escrito por un ser humano; fue generado por un algoritmo de búsqueda de haz diseñado por Andrew Cooke e implementado en Lisp​.

Más tarde, Lou Scheffer publicó un criptoanálisis de Malbolge y proporcionó un programa para copiar su entrada a su salida.​ También guardó el intérprete original y la especificación después de que el sitio original dejara de funcionar, y ofreció una estrategia general para escribir programas en Malbolge, así como algunas ideas sobre su integridad Turing .​

Olmstead creía que Malbolge era un autómata linealmente acotado . Existe una discusión sobre si se pueden implementar bucles en Malbolge; pasaron muchos años antes de que se introdujera el primer bucle infinito. Durante siete años no se anunció un programa correcto de 99 Bottles of Beer que usara bucles y condiciones no triviales. El primero correcto fue el de Hisashi Iizawa en 2005.​ El mismo autor también propuso una guía para la programación en Malbolge con el propósito de ofuscación para la protección del software.​

En 2020, el usuario de GitHub kspalaiologos creó un intérprete de Lisp funcional en Malbolge Unshackled.​

Ejemplos

Código de ejemplo Hello World:​

 (=<`$9]7<5YXz7wT.3,+O/o'K%$H"'~D|#z@}b=`{^Lx8%$Xmrkpohm-kNi;gsedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543s+O<oLm

Programa cat

Este programa lee una cadena desde la entrada estándar e imprime esa cadena, similar a cat en Unix.​

(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.
~P<
<:(8&
66#"!~}|{zyxwvu
gJ%

Diseño

Los programas en Malbolge son código máquina para una máquina virtual que trabaja con valores ternarios: el intérprete de Malbolge.

El lenguaje Malbolge tiene una especificación oficial​ y un intérprete de referencia programado en C por el propio autor​. La especificación y el intérprete no coinciden a la perfección: por ejemplo, los códigos de operación correspondientes a la lectura e impresión de datos son 5 y 23 respectivamente en la especificación, pero están invertidos en el intérprete. La mayoría de implementaciones de Malbolge, y la tabla de operaciones que puede encontrarse más abajo, ignoran la especificación para concordar con el intérprete de referencia. No está claro si estas diferencias son un simple error, o un intento deliberado de hacer el lenguaje aún más confuso.

Registros

La máquina virtual de Malbolge tiene tres registros: A, C y D. El registro A es el acumulador, que se usa para las operaciones de entrada/salida. C es el puntero de instrucción, y apunta a la siguiente instrucción a ejecutar. D es el puntero de datos, usado para las operaciones de manipulación de datos. Al comenzar la ejecución, el valor de todos los registros es cero. El valor de los registros C y D se incrementa en 1 tras ejecutar cada instrucción.

Notación de punteros

El valor de los registros C y D se puede usar tal cual, o como puntero a una posición de memoria. En adelante, C indica el valor literal almacenado en el registro, mientras que [C] indica el valor presente en la dirección de memoria C. Las mismas consideraciones aplican al registro D.

Memoria

La máquina virtual tiene 59.049 (3¹⁰) direcciones de memoria. Cada una de estas direcciones almacena un valor codificado en ternario, usando 10 trits. Un trit es la unidad mínima de información en el sistema ternario, y puede tomar los valores 0, 1 o 2 (su equivalente en binario, el bit, sólo puede tomar los valores 0 o 1). Por tanto, cada posición de memoria tiene un valor entre 0 y 59.048 (3¹⁰ - 1). Incrementar un valor pasado ese límite lo devuelve a cero.

Al igual que en las arquitecturas x86 actuales, la máquina virtual sigue la arquitectura Von Neumann, es decir, las instrucciones a ejecutar y los datos sobre los que operan comparten el mismo espacio de memoria. Antes de comenzar la ejecución, el programa a ejecutar se copia en las primeras posiciones del espacio de memoria.

El resto de la memoria se rellena con el resultado de aplicar la crazy operation (definida más abajo) a los valores contenidos en las dos posiciones de memoria anteriores ([M] = CRAZY_OP([M-1], [M-2])). El orden de los argumentos de esta operación es relevante, ya que la crazy operation no es conmutativa.

Un detalle a tener en cuenta es que la especificación oficial no contempla el caso específico de programas Malbolge que tienen sólo una instrucción. En esos casos, intentar rellenar la segunda posición de memoria usando la crazy operation, según el proceso descrito anteriormente, requiere leer la primera posición (que contiene la única instrucción del programa), y la posición anterior a esa, que está fuera del espacio de memoria. El intérprete de referencia del lenguaje tampoco considera esta posibilidad, e incurre en comportamiento indefinido al leer fuera del espacio de memoria designado.

Instrucciones

Malbolge tiene ocho instrucciones. El proceso de ejecución de cada instrucción tiene tres fases:

En primer lugar, se comprueba que el valor referenciado por el puntero de instrucción, [C], sea válido. Se considera que es válido si está en el rango [33, 126]. Si no es válido, la ejecución finaliza inmediatamente con un error.

A continuación, se determina la instrucción a ejecutar y ésta se lleva a cabo. Para ello, se toma el valor referenciado por el puntero de instrucción, [C], se le suma el valor de C y se toma el módulo 94 de la suma anterior. El resultado de esta operación determina la instrucción a realizar, según la siguiente tabla:

Instrucciones Malbolge

Resultado de ([C] + C) % 94	Pseudocódigo	Descripción
4	C ← [D]	Copia el valor apuntado por el puntero de datos al puntero de instrucción (salto incondicional).
5	PRINT(A % 256)	Imprime por pantalla el resultado de A % 256, interpretado como un carácter ASCII.
23	A ← INPUT	Lee un byte de la entrada estándar y lo almacena en A. El fin de fichero se representa con el valor 59048.
39	A ← [D] ← ROTATE_RIGHT([D])	Rota el valor en [D] un trit a la derecha (0002111112 pasa a ser 2000211111). Almacena el valor resultante en A y en [D].
40	D ← [D]	Establece el puntero de datos al valor apuntado por sí mismo.
62	A ← [D] ← CRAZY_OP(A, [D])	Realiza la crazy operation sobre los valores A y [D] (en ese orden). Almacena el valor resultante en A y en [D].
68	NOP	No hace nada (pero los valores en C y D se incrementan igualmente tras la instrucción).
81	END	Finaliza inmediatamente la ejecución.
Cualquier otro valor	Igual que el valor 68: no hace nada. Estos otros valores se permiten en tiempo de ejecución, pero no durante la carga del programa.

Tras la ejecución de cada instrucción, el valor en [C] se cifra, usando el método de cifrado que puede encontrarse más abajo. Finalmente, el valor de los registros C y D se incrementa en 1.

Crazy operation

La crazy operation es una operación a nivel de trits. Para cada dígito ternario de los dos valores de entrada, se usa la siguiente tabla para determinar el dígito correspondiente en el valor de salida. La tabla no es simétrica, por lo que la crazy operation no es conmutativa.

Por ejemplo, el resultado de aplicar la crazy operation sobre 0001112220 y 0120120120 es 1120020211.

Crazy operation

		Trit 1
		0	1	2
Trit 2	0	1	0	0
	1	1	0	2
	2	2	2	1

Cifrado de instrucciones

Al final de cada instrucción, y previamente a incrementar los valores de C y D, la instrucción apuntada por el puntero de instrucción se cifra. El proceso consiste en calcular [C] % 94 y usar ese resultado para consultar el valor cifrado a almacenar en [C], según la siguiente tabla:

Tabla de cifrado

[C]%94	Nuevo valor	[C]%94	Nuevo valor	[C]%94	Nuevo valor	[C]%94	Nuevo valor	[C]%94	Nuevo valor
0	57	19	108	38	113	57	91	76	79
1	109	20	125	39	116	58	37	77	65
2	60	21	82	40	121	59	92	78	49
3	46	22	69	41	102	60	51	79	67
4	84	23	111	42	114	61	100	80	66
5	86	24	107	43	36	62	76	81	54
6	97	25	78	44	40	63	43	82	118
7	99	26	58	45	119	64	81	83	94
8	96	27	35	46	101	65	59	84	61
9	117	28	63	47	52	66	62	85	73
10	89	29	71	48	123	67	85	86	95
11	42	30	34	49	87	68	33	87	48
12	77	31	105	50	80	69	112	88	47
13	75	32	64	51	41	70	74	89	56
14	39	33	53	52	72	71	83	90	124
15	88	34	122	53	45	72	55	91	106
16	126	35	93	54	90	73	50	92	115
17	120	36	38	55	110	74	70	93	98
18	68	37	103	56	44	75	104

Referencias

• Datos: Q517956
• Multimedia: Malbolge / Q517956