Programación Avanzada
Calc: Programa
Kpress----Calc:
Kpress
ción Avanzada
Programa
Calc:
Kpress
Kpress
Calc:
Programa
ción Avanzada
ción Avanzada
. Expresiones y reglas
Esencialmente hablando, el núcleo de KPress-Calc manipula expresiones1 según una serie de
reglas de transformación2, a la que llamamos programa.
Veamos un ejemplo: en KPress-Calc, una secuencia de objetos se representa mediante una
expresión de la forma
[objeto1 , objeto2 , . . . , objeton]
por ejemplo [pera,manzana,fresa]. Dichas expresiones son conocidas con el nombre de
listas. Internamente, KPress-Calc representa las listas mediante una expresión de la forma
[objeto1 | [objeto2 | [ . . . [objeton |[]] . . . ]]]
Así que si escribimos en el área de trabajo (no olvidar el ; que indica a KPress-Calc final de
expresión)
[pera|[manzana|[fresa|[]]]];
y presionamos el botón F2 , obtendremos
[pera,manzana,fresa]
Ahora supongamos que queremos una función que extraiga el primer elemento de una lista. Para
ello escribimos en el área de trabajo:
primer_elemento([X|Y]) := X;
primer_elemento([pera,manzana,fresa]);
y tras presionar F2 , obtenemos
pera
¿Qué ha pasado? KPress-Calc ejecuta secuencialmente las expresiones que hay en el área de
trabajo. La primera que encuentra es de la forma expresión1:= expresión2 . Esto indica a KPress-
Calc que se trata de una regla, y lo que hace es incorporarla al programa. En adelante, nos
referiremos a la expresión1 como la cabeza de la regla y a la expresión2 como la cola de la regla.
Es importante observar que los símbolos que comienzan por (o son) una letra mayúscula, como X
e Y, son los símbolos de variable.
1
funcionales
2
reescritura
X => pera
Y => [manzana|[fresa|[]]]
A continuación KPress-Calc ejecuta primer_elemento([pera,manzana,fresa]). Como no
es una regla, le aplica las del programa. El proceso de aplicación de reglas, se conoce como
proceso de reescritura. En este caso, consiste en lo siguiente: la cabeza de la regla que hemos
escrito, esto es la expresión primer_elemento([X|Y]), encaja3 con
primer_elemento([pera|[manzana|[fresa|[]]]]) mediante la asignación
Entonces, el resultado de aplicar la regla, es el valor que toma la cola de la regla (es decir X), tras
dicha asignación (es decir pera).
¿Qué se obtiene al ejecutar el siguiente programa?
resto_de_elementos([X|Y]) := Y;
resto_de_elementos([pera,manzana,fresa]);
Sólo resta observar que:
1. El resultado que muestra KPress-Calc, es una expresión a la que no puede aplicar ninguna
regla del programa, esto es, cuando no hay ninguna regla cuya cabeza unifique con la
expresión o con alguna subexpresión. Por ejemplo al escribir
primer_elemento([X|Y]) := X;
resto_de_elementos([X|Y]) := Y;
primer_elemento(resto_de_elementos([pera,manzana,fresa]));
obtenemos manzana, para ello KPress-Calc ha realizado las siguientes transformaciones:
primer_elemento(resto_de_elementos([pera,manzana,fresa]))
primer_elemento([manzana,fresa])
manzana
2. En el caso de que sean aplicables varias reglas, KPress-Calc aplica la que se encuentre
en primer lugar dentro del programa.
. ¿Cómo sacar el último de la lista?
Aparentemente, sacar el último de la lista debería ser similar a sacar al primero. Sin embargo en
cuanto lo intentamos . . . ¡vemos que no hay forma! . . . bueno, si utilizamos varias reglas . . .
ultimo_elemento([X1]) := X1;
ultimo_elemento([X1,X2]) := X2;
3
unifica
ultimo_elemento([X1,X2,X3]) := X3;
...
Sólo tenemos que escribir un número infinito de reglas . . . o adoptar otra estrategia. La idea es
utilizar una regla, no para obtener directamente el resultado, sino para plantear una situación más
sencilla, cuyo resultado coincida con lo que buscamos. Veamos, sabemos que:
ultimo_elemento([pera,manzana,fresa]) = ultimo_elemento([manzana,fresa])
= ultimo_elemento([fresa])
ultimo_elemento([X,Y|Z]) := ultimo_elemento([Y|Z]);
ultimo_elemento([melocoton,platano,pera,manzana,fresa]);
y tras presionar F2 , obtenemos
ultimo_elemento([fresa])
Casi lo tenemos . . . ya que nuestra regla que dice “el último de una lista con al menos dos
elementos, coincide con el último de la lista resultante de quitarle el primero” reduce el problema al
de obtener el último de una lista formada por un único elemento. Así que si escribimos:
ultimo_elemento([X,Y|Z]) := ultimo_elemento([Y|Z]);
ultimo_elemento([X]) := X;
ultimo_elemento([melocoton,platano,pera,manzana,fresa]);
y tras presionar F2 , obtenemos
fresa
Observación: Vemos que el alcance de una variable es la regla en la que aparece, por ello la X de
la primera regla no tiene nada que ver con la X de la segunda.
¡Te atreves con los primeros elementos! es decir
Aquí
primeros_elementos([pera,manzana,fresa] ≠ primeros_elementos([manzana,fresa])
¿Qué hacer? . . . nos plantemos la siguiente pregunta: ¿Podemos construir fácilmente
primeros_elementos([pera,manzana,fresa])
[pera,manzana]
primeros_elementos([pera,manzana,fresa])
a partir de primeros_elementos([manzana,fresa])? . . . un modo de hacerlo es:
primeros_elementos([pera,manzana,fresa]) = [pera,manzana] = [pera|[manzana]]
= [pera | primeros_elementos([manzana,fresa])]
Ya lo tenemos: si escribimos en el área de trabajo
primeros_elementos([X,Y|Z]) := [X|primeros_elementos([Y|Z])];
primeros_elementos([X]) := [];
primeros_elementos([melocoton,platano,pera,manzana,fresa]);
tras presionar F2 , obtenemos [melocoton,platano,pera,manzana].
. Jugando con listas
Aunque no hemos visto todo el lenguaje, sí lo esencial. Antes de seguir es fundamental asimilar lo
expuesto, y el único modo de hacerlo es programando. A continuación discutiremos unos
ejemplos, donde es importante, una vez entendido el planteamiento, intentar dar con la solución
antes de leer la explicación. Con ello, en un momento dado, particular de cada persona, se
produce un “clic mental” (como cuando se logra ver en 3D un estereograma), a partir del cual se
es capaz de programar recursivamente.
juntar(X,Y)
Queremos programar una función que junte dos listas, es decir,
juntar([melocoton,platano],[pera,manzana,fresa])
[melocoton,platano,pera,manzana,fresa]
. . . parece elemental . . . si escribimos en el área de trabajo
juntar(X,Y) := [X|Y];
juntar([melocoton,platano],[pera,manzana,fresa]);
tras presionar F2 obtenemos ¡¡¡ [[melocoton,platano],pera,manzana,fresa] !!! . . . a lo
mejor no hemos entendido bien, probemos con la coma . . .
juntar(X,Y) := [X,Y];
juntar([melocoton,platano],[pera,manzana,fresa]);
... y tras presionar F2 obtenemos ¡¡¡ [[melocoton,platano],[pera,manzana,fresa]] !!!
Para entender lo que está ocurriendo, tenemos que ver las listas del mismo modo en que lo hace
KPress-Calc. Para ello adoptaremos la siguiente forma de representar gráficamente las listas:
El resultado deseado es [melocoton|[platano|[pera|[manzana|[fresa|[]]]]]], luego
su representación gráfica es:
Ahora veamos porqué no hemos obtenido este resultado. Sabiendo que
por un lado tendremos que
y por otro
Volvamos al problema, juntar(X,Y) significa encadenar Y al final X. Ahora tenemos dos
argumentos, entonces para reducir el problema, ¿Descomponemos el primero, . . . el segundo, . . .
o ambos? . . .Probando la primera opción, vemos que
juntar([melocoton,platano],[pera,manzana,fresa]) =
= [melocoton,platano,pera,manzana,fresa]
= [melocoton | [platano,pera,manzana,fresa]]
= [melocoton | juntar([platano],[pera,manzana,fresa])]
Ensayemos entonces la siguiente regla reductora:
juntar([X|Y],Z) := [X|juntar(Y,Z)];
juntar([melocoton,platano],[pera,manzana,fresa]);
y tras presionar F2 , obtenemos
[melocoton,platano|juntar([],[pera,manzana,fresa])], es decir,
Sólo tenemos que añadir una regla para juntar la lista vacía [] con cualquier otra:
juntar([X|Y],Z) := [X|juntar(Y,Z)];
juntar([],Z) := Z;
juntar([melocoton,platano],[pera,manzana,fresa]);
y tras presionar F2 , finalmente obtenemos [melocoton,platano,pera,manzana,fresa].
voltear(X)
Queremos una función que ponga en orden inverso los elementos de una lista. Por ejemplo
voltear([melocoton,platano,pera,manzana,fresa])
[fresa,manzana,pera,platano,melocoton]
Apliquemos nuestra estrategia: ¿Nos ayuda en algo ...?
voltear([platano,pera,manzana,fresa]
Desde luego que sí:
voltear([melocoton,platano,pera,manzana,fresa]) = [fresa,manzana,pera,platano,melocoton]
voltear([platano,pera,manzana,fresa]) = [fresa,manzana,pera,platano]
Así que para obtener el resultado deseado sólo debemos colocar melocoton al final del resultado
de voltear([platano,pera,manzana,fresa]. Para ello podemos utilizar la función juntar:
voltear([melocoton,platano,pera,manzana,fresa]) =
juntar( voltear([platano,pera,manzana,fresa]) , [melocoton] )
Ya podemos construir la regla de reducción que actúa siempre que la lista sea no vacía. Luego si
añadimos la regla que voltea la lista vacía, habremos resuelto el problema:
voltear([X|Y]) := juntar(voltear(Y),[X]);
voltear([]) := [];
juntar([X|Y],Z) := [X|juntar(Y,Z)];
juntar([],Z) := Z;
voltear([melocoton,platano,pera,manzana,fresa]);
y tras presionar F2 obtenemos [fresa,manzana,pera,platano,melocoton].
¿Qué hemos aprendido?
a) Se puede invocar a una función (juntar), para generar el resultado final
([fresa,manzana,pera,platano,melocoton]), a partir del de el problema reducido
(voltear([platano,pera,manzana,fresa])).
b) El orden relativo en que se definen la
Comentarios de: KPress-Calc_Programación Avanzada (0)
No hay comentarios