La perlificación de Python

You know, FOX turned into a hardcore sex channel so gradually I didn’t even notice

Marge Simpson, Los Simpson

Recientemente ha salido Python 3.7, con interesantes novedades. También han salido los primeros artículos hablando de las novedades que podrá traer Python 3.8. Como muchos ya conoceréis, y si no es así explico, Python funciona a base de PEPs (Python Enhancement Proposal). Cualquier persona puede abrir un PEP, que es un documento que describe la funcionalidad que se quiere añadir/modificar/eliminar. Estas PEPs se discuten y finalmente Guido, creador de Python, las aprueba y se codifican.

Dentro de las PEP relacionadas con Python 3.8 hay algunas bastante controvertidas que han hecho saltar la voz de alarma. No ha faltado gente que ha opinado que cada vez Python se parece más a Perl. Este proceso habría empezado con Python 3 pero se habría ido haciendo más evidente hasta llegar a hoy. Cada vez con más sintaxis poco utilizada, con más elementos, más cómodo de escribir para el experimentado aunque menos legible si no dominas el lenguaje.

Y resulta curioso, porque Python es en parte una respuesta a la excesiva complejidad que podían tener los programas hechos en Perl. Su popularidad se debe a que es fácil de aprender y eso parece que ya no está tan claro.

Con la introducción de operadores como := o ?? o anotaciones como @dataclass se va, en cierta medida, perdiendo el espíritu original de Python. Y es cierto que otros lenguajes tienen algo similar, pero precisamente Python había sido muy selecto en incluir un conjunto bastante reducido de características, que todo el mundo pudiese dominar. Al final se sacrifica legibilidad y facilidad de aprendizaje por una ergonomía que beneficia a unos pocos en unos casos concretos.

Lenguajes de programación barrocos

Universidad de Valladolid, ejemplo de barroco civil. Foto: https://artevalladolid.blogspot.com

Python lleva un tiempo entrando en un proceso de perlificación pero en mi opinión no es el único lenguaje que ha entrado en una espiral parecida. Cada vez más lenguajes han pasado del renacimiento, donde se buscaba la consistencia, la simetría, la sencillez sin perder la funcionalidad, hacia el barroco, donde los lenguajes son más recargados, con más elementos sintácticos, que cubren mejor casos concretos, pero que de por sí no son tan esenciales, no cambian aspectos fundamentales del lenguaje y normalmente introducen diversas formas de hacer algo en un mismo lenguaje.

Veamos más ejemplos: en C++20 se propuso añadir funcionalidad de dibujado 2D a la librería estándar (propuesta que fue rechazada en una historia bastante larga para este post) y se han propuesto conceptos, módulos, comparación de tres vías, reflexión, metaclases,… En C# 8.0 se han propuesto también bastantes cosas como records, tipos non-nullable, interfaces con métodos ya implementados (traits) y rangos. Y eso sin contar con las características que estos dos lenguajes ya tienen, que son bastante más extensos que Python.

Retablo lateral de la Iglesia de San Miguel y San Julián (Valladolid). Barroco puro. Foto: https://commons.wikimedia.org/wiki/File:San_Miguel_-_retablo_relicario.jpg

Hay un horror vacui, horror al vacío, a funcionalidades. Siempre se añade y casi nunca se elimina. ¿Pero es realmente necesario? Es evidente que durante mucho tiempo, los lenguajes evolucionaban de forma muy lenta y muchos de los cambios que han hecho eran necesarios. Desde hace unos años, se ha aumentado la velocidad de los cambios, pero esto no puede seguir así eternamente, porque el ritmo que llevan muchas veces es superior al de los avances en lenguajes de programación y la retrocompatibilidad impide ir quitando cosas al mismo ritmo que se añaden. De este modo, todos los lenguajes que entran en esta espiral crecen y crecen. No se llegan a pulir, simplemente crecen.

La perfección no se alcanza cuando no hay nada más que añadir, sino cuando no hay nada más que quitar

Antoine de SaintExupéry

Uno podría comparar esto con lenguajes naturales, como el español o el inglés. En estos idiomas, pese a existir reglas, existen numerosas excepciones. Es posible que lenguajes como Python se estén viendo influenciados por las mismas mecánicas humanas que rigen los lenguajes naturales y que han hecho que existan excepciones. Tendría bastante sentido que ocurriese así. Pero personalmente, me gustaría que aprender Python no costase tanto como aprender alemán o francés.

Los procesos comunitarios

Para mí, gran parte de esta sobrecarga viene dada por los procesos comunitarios. En un proceso comunitario como PEP, comité de C++ o similares es mucho más fácil añadir que eliminar. En C++ la situación ha llegado a un punto en el que Bjarne Stroustrup, creador de C++, ha pedido que se relajen con las propuestas en Remember the Vasa!, en honor a un bonito barco sueco que se hundió por exceso de carga. No tanto por su peso, sino por su disposición y las reformas que hubo que hacer para que todo encajase.

El Vasa fue recuperado después de su naufragio y se expone en Estocolmo. Foto: https://rachelannsblog.wordpress.com/2016/08/03/set-sail-set-at-the-bottom-of-the-sea/

Es por ello que las personas encargadas de elegir que se añade al lenguaje o no deben de ser muy conscientes de lo que supone, ya que una vez se introduzca, va a ser casi imposible eliminarlo.

No estoy en contra de añadir nuevas características (¡al contrario!) pero se debe respetar la visión de conjunto del lenguaje, que todo cuadre y esté cohesionado. No siempre tener más es mejor.

¿Te ha gustado el artículo?

Si es así, puedes ayudar al blog. Dentro de unos días es el Amazon Prime Day. Como muchos de vosotros seguro que os compraréis algo, no quiero dejar la oportunidad de deciros que este blog tiene enlace de referidos y que por cada cosa que compréis con el enlace, me llevo una pequeña parte (a vosotros no os va a costar más caro).

Enlace Amazon.es

Será muy bien recibido

 

¿Cómo funcionan los sistemas basados en inodos?

Después de ver como funcionan de forma genérica los sistemas FAT, saltamos a los sistemas de inodos. Estos se han usado tradicionalmente en sistemas UNIX (UFS, ext2), así que tradicionalmente ha existido una cierta rivalidad  en las redes entre FAT e inodos similar a la de Windows/Linux. Lo cierto es que a nivel técnico cada uno tiene fortalezas y debilidades.

Partición

Tomando la base de FAT, una partición de un sistema basado en inodos también contiene un sector de arranque y un superbloque con metadatos. También es necesario un bloque dedicado al directorio raíz presente en el disco. Además es necesario espacio para almacenar todos los inodos y un mapa de bits de espacio libre que en FAT no hacía falta, ya que la propia tabla nos indicaba que bloques del disco estaban libres.

Los inodos

¿Qué es inodo te podrás preguntar? Es una estructura de datos, su nombre proviene de index node y es que los inodos no son más que índices, que almacenan los números de bloque de las diferentes partes del archivo. Además, contienen metadatos como permisos, propietario, tamaño, fecha de modificación, referencias, tipo de fichero (directorio, archivo, enlace duro, enlace blando,…) salvo el nombre del propio archivo, que en ningún sitio del inodo aparece.

Este sistema tiene una ventaja de rendimiento respecto a FAT en cuanto al acceso aleatorio a los archivos, ya que es mucho más rápido de esta forma que con FAT. En FAT para hacer lo mismo tenemos que ir recorriendo la tabla arriba y abajo siguiendo los números de bloque hasta encontrar el bloque deseado.

Normalmente un inodo tiene un tamaño fijo, lo que implica que el índice no se puede alargar hasta el infinito. Esto hace que haya un número limitado de bloques que puede usar un archivo y por ende, que haya un tamaño máximo de archivo que no es muy elevado. Para solventar este problema hay varias soluciones. El enfoque de UFS y de ext2/3/4 consiste en múltiples niveles de indexado progresivo.

Esto significa que los primeros bloques son números de bloque directos pero los siguientes son números de bloque que llevan a tablas de inodo secundarias que ya sí, hacen referencia al archivo real. Más adelante los números de bloque hacen referencias a tablas de inodo secundarias que a su vez llaman a tablas de inodos terciarias.

Esto provoca algo que en principio puede parecer paradójico y es que es más lento leer una zona final de un archivo que una zona del principio, aunque en una lectura secuencial no se nota demasiado.

Otra solución a esto es enlazar los inodos a modo de lista enlazada añadiendo al final de cada inodo un número de inodo al que continuar la lectura de índices.

Localización de los inodos

Los inodos se crean cuando se formatea el disco y permanecen en un estado libre. No se pueden añadir más inodos ni quitar inodos y no puede haber más archivos y directorios que inodos por esta misma razón. Esto es una desventaja respecto a FAT, ya que en FAT puede haber tantos archivos como bloques haya/entradas tenga la tabla. En sistemas de inodos como ext2/3/4 puede ocurrir que no queden inodos libres pero haya todavía bloques libres, dejando todo ese espacio inutilizado (aunque en realidad lo podrían usar los archivos existentes si creciesen).

Los inodos se pueden ubicar de dos formas distintas. Un enfoque consiste en ponerlos al principio del disco todos juntos. Otro enfoque, el que sigue ext3, consiste en dividir el disco en 4 zonas y ubicar inodos en cada inicio de zona. La idea es que los inodos de esa zona usen bloques de esa zona y de esta forma reducir los desplazamientos de las cabezas lectoras del disco (en unidades SSD esto da completamente igual como podréis suponer).

Gestión del espacio libre

Una de las grandes ventajas de FAT era que la tabla podía mantener a la vez un listado de bloques libres, listos para ser usados. Con inodos no tenemos esa facilidad y tenemos que recurrir a otros tipos de estructura. Aquí hay muchos planteamientos siendo el más común el mapa de bits. El mapa de bits es una estructura que se compone de un listado de bits. Cada bit corresponde a un bloque y dependiendo de si el bit es 1 o 0 podemos saber si el bloque está libre u ocupado.

Como veis, los sistemas basados en inodos tienen que mantener varias estructuras de datos de forma paralela. Esto aumenta las probabilidades de inconsistencias en el sistema. Por este motivo, muchos sistemas más avanzados como ext4 mantienen un journal o diario.

Fragmentación

Veamos como se comportan los sistemas de inodos ante los tres tipos de fragmentación. Respecto a la fragmentación interna, que es aquella que sucede cuando asignamos espacio de más a archivos que no necesitan tanto, tiene los mismos valores que FAT, ya que los bloques siguen pudiendo pertenecer únicamente a un archivo. Realmente, para mejorar la fragmentación interna tenemos que saltar a sistemas como XFS o JFS.

La fragmentación externa de los sistemas basados en inodos es la misma que la de FAT, 0, ya que todo se asigna mediante bloques del mismo tamaño.

Respecto a la fragmentación de datos, históricamente las implementaciones como UFS o ext2/3 se han comportado relativamente bien, aunque a nivel teórico nada impide que se comporten igual de mal que FAT, no existen mecanismos preventivos. Ext4 por contra, sí que tiene mecanismos de prevención (delayed allocation).

Directorios y enlaces duros

En los sistemas basados en inodos los directorios son más sencillos que en FAT, ya que no tienen que almacenar los metadatos del archivo en cuestión. En un fichero de directorio simplemente se almacena el nombre y el número de inodo correspondiente.

Aquí surge un concepto muy interesante, el de enlaces duros. Un enlace duro no es más que otra entrada de directorio que apunta a un mismo inodo. Realmente desde el punto de vista del sistema de archivos no existe un fichero original y su enlace. Simplemente dos entradas diferentes apuntando al mismo inodo. ¿Y cómo reacciona esto a los borrados? Imagina la siguiente situación: tengo un fichero y creo un enlace duro. Borro el fichero original y su inodo se libera. Ahora creo otro archivo y reutiliza ese mismo inodo que estaba libre. ¡Ahora el enlace duro apunta a un contenido totalmente distinto sin darse cuenta! Para prevenir esto, los inodos no se liberan hasta que no quede ninguna entrada de directorio apuntando a ellos. Para eso sirve el campo referencias dentro del inodo, para llevar la cuenta de cuántas veces se hace referencia al inodo en el sistema de archivos. Cuando el valor de referencias llega a cero, se puede liberar sin problema.

Conclusiones

Los sistemas basados en inodos son conceptualmente algo más complejos que los basados en FAT. Comparten además limitaciones comunes, usan más espacio de disco, aunque suelen ser más rápidos.

Actualmente existen sistemas basados en inodos mucho más avanzados y complejos que UFS y ext2/3/4 y que mejoran este sistema de forma sustancial. Por ejemplo en XFS los inodos tienen una estructura totalmente distinta donde se indica un bloque de inicio y una longitud en número de bloques contiguos que pertenecen al archivo. Muchos sistemas además usan estructuras de árbol B+ como pueden ser ZFS o Btrfs.

¿Cómo funcionan los sistemas de archivos basados en FAT?

Voy a dedicar unas entradas en el blog a hablar del funcionamiento de los sistemas de archivos, un componente fundamental en la gran mayoría de sistemas informáticos. Voy a empezar con los basados en FAT sin centrarme en ninguno en concreto (FAT16, FAT32, exFAT,…). Intentaré escribir también sobre inodos y mecanismos más raros y avanzados.

En esencia un sistema de archivos es un método ordenado que permite guardar datos sobre un soporte físico para luego poder acceder a ellos. Históricamente ha habido muchos enfoques a este problema: los sistemas más usados usan archivos, directorios y enlaces.

Bloques y sectores: la división del disco

Esta parte es común a muchos sistemas de archivos, tanto FAT como inodos, como otros. A nivel físico los dipositivos están divididos. En el caso del disco duro, el dispositivo de almacenamiento más común, los discos se dividen en sectores de N bytes, según parámetros de la fabricación. Estos sectores cuentan con código de control de errores incorporado y todo ello es manejado por la controladora de disco que opera ajena al sistema operativo. Los sistemas de archivos dividen a su vez el disco en bloques. Es importante dejar claro que bloque no es igual a sector. El bloque es una división que hace el sistema de archivos y los sectores los hace la controladora de disco. Usualmente un bloque equivale a varios sectores, aunque la equivalencia real depende del sistema de archivos en concreto.

Algunos bloques especiales: boot y superbloque y raíz

Antes de entrar en el mecanismo específico de FAT es necesario comentar que en un disco existirán dos bloques de vital importancia ajenos a FAT. El primero es el bloque de boot o arranque (también llamado MBR). Normalmente situado en el sector 0 del disco duro, contiene código para iniciar el sistema operativo. El superbloque suele ser el bloque siguiente, contiene metadatos del sistema de archivos (por ejemplo, puede decir que usamos FAT con bloques de 32KiB, etc). Además en FAT es necesario que exista un fichero siempre, el fichero del directorio raíz.

Directorios

Los directorios o carpetas son archivos como otros cualquiera, solamente que en sus metadatos se indica que es un directorio y no un fichero corriente. Los ficheros de directorios son los encargados de almacenar los metadatos de los ficheros (paras saber si son ficheros, otros directorios, su fecha de modificación, propietario y tamaño entre otros) que se encuentran en el directorio así como una referencia al bloque.

Un fichero en FAT

Vamos al asunto. Supongamos que en un determinado bloque N tenemos un fichero. Este bloque es de 64 KiB. Si un fichero ocupa menos de 64 KiB, perfecto, todos los datos entran en el bloque. Simplemente ajustamos los metadatos de tamaño con el valor correcto y el resto del espacio que queda en el bloque queda inutilizado.

Este espacio perdido se denomina fragmentación interna y dependiendo de los datos que se almacenen en un disco duro, el porcentaje de pérdida puede ser mayor o menor. Evidentemente si tenemos bloques muy grandes y ficheros muy pequeños perderemos mucho espacio debido a la fragmentación interna. Tener bloques muy pequeños y ficheros muy grandes también es problemático pero por otros motivos.

Tipos de fragmentación

En un sistema de archivos existen 3 tipos de fragmentación: interna, externa y de datos. La interna se refiere al espacio perdido en bloques asignados a ficheros que no están llenos por completo. La externa se refiere al espacio que perdemos por no tener un espacio libre contiguo lo suficientemente grande como para guardar el fichero allí. Ningún sistema FAT o de inodos tiene fragmentación externa al usar todos bloques de tamaño predefinido. Por último la fragmentación de datos, o fragmentación a secas, se refiere a que los bloques asignados estén contiguos o no. Esto tiene implicaciones a nivel de rendimiento pero no al número de bytes que se vuelven inútiles como los otros dos tipos de fragmentación.

¿Pero qué pasa si el contenido de nuestro fichero no puede entrar en el tamaño de bloque? Aquí viene la gracia de FAT, la File-Allocation-Table. La FAT es una tabla compuesta por entradas que indican el siguiente bloque del archivo. La tabla está indexada por bloque y además de indicar cuál es el siguiente bloque del archivo también indica si el archivo acaba ahí o si ese bloque está libre y puede usarse para un archivo nuevo.

En la foto el archivo /home/user/hola.txt tiene una longitud menor al tamaño de bloque. Así que miramos en la FAT la entrada 150 y efectivamente comprobamos que no hay bloque siguiente ya que es un End-of-File.

Pongamos un ejemplo con un archivo largo. Cada celda de la tabla correspondiente al índice del bloque actual indica el siguiente bloque a leer. Estos bloques pueden estar en cualquier parte. Si en un disco duro muchos ficheros tienen los bloques muy dispersos, se dice que necesita ser desfragmentado.

Conclusiones

FAT es muy rápido si la tabla FAT consigue ser cargada en memoria, ya que obtener los datos necesarios de ella será muy rápido. Desgraciadamente, dependiendo del tamaño del disco duro y del tamaño de los bloques, esta tabla puede ocupar mucho y ser impráctico.

El mecanismo FAT como vemos es simple pero efectivo. Dispone de una fragmentación interna limitada y carece de fragmentación externa. Un inconveniente es que FAT cuando busca un archivo necesita empezar siempre desde el directorio raíz. Esto implica accesos cada vez más lentos a medida que vayamos haciendo carpetas, aunque con sistemas de caché se puede reducir.

El esquema FAT tampoco impone restricciones propiamente dichas al número archivos de un sistema ni a su tamaño. Sin embargo en la práctica suelen existir límites.

Edito: He explicado mejor que significa la fragmentación y sus tipos

Bindings entre Rust y C/C++ con bindgen

Rust es un lenguaje con muchas posibilidades pero existe mucho código ya escrito en librerías de C y C++. Código que ha llevado mucho tiempo, que ha sido probado en miles de escenarios, software maduro y que no compensa reescribir. Afortunadamente podemos reutilizar ese código en nuestras aplicaciones Rust a través de bindings. Los bindings no son más que trozos de código que sirven de pegamento entre lenguajes. Esto es algo que se ha podido hacer desde siempre pero dependiendo de la librería podía llegar a ser muy tedioso. Afortunadamente tenemos bindgen, un programa que permite generar estos bindings de forma automática analizando el código de la librería de C o C++.

En este post veremos como usar SQLite desde Rust usando bindgen.

Instalando bindgen

En primer lugar necesitamos tener instalado Clang 3.9 o superior. En Ubuntu o Debian necesitamos estos paquetes:

Para el resto de plataformas puedes descargar el binario desde la página de descargas de LLVM.

Bindgen permite dos modos de uso: línea de comandos o desde el código Rust. El más habitual es desde código Rust pero antes veremos el modo en línea de comandos.

Modo línea de comandos

Para bindings sencillos podemos usar el modo línea de comandos. Instalamos binden con Cargo:

Su uso es muy sencillo:

Simplemente indicamos el fichero de cabecera que queremos traducir y su correspondiente fichero de salida en Rust. Este fichero será el pegamento. Vamos a crear un programa que use este pegamento:

Como se puede apreciar, las llamadas al módulo de pegamento de hacen desde un bloque unsafe ya que se van a usar punteros al estilo C, de forma insegura. Hace tiempo escribí sobre ello así que voy a saltarme esa parte.

Compilamos enlazando de forma manual libsqlite3 de la siguiente forma:

Si todo va bien, compilará aunque con numerosos warnings. En principio no son importantes.

Ahora si ejecutamos el programa resultante debería crear una base de datos nueva con una tabla contacts y los datos insertados.

¡Hemos conseguido llamar a una librería de C desde Rust y no hemos escrito ningún binding!

Build.rs

El sistema anterior funciona, pero no es lo más práctico, además no usa Cargo que es el sistema estándar de construcción de programas y crates un Rust. Lo habitual es dejar este proceso automatizado en el fichero build.rs que se ejecuta con Cargo.

Lo primero es añadir la siguiente línea al fichero Cargo.toml:

El siguiente paso consiste en crear un archivo cabecera de C que a su vez haga referencia a todos los archivos de cabecera que necesitamos. En el caso de SQLite es bastante simple.

Y lo llamamos wrapper.h

Ahora viene lo interesante. Dentro de build.rs creamos un programa que gracias a la API de bindgen haga lo mismo que la línea de comandos.

El archivo build.rs debe estar en la misma carpeta que Cargo.toml para que funcione.

Finalmente para hacer accesible nuestros bindings creamos un módulo llamado sqlite.rs con el siguiente contenido.

Lo único que hace es desactivar unos warnings molestos e incluir el texto de bindings.rs al completo.

Una vez hecho esto podemos usar desde el programa principal la librería de la misma forma que hemos visto antes.

Ahora podríamos usar estos bindings directamente en nuestro programa o rustizarlos (darles una capa segura alrededor e idiomática) y subirlo a Crates.io.

El código del post está en GitHub

Introducción a Prolog, tutorial en español

Prolog es un lenguaje de programación lógico, quizá uno de los más populares de este paradigma ya que fue el primero en implementarlo, en el año 1972 en Francia.

Durante un tiempo, se creyó que PROLOG supondría la revolución de los lenguajes de programación, siendo uno de los estandartes de los lenguajes de programación de quinta generación. Tanto se creía que Borland, la famosa empresa de compiladores para MS-DOS, tenía Turbo Prolog, junto a Turbo C++, Turbo Pascal, Turbo Assembler y Turbo Basic.

Desafortunadamente, Prolog no triunfó como se esperaba y solo fue usado dentro del mundo de la Inteligencia Artificial. Existe un estándar ISO sobre Prolog (al igual que Ada, C++ y otros lenguajes estandarizados) pero no es demasiado influyente. Tampoco ha habido ningún éxito en alguna de las versiones propuestas para dotarle de orientación a objetos al lenguaje.

Prolog sin embargo ha influenciado a algunos lenguajes como Erlang, que toman algunos aspectos de él.

No obstante, Prolog sigue siendo un lenguaje muy interesante, diferente al resto de lenguajes (tanto imperativos, como funcionales), así que pongámonos a ello.

Actualmente existen varios compiladores de Prolog: SWI Prolog, GNU Prolog, Visual Prolog (al mucha gente no lo considera Prolog de verdad), …

La mejor versión bajo mi punto de vista es SWI Prolog, que tiene una librería de predicados bastante extensa. Es rápido y permite generar ejecutables nativos (realmente no lo son, pero la máquina virtual de Prolog ocupa muy poco y apenas se nota en el tamaño del ejecutable).

Lo podéis descargar gratuitamente desde su página oficial que como curiosiad, está hecha en SWI Prolog. También está en la paquetería de las distribuciones GNU/Linux habituales.

Nuestro primer programa

Para empezar con Prolog voy a tomar un camino distinto de muchos tutoriales y voy a empezar haciendo un programa con Entrada/Salida y que se ejecute como un binario independiente. La potencia de Prolog no está ahí especialmente, pero es un buen punto de partida

Para ello definimos un predicado main de la siguiente forma y lo guardamos en un fichero main.pl.

¿Qué hace el programa? Imprime en pantalla Hola Mundo (write), una nueva línea (nl), lee un string de teclado con el separador \n y lo unifica con la variable Nombre. Esto ya veremos que significa, pero de momento puedes pensar que Nombre es una variable de salida y que a partir de ahí Nombre tiene un valor establecido.

Compilamos con el siguiente comando:

Con esto le decimos a SWI Prolog que el objetivo a demostrar es main y que nos genere un fichero stand_alone (independiente).

Y ejecutamos el fichero ejecutable como uno más.

Ahora que ya sabemos como se generan programas compilados, vamos a introducirnos más en lo que hace especial a Prolog.

La terminal de Prolog

Prolog fue diseñado con una terminal interactiva en mente. La idea era que el usuario fuese introduciendo preguntas y el programa en Prolog fuese contestando. Este enfoque, similar a usar un programa desde el REPL de tu lenguaje, no ha acabado cuajando, pero es necesario pasar por él. Más adelante veremos como con SWI Prolog no hace falta usar la terminal. La terminal se abre escribiendo swipl en la línea de comandos:

Vemos un símbolo de interrogación. Eso nos permite saber que estamos en una terminal de Prolog. Podemos escribir write(“Hola”). y tener nuestro hola mundo tradicional, aunque no es muy interesante, pero sí es muy interesante que después escribe true. Más adelante veremos por qué.

Los programas Prolog

En Prolog los programas son algo diferentes a lo que estamos acostumbrados. Realmente en Prolog no hay programas sino una base de datos. Un programa se compone de predicados, muy parecidos a los del Cálculo de Predicados. Los predicados aportan información sobre las relaciones entre elementos. Todos los predicados tienen que acabar en punto.

Siguiendo las mismas normas que el cálculo de predicados:

  • Las constantes empiezan por minúscula
  • Las variables empiezan por mayúscula
  • Las funciones son constantes seguidas de N teŕminos. Son funciones estrictamente matemáticas.
  • Los predicados pueden ser atómicos o compuestos, con operadores lógicos (and, or, implica, etc)

Prolog durante la ejecución, va a intentar demostrar que el predicado es cierto, usando el algoritmo de backtracking. Y ahí está la verdadera potencia de Prolog. Veamos unos ejemplos:

Guarda ese archivo con extensión .pl y ejecuta swipl comida.pl.

Ahora en la terminal podemos hacer preguntas. ¿Es la manzana una fruta? Prolog responde verdadero. ¿Es la pera una fruta? Prolog responde que falso, porque según el archivo comida.pl, no lo es. Prolog no es inteligente, no sabe que significan las palabras, simplemente actúa siguiendo un conjunto de normas formales.

Hemos dicho que Prolog tiene variables. Una variable en Prolog es un marcador de hueco, es algo que no existe, porque no es ninguna constante en específico. Veamos la potencia de las variables con este otro predicado.

En este caso pedimos demostrar fruta(X).. Prolog buscará la primera solución que demuestra el predicado, que es que X valga manzana. Aquí podemos pulsar ENTER y Prolog se para o pulsar N y Prolog busca otra solución. ¿Potente, verdad? Prolog realiza un proceso interno que se llama unificación, es importante saber como funciona para ver que hace Prolog en realidad.

Unificación

La unificación es un proceso que combina dos predicados en uno que encaja. Para ello buscamos las sustituciones de valores con los que dos predicados son compatibles (realmente solo se pueden modificar las variables). No obstante, Prolog busca siempre el unificador más general, que es aquel que unifica dejando los predicados de forma más genérica posible, es decir, que pueden usarse con más valores.

Espero que esta imagen aclare el concepto de unificación. Básicamente Prolog para intentar demostrar un predicado intentará unificar con otros predicados del programa. Así cuando ponemos por ejemplo comida(manzana) , unifica con comida(X) así que Prolog toma ese predicado para continuar.

Backtracking

Cuando Prolog intenta demostrar un predicado aplica el algoritmo de backtracking. Este algoritmo recorre todas las soluciones posibles pero de forma más inteligente que la fuerza bruta. Backtracking intenta conseguir una solución hasta que un predicado falla, en ese momento, Prolog va hacia atrás y continúa por otra vía que pueda seguir.

Cada predicado es un nodo. Si un predicado falla se vuelve atrás. Esto es muy interesate ya que Prolog técnicamente puede ejecutar código hacia atrás.

Un predicado Prolog sigue esta estructura:

Predicados avanzados

Pero los predicados de Prolog no tienen por qué ser así de simples. Normalmente se usa el operador :- para indicar algo que para que se cumpla la parte de la izquierda, tiene que cumplirse la parte de la derecha antes (en cálculo de predicados es ←).

Por ejemplo, todas las frutas son comidas, así que podemos añadir esto a nuestro archivo.

Y los predicados en Prolog se pueden repetir y repetir y repetir. Prolog siempre intenta demostrar de arriba a abajo, si falla un predicado, prueba con el siguiente más para abajo y termina cuando no hay más predicados que probar. ¡Así que podemos definir comida en base a más predicados!

Operaciones

En Prolog existen varios operadores importantes:

  • , (coma) AND
  • ; (punto y coma) OR
  • A = B, se intenta unificar A y B. Devuelve true si funciona
  • A \= B es falso si A y B unifican
  • A is B, se evalúa B (es decir, se calcula lo que representa) y se unifica con A
  • A =:= B , evalúa A, evalúa B y los compara. Verdadero si son iguales
  • A =\= B, evalúa A, evalúa B y los compara. Falso si son iguales
  • Y muchos otros como =<, >=, >, < que tienen el comportamiento esperado.
  • Las operaciones matemáticas solo se pueden introducir en expresiones que vayan a ser evaluadas.

Quiero prestar especial atención en símbolo de igual que no es asignación sino unificación, pero puede parecerse. Estas dos líneas son equivalentes:

Ya que en ambos casos se unifica X con 5.

Veamos un ejemplo de todo esto, ya mucho más realista.

Lo cargamos con swipl restaurante.pl y podemos contestar a las siguientes preguntas de forma sencilla:

¿Qué valor calórico tiene la comida de paella, trucha y flan?

Dime una comidas equilibrada que lleve naranja de postre

¿Cuántas comidas con naranja hay?

Variables anónimas y predicados predefinidos

Si te fijas en el predicado comidas_con_naranja, es diferente al resto. Esta programado de otra forma. La salida por pantalla se hace con write como ya habíamos visto al principio, write es un predicado que siempre es cierto y en caso de backtracking simplemente pasa. aggregate_all es también otro predicado incluido en SWI Prolog, para en este caso, contar cuantas soluciones tiene el predicado comida(_,_,naranja). X unifica en aggregate_all con el valor que toca (que es una constante, los números son constantes) y en las siguientes sentencias (write), X ha sido sustituido por el valor con el que unificó en aggregate_all.

Por otro lado, ¿qué significa la barra baja? Es una variable anónima. Cuando no usamos una variable en más lugares y no nos interesan sus valores podemos simplemente poner barra baja.

Listas en Prolog

Prolog tiene un tipo de dato más avanzado, las listas. Su tamaño es dinámico y es conveniente distinguir la cabeza de la cola. La cabeza es el primer elemento de una lista, la cola el resto de la lista.

Las listas se crean con corchetes:

sumlist es un predicado de SWI que hace la suma de todos los elementos de una lista.

Con la barra podemos separar cabeza y cola de una lista:

Implementando sumlist

Vamos a ver como se puede implementar sumlist con Prolog de forma sencilla.

El predicado es sencillo, para un caso base de lista vacía, la suma es 0. Para otros casos más complejos separamos la lista en cabeza H y cola T y la suma es N. Esta suma se define como el resultado de sumar T (queda en X) y la cabeza H.

Assert y retract

¿Podemos crear predicados en tiempo real? Claro. Prolog provee de los predicados especiales assert para añadir y retract para eliminar un predicado.

Operador de corte

Prolog tiene un operador muy controvertido, el operador de corte, !. Se trata de un operador que permite no volver hacia atrás. Hay que intentar no usarlo, pero muchas veces mejora el rendimiento.

Metaprogramación

Prolog tiene un gran soporte para la metaprogramación. Assert y Retract son ya formas de metaprogramación, no obstante Prolog tiene muchas más.

call permite ejecutar código Prolog desde Prolog.

setarg permite modificar un término de un predicado y arg unifica una variable con el término de un predicado que queramos. nb_setarg es la versión de setarg que en caso de backtracking no deshace la operación. Un ejemplo de esto lo podemos encontrar en la definición de aggregate_all en la librería de SWI Prolog:

 

Debug con trace

Prolog posee un predicado muy útil para hacer debugging. Es trace y con el predicado que vaya a continuación podremos inspeccionar todas las operaciones del motor de backtracking.