Un servidor SSH a la tauleta Android

Tota tauleta Android té un Linux amagat al seu interior.

Per arribar fins aquest Linux hi han diverses opcions. La que he trobat més senzilla és mitjançant l’app Termux.

Termux

Termux és una app que es pot instal·lar des del Google Play.

Segons ens diu la seva pàgina:

“Termux combina una potent emulació de terminal amb una extensa col·lecció de packages de Linux :

• Gaudeix de les shells bash i zsh.
• Edita fitxers amb nano i vim (o emacs, però en aquest cas és imprescindible un teclat!)
• Accedeix a servidors remots mitjançant ssh (o, afegeixo, aixeca un servidor ssh i accedeix remotament a la teva tauleta/telèfon!)
• Desenvolupa en C/C++ amb les eines clang, make i gdb.
• Fes servir la consola Python com una calculadora de butxaca (o escriu scripts de propòsit general amb Python).
• Fes check out o clona projectes de repositoris remots amb git o amb subversion.
• Juga amb aventures conversacionals basades en text (us sona la saga Zork?) amb l’interpret frotz.”

Tot això -punt important- sense necessitat de rootejar la tauleta.

Instal·lar Termux no té cap secret. A més de Termux,  convé instal·lar l’app Termux:API que complementa a Termux :

“Termux:API proporciona accés per la línia de comandes a les API’s del disposotiu :

* lectura i enviament de sms des del terminal.
* Accés al GPS des dels scripts.
* Aplicació del dispositiu text-to-speech als resultats de les comandes.
* Vibració del dispositiu.
* Accés al clipboard per als scripts.
* Accés a la llista de contactes per als scripts.”

Per un petit preu, també s’ofereixen altres apps que encara fan més útil Termux.

– Termux:Boot : permet executar scripts quan el dispositiu arrenca.
– Termux:Float : Permetr executar Termuxa una finestra flotant.
– Termux:Styling _ squemes de color i customització de l’aparença delterminal.
– Termux:Task : permet invocar executables de Termux des de Tasker i apps compatibles
– Termux:Widget : permet arrencar scripts de Termux des de la pantalla inicial de la tauleta

La Wiki de Termux és força completa i entenedora. Dins la Wiki de Termux també trobem una completa secció de FAQs.

El que m’ha interessat més ha estat la possibilitat de disposar d’un repositori git a la tauleta, i que aquest repositori fos accessible des d’un altre ordinador mitjançant protocol ssh. És dir, el problema principal que m’he proposat resoldre amb Termux ha estat : com posar en marxa el servidor ssh a la tauleta? idealment, amb el servidor ssh actiu a la tauleta, jo podria connectar-m’hi un client git des del portàtil, per exemple.

Instal·lació del programari

Primer de tot, cal instal·lar el programari necessari a la tauleta. La instal·lació de Termux des de Google Play no té cap dificultat. Un cop instal·lat, engego Termux…

Welcome to Termux!

Wiki: https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel: #termux on freenode
Gitter chat: https://gitter.im/termux/termux
Mailing list: termux+subscribe@groups.io

Search packages: pkg search 
Install a package: pkg install 
Upgrade packages: pkg upgrade
Learn more: pkg help
bash-4.4$ 

Observo que només hi ha un sistema base i cal afegir tot el programari que emcalgui.

Executo les següents instruccions (un teclat extern USB o Bluetooth pot ser de molta ajuda!)

Afegir paquets és molt semblant al procediment que se segueix amb distribucions Linux com Debian.

Vull una shell bash, com al Linux del sobretaula:

bash-4.4$ pkg install bash
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree       
Reading state information... Done
36 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  bash
1 upgraded, 0 newly installed, 0 to remove and 35 not upgraded.
Need to get 360 kB of archives.
After this operation, 0 B of additional disk space will be used.
Get:1 http://termux.net stable/main arm bash arm 4.4.23-2 [360 kB]
Fetched 360 kB in 0s (1291 kB/s)
(Reading database ... 7367 files and directories currently installed.)
Preparing to unpack .../archives/bash_4.4.23-2_arm.deb ...
Unpacking bash (4.4.23-2) over (4.4.19) ...
Setting up bash (4.4.23-2) ...
bash-4.4$ 

Vull C/C++ i Python per a poder programar

– instal·lació de clang

bash-4.4$ pkg install clang
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree
Reading state information... Done
38 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be upgraded:
clang
1 upgraded, 0 newly installed, 0 to remove and 37 not upgraded.
Need to get 11.1 MB of archives.
After this operation, 13.4 MB of additional disk space will be used.
Get:1 http://termux.net stable/main arm clang arm 6.0.1 [11.1 MB]
Fetched 11.1 MB in 6s (1664 kB/s)
(Reading database ... 7379 files and directories currently installed.)
Preparing to unpack .../archives/clang_6.0.1_arm.deb ...
Unpacking clang (6.0.1) over (5.0.1-1) ...
Setting up clang (6.0.1) ...
bash-4.4$

– instal·lació de python :

bash-4.4$ pkg install python
Hit:1 http://termux.net stable InRelease
Reading package lists... Done
Building dependency tree       
Reading state information... Done
37 packages can be upgraded. Run 'apt list --upgradable' to see them.
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  python
1 upgraded, 0 newly installed, 0 to remove and 36 not upgraded.
Need to get 5564 kB of archives.
After this operation, 393 kB disk space will be freed.
Get:1 http://termux.net stable/main arm python arm 3.6.6 [5564 kB]
Fetched 5564 kB in 3s (1849 kB/s) 
(Reading database ... 7397 files and directories currently installed.)
Preparing to unpack .../archives/python_3.6.6_arm.deb ...
Unpacking python (3.6.6) over (3.6.4-1) ...
dpkg: warning: unable to delete old directory '/data/data/com.termux/files/usr/lib/python3.6/lib2to3/tests': Directory not empty
Setting up python (3.6.6) ...
Setting up pip...
Looking in links: /data/data/com.termux/files/usr/tmp/tmp599bopw8
Collecting setuptools
Collecting pip
Installing collected packages: setuptools, pip
  Found existing installation: setuptools 28.8.0
    Uninstalling setuptools-28.8.0:
      Successfully uninstalled setuptools-28.8.0
  Found existing installation: pip 9.0.1
    Uninstalling pip-9.0.1:
      Successfully uninstalled pip-9.0.1
Successfully installed pip-10.0.1 setuptools-39.0.1
bash-4.4$ 

Haureu notat que els missatges que estic mostrant no corresponen a una instal·lació inicial si no a un upgrade. És que, de fet, per a escriure aquest post estic tornant a passar l’instal·lador.

En resum : el procediment és el mateix que amb els gestor de paquets d’altres distribucions.

Vull el git per mantenir el meu codi ben versionat

– git

pkg install git

Vull un editor que em permeti fer de tot, i que a més sigui programable amb Lisp!

– emacs

pkg install emacs

Necessito relaxar-me i distreure’m amb jocs de ficció interactiva.

– frotz

pkg install frotz

Criptografia i ssh.

– openssl :

pkg install openssl

– openssh :

pkg install openssh

Altres paquets que poden ser interessants : el gpg, netcat, curl…

Si feu

pkg list-all

Obtindreu una llista dels paquets disponibles. En general, instal·lar un paquet és tan senzill com

pkg install nom_paquet

Configuració del servidor SSH

El client SSH ens queda instal·lat sense més que instal·lar el paquet openssh El que resta és configurar el servidor ssh per a fer accessible la tauleta des de l’exterior.

Em baso en el que hi ha a :

https://glow.li/technology/2015/11/06/run-an-ssh-server-on-your-android-with-termux/

i també a https://wiki.termux.com/wiki/Remote_Access

El primer que cal tenir en compte és que el Termux només es per a un usuari. Això vol dir que qualsevol accés des de l’exterior ha de fer-se amb l’usuari que termux ens ha proporcionat. Però com us adonareu, termux no ens dona el password d’aquest usuari. És dir: no podem fer un login amb usuari – password.

Necessàriament, doncs, hem de fer el login d’una altre forma. La solució és crear una parell clau privada – clau pública d’accés amb ssh-keygen.

Simplement, executo ssh-keygen amb les opcions per defecte.

En el meu cas, com que ja disposava d’un parell clau privada/clau pública i ja l’he distribuït, el que he fet és generar el parell de claus a una carpeta alternativa.

bash-4.4$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/data/data/com.termux/files/home/.ssh/id_rsa): /data/data/com.termux/files/home/alternative1_rsa
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /data/data/com.termux/files/home/alternative1_rsa.
Your public key has been saved in /data/data/com.termux/files/home/alternative1_rsa.pub.
The key fingerprint is:
SHA256:xMACExf/9or00y35to2/vw/ft3HBWKZypXOoWFJpAFk u0_a89@localhost
The key's randomart image is:
+---[RSA 2048]----+
|  +ooo..+E       |
|   o...+  . .    |
|     .. o  +   + |
|       o  o   X  |
|        S. o B + |
|       . .+ + o .|
|      .  o.+  ...|
|     . o..+ oo o=|
|      . o. ++o+=X|
+----[SHA256]-----+
bash-4.4$ 

Ara puc observar que han aparegut els fitxers id_rsa i id_rsa.pub a la carpeta ~/.ssh. Respectivament la clau privada i la clau pública que he generat.

bash-4.4$ ls -al ~/.ssh
total 32
drwx------    2 u0_a89   u0_a89        4096 Sep  1 22:33 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 17:20 ..
-rw-------    1 u0_a89   u0_a89           0 Sep  1 22:34 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
bash-4.4$ 

Ara vaig a provar que el servidor ssh funciona. Per a fer-ho, primer de tot l’engego (amb termux en mode bàsic, no tinc una altre opció que engegar manualment)

sshd

Vull provar connectant-me amb ssh des del mateix termux, per a fer-ho cal que la clau pública que acabo de generar estigui a la llista de claus autoritzades

Per això, simplement la concateno a authorized_keys que es troba a ~/.ssh

bash-4.4$ cat id_rsa.pub >> authorized_keys
bash-4.4$ chmod 600 authorized_keys
bash-4.4$ ls -al
total 36
drwx------    2 u0_a89   u0_a89        4096 Sep  2 18:42 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 17:20 ..
-rw-------    1 u0_a89   u0_a89         742 Sep  2 18:42 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
bash-4.4$ 

Arribats a aquest punt, ja puc provar el meu servidor ssh

bash-4.4$ ssh ip_tauleta -p 8022
Welcome to Termux!

Wiki:            https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel:     #termux on freenode
Gitter chat:     https://gitter.im/termux/termux
Mailing list:    termux+subscribe@groups.io

Search packages:   pkg search 
Install a package: pkg install 
Upgrade packages:  pkg upgrade
Learn more:        pkg help
$ 

Accés des de l’exterior

A la vista de com ha funcionat aquest primer accés, ja puc veure quin és el procediment per accedir remotament al servidor ssh de la tauleta: cal que a les authorized_keys de la tauleta hi hagi la clau pública de l’usauri de l’ordinador remot amb el que penso accedir.

Això vol dir que si vull accedir a la tauleta des del meu sobretaula, el procediment és el següent:

1 – he de generar una parella clau privada-clau pública amb ssh-keygen al sobretaula
2 – aleshores, he de concatenar la clau pública generada a l’authorized_keys de la la tauleta.
3 – reinicio sshd.
Per engegar el servidor :

sshd

Per controlar-ne el funcionament :

logcat -s 'syslog:*'

Per aturar el servidor :

pkill sshd

He de copiar la clau pública del sobretaula a la tauleta. La solució més primitiva és fer servir un pendrive usb, passant físicament la clau des del sobretaula a la tauleta. Però, certament, aquest mètode no és gaire elegant.

Hi ha una opció millor : Des de la tauleta puc connectar-me amb scp o sftp al sobretaula (evidentment, sempre que el sobretaula també tingui un servidor ssh! en funcionament)

$ sftp albert@ip_sobretaula
Connected to albert@ip_sobretaula.
sftp> ls
Baixades                               Escriptori                             ...      
sftp> cd .ssh
sftp> ls
authorized_keys   authorized_keys~  id_rsa            id_rsa.pub        known_hosts       
sftp> get id_rsa.pub id_rsa_sobretaula.pub
Fetching /home/albert/.ssh/id_rsa.pub to id_rsa_sobretaula.pub
...
sftp> exit
$ ls -al
total 36
drwx------    2 u0_a89   u0_a89        4096 Sep  2 22:25 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 22:23 ..
-rw-------    1 u0_a89   u0_a89         742 Sep  1 22:06 authorized_keys
-rw-------    1 u0_a89   u0_a89        3381 Sep  1 21:15 id_rsa
-rw-------    1 u0_a89   u0_a89         742 Sep  1 21:15 id_rsa.pub
-rw-------    1 u0_a89   u0_a89         740 Sep  2 22:25 id_rsa_sobretaula.pub
-rw-r--r--    1 u0_a89   u0_a89         532 Sep  1 21:32 known_hosts
$ 

Cal indicar que des del sobretaula, també hi ha la possibilitat de fer servir ssh-copy-id per passar la clau pública tot just generada a un servidor remot. (consulteu https://www.ssh.com/ssh/copy-id).

ssh-copy-id

Es pot fer amb una instrucció com aquesta:

ssh-copy-id -i ~/.ssh/mykey user@host

Aquesta instrucció accedeix al host remot i afegeix la clau pública (*) de mykey al fitxer authorized_keys del host remot.

(*) La clau pública! La clau privada, com el seu nom indica, és privada i ningú més que el propietari l’ha de conèixer!

Si li cal, ssh-copy-id demanarà la forma d’autenticar-se amb el host remot. En el cas de Termux, això planteja el problema que no es coneix el password de l’usuari de Termux.

Arribats a aquest punt, ja tinc la clau pública del sobretaula a la tauleta i l’he concatenat a l’authorized_keys. Reinicio el servidor sshd i, des del sobretaula provo a accedir :

albert@artemis:~$ ssh 192.168.0.112 -p 8022
Welcome to Termux!

Wiki:            https://wiki.termux.com
Community forum: https://termux.com/community
IRC channel:     #termux on freenode
Gitter chat:     https://gitter.im/termux/termux
Mailing list:    termux+subscribe@groups.io

Search packages:   pkg search 
Install a package: pkg install 
Upgrade packages:  pkg upgrade
Learn more:        pkg help
$ 

Ja puc accedir a la tauleta des del sobretaula.

Seguint el mateix procediment puc donar accés ssh a la tauleta des de qualsevol altre equip. El truc és generar el parell clau privada/clau pública a cada ordinador des del que em vulgui connectar i concatenar la clau pública obtinguda a l’authorized_keys de la tauleta.

Accés Git al repositori de la tauleta

Finalment, una aplicació pràctica. Inicialitzo un repositori git a la tauleta. En el meu cas he creat una carpeta workspace amb diferents subcarpetes per a desar-hi projectes en diferents llenguatges. He inicialitzat un repositori git a aquesta carpeta workspace.

$ ls 
albert                alternative1_rsa      alternative1_rsa.pub  hosts                 prova.txt             storage               workspace
$ cd workspace/
$ ls -al
total 40
drwx------   10 u0_a89   u0_a89        4096 Sep  1 20:53 .
drwx------    7 u0_a89   u0_a89        4096 Sep  2 22:30 ..
drwx------    7 u0_a89   u0_a89        4096 Sep  1 20:58 .git
drwx------    2 u0_a89   u0_a89        4096 Aug 19 12:48 as
drwx------    2 u0_a89   u0_a89        4096 Aug 19 12:49 awk
drwx------    2 u0_a89   u0_a89        4096 Dec 16  2017 bash
drwx------    2 u0_a89   u0_a89        4096 Feb 20  2018 c
drwx------    2 u0_a89   u0_a89        4096 Feb 20  2018 cc
drwx------    2 u0_a89   u0_a89        4096 Dec 16  2017 elisp
drwx------    4 u0_a89   u0_a89        4096 Aug 19 12:49 python
$ 

Ara me’n vaig al sobretaula, i obro, per exemple, l’Eclipse que té el client EGit.

Simplement he de configurar ela URI del repositori al que vull accedir. He de parar atenció a:

1 – Indicar protocol ssh.
2 – Indicar la ip de la tauleta i, molt important, el port 8022.
3 – He indicat el path complet fins el repositori
3 – No cal que indiqui usuari i password.

La imatge ho aclareix :

git01

La següent pantalla em mostra la branca master del repositori git de la tauleta :

Selecció_002

A partir d’aquest punt ja podria fer el checkout dels projectes.

Molt important : per a que tot això funcioni cal que les IP dels diferents dispositius involucrats siguin fixes. Això vol dir que

1 – Al router de la vostra xarxa local cal donar IP fixes (dins del rang intranet, òbviament, és dir 192.168.x.x) als diferents ordinadors , impresores, smartphones o tauletes que pugueu tenir connectats

2 – Cal indicar a les tauletes que facin servir sempre la mateixa IP que li heu fet correspondre al router  per connectar-se a la vostra xarxa local.

Caçar el Wumpus!

huntthewumpus

“Hunt the Wumpus” és un joc d’ordinador de 1972, inicialment escrit en mode text i desenvolupat en llenguatge BASIC. La seva simplicitat, a més de tenir les fonts disponibles, va motivar l’aparició de diverses i successives versions.

En aquest post escric la meva pròpia versió en català i en Python

Vet aquí les instruccions de “Caçar el Wumpus” :

Caçar el Wumpus
—————
El Wumpus és un monstre enorme i pesat amb la pell plena de ventoses
que s’alimenta de tot allò que cau a les seves urpes.
Tu ets un caçador que vol aconseguir el cap del Wumpus com a trofeu
i ets a un castell on se sap que n’hi ha un.
El castell té vint habitacions, cada habitació es connecta amb
altres tres habitacions.
Si entres a l’habitació on és el Wumpus, et menjarà.
Al castell hi ha un parell d’habitacions que tenen un fals terra.
Només entrar s’ensorra el terra i caus a un pou amb un potent àcid al fons.
Tothom que entra a una habitació amb pou, mor.
Menys el Wumpus. El Wumpus no hi cau perquè amb les seves ventoses
s’enganxa a les parets i no toca l’àcid.
Al castell també hi ha un parell de rats penats gegants.
Si entres a una habitació amb un rat penat, t’agafarà, se t’emportarà volant
i et deixarà caure a una habitació qualsevol del castell.
Els rats penats no poden endur-se al Wumpus perquè pesa massa per ells
i el Wumpus no es pot menjar als rats penats perquè són massa ràpids
per atrapar-los.
Saps que a alguna de les habitacions adjacents hi ha el Wumpus
perquè mai s’ha banyat i fa molta pudor, i el pots ensumar.
Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales,
I, finalment, saps que a les habitacions adjacents poden haver pous
perquè sents el soroll de l’acid bullint.
Tens cinc fletxes. Has de moure’t pel castell
i quan dedueixis a quina habitació està el Wumpus, pots tirar-li
una fletxa des d’una de les habitacions adjacents.
Si l’habitació a la que has tirat la fletxa és la del Wumpus,
el mataràs i hauràs guanyat.
Però si el Wumpus no és a l’habitació, el soroll de la fletxa
potser el posarà en alerta i farà que es mogui a alguna habitació
contigua a la que ocupa.
Si esgotes totes les fletxes, aleshores ja no tens defensa
possible contra el Wumpus, que et trobarà i et menjarà.

Com he implementat les anteriors instruccions?

“El castell té vint habitacions, cada habitació es connecta amb altres tres habitacions.”

De fet, el castell del wumpus es pot modelar com un dodecaedre, on cada vèrtex representa una habitació i cada aresta ens porta a l’habitació contigua.

Vet aquí una bonica imatge d’un dodecaedre regular extreta de la Viquipèdia:

Si aplano aquesta figura obtinc una versió del mapa que em serà més útil.

Per a dibuixar el mapa del castell he fet servir el següent codi Python :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import Tkinter as tk
import math

class Room:
    xc = 0
    yc = 0
    x0 = 0
    y0 = 0
    x1 = 0
    y1 = 0
    doors = []

if __name__ == "__main__":
    # initialize map
    rooms = [Room() for i in range(0, 20)]

    rooms[ 0].doors = [1, 4, 5]
    rooms[ 1].doors = [0, 2, 7]
    rooms[ 2].doors = [1, 3, 9]
    rooms[ 3].doors = [2, 4, 11]
    rooms[ 4].doors = [0, 3, 13]
    rooms[ 5].doors = [0, 6, 14]
    rooms[ 6].doors = [5, 7, 16]
    rooms[ 7].doors = [1, 6, 8]
    rooms[ 8].doors = [7, 9, 17]
    rooms[ 9].doors = [2, 8, 10]
    rooms[10].doors = [9, 11, 18]
    rooms[11].doors = [3, 10, 12]
    rooms[12].doors = [11, 13, 19]
    rooms[13].doors = [4, 12, 14]
    rooms[14].doors = [5, 13, 15]
    rooms[15].doors = [14, 16, 19]
    rooms[16].doors = [6, 15, 17]
    rooms[17].doors = [8, 16, 18]
    rooms[18].doors = [10, 17, 19]
    rooms[19].doors = [12, 15, 18]    
    
    root = tk.Tk()
    canvas = tk.Canvas(root, width=600, height=600, borderwidth=0, highlightthickness=0, bg="grey")
    j = 0
    R = 20
    for i in range(0, 5):
        x = 300 + int(80.0 * math.cos( (2.0 * math.pi / 5.0) * i)) 
        y = 300 + int(80.0 * math.sin( (2.0 * math.pi / 5.0) * i))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 10):
        x = 300 + int(180.0 * math.cos( (math.pi / 5.0) * i)) 
        y = 300 + int(180.0 * math.sin( (math.pi / 5.0) * i))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 5):
        x = 300 + int(280.0 * math.cos( (2.0 * math.pi / 5.0) * i - (math.pi / 5.0)))
        y = 300 + int(280.0 * math.sin( (2.0 * math.pi / 5.0) * i - (math.pi / 5.0)))

        rooms[j].xc = x
        rooms[j].yc = y
        rooms[j].x0 = x - R
        rooms[j].y0 = y - R
        rooms[j].x1 = x + R
        rooms[j].y1 = y + R
        j = j + 1

    for i in range(0, 20):
        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[0]].xc, \
                           rooms[rooms[i].doors[0]].yc)

        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[1]].xc, \
                           rooms[rooms[i].doors[1]].yc)
        
        canvas.create_line(rooms[i].xc, \
                           rooms[i].yc, \
                           rooms[rooms[i].doors[2]].xc, \
                           rooms[rooms[i].doors[2]].yc)

    for i in range(0, 20):
        canvas.create_oval(rooms[i].x0, rooms[i].y0, rooms[i].x1, rooms[i].y1, fill='white')
        canvas.create_text(rooms[i].xc, rooms[i].yc, text='%d' % i, fill='black')
        
    canvas.grid()
    root.wm_title("El Castell del Wumpus!")
    root.mainloop()

Destacar en el codi anterior l’us del canvas de Tkinter per a fer el dibuix, i l’us de la Python comprehension per a inicialitzar l’array rooms (just abans d’assignar les door de cada room).

Al codi anterior ja apareix l’estructura del mapa : el array rooms, de 20 posicions, on cada posició conté una instancia de la classe Room que, entre d’altres propietats, té l’array doors de tres posicions, que manté els números de les habitacions que es connecten a l’habitació.

“Al castell hi ha un parell d’habitacions que tenen un fals terra…
Al castell també hi ha un parell de rats penats gegants…
Tens cinc fletxes…·

Per tant, tenim els següents personatges o objectes del joc : un caçador, un wumpus, dos pous d’àcid, dos rats penats gegants i cinc fletxes. Les cinc fletxes les porta el caçador i no cal, doncs, ubicar-les específicament. El que cal fer en iniciar el joc és col·locar els objectes wumpus, caçador, pous i rats penats al castell, de forma que el caçador no coincideix amb el wumpus, els rats penats i els pous; els rats penats no coincideixen entre ells ; i els pous tampoc. És dir : el wumpus podria compartir habitació amb un rat-penat i un pou. Però això és possible perquè “El wumpus no hi cau [als pous] perquè amb les seves ventoses s’enganxa a les parets i en pot sortir sense perill.” i “Els rats penats no poden endur-se al wumpus perquè pesa massa per ells i el wumpus no es pot menjar als rats penats perquè són massa ràpids per ell.”.

Això es fa amb aquest codi :

Una classe molt simple GameObject, que manté la ubicació de l’objecte

class GameObject:
    roomNumber = -1

    def __init__(self, roomNumber):
        self.roomNumber = roomNumber
    # initialize characters and objects
    wumpusRoom = -1
    bat1Room = -1
    bat2Room = -1
    pit1Room = -1
    pit2Room = -1
    hunterRoom = -1
    arrows = 5

    while (hunterRoom == wumpusRoom) or \
          (hunterRoom == bat1Room) or   \
          (hunterRoom == bat2Room) or   \
          (hunterRoom == pit1Room) or   \
          (hunterRoom == pit2Room) or   \
          (pit1Room == pit2Room) or     \
          (bat1Room == bat2Room):
        
        hunterRoom = rnd.randint(0, 19)
        wumpusRoom = rnd.randint(0, 19)
        bat1Room = rnd.randint(0, 19)
        bat2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)

    hunter = GameObject(hunterRoom)
    wumpus = GameObject(wumpusRoom)
    bat1 = GameObject(bat1Room)
    bat2 = GameObject(bat2Room)
    pit1 = GameObject(pit1Room)
    pit2 = GameObject(pit2Room)

    return {"rooms":rooms, "hunter":hunter, "wumpus":wumpus,
            "bat1":bat1, "bat2":bat2, "pit1":pit1, "pit2":pit2, "arrows":arrows}

L’estratègia utilitzada és repetir fins que es torna una combinació a l’atzar que ubica tots els objectes en habitacions diferents.

Destacar, també, l’us d’un diccionari per retornar els objectes.

“Si entres a l’habitació on és el Wumpus, et menjarà…
Tothom que hi cau [a una habitació amb pou], mor…
Si entres a una habitació amb un rat penat, t’agafarà, se t’emportarà volant
i et deixarà caure a una habitació qualsevol del castell…

A la funció enterRoom tenim la codificació de les regles anteriors

def enterRoom(gameObjects):
    continueGame = True
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    
    print "\nEts a l'habitació número %d" % hunterRoom

    if wumpusRoom == hunterRoom:
        print "El wumpus és a l'habitació!"
        print "T'ha atrapat i comença a devorar-te!" 
        print "No és que sigui dolent... Et menja perquè és la seva natura de Wumpus..."    
        continueGame = False

    if continueGame and (hunterRoom in (pit1Room, pit2Room)):
        print "Hi ha un pou amb acid a l'habitació!"
        print "Has caigut dins i comences a dissoldre't de forma lenta i dolorosament agònica!"
        continueGame = False

    if continueGame and (hunterRoom in (bat1Room, bat2Room)):
        print "I un rat penat gegant a l'habitació! T'ha agafat i se t'emporta volant!"
        newHunterRoom = rnd.randint(0, 19)
        newBat1Room = rnd.randint(0, 19)
        newBat2Room = rnd.randint(0, 19)
        gameObjects.get("hunter").roomNumber = newHunterRoom
        gameObjects.get("bat1").roomNumber = newBat1Room
        gameObjects.get("bat2").roomNumber = newBat2Room
        print "El rat penat t'ha deixat caure a l'habitació número %d" % newHunterRoom
        continueGame = enterRoom(gameObjects)

    if not continueGame:
        print "Has mort de forma horrible!" 
        print "..." 
        print "Però altres vindran a intentar triomfar allà on tu has fracassat tan lamentablement "

    return continueGame


“Has de moure’t pel castell…”

Una de les possibles accions és, doncs, moure’s a una habitació adjacent.

El següent codi és la part de la funció actionHunter que recull l’acció “moure’s” del caçador :

def actionsHunter(gameObjects):
    continueGame = True
    wumpusMove = False
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    arrows = gameObjects.get("arrows")
    rooms = gameObjects.get("rooms")
    [door0, door1, door2] = rooms[hunterRoom].doors

    while True:
        action = raw_input("Moure's 'm' o Tirar una fletxa 's' ? ")
        if action in ('m','s','M','S'):
            break

    while True:
        try:
            door = int(raw_input("A quina habitació %d, %d or %d ? " % (door0, door1, door2)))
            if door in (door0, door1, door2):
              break
        except:
            None

    if (action=='m' or action=='M'):
        gameObjects.get("hunter").roomNumber = door


“quan dedueixis a quina habitació està el Wumpus, pots tirar-li una fletxa des d’una de les habitacions adjacents.

Si l’habitació a la que has tirat la fletxa és la del wumpus, el mataràs i hauràs guanyat.

Però si el Wumpus no és a l’habitació, el soroll de la fletxa potser el posarà en alerta i farà que es mogui a alguna habitació contigua a la que ocupa…”

Això és el que es fa amb el següent fragment de actionsHunter

    if ((action=='s' or action=='S') and \
        ((wumpusRoom == door0) or \
         (wumpusRoom == door1) or \
         (wumpusRoom == door2))):
            print "La fletxa ha matat al Wumpus!"
            print "La protectora d'animals et denunciarà si et descobreixen!"
            print "Ets l'assassí del wumpus!"
            print "Un altre sàdic que mata pobres bestioletes indefenses!"
            print "Suposo que estaràs content, criminal!"
            print "En fi. Suposo que t'he de felicitar perquè has guanyat."
            continueGame = False

    if ((action=='s' or action=='S') and \
        ((wumpusRoom <> door0) and \
         (wumpusRoom <> door1) and \
         (wumpusRoom <> door2))):
            print "has fallat! No hi havia cap wumpus a l'habitació!"

            # move wumpus
            doorsWumpus = doors[wumpusRoom].doors
            randomDoor = rnd.random()
            if randomDoor < 0.75 :                 wumpusMove= True             if randomDoor >= 0 and randomDoor < 0.25:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[0]             if randomDoor >= 0.25 and randomDoor < 0.50:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[1]             if randomDoor >= 0.50 and randomDoor < 0.75:
                gameObjects.get("wumpus").roomNumber = doorsWumpus[2]


Si esgotes totes les fletxes, aleshores ja no tens defensa possible contra el wumpus, que et trobarà i et menjarà.

És la part final d’actionsHunter

            arrows = arrows - 1

            if arrow == 1:
                aux = "fletxa"
            else:
                aux = "fletxes"
            print "Ara tens %d %s" % (arrows, aux)

            if arrow == 0:
                print "No tens fletxes i, per tant, ja no pots matar el Wumpus."
                print "No trigarà a descobrir-te i, aleshores, et menjarà."
                print "Serà molt dolorós i horrible..."
                print "Ja se sent com ve!"
                print "Ara entra per la porta i es llença sobre teu!"
                print "La resistència és inútil.."
                print "Encara ets conscient quan se t'empassa!"
                print "Els àcids de la seva digestio fan la resta. Has mort."
                print "Però recorda que no és que el wumpus sigui dolent..." 
                print "Et menja perquè és la seva natura de Wumpus..."
            continueGame = False

            if continueGame and wumpusMove:
                print "La fletxa ha alertat el Wumpus i es mou! espero que no vingui cap aquí!"

“Saps que a alguna de les habitacions adjacents hi ha el Wumpus perquè mai s’ha banyat i fa molta pudor, i el pots ensumar.

Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales.

I, finalment, saps que a les habitacions adjacents poden haver pous
perquè sents el soroll de l’acid bullint.”

Si el caçador pot entrar a una habitació, pot fer-se una idea de que es trobarà més endavant. És el que s’aconsegueix amb la funció examineRoom.

def examineRoom(gameObjects):
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    arrows = gameObjects.get("arrows")
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    [door0, door1, door2] = rooms[hunterRoom].doors
    
    print "L'habitació %d es connecta amb les habitacions %d, %d i %d" % (hunterRoom, door0, door1, door2)

    if arrows > 1:
        aux = "fletxes"
    else:
        aux = "fletxa"
    print "Encara tens %d %s" % (arrows, aux) 
    
    if wumpusRoom in rooms[hunterRoom].doors:
        print "Fa una insuportable fortor de wumpus!"
        print "Hi ha un wumpus pudent a una de les habitacions que es connecten des d'aquí!"

    if (bat1Room in rooms[hunterRoom].doors) or (bat2Room in rooms[hunterRoom].doors):
        print "Se sent soroll d'ales!"
        print "Hi ha almenys un rat penat gegant a les habitacions que es connecten des d'aquí"

    if (pit1Room in rooms[hunterRoom].doors) or (pit2Room in rooms[hunterRoom].doors):
        print "Se sent el soroll d'àcid bullint!"
        print "Hi ha almenys un pou ple d'àcid a les habitacions que es connecten des d'aquí"

En aquest moment, ja tinc tots els elements. Si ho junto tot el que obtinc és el següent codi :

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import random as rnd

class Room:
    doors = []

class GameObject:
    roomNumber = -1

    def __init__(self, roomNumber):
        self.roomNumber = roomNumber

def initializeObjects():
    # map
    rooms = [Room() for i in range(0, 20)]

    # initialize map
    rooms[ 0].doors = [1, 4, 5]
    rooms[ 1].doors = [0, 2, 7]
    rooms[ 2].doors = [1, 3, 9]
    rooms[ 3].doors = [2, 4, 11]
    rooms[ 4].doors = [0, 3, 13]
    rooms[ 5].doors = [0, 6, 14]
    rooms[ 6].doors = [5, 7, 16]
    rooms[ 7].doors = [1, 6, 8]
    rooms[ 8].doors = [7, 9, 17]
    rooms[ 9].doors = [2, 8, 10]
    rooms[10].doors = [9, 11, 18]
    rooms[11].doors = [3, 10, 12]
    rooms[12].doors = [11, 13, 19]
    rooms[13].doors = [4, 12, 14]
    rooms[14].doors = [5, 13, 15]
    rooms[15].doors = [14, 16, 19]
    rooms[16].doors = [6, 15, 17]
    rooms[17].doors = [8, 16, 18]
    rooms[18].doors = [10, 17, 19]
    rooms[19].doors = [12, 15, 18]

    # initialize characters and objects
    wumpusRoom = -1
    bat1Room = -1
    bat2Room = -1
    pit1Room = -1
    pit2Room = -1
    hunterRoom = -1
    arrows = 5

    while (hunterRoom == wumpusRoom) or \
          (hunterRoom == bat1Room) or   \
          (hunterRoom == bat2Room) or   \
          (hunterRoom == pit1Room) or   \
          (hunterRoom == pit2Room) or   \
          (pit1Room == pit2Room) or     \
          (bat1Room == bat2Room):
        
        hunterRoom = rnd.randint(0, 19)
        wumpusRoom = rnd.randint(0, 19)
        bat1Room = rnd.randint(0, 19)
        bat2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)
        pit2Room = rnd.randint(0, 19)

    hunter = GameObject(hunterRoom)
    wumpus = GameObject(wumpusRoom)
    bat1 = GameObject(bat1Room)
    bat2 = GameObject(bat2Room)
    pit1 = GameObject(pit1Room)
    pit2 = GameObject(pit2Room)

    return {"rooms":rooms, "hunter":hunter, "wumpus":wumpus,
            "bat1":bat1, "bat2":bat2, "pit1":pit1, "pit2":pit2, "arrows":arrows}

def enterRoom(gameObjects):
    continueGame = True
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    
    print "\nEts a l'habitació número %d" % hunterRoom

    if wumpusRoom == hunterRoom:
        print "El wumpus és a l'habitació!"
        print "T'ha atrapat i comença a devorar-te!" 
        print "No és que sigui dolent... Et menja perquè és la seva natura de Wumpus..."    
        continueGame = False

    if continueGame and (hunterRoom in (pit1Room, pit2Room)):
        print "Hi ha un pou amb acid a l'habitació!"
        print "Has caigut dins i comences a dissoldre't de forma lenta i dolorosament agònica!"
        continueGame = False

    if continueGame and (hunterRoom in (bat1Room, bat2Room)):
        print "I un rat penat gegant a l'habitació! T'ha agafat i se t'emporta volant!"
        newHunterRoom = rnd.randint(0, 19)
        newBat1Room = rnd.randint(0, 19)
        newBat2Room = rnd.randint(0, 19)
        gameObjects.get("hunter").roomNumber = newHunterRoom
        gameObjects.get("bat1").roomNumber = newBat1Room
        gameObjects.get("bat2").roomNumber = newBat2Room
        print "El rat penat t'ha deixat caure a l'habitació número %d" % newHunterRoom
        continueGame = enterRoom(gameObjects)

    if not continueGame:
        print "Has mort de forma horrible!" 
        print "..." 
        print "Però altres vindran a intentar triomfar allà on tu has fracassat tan lamentablement "

    return continueGame

def examineRoom(gameObjects):
    rooms = gameObjects.get("rooms")
    hunterRoom = gameObjects.get("hunter").roomNumber
    arrows = gameObjects.get("arrows")
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    bat1Room = gameObjects.get("bat1").roomNumber
    bat2Room = gameObjects.get("bat2").roomNumber
    pit1Room = gameObjects.get("pit1").roomNumber
    pit2Room = gameObjects.get("pit2").roomNumber
    [door0, door1, door2] = rooms[hunterRoom].doors
    
    print "L'habitació %d es connecta amb les habitacions %d, %d i %d" % (hunterRoom, door0, door1, door2)

    if arrows > 1:
        aux = "fletxes"
    else:
        aux = "fletxa"
    print "Encara tens %d %s" % (arrows, aux) 
    
    if wumpusRoom in rooms[hunterRoom].doors:
        print "Fa una insuportable fortor de wumpus!"
        print "Hi ha un wumpus pudent a una de les habitacions que es connecten des d'aquí!"

    if (bat1Room in rooms[hunterRoom].doors) or (bat2Room in rooms[hunterRoom].doors):
        print "Se sent soroll d'ales!"
        print "Hi ha almenys un rat penat gegant a les habitacions que es connecten des d'aquí"

    if (pit1Room in rooms[hunterRoom].doors) or (pit2Room in rooms[hunterRoom].doors):
        print "Se sent el soroll d'àcid bullint!"
        print "Hi ha almenys un pou ple d'àcid a les habitacions que es connecten des d'aquí"
    
def actionsHunter(gameObjects):
    continueGame = True
    wumpusMove = False
    hunterRoom = gameObjects.get("hunter").roomNumber
    wumpusRoom = gameObjects.get("wumpus").roomNumber
    arrows = gameObjects.get("arrows")
    rooms = gameObjects.get("rooms")
    [door0, door1, door2] = rooms[hunterRoom].doors

    while True:
        action = raw_input("Moure's 'm' o Tirar una fletxa 's' ? ")
        if action in ('m','s','M','S'):
            break

    while True:
        try:
            door = int(raw_input("A quina habitació %d, %d or %d ? " % (door0, door1, door2)))
            if door in (door0, door1, door2):
              break
        except:
            None

    if (action=='m' or action=='M'):
        gameObjects.get("hunter").roomNumber = door

    if ((action=='s' or action=='S') and \
        ((wumpusRoom == door0) or \
         (wumpusRoom == door1) or \
         (wumpusRoom == door2))):
            print "La fletxa ha matat al Wumpus!"
            print "La protectora d'animals et denunciarà si et descobreixen!"
            print "Ets l'assassí del wumpus!"
            print "Un altre sàdic que mata pobres bestioletes indefenses!"
            print "Suposo que estaràs content, criminal!"
            print "En fi. Suposo que t'he de felicitar perquè has guanyat."
            continueGame = False

    if ((action=='s' or action=='S') and \
        ((wumpusRoom <> door0) and \
         (wumpusRoom <> door1) and \
         (wumpusRoom <> door2))):
            print "has fallat! No hi havia cap wumpus a l'habitació!"

            # move wumpus
            doorsWumpus = doors[wumpusRoom].doors
            randomDoor = rnd.random()
            if randomDoor < 0.75 :                 wumpusMove= True             if randomDoor >= 0 and randomDoor < 0.25:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[0]             if randomDoor >= 0.25 and randomDoor < 0.50:                 gameObjects.get("wumpus").roomNumber = doorsWumpus[1]             if randomDoor >= 0.50 and randomDoor < 0.75:
                gameObjects.get("wumpus").roomNumber = doorsWumpus[2]

            arrows = arrows - 1

            if arrow == 1:
                aux = "fletxa"
            else:
                aux = "fletxes"
            print "Ara tens %d %s" % (arrows, aux)

            if arrow == 0:
                print "No tens fletxes i, per tant, ja no pots matar el Wumpus."
                print "No trigarà a descobrir-te i, aleshores, et menjarà."
                print "Serà molt dolorós i horrible..."
                print "Ja se sent com ve!"
                print "Ara entra per la porta i es llença sobre teu!"
                print "La resistència és inútil.."
                print "Encara ets conscient quan se t'empassa!"
                print "Els àcids de la seva digestio fan la resta. Has mort."
                print "Però recorda que no és que el wumpus sigui dolent..." 
                print "Et menja perquè és la seva natura de Wumpus..."
            continueGame = False

            if continueGame and wumpusMove:
                print "La fletxa ha alertat el Wumpus i es mou! espero que no vingui cap aquí!"

    return continueGame

def gameLoop(gameObjects):
    continueGame = True

    while continueGame:
        continueGame = enterRoom(gameObjects)
        if continueGame:
            examineRoom(gameObjects)
            continueGame = actionsHunter(gameObjects)

instructions = '''
Caçar el Wumpus
---------------
El Wumpus és un monstre enorme i pesat amb la pell plena de ventoses 
que s'alimenta de tot allò que cau a les seves urpes. 
Tu ets un caçador que vol aconseguir el cap del Wumpus com a trofeu 
i ets a un castell on se sap que n'hi ha un.  
El castell té vint habitacions, cada habitació es connecta amb 
altres tres habitacions.
Si entres a l'habitació on és el Wumpus, et menjarà.
Al castell hi ha un parell d'habitacions que tenen un fals terra. 
Només entrar s'ensorra el terra i caus a un pou amb un potent àcid al fons. 
Tothom que entra a una habitació amb pou, mor. 
Menys el Wumpus. El Wumpus no hi cau perquè amb les seves ventoses 
s'enganxa a les parets i no toca l'àcid.
Al castell també hi ha un parell de rats penats gegants. 
Si entres a una habitació amb un rat penat, t'agafarà, se t'emportarà volant 
i et deixarà caure a una habitació qualsevol del castell. 
Els rats penats no poden endur-se al Wumpus perquè pesa massa per ells 
i el Wumpus no es pot menjar als rats penats perquè són massa ràpids 
per atrapar-los.
Saps que a alguna de les habitacions adjacents hi ha el Wumpus
perquè mai s'ha banyat i fa molta pudor, i el pots ensumar.
Saps que a les habitacions adjacents hi poden haver rats-penats
perquè sents el soroll del batec de les seves ales,
I, finalment, saps que a les habitacions adjacents poden haver pous 
perquè sents el soroll de l'acid bullint.
Tens cinc fletxes. Has de moure't pel castell 
i quan dedueixis a quina habitació està el Wumpus, pots tirar-li 
una fletxa des d'una de les habitacions adjacents. 
Si l'habitació a la que has tirat la fletxa és la del Wumpus, 
el mataràs i hauràs guanyat. 
Però si el Wumpus no és a l'habitació, el soroll de la fletxa 
potser el posarà en alerta i farà que es mogui a alguna habitació 
contigua a la que ocupa.
Si esgotes totes les fletxes, aleshores ja no tens defensa 
possible contra el Wumpus, que et trobarà i et menjarà.
'''

if __name__ == "__main__":

    print instructions

    # gameObjects = [rooms, hunter, wumpus, bat1, bat2, pit1, pit2]
    gameObjects = initializeObjects()
    
    gameLoop(gameObjects)

Per si algú té ganes de millorar-lo -afegint una interfície gràfica, per exemple- el codi es pot descarregar del repositori GitHub.

Divisió de polinomis amb Emacs Lisp

Per passar l’estona es poden fer moltes coses: llegir un llibre, escoltar música, veure la tele o escriure programes, entre moltes d’altres.

Per circumstàncies diverses, aquests darrers temps he pogut dedicar moltes estones a escriure programes i, un cop escrits, he pensat que els puc aprofitar per fer-ne un post al bloc de tecnologia.

En aquesta ocasió, es tracta d’un programa que fa la divisió entre dos polinomis. Al programa se li entrega una llista amb els coeficients numèrics del numerador (amb zero per als coeficients nuls) i una llista amb els del denominador. Cal que el grau del polinomi del numerador sigui major o igual que el del denominador.

Amb aquestes condicions, només cal aplicar el conegut algorisme de divisió de polinomis. Un exemple il·lustra el procediment:

Donats e numerador i denominador:

 N: x^3 + -12*x^2 + -42
 D: x + -3

La resposta és:

 Q: x^2 + -9*x + -27
 R: -123

Vet aquí el procediment. Cada parell és (coeficient, grau):

    (1,3)  (-12,2)  (0,1)  (-42,0) | (1,1) (-3,0) 
   -(1,3)   -(-3,2)                  (1,2)(-9,1) (-27,0)
    -------------
       0    (-9,2)   (0,1)  
           -(-9,2) -(27,1)
    ----------------------
                0  (-27,1) (-42,0)
                  -(-27,1) -(81,0) 
    ------------------------------
                        0  (-123,0)

Un exemple numèric diferent (aquí només indico el coeficients):

 6   5   4  3   2   1     | 1  2 3
-6 -12 -18                  6 -7 0 24
----------
    -7 -14  3   2   1
     7  14 21
---------------------
           24   2   1
            0   0   0
---------------------
           24   2   1
          -24 -48 -72
---------------------
              -46 -71

Es tracta d’implementar l’algorisme anterior. A manca d’alguna altre cosa, aquest cop he fet servir Emacs Lisp, el llenguatge d’extensió que porta incorporat l’Emacs. Al tractar-se d’un algorisme essencialment recursiu resulta senzill d’implementar amb un dialecte de Lisp com l’Emacs Lisp.

Bé, doncs és això:

(progn
  (setq coefs (list))
  (setq rest (list))

  (defun show-poly (poly)
    (if (>= (length poly) 1)
	(progn
	  (setq exponent (1- (length poly)))
	  (insert (format "(%s*(x^%d))" (car poly) exponent))
	  (if (> exponent 0)
	      (progn
		(insert "+")
		(show-poly (cdr poly)))))))

  (defun get-quotient (num den)
    (setq lnum (length num))
    (setq lden (length den))
    (setq quotient (list))

    (setq high-coef-num (car num))
    (setq high-coef-denom (car den))
    (setq coef (/ high-coef-num high-coef-denom))

    (dotimes (i lden)
      (setq quotient (append quotient (list (- (nth i num) 
                                      (* coef (nth i den)))))))
    (dotimes (i (- lnum lden))
      (setq quotient (append quotient (list (nth (+ lden i) num)))))

    (newline)
    (insert "Last rest: ")
    (show-poly quotient)
    (newline)
    (cons coef quotient))

  (defun divide (numerator denominator)
    (setq lnum (length numerator))
    (setq lden (length denominator))
    
    (if (>= lnum lden)   
	(progn 
          (setq pair (get-quotient numerator denominator))
          (setq coefs (append coefs (list (car pair))))
          (divide (cdr (cdr pair)) denominator))))

  ;; main
  (newline)
  (newline)
  (insert "Polynomial division")
  (newline)
  (setq num '(1 2 1))
  (setq den '(1 1))
  (newline)
  (insert "divide")
  (newline)
  (show-poly num)
  (newline)
  (insert "by")
  (newline)
  (show-poly den)
  (newline)
  (divide num den)
  (newline)
  (insert "Quotient: ")
  (show-poly coefs)
  (newline))

Per a executar el programa copieu el codi anterior a un buffer de l’Emacs i executeu-lo amb C-x C-e (la seqüència control-x control-m).

El programa calcularà la divisió del polinomi x² + 2x + 1 per x + 1, resultat x + 1 i rest 0. Per a provar amb altres polinomis n’hi ha prou de canviar el parell de línies

  (setq num '(1 2 1))
  (setq den '(1 1))

El codi també està al meu GitHub

I, per acabar, encara que aquests dies han donat per algun altre joc amb Python que segurament també publicaré, espero que els propers posts siguin una mica més sucosos (en cartera: programació funcional amb javascript i underscore.js. A veure quan cau!).

Títols de crèdit com els d’Star Wars (efecte “rolling”) amb Python

1 Fa molt temps (però no en una galàxia molt llunyana)…

… vaig a anar al cine -i era un dels primers cops que hi anava- per veure “La guerra de las galaxias”, que era com es va traduir el nom de “Star Wars: A new hope”.
La pel·lícula em va impressionar des del primer segon, començant pels imponents títols de crèdit que introduïen la història i que s’allunyaven majestuosament per l’espai.
Per a la realització de l’efecte dels títols allunyant-se es van utilitzar tècniques “artesanals”. En aquest enllaç expliquen com, però una foto val més que mil paraules:
Star-Wars-Intro-Creation-Secret-2
Des de l’arribada de la informàtica personal s’han inventat de forma recurrent sistemes per reproduir l’efecte amb ordinadors. Una cerca a Google ens mostra un munt de resultats.
L’efecte es pot aconseguir directament amb diverses aplicacions, però segueix sent un repte interessant la seva realització per programa. En el post d’avui, doncs, presento un “prova de concepte” feta amb Python per a generar aquest efecte de rolling a uns títols de crèdit.

2 Com es fa una animació?

Es sabut que una animació no és més que la successió ràpida d’imatges (frames, o fotogrames). Per tant, per a fer una animació només cal mostrar una imatge durant un breu instant, a continuació una altre amb un petit canvi, després un altre… la integració de la successió de les imatges estàtiques al nostre cervell és el que provoca la sensació de moviment. Aleshores, per a fer una animació el que he de fer és crear els diferents fotogrames que la formen. La sensació de moviment suau depèn de quantes imatges (o frames) per segon es fan servir: amb 12 frames per segon (fps) s’arriben a notar alguns salts; a 25fps la sensació de moviment és pràcticament perfecte, i és el valor que es fa servir a les càmeres de vídeo.

2.1 Un experiment

Fem un petit experiment. Agafem aquesta imatge que és de 606×700
swtfa

En comptes de visualitzar-la sencera…

  • en visualitzaré només un quadre de 320×240;
  • aniré desplaçant el quadre un píxel per cop cap avall;
  • a una velocitat de 10 píxels per segon, és dir, a 10fps.

Faig servir la funció blit de la llibreria pygame per mostrar només una part de la imatge.

blit-image.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pygame as pg
from pygame.locals import *

pg.init()                           # init pygame
w = 320                             # width
h = 240                             # height
size=(w,h)                          # size
screen = pg.display.set_mode(size)  # init screen
pg.display.set_caption('Star Wars TFA')  # caption
filename = "./swtfa.jpg"            # filename
img=pg.image.load(filename)         # image 606x700
x = 0
y = 0
FPS = 10                            # frames per second setting
framerate = pg.time.Clock()
repeat = True
   
while repeat:                       # iterate
    # put image
    screen.blit(img, (0,0), (x, y, 320, 240)) 
    pg.display.flip() 
          
    # scroll down image
    y = y + 1
    if (y + 240 > 800):
      y = 0

    #10fps
    framerate.tick(FPS)

    # capture events
    for event in pg.event.get():
      if event.type == QUIT:
          repeat = False

# exit          
pg.quit()    
print "done!"

Si executo el programa anterior sembla que la imatge dins el requadre es vagi movent cap avall. He aconseguit crear la sensació de moviment a partir d’una imatge estàtica. Amb els títols de crèdit he de fer el mateix: construiré una imatge amb el text i aniré obtenint-ne els diferents frames sense més que anar desplaçant-me un píxel cap avall per a cada frame. Aleshores, un cop tingui tots els frames base, aplicaré una transformació sobre cada frame per afegir l’efecte d’allunyament.

3 Esquema general

La idea és partir d’un text d’entrada inicial i obtenir, com a resultat final, un vídeo amb l’scrolling del text.
Especifico més: el vídeo serà de format mp4 de 320×240 px.

El procés es pot dividir en sub-processos més senzills. Em plantejo aquests quatre passos:

  • donar al text un format adequat per a ser processat.
  • crear els frames base del vídeo (imatges o frames de 320×240)
  • processar els frames per afegir l’efecte d’allunyament: el resultat de processar cada frame serà un nou frame, també de 320×240.
  • crear un vídeo amb els frames processats.

Som hi.

4 Donar al text un format adequat

Primer de tot, el text a mostrar:

EPISODI V
L'IMPERI CONTRAATACA
Les forces imperials avancen implacablement 
de victòria en victòria sobre els rebels. 
L'Imperi prepara el cop definitiu: 
ha descobert la principal base rebel 
al planeta gelat de Hoth 
i es llença a l'atac per destruir-la.
Però no tot està perdut per 
als rebels. 
Si aconsegueixen retenir prou temps 
a les tropes d'assalt, la flota rebel 
podrà escapar a la nova base secreta...

Ara he de preparar aquest text per a que em sigui fàcil generar els frames de la imatge i processar-los.

La idea és aquesta: vaig a convertir el text en una imatge de 320px d’ample (ample de imatge que coincideixi amb l’ample de frame) per el llarg suficient per encabir-hi el text, més 240px (un frame) addicionals en blanc al principi i 240px (un frame addicional) en blanc al final.

Amb aquestes restriccions (i després d’algunes proves) resulta que la mida 320×800 em serveix.

I quin format? La restricció és fer-m’ho fàcil i que tot sigui molt evident i clar. El format més adequat que he trobat és el pbm:

https://en.wikipedia.org/wiki/Netpbm_format

Es tracta d’un format monocrom molt senzill. Reviso l’exemple que apareix a la wiki:

P1
# This is an example bitmap of the letter "J"
6 10
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 0 0 0 1 0
1 0 0 0 1 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
  • ‘P1’ indica que és el format pbm, es dir monocrom amb dades en format ascii
  • ‘# This is…’ és un comentari
  • ‘6 10’ diu que és una imatge de 6×10 píxels
  • ‘0’ indica punt en blanc ‘1’ punt en negre
  • A més, els espais en blanc, i salts de línia es descarten

Tenint en compte tot l’anterior, genero amb GIMP un llenç de 320×800 de fons negre; hi afegeixo el text deixant 240px abans de l’inici i 240px després.

El resultat és aquest:

intro

5 crear el fitxer “master”

Si examino intro.pbm veig el següent:

albert@eowyn:~/workspace/python/starwars-credits$ head intro.pbm
P1
# CREATOR: GIMP PNM Filter Version 1.1
320 800
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111
albert@eowyn:~/workspace/python/starwars-credits$ wc intro.pbm
  3660   3668 259707 intro.pbm
albert@eowyn:~/workspace/python/starwars-credits$

La part de la imatge es divideix en línies de 70 caràcters. L’especificació dels formats pbm, pgm, ppm recomana que les línies de dades no superin els 70 caràcters, però només és una recomanació. Aprofito aquest grau de llibertat perquè em sembla que és més senzill transformar el bloc de 70×3657 (3660 línies menys les tres de capçalera) en una bloc de 320(+ 1 de retorn de carro)x800 per a poder moure’m directament als inicis de cada fila d’imatge i agafar blocs de 240 files per a generar els frames. O sigui, em preparo un “master” per a poder generar més senzillament els frames. Ho faig amb el següent codi:

w = 320                                   # width of a frame and base image
h_frame = 240                             # height of a frame
h_img_base = 800                          # height of base image
c = 0                                     # counter
frame_size=(w,h_frame)                    # size of frame
filename_read = "intro.pbm"
frames_folder = "./frames/"
filename_master = "master"
bit = ""

# create master
with open(filename_read, "r") as fr:    
    with open(frames_folder + filename_master, "w") as fm:
        # discards three first header lines
        fr.readline()
        fr.readline()
        fr.readline()

        for i in xrange(0, w * h_img_base):
            c = c + 1
            bit = fr.read(1)
            if bit == '\n':
                bit = fr.read(1)
            fm.write(bit)

            if c == w:
                fm.write('\n')
                c = 0

El resultat de l’anterior és un fitxer master de 800 files de 320 caràcters (més un caràcter de retorn de carro a cada línia).

6 creació dels frames

A partir del master és molt senzill generar els frames. Això ho faig amb el següent codi

# create frames
filename_frame = ""
filename_pattern = "frame_%0#5d.pbm"
frame_count = 0

with open(frames_folder + filename_master, "r") as fr:
    for frame_count in xrange(0, h_img_base - h_frame): 
        filename_frame = filename_pattern % frame_count
        print "[Frame %d]" % frame_count

        with open(frames_folder + filename_frame, "w") as fw:
            fw.write("P1\n")
            fw.write("# CREATOR: Albert Baranguer Codina\n")
            fw.write("%d %d\n" % frame_size)

            fr.seek(frame_count * (w + 1))

            for i in xrange(h_frame ):
                fw.write(fr.readline())

Remarcar que amb

fr.seek(frame_count * (w + 1))

Em situo a l’inici de cada frame, i amb

for i in xrange(h_frame ):
    fw.write(fr.readline())

llegeixo el bloc de 240 línies. En aquest moment, després d’executar el bloc anterior, tinc 560 fitxers pbm (560 = 800 – 240) amb noms de frame_00000.pbm a frame_00559.pbm a la carpeta frames. Cada fitxer té un bloc d’imatge de 240 línies de 320 caràcters, més un de retorn de carro, per fila.

7 EL vídeo sense processar

Puc fer servir els frames generats per visualitzar la versió del vídeo sense l’efecte d’allunyament. Faig servir el següent visualitzador:

player1.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import pygame as pg
from pygame.locals import *

pg.init()                           # init pygame
w = 320                             # width
h = 240                             # height
size=(w,h)                          # size
screen = pg.display.set_mode(size)  # init screen  
FPS = 18                            # frames per second setting
framerate = pg.time.Clock()
pg.display.set_caption('STAR WARS CAPTION FX')

filename_processed_pattern = "frame_%0#5d.pbm"
processed_frames_folder = "./frames/"  

filename_frame = ""
repeat = True
while repeat: # iterate
    for frame_count in range(0, 560):
        filename_frame = filename_processed_pattern % frame_count
 
        img=pg.image.load(processed_frames_folder + filename_frame)
        screen.blit(img, (0,0)) # put image 
        pg.display.update()
        pg.display.flip() 
        framerate.tick(FPS)

        for event in pg.event.get():
            if event.type == QUIT:
                repeat = False

        if not repeat:
            break

pg.quit()    
print "done!"

8 Filtre d’allunyament

Un cop tinc tots els frames, aplico a cadascun el filtre “d’allunyament”. La idea és mapejar  el frame rectangular a  un trapezi:

(0,0)--------------------------------------(319,0)
  |                                           |
  |                                           |
  |     (c, e)----------------------(d, e)    |
  |       |                           |       |
  |      |                             |      |
  |     |                               |     |
  |    |                                 |    |
  |   |                                   |   |
  |  |                                     |  |
  | |                                       | |
  ||                                         ||
  |                                           |
(239,0)----------------------------------(319,239)

és dir, vull una funció que transformi els punts del rectangle del frame en punts del trapezi definit per (c,e) (d,e) i els cantons inferiors del frame

  • (0,0) –> (c, e)
  • (319, 0) –> (d, e)
  • (239, 0) –> (239, 0)
  • (319, 239) –> (319, 239)

Després d’algunes proves, trio els valors e = 40, d = 199 i, per simetria, c = 319 – d = 120.

Horitzontalment, la transformació serà un escalat lineal depenent de l’alçada dins del trapezi.

A l’eix vertical la densitat del mapeig ha d’anar creixent a mida que pugem pel trapezi. És a dir, a mida que ens apropem al costat superior del trapezi han d’haver-hi cada cop “més línies”.

Combinant aquestes dues transformacions s’aconsegueix fer les lletres cada cop més petites a mida que “van pujant”.

Donat un punt del frame (x0, y0) caldrà, doncs, determinar a quina posició vertical es desplaça yt i, amb aquesta dada, determinar quin escalat horitzontal li correspon yt.

És dir, una mapeig del punt (x0, y0) al punt (xt, yt)

T:(x0, y0)——> (xt, yt)

Aquesta transformació la resolc amb la següent funció

def transform(x0, y0):
     a = 319.0
     b = 239.0
     d = 199.0
     e = 40.0
     c = a - d

     # lineal
     # y1 = e + (y0 * ((b - e) / b))
     
     # parabolic
     c0 = (b - e) / (b * b)
     c1 = e
     y1 = (c0 * y0 * y0) + c1


     x2 = (((y1 * c) - (b * c)) / (e - b))
     x3 = a - x2
     x1 = x2 + (((x3 - x2) / a) *  x0)

     return (x1, y1)

El mapeig en vertical es fa amb

# lineal
# y1 = e + (y0 * ((b - e) / b))

# parabolic
c0 = (b - e) / (b * b)
c1 = e
y1 = (c0 * y0 * y0) + c1

Al codi està comentada la línia que caldria per a fer un mapeig lineal. És dir, amb “densitat” de línies homogènia.

Si proveu el mapeig vertical lineal veureu que les lletres mantenen l’alçada durant tot el seu recorregut per la pantalla.

El que aplico és el mapeig “parabòlic”, en comptes de lineal.

La següent línia defineix una paràbola amb el vèrtex (0, c1), on c1 és 40.

y1 = (c0 * y0 * y0) + c1

El valor de c0 es determina amb la següent línia

c0 = (b - e) / (b * b)

Amb aquesta definició de c0, quan y0 és b (que té el valors de 239, és dir, última línia) y1 val b, com es pot comprovar fàcilment.

C0 és molt petit (està dividit pel quadrat de 239), de forma que amb valors “petits” de y0 tinc valors petits de y1.

El resultat és que n línies y0 es mapegen a la mateixa línia y1 (n > 1)

Però el creixement parabòlic fa que a mida que creix y0, en el mapeig d’n a 1 la n  cada cop es fa més petita.

De fet, a mida que y0 s’apropa al valor de 239 (la línia inferior) la n passa a ser fraccionària. Caldrà tenir-ho en compte mes tard.

He fet servir una funció “parabòlica” per a augmentar la densitat de línies prop de la línia superior, però és podria provar una altre funció que donés un resultat similar, a veure quin efecte té.

Un cop tinc la y1, aleshores puc calcular l’escalat horitzontal. En aquest cas es tracta d’una escalat lineal.

x2 = (((y1 * c) - (b * c)) / (e - b))
x3 = a - x2
x1 = x2 + (((x3 - x2) / a) *  x0)

A partir de y1 es calcula el punt x2 fent servir l’equació de la recta que passa per (0,239) i (c=120, e=40).

Per simetria horitzontal es calcula x3.

El punt x1 es calcula considerant el mapeig lineal entre (0, 319) i (x2, x3)

9 Optimització i línies en blanc

El mapeig és el mateix per a tots els frames. Aleshores, en comptes de recalcular el mapeig per a cada frame, es pot calcular un cop al començament i mantenir-lo en un array.
Un array, en principi, de 320×240. Però el cas és que el creixement en y1 de la funció de mapeig entre els punts d’un frame (x0,y0) i els punts del trapezi (x1, y1) fa que per a increments d’1 píxel en la variació de y0 el trapezi tingui línies buides a la seva part inferior, o sigui, y1 té “forats”. La solució és fer que els increments en y0 siguin més petits que un píxel, per a que y1 no tingui forats. Fent algunes proves, he vist que amb increments de y0 de 0.5 ja n’hi ha prou per a que la funció de transformació no deixi línies buides.

Al final, doncs, el precàlcul de la transformació es pot fer amb el següent codi:

# create frame transform master
num_steps = 2.0
frame_transform = [["1" for j in xrange(0,int(num_steps))] for i in range(0, w * h_frame)]
for y in xrange(0, h_frame):
    for x in xrange(0, w):
        for inc_y in xrange(0, int(num_steps)):
            frame_transform[x + y * w][inc_y] = transform(x, y + inc_y * (1 / num_steps) )

10 Generació dels frames processats (i afegir el color)

La generació dels frames processats és directa: per a cada frame…

for frame_count in xrange(0, h_img_base - h_frame): 
      filename_frame = filename_pattern % frame_count
      filename_processed_frame = filename_processed_pattern % frame_count

      # read and transform frame 
      with open(frames_folder + filename_frame, "r") as fr:
          # discards three first header lines 
          fr.readline()
          fr.readline()
          fr.readline()

… aplico la transformació,tenint en compte que els increments de y0 seran fraccionaris. Per simplificar, en comptes de generar directament el frame transformat faig servir un array de 320×240 com a pas intermig…

# initialize black frame
frame_bits = ["1" for i in xrange(0, w * h_frame)]

for y in xrange(0, h_frame):
    for x in xrange(0, w):
        bit = fr.read(1)
        if bit == '\n':
            bit = fr.read(1)

        # parabolic. trick for filling gaps
        for inc_y in xrange(0, int(num_steps)):
            (xt, yt) = frame_transform[x + y * w][inc_y]
            if int(xt) < w and int(yt)< h_frame:
                frame_bits[int(xt) + int(yt) * w] = bit

Finalment, escric el frame transformat. Aprofito aquest últim pas per afegir el color ja que durant tot el procés he considerat la imatge només en blanc i negre.

Simplement, genero el frame transformat amb el format PPM

10.1 Format PPM

De la viquipèdia, un exemple de PPM.

P3
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255   0   0     0 255   0     0   0 255
255 255   0   255 255 255     0   0   0

Per tant,

# write transformed frame
# c = 0
rgb = ""
black = " 0 0 0"
yellow = " 255 255 0"  
print "[Processed Frame %0#5d]" % frame_count
with open(processed_frames_folder + filename_processed_frame, "w") as fw:
    fw.write("P3\n")
    fw.write("# CREATOR: Albert Baranguer Codina\n")
    fw.write("%d %d 255\n" % frame_size)
    for bit in frame_bits:
        if bit == "1":
            rgb = black
        else:
            rgb = yellow 
        fw.write(rgb)
        c = c + 1
        if (c == w):
            c = 0
            fw.write('\n')

El resultat de l’execució d’aquest codi és que tindré 560 frames processats a carpeta processed-frames

11 generació del video mp4

Arribats a aquest punt ja podem visualitzar el vídeo fent servir una petita modificació del player1.py que he mostrat abans. Però com que el resultat demanat era un mp4, amb un parell de passos addicionals fent servir convert de imagemagick i ffmpeg obtinc el resultat final.

La idea original era fer servir ffmpeg amb els pbm generats en el pas anterior per a obtenir el vídeo, pero en proves he vist que al ffmpeg no sembla agradar-li aquest format de imatge. O sigui que he transformat els pbm a png amb el següent script: pbm-to-png.sh

#!/bin/bash

for filename in $(ls -b ./processed-frames)
do
    convert ./processed-frames/"$filename" ./png/"$filename".png
done
echo "done!"

I un cop he obtingut els frame en format png a la carpeta png, finalment, he generat l’mp4 amb create-mp4.sh

#!/bin/bash
ffmpeg -i png/frame_%05d.processed.pbm.png \
       -c:v libx264 \
       -pix_fmt yuv420p png/starwars-credits-fx.v1.mp4

I vet aquí el resultat

 

12 Repositori a GitHub

Podeu trobar el codi ue he fet servir al meu repositori de GitHub

https://github.com/abaranguer/sw-rolling-fx

60 anys de Lisp. Old rockers never die.

El programador no neix. Es fa.

La formació d’un bon programador passa per diverses etapes. En la etapa inicial hom aprèn un llenguatge. Normalment un llenguatge d’iniciació. Un llenguatge d’iniciació serveix, més que res, per comprendre conceptes de programació.  I no és tan important el seu rendiment o la seva aplicació en problemes reals.

Avui, per exemple, es fa servir, a nivell de ESO i secundària, el llenguatge Scratch (un fantàstic i versàtil entorn d’aprenentatge) com a llenguatge d’iniciació.

A nivells més avançats, hi ha més varietat. Sobretot als EUA es fa servir molt -com a llenguatge d’iniciació per a universitaris, repeteixo- el Lisp, en alguna de les seves encarnacions: Scheme, Racket, CLisp

Lisp és proper al llenguatge matemàtic, té una sintaxi mínima i no imposa gaires restriccions en quant a paradigmes de programació, tot plegat el fa molt versàtil per a presentar conceptes informàtics. Alguns dels millors i més influents manuals de programació fan servir el Lisp. Cal llegir al menys una vegada en la vida el llibre porpra: Structure and Interpretation of Computer Programs.

Potser sorprenentment, el Lisp es un llenguatge que es troba amb  facilitat a entorns productius Unix. Guile (Scheme), un altre dialecte de Lisp, és el llenguatge d’extensió oficial de les aplicacions GNU (un llenguatge d’extensió és, per entendre’ns, un llenguatge de macros). També es pot trobar Lisp sent part indestriable i indissoluble de l’Emacs, l’editor de texts més versàtil mai creat. Emacs, en ell mateix, està en molt bona part programat amb Emacs Lisp. La forma d’estendre Emacs és, evidentment, amb l’Emacs Lisp. La presència universal d’Emacs posa el Lisp allà on hi hagi un Emacs instal·lat.

Lisp (inventat per John McCarthy entre 1956 i 1958) és el segon llenguatge informàtic més antic encara en servei (el més antic, encara en servei, és Fortran. La primera especificació de Fortran va ser escrita per IBM a  1954). Aquesta timeline de la wiki us pot ajudar a situar-lo en el temps.

Estem parlant, doncs,  d’un llenguatge informàtic amb 60 anys d’història. Es diu de pressa. En termes informàtics tant de temps equival al pas  de vàries eres geològiques.

Però el millor del cas és que l’evolució del Lisp continua: és relativament senzill programar un interpret de Lisp i això fa que es puguin trobar dialectes per a multitud de plataformes. Concretament, per a la JVM en aquests moment hi ha una versió de Lisp que destaca sobre les altres: Clojure.

Clojure és un dialecte de Lisp que funciona sobre la JVM. Tot i que no imposa el paradigma, presenta una orientació envers la Programació Funcional (FP) [i Clojure FP ]. Val a dir que és possible fer FP, en general, amb dialectes comuns de Lisp.

Com a punt molt fort, es relaciona de forma senzilla amb la JVM, de forma que té accés a la infinitat de llibreries i frameworks de Java i, a l’hora, és senzill des de Java  invocar Clojure, o fer servir des de Java les classes desenvolupades amb Clojure.

Més enllà de la curiositat de portar Lisp a la JVM, sembla que Clojure està fent-se, poc a poc, això sí, amb una part de mercat en l’anàlisi de dades (on a hores d’ara dominen R i Python amb Pandas, sense comptar amb el clàssic SQL, o l’omnipresent Java).

Però, tornant al principi, en la formació d’un programador el primer pas acostuma a ser algun llenguatge d’iniciació que ràpidament es complementa amb l’aprenentatge de llenguatges més utilitzats professionalment i amb llenguatges de paradigmes diferents.

La programació amb diferents paradigmes dona una visió completa al programador. Li obre la ment. L’habilita per enfocar els problemes des de punts de vista diferents. Per això, un bon programador ho és de forma independent als llenguatges que conegui , tot i que, evidentment, el més probable i el més recomanable és que tingui alguns llenguatges preferents  que domini. I també que aquestes preferències vagin canviant amb el pas del temps. El bon programador és poliglot, i sempre té un ull posat en els nous llenguatges i paradigmes que van apareixent.

Dins la caixa d’eines del programador hom pot trobar, doncs,  diferents llenguatges per a diferents propòsits. Alguns llenguatges seran molt demandats professionalment, i altres, no tant, o gens ni mica. Però en l’arsenal mental del programador, aquesta varietat expressiva és riquesa i versatilitat.

Per acabar, l’objectiu del post d’avui era redescobrir Lisp i perquè crec que pot tenir interès dedicar un temps a aquest llenguatge. Com usuari que sóc d’Emacs (Emacs Lisp) i d’eines GNU (Guile i Scheme), Lisp té un caràcter pràctic. Com programador Java i que ha treballat més o menys amb anàlisi de dades, Clojure també em crida l’atenció.

La paraula clau és poliglotisme. Us deixo un enllaç: http://hyperpolyglot.org/. Es tracta d’un lloc web que ofereix taules de comparació entre llenguatges més o menys afins. En concret, us proposo fer un cop d’ull a aquestes taules:

Llenguatges d’Scripting : Node.js, PHP, Python i Ruby. [full 1]i [full 2].

Llenguatges d’anàlisi numèric i estadístic: MATLAB (i Octave), R, NumPy i Julia. [full 1] i [full 2].

Comparació entre dialectes de Lisp: Common Lisp, Racket (Scheme), Clojure, Emacs Lisp .

Cinc problemes de programació

Una de les conseqüències de l’ERO a Indra (on encara treballo) és que a …curt? …mig? termini m’incorporaré al mercat laboral, o el que és el mateix, que hauré de buscar feina. I és bastant probable (i em sembla el més sensat) que la feina que busqui estigui relacionada amb el que sé fer, que és, bàsicament, de programador.

Programador? Alguns diran Analista, o en anglès, Software Engineer, o Software Architect, o títols encara més originals… En essència, però, jo crec que el que és distintiu de la meva feina és que sóc capaç de programar ordinadors i fer-los funcionar junts. Per tant, fem-ho fàcil i digues-me programador. Ras i curt.

El cas és que buscant sobre el que em puc esperar a les entrevistes de feina vaig trobar el següent article: “Five programming problems every Software Engineer should be able to solve in less than 1 hour“. Sí,ho heu entès: cinc problemes de programació que tot enginyer de software hauria de ser capaç de resoldre en menys d’una hora. Em va semblar força interessant.

L’autor d’aquest article diu que quan publica una oferta demanant programadors es troba amb candidats que no saben què vol dir “programar”. Aleshores proposa el que, al seu entendre, són cinc problemes bàsics que tot programador “de veritat” hauria de ser capaç de resoldre en menys d’una hora.

Cinc problemes en una hora. Cal fer algunes consideracions. Què ha de fer un programador per superar un repte d’aquest estil? primer de tot, cal comprendre (analitzar) el problema i les seves implicacions, i dissenyar una solució. Encara que sigui en forma de notes mentals. Hi ha alguna forma de validar el disseny de la solució trobada? Un cop analitzat i dissenyat el problema, cal pensar en la implementació de la solució. Probablement serà més eficient un llenguatge específic del domini del problema que un llenguatge de propòsit general. Si es pot triar, en general és més ràpid desenvolupar una resposta amb un intèrpret que amb un compilador (ni que només sigui perquè s’estalvia el temps de compilat); per descomptat, és més eficient disposar d’un bon entorn de desenvolupament, que proporcioni coses com compleció del codi, acoloriment de sintaxi, snippets de codi, generació automàtica de codi, depurador… que fer servir un editor de texts pelat, per molt que per Internet es trobin acudits tan graciosos com aquell que diu que el millor IDE és vi + gcc.

Per descomptat, més enllà de si interpretat o compilat, és clau per a desenvolupar de forma eficient, el conèixer a fons el llenguatge triat per al desenvolupament. Finalment, l’experiència és un grau. És més probable que algú que ha fet moltes hores de programació s’hagi trobat amb problemes similars en algun moment de la seva trajectòria i que els hagi solucionat. En resum: per a millorar l’eficiència cal experiència i coneixement en el llenguatge i les eines a utilitzar.

A més de tot l’anterior, un programador de veritat sap que l’objecte del seu treball, el codi, ha de tenir unes determinades característiques, com per exemple la legibilitat i l’organització. per no parlar de la gestió de recursos, erros i la generació i gestió de casos de proves.

Per si fos poc, el codi, com producte, s’ha d’administrar i segueix uns fluxos dins de les organitzacions. Al menys com usuari, un programador hauria d’estar al cas dels sistemes de Control de Versions, o dels sistemes d’Integració Continua.

Tot això son coneixements tècnics que ha de tenir el programador. Però no només. El programador hauria de tenir unes competències generals que inclourien la capacitat d’auto-organització (tècniques com GTD), l’autonomia, l’auto-didactisme, la bona capacitat de comunicació, oral i escrita (afegiria també audiovisual), la capacitat de treball en equip, i també capacitat didàctica i de lideratge. I segur que em deixo coses.

Bé. De totes aquestes característiques no no en parla l’autor de l’article. Jo trobo que a l’hora de contractar un programador caldria tenir-les en compte. Però el fet és aquest: el que de debò és imprescindible per a un programador és que sàpiga programar.

Tornant al prinicipi: Quins són aquests cinc problemes que tot programador hauria de poder resoldre en menys d’una hora?

Problem 1
Write three functions that compute the sum of the numbers in a given list using

  • a for-loop
  • a while-loop
  • recursion

Problem 2
Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

Problem 3
Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

Problem 4
Write a function that given a list of non negative integers, arranges them such that they form the largest
possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

Problem 5
Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

Déu n’hi do! Els problemes 1,2 i 3 són senzills. Ara bé, el 4 i el 5 poden fer-te rumiar una bona estona.

En una actualització de post, el mateix autor de l’article reconeixia que els problemes 4 i 5 havien generat una important controvèrsia.

Bé, jo també trobo que en una hora els cinc problemes és, més aviat, justet.

En el meu cas, em vaig decidir a fer els problemes. Ara bé, no pretenia resoldre’ls en una hora. De fet, el que pretenia és que em servissin per practicar un llenguatge que em fa molta gràcia i que he “descobert”, per dir-ho d’alguna manera, fa poc: amb l’Elisp de l’Emacs.

Sí, he fet servir lisp per resoldre els problemes, què passa? xD (de fet, el problema 5 l’he fet primer amb Python, però ja en parlaré després)

Allà van les meves solucions:

Solució al problema 1 (amb for-loop –> dotimes)

;; The 5 problems
;;
;; Problem 1
;; Write three functions that compute the sum of the numbers in a given list using 
;;  - a for-loop
;;  - a while-loop
;;  - recursion
;;
;; 1.1 - for-loop (dotimes)
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)

  (dotimes (i N) 
    (setq suma (+ suma (elt nums i)))
  )

  (insert (format "\nFor loop (with dotimes) sum: %d" suma))
)
For loop (with dotimes) sum: 55

Solució al problema 1 (amb while-loop)

;; 1.2 - while
(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq N (length nums))
  (setq suma 0)
  (setq i 0)
  (while (< i N) 
    (setq suma (+ suma (elt nums i)))
    (setq i (1+ i))
  )

  (insert (format "\nWhile loop sum: %d" suma))
)
While loop sum: 55

Solució al problema 1 (recursiva)

;; 1.3 - recursion
(defun recursiveSum(numsList)
  (setq N (length numsList))
  
  (if (> N 0)
    (+ (car numsList) (recursiveSum (cdr numsList)))  ;; if part
    0                                                 ;; else part
  )
)

(progn 
  (setq nums (list 1 2 3 4 5 6 7 8 9 10))
  (setq suma 0)

  (setq suma (+ (car nums) (recursiveSum (cdr nums)))) 
  
  (insert (format "\nRecursive sum: %d" suma))
)
Recursive sum: 55

Fàcils, no? Anem pel problema 2:

;; Problem 2
;; Write a function that combines two lists by alternatingly taking elements. 
;; For example: given the two lists [a, b, c] and [1, 2, 3], 
;; the function should return [a, 1, b, 2, c, 3].
;;
(defun merger (listData indexListData listUnion) 
  (push (nth indexListData listData) listUnion)
  listUnion   ;; not strictly necessary
)

(progn 
  ;; test data
  (setq list1 (list "a" "b" "c"))
  (setq list2 (list 1 2 3 4 5 6))
  (setq listUnion (list))

  ;; get length of lists
  (setq lengthList1 (length list1))
  (setq lengthList2 (length list2))
  
  ;; length of union list
  (setq lengthUnion (+ lengthList1 lengthList2))

  (setq indexList1 0)
  (setq indexList2 0)

  (dotimes (i lengthUnion)
    ;; list 1
    (if (< indexList1 lengthList1)
      (setq listUnion (merger list1 indexList1 listUnion)) 
    )
    (setq indexList1 (1+ indexList1))
    
    ;; list 2
    (if (< indexList2 lengthList2)
      (setq listUnion (merger list2 indexList2 listUnion)) 
    )
    (setq indexList2 (1+ indexList2))
  )
 
  ;; reverse
  (setq listReversed (reverse listUnion))

  ;; show results
  (print "List merger")
  (print listReversed)
)

Una mica embolicat, no? No és el millor codi que he escrit, la veritat. El codi s’hauria simplificat si en comptes de fer servir list hagués fet servir vectors.

La funció merger no fa mes que posar al principi de la llista unificada l’element enèsim de la llista passada com argument. Com que els elements de les dues llistes es van posar alternativament al començament (push) de la llista unificada, per això cal fer un reverse de la llista unificada al final.

Bé, amb Python o amb Basic m’hauria sortit millor. Seguim.

Solució del problema 3

;; Problem 3
;; Write a function that computes the list of the first 50 Fibonacci numbers. 
;; By definition, the first two numbers in the Fibonacci sequence are 0 and 1, 
;; and each subsequent number is the sum of the previous two. 
;; As an example, here are the first 10 Fibonnaci numbers: 
;; 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.
;; 
(progn 
  (setq n0 0.0)
  (setq n1 1.0)
  (insert "\n - 50 first Fibonacci numbers -\n")
  (insert "0\n1\n")
  (dotimes (i 50)
    (setq n (+ n1 n0))
    (insert (format "%d\n" n))
    (setq n0 n1)
    (setq n1 n)
  )
)
 - 50 first Fibonacci numbers -
0
1
1
2
3
5
8
13
21
34
...
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074

Un clàssic. La successió de Fibonacci. Aquest problema també és molt senzill.

Solució (errònia) al problema 4

;; Problem 4
;; Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. 
;; For example, given [50, 2, 1, 9], the largest formed number is 95021.
;; 
(defun greater (lower upper)
  (and (not (string< lower upper)) (not (string= lower upper)))
)

(defun swap (row i)
   (setq aux (aref row i))
   (aset row i (aref row (1+ i)))
   (aset row (1+ i) aux)
)

(defun bubble-sort (strNums)
  (setq N (length strNums))
 
   ;; sort array of strings 
  (dotimes (j (- N 1))
    (dotimes (i (- N 1)) 
      (setq lower (aref strNums i))
      (setq upper (aref strNums (1+ i)))
   
      (if (greater lower upper)
        (swap strNums i)
      )
      ;;(show-row strNums)
    )
  )
)

(defun show-row (strNums)
  (setq N (length strNums))
  (dotimes (i N)
    (insert (format "%s " (aref strNums i )))
  )
  (insert "\n") 
)

(defun reverseVector (row)
  (setq N (length row))
  (dotimes (j (/ N 2))
    (setq val1 (elt row j))
    (setq val2 (elt row (- (- N 1) j)))
      
    (aset row (- (- N 1) j) val1)
    (aset row j val2)
  ) 
)

(defun concatVector (row)
  (setq N (length row))
  (setq retvalue "")
  (dotimes (i N)
    (setq retvalue (concat retvalue (elt row i)))
  )
  retvalue  ;; not strictly necessary 
)

(progn
  ;; data: list of non negative integers
  (setq nums (list 9 8 7 6 5 4 3 2 1 0))
 
  ;; convert to array of strings
  (setq N (length nums))
  (setq strNums (make-vector N nil))
  (dotimes (i N) 
    (aset strNums i (number-to-string (elt nums i)))
  )

  (insert "\nGreatest integer\n")
  (insert "\nunsorted array:\n")  
  (show-row strNums)

  (insert "\nsorted array:\n") 
  (bubble-sort strNums)
  (show-row strNums)

  (insert "\nreversed sorted array:\n") 
  (reverseVector strNums)
  (show-row strNums)
 
  ;; string to number
  (setq greatestNumber (string-to-number (concatVector strNums)))
  (insert (format "Greatest integer: %d\n" greatestNumber)) 
)
Greatest integer

unsorted array:
9 8 7 6 5 4 3 2 1 0 

sorted array:
0 1 2 3 4 5 6 7 8 9 

reversed sorted array:
9 8 7 6 5 4 3 2 1 0 
Greatest integer: 9876543210

Doncs bé, resulta que la solució no és correcta! He suposat que n’hi havia prou amb ordenar (funció bubble-sort, com no!) alfabèticament els números, però resulta que aquesta suposició és falsa, com indiquen en aquest altre post:

“A lot of folks have rightly pointed out that this problem can be solved using a lexical comparison of strings. However, that’s not all you need.

Consider the following example: [5, 50, 56]. A lexical comparison returns 56, 50, and 5, but that doesn’t make the larger number (56, 5, 50 does)”

O sigui que: meeec! cal rumiar un altre cop la solució del problema 4. Queda pendent la solució per a un futur post.

UPDATE: Solució Brute Force:

Ahir no estava d’humor per a posar-me a investigar un algorisme pera solucionar el problema 4… i avui tampoc! L’opció és fer força bruta, que,de fet, als ordinadors se’ls dona molt bé.

Amb força bruta i generadors de Python (itertools) la cosa queda tan simple com això:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# biggetst integer

import itertools as itt

print "\nBiggest number\n"

nums = ['500', '5', '51', '52', '504', '506', '54', '56', '514', '515', '516', '575']

max_str = ''
num_iters = 0

for perm in itt.permutations(nums, len(nums)):
    num_iters = num_iters + 1
    num = ''.join(perm)
    if  num > max_str:
        max_str = num

print "max: %s; iters: %d\n" % (max_str, num_iters)        

'''
>>> import biggest

Biggest number

max: 575565545251651551514506504500; iters: 479001600
''' 

Aquesta solució és qualsevol cosa menys elegant, però és molt ràpida de programar i soluciona el problema en un temps finit. Cal dir que he tirat, de nou, de la màgia de Pyhton que m’ha permès resoldre amb el simple import de les itertools la generació de les permutacions dels números. Després la concatenació amb el join i actualitzar el màxim a mida que es va trobant.

Queda pendent, per a quan tingui temps i ganes d’investigar-ho, el trobar un algorisme més intel·ligent que la solució per força bruta. Això sí, en tot cas, la força bruta sempre és una opció a considerar (i els bons programadors ho saben).

Finalment, la solució al problema 5

Primer la solució amb Python. I ara veureu perquè Python és el Llenguatge dels Déus:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Problem 5
Write a program that outputs all possibilities to put + or - or nothing 
between the numbers 1, 2, ..., 9 (in this order) 
such that the result is always 100. 
For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
'''
def get_base3_indexes(num):
    ix = [0,0,0,0,0,0,0,0]
    done = False
    i = 0
    while not done:
        quot, mod = num / 3, num % 3

        if quot >= 3:
            num = quot
            ix[i] = mod
        else:
            done = True
            ix[i] = mod
            ix[i + 1] = quot

        i = i + 1

    ix.reverse()
    return ix

if __name__ == "__main__":
    symbols = ["+","-"," "]
    formula = "1%c2%c3%c4%c5%c6%c7%c8%c9"
    ix = [0,0,0,0,0,0,0,0]
     
    # és a dir: Variacions amb Repetició de 3 elements agafats de 8 en 8
    # RV n m = n ** m
 
    top =  3**8
    
    for i in range(0, top - 1):
        ix = get_base3_indexes(i)
        
        calc = formula % (symbols[ix[0]],
                          symbols[ix[1]],
                          symbols[ix[2]],
                          symbols[ix[3]],
                          symbols[ix[4]],
                          symbols[ix[5]],
                          symbols[ix[6]],
                          symbols[ix[7]])

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)
        if result == 100:
            print "%s = %d" % (calc2_compact, result)
            
    print "%d lines analyzed" % top
    print "done!"

O sigui, calcula les “variacions amb repetició de tres elements agafats de 8 en 8″ Els tres elements són les tres “operacions” possibles entre dígits: sumar (“1” + “2” = 3), restar (“1” – “2” = -1) i concatenar (“1” concat “2” = “12”) i els agafo de 8 en 8 perquè són 8 posicions per a operadors entre els 9 operands numèrics. la iteració per tots els casos possibles i la conversió a base 3 de l’index actual permet posar els operadors adequats on els toca en cada iteració.

Però la màgia de Python ve en aquestes tres línies:

        calc2 = [c for c in calc if c != " "]
        calc2_compact = "".join(calc2)
        result = eval(calc2_compact)

La primera línia fa una llista d’elements (calc2) a partir de la llista original (calc) on els operadors “concat” apareixen com blancs entre els números. Agafa cada element c de calc excepte els elements iguals a ” “. És dir, “compacta” la llista calc eliminant-li els blancs. Es tracta d’un bonic exemple de Python Comprehensions.

La següent línea genera un string a partir de la llista compactada.

la tercera línia avalua la suma.

La dada és que fa tot això en tres línies. Eficiència i productivitat en un llenguatge és exactament això.

I ara l’equivalent amb elisp:

;; Problem 5
;; Write a program that outputs all possibilities to put + or - or nothing 
;; between the numbers 1, 2, ..., 9 (in this order) 
;; such that the result is always 100. 
;; For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100.
;; 
;; variations with repetition of 3 elements (the +,- and "concat" operators) 
;; taken 8 (8 operands within the 1,2,3,4,5,6,7,8 and 9 operands) at a time
;;
;; VR n r = n ** r
;;  
(defun main ()
  ;; return vector with coeficients of the conversion of num to base 3.
  (defun get_base3 (num)
    (let
      ( 
        (base3 (make-vector 8 0))
        (n 8)
        (done nil)
        (i 0)
        (quot 0)
        (mod 0)
      )
      
      (while (not done)
        (setq quot (/ num 3))
        (setq mod (% num 3))

        (if (>= quot 3)
          (progn
            (setq num quot)
            (aset base3 i mod)
        
          )
          (progn
            (setq done t)
            (aset base3 i mod)
            (aset base3 (1+ i) quot)
          ) 
        )
        (setq i (1+ i))
      )

      ;; return
      base3
    )
  )

  ;; clean white spaces
  (defun clean_white_spc (str)
    (let
      ( 
        (c "")
        (j 0)
        (str_out "")
        (len (length str))
      )
      (dotimes (j len)
        (setq c (substring str j (+ j 1)))
        (if (not (string= c " "))
          (setq str_out (concat str_out c))
        )
      )

      ;; return
      str_out
    )
  )

  ;; formula parser
  (defun perform_calculation (formula)
    (let 
      (
        (n (length formula))
        (stackoperands (make-vector 9 0))
        (stackoperators (make-vector 8 "+"))
        (i 0)
        (j 0)
        (k 0)
        (accum 0)
      )
 
      ;; lexical parser
      (dotimes (i n)
        (setq c (substring formula i (1+ i)))
        (if (and (not (string= c "+")) (not (string= c "-")))
          (progn ;; true. c is a number
            (setq accum (+ (* accum 10) (string-to-number c)))
          ) 
          (progn ;; false. c is an operator  
            (aset stackoperands j accum)
            (aset stackoperators k c)
            (setq k (1+ k))
            (setq j (1+ j))
            (setq accum 0)
          )
        )
        (if (> accum  0)
          (aset stackoperands j accum)
        )
      )

      ;; performs the sum
      (setq i 0)
      (setq j 0)
      (setq operator "")
      (setq operand 0)
      (setq accum 0)

      (dotimes (i (length stackoperands))
        (setq operand (aref stackoperands i))
        (if (= i 0)
          (progn ;; i = 0
            (setq accum operand) 
          )
          (progn ;; i > 0
            (setq j (1- i))
            (setq operator (aref stackoperators j))
            (if (string= operator "+")
              (setq accum (+ accum operand))
              (setq accum (- accum operand))
            )
          )
        )
      )

      ;; return
      accum
    )
  )

  ;; main
  (let
    (
      (symbols ["+" "-" " "])
      (formula "1%s2%s3%s4%s5%s6%s7%s8%s9")
      (ix (make-vector 8 0)) 
      (top (- (expt 3 8) 1))
      (i 0)
      (count 0)
    )
  
    (insert "\nSum 100\n")
 
    (dotimes(i top) 
      (setq ix (get_base3 i))
      (setq calc (format formula (aref symbols (aref ix 0))
                                 (aref symbols (aref ix 1))
                                 (aref symbols (aref ix 2))
                                 (aref symbols (aref ix 3))
                                 (aref symbols (aref ix 4))
                                 (aref symbols (aref ix 5))
                                 (aref symbols (aref ix 6))
                                 (aref symbols (aref ix 7))  
                 )
      )
     
      (setq calc2 (clean_white_spc calc))
      (setq sum (perform_calculation calc2))

      (if (= sum 100)
        (progn 
          (setq count (1+ count))
          (insert (format "%d: %s = %d\n" count calc2 sum))
        )
      )
    )
    (insert (format "\n%d lines analyzed\ndone!"  top))
  )
)

És equivalent a la solució amb Pyhton, només que ha calgut fer funcions per a fer la compactació i eliminació dels espais en blanc, i també per avaluar la fórmula amb un senzill parser.

……

Una hora diu. En fi.

Una aplicació de qüestionaris amb Python, GTK (Glade) i SQLite (Star Wars Quizz!)

Motivació

Sempre pot ser útil una aplicació per a fer qüestionaris, o tests. Avui presento el que podria ser l’esquema inicial, la maqueta, d’una aplicació de qüestionaris.

En realitat, la cosa és més divertida: No cal que us recordi que avui, divendres 18 de desembre de 2015, és l’estrena mundial de “Star Wars: The Force Awakens”. Aquesta és una data esperada per molts fans i, en particular, pel meu fill. Fa uns dies el meu fill va preparar un qüestionari, amb Scratch 1.4, sobre l’univers Star Wars. El qüestionari amb Scratch li va quedar força bé i, inesperadament per ell, jo vaig obtenir la màxima puntuació en fer-lo. Va ser el moment per tenir una conversa, de pare a fill, sobre com es poden fer aquests programes de preguntes i respostes. El resultat és que jo li vaig preparar a ell un qüestionari sobre Star Wars, en mode text, amb Pyhton.

A partir d’aquí vaig pensar en sofisticar-ho una mica, desant les preguntes a una base de dades i fent servir una GUI, en comptes del mode text. El resultat és aquesta maqueta d’aplicació de qüestionaris, que originalment era un qüestionari sobre Star Wars i que, per això, és diu Star Wars Quizz! Quines coses, oi? fet aquest aclariment, només ens resta començar i… que la Força ens acompanyi!

 

Programari utilitzat

He triat per a desenvolupar l’aplicació el llenguatge Python, amb Emacs fent de IDE. He fet servir el constructor d’interfícies gràfiques Glade per a fer el disseny de les finestres de l’aplicació. La combinació de Python i Glade (GTK) és, a la pràctica, un entorn ràpid de desenvolupament.

La base de dades de l’aplicació és SQLite3.

El sistema operatiu és Lubuntu 15.10

 

Descripció funcional

Finestra principal i menú de l’aplicació

L’aplicació és molt senzilla: Es presenta com una finestra amb una barra de menús que conté  dos menús desplegables: “Arxiu” i “Ajuda”.

A “Arxiu” hi ha l’entrada “Nou”, que posa en marxa el qüestionari; i l’entrada “Surt”, que tanca l’aplicació.

A “Ajuda” hi ha l’entrada “Quant a” que presenta una finestra amb el logo de l’aplicació, crèdits i llicència.

 

Diàleg de nom i curs

Quan es fa click a “Nou” s’obre una finestra de diàleg en la que se’ns demana el nom de l’usuari i quin curs fa. Hi han dos botons, “Acceptar” i “Tancar”.

Amb “Acceptar” es prenen les dades introduïdes als camps de text, es tanca la finestra que demana el nom i el curs i es mostra el diàleg amb la primera pregunta.

Amb “Tancar” es tanca el diàleg de nom i curs i es descarta la informació que s’hagués introduït.

 

Diàleg de preguntes

La finestra de diàleg que mostra les preguntes s’encapçala amb el nom de l’usuari i el curs que fa. S’indica quin és el número de pregunta que s’està fent.  En cursiva es mostra la pregunta i, a continuació, quatre possibles respostes. L’usuari marca la resposta, o respostes, correctes activant els checkboxes corresponents.

Fent click en “Següent”, es carrega la següent pregunta si n’hi ha. Si s’ha completat el qüestionari es tanca el diàleg de preguntes i s’obre el diàleg que mostra els resultats del qüestionari.

Fent click a “Tancar” es tanca el diàleg de preguntes i respostes, i es descarta nom, curs i el resultat que s’hagués obtingut fins el moment.

 

Diàleg de resultats

Finalment, la pantalla que mostra els resultats indica el nom i curs de l’usuari i mostra quantes preguntes s’han encertat del total.

La pantalla de resultats té un botó de “Tancar” amb el que  es tanca el diàleg de resultat, es descarta nom, curs i el resultat que s’hagués obtingut fins el moment.

Taules

El primer pas ha estat desenvolupar les taules que suporten la funcionalitat  descrita. Són les taules següents:

CREATE TABLE "topics_questions" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_topic" INTEGER NOT NULL
);

CREATE TABLE "topics" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL
);

CREATE TABLE "questions_answers" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_question" INTEGER NOT NULL,
    "id_answer" INTEGER NOT NULL
);

CREATE TABLE "questions" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "question" TEXT
);

CREATE TABLE "question_right_answer" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "id_question" INTEGER NOT NULL,
    "id_right_answer" INTEGER NOT NULL
);

CREATE TABLE "answers" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "answer" TEXT
);

No faig servir totes les taules. Algunes estan pensant en futures ampliacions de funcionalitat. Les taules importants són QUESTIONS, que manté les preguntes; ANSWERS, les respostes; QUESTIONS_ANSWERS, taula de relació m-n entre preguntes i respostes; QUESTION_RIGHT_ANSWER, taula m-n entre preguntes i respostes correctes.

Ara mateix només hi ha preguntes sobre Star Wars i llavors es pot simplificar encara més: no he fet servir TOPICS, taula que manté els temes dels qüestionaris; ni TOPICS_QUESTIONS, m-n que relaciona temes i preguntes. Però les taules hi són.

db_loader

Val a dir que la versió original del programa feia servir un questionari mantingut en un parell de llistes de Python. Aleshores, el que he fet és partir d’aquestes llistes per a fer la càrrega inicial de les taules. L’script de càrrega de les taules de l’SQLite ha estat el següent:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sqlite3

questions = (
    u"Com es diu el wookie que acompanya a Han Solo?",
    u"De quina especie són els ossets peluts de la lluna santuari d'Endor?",
    u"A quina batalla va ser destruida la primera Estrella de la Mort?",
    u"Quantes temporades té la serie de The Clone Wars?",
    u"Com es diu la padawan d'Anakin Skywalker?",
    u"Quin és el nom Sith del Comte Dooku?",
    u"De quin planeta és Luke Skywalker?",
    u"A quin planeta és el duel entre Anakin Skywalker i Obi-Wan Kenobi?",
    u"De quin color és l'espasa laser de Mace Windu?",
    u"De quin color és l'espasa laser dels lords Sith?"
)

answers = (
    (2, "Peret", "Chewbacca", "Sr. Spock", "Leia Organa"),
    (1, "Ewoks", "Wookies", "Mandalorians", "Corellians"),
    (4, "Waterloo", "Normandia", "Toth", "Yavin-4"),
    (3, "1000", "5", "6", "7"),
    (3, "Artiom", "Assaj Ventress", "Ahsoka Tano", "Kanan Jarrus"),
    (4, "Darth Sidious", "Darth Turo", "Darth Tenebre", "Darth Tyranus"),
    (2, "Naboo", "Tatooine", "Mandalore", "Alderaan"),
    (1, "Mustafar", "Kamino", "Vulcano", "Warsoom"),
    (4, "Blau", "Verd", "Vermell", "Violeta"),
    (2, "Blanc", "Vermell", "Blau", "Violeta")
)

CONNECTION_STRING = "/home/albert/workspace/python/quizz/db/quizz.db"
INSERT_QUESTION = "insert into questions(question) values (?)"
INSERT_ANSWER = "insert into answers(answer) values (?)"
INSERT_QUESTION_ANSWER = "insert into questions_answers(id_question, id_answer) values (?, ?)"
INSERT_RIGHT_ANSWER = "insert into question_right_answer(id_question, id_right_answer) values (?,?)"

if __name__ == '__main__':
    print "begin"
    conn = sqlite3.connect(CONNECTION_STRING)

    cur = conn.cursor()
    num_question = 0
    
    for question in questions:
        cur.execute(INSERT_QUESTION, (question,))
        id_question = cur.lastrowid

        right_answer = answers[num_question][0]

        for num_answer in range(1,5):
            cur.execute(INSERT_ANSWER, (answers[num_question][num_answer],))
            id_answer = cur.lastrowid

            cur.execute(INSERT_QUESTION_ANSWER, (id_question, id_answer))
            if num_answer == right_answer:
                cur.execute(INSERT_RIGHT_ANSWER, (id_question, id_answer))

        num_question = num_question + 1
        
    conn.commit()
    conn.close()

    print "done!"

El que és interessant de l’script anterior és la llista answers. Es tracta d’una “llista de llistes” (un array multidimensional, en definitiva). En aquesta llista de llistes l’element answers[numPregunta][0] ens diu quin és l’índex de la resposta correcta de la pregunta numPregunta. No he fet una traducció directa de l’estructura de les llistes questions i answers a taules si no que he plantejat unes entitats totalment normalitzades. En la pràctica és el dona més flexibilitat per evolucionar l’aplicació.

Arquitectura de l’aplicació

L’aplicació és molt senzilla i s’hauria pogut resoldre amb un únic mòdul. Però crec que és una bona idea mantenir els bons costums sempre i, per això, he tractat de seguir algunes “bones pràctiques” pel que fa a arquitectura. Essencialment, he procurat seguir el patró MVC i he separat la funcionalitat en quatre mòduls.

quizz.py

Aquest mòdul no fa res més que instanciar el controlador i iniciar l’aplicació.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from controller import Controller

if __name__ == "__main__":
    controller = Controller()
    controller.initApp()

controller.py

El controlador s’implementa amb la classe Controller, molt senzilla, que veu tant la classe GUI com la classe Loader. Realment aquest controlador fa poc més que de pont entre la GUI i les dades carregades amb el Loader. Això és perquè el pas de pantalles està codificat directament als mètodes dels events de la GUI. Seria una bona idea, des del punt de vista d’arquitectura, portar aquesta navegació entre pantalles al controlador.

El codi és el següent:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from gui import GUI
from db import Loader


class Controller():
    gui = None
    db = None
    
    def __init__(self):
        self.db = Loader()
        self.gui = GUI()
        self.gui.setController(self)

    def initApp(self):
        self.db.loadData()
        self.gui.initApp()

    def getQuestion(self, numQuestion):
        return self.db.getQuestion(numQuestion)

    def getNumQuestions(self):
        return self.db.getNumQuestions()

dp.py

Al mòdul db.py implemento la classe Loader. Aquesta classe fa el procés invers de l’script db_loader.py: construeix les llistes questions i answers a partir de les taules de l’aplicació. A més, també afegeix uns mètodes per obtenir el nombre total de preguntes carregades, i per obtenir una pregunta, les seves respostes i la resposta correcta.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sqlite3

class Loader:
    CONNECTION_STRING = "/home/albert/workspace/python/quizz2/db/quizz.db"
    SELECT_QUESTIONS = "select id, question from questions"
    SELECT_ANSWERS = "select a.id, a.answer " + \
                     " from answers a, questions_answers qa " + \
                     " where qa.id_question = ? " + \
                     " and qa.id_answer = a.id"
    SELECT_RIGHT_ANSWER = "select id_right_answer " + \
                          " from question_right_answer " + \
                          " where id_question = ? "

    questions = []
    answer = []
    answers = []
    numQuestions = 0
    
    def loadData(self):
        conn = sqlite3.connect(self.CONNECTION_STRING)
        cur_questions = conn.cursor()
        cur_answers = conn.cursor()
        cur_right_answer = conn.cursor()
    
        cur_questions.execute(self.SELECT_QUESTIONS)
        self.numQuestions = 0
        for row_question in cur_questions:
            # load question
            self.questions.append(row_question[1])
            # load right answer
            cur_right_answer.execute(self.SELECT_RIGHT_ANSWER, (row_question[0],))
            id_right_answer = cur_right_answer.fetchone()[0]
            self.answer = []
            self.answer.append(id_right_answer)
            # load answers for this question
            cur_answers.execute(self.SELECT_ANSWERS, (row_question[0],))
            num_right_answer = 1
            for r_answer in cur_answers:
                self.answer.append(r_answer[1])
                if id_right_answer == r_answer[0]:
                    self.answer[0] = num_right_answer
                num_right_answer = num_right_answer + 1
            self.answers.append(self.answer)
            self.numQuestions = self.numQuestions + 1
        conn.close()
    
    def getQuestion(self, numQuestion):
        return [self.questions[numQuestion-1],
                self.answers[numQuestion-1],
                self.answers[numQuestion-1][0]] 

    def getNumQuestions(self):
        return self.numQuestions
        

Remarcar la utilització de les classes de connexió i de cursor. La paraula Cursor em fa pensar immediatament en els cursors de bases de dades, però a Python la classe Cursors cumpleix més missions que les d’un cursor de base de dades.

GUI.py

Finalment, implemento la classe GUI al mòdul gui.py. Aquesta classe implementa els mètodes de resposta a events de la interfícia gràfica. Tota la interfície gràfica està codificada en un fitxer xml (amb extensió .glade) ies construeix amb Gtk.builder().

L’accés als diferents objectes de la interfícies es fa per nom amb invocacions al mètode get_object(). Amb la referència a l’objecte, es poden fer servir tots els seus mètodes. El procés és molt senzill. Vet aquí el codi:

#!/usr/bin/env python
#-*- coding: utf-8 -*-

from gi.repository import Gtk

class GUI():
    builder = None
    formMain = None
    formNew =None
    formQuestion = None
    formScoring =None
    formAbout = None
    name = ""
    course = ""
    numQuestion = 1
    numQuestions = 0
    rightAnswer = 0
    rightAnswersCounter = 0
    controller = None
    FORMS = "/home/albert/workspace/python/quizz2/forms.glade"

    def setController(self, controller):
        self.controller = controller

    def initApp(self):
        self.builder = Gtk.Builder()
        self.builder.add_from_file(self.FORMS)
        self.builder.connect_signals(self)
        
        self.formMain = self.builder.get_object("applicationwindow1")
        self.formMain.show()
        Gtk.main()
        
    def onClose(self, *args):
        print "onClose"
        Gtk.main_quit(*args)
        exit()
    
    def onMenuitemNou(self, widget):
        self.formNew = self.builder.get_object("dialog1")
        self.formNew.set_transient_for(self.formMain)
        self.numQuestions = self.controller.getNumQuestions()
        self.builder.get_object("entry3").set_text("")
        self.builder.get_object("entry2").set_text("")        
        self.formNew.show()
        print "onMenuitemNouClick"
        
    def onMenuitemSurt(self, widget):
        print "onMenuitemSurtClick"
        Gtk.main_quit()
        exit()
        
    def onMenuitemAbout(self, widget):
        self.formAbout = self.builder.get_object("aboutdialog1")
        self.formAbout.set_transient_for(self.formMain)
        self.formAbout.run()
        self.formAbout.hide()
            
        print "onMenuitemAbout"
        
    def onButton1AcceptarClick(self, widget):
        self.name = self.builder.get_object("entry3").get_text()
        self.course = self.builder.get_object("entry2").get_text()
        self.formNew.hide()

        self.formQuestion = self.builder.get_object("dialog2")
        self.formQuestion.set_transient_for(self.formMain)
        self.setFormQuestion(self.numQuestion)
        self.formQuestion.show()        
        
        print "Nom: %s; Curs: %s" % (self.name, self.course)
        print "onButton1AcceptarClick"

    def setFormQuestion(self, numQuestion):
        [question, answers, self.rightAnswer] = self.controller.getQuestion(numQuestion)
        self.builder.get_object("label8").set_text("%s de %s curs" % (self.name, self.course))
        self.builder.get_object("label3").set_text("Pregunta %d" % numQuestion)
        self.builder.get_object("label4").set_text(question)
        self.builder.get_object("checkbutton1").set_label(answers[1])
        self.builder.get_object("checkbutton2").set_label(answers[2])
        self.builder.get_object("checkbutton3").set_label(answers[3])
        self.builder.get_object("checkbutton4").set_label(answers[4])
        self.builder.get_object("checkbutton1").set_active(False)
        self.builder.get_object("checkbutton2").set_active(False)
        self.builder.get_object("checkbutton3").set_active(False)
        self.builder.get_object("checkbutton4").set_active(False)

    def onButton2CancelarClick(self, widget):
        self.formNew.hide()
        print "onButton2CancelarClick"

    def onButtonSeguir(self, widget):
        # validate right answer. increment question counter,
        myAnswer = (1 * self.builder.get_object("checkbutton1").get_active()) + \
                   (2 * self.builder.get_object("checkbutton2").get_active()) + \
                   (4 * self.builder.get_object("checkbutton3").get_active()) + \
                   (8 * self.builder.get_object("checkbutton4").get_active())
        rightAnswer = pow(2, self.rightAnswer - 1)

        if myAnswer == rightAnswer:
            self.rightAnswersCounter = self.rightAnswersCounter + 1

        self.numQuestion = self.numQuestion + 1

        if self.numQuestion <= self.numQuestions:
            self.setFormQuestion(self.numQuestion)
            self.formQuestion.show()
        else:
            self.formQuestion.hide()
            self.formScoring = self.builder.get_object("dialog3")
            self.formScoring.set_transient_for(self.formMain)
            self.builder.get_object("labelNom").set_text("%s de %s curs" % (self.name, self.course))
            self.builder.get_object("label6").set_text("%d preguntes" % self.rightAnswersCounter)
            self.builder.get_object("label7").set_text("d'un total de %d preguntes" % self.numQuestions)
            self.formScoring.show()        

        print "onButtonSeguir"
        
    def onCancelarQuizz(self, widget):
        self.reset()
        self.formQuestion.hide()
        print "onCancelarClick"

    def onTancarClick(self, widget):
        self.reset()
        self.formScoring.hide()
        print "onTancarClick"

    def reset(self):
        self.name = ""
        self.course = ""
        self.numQuestion = 1
        self.rightAnswer = 0
        self.rightAnswersCounter = 0

Millores
El programa és una maqueta i es pot ampliar de moltes formes. Se m’acuden les següents millores:
– desar nom, curs i resultat obtingut a la BD.
– incorporar un cronòmetre per qüestionari: temps màxim de resolució del qüestionari.
– incorporar un cronòmetre per pregunta: temps màxim per pregunta.
– possibilitat de navegació endavant i endarrere pel qüestionari (ara només deixa avançar)
– possibilitat de nombre variable de possibles respostes
– possibilitat de vàries (o cap) respostes correctes possibles
– possibilitat de repetir el qüestionari un nombre màxim de cops.

Més millores:
– Afegir pantalles per a poder entrar nous qüestionaris
– perfils d’usuari (administrador, pot crear qüestionaris; usuari, pot resoldre qüestionaris)
– tenir en compte el curs i que l qüestionari s’adapti als nivell de l’usuari
– selecció de qüestionaris per tòpic, o per codi…
– descarregar d’Internet nous qüestionaris i desar-los en local per a execució off-line
– publicació a un servidor dels resultats obtinguts
– …

En fi. Un munt de possibilitats. De fet, si fem servir programari educatiu veurem un munt d’opcions que es podrien implementar a l’aplicació.

Repositori Github
Tot el codi el podeu trobar al github, a https://github.com/abaranguer/quiz

Un Curriculum fet amb l’org-mode de l’Emacs

Emacs és el veterà i llegendari editor de textos que va programar Richard Stallman al MIT allà pel 1975. Amb el pas dels anys Emacs ha esdevingut alguna cosa més que un simple editor de textos i se li han incorporat multitud d’opcions i facilitats de tota mena.

És una eina molt potent, versàtil i extensible: una aplicació amb vocació de sistema operatiu, de la que no cal sortir per  a poder fer, pràcticament, totes les tasques que habitualment realitza un desenvolupador.

La potència d’Emacs ve, principalment, de la seva capacitat per a personalitzar-lo i fer-lo créixer. Més que un editor de textos, Emacs es pot considerar com una plataforma de desenvolupament basada en el llenguatge Lisp (en el seu dialecte ELisp).

Lisp és un dels llenguatges informàtics més antics, però és plenament vigent. No només és el llenguatge de l’Emacs. Ës ben viu i, per exemple, compta amb una moderna versió, Clojure,  per a la Java Virtual Machine.

40 anys d’extensions per l’Emacs donen per molt i n’hi han algunes que són, senzillament, genials. Una d’aquestes extensions, genials, és l’Org-Mode.

L’Org-Mode és una extensió de l’Emacs que permet prendre notes i apunts, organitzar-los, definir tasques, prioritzar-les, controlar temps d’execució de les tasques, o implementar el popular mètode GTD de David Allen… Seria com una mena de súper-agenda, planificador, control de projectes… també permet exportar tota aquesta organització a LaTeX, a Pdf… o a formats més exòtics com el format FreeMind (i crear fàcilment mind maps). De fet, Org-Mode és tan versàtil , com l’Emacs, que es pot fer servir de moltes formes diferents i trobar-li usos variats.

Doncs bé, circumstàncies personals i el fet d’estar de vacances m’han portat a dedicar algunes hores a posar al dia el meu currículum, però he pensat que millor fer-ho de forma que em servís per practicar alguna cosa. La “cosa” que que he “practicat” és l’org-mode de l’Emacs.

La millor explicació de l’Org-Mode i de com fer-lo servir l’he trobat en aquest vídeo d’una conferència que va dir Carsten Dominik, l’autor de l’Org-Mode, a les Google Tech Talks de 2008.

El procediment que he seguit ha estat

1. Recuperar la versio desactualitzada del CV i desar-lo com  text.

2. He completat la informació que faltava.

3. Amb Emacs en Org-Mode, anar reestructurant les diferents parts del text i organitzant-les en apartats, subapartats… reordenant on considerés que fos necessari.

4. He afegit formats (itàliques, negretes, subratllats…), enllaços a Internet, una bonica foto… tot fent ús de l’etiquetat que ofereix l’Org-Mode per a l’efecte.

5. He revisat, i tornat a revisar, l’ortografia, la sintaxi… (i segur que se m’han colat errors).

6. He exportat als formats:

HTML:  amb org-export-as-html

TeX (LaTeX) i PDF: amb org-export-as-pdf

ASCII: amb org-export-as-ascii

FREEMIND: Amb org-export-as-freemind

Aleshores, fent us del FreeMind he fet un pas addicional d’exportació i he obtingut el meu currículum en versio Flash (Cal dir, però, que la versió flash ha de polir-se una mica, perquè els formats de l’Org-Mode no s’han traduït correctament.)

7. He actualitzat el curriculum a aquest mateix blog, i he posat la versió Html, el PDF  i la versió Flash a un espai de pàgines personals que tinc des de fa temps.

8. He penjat el projecte -realment crec que l’edició del CV amb Org-Mode i Emacs s’ha semblat molt més a un petit projecte que no pas una simple ediciṕ de text- al meu GitHub. Si teniu interès per veure com és el font d’un document en org-mode, reviseu el fitxer cv.org.

I ara una confessió: En la guerra religiosa entre Vimàires i Emacsers jo he estat, durant molts anys, essencialment agnòstic. Però d’un parell d’anys cap aquí que m’he decantat.

Vi (o Vim) és una eina extraordinària (amb el punt a favor que forma part de les instal·lacions base de les distribucions Linux, o sigui, que no cal instalar-lo) però, que els vimàires em perdonin, crec que avui ja no podria passar sense l’Emacs.

real_programmers

😉 Bones vacances!

Biblioteques compartides a Linux, i com utilitzar-les des de Python amb ctypes

Shared libraries, Python, Linux… feia temps que tenia ganes de tractar aquestes qüestions i, finalment, he trobat el moment. El post d’avui plantejarà aquests punts:

1. Què és una static library de Linux?
2. Què és una shared library de Linux?
3. Com fer una shared library amb C?
4. Com fer servir la shared library?
5. Com invocar dinàmicament una shared library des de Python amb CTypes?
6. Com invocar dinàmicament una shared library des de C amb les funcions de càrrega dinàmica()?

1. Què són les static library
Per explicar què són les shared libraries és interessant explicar primer que són les static libraries. Reviseu Static Libraries, del Program Library HOWTO de The Linux Documentation Project (capítol 2 de PDF).

Les static librares són col·leccions de fitxers objecte ordinaris (fitxers “.o”, els que resulten de compilar amb gcc -c) que s’agrupen en biblioteques que acostumen a prendre l’extensió “.a”. Per a generar la biblioteca es fa servir el programa “ar” (“archiver”).

Les biblioteques estàtiques permeten enllaçar amb els programes sense que calgui compilar-ne el codi estalviant, doncs,  temps de recompilació; i, per tant, sense que calgui el codi de la biblioteca.

1.1. Com crear una static library
Per a crear una static library a partir dels fitxers objecte file1.o i file2.o la instrucció bàsica seria:

ar rcs biblioteca.a file1.o file2.o

les opcions rcs volen dir:
c: crea l’arxiu de biblioteca.
r: afegeix, o reemplaça, els fitxers objecte.
s: afegeix o actualitza l’índex a la biblioteca

Per a una referència completa, consulteu el manual:

man ar

1.2. Com fer servir l’static library
Un cop creada la biblioteca aleshores es fa servir al compilar amb l’opció gcc -lnom_biblioteca. Consulteu el manual

man gcc

Tingueu en compte les opcions:

-l library Cerca la biblioteca “library” durant l’enllaçat. Cal tenir en compte on s’escriu l’opció, l’enllaçador cerca i processa les biblioteques i els mòduls objecte en l’ordre en que apareixen a l’ordre de compilació; per tant, foo.o -lz bar.o cerca la llibreria z després de foo.o però abans de bar.o. Si bar.o fa referència a funcions de z, aquestes funcions no es carregaran.

Finalment, amb l’opció -L es pot indicar l’ubicació de la lliberia.

1.3. Nom de la static llibrary

L’enllaçador cerca la biblioteca per la llista de directoris estàndard. El nom del fitxer que cerca és “liblibrary.a”, és dir, prefixa el nom de la biblioteca amb “lib” i afegeix l’extensió “.a”. En l’exemple d’abans amb la biblioteca z l’enllaçador buscaria “libz.a”.

Atenció, doncs: seguint amb l’exemple anterior, a la creació de la biblioteca z amb ar faré servir el nom libz.a, però l’invocaré al gcc amb gcc -lz. z és el nom d’invocació, i libz.a el nom real de la biblioteca

1.4. Exemple

Amb un exemple es veurà tot més clar:

Creo una biblioteca estàtica amb els dos fitxers file1.c i file2.c (i file1.h, file2.h); les funcions de la biblioteca s’invoquen des d’una funció main definida al fitxer principal.c (i principal.h). Al Makefile es troben els detalls de l’utilització. Fixeu-vos que, com era d’esperar, el resultat de compilar fent servir la biblioteca, o fent servir els mòduls objecte directament és el mateix en ambdós casos. Fixem-nos també amb la mida dels binaris (biblioteca, mòduls objecte i executables) obtinguts.

file1.c

#include 

int funcio1(int num) {
  int i;

  for(i=1; i<=num; i++) {
    printf("fun1 - %d\n",i);
  }

  return 0;
}

file2.c

#include 

int funcio2(int num) {
  int i;  

  for(i=1; i<=num; i++) {
    printf("fun2 - %d\n",i);
  }

  return 0;
}

Els fitxers de capçalera, file1.h i file2.h

file1.h

/* function prototype */
extern int funcio1(int val);

file2.h

/* function prototype */
extern int funcio2(int val);

i el fitxer principal.c, que invoca les funcio1 i funcio2.

#include  

#include "file1.h"
#include "file2.h"
 
int main(int argc, char *argv[]) {
  funcio1(5);
  funcio2(8);

  return 0; 
} 

Makefile que genera la biblioteca estàtica i dos executables, el primer fent servir la biblioteca estàtica; i el segon, enllaçant directament els mòduls objecte

all: principal2 principal clean

file1.o: file1.c
    gcc -c file1.c

file2.o: file2.c
    gcc -c file2.c

proves: file1.o file2.o
    ar rcs libprova.a file1.o file2.o

principal.o: principal.c 
    gcc -c principal.c

principal: principal.o proves
    gcc -o principal principal.o -L. -lprova

principal2: principal.o file1.o file2.o
    gcc -o principal2 principal.o file1.o file2.o

Faré servir aquests fitxers de prova al llarg del post.

Si executo el makefile

albert@atenea:/media/albert/post/prova-lib$ make
gcc -c principal.c
gcc -c file1.c
gcc -c file2.c
gcc -o principal2 principal.o file1.o file2.o
ar rcs libprova.a file1.o file2.o
gcc -o principal principal.o -L. -lprova

Es genera la biblioteca estàtica i els executables principal i principal2 que, com era d’esperar, són de la mateixa mida.

aalbert@atenea:/media/albert/post/prova-lib$ ls -al
total 152
drwx------ 2 albert albert 8192 jun 13 21:42 .
drwx------ 4 albert albert 8192 jun 13 20:47 ..
-rw-r--r-- 1 albert albert  127 jun 13 21:08 file1.c
-rw-r--r-- 1 albert albert   54 jun  2 23:29 file1.h
-rw-r--r-- 1 albert albert 1052 jun 13 21:42 file1.o
-rw-r--r-- 1 albert albert  129 jun 13 21:08 file2.c
-rw-r--r-- 1 albert albert   54 jun  2 23:29 file2.h
-rw-r--r-- 1 albert albert 1052 jun 13 21:42 file2.o
-rw-r--r-- 1 albert albert 2320 jun 13 21:42 libprova.a
-rw-r--r-- 1 albert albert  519 jun 13 21:41 Makefile
-rw-r--r-- 1 albert albert 7394 jun 13 21:42 principal
-rw-r--r-- 1 albert albert 7394 jun 13 21:42 principal2
-rw-r--r-- 1 albert albert  140 jun  2 23:29 principal.c
-rw-r--r-- 1 albert albert  992 jun 13 21:42 principal.o

2. Què són les shared library?

Pe contestar aquesta pegunta, l’article de referència és Shared Libraries, del Program Library HOWTO de The Linux Documentation Project (capítol 3 de PDF).

Literalment, shared library vol dir biblioteca -de funcions- compartida. Les shared libraries són mòduls que s’enllacen en temps d’execució, en el moment de carregar-se l’aplicació que les enllaça, és dir en runtime; a diferència de les biblioteques estàtiques que s’enllacen en temps de compilació.

Això permet que les aplicacions que les invoquen tinguin executables més petits i que siguin més fàcils de mantenir i actualitzar.

A més, mitjançant la crida al sistema dlopen(), les shared libraries també poden carregar-se dinàmicament en qualsevol moment de l’execució i no només a l’inici. Per aquesta raó, les shared libraries també se les coneix com DLL, Dinamic Link Libraries, tot i que potser aquesta nomenclatura és més utilitzada a entorns Windows.

Que diferents tipus d’aplicacions puguin fer servir les mateixes shared libraries vol dir que les funcions i dades d’aquestes biblioteques no poden fer referencies a adreces de memòria absolutes, doncs l’enllaçat farà que les posicions de memòria en que finalment s’ubicaran puguin variar entre les diferents aplicacions. Això ens diu que per generar les shared libraries caldrà demanar que el mòdul objecte generat sigui reubicable.

Una shared library pot enllaçar-se simultàniament a diverses aplicacions. Quan la shared library està correctament instal·lada i respectant uns convenis de noms, el sistema de biblioteques compartides permet la convivència de diferents versions de la mateixa llibreria i el seu us per les diferents aplicacions.

2.1. Noms de les biblioteques compartides
2.1.1. soname
La clau del sistema de shared libraries està en els convenis de noms a seguir. Cal distingir entre el nom real de la shared library i el seu “soname”.
El “soname” d’una shared library es construeix amb el prefix “lib”, seguit del nom de la biblioteca, seguit del sufix “.so”, un punt, i un número de versió que s’ha d’augmentar cada cop que es canviï la interface de la biblioteca, és dir quan canvia el nombre de les funcions, o la signatura de les funcions.
El soname complet de la biblioteca inclou també el path fins a la biblioteca.
En general, el soname no és la llibreria propiament dita, si no un enllaç simbòlic al nom real de la biblioteca compartida

2.1.2. nom real (“real name”)
El fitxer amb el modul objecte reubicable rep el nom real de la biblioteca. El nom real es construeix afegint al soname un “minor number” i, opcionalment, un altre punt i el nombre de release. El minor number i el de release permeten conèixer exactament quina versió de la biblioteca està instal·lada i habiliten un control fi de la configuració. El nom complet de la biblioteca inclou també el path fins a la biblioteca.
El “real name” complet de la biblioteca inclou també el path fins a la biblioteca.

2.1.3. Nom per l’enllaçador (“linker name”)
És el nom que es fa servir per utilitzar la biblioteca. Es el soname sense número de versió. Com amb la resta de noms, el linker name complet de la biblioteca inclou també el path fins a la biblioteca.

2.1.4 Nom d’invocació

Com amb les biblioteques estàtiques, la invocació de la biblioteca al gcc amb l’opció -l es fa pel seu “nom d’invocació”, que serveix per construir el linker name. La cadena és, doncs, Nom d’invocació – Linker Name – Soname – Real name

2.2. utilització dels noms

La gestió de les biblioteques compartides és basa en la separació d’aquests noms.

– Utilització: quan les aplicacions llisten internament les shared libraries que necessiten només han de llistar el sonames requerits.

– Creació: quan es crea una shared library s’ha de crear amb tota la informació de versió completament detallada, és dir, els noms reals (“real names”).

– Instal·lació 1. ldconfig. La instal·lació d’una shared library s’ha de fer a alguna de les carpetes especials destinades a acollir biblioteques compartides i aleshores executar el programa ldconfig. ldconfig examina els fitxers existents i crea els sonames, és dir, els enllaços simbòlics als real names. A més actualitza la caché de biblioteques compartides /etc/ld.so.cache.

– Instal·lació 2. linker name. ldconfig no estableix els “linker names”, això es fa durant la instal·lació de la biblioteca, amb un script d’instal·lació, en general. El linker name, en general, és un enllaç simbòlic al soname més recent.

Aquest joc d’enllaços simbòlics permet que es pugui apuntar a una versió o una altre de les biblioteques. Per exemple, en desenvolupament, amb finalitats de depuració enllaçant diferents versions de la biblioteca.

Per exemple, la shared library que implementa readline:

/usr/lib/libreadline.so és el linker name complet i és l’enllaç simbòlic a…
/usr/lib/libreadline.so.3 és el soname complet i és l’enllaç simbòlic a…
/usr/lib/libreadline.so.3.0 que és el nom real complet i el mòdul objecte que conté el codi.

Els tres noms anteriors, en principi, són necessaris en runtime.

En compilació, a més, es fa servir el nom d’invocació de la biblioteca a l’opció -l del gcc: és dir,  gcc -lreadline

3. Com crear una Shared Library?

És molt semblant al procés de crear una Static Library.
Primer: crear els diferents mòduls objecte que conformen la biblioteca, amb l’opció -fPIC que genera codi reubicable.
Segon: amb els mòduls objecte creats, ja es pot construir la biblioteca amb gcc:

gcc -shared -Wl,-soname,soname_de_la_library -o real_name_library mòdul1.o mòdul2.o... -lc

El següent Makefile mostra el procediment:

all: prova

file1.o: file1.c
    gcc -fPIC -g -c -Wall file1.c

file2.o: file2.c
    gcc -fPIC -g -c -Wall file2.c

prova: file1.o file2.o
    gcc -shared -Wl,-soname,libprova.so.1 -o libprova.so.1.0.1 file1.o file2.o -lc

Com a remarques: a la generació dels mòduls objecte he fet servir,a més de -fPIC que ja he explicat, les opcions -g, per afegir informació de depuració i -Wall, per a mostrar tots els missatges de warnings. Són opcions que faciliten el desenvolupament.

La línia que construeix la shared library inclou

-shared indicar que és una shared library
-Wl,-soname,libprova.so.1 -Wl passa paràmetres a l’enllaçador. El paràmetre passat és el soname. Cal posar les comes i no es poden deixar espais en blanc que no estiguin “escapats”
-o libprova.so.1.0.1 és el “real name” de la biblioteca
-lc enllaça amb la lliberia libc.a estàtica

Aleshores, executant make obtinc la shared library libprova.so.1.0.1

albert@atenea:/media/albert/16GB/post shared libraries/prova-lib$ make
gcc -fPIC -g -c -Wall file1.c
gcc -fPIC -g -c -Wall file2.c
gcc -shared -Wl,-soname,libprova.so.1 -o libprova.so.1.0.1 file1.o file2.o -lc

i , efectivament:

albert@atenea:/media/albert/post/prova-lib$ ls -al
total 168
drwx------ 2 albert albert 8192 jun 13 22:22 .
drwx------ 4 albert albert 8192 jun 13 20:47 ..
-rw-r--r-- 1 albert albert  127 jun 13 21:08 file1.c
-rw-r--r-- 1 albert albert   54 jun  2 23:29 file1.h
-rw-r--r-- 1 albert albert 2660 jun 13 22:22 file1.o
-rw-r--r-- 1 albert albert  129 jun 13 21:08 file2.c
-rw-r--r-- 1 albert albert   54 jun  2 23:29 file2.h
-rw-r--r-- 1 albert albert 2660 jun 13 22:22 file2.o
-rw-r--r-- 1 albert albert 8271 jun 13 22:22 libprova.so.1.0.1
-rw-r--r-- 1 albert albert  247 jun 13 22:22 Makefile
-rw-r--r-- 1 albert albert  140 jun  2 23:29 principal.c

4. Fer servir la biblioteca compartida

El següent pas és fer servir la biblioteca. Hi han dos punts de vista a tenir en compte:

4.1 El desenvolupador

El desenvolupador genera versions de la biblioteca i requereix provar-les ràpidament. Per al desenvolupador la ubicació de la biblioteca ha de poder ser qualsevol lloc que li vagi bé.

Hi han dues opcions principals:

– o bé fer servir LD_LIBRARY_PATH a la sessió actual

– o bé instal·lar de forma permanent la biblioteca a una carpeta de desenvolupament

4.1.1 Per sessió, amb LD_LIBRARY_PATH

Al punt 3 he creat la  biblioteca libprova.so.1.0.1. Ara la faig servir per crear un executable amb el següent makefile

all: principal3

principal.o: principal.c
    gcc -o principal.o -c principal.c

principal3: principal.o
    gcc -o principal3  principal.o -lprova -L.

El resultat de la compilació és l’executable principal3

albert@atenea:~/workspace/prova-lib$ make
gcc -o principal3  principal.o -lprova -L.
albert@atenea:~/workspace/prova-lib$ ls -al
total 100
drwxrwxr-x  2 albert albert 4096 jun 13 23:19 .
drwxrwxr-x 13 albert albert 4096 jun  6 21:46 ..
-rw-r--r--  1 albert albert  127 jun 13 21:08 file1.c
-rw-r--r--  1 albert albert   54 jun  2 23:29 file1.h
-rw-r--r--  1 albert albert  129 jun 13 21:08 file2.c
-rw-r--r--  1 albert albert   54 jun  2 23:29 file2.h
-rw-r--r--  1 albert albert 8271 jun 13 22:22 libprova.so.1.0.1
-rw-r--r--  1 albert albert  185 jun 13 22:54 Makefile
-rw-r--r--  1 albert albert 7394 jun 13 21:42 principal
-rw-r--r--  1 albert albert 7394 jun 13 21:42 principal2
-rwxrwxr-x  1 albert albert 7316 jun 13 23:19 principal3
-rw-r--r--  1 albert albert  140 jun  2 23:29 principal.c
-rw-rw-r--  1 albert albert  992 jun 13 23:04 principal.o

Es pot veure que ha generat principal3 i que, efectivament és més petit que executables obtinguts amb les biblioteques estàtiques, fins aquí bé. Però què passa quan provo d’executar principal3?

albert@atenea:~/workspace/prova-lib$ principal3
principal3: error while loading shared libraries: libprova.so.1: cannot open shared object file: No such file or directory

Que no troba la biblioteca. Com he dit abans, les biblioteques compartides han d’estar a unes carpetes específiques. O bé, a les carpeta indicades a LD_LIBRARY_PATH (cal, però, anar amb compte amb LD_LIBRARY_PATH).

Aquest problema es veu molt clar amb ldd (Consulteu el manual man ldd) que torna  les biblioteques compartides que fa servir un executable.

albert@atenea:~/workspace/prova-lib$ ldd principal3
    linux-gate.so.1 =>  (0xb7798000)
    libprova.so.1 => not found
    libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xb75cc000)
    /lib/ld-linux.so.2 (0xb7799000)

Com he explicat abans, el procediment és executar ldconfig i crear un enllaç simbòlic del linker name a soname.  Som-hi:

albert@atenea:~/workspace/prova-lib$ ldconfig -n .
albert@atenea:~/workspace/prova-lib$ ln -s ./libprova.so.1 ./libprova.so
albert@atenea:~/workspace/prova-lib$ ls -al
total 100
drwxrwxr-x  2 albert albert 4096 jun 13 23:34 .
drwxrwxr-x 13 albert albert 4096 jun  6 21:46 ..
-rw-r--r--  1 albert albert  127 jun 13 21:08 file1.c
-rw-r--r--  1 albert albert   54 jun  2 23:29 file1.h
-rw-r--r--  1 albert albert  129 jun 13 21:08 file2.c
-rw-r--r--  1 albert albert   54 jun  2 23:29 file2.h
lrwxrwxrwx  1 albert albert   15 jun 13 23:34 libprova.so -> ./libprova.so.1
lrwxrwxrwx  1 albert albert   17 jun 13 23:34 libprova.so.1 -> libprova.so.1.0.1
-rw-r--r--  1 albert albert 8271 jun 13 22:22 libprova.so.1.0.1
-rw-r--r--  1 albert albert  185 jun 13 22:54 Makefile
-rw-r--r--  1 albert albert 7394 jun 13 21:42 principal
-rw-r--r--  1 albert albert 7394 jun 13 21:42 principal2
-rwxrwxr-x  1 albert albert 7316 jun 13 23:19 principal3
-rw-r--r--  1 albert albert  140 jun  2 23:29 principal.c

“ldconfig n .” busca sobre el directori actual i crea l’enllaç simbòlic al soname

libprova.so.1 -> libprova.so.1.0.1

Manualment, amb ln -s he creat l’enllaç simbòlic al linker name

libprova.so -> ./libprova.so.1

I ara, ja només cal establir amb  LD_LIBRARY_PATH  que a la carpeta /home/abert/workspace/prova-lib hi han biblioteques compartides

albert@atenea:~/workspace/prova-lib$ LD_LIBRARY_PATH=/home/albert/workspace/prova-lib/
albert@atenea:~/workspace/prova-lib$ export LD_LIBRARY_PATH

i, per descomptat, ara sí que funciona:    😉

albert@atenea:~/workspace/prova-lib$ principal3
fun1 - 1
fun1 - 2
fun1 - 3
fun1 - 4
fun1 - 5
fun2 - 1
fun2 - 2
fun2 - 3
fun2 - 4
fun2 - 5
fun2 - 6
fun2 - 7
fun2 - 8
albert@atenea:~/workspace/prova-lib$

El procediment amb LD_LIBRARY_PATH només hauria de fer-se servir en desenvolupament, de forma puntual per provar.

4.1.1 Permanent, a una carpeta especificada a /etc/ld.so.conf

Si torno LD_LIBRARY_PATH al seu estat original principal3 deixa de funcionar. Per exemple, si apago l’ordinador i el torno engegar, LD_LIBRARY_PATH perd els canvis. En lloc d’establir de forma general un valor per LD_LIBRARY_PATH, que pot ser perillós, una alternativa segura és especificar una carpeta pròpia de desenvolupament a /etc/ld.so.conf

Resetejo LD_LIBRARY_PATH, i preparo la carpeta de desenvolupament, copiant-hi la biblioteca compartida, executant ldconfig i establint l’enllaç simbòlic del linker name

albert@atenea:~/workspace/prova-lib$ LD_LIBRARY_PATH=
albert@atenea:~/workspace/prova-lib$ export LD_LIBRARY_PATH
albert@atenea:~/workspace/prova-lib$ mkdir /home/albert/dev-lib
albert@atenea:~/workspace/prova-lib$ cp libprova.so.1.0.1 /home/albert/dev-lib/
albert@atenea:~/workspace/prova-lib$ cd /home/albert/dev-lib/
albert@atenea:~/dev-lib$ ldconfig -n /home/albert/dev-lib/
albert@atenea:~/dev-lib$ ln -s /home/albert/dev-lib/libprova.so.1 /home/albert/dev-lib/libprova.so
albert@atenea:~/dev-lib$ ls -al
total 20
drwxrwxr-x  2 albert albert 4096 jun 14 00:03 .
drwxr-xr-x 80 albert albert 4096 jun 14 00:01 ..
lrwxrwxrwx  1 albert albert   34 jun 14 00:03 libprova.so -> /home/albert/dev-lib/libprova.so.1
lrwxrwxrwx  1 albert albert   17 jun 14 00:02 libprova.so.1 -> libprova.so.1.0.1
-rw-r--r--  1 albert albert 8271 jun 14 00:01 libprova.so.1.0.1
albert@atenea:~/dev-lib$

En aquest moment, principal3 falla perquè no troba la biblioteca compartida.

Ara estableixo a /etc/ld.so.conf la nova carpeta on cercar biblioteques compartides

sudo emacs /etc/ld.so.conf

/etc/ld.so.conf queda així

include /etc/ld.so.conf.d/*.conf
# afegeixo carpeta de biblioteques de desenvolupament
/home/albert/dev-lib

A continuació cal indicar que es tingui en compte la nova carpeta i es reconstrueixi la memòria cau de biblioteques compartides. Es fa amb ldconfig:

sudo ldconfig

En aquest moment, principal3 torna a ser operativa. Si ara examino la memòria cau de biblioteques compartides observo que, efectivament, està fent servir la biblioteca de /home/albert/dev-lib

albert@atenea:~/workspace/prova-lib$ principal3 
fun1 - 1
fun1 - 2
fun1 - 3
fun1 - 4
fun1 - 5
fun2 - 1
fun2 - 2
fun2 - 3
fun2 - 4
fun2 - 5
fun2 - 6
fun2 - 7
fun2 - 8
albert@atenea:~/workspace/prova-lib$ ldconfig -p | grep "prova"
    libprova.so.1 (libc6) => /home/albert/dev-lib/libprova.so.1
    libprova.so (libc6) => /home/albert/dev-lib/libprova.so
albert@atenea:~/workspace/prova-lib$

4.2 El distribuïdor

L’altre punt de vista d’ús de la biblioteca és el del distribuïdor de la biblioteca. Hi han un parell de criteris a tenir en compte en la distribució de codi i en la ubicació de les biblioteques compartides.

Ambdós criteris estableixen ubicacions permanents de les biblioteques compartides i, per tant, es defineixen a /etc/ld.so.conf.
4.2.1 Distribució seguint l’Estàndard GNU
L’estàndard aplica a projectes de desenvolupament de codi obert. Seguint aquest estàndard, les biblioteques han d’anar a /usr/local/lib, i els executables a /usr/local/bin
4.2.2 Filesystem Hierarchy Standard (FHS)
L’estàndard aplica al programari d’una distribució. La majoria de les biblioteques ha d’anar a /usr/lib, i les biblioteques per a l’arrencada del sistema, a /lib

En general, quan es distribueix codi de projectes GNU, és dir, projectes en evolució i construcció, la recomanació és seguir el GNU Standard. En canvi, quan el codi està en “producció” i s’inclou a una distribució de Linux, aleshores la recomanació és ubicar les biblioteques d’acord amb el criteri FHS.

5. Com invocar una shared library des de Python amb CTypes?

No me n’he oblidat. Per acabar, Python incorpora el package CTypes (documentació) que li permet enllaçar shared libraries i fer-ne us de les seves funcions de forma molt senzilla, semblant al LoadLibrary de VisualBasic.

És directe:
– faig l’import;
– amb CDLL carrego la biblioteca i obtinc un handle per fer-la servir. CDLL rep el soname com a paràmetre.
– Faig servir el handle per invocar les funcions de la biblioteca.

albert@atenea:~/workspace/prova-lib$ python
Python 2.7.6 (default, Mar 22 2014, 22:59:38) 
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from ctypes import *
>>> prova = CDLL("libprova.so.1")
>>> ret = prova.funcio1(7)
fun1 - 1
fun1 - 2
fun1 - 3
fun1 - 4
fun1 - 5
fun1 - 6
fun1 - 7
>>> ret = prova.funcio2(3)
fun2 - 1
fun2 - 2
fun2 - 3

6. Com invocar una shared library des de C amb les funcions de càrrega dinàmica()?

El que he fet al punt 4 és una invocació dinàmica de la shared library prova des de Python. Això mateix també es pot fer amb C, fent servir les crides al sistema dl*, (dlopen(), dlsym(), dlerror() i dlclose()). La referència, en aquest cas, Dynamically Loaded (DL) Libraries, del Program Library HOWTO de The Linux Documentation Project (capítol 4 del PDF).

També és directe. Per il·lustrar el procediment, faré un principal4 que, com es veu al makefile, no invoca la biblioteca prova, sino la dl (Dynamic Load), que és la que aporta les funcions de càrrega dinàmica:

Makefile

all: principal4

principal_dl.o: principal_dl.c
    gcc -o principal_dl.o -c principal_dl.c

principal4: principal_dl.o
    gcc -o principal4  principal_dl.o -ldl

principal_dl.c

#include <stdlib.h>
#include <stdio.h>
#include <dlfcn.h>

int main(int argc, char **argv) {
    void *handle;
    int (*fun1)(int);   /* extern int funcio1(int val); */
    int (*fun2)(int);   /* extern int funcio2(int val); */
    char *error;
    int ret1;
    int ret2;
    
    handle = dlopen ("libprova.so.1", RTLD_LAZY);
    if (!handle) {
        fputs (dlerror(), stderr);
        exit(1);
    }
    
    fun1 = dlsym(handle, "funcio1");
    if ((error = dlerror()) != NULL)  {
        fputs(error, stderr);
        exit(1);
    }

    fun2 = dlsym(handle, "funcio2");
    if ((error = dlerror()) != NULL)  {
        fputs(error, stderr);
        exit(1);
    }

    printf("Sortida de funcio1(3)\n");
    ret1 = (*fun1)(3);
    printf("\nSortida de funcio2(7)\n");
    ret2 = (*fun2)(7);
    printf("\nret1: %d; ret2: %d\n\n", ret1, ret2);

    dlclose(handle);
}

Del codi anterior, destacar que:

– He definit fun1 i fun2 com punters a funcions amb la  mateixa signatura de funcio1 i funcio2;

– La utilització de dlopen() per carregar dinàmicament la biblioteca, passant el soname com a paràmetre. dlopen() retorna un “handle”, una referència, a la biblioteca.

– Amb aquest handle, faig servir dlsym() per trobar les funcions a executar. dlsym() retorna punters a les funcions

– Faig servir els punters a les funcions, és dir, utiloitzo les funcions de la biblioteca.

– Al llarg de tot el programa, si hi ha algun error de càrrega de la biblioteca, aquest es pot obtenir amb dlerror()

– Quan he fet servir la biblioteca, la descarrego amb dlclose()

7. Resum
En aquest post he explicat com
– Què és una static library.
– Què és una shared library.
– Com fer una shared library amb C.
– Com fer servir la shared library.
– Com invocar una shared library des de Python amb ctypes.
– I com invocar una shared library des de C amb el grup de funcions de càrrega dinàmica().

EL codi del post es pot descarregar del  repositori GitHub.

Jeremy Rifkin. La societat del cost marginal zero.

Enceto el 2015 amb un post sobre un llibre que estic llegint i que m’està semblant molt interessant: “The Zero Marginal Cost Society” de Jeremy Rifkin.

Jeremy Rifkin és moltes coses però, de forma molt simplificada, diré que és algú que té la virtut de captar tendències actuals (de molts aspectes: socials, polítiques, econòmiques, tecnològiques) i  descriure possibles escenaris de futur i els camins que duen a ells a partir d’aquestes tendències. En definitva, un dels gurús més respectats de la prospectiva.

Rifkin ha publicat llibres tan interessants com “The end of work” (1995), “The age of access” (2000),  “The hydrogen economy” (2002) o “The third industrial revolution” (2010), entre d’altres.  Doncs bé, es pot dir que “The zero marginal cost society” ve a relligar els més de vint anys de teories sobre com serà el futur en una aposta que, en síntesi, és: la conjunció de la internet de la informació, la internet  de les coses (Internet of Things, IoT) i la internet de l’energia (smart grids), amb l’adopció  de les energies renovables barates i a l’abast de tothom provocaran, ni més ni menys, que la fi del capitalisme tal com l’entenem avui i l’aparició d’un model de societat basat en el “procomú col·laboratiu”.

Aquesta és una afirmació contundent i Rifkin l’argumenta parlant de tecnologies disruptives que avui ja han arribat, o són a punt d’arribar, al gran públic. Per exemple les impressores 3D, però també les plaques Raspberry Pi (i no les esmenta, però ho faig jo: les plaques Arduino) o l’energia solar fotovoltaica barata. Sobre la fotovoltaica barata és interessant fer un cop d’ull a aquest MOOC de Coursera, per la Universitat Tècnica de Dinamarca: Organic Solar Cell. Theory and Practice (mireu http://plasticphotovoltaics.org/) Per cert, que el concepte MOOC també és citat com un dels factors disruptius d’aquesta revolució que ve.

Molt engrescador. Algú dirà, però, que el capitalisme té una mala salut de ferro i que són molts els que al llarg de la història l’han donat per mort… i que tal dia farà un any. Cert. Per mi, aquest excitant llibre de Rifkin cal complementar-lo amb la lectura d’un altre llibre important: “Why nations fail”, del que n’he parlat al meu blog personal. De la lectura dels dos llibres, hom pot preveure que aquesta revolució no serà sense tibantors i que, potser, en algun moment ens trobarem quedisposar d’una impressora 3D a casa serà quelcom de subversiu.

En definitiva, els actors i les tecnologies són a punt, o gairebé. És segur que d’aquí 20 anys el món serà absolutament diferent de com és avui. No cal ser cap vident: el món de 1995 era completament diferent del d’avui. Internet només era accessible des de les universitats (en aquella època jo treballava a l’Escola Universitària de Mataró, actualment Escola Superior Politècnica Tecnocampus)  i teníem un accés incipient i reduït a la Xarxa); avui, en canvi, és possible fer videoconferència des del mòbil (al 95 jo ni tenia mòbil!). Per no parlar dels canvis socials i polítics que s’han produït des d’aleshores.

Com serà el món de les properes dues dècades? qui ho sap, però hi han  paraules i conceptes claus que avui cal tenir en compte: maker, FabLab (i Fablab BCN), Arduino, Raspberry, MOOC (i [1],[2],[3]), Internet of Things, Smart Cities, Smart Grids, Big Data, Open data, Renovables, Organic Photovoltaic, Biotecnologia, Bitcoin… i també democràcia, autogestió, cooperatives, identitats…

En fi, enllaço un parell de vídeos amb Jeremy Rifkin parlant d’aquesta nova societat del cost marginal zero. El primer correspon a la conferència de Rifkin dins de les Talks at Google:

I aquesta altre, a la realitzada a la llibreria Politics & Prose Bookstore de Washington.

.

Per rumiar… però potser arriba l’hora de passar a l’acció.