El poderoso quicklisp

Este programa permite descargar otros programas hechos en lisp directamente desde tu consola, para poder utilizar y agregar otras funcionalidades a tu implementación de lisp sin mucho esfuerzo.
Antes que nada hay que descargar quicklisp.lisp

Ahora debes cargarlo en la consola, cargalo donde has guardado el archivo, o desde tu carpeta de descargas:

> (load ".../.../quicklisp.lisp")

Genial!!!. Ahora hay que instalarlo:

> (quicklisp-quickstart:install)

Para que se cargue siempre, cada vez que se inicia tu lisp:

> (ql:add-to-init-file)

Pues, de otro modo, para volver a usarlo, tendrías que cargar el setup.lisp, desde el directorio de instalación, haciendo:

> (load "c:/users/pc hogar/quicklisp/setup.lisp") ;;el nombre de usuario depende de cada pc, el mio es pc hogar!!!

Probemos un ejemplo concreto, deseo descargar un programa que reproduzca sonidos en lisp, que se llama "harmony". Hago:

> (ql:quickload :harmony-simple)

El codigo de Beale

No se para que me meti en este tema, lo dejo como curiosidad. La historia de los papeles de Beale aparecen en innumerables sitios y videos sobre misterios y otras yerbas. Asi que no voy a ocuparme demasiado en la historia. De manera resumida: un tipo que se llamaba Thomas Jefferson Beale le deja al dueño de una posada tres codigos cifrados que contienen: una carta (el numero 2), la supuesta ubicacion de un millonario tesoro (el numero 1), dentro de la ciudad de Virginia; y los nombres de los dueños del tesoro y sus domicilios. Un tipo que se quedo con los codigos descifro el papel numero 2, (la carta) usando la declaracion de independencia de los EE.UU. Usa los numeros como las ubicaciones de las palabras dentro del texto de la declaracion de independencia, de las cuales toma la primera letra para formar el mensaje. (De una usa la ultima, para formar la "Y", pues ninguna de las palabras comienza con esta letra). Por ejemplo los primeros numeros 115 73 24 807 37 corresponde con palabras que comienzan respectivamente con I H A V E. Aunque por alguna razon la V no coincide con la ubicacion que da, si miramos el texto esa letra es la I. Tal vez se equivocó en la cuenta, o la declaracion original "el manuscrito que él tenia a la mano" varió con el que tenemos aqui. (Observe aquel lector instruido en el tema, que el primero que firma la declaracion de independencia de los EE.UU. es Thomas Jefferson y quien deja los codigos numericos se llama "Thomas Jefferson" Beale.)

El texto dice:

I have deposited in the county of Bedford, about four miles from Buford's, in an excavation or vault, six feet below the surface of the ground, the following articles, belonging jointly to the parties whose names are given in number "3," herewith:

The first deposit consisted of one thousand and fourteen pounds of gold, and three thousand eight hundred and twelve pounds of silver, deposited November, 1819. The second was made December, 1821, and consisted of nineteen hundred and seven pounds of gold, and twelve hundred and eighty-eight pounds of silver; also jewels, obtained in St. Louis in exchange for silver to save transportation, and valued at $13,000.

The above is securely packed in iron pots, with iron covers. The vault is roughly lined with stone, and the vessels rest on solid stone, and are covered with others. Paper number "1" describes the exact locality of the vault so that no difficulty will be had in finding it.

Pero como dice mas arriba, pasando por el programa que descifra no queda exactamente asi, pero peor es nada. Ademas el texto decodificado sale sin espacios, por lo que deberías ir formando las palabras.

El problema es que nadie pudo nunca descifrar los otros dos codigos, la ubicación del tesoro y los nombres y ubicaciones de sus dueños. No se ha encontrado el texto "llave", que podría ser cualquiera, o no se ha tenido la suficiente inteligencia como para descifrarlo. Aclaro que el misterio lleva cientos de años y nadie nunca lo ha podido resolver.

Basta ya de cháchara. Yo quería nada mas mostrar como descifraría el codigo en lisp, teniendo como datos la declaración de independencia INDEPENDENCE y la carta LETTER. Tambien figuran los otros dos códigos, la ubicación del tesoro LOCALITY, y los nombres y direcciones de sus dueños NAMES. Lamentablemente no se como descifrar los dos últimos, dejo el programa como simple curiosidad. Si quiere mas información al respecto, consulte la pagina:

http://www.unmuseum.org/bealepap.htm

El programa completo esta abajo. Una vez cargado el programa con (load ...), se puede decodificar el texto con:

> (decode-all letter independence)

;;DECLARATION OF INDEPENDENCE

(setf independence '(When  in  the  course  of  human  events  it  becomes  necessary  for  one  people  to   

dissolve  the  political  bands  which  have  connected  them  with  another  and  to   

assume  among  the  powers  of  the  earth  the  separate  and   equal   station   to   

which   the   laws   of   nature   and   of   nature´s   god   entitle   them   a   decent  

respect   to   the   opinions   of   mankind   requires   that   they   should   declare   the   

causes   which   impel   them   to   the   separation   we   hold   these   truths   to   be   

self   evident   that   all   men   are   created   equal   that   they   are   endowed   by   

their   creator   with   certain   unalienable   rights   that   among   these   are   life   

liberty   and   the   pursuit   of   happiness   that   to   secure   these   rights   

governments   are   instituted   among   men   deriving   their   just   powers   from   

the   consent   of   the   governed   that   whenever   any   form   of   government   

becomes   destructive   of   these   ends   it   is   the   right   of   the   people   

to   alter   or   to   abolish   it   and   to   institute   new   government   laying   

its   foundation   on   such   principles   and   organizing   its   powers   in   such   

form   as   to   them   shall   seem   most   likely   to   effect   their   safety   

and   happiness   prudence   indeed   will   dictate   that   governments   long   established   

should   not   be   changed   for   light   and   transient   causes   and   accordingly   

all   experience   hath   shown   that   mankind   are   more   disposed   to   suffer   

while   evils   are   sufferable   than   to   right   themselves   by   abolishing   the   

forms   to   which   they   are   accustomed   but   when   a   long   train   of   

abuses   and   usurpations   pursuing   invariably   the   same   object   evinces   a   

design   to   reduce   them   under   absolute   despotism   it   is   their   right   

it   is   their   duty   to   throw   off   such   government   and   to   provide   

new   guards   for   their   future   security   such   has   been   the   patient   

sufferance   of   these   colonies   and   such   is   now   the   necessity   which   

constrains   them   to   alter   their   former   systems   of   government   the   

history   of   the   present   king   of   great   Britain   is   a   history   of   

repeated   injuries   and   usurpations   all   having   in   direct   object   the   

establishment   of   an   absolute   tyranny   over   these   states   to   prove   

this   let   facts   be   submitted   to   a   candid   world   he   has   refused   

his   assent   to   laws   the   most   wholesome   and   necessary   for   the   

public   good   he   has   forbidden   his   governors   to   pass   laws   of  

immediate   and   pressing   importance   unless   suspended   in   their   operation  

till   his   assent   should   be   obtained   and   when   so   suspended   he   

has   utterly   neglected   to   attend   to   them   he   has   refused   to   

pass   other   laws   for   the   accommodation   of   large   districts   of  

people   unless   those   people   would   relinquish   the   right   of   representation   

in   the   legislature   a   right   inestimable   to   them   and   formidable   to   

tyrants   only   he   has   called   together   legislative   bodies   at   places   

unusual   uncomfortable   and   distant   from   the   depository   of   their   public   

records   for   the   sole   purpose   of   fatiguing   them   into   compliance   with   

his   measures   he   has   dissolved   representative   houses   repeatedly   for   opposing   

with   manly   firmness   his   invasions   on   the   rights   of   the   people   he   

has   refused   for   a   long   time   after   such   dissolutions   to   cause   others   

to   be   elected   whereby   the   legislative   powers   incapable   of   annihilation   

have   returned   to   the   people   at   large   for   their   exercise   the   state   

remaining   in   the   meantime   exposed   to   all   the   dangers   of   invasion   from   

without   and   convulsions   within   he   has   endeavored   to   prevent   the   population   

of   these   states   for   that   purpose   obstructing   the   laws   for   naturalization   

of   foreigners   refusing   to   pass   others   to   encourage   their   migration   hither   

and   raising   the   conditions   of   new   appropriations   of   lands   he   has   

obstructed   the   administration   of   justice   by   refusing   his   assent   to   laws   

for   establishing   judiciary   powers   he   has   made   judges   dependent   on   his   

will   alone   for   the   tenure   of   their   offices   and   the   amount   and  

payment   of   their   salaries   he   has   erected   a   multitude   of   new   offices   

and   sent   hither   swarms   of   officers   to   harass   our   people   and   eat   

out   their   substance   he   has   kept   among   us   in   times   of   peace  

standing   armies   without   the   consent   of   our   legislatures   he   has   affected   

to   render   the   military   independent   of   and   superior   to   the   civil   

power   he   has   combined   with   others   to   subject   us   to   a   jurisdiction   

foreign   to   our   constitution   and   unacknowledged   by   our   laws   giving   his   

assent   to   their   acts   of   pretended   legislation   for   quartering   large   bodies   

of   armed   troops   among   us   for   protecting   them   by   a   mock   trial   

from   punishment   for   any   murders   which   they   should   commit   on   the   

inhabitants   of   these   states   for   cutting   off   our   trade   with   all   

parts   of   the   world   for   imposing   taxes   on   us   without   our   consent   

for   depriving   us   in   many   cases   of   the   benefits   of   trial   by   jury   

for   transporting   us   beyond   seas   to   be   tried   for   pretended   offenses   for   

abolishing   the   free   system   of   English   laws   in   a   neighboring   province   

establishing   therein   an   arbitrary   government   and   enlarging   its   boundaries   so   

as   to   render   it   at   once   an   example   and   fit   instrument   for   

introducing   the   same   absolute   rule   into   these   colonies   for   taking   away   

our   charters   abolishing   our   most   valuable   laws   and   altering   fundamentally   

the   forms   of   our   governments   for   suspending   our   own   legislature   and   

declaring   themselves   invested   with   power   to   legislate   for   us   in   all   

cases   whatsoever   he   has   abdicated   government   here   by   declaring   us   out   

of   his   protection   and   waging   war   against   us   he   has   plundered   our   

seas   ravaged   our   coasts   burnt   our   towns   and   destroyed   the   lives   of   

our   people   he   is   at   this   time   transporting   large   armies   of   foreign   

mercenaries   to   complete   the   works   of   death   desolation   and   tyranny   

already   begun   with   circumstances   of   cruelty   and &    perfidy   scarcely   

paralleled   in   the   most   barbarous   ages   and   totally   unworthy   the   head   

of   a   civilized   nation   he   has   constrained   our   fellow   citizens   taken   

captive   on   the   high   seas   to   bear   arms   against   their   country   to   

become   the   executioners   of   their   friends   and   brethren   or   to   fall  

themselves   by   their   hands   he   has   excited   domestic   insurrections   amongst   

us   and   has   endeavored   to   bring   on   the   inhabitants   of   our   frontiers   

the   merciless   Indian   savages   whose   known   rule   of   warfare   is   an  

undistinguished   destruction   of   all   ages   sexes   and   conditions   in   every   

stage   of   these   oppressions   we   have   petitioned   for   redress   in   

the   most   humble   terms   our   repeated   petitions   have   been   answered   

only   by   repeated   injury   a   prince   whole   character   is   thus  

marked   by   every   act   which   may   define   a   tyrant   is   unfit   

to   be   the   ruler   of   a   free   people   nor   have   we   been   

wanting   in   attention   to   our   British   brethren   we   have   warned  

them   from   time   to   time   of   attempts   by   their   legislature   to   

extend   an   unwarrantable   jurisdiction   over   us   we   have   reminded   them   

of   the   circumstances   of   our   emigration   and   settlement   here   we  

have   appealed   to   their   native   justice   and   magnanimity   and   we   

have   conjured   them   by   the   ties   of   our   common   kindred   to   

disavow   these   usurpations   which   would   inevitably   interrupt   our  

connections   and   correspondence   they   too   have   been   deaf   to   

the   voice   of   justice   and   of   consanguinity   we   must   therefore   

acquiesce   in   the   necessity   which   denounces   our   separation   and  

hold   them   as   we   hold   the   rest   of   mankind   enemies   in   

war   in   peace   friends   we   therefore   the   representatives   of   the   

united   states   of   America   in   general   congress   assembled   appealing  

to   the   supreme   judge   of   the   world   for   the   rectitude   of   

our   intentions   do   in   the   name   and   by   authority   of   the   

good   people   of   these   colonies   solemnly   publish   and   declare   that   

these   united   colonies   are   and   of   right   ought   to   be   free   

and   independent   states   that   they   are   absolved   from   all   allegiance   

to   the   British   crown   and   that   all   political   connection   between  

them   and   the   state   of   great   Britain   is   and   ought   to  

be   totally   dissolved   and   that   as   free   and   independent   states   

they   have   full   power   to   levy   war   conclude   peace   contract  

alliances   establish   commerce   and   to   do   all   other   acts   and   

things   which   independent   states   may   of   right   do   and   for  

the   support   of   this   declaration   with   a   firm   reliance   on   

the   protection   of   divine   providence   we   mutually   pledge   to  ))

;;paper 2:

;;LETTER.

(setf letter '(115 73 24 807 37 52 49 17 31 62 647 22 7 15 140 47 29 107 79 84 56 239 10 26 811 5 196 308 85 52 160 136 59 

211 36 9 46 316 554 122 106 95 53 58 2 42 7 35 122 53 31 82 77 250 196 56 96 118 71 140 287 28 353 37 1005 

65 147 807 24 3 8 12 47 43 59 807 45 316 101 41 78 154 1005 122 138 191 16 77 49 102 57 72 34 73 85 35 371 

59 196 81 92 191 106 273 60 394 620 270 220 106 388 287 63 3 6 191 122 43 234 400 106 290 314 47 48 81 96 

26 115 92 158 191 110 77 85 197 46 10 113 140 353 48 120 106 2 607 61 420 811 29 125 14 20 37 105 28 248 16 

159 7 35 19 301 125 110 486 287 98 117 511 62 51 220 37 113 140 807 138 540 8 44 287 388 117 18 79 344 34 

20 59 511 548 107 603 220 7 66 154 41 20 50 6 575 122 154 248 110 61 52 33 30 5 38 8 14 84 57 540 217 115 

71 29 84 63 43 131 29 138 47 73 239 540 52 53 79 118 51 44 63 196 12 239 112 3 49 79 353 105 56 371 557 211 

505 125 360 133 143 101 15 284 540 252 14 205 140 344 26 811 138 115 48 73 34 205 316 607 63 220 7 52 150 44 

52 16 40 37 158 807 37 121 12 95 10 15 35 12 131 62 115 102 807 49 53 135 138 30 31 62 67 41 85 63 10 106 807 

138 8 113 20 32 33 37 353 287 140 47 85 50 37 49 47 64 6 7 71 33 4 43 47 63 1 27 600 208 230 15 191 246 85 94 

511 2 270 20 39 7 33 44 22 40 7 10 3 811 106 44 486 230 353 211 200 31 10 38 140 297 61 603 320 302 666 287 2 

44 33 32 511 548 10 6 250 557 246 53 37 52 83 47 320 38 33 807 7 44 30 31 250 10 15 35 106 160 113 31 102 406 

230 540 320 29 66 33 101 807 138 301 316 353 320 220 37 52 28 540 320 33 8 48 107 50 811 7 2 113 73 16 125 11 

110 67 102 807 33 59 81 158 38 43 581 138 19 85 400 38 43 77 14 27 8 47 138 63 140 44 35 22 177 106 250 314 217 

2 10 7 1005 4 20 25 44 48 7 26 46 110 230 807 191 34 112 147 44 110 121 125 96 41 51 50 140 56 47 152 540 63 807 

28 42 250 138 582 98 643 32 107 140 112 26 85 138 540 53 20 125 371 38 36 10 52 118 136 102 420 150 112 71 14 20 

7 24 18 12 807 37 67 110 62 33 21 95 220 511 102 811 30 83 84 305 620 15 2 10 8 220 106 353 105 106 60 275 72 8 

50 205 185 112 125 540 65 106 807 138 96 110 16 73 33 807 150 409 400 50 154 285 96 106 316 270 205 101 811 400 

8 44 37 52 40 241 34 205 38 16 46 47 85 24 44 15 64 73 138 807 85 78 110 33 420 505 53 37 38 22 31 10 110 106 101 

140 15 38 3 5 44 7 98 287 135 150 96 33 84 125 807 191 96 511 118 40 370 643 466 106 41 107 603 220 275 30 150 

105 49 53 287 250 208 134 7 53 12 47 85 63 138 110 21 112 140 485 486 505 14 73 84 575 1005 150 200 16 42 5 4 25 

42 8 16 811 125 160 32 205 603 807 81 96 405 41 600 136 14 20 28 26 353 302 246 8 131 160 140 84 440 42 16 811 

40 67 101 102 194 138 205 51 63 241 540 122 8 10 63 140 47 48 140 288))

;;paper 1:

;;THE LOCALITY OF THE VAULT.

(setf locality '(71 194 38 1701 89 76 11 83 1629 48 94 63 132 16 111 95 84 341 975 14 40 64 27 81 139 213 63 90 1120 8 15 3 

126 2018 40 74 758 485 604 230 436 664 582 150 251 284 308 231 124 211 486 225 401 370 11 101 305 139 189 17 

33 88 208 193 145 1 94 73 416 918 263 28 500 538 356 117 136 219 27 176 130 10 460 25 485 18 436 65 84 200 

283 118 320 138 36 416 280 15 71 224 961 44 16 401 39 88 61 304 12 21 24 283 134 92 63 246 486 682 7 219 184 

360 780 18 64 463 474 131 160 79 73 440 95 18 64 581 34 69 128 367 460 17 81 12 103 820 62 116 97 103 862 70 60 

1317 471 540 208 121 890 346 36 150 59 568 614 13 120 63 219 812 2160 1780 99 35 18 21 136 872 15 28 170 88 4 

30 44 112 18 147 436 195 320 37 122 113 6 140 8 120 305 42 58 461 44 106 301 13 408 680 93 86 116 530 82 568 9 

102 38 416 89 71 216 728 965 818 2 38 121 195 14 326 148 234 18 55 131 234 361 824 5 81 623 48 961 19 26 33 10 

1101 365 92 88 181 275 346 201 206 86 36 219 324 829 840 64 326 19 48 122 85 216 284 919 861 326 985 233 64 68 

232 431 960 50 29 81 216 321 603 14 612 81 360 36 51 62 194 78 60 200 314 676 112 4 28 18 61 136 247 819 921 

1060 464 895 10 6 66 119 38 41 49 602 423 962 302 294 875 78 14 23 111 109 62 31 501 823 216 280 34 24 150 

1000 162 286 19 21 17 340 19 242 31 86 234 140 607 115 33 191 67 104 86 52 88 16 80 121 67 95 122 216 548 96 

11 201 77 364 218 65 667 890 236 154 211 10 98 34 119 56 216 119 71 218 1164 1496 1817 51 39 210 36 3 19 540 

232 22 141 617 84 290 80 46 207 411 150 29 38 46 172 85 194 39 261 543 897 624 18 212 416 127 931 19 4 63 96 12 

101 418 16 140 230 460 538 19 27 88 612 1431 90 716 275 74 83 11 426 89 72 84 1300 1706 814 221 132 40 102 34 

868 975 1101 84 16 79 23 16 81 122 324 403 912 227 936 447 55 86 34 43 212 107 96 314 264 1065 323 428 601 203 

124 95 216 814 2906 654 820 2 301 112 176 213 71 87 96 202 35 10 2 41 17 84 221 736 820 214 11 60 760))

;;paper 3:

;;NAMES AND RESIDENCES.

(setf names '(317 8 92 73 112 89 67 318 28 96 107 41 631 78 146 397 118 98 114 246 348 116 74 88 12 65 32 14 81 19 76 121 216 

85 33 66 15 108 68 77 43 24 122 96 117 36 211 301 15 44 11 46 89 18 136 68 317 28 90 82 304 71 43 221 198 176 

310 319 81 99 264 380 56 37 319 2 44 53 28 44 75 98 102 37 85 107 117 64 88 136 48 151 99 175 89 315 326 78 96 

214 218 311 43 89 51 90 75 128 96 33 28 103 84 65 26 41 246 84 270 98 116 32 59 74 66 69 240 15 8 121 20 77 89 

31 11 106 81 191 224 328 18 75 52 82 117 201 39 23 217 27 21 84 35 54 109 128 49 77 88 1 81 217 64 55 83 116 251 

269 311 96 54 32 120 18 132 102 219 211 84 150 219 275 312 64 10 106 87 75 47 21 29 37 81 44 18 126 115 132 160 

181 203 76 81 299 314 337 351 96 11 28 97 318 238 106 24 93 3 19 17 26 60 73 88 14 126 138 234 286 297 321 365 

264 19 22 84 56 107 98 123 111 214 136 7 33 45 40 13 28 46 42 107 196 227 344 198 203 247 116 19 8 212 230 31 6 

328 65 48 52 59 41 122 33 117 11 18 25 71 36 45 83 76 89 92 31 65 70 83 96 27 33 44 50 61 24 112 136 149 176 180 

194 143 171 205 296 87 12 44 51 89 98 34 41 208 173 66 9 35 16 95 8 113 175 90 56 203 19 177 183 206 157 200 218 

260 291 305 618 951 320 18 124 78 65 19 32 124 48 53 57 84 96 207 244 66 82 119 71 11 86 77 213 54 82 316 245 303 

86 97 106 212 18 37 15 81 89 16 7 81 39 96 14 43 216 118 29 55 109 136 172 213 64 8 227 304 611 221 364 819 375 

128 296 1 18 53 76 10 15 23 19 71 84 120 134 66 73 89 96 230 48 77 26 101 127 936 218 439 178 171 61 226 313 215 

102 18 167 262 114 218 66 59 48 27 19 13 82 48 162 119 34 127 139 34 128 129 74 63 120 11 54 61 73 92 180 66 75 

101 124 265 89 96 126 274 896 917 434 461 235 890 312 413 328 381 96 105 217 66 118 22 77 64 42 12 7 55 24 83 67 

97 109 121 135 181 203 219 228 256 21 34 77 319 374 382 675 684 717 864 203 4 18 92 16 63 82 22 46 55 69 74 112 

134 186 175 119 213 416 312 343 264 119 186 218 343 417 845 951 124 209 49 617 856 924 936 72 19 28 11 35 42 40 

66 85 94 112 65 82 115 119 236 244 186 172 112 85 6 56 38 44 85 72 32 47 63 96 124 217 314 319 221 644 817 821 

934 922 416 975 10 22 18 46 137 181 101 39 86 103 116 138 164 212 218 296 815 380 412 460 495 675 820 952))

;;Decodificacion:

;;Deberia mostrar el texto en ingles claramente (pero sin espacios), pero hay un problema

;;Beale al codificar su mensaje de la Declaración de Independencia, 

;;contó incorrectamente por lo tanto, ahi esta el problema. 

;;la letra "V" NO concuerda con el número 807, por ejemplo

;;Lamentablemente conto mal el babieca de beale, 807 es 818 y hay que sumar 11, pero no se

;;desde donde exactamente, asumo que desde el 490 inclusive. Para colmo no se sabe cuantas 

;;veces se equivoco en la cuenta.

;;Entonces hay que cambiar la funcion decode-num, veamos:

(defun decode-num (numero texto-llave)

   "Busca primera letra que corresponde con la posicion dentro del texto llave y la devuelve"

   (decf numero);; decremento porque el indice empieza en cero

   ;;-------------------------------------------------------------------------------------

   ;;AJUSTES: se equivoco en la cuenta o la declaracion de indepencia original vario con el tiempo

   ;; faltan mas ajustes...

   (when (> numero 490) (setf numero (+ numero 10)))

   (when (> numero 800) (setf numero (+ numero 1)))

   (when (and (> numero 150)

              (< numero 250) (setf numero (- numero 1))))

   ;;-------------------------------------------------------------------------------------

   ;;encuentra simbolo segun posicion   

   (setf simbolo (nth numero texto-llave))

   (setf c (char (symbol-name simbolo) 0)) ;halla caracter

   (when (= numero 821) (setf c (char (symbol-name simbolo) (- (length (symbol-name simbolo)) 1)))) ;el caracter es el ultimo

   (setf s (string c))         ;lo pasa a string  

   s)

(defun decode-all(codigo texto-llave)

   "decodifica todo el codigo numerico segun texto-llave"

   (setf texto (mapcar #'(lambda (numero) (decode-num numero texto-llave)) codigo))

   (setf texto (unir-cadenas texto))   

   texto)

(defun unir-cadenas(lista-cad)

   "concatena todas las cadenas de una lista"

   (setf result "")

   (dolist (item lista-cad)

(setf result (concatenate 'string result item)))

   result)

;;(decode-all letter independence)

Inteligencia Artificial. Eliza: Dialogo con una máquina

Nota del T: Sigo traduciendo el libro de Peter Norvig. Son complicadas algunas funciones, le aconsejo que las vaya construyendo a medida que lee. Si hay problemas con alguna traducción les ruego me avisen.

Acá dejo el programa completo: ELIZA.lisp

Este capítulo y el resto de la parte 1 examina tres programas más de IA bien conocidos de la década de 1960. Eliza mantiene una conversación con el usuario en la que es simulada una psicóloga. STUDENT resuelve problemas de los que son encontrados en los libros de álgebra, y MACSYMA resuelve una variedad de problemas matemáticos, incluyendo cálculo diferencial e integral. Desarrollaremos versiones de los primeros dos programas que duplican la mayoría de las características esenciales, pero para el tercero implementaremos solo una pequeña parte de las capacidades del programa original.

Los tres programas usan una técnica llamada “coincidencia de patrones”. La parte 1 sirve para mostrar la versatilidad –y también las limitaciones- de esta técnica.

De los tres programas, los primeros dos procesos introducen un Español plano, y los últimos dos resuelven problemas no triviales de matemática, de esta manera hay algunas bases para describirlos como “inteligentes”. Por otro lado, veremos que esta inteligencia es por lejos una ilusión, y que Eliza en particular fue diseñada para demostrar esta ilusión, no para ser un programa “serio” de IA.

ELIZA fue uno de los primeros programas que tenía al idioma Inglés como salida tanto así como en la entrada. El programa fue llamado después la heroína de Pygmalion, que fue enseñada para hablar Inglés correctamente a través de un dedicado profesor. El principal desarrollador de ELIZA fue el profesor Joseph Weizenbaum del MIT, publicada en el documento sobre ELIZA en Enero del 1966 para el problema de la comunicación entre máquinas de cómputo. La introducción a ese documento es reproducida enteramente aquí:

Se dice que explicar algo es explicarlo en profundidad. Esta máxima está aquí para mostrar como es el área de programación de ordenadores, especialmente en lo que se concierne a programación heurística e inteligencia artificial. En estos dominios las maquinas son hechas para comportarse de maneras maravillosas, obteniendo suficiente para deslumbrar incluso a la mayoría de los observadores experimentados. Pero una vez que un programa particular es desenmascarado, una vez que el trabajo interno es explicado en un lenguaje suficientemente plano para inducir a la comprensión, su magia se desmorona, su puesto es revelado como una mera colección de procedimientos, cada uno de los cuales es comprensible. El observador se dice a si mismo, “Yo podría haber escrito eso”. Con ese pensamiento el mueve el programa en cuestión del estante marcado como “inteligente”, al de las curiosidades, encajando en la discusión solo con personas menos ilustradas que él.

El objeto de este documento es causar solo una re-evaluación del programa a ser “explicado”. Pocos programas necesitan eso.

Déjeme explicar el punto sobre que el objeto principal de este libro es causar que el lector se diga a sí mismo, “yo podría haber escrito eso”. Esta será la esperanza en algunos casos debido a que el lector haya ganado algo, y no solamente porque el programa en cuestión haya perdido su habilidad para deslumbrar.

Empecemos nuestra investigación sobre ELIZA mirando un ejemplo de diálogo desde el artículo de Weizenbaum. ELIZA fue diseñada para ser instruida por una variedad de guiones, o patrones de interacción. En efecto tiene varios guiones, incluyendo algunos en alemán y galés. Pero el único guión que fue usado para cualquier extensión fue en inglés, y esto hace ELIZA emular un psicoanalista Rogeriano. Los Rogerianos no tienen “directivas” – ellos intentan dejar al paciente que se revele a sí mismo. Este es un guion sencillo de seguir para ELIZA, porque este encierra el hecho de estar pasivo y reaccionar, antes que voluntariamente generar nueva información. En el listado siguiente, la entrada del usuario está en oraciones, tanto en mayúsculas como minúsculas, y ELIZA responde solo en mayúsculas:

Los hombres son todos iguales.

EN QUE SENTIDO

Ellos están siempre fastidiándonos sobre una cosa u otra.

PUEDES SER MAS ESPECIFICA

Bueno, mi novio me hizo venir aquí.

TU NOVIO TE HIZO VENIR AQUÍ

El me dice que estoy deprimida a menudo.

ME APENA ESCUCHAR QUE ESTES DEPRIMIDA

Es verdad. No soy feliz.

PIENSAS VENIR AQUÍ PARA QUE TE AYUDE A SER FELIZ.

Necesito alguna ayuda, eso me parece.

QUE PASARIA SI TE OFREZCO ALGUNA AYUDA

Tal vez aprendería a llevarme bien con mi madre.

HABLAME MAS ACERCA DE TU FAMILIA

Esto parece impresionante; el programa está respondiendo razonablemente a una variedad de entradas y muestra una verdadera “comprensión”. Pero, como explica Weizenbaum, esta apariencia es una ilusión, y el programa ha reducido la difícil tarea de comprender a través de un cuidadoso reconocimiento, transformando, y haciendo eco de las piezas de entrada. El procedimiento es observar patrones específicos, basados en una palabra clave o palabras en la entrada. Por ejemplo, siempre que el programa aparece la palabra “iguales” o “mismo”, esta escribe un mensaje en pantalla respondiendo sobre cosas que son semejantes, en este caso “EN QUE SENTIDO”. Otros patrones son más complicados. Cerca del último intercambio, ELIZA arroja lejos todo lo que esta después de la coma, y luego usa un patrón que mira las entradas de la forma “necesito X” y lo transforma en la salida “Que pasaría si te ofrezco X”, donde X es la frase “alguna ayuda” en este caso. La gran ventaja de este enfoque es que la respuesta se hará en base a una variedad de entradas: “necesito vacaciones” y se obtendrá “Que pasaría si te ofrezco vacaciones”. Esto ocurrirá automáticamente, sin tener que decirle al programa la diferencia entre “alguna ayuda” y “vacaciones”. La desventaja es que el programa algunas veces hará respuestas tontas: “necesito esto como un agujero en la cabeza” será respondido con “Que pasaría si te ofrezco esto como un agujero en la cabeza”. En efecto, el programa solo construye cualquier sentido en todo caso si recibe entradas desde alguien que construye sentido –y alguien que interpreta sus respuestas caritativamente. Cuando se le da “necesito gibble pliz zzq”, ELIZA replicaría “Que pasaría si te ofrezto gibble plix zzq”, sin ningún indicio de que algo está mal. Otro ejemplo del programa original ELIZA cuando mantiene una comunicación con otro programa PARRY, que fue escrito por el Dr. Kenneth Colby para simular un comportamiento paranoico. Parte de esa conversación sigue a continuación, con ELIZA nuevamente solo en mayúsculas y PARRY en oraciones, tanto en mayúsculas como minúsculas:

No entiendo tus motivaciones.

¿QUE NO ENTIENDES DE MIS MOTIVACIONES?

¿No debería ser yo?

¿POR QUE DICES ESO AHORA?

Así es la manera.

SUPONGA QUE LA MANERA NO FUERA ASI.

¿Así?

NO ESTOY SEGURA DE ENTENDERTE COMPLETAMENTE.

Insistes demasiado en las mismas preguntas.

¿QUE TE SUGIERE ESA SEMEJANZA?

No te entiendo.

¿QUE ES LO QUE DESEAS ENTENDER?

Esto sugiere que PARRY el vecino de ELIZA, tiene una comprensión profunda del diálogo. Cuando hay un humano que tiene la mayoría de la carga para llevar adelante la conversación, estos programas pueden ser convincentes, pero cuando el humano está fuera de la conversación, las debilidades del programa son reveladas.

Describiendo y especificando ELIZA

Ahora que tenemos una idea de lo que es ELIZA, podemos comenzar la descripción y especificación del programa, y eventualmente movernos hacia la implementación y el debugging. El algoritmo de ELIZA puede ser descrito simplemente como: (1) leer una entrada, (2) buscar un patrón que coincida con la entrada, (3) transformar la entrada en una respuesta, y (4) mostrar en pantalla la respuesta. Estos cuatro pasos son repetidos para cada entrada.

La especificación e implementación de los pasos (1) y (4) son triviales: para (1), usa la función interna read para leer una lista de palabras, y para (4) usa print para mostrar en pantalla la lista de palabras en la respuesta.

Por supuesto, hay algunos inconvenientes para esta especificación. El usuario tendrá que escribir una lista real –usando paréntesis- y el usuario no puede usar caracteres especiales para leer, tales como comillas, comas y períodos. Así nuestra entrada no puede estar sin restricciones tal como el dialogo del ejemplo, pero ese es un pequeño precio a pagar para la conveniencia de tener la mitad del problema resuelto.

Coincidencia de patrones

La parte difícil está en los pasos (2) y (3) –esta noción de coincidencia de patrones y transformación. Hay cuatro cosas relacionadas: un patrón general y la respuesta, y una entrada específica y la transformación de esa entrada. Desde que accedimos a representar las entradas como una lista, esto permite tratar a otros componentes como listas también. Por ejemplo, podemos tener:

Patrón: (necesito X)

Respuesta: (¿Qué pasaría si te ofrezco X?)

Entrada: (necesito vacaciones)

Transformación: (¿Qué pasaría si te ofrezco vacaciones?)

El programa de coincidencia de patrones debe hacer coincidir los literales i con i, necesito con necesito, y a con a, como así también hacer coincidir la variable X con vacaciones. Esto presupone que hay algunas maneras de decidir que X sea una variable y que necesito no lo es. Debemos arreglar el sustituto vacaciones para X con la respuesta, para obtener la transformación final.

Ignorando por un momento el problema de transformar el patrón en la respuesta,  podemos ver que esta noción de coincidencia de patrones es solo una generalización de la función Lisp equal. Primero mostramos la función simple-equal, que es como la función interna equal, y la función patron-coincide que es definida para manejar variables de coincidencia de patrones:

(defun simple-equal (x y)

  "¿Son x e y iguales? (No hace revision dentro de cadenas.)"

  (if (or (atom x) (atom y))

      (eql x y)

    (and (simple-equal (first x) (first y))

                 (simple-equal (rest x) (rest y)))))

(defun patron-coincide (patron entrada)

  "¿Hay coincidencia entre patron y entrada? Cualquier variable puede coincidir con cualquier cosa."

  (if (variable-p patron)

      t

    (if (or (atom patron) (atom entrada))

                (eql patron entrada)

      (and (patron-coincide (first patron) (first entrada))

                   (patron-coincide (rest patron) (rest entrada))))))

Antes de que podamos avanzar, necesitamos decidir sobre una implementación para las variables de patron-coincide. Podríamos, por instancia, decir que solo un cierto conjunto de símbolos, tales como {X,Y,Z} son variables. Alternativamente, podríamos definir una estructura de tipo de variable, pero entonces no tendríamos que escribir algo como (make-variable :name ‘X) cada vez que buscamos una. Otra opción podría ser el uso de símbolos, pero para distinguir variables de constantes por el nombre del símbolo.  Por ejemplo, en Prolog, las variables comienzan con letras mayúsculas y las constantes con minúsculas. Pero Common Lisp no es sensible al contexto, así que esto no funcionará. En lugar de ello, hay una tradición en los programas de IA basados en Lisp donde las variables son símbolos que comienzan el carácter de pregunta. Hasta aquí hemos repartido símbolos como átomos –objetos sin estructura interna. Pero las cosas son siempre más complicadas de lo que aparentan al principio y, tanto en Lisp así como en física, lo que provoca que incluso los átomos tengan componentes. En partículas, los símbolos tienen nombres, que son cadenas de caracteres y son accesibles a través de la función symbol-name. Las cadenas en cambio tienen elementos que son caracteres, accesibles a través de la función char. El carácter ‘7’ es denotado por la secuencia de auto-evaluación #\? De esta manera el predicado variable-p puede ser definido como sigue a continuación, y ahora tenemos un programa completo de patrón de coincidencias:

(defun variable-p (x)

  "¿x es una variable? (un simbolo que comienza con '?')"

  (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

> (patron-coincide '(necesito ?X) '(necesito vacaciones))

T

> (patron-coincide '(necesito ?X) '(realmente necesito vacaciones))

NIL

En cada caso obtenemos la respuesta correcta, pero no obtenemos ninguna indicación de lo que es  ?X, de esta manera no podríamos sustituirla dentro de la respuesta. Necesitamos modificar patron-coincide para que devuelva algún tipo de tabla de variables y sus correspondientes valores. En la construcción de esta opción, el programador experimentado en Common Lisp puede ganar algo de tiempo siendo oportunista: reconocer cuando hay una función existente que hará una gran parte de la tarea. Lo que buscamos es sustituir valores para variables a través de la respuesta. El programador atento haría referencia al índice de este libro o de un manual de referencia de Common Lisp y buscará las funciones substitute, subst y sublis. Todas estas sustituyen algunas expresiones nuevas por unas anteriores con una expresión. Sublis en cambio es la más apropiada porque es la única que nos permite hacer varias sustituciones al mismo tiempo. Sublis toma dos argumentos, el primero es una lista de pares anterior-nuevo, y el segundo es una expresión en la que hace las sustituciones. Para cada uno de los pares, el car es reemplazado por el cdr. En otras palabras, formaríamos cada par con algo como (cons anterior nuevo). (Así como una lista de pares es conocida como una lista de asociación, o a-list, debido a que esta asocia claves con valores. En términos del ejemplo abajo, usaríamos:

> (sublis '((?X . vacaciones))

                '(Que pasaría si te ofrezco  ?X ?))

(QUE PASARIA SI TE OFREZCO VACACIONES ?)

Nota: Quisiera poner el signo de pregunta ¿ de apertura, pero algunos interpretes no los tienen.

Ahora necesitamos arreglar nuestro patron-coincide para que devuelva una a-lisp, mejor que solo T para un resultado exitoso. Aquí tenemos un primer intento:

(defun patron-coincide (patron entrada)

  "¿Coincide el patron con la entrada? CUIDADO: versión con errores."

  (if (variable-p patron)

      (list (cons patron entrada))

    (if (or (atom patron) (atom entrada))

                (eql patron entrada)

      (append (patron-coincide (first patron) (first entrada))

                      (patron-coincide (rest patron) (rest entrada))))))

Esta implementación luce razonable: devuelve una a-list de un elemento si el patrón es una variable, y une las a-list si el patrón y la entrada son listas. Sin embargo, hay varios problemas. Primero, la verificación (eql patron entrada) puede devolver T, que no es una lista, de esta manera append se quejará. Segundo, el mismo test debe devolver nil, lo que indicaría una falla, pero este será tratado como una lista, y será unido al resto de la respuesta. Tercero, no podemos distinguir entre el caso donde el patron falla –y devuelve nil- contra el caso donde todo coincide, pero no hay variables, devolviendo una a-lista nula. (Este es el problema del semipredicado). Cuarto, queremos las uniones de variables para acceder –si ?X es usado dos veces en el patrón, no queremos hacer coincidir dos valores distintos en la entrada. Finalmente, patron-coincide es ineficiente para verificar tanto el primero como el resto de las listas, incluso cuando la primera parte correspondiente no coincide. (¿No es increíble que haya cinco errores en una función de siete líneas?)

Podemos resolver estos problemas aceptando dos convenciones. Primero, es más conveniente hacer que patron-coincide sea un verdadero predicado, de esta manera aceptamos que devuelve nil solo para indicar falla. Lo que ocurre es que necesitaremos un valor nil-anonimo para representar la lista vacía. Segundo, si estamos yendo hacia una consistencia de los valores de las variables, entonces el first tendrá que saber cuál es el rest. Podemos lograr esto pasando la lista de uniones como un tercer argumento para patron-coincide. Lo haremos como un argumento opcional, porque queremos poder decir simplemente (patron-coincide a b).

Para abstraer más allá de estas decisiones de implementación, definiremos las constantes falla y sin-uniones para representar los dos valores devueltos con problemas. La forma especial defconstant es usada para indicar que estos valores no cambiarán. (Es opcional tener nombres de variables que comienzan y terminan con asteriscos, pero esta convención usualmente no se usa para las constantes). El motivo es que los asteriscos gritan, “Cuidado! Puedo ser cambiado por algo fuera de este alcance léxico”. Las constantes, por supuesto, no pueden ser cambiadas.

(defconstant falla nil "Indica que patron-coincide falla")

(defconstant sin-uniones '((t . t))

  "Indica el éxito de patron-coincide, sin variables.")

Luego, abstraemos más alla con el uso de assoc, introduciendo las siguientes cuatro funciones:

(defun obtener-union(var uniones)

  "Busca un par (variable . valor) en una lista de uniones."

(assoc var uniones))

(defun union-val(union)

  "Obtiene el valor de una union."

  (cdr union))

(defun buscar(var uniones)

  "Obtiene el valor (para var) de una lista de uniones."

  (union-val (obtener-union var uniones)))

(defun extender-uniones (var valor uniones)

  "Agrega un par (var . valor) a una lista de uniones."

  (cons (cons var valor) uniones))

Ahora que las variables y las uniones están definidas, patron-coincide es fácil. Este consiste de cinco casos. Primero, si la lista de uniones es falla, entonces la coincidencia falla (debido a que algunas coincidencias previas deben haber fallado). Si el patrón es una sola variable, entonces la coincidencia devuelve lo que sea que coincida con la variable; ya sea la lista de uniones existente, una extendida, o falla. Luego, tanto el patron como la entrada son listas, primero llamaremos a patron-coincide recursivamente sobre el primer elemento de cada lista. Este devuelve una lista de uniones (o falla), la que usaremos para hacer coincidir con el resto de las listas. Este es el único caso que invoca a una función no trivial, asi que es una buena idea probar informalmente que la función terminará: cada una de las dos llamadas recursivas redice el tamaño tanto del patron como de la entrada, y patron-coincide verifica el caso de patrones atómicos y entradas, de esta manera la función como un todo debe devolver eventualmente una respuesta (a menos que patrón y entrada tengan un tamaño infinito). Si ninguno de estos cuatro casos ocurre, entonces la coincidencia falla.

(defun patron-coincide (patron entrada &optional (uniones sin-uniones))

  "Coincidencia de patrones preparando la entrada en el contexto de las uniones"

  (cond ((eq uniones falla) falla)

                ((variable-p patron)

                 (coincidir-variable patron entrada uniones))

                ((eql patron entrada) uniones)

                ((and (consp patron) (consp entrada))

                 (patron-coincide (rest patron) (rest entrada)

                                                 (patron-coincide (first patron) (first entrada)

                                                                                 uniones)))

                (t falla)))

 

(defun coincidir-variable (var entrada uniones)

  "Coincide VAR con entrada? Usa (o actualiza) y devuelve las uniones."

  (let ((union (obtener-union var uniones)))

    (cond ((not union) (extender-uniones var entrada uniones))

                  ((equal entrada (union-val union)) uniones)

                  (t falla))))

Ahora podemos probar patron-coincide y ver cómo trabaja:

> (patron-coincide '(necesito ?X) '(necesito vacaciones))

((?X . VACACIONES) (T . T))

La respuesta es una lista de uniones de variable que esta dotadas de notación de pares; cada elemento de la lista es una par (variable . valor). (T . T) es un residuo de sin-uniones. Esto no hace daño realmente, pero podemos eliminarlo haciendo extender-uniones un poco más complicada:

(defun extender-uniones(var valor uniones)

  "Agrega un par (var . value) a la lista de uniones."

  (cons (cons var valor)

                ;; Una ver que agregamos una union "real",

                ;; podemos eliminar el tonto sin-uniones

                (if (eq uniones sin-uniones)

                    nil

                  uniones)))

> (sublis (patron-coincide '(necesito ?X) '(necesito vacaciones))

'(que pasaria si te ofrezco ?X ?))

(QUE PASARIA SI TE OFREZCO VACACIONES ?)

> (patron-coincide '(necesito ?X) '(realmente necesito vacaciones))

NIL

> (patron-coincide '(esto es facil) '(esto es facil) )

((T. T))

> (patron-coincide '(?X es ?X) '((2 + 2) es 4))

NIL

> (patron-coincide '(?X es ?X) '((2 + 2) es (2 + 2)))

((?X 2 + 2))

> (patron-coincide '(?P necesito . ?X)  '(yo necesito unas largas vacaciones))

((?X UNAS LARGAS VACACIONES) (?P . YO))

Nota del T: El problema con el español es que las conjugaciones del verbo dependen de persona y numero.

Note la distinción entre NIL y ( (T . T) ). El último tratamiento es exitoso, pero no hubieron uniones para devolver. Recuerde también que (?X 2 + 2) es lo mismo que (?X . (2 + 2)).

Una implementación más poderosa de patron-coincide se da en el capítulo 6. Otra implementación es dada más adelante. Es más eficiente pero más incómoda de usar.

Coincidencia de Segmentos  Patrones

En el patrón (?P necesito . ?X), la variable ?X coincide con el rest de la lista de entrada, sin importar cuál es su longitud. Esto está en contraste con ?P, que puede solo coincidir con un solo elemento, llamado, el primer elemento de la entrada. Para muchas aplicaciones de coincidencia de patrones, esto está bien; buscamos solamente hacer coincidir los elementos correspondientes. Sin embargo, ELIZA es algo diferente en que necesita llevar una cuenta para variables en cualquier posición que coincida una secuencia de ítems en la entrada. Llamaremos a tales variables de segmento. Necesitaremos una notación para diferenciar variables de segmento de las variables normales. Las posibilidades caen en dos clases: ya sea que usemos átomos para representar variables de segmento y distinguirlas por alguna convención ortográfica (como hicimos para distinguir variables de constantes) o que usemos construcciones no atómicas. Elegiremos la última, usando una lista de la forma (?* variable) para denotar variables de segmento.

El símbolo ?* es elegido porque combina la noción de variable con la notación de estrella de Kleene. De esta manera, el comportamiento que buscamos para patron-coincide es ahora:

> (patron-coincide  '((?* ?p) necesitamos (?* ?X))

                                    '(El Sr Perez y yo necesitamos vacaciones))

((?P EL SR PEREZ Y YO) (?X VACACIONES))

En otras palabras, cuando el patrón y la entrada son listas y el primer elemento del patrón es una variable de segmento, la variable hará coincidir la parte inicial de la entrada, y el resto del patrón  se intentará coincidir con el resto. Podemos actualizar patron-coincide para llevar una cuenta para esto agregando una simple cláusula cond. Definir el predicado para verificar las variables de segmento es fácil también:

(defun patron-coincide (patron entrada &optional (uniones sin-uniones))

  "Coincidencia de patrones preparando la entrada en el contexto de las uniones"

  (cond ((eq uniones falla) falla)

                ((variable-p patron)

                 (coincidir-variable patron entrada uniones))

                ((eql patron entrada) uniones)

                ((segmento-patron-p patron)                       ;***

                 (segmento-coincide patron entrada uniones))      ;***

                ((and (consp patron) (consp entrada))

                 (patron-coincide (rest patron) (rest entrada)

                                                  (patron-coincide (first patron) (first entrada)

                                                                                  uniones)))

                (t falla)))

(defun segmento-patron-p (patron)

  "Es este un segmento patron: (?* var) . pat)"

  (and (consp patron)

       (comienza-con (first patron) '?*)))

(defun comienza-con (list x)

  "Es esta una lista cuyo primer elemento es x?"

  (and (consp list) (eql (first list) x)))

Para escribir segmento-coincide, la pregunta importante es cuánto de la entrada va a coincidir con el segmento. Una respuesta es mirar el próximo elemento del patrón (el que está después de la variable de segmento) y ver que en esa posición eso ocurre en la entrada. Si no ocurre, el patrón total nunca puede coincidir, y debería fallar. Si eso ocurre, pasa a su posición. Si queremos hacer coincidir la variable preparando la parte inicial de la entrada, pasa por arriba. Pero primero tenemos que ver si el resto del patrón coincide con el resto de la entrada. Si esto es así se hace una llamada recursiva a patron-coincide. El resultado de esta llamada recursiva es llamado b2. Si b2 es exitoso, entonces vamos hacia adelante y hacemos coincidir la variable de segmento preparando la subsecuencia inicial.

El truco es que b2 falla. No queremos darlo completamente, porque puede ser que si la variable de segmento coincide con una subsecuencia más larga de la entrada, entonces el resto del patrón coincidiría con el resto de la entrada. De esta manera queremos intentar nuevamente la función segmento-coincide, pero forzándola a considerar una coincidencia más larga para la variable. Esto se hace introduciendo un parámetro opcional, inicio, que es inicialmente 0 y se incrementa con cada falla. Observe que esta política deja afuera la posibilidad de cualquier tipo de variable siguiendo  una variable de segmento. (Luego de remover esta restricción).

(defun segmento-coincide(patron entrada uniones &optional (inicio 0))

  "Coincide el segmento patron ((?* var) . pat) preparando la entrada."

  (let ((var (second (first patron)))

                (pat (rest patron)))

    (if (null pat)

                (coincidir-variable var entrada uniones)

      ;; Asumimos que pat comienza con una constante

      ;; En otras palabras, un patron no puede tener 2 vars consecutivas

      (let ((pos (position (first pat) entrada

                                                  :start inicio :test #'equal )))

                (if (null pos)

                    falla

                  (let ((b2 (patron-coincide pat (subseq entrada pos) uniones)))

                    ;;Si esta coincidencia falla, intenta otra mas larga

                    ;;Si esto funciona, verifica que las variables coincidan

                    (if (eq b2 falla)

                               (segmento-coincide patron entrada uniones (+ pos 1))

                      (coincidir-variable var (subseq entrada 0 pos) b2))))))))

Vemos algunos ejemplos de coincidencia de patrones:

> (patron-coincide '((?* ?p) necesitamos (?* ?x))

                                  '(El Sr Gomez y yo necesitamos vacaciones))

((?P EL SR GOMEZ Y YO) (?X VACACIONES))

> (patron-coincide '((?* ?x) es un (?* ?y)) '(que el es es un tonto))

((?X QUE EL ES) (?Y TONTO))

El primero de estos ejemplos muestra un caso bastante simple: ?P coincide con todo lo necesario, y ?X coincide con el resto. El siguiente ejemplo encierra el caso más complicado. Primero ?X coincide con todo lo que esta primero (esta es la posición 2, con la cuenta comenzando en 0 en Common Lisp). Pero luego el patrón falla al coincidir la entrada, de esta manera segmento-coincide intenta nuevamente iniciar con la posición 3. Esta vez todo funciona; es coincide con es, un coincide con un, y (?* ?Y) coincide con tonto.

Desafortunadamente, esta versión de segmento-coincide no hace coincidir todo como debería.

Considere el siguiente ejemplo:

> (patron-coincide '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1 2 a b)) => NIL

Esto falla porque ?x coincide con la subsecuencia (1 2), y luego el resto del patrón coincide exitosamente con el resto de la entrada, pero al final la llamada coincidir-variable falla, porque ?X tiene dos valores diferentes. La solución es llamar a coincidir-variable antes de verificar que b2 falle, así nos aseguraremos intentar segmento-coincide nuevamente con una coincidencia larga sin importar cuál sea la causa de la falla.

(defun segmento-coincide (patron entrada uniones &optional (inicio 0))

  "Coincide el segmento patron (?* var) . pat) preparando la entrada."

  (let ((var (second (first patron)))

                (pat (rest patron)))

    (if (null pat)

                (coincidir-variable var entrada uniones)

      ;;Asumimos que pat comienza con una constante

      ;;En otras palabras, un patron no puede tener 2 vars consecutivas

      (let ((pos (position (first pat) entrada

                                                  :start inicio :test #'equal)))

                (if (null pos)

                    falaa

                  (let ((b2 (patron-coincide

                                    pat (subseq entrada pos)

                                    (coincidir-variable var (subseq entrada 0 pos)

                                                                               uniones))))

                    ;; Si esta coincidencia falla, intenta otra mas larga

                    (if (eq b2 falla)

                               (segmento-coincide patron entrada uniones (+ pos 1))

                      b2)))))))

Ahora vemos que la coincidencia ocurre:

> (patron-coincide '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1 2 a b))

((?X 1 2 A B))

Observe que esta versión de segmento-coincide intenta hacer coincidir primero lo más corto posible. Podría también ser posible intentar hacer coincidir primero lo mas largo.

El programa ELIZA: Un traductor basado en reglas

Ahora que tenemos una coincidencia de patrones funcionando, necesitamos algunos patrones para hacer coincidir. Algo más, queremos que el patrón esté asociado con respuestas. Podemos hacer esto inventando una estructura de datos llamada regla, que consisten de un patrón y una o más respuestas asociadas. Hay reglas en el sentido en que ellas afirman, “Si tú ves A, entonces responde B o C, seleccionadas al azar.” Elegiremos la implementación más simple posible para las reglas: como listas, donde el primer elemento es el patrón y el resto es una lista de respuestas:

(defun regla-patron (regla) (first regla))

(defun regla-respuesta (regla) (rest regla))

Aquí un ejemplo de una regla:

(((?* ?x) quiero (?* ?y))

(que pasaria si te ofrezco ?y)

(por que quieres ?y)

(suponga que obtiene ?y pronto)

Nota del T: En español tenemos que usar verbos distintos para decir cosas distintas, en cambio en ingles un verbo tiene distintos significados. Por ejemplo  want en ingles puede decir varias cosas (querer, necesitar, desear). Pero en español debemos usar verbos distintos para decir “quiero” “necesito” “deseo”. También está el tema, no menor, del uso de las distintas conjugaciones de los verbos según la persona y el número.

Cuando es aplicada en la entrada (yo quiero verificar este programa), esta regla (cuando es interpretada por el programa ELIZA) debería replicar una respuesta aleatoria, sustituyendo en el valor de ?y, y respondiendo con (por que quieres verificar este programa). Ahora que sabemos lo que hará una regla individual, necesitamos decidir cómo manejar un conjunto de reglas. Si ELIZA está hecha para cualquier contexto, tendrá que tener una variedad de respuestas. Así varias reglas pueden ser aplicables a la misma entrada. Una posibilidad podría ser elegir una regla al azar desde un montón de reglas teniendo patrones que coinciden con la entrada.

Otra posibilidad es solo aceptar la primera regla que coincida. Esto implica que las reglas están en una lista ordenada, antes que un conjunto desordenado. La regla inteligente de ELIZA puede tomar ventaja de este ordenamiento y arreglo para la mayoría de las reglas específicas  come first, mientras más reglas vagas están cerca del fin de la lista.

El ELIZA original tiene un sistema donde cada regla tiene un número de prioridad asociado con ella. La regla de coincidencia con la más alta prioridad fue elegida. Observe que poniendo las reglas en orden logra el mismo efecto que tener un número de prioridad en cada regla: la primer regla implícita tiene la más alta prioridad, la segunda regla es la próxima más alta, y así sucesivamente. Hay una lista corta de reglas, seleccionadas del artículo original de Weizenbaum, pero con la forma de las reglas actualizadas a la forma que nosotros estamos usando. La respuesta al ejercicio 5.19 contiene una larga lista de reglas.

(defparameter *reglas-eliza*

'((((?* ?x) hola (?* ?y))

(Como estas. Por favor cuentame tu problema.))

(((?* ?x) quiero (?* ?y))

(que pasaria si te ofrezco ?y)

(por que quieres ?y) (suponga que obtienes ?y pronto))

(((?* ?x) si (?* ?y))

(realmente piensas que es probable que ?y) (deseas que ?y)

(que piensas sobre ?y) (realmente si ?y))

(((?* ?x) no (?* ?y))

(por que no?) (estas siendo un poco negativo)

(estas diciendo "NO" solo para ser negativo?))

(((?* ?x) era (?* ?y))

(eras tu realmente?) (tal vez ya sabia que tu eras ?y)

(por que me dices que tu eras ?y ahora?))

(((?* ?x) siento (?* ?y))

(te sientes a menudo ?y ?))

(((?* ?x) senti (?* ?y))

(que otros sentimientos tienes?))))

Finalmente estamos listos para definir a ELIZA apropiadamente. Como dijimos antes, el programa principal debería ser un bucle que lee entradas, las transforma, e imprime en pantalla el resultado. La transformación es hecha primariamente buscando alguna regla tal que su patrón coincida con la entrada, y luego sustituir las variables dentro de la respuesta de la regla. El programa es resumido a continuación en una tabla.

Hay unas complicaciones menores. Imprimiremos en pantalla un prompt para decirle al usuario que escriba algo. Usaremos la función aplanar para asegurarnos que la salida no tiene embebidas listas después de la sustitución de la variable. Un truco importante es alterar la entrada intercambiando “tu” por “mi” y así sucesivamente, ya que estos términos son relativos al que habla.

Funciones de alto nivel
eliza	Responde a la entrada del usuario usando reglas de coincidencia de patrones.
Variables Globales
*reglas-eliza*	Una lista de reglas de transformación.
Tipos de dato
regla	Una asociación de un patrón con una lista de respuestas.
Funciones
eliza	Responde a la entrada del usuario usando reglas de coincidencia de patrones.
usar-reglas-eliza	Busca alguna regla con la cual transformar la entrada.
cambiar-puntodevista	Cambia yo por tu y viceversa, y asi sucesivamente.
aplanar	Une juntos elementos (o listas) en la lista.
Funciones de Common-Lisp
sublis	Sustituye elementos dentro de un árbol.
Funciones definidas previamente
random-elt	Recoge un elemento aleatorio de una lista.
patron-coincide	Coincide un patrón con una entrada.
mappend	Aplica una función a cada elemento de la lista y une los resultados.

Aquí está el programa completo:

(defun eliza ()

  "Responde a la entrada del usuario usando reglas de coincidencia de patrones."

  (loop

   (print 'eliza>)

   (write (aplanar (usar-reglas-eliza (read))) :pretty t)))

(defun usar-reglas-eliza (entrada)

  "Busca alguna regla con la cual transformar la entrada."

  (some #'(lambda (regla)

                    (let ((resultado (patron-coincide (regla-patron regla) entrada)))

                      (if (not (eq resultado falla))

                                 (sublis (cambiar-puntodevista resultado)

                                                 (random-elt (regla-respuesta regla))))))

                *reglas-eliza*))

(defun cambiar-puntodevista (palabras)

  "Cambia yo por tu y viceversa, y asi sucesivamente."

  (sublis '((yo . tu) (tu . yo) (mi . ti) (soy . eres))

                  palabras))

(defun aplanar (la-lista)

  "Une juntos elementos (o listas) en la lista."

  (mappend #'mklist la-lista))

(defun mklist (x)

  "Devuelve x si este es una lista, en otro caso devuelve (x)."

  (if (listp x)

      x

    (list x)))

(defun mappend (funcion la-lista)

  "Aplica funcion a cada elemento de la lista y une los resultados."

  (apply #'append (mapcar funcion la-lista)))

(defun random-elt (opciones)

  "Recoge un elemento de una lista al azar."

  (elt opciones (random (length opciones))))

Observe el uso de write con la palabra clave :pretty. Este dará una mejor salida formateada en algunos casos. El programa hace uso de la función previamente definida random-elt, y aplanar, que son definidas aquí usando mappend y mklist, una función que es definida en el dialecto InterLisp pero no en Common Lisp.

El programa ELIZA actual tiene algunas complicaciones que no se muestran en esta versión. Primero, había un método alias para asociar varias palabras con el mismo patrón; tanto “madre” como “padre” podría ser asociado con el patrón “familia”.  Había también un mecanismo de sinónimo que podría tratar las palabras que signifiquen lo mismo. En el caso de entradas con varias frases separadas con coma, cada frase fue procesada en forma separada, y la respuesta con la prioridad más alta fue seleccionada. Adicionalmente, el ELIZA original tiene un mecanismo de  “memoria”. Cuando no coincide un patrón de entrada, esta dice algo como “Háblame más sobre X”, donde X es alguna entrada anteriormente dada. Finalmente, nuestra versión tiene pocas reglas. A pesar delos defectos de nuestra versión, esta puede ocasionalmente mantener una conversación como se muestra aquí:

> (eliza)

ELIZA> (hola)

(COMO ESTAS. POR FAVOR CUENTAME TU PROBLEMA.)

ELIZA> (quiero verificar este programa)

(QUE PASARIA SI TE OFREZCO VERIFICAR ESTE PROGRAMA)

ELIZA> (podria ver si funciona)

(REALMENTE PIENSAS QUE ES PROBABLE QUE FUNCIONA)

ELIZA> (no realmente)

(ESTAS DICIENDO "NO" SOLO PARA SER NEGATIVO?)

ELIZA> (no)

(ESTAS SIENDO UN POCO NEGATIVO)

ELIZA> (olvida eso estoy asombrado por el funcionamiento del programa)

(POR QUE ME DICES QUE TU ESTAS ASOMBRADO POR EL FUNCIONAMIENTO DEL PROGRAMA

 AHORA?)

ELIZA> (senti eso)

(QUE OTROS SENTIMIENTOS TIENES?)

ELIZA> (siento que ya es suficiente)

(TE SIENTES A MENUDO QUE YA ES SUFICIENTE ?)

ELIZA> :q

> 

Al final, lo que importa es la técnica, no el programa. ELIZA ha sido “explicada en profundidad” y podría legítimamente ser movida a la repisa de curiosidades. La coincidencia de patrones en general permanece como una técnica importante, y la veremos nuevamente en capítulos siguientes. La noción de un traductor basado en reglas  es importante también. El problema de entender español (y otros lenguajes) si siendo una parte importante en la IA. Claramente, el problema de entender español no fue resuelto por ELIZA. En la parte V, veremos el problema nuevamente, usando técnicas más sofisticadas.

Dejo un link con el eliza modificado; con mas reglas, agregue mas reglas si lo desea: Eliza2.lisp

Historia y Referencias

Como se mencionó antes, el artículo original describiendo ELIZA está en Weizenbaum 1966. Y otros sistemas de dialogo que usan técnicas similares a la coincidencia de patrones está en el PARRY de Kennth Colby (1975). Este programa simula la conversación de una persona paranoica de manera demasiado elemental para varios psicólogos profesionales. Aunque la técnica de coincidencia de patrones fue simple, el modelo es mantenido por sistemas mucho más sofisticados que ELIZA. Colby ha sugerido que los programas de dialogo como ELIZA, es aumentado con algunos modelos como PARRY, podrían ser herramientas útiles en el tratamiento de enfermedades mentales de personas. De acuerdo a Colby, podría ser barato y efectivo tener conversaciones con pacientes con un programa especialmente diseñado, que podría manejar casos simples y alertar a los doctores sobre los pacientes que necesitan más ayuda. El libro Poded de Ordenadores y Razones Humanas de Weizenbaum (1976) habla sobre ELIZA y PARRY y toma una visión muy crítica sobre la sugerencia de Colby. Otro trabajo interesante sobre modelos de sistemas de diálogo esta reportado por Allan Collins (1978) y Jamie Carbonell (1981).