jueves, 14 de diciembre de 2017

6. Integración del intérprete

6.1. Lenguaje intermedio


En esta sección se describirá la implementación de un intérprete de un lenguaje intermedio básico. El lenguaje consta únicamente de un tipo int y se basa en una pila de ejecución sobre la que se realizan las principales instrucciones aritméticas. Las instrucciones del lenguaje son:



Desde el punto de vista sintáctico un programa está formado por una secuencia de instrucciones. Las variables y etiquetas son identificadores formados por una secuencia de letras y dígitos que comienzan por letra y se permiten comentarios con el formato de C++ (/*...*/) y (//....).

Ejemplo: El siguiente programa calcula el factorial de un número.

6.2.Construcción del intérprete

en No hay comentarios:

martes, 12 de diciembre de 2017

5. Análisis Sintáctico

El analizador sintáctico tiene como objetivo encontrar las estructuras presentes en su entrada.
Estas estructuras se pueden representar mediante el árbol de análisis sintáctico, que explica cómo se puede derivar la cadena de entrada en la gramática que especi ca el lenguaje. Aunque en la práctica es habitual que el árbol de análisis no llegue a construirse, se trata de una abstracción que nos permite entender mejor todo el proceso.

Para construir la especi ficación sintáctica de los lenguajes de programación, se suelen emplear gramáticas incontextuales, generalmente restringidas para que el análisis se pueda realizar demanera efi ciente.
Para que sea posible construir el árbol de análisis, es necesario que la entrada no presente errores sintácticos. En caso de que los haya, el analizador debe informar de su presencia adecuadamente y, si es posible, intentar continuar el análisis.Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. 

En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico.
En la práctica, el analizador sintáctico también hace: 
• Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico). 
• Chequeo de tipos ( del analizador semántico).
 • Generar código intermedio. 
• Generar errores cuando se producen.
En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.
http://www.lcc.uma.es/~galvez/ftp/tci/tictema3.pdf
 

5.1. Aspectos generales de un analizador sintáctico

El analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente.

Tipos generales de analizadores sintácticos para gramáticas:
a) Análisis sintáctico descendente. Construye árboles de análisis sintáctico desde arriba (raíz) hacia abajo (hojas). El análisis se realiza de lo general a lo particular.
b) Análisis sintáctico ascendente. Construyen árboles de análisis sintáctico comenzando en las hojas y suben hacia la raíz. El análisis se realiza de lo particular a lo general.
En ambos casos, se examina la entrada al analizador léxico de izquierda a derecha, un símbolo a la vez.

5.2. Gramáticas y diseño de un árbol gramatical


Una gramática describe de forma natural la estructura jerárquica de muchas construcciones de los lenguajes de programación. Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática
Consta de:
• TERMINALES. Símbolos básicos con que se forman las cadenas. Para un lenguaje de programación, cada palabra clave/reservada es un terminal.

• NO TERMINALES. Son variables sintácticas que denotan conjuntos de cadenas (identificadotes o variables). Los no terminales definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la gramática. Imponen una estructura jerárquica sobre el lenguaje que es útil tanto para el análisis sintáctico como para la traducción.

• UN SÍMBOLO INICIAL. En una gramática, es un no terminal que representa un conjunto de cadenas.

• PRODUCCIONES. Especifican cómo se pueden combinar los terminales y no terminales para formar cadenas. Cada producción consta de un No terminal (símbolo inicial), seguido por una flecha o símbolo de asignación, seguida por una cadena de no terminales y terminales.


ESCRITURA DE UNA GRAMATICA

Las gramáticas describen la mayoría de las sintaxis de los lenguajes de programación.Toda construcción que se pueda describir mediante una expresión regular también se puede describir por medio de una gramática.
Por ejemplo, para la expresión regular (a|b)* abb

Y la gramática: A0 → a A0 | b A0| b A1 
A1 → b A2
A2 → bA3 
A3 → є
*Árbol sintáctico de una sentencia de un lenguaje
 Es una representación que se utiliza para describir el proceso de derivación de dicha sentencia. 
Como nodos internos del árbol, se sitúan los elementos no terminales de las reglas de producción que vayamos aplicando, y tantos hijos como símbolos existan en la parte derecha de dichas reglas. 
Veamos un ejemplo: Sea la gramática anterior.
 E Ú E + T | T T Ú T * F | F F Ú ( E ) | a | b 
Supongamos que hay que reconocer: ( a + b ) * a + b 
Si el árbol puede construirse, es que la sentencia es correcta:

5.3. Verificación de sintaxis y aplicación de reglas sintácticas


 5.4. Elaboración del PARSER

en No hay comentarios:

viernes, 8 de diciembre de 2017

4. Análisis léxico

4.1.  Aspectos generales de un analizador léxico

Image result for analizador lexico
Un analizador léxico es la especificación y el diseño de programas que ejecuten las acciones activadas por patrones dentro de las cadenas.

*La principal función es leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que se utilizaran.

*Convierte una cadena de caracteres en una cadena de palabras.

*Una forma sencilla de crear un analizador léxico consiste en la elaboración de un diagrama que muestre la estructura de los componentes léxicos del archivo fuente, y después hacer la traducción “a mano” del diagrama a un programa para encontrar los componentes léxicos.

*Una herramienta de software que automatiza la construcción de analizadores léxicos, permite que personas con diferentes conocimientos utilicen la concordancia de patrones en sus propias áreas de aplicación.

*La gran ventaja de un generador de analizadores léxicos es que puede utilizar los algoritmos más conocidos de concordancia de patrones, con lo cual crea analizadores léxicos eficientes para los no especialistas en dichas técnicas. 

4.2.  Definición de grafos y autómatas

AFD.
Grafos.
Los grafos no son más que la versión general de un árbol, es decir, cualquier nodo de un grafo puede apuntar a cualquier otro nodo de éste (incluso a él mismo). Este tipo de estructuras de datos tienen una característica que lo diferencia: los grafos se usan para almacenar datos que están relacionados de alguna manera (relaciones de parentesco, puestos de trabajo, ...); por esta razón se puede decir que los grafos representan la estructura real de un problema. En lo que a ingeniería de telecomunicaciones se refiere, los grafos son una importante herramienta de trabajo, pues se utilizan tanto para diseño de circuitos como para calcular la mejor ruta de comunicación en Internet.

Autómata

Se llama autómata a cualquier mecanismo que es capaz de moverse por sí mismo. Si los autómatas se producen en serie tenemos los robots. Y, en el campo de la ficción, si el autómata tiene aspecto humano (por estar recubierto de materia orgánica por ejemplo), tenemos los androides.


También cabe llamar autómata a toda máquina que sigue un programa de instrucciones diseñado por un programador. En este sentido, los ordenadores también son autómatas. Cabe hablar también de autómatas de propósito general o universal y de autómatas de propósito limitado. En el primer caso tenemos los ordenadores convencionales, que están construidos de tal forma que pueden programarse para resolver muchos tipos diferentes de problemas, y en el segundo los computadores diseñados para realizar una tarea específica, como nuestras calculadoras o el computador de un automóvil. Por extensión, también recibe el nombre de "autómata" el programa mismo, o la arquitectura computacional en la que descansa la ejecución del programa, como es el caso de la llamada "máquina de Turing".

http://www.e-torredebabel.com/Psicologia/Vocabulario/Automatas.htm

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.
Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.
La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.
Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

4.3.  Definición de clases, estados y tokens

Clase. Es una construcción que permite crear tipos personalizados propios mediante la agrupación de variables de otros tipos, métodos y eventos. Una clase es como un plano. Define los datos y el comportamiento de un tipo. Si la clase no se declara como estática, el código de cliente puede utilizarla mediante la creación de objetos o instancias que se asignan a una variable. La variable permanece en memoria hasta todas las referencias a ella están fuera del ámbito. Si la clase se declara como estática, solo existe una copia en memoria y el código de cliente solo puede tener acceso a ella a través de la propia clase y no de una variable de instancia.


Estados. un estado es una configuración única de información en un programa o máquina. Esto es un concepto que ocasionalmente se ha extendido en varias formas de programación de sistemas tales como lexers y Parsers.

Si el autómata en cuestión es una Máquina de estados finitos, un Autómata con pila o una auténtica Máquina de Turing, un estado es un conjunto particular de instrucciones las cuales serán ejecutadas en respuesta a la entrada de la máquina. Se puede pensar en el estado como algo análogo a la memoria principal de la computadora. El comportamiento del sistema es una función de (a) la definición del autómata, (b) la entrada y (c) el estado actual.
  • Estados Compatibles son estados de una máquina de estados los cuales no tienen conflictos para ningún valor de entrada. Así para cada entrada, ambos estados deben tener la misma salida, y ambos estados deben tener el mismo sucesor (o sucesores sin especificar) o ambos no deben cambiar. Los estados compatibles son redundantes si aparecen en la misma máquina de estados.
  • Estados Equivalentes son los estados de una máquina de estados los cuales, para cada posible secuencia de entrada, la misma secuencia de salida será producida - sin importar cual estado es el estado inicial.
  • Estados Distinguibles son estados en una máquina de estados los cuales tienen al menos una secuencia de entrada la cual causa secuencias de salida diferentes - sin importar cual estado es el estado inicial.


Tokens. Un token es un par que consiste en un nombre de token y un valor de atributo opcional. El nombre del token es un símbolo abstracto que representa un tipo de unidad léxica; por ejemplo, una palabra clave específica o una secuencia de caracteres de entrada que denotan un identificador. Los nombres de los tokens son los símbolos de entrada que procesa el analizador sintáctico.

4.4.  Matriz de transición de estados y matriz de salidas

Una tabla de transiciones es un arreglo (o matriz) bidimensional cuyos elementos proporcionan el resumen de un diagrama de transiciones correspondiente.


Tabla que muestra qué estado se moverá un autómata finito dado, basándose en el estado actual y otras entradas. Una tabla de estados es esencialmente una tabla de verdad en la cual algunas de las entradas son el estado actual, y las salidas incluyen el siguiente estado, junto con otras salidas.

Una tabla de estados es una de las muchas maneras de especificar una máquina de estados, otras formas son un diagrama de estados, y una ecuación característica.

Cuando se trata de un autómata finito no determinista, entonces la tabla de transición muestra todos los estados que se moverá el autómata.

Matriz de salidas.

4.5.  Elaboración del SCANNER


en No hay comentarios:

jueves, 30 de noviembre de 2017

Aplicación de los intérpretes interactivo y recursivo

Recursión

Ya hemos visto algunos ejemplos de funciones recursivas. Una función es recursiva cuando se llama a si misma. Una vez que uno se acostumbra a su uso, se comprueba que la recursión es una forma mucho más natural que la iteración de expresar un gran número de funciones y procedimientos.
Recordemos el ejemplo típico de función recursiva, el factorial:
(define (factorial x)
   (if (= x 0)
      1
      (x * (factorial (- x 1)))))
La formulación matemática de la recursión es sencilla de entender, pero su implementación en un lenguaje de programación no lo es tanto. El primer lenguaje de programación que permitió el uso de expresiones recursivas fue el LISP. En el momento de su creación existía ya el Fortran, que no permitía que una función se llamase a si misma.

Confía en la recursión

Ya sabemos cómo es un algoritmo recursivo. Hemos visto varios ejemplos utilizando números, identificadores o listas. Pero… ¿cómo diseñar un algoritmo recursivo? Para resolver un problema de forma recursiva debes:
  1. Descomponer el problema principal en alguna versión más simple, que puedas resolver llamando a la propia función recursiva
  2. Confiar en la recursión para resolver esta versión más simple del problema y que va a devolver su solución
  3. Obtener la solución al problema completo a partir de la solución de la versión más simple
La frase confía en la recursión quiere decir que cuando estés analizando el funcionamiento de un programa recursivo y veas una llamada recursiva debes confiar en que esta llamada va a devolver el resultado que se prentende.
Es útil escribir y pensar en los procedimientos recursivos de forma declarativa, teniendo en cuenta lo que hacen y no cómo lo hacen. Es útil pensar en la formulación recursiva del problema de una forma matemática, analítica o gráfica antes de ponerse a programar. Es muy útil también probar con algunos ejemplos concretos.
¿Cuándo para el algoritmo? Cuando el problema es lo más simple posible y ya no se puede simplificar más: este es el caso base. Debemos entonces devolver un valor concreto, la recursión ya ha terminado.
Vamos a utilizar estos consejos para construir algunos procedimientos recursivos.

longitud

Queremos diseñar la función (longitud lista) que devuelva la longitud de una lista.
Un ejemplo de un diseño recursivo de la función podría ser el siguiente:
  • Supongamos que tenemos la lista (a b c d).
  • ¿Cómo podemos llamar a la propia función longitud de forma recursiva con una lista más pequeña?
  • Podríamos quitar el primer elemento de la lista llamando a cdr y calcular la longitud de la lista restante, confiando en la llamada recursiva:
    (longitud (cdr '(a b c d))) ->
(longitud '(b c d)) -> 3
  • Hemos obtenido 3. Como habíamos quitado el primer elemento de la lista, la longitud de la lista original se obtien sumando 1.
  • Este ejemplo nos lleva a la formulación declarativa de la recursión:
    longitud (lista) = 1 + longitud (resto (lista))
  • Falta el caso base. Normalmente es la parte más sencilla. En este caso es trivial: la longitud de la lista vacía es 0.
Y sólo queda convertir este diseño en un programa de Scheme:
(define (longitud lista)
   (if (null? lista)
      0
      (+ 1 (longitud (cdr lista)))))

sumatorio

Queremos implementar la función (sumatorio n m) que devuelve la suma de los números desde n hasta m, ambos incluidos.
Igual que en el ejemplo anterior, comenzamos con un caso sencillo y vemos cómo se puede formular recursivamente.
sumatorio(8,20) = 8+9+...+20 = 8 + (9+10+...+20) = 8+sumatorio(9,20)
También se podría expresar otra recursión:
sumatorio(8,20) = 8+9+...+20 = (8+9+...+19)+20 = sumatorio(8,19)+20
Podemos considerar como caso base el caso en el que n/=/m y devolver n, o el caso en el que n/>/m y devolver 0.
El paso a Scheme es directo.
Versión 1:
(define (sumatorio n m)
   (if (= n m)
      0
      (+ n (sumatorio (+ n 1) m))))
Versión 2:
(define (sumatorio n m)
   (if (= n m)
      0
      (+ m (sumatorio n (- m 1)))))

elemento?

Otro ejemplo. La función (elemento? x lista) que comprueba si el elemento x está incluido en la lista.
El diseño recursivo consiste en quitar el primer elemento de la lista y preguntar si es x o si x está en el resto de la lista. La descripción declarativa es la siguiente:
(define (elemento? x lista)
   (if (null? lista)
      #f
      (or (equal? x (car lista))
          (elemento? x (cdr lista)))))

nth

Vamos a ver cómo encontrar el elemento n-ésimo de una lista de forma recursiva. Este va a ser un ejemplo algo distinto a los anteriores, ya que aquí no tendremos que construir ninguna solución a partir de la llamada recursiva, sino que debermos buscar esta solución haciendo cada vez más sencillo el problema.
Vamos a llamar a la función (nth n lista), donde n es la posición del elemento que queremos devolver (comenzando por 1) y lista es la lista que recorremos.
Podemos empezar por preguntarnos qué sabemos hacer con las listas:
  • Devolver el primer elemento de una lista utilizando la función car
  • Devolver el resto de la lista sin el primer elemento utilizando la función cdr
O sea, que si nos preguntaran por el primer elemento de la lista:
(nth 1 '(a b c))
para devolverlo habría que llamar a car:
(car '(a b c)) -> a
¿Cómo podríamos usar la recursión para devolver un elemento que no está en primer lugar? Esto es, ¿qué hacer cuando n es distinto de 1? Habrá que simplificar el problema y pasarle a la llamada recursiva la lista sin el primer elemento y habiendo restado 1 a n:
(define (nth n lista)
  (if (= n 1)
    (car lista)
    (nth (- n 1) (cdr lista)))
¿Qué pasaría si se llama a la función con el número n siendo mayor que el número de elementos de la lista? Tendríamos un error, ya que la se intentaría obtener el primer elemento de una lista vacía. Para solucionarlo, basta con contemplar este caso como otra posible condición de terminación de la recursión:
(define (nth n lista)
  (cond
    ((null? lista) lista)
    ((= n 1) (car lista))
    (else (nth (- n 1) (cdr lista)))))

Recursión mutua

A veces es útil usar un patrón de recursión mutua, en el que dos funciones se llaman una a la otra. El patrón recuerda la famosa ilustración Drawing Hands de M.C. Escher:
Drawing Hands
Un primer ejemplo de este comportamiento es la definición recursiva mutua de par e impar:
  • x es par si x-1 es impar
  • x es impar si x-1 es par
  • 0 es par
La implementación en Scheme es directa:
(define (par? x)
   (if (= 0 x)
      #t
      (impar? (- x 1))))

(define (impar? x)
   (if (= 0 x)
      #f
      (par? (- x 1))))
Un ejemplo algo más complejo es la curva de Hilbert. La curva de Hilbert es una curva fractal que tiene la propiedad de rellenar completamente el espacio. Su dibujo tiene una formulación recursiva.
Curvas de Hilbert
Vemos que la curva H3 se puede construir a partir de la curva H2.
Utilizamos la librería graphics/turtles que permite usar la conocida tortuga y comandos de Logo en Scheme (draw y turn).
  • La función (h-der i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la derecha de la tortuga.
  • La función (h-izq i w) dibuja una curva de Hilbert de orden i con una longitud de trazo w a la izquierda de la tortuga.
Para dibujar una curva de Hilbert de orden i a la derecha de la tortuga:
  1. Gira la tortuga -90
  2. Dibuja una curva de orden i-1 a la izquierda
  3. Avanza w dibujando
  4. Gira 90
  5. Dibuja una curva de orden i-1 a la derecha
  6. Avanza w dibujando
  7. Dibuja una curva de orden i-1 a la derecha
  8. Gira 90
  9. Avanza w dibujando
  10. Dibuja una curva de orden i-1 a la izquierda
  11. Gira -90
El algoritmo para dibujar a la izquierda es simétrico.
Algoritmo en Scheme:
(require graphics/turtles)
(turtles #t)
(define (h-der i w)
    (if (> i 0)
        (begin
          (turn -90)
          (h-izq (- i 1) w)
          (draw  w)
          (turn 90)
          (h-der (- i 1) w)
          (draw w)
          (h-der (- i 1) w)
          (turn 90)
          (draw w)
          (h-izq (- i 1) w)
          (turn -90))))
(define (h-izq i w)
    (if (> i 0)
      (begin
        (turn 90)
        (h-der (- i 1) w)
        (draw  w)
        (turn -90)
        (h-izq (- i 1) w)
        (draw w)
        (h-izq (- i 1) w)
        (turn -90)
        (draw w)
        (h-der (- i 1) w)
        (turn 90))))
Podemos probarlo con distintos parámetros de grado de curva y longitud de trazo:
(clear)
(h-izq 3 20)
(h-izq 6 5)
El resultado de esta última llamada es:
Curvas de Hilbert

Procesos recursivos e iterativos

Hemos visto que la recursión es una herramienta muy elegant y con un alto nivel de abstracción. Pero hay que tener cuidado al utilizarla, porque a veces una solución recursiva pura es muy elegante pero tiene un coste demasiado elevado.
Veremos en este apartado que en estos casos es posible modificar la recursión y construir una solución que crea un proceso iterativo utilizando lo que se denomina recursión por la cola.

El coste espacial de la recursión

Vamos examinar en primer lugar el coste espacial de la recursión. ¿Cuál es el coste espacial de una llamada recursiva? ¿Qué información debo guardar para realizar la recursión? La respuesta es que el coste viene dado por el número de llamadas a funciones que quedan a la espera de que termine la recursión. Veamos algunos ejemplos.

longitud

Comenzamos repasando la función longitud que hemos visto anteriormente. Supongamos la siguiente invocación de esta función:
(longitud '(a b c d)) -> 4
La traza de llamadas recursivas que se han generado con la llamada anterior es la siguiente:
(longitud '(a b c d))
(+ 1 (longitud '(b c d)))
(+ 1 (+ 1 (longitud '(c d))))
(+ 1 (+ 1 (+ 1 (longitud '(d)))))
(+ 1 (+ 1 (+ 1 (+ 1 (longitud '())))))
(+ 1 (+ 1 (+ 1 (+ 1 0))))
(+ 1 (+ 1 (+ 1 1)))
(+ 1 (+ 1 2))
(+ 1 3)
4
Cada llamada a la recursión deja en espera una llamada a la función + con los parámetros 1 y el propio resultado de la recursión. Como en cualquier llamada a una función, este estado local se almacena en una /pila de llamada/ de la que será recuperado cuando la llamada termine. En el caso de la recursión la pila va creciendo hasta que la recursión termina. Si por un error la recursión no termina y se entra en un bucle infinito en algún momento se produce un stack overflow, un desbordamiento de la memoria reservada por el sistema operativo para el programa que está en funcionamiento.
Estas llamadas en espera son las que determinan el coste espacial de la recursión. En este caso el coste espacial depende linealmente de la longitud de la palabra. Se trata de un coste O(n), siendo n la longitud de la palabra.

fibonacci

El coste espacial y el temporal depende del número de llamadas a la recursión. En el caso en que se realicen dos llamadas a la recursión tendríamos un coste exponencial.
Veámoslo con una recursión que implementan de forma elegante, pero poco eficiente, la serie de Fibonacci.
Recordemos que la secuencia de números de Fibonacci se define con la siguiente expresión:
fib (n) = fib (n-1) + fib (n-2)
fib (1) = fib (0) = 1
De esta forma, la secuencia de números de Fibonacci es: 1, 1, 2, 3, 5, 8, 13, 21, …
La función recursiva que resulta de aplicar directamente esta ecuación es la siguiente:
(define (fib n)
(cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
La diferencia con las funciones recursivas vistas hasta ahora es que en el cuerpo de la función se realizan dos llamadas recursivas. Esto genera un proceso recursivo en forma de árbol, como se comprueba en la siguiente figura, extraída del Abelson & Sussman:
Recursión en Fibonacci
Cada llamada a la recursión produce otras dos llamadas, con lo que el número de llamadas finales es 2n, siendo n el número que se pasa a la función. El coste espacial y temporal es por tanto de O(2n). Podemos comprobar con el intérprete que es imposible evaluar la función para números a partir de 30.
¿Es posible diseñar la función recursiva de otra forma, para evitar este coste? Vamos a verlo.

Procesos recursivos e iterativos

En la asignatura hecho la distinción entre programas y los procesos que éstos generan. Esta distinción se hace muy importante en el caso de los programas recursivos.
Hemos visto en el apartado anterior que el proceso generado por una función recursiva tiene a veces un alto coste espacial y temporal debido a las llamadas que permenacen en espera en la pila de la recursión.
Es posible escribir programas recursivos que generen procesos que no dejan llamadas en espera. A estos procesos los llamamos procesos iterativos, en contraposición con los procesos recursivos que generan los programas vistos hasta ahora.
La siguiente versión de la función factorial está escrita de forma que el proceso generado es iterativo y no deja llamadas en espera.
(define (factorial-iter n)
   (fact-iter-aux n n))

(define (fact-iter-aux product n)
    (if (= n 1)
        product
        (fact-iter-aux (* product (- n 1))  (- n 1))))
La función (fact-iter-aux product n) es la que implementa la nueva versión de factorial. El parámetro adicional product que se ha añadido guarda en cada llamada el cálculo parcial del factorial. Cuando la recursión llega a su fin ya se tiene el resultado calculado y se devuelve directamente, sin necesidad de evaluar ninguna función en espera.
Lo podemos comprobar en la secuencia de llamadas que se produce para evaluar (factorial-iter 4):
(factorial-iter 4)
(factorial-iter-aux 4 4)
(factorial-iter-aux 12 3)
(factorial-iter-aux 24 2)
(factorial-iter-aux 24 1)
24
Veamos otro ejemplo más, la versión iterativa de la función longitud que calcula la longitud de una lista.
(define (longitud-iter lista)
   (longitud-iter-aux lista 0))

(define (longitud-iter-aux lista result)
   (if (null? lista)
      result
      (longitud-iter-aux (cdr lista) (+ result 1))))
La función longitud-iter ahora recibe un argumento adicional, denominado result. Igual que en la función fact-aux anterior en él se almacena el valor parcial del cálculo de la recursión. En este caso de la longitud de la palabra.
En cada llamada recursiva se incrementa en 1 el resultado parcial y se elimina un elemento de la lista. De esta forma, cuando la lista esté vacía, el resultado habrá acumulado su longitud (siempre que inicialmente se haya pasado 0 como valor).
La función longitud se redefine para que llame a longitud-iter con los valores iniciales correctos.
Como podemos comprobar, tampoco se deja ninguna llamada en espera en la pila de llamada. Cuando alcanzamos el caso base de la recursión tenemos la respuesta al problema completo.
(longitud 'abcdef)
(longitud-iter 'abcdef 0)
(longitud-iter 'bcdef 1)
(longitud-iter 'cdef 2)
(longitud-iter 'def 3)
(longitud-iter 'ef 4)
(longitud-iter 'f 5)
(longitud-iter "" 6)
6

Procesos iterativos

Las dos funciones anteriores son ejemplos de funciones que generan procesos iterativos.
En general, las versiones iterativas son menos elegantes y más difíciles de entender que las recursivas, pero son más eficientes.
En otros lenguajes de programación existen bucles (for, while) para definir procesos iterativos. En un lenguaje funcional puro no existen bucles; el proceso iterativo se implementa como hemos visto. Se utiliza uno o más parámetros auxiliares y se modifica su valor en cada llamada a la recursión.
Esta recursión que no deja llamadas en espera también recibe el nombre de tail recursión o recursión por la cola. El código del intérprete que evalua la recursión por la cola puede tratar estas llamadas de una forma especial, sabiendo que no hay que devolver el resultado para que vuelva a ser procesado. Se devuelve el último valor a la llamada original y se puede eliminar la pila de la llamada.

Fibonacci iterativo

La versión recursiva de la función que devuelve el número de Fibonacci tenía un coste exponencial, debido a las dos llamadas recursivas.
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
Se puede implementar una versión eficiente de la misma función utilizando el mecanismo de recursión por la cola.
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define (fib n)
  (fib-iter 1 0 n))
La función (fib-iter a b count) define un proceso iterativo que va calculando cada número sucesivo de fibonacci utilizando los parámetros a y b. El parámetro count cuenta el número de iteraciones.
Esta recursión tiene un coste lineal O(n) y permite calcular sin problemas valores de fibonacci imposibles de obtener con la recursión anterior.

Memoization

La memoization es una técnica de optimización que permite mantener la elegancia de los procesos recursivos sin incurrir en el coste de las llamadas repetidas a la recursión.
Si miramos la traza de (fibonaci 4) podemos ver que se está llamando de forma repetida a la recursión con los mismos valores.
Por ejemplo, para calcular (fib 200) hay que llamar a (fib 199) y (fib 198). A su vez, para calcular (fib 199) se llama a (fib 198) y (fib 197). ¿Por qué llamar dos veces a (fib 198)? Estamos en programación funcional y el resultado de la llamada siempre va a ser el mismo. ¿No podríamos guardar el valor devuelto por (fib 198) la primera vez y utilizarlo la segunda vez? De esta forma no volveríamos a lanzar la recursión para este valor (ni para ningún otro).
Esto es lo que hace la memoization, en una llamada recursiva guarda el valor devuelto por cada una de las llamadas en alguna estructura de datos adecuada (una tabla hash por ejemplo) y lo reutiliza en el resto de llamadas.
La forma de implementar la memoization en Scheme utiliza continuaciones y la forma especial no funcional set!, características del lenguaje que todavía no hemos estudiado. Una explicación muy buena de cómo hacerlo se puede encontrar en Community Scheme Wiki.

Triángulo de pascal

El último ejemplo de función recursiva que vamos a transformar en iterativa es el triángulo de Pascal.
Cada elemento del triángulo de Pascal es la suma de los dos números que hay sobre él:
              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10  5   1
  1   6  15  20  15  6   1
1   7  21  35  35  21  7   1
             ...
La función Pascal(fila, columna) se define matemáticamente de la siguiente forma:
Pascal(fila, 0) = 1 para cualquier valor de fila
Pascal(fila, columna) = 1 si fila = columna
Pascal(fila, columna) = Pascal(fila-1,columna-1) + Pascal(fila-1, columna) en otro caso
La función Scheme que calcula de forma recursiva el número de Pascal que se encuentra en una determinada fila y columna es la siguiente:
(define (pascal row col)
  (cond ((= col 0) 1)
        ((= col row) 1)
        (else (+ (pascal (- row 1) (- col 1))
                 (pascal (- row 1) col) ))))
Al igual que con la función fibonacci esta solución es muy poco eficiente. Para calcular un valor de la recursión se hacen dos llamadas recursivas, lo que genera un proceso en forma de árbol con un coste exponencial.
Una forma de solucionar el problema con una versión iterativa consiste en generar cada una de las filas del triángulo a partir de la anterior. La fila se puede representar con una lista.
La función (pascal-sig-fila fila) se encarga de construir la fila siguiente del triángulo de Pascal a partir de la anterior. Por ejemplo:
(pascal-sig-fila '(1 3 3 1)) -> (1 4 6 4 1)
Su implementación se basa en la función (pascal-sig-fila-central fila) que calcula de forma recursiva los elementos interiores de la fila. Esta función no es iterativa.
(define (pascal-sig-fila fila)
    (append '(1)
                (pascal-sig-fila-central fila)
                '(1)))

(define (pascal-sig-fila-central fila)
   (if (= 1 (length fila))
      '()
       (append (list (+ (car fila) (car (cdr fila))))
                   (pascal-sig-fila-central (cdr fila)))))
La función (pascal-iter-aux fila n) es la que realiza las n iteraciones utilizando fila como parámetro auxiliar en el que se van construyendo las sucesivas filas. Termina cuando la longitud de la fila calculada coincide con n.
Por último, la función (pascal-iter fila col) llama a la anterior para producir la fila número fila, y devuelve el elemento número col:
(define (pascal-iter fila col)
   (if (= 0 col)
      1
      (list-ref (pascal-iter-aux '(1 1) fila) col)))

(define (pascal-iter-aux fila n)
    (if (= n (- (length fila) 1))
        fila
        (pascal-iter-aux (pascal-sig-fila fila) n)))
La función pascal-sig-fila se encarga de construir la fila siguiente del triángulo de Pascal a partir de la anterior. Por ejemplo:
La función pascal-iter va llamando de forma iterativa a pascal-sig-fila hasta que llegamos a la fila n que deseamos. La función pascal recoge esa fila y devuelve el elemento coldeseado.
Puedes probar los siguientes valores para comprobar la diferencia de rendimiento entre las dos versiones:
(pascal 28 10) -> 13123110
(pascal-iter 28 10) -> 13123110

Estructuras de datos recursivas

En este apartado vamos a estudiar el diseño y la implementación en Scheme de tres estructuras de datos que tienen definiciones recursivas:
  • Expresiones-s
  • Árboles binarios
  • Árboles genéricos

Expresiones-s

Las expresiones-s (expresión simbólica) son la base del diseño del lenguaje de programación LISP. Fueron introducidas en 1958 por John McCarthy, en el artículo Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, en el que define el lenguaje de programación LISP.

Definición

En su formulación original de McCarty, una expresión-s es una expresión matemática que se define con la siguiente formulación recursiva:
  • Un dato atómico es una expresión-s
  • Si e1 y e2 son expresiones-s, la expresión (e1 . e2) también es una expresión-s
Por ejemplo, las siguientes expresiones son expresiones-s de McCarthy:
(A . B)
(A . (B . C))
((A . B) . (C . D))
(A. ((A . B) . (C . D)))
Y las siguientes expresiones no son expresiones-S de McCarthy:
(A . B . C)
(A)
(() . B)
En la misma formulación, McCarthy define una lista como un tipo especial de expresión-s que termina con el átomo NIL:
(m1, m2, …, mn) -> (m1 . (m2 . ( … (mn . NIL) … )))
Esta formulación matemática fue el origen del concepto de pareja de LISP utilizando las funciones cons, car y cdr (también definidas en el mismo artículo).
En la actualidad, el concepto de expresión-s se ha extendido, eliminando la notación del punto y refiriéndose a expresiones con símbolos (identificadores) entre un número balanceado de paréntesis.
Los siguientes son ejemplos de expresiones-s extendidas:
(= 4 (+ 2 2))
(if (= x y) (* x y) (+ (/ x y) 45))
(define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))
Esta es la interpretación que vamos a utilizar a partir de ahora cuando hablemos de expresión-s en general.
En Scheme las expresiones-s se implementan con listas. Cuando el intérprete, en su bucle read-eval-print recibe una expresión-s, la convierte en una lista e intenta evaluarla.
Cualquier expresión de Scheme correcta es una expresión-s, pero al revés no. Por ejemplo, las siguientes expresionesn-s son expresiones correctas de Scheme:
(define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))
(define lista (quote (1 (2 (3)))))
Y la siguiente expresión-s no lo es:
(1 (2 (3)))
La consideración de una expresión-s como una lista nos lleva a su última definición recursiva:
  • Una expresión-s es una lista cuyos elementos pueden ser datos atómicos o expresiones-s
  • Una expresión-s vacía es una lista vacía
Con esta definición, considerando las expresiones-s como listas, vemos que se pueden aplicar las funciones car y cdr para recorrerlas:
  • La función car devolverá un dato atómico u otra expresión-s
  • La función cdr devolverá la expresión-s resultante de eliminar el primer elemento de la lista. Nunca devolverá un dato atómico.

Estructura jerárquica

Las expresiones-s representan una estructura de niveles, en la que la lista inicial define el nivel 1, y las siguientes expresiones anidadas van aumentando de nivel.
Los datos atómicos constituyen las hojas de la estructura.
Expresion-e jerarquica
  • Otro ejemplo (ejercicio en clase):
    (let ((x 12)
      (y 5))
   (+ x y)))
Las funciones que podemos utilizar para recorrer una expresion-s son:
  • list y quote: construcción
  • cons: añadir elemento a la cabeza
  • car: devuelve el primer dato (puede ser una hoja o una expresión-S)
  • cdr: devuelve el resto (siempre una expresión-S)
  • null?: comprueba si es lista vacía
Para remarcar el carácter jerárquico de las expresiones-s definimos la función hoja? que comprueba si el elemento es una hoja o una expresión-s (lista)
(define (hoja? x)
   (not (pair? x)))

Funciones sobre expresiones-s como estructuras jerárquicas

  • (cuenta-hojas-exp exp): cuenta las hojas
  • (niveles-exp exp): cuenta los niveles
  • (pertenece-exp x exp): busca una hoja
  • (cuadrado-exp exp): eleva todas las hojas al cuadrado
  • (map-exp f exp): similar a map
La función (cuenta-hojas-exp exp) cuenta las hojas que hay en una expresión-s
(define (cuenta-hojas-exp exp)
    (cond
      ((null? lista) 0)
      ((hoja? (car exp)) (+ 1 (cuenta-hojas-exp (cdr exp))))
      (else
           (+ (cuenta-hojas-exp (car exp))
              (cuenta-hojas-exp (cdr exp))))))
La función (niveles-exp exp) devuelve el número de niveles de una expresión-s.
(define (niveles-exp exp)
   (cond 
      ((null? exp) 0)
      ((hoja? exp) 0)
      (else (max (+ 1 (niveles-exp (car exp)))
                 (niveles-exp (cdr exp))))))
La función (pertenece-exp? x exp) comprueba si el átomo x aparece en la expresión-s
(define (pertenece-exp? x exp)
         (cond 
             ((null? exp) #f)
             ((hoja? exp) (equal? x exp))
             (else (or (pertenece-exp? x (car exp))
                       (pertenece-exp? x (cdr exp))))))
La función (cuadrado-exp exp) devuelve una expresión-s formada por números con la expresión-s con la misma estructura y los números elevados al cuadrado.
(define (cuadrado-exp exp)
  (cond ((null? exp) '())
        ((hoja? exp) (cuadrado exp))
        (else (cons (cuadrado-exp (car exp))
                    (cuadrado-exp (cdr exp)) )) ))
Por último (map-exp f exp) devuelve una expresión-s formada con la misma estructura que la original con el resultado de aplicar a cada uno de sus átomos la función f
(define (map-exp f exp)
  (cond ((null? exp) '())
        ((hoja? exp) (f exp))
        (else (cons (map-exp f (car exp))
                    (map-exp f (cdr exp)) )) ))

Árboles binarios

Un árbol binario es una estructura que contiene tres elementos: un dato, un árbol binario izquierdo y un árbol binario derecho.
Esta definición es recursiva y necesita un caso base. Es el siguiente: un árbol binario puede ser también un árbol-vacio, un símbolo especial vacio-bt que simboliza un árbol que no tiene datos ni hijos.
Árbol binario
En la asignatura no nos preocupa cuáles son los datos del árbol, ni su ordenación; sólo su estructura. Veremos un conjunto de funciones que definen la barrera de abstracción para trabajar con árboles binarios y después las utilizaremos para construir funciones de mayor nivel.

Barrera de abstracción

Ya hemos comentado que una de las características de los lenguajes de programación es que permiten construir abstracciones.
Llamamos barrera de abstracción al conjunto de funciones que permiten trabajar con una abstracción y aislan su implementación. Estas funciones definen la especificación de la abstracción: qué nos permite hacer la abstracción.
En el caso de las estructuras de datos, las funciones de la barrera de abstracción permiten crear nuevas estructuras y trabajar con ellas.
Cuando estamos trabajando con una estructura de datos o con cualquier otra abstracción no debemos saltar la barrera de abstracción. Las funciones superiores siempre deben usar las funciones proporcionadas por la barrera de abstracción. De esta forma no les afectan posibles cambios en la implementación de la barrera.
En informática se utilizan barreras de abstracción continuamente. Otros nombres alternativos que recibe este concepto son: capa de una aplicación, interfaz, API (Application Programming Interface).
Por ejemplo, las distintas capas de un sistema operativo, un driver de un dispositivo, un API accesible por web de una aplicación como Twitter o Google Maps o todo un nuevo lenguaje para hacer un (como OpenGL para crear gráficos 3D).
Muchos lenguajes de programación tienen elementos más elaborados para definir abstracciones (clases, métodos, paquetes, modificadores de visibilidad, etc.). En el caso de Scheme, la única forma de definir una barrera de abstracción es definiendo una lista de funciones.

Barrera de abstracción de árbol binario

Representamos la barrera de abstracción dibujando dos capas separadas por una lista de funciones. La capa inferior representa el código que implementa la barrera de abstracción. La capa superior representa el código que usa la barrera de abstracción.
En el caso de los árboles binarios, definimos la siguiente barrera:
Barrera de abstraccion
Las funciones de la barrera son las siguientes:
  • (make-bt dato izq-bt der-bt): crea un árbol binario con un dato, un árbol binario izquierdo y un árbol binario derecho
  • vacio-bt: constante que define el árbol binario vacío
  • (dato-bt bt): devuelve el dato de un árbol binario
  • (izq-bt bt): devuelve el árbol binario izquierdo
  • (der-bt bt): devuelve el árbol binario derecho
  • (hoja-bt? bt): comprueba si el árbol es una hoja (no tiene hijos)
  • (vacio-bt? bt): comprueba si el árbol es vacío
Usamos el convenio de que todas las funciones de la barrera terminan con el mismo sufijo. En esta caso -bt de binary tree. También usamos el convenio de llamar make- a la función que construye la estructura de datos.
Una vez que hemos definido las funciones (y suponiendo que alguien las haya implementado) podemos usarlas para trabajar con la abstracción. Por ejemplo vamos a construir un árbol binario y a obtener algunos de sus elementos.
    *
   / \
  +   8
 / \
5   3

(define t1 (make-bt 5 vacio-bt vacio-bt))
(define t2 (make-bt 3 vacio-bt vacio-bt))
(define t3 (make-bt '+ t1 t2))
(define t4 (make-bt 8 vacio-bt vacio-bt))
(define t5 (make-bt '* t3 t4))
(dato-bt t5) -> *
(dato-bt (izq-bt t5)) -> +
(dato-bt (izq-bt (izq-bt t5))) -> 5

Implementación de los árboles binarios

Necesitamos una estructura con la que podamos guardar 3 elementos: el dato de la raiz, el sub-árbol izquierdo y el sub-árbol derecho.
La forma natural en Scheme es utilizar una lista que contiene a esos tres elementos. Y el árbol binario vacio se puede representar entonces como una lista vacía.
Implementación del árbol binario
Vemos que con esta definición un árbol binario se puede expresar como una expresión-s. En el caso del ejemplo visto en la figura la expresión-s que define el árbol binario es:
(10 (5 (3 () ()) ()) (23 (12 () ()) (28 () ())))
La implementación de la barrera de abstracción en Scheme es la siguiente:
(define (make-bt dato izq der)
    (list dato izq der))
(define vacio-bt '())

(define (vacio-bt? btree) (null? btree))
(define (dato-bt btree) (car btree))
(define (izq-bt btree) (car (cdr btree)))
(define (der-bt btree) (car (cdr (cdr btree))))

(define (hoja-bt? btree)
   (and (vacio-bt? (izq-bt btree))
        (vacio-bt? (der-bt btree))))

Funciones de mayor nivel

Terminamos construyendo algunas operaciones sobre árboles binarios, definidas sobre la barrera de abstracción anterior.
  • (to-list-bt bt): devuelve una lista formada por los elementos del bt
  • (member-bt? x bt): busca el elemento x en un árbol binario ordenado
  • (insert-bt x bt): "inserta" (realmente, no modifica el árbol que se pasa como parámetro, sino que crea otro) un dato en un árbol binario ordenado
  • (insert-list-bt lista bt): "inserta" una lista en un árbol binario ordenado
  • (list-to-bt list): construye un árbol binario ordenado a partir de una lista
to-list-bt
La función (bt-to-list bt) construye una lista con los elementos contenidos en el árbol binario bt.
(define (to-list-bt btree)
   (if (vacio-bt? btree)
      '()
      (append (to-list-bt (izq-bt btree)) 
              (list (dato-bt btree))
              (to-list-bt (der-bt btree)))))
La recursión de esta función se basa en obtener el dato de la raíz, obtener de forma recursiva la lista de elementos de la rama izquierda y la lista de elementos de la rama derecha. La función append concatena todos los elementos. Dependiendo del orden en que los concatenemos aparecerán los elementos en pre-order, in-order o post-order.
(member-bt? x bt)
La función (member-bt? x bt) comprueba si un número x pertenece a un árbol binario ordenado bt. En el árbol binario ordenado todos los datos del hijo izquierdo son menores que el dato de la raíz y los del hijo derecho son mayores.
La búsqueda se implementa con la típica búsqueda dicotómica:
  • Si el dato de la raíz del árbol es menor que x, hacemos una llamada recursiva para comprobar si el dato está el subárbol derecho
  • Si el dato es mayor que x, buscamos x en el subárbol izquierdo
  • Si el dato de la raiz es igual que x devolvemos #t.
El coste de la búsqueda es log(n).
(define (member-bt? x bt)
   (cond 
      ((vacio-bt? bt) #f)
      ((= x (dato-bt bt)) #t)
      ((< x (dato-bt bt))
         (member-bt? x (izq-bt bt)))
      (else
         (member-bt? x (der-bt bt)))))
(insert-bt x bt)
La función insert-bt devuelve un nuevo árbol binario nuevo a partir de bt en el que se ha colocado el dato x en su posición correcta.
La función se basa en identificar en qué subárbol va el dato que estamos insertando. Si el dato es mayor que la raíz hay que ponerlo en el hijo derecho, por lo quec onstruimos un nuevo árbol con la misma raíz e hijo izquierdo que el actual y como hijo derecho ponemos el resultado de la llamada recursiva de insertar un dato en el árbol derecho (¡confía en la recursión!). Si el dato es menor hacemos lo contrario.
(define (insert-bt x bt)
   (cond
      ((vacio-bt? bt) (make-bt x vacio-bt vacio-bt))
      ((< x (dato-bt bt))
         (make-bt (dato-bt bt) 
                    (insert-bt x (izq-bt bt)) 
                    (der-bt bt)))
      ((> x (dato-bt bt))
         (make-bt (dato-bt bt)
                    (izq-bt bt)
                    (insert-bt x (der-bt bt))))
      (else bt)))
(insert-list-bt lista bt)
La función insert-list-bt se basa en la función anterior para insertar todos los elementos de una lista en un árbol binario. Al igual que en el caso anterior, hay que hacer notar que no existe tal inserción, sino que se construye un árbol nuevo que se devuelve como resultado.
(define (insert-list-bt lista bt)
   (if (null? lista)
      bt
      (insert-list-bt (cdr lista) 
          (insert-bt (car lista) bt))))
(list-to-bt lista)
Por último, la función list-to-bt construye una árbol binario ordenado a partir de una lista de números utilizando la función anterior.
(define (list-to-bt lista)
   (insert-list-bt lista vacio-bt))

Árboles genéricos

A diferencia de los árboles binarios, los árboles genéricos pueden tener un número de hijos variables. Se usan en un gran número de dominios en los que es necesario representar estructuras jerárquicas: procesadores de lenguaje, documentos XML, documentos HTML, etc.
La definición recursiva del tipo de datos árbol:
  • Un árbol genérico está formado por un dato y una lista de árboles hijos (también árboles)
La lista de árboles hijos puede ser vacía. De esta forma, a diferencia de los árboles binarios, en los árboles genéricos no usamos el concepto de árbol-vacio. Un árbol o nodo hoja es un árbol cuya lista de hijos es una lista vacía.
La siguiente figura representa un árbol genérico.
Implementación del árbol binario
Y su representación utilizando la definición anterior:
Implementación del árbol binario

Barrera de abstracción e implementación de árboles genéricos

La barrera de abstracción de los árboles genéricos se construye únicamente con las siguientes funciones:
  • (make-tree dato lista-hijos): construye un árbol a partir de un dato y una lista de hijos formada por árboles. La lista puede ser vacía.
  • (dato-tree tree): devuelve el dato de la raíz del árbol
  • (hijos-tree tree): devuelve una lista de árboles hijos
Vemos que utilizamos el sufijo -tree para todas las funciones.
Una estructura muy relevante es la lista de hijos, una lista de árboles. En las siguientes funciones vamos a utilizar esta estructura en bastantes ocasiones. Vamos por ello a darle un nombre y denominarla bosque. Decimos, por tanto, que la función hijos-tree es un bosque formado por los hijos del árbol.
¿Cómo implementamos los árboles? En Scheme es muy fácil, utilizando una lista. El primer elemento de la lista es el dato del árbol y el resto de la lista (otra lista) es la lista de hijos.
Las implementación de las funciones es la siguiente:
(define (make-tree dato lista-hijos)  (cons dato lista-hijos))
(define (dato-tree tree)  (car tree))
(define (hijos-tree tree)  (cdr tree))
El árbol anterior se puede construir con las siguientes instrucciones:
(define t1 (make-tree 5 '()))
(define t2 (make-tree 2 '()))
(define t3 (make-tree 3 '()))
(define t4 (make-tree 10 '()))
(define t5 (make-tree 12 '()))
(define t6 (make-tree '* (list t2 t3)))
(define t7 (make-tree '- (list t5)))
(define t8 (make-tree '+ (list t1 t6 t4)))
(define tree (make-tree '* (list t8 t7)))
Si expresamos el árbol en forma de lista podemos comprobar que es una expresión-s:
(+ (5) (* (2) (3)) (10))
De hecho, podríamos construirlo también utilizando directamente su formulación como expresión-s:

 
(define tree '(+ (5) (* (2) (3)) (10)))h
ttp://www.dccia.ua.es/dccia/inf/asignaturas/LPP/2010-2011/teoria/tema4.html#sec-3_2
en No hay comentarios:
Suscribirse a: Entradas (Atom)

6. Integración del intérprete

6.1. Lenguaje intermedio En esta sección se describirá la implementación de un intérprete de un lenguaje intermedio básico. El lenguaje...