Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Implementación de Lenguajes Funcionales (ppt)




Enviado por Pablo Turmero



Partes: 1, 2


    Monografias.com

    1
    Clasificación de los Lenguajes Funcionales

    Según el método de evaluación
    Evaluación estricta (eaguer)
    Evaluación diferida (lazy, perezosa)
    Según la asignación
    Lenguajes funcionales puros o sin asignación
    Lenguajes funcionales con asignación
    Máquina abstracta para un lenguaje con evaluación eager (directa)
    FAM
    máquina basada en ámbitos
    Máquina abstracta para un un lenguaje con evaluación lazy (diferida)
    G-Machine
    máquina basada en grafos y combinadores.

    Monografias.com

    2
    Implementación de la Evaluación Estricta
    Un lenguaje funcional con evaluación estricta se parece mucho a un lenguaje imperativo por
    Las operaciones se realizan en el orden que indica el programador
    La evaluación estricta es compatible con la asignación
    Idea de implementación
    Modificar la máquina abstracta para lenguajes imperativos para que pueda ejecutar lenguajes funcionales con evaluación estricta.
    Problemas a resolver con las modificaciones
    Implementación óptima de la recursividad en cola.
    Funciones locales validas fuera de su entorno de definición
    Clausuras (código función+ámbito)
    Acceso a ámbitos de funciones inactivas

    Monografias.com

    3
    Recursividad en Cola: Importacia
    Problema de los lenguajes funcionales puros
    Un lenguaje funcional puro no tiene asignación. Por lo tanto, los cambios de estado solo se pueden realizar creando nuevas variables, o sea, realizando llamadas a funciones.
    Un programa que interaccione con el mundo real ha de cambiar su estado para representar el nuevo estado del mundo.
    Si para cada llamada a función se utiliza espacio de pila, el resultado es que el programa llenará la pila.
    Solución: Optimización de la recursividad en cola
    La interacción se implementa en un lenguaje imperativo con un bucle que procesa los eventos que vienen del mundo. En un lenguaje funcional se implementa con una función que procesa un evento y que al final se llama recursivamente para procesar en siguiente evento (recursividad en cola).
    Objetivo: Conseguir que la última llamada que realiza una función no consuma pila.

    Monografias.com

    4
    Recursividad en Cola: Problema
    Última llamada en un lenguaje imperativo
    void f(a,b) {
    int c,d,e;

    g(c,d)
    }

    b
    a
    PC f
    ED
    c
    d
    e
    d
    c
    Bloque de
    activación de f
    Parámetros de g
    Estado de la pila
    justo antes de
    llamar a g
    ( parametros de g
    en la pila)
    PC f
    d
    c
    Pila
    anterior
    Pila
    anterior
    Contenido de la pila que necesita
    la llamada a g. El bloque de
    activación de f se puede eliminar
    ya que lo último que se hace es
    llamar a g.
    Problema: después del bloque de
    activación de f se encuentran los
    parámetros de g

    Monografias.com

    5
    Recursividad en Cola: Solución
    Usar dos pilas
    Pila de contexto con los bloques de activación un pila de parámetros.
    De esta forma se evita que los parámetros impidan la eliminación del bloque de activación antes de la última llamada
    Los parámetros se han de copiar de la pila de argumentos al bloque de activación o ámbito de la función
    Pila de
    Contexto
    Pila de
    Argumentos
    EP
    CSP
    AP

    Monografias.com

    6
    Llamada a una Función (Ambito en la Pila)
    Código Llamada
    Calcular los argumentos y ponerlos en la pila de argumentos
    Llamar a la función

    Código Función
    Guardar EP en la pila
    Copiar argumentos de la pila de argumentos a la pila de contexto
    Inicializar espacio de variables
    Cuerpo de la función
    Poner el valor de retorno en un registro
    Eliminar de la pila variables y argumentos
    Recuperar EP
    retornar

    Monografias.com

    7
    Ejemplo de Secuencia de Llamada
    Fun f(x,y)=>{ Var A; x+y; }
    Llamada f(10,20)
    Código llamada
    PushArg 10
    PushArg 20
    Call f
    Código función
    PushCon EP
    EP=SP
    PopArg VR
    PushCon VR
    PopArg VR
    PushCon VR
    PushCon NIL
    Cuerpo función
    SP=EP
    PopCon EP
    Ret

    Monografias.com

    8
    Aplicación de la Recursividad en Cola
    Función que realiza una llamada
    Fun f(x)={… g(10,20); }
    Código sin optimizar
    PushArg 10
    PushArg 20
    Call g
    SP=EP
    PopCon EP
    Ret
    Eliminar bloque de activación de f antes de llamar
    PushArg 10
    PushArg 20
    SP=EP
    PopCon EP
    Call g
    Ret
    Código optimizado
    PushArg 10
    PushArg 20
    SP=EP
    PopCon EP
    Jmp g

    Monografias.com

    9
    Definiciones Anidadas y Clausuras
    En los lenguajes funcionales son básicas las siguientes características
    Definición anidada de funciones
    Esta implica el uso de display
    Poder tratar cualquier función como un valor (apuntadores a funciones)
    Para que una función local a otra pueda referenciarse desde donde queramos hay que asociarle su ámbito de definición. Esta asociación la realizan las clausuras
    A través de una clausura es posible acceder a un ámbito de una función después de que esta haya acabado su ejecución
    Funciones lambda o anónimas
    Son necesarias para facilitar la escritura de llamadas a funciones de orden superior, pero no obligan a modificar la máquina abstracta una vez consideradas las características anteriores
    Son funciones definidas localmente
    Son funciones tratadas como un valor

    Monografias.com

    10
    Implementación de Clausuras
    Una clausura es
    Apuntador a la entrada del código de la función
    Ambito de la función donde se creo
    Display o valor de EP cuando se creo la clausura
    Fun f(x)={
    Var y;
    Fun g(a,b)=
    {
    Var z;

    }

    g
    }
    PC
    EP
    x
    y
    Bloque de
    activación de f
    PC
    EP
    EP f
    a
    b
    z
    Bloque de
    activación de g
    Display
    EP
    EP
    Entrada g
    EP def
    Clausura
    Clausura de g

    Monografias.com

    11
    Ambitos en el Heap
    La función f retorna la clausura de g y al llamar a esta clausura se puede acceder a las variables de f. Por lo tanto, no se puede eliminar el ámbito de f al finalizar su ejecución
    Solución:
    Guardar el ámbito de f en el heap para que no se elimine al salir de f
    Los ámbitos en el heap existirán hasta que no se pueda acceder a ellos
    nulo
    x
    y
    EP
    PC
    EP
    Pila
    anterior
    Env
    SP
    Contenido de la pila
    al llamar a f con el ámbito
    en el heap
    Nodo con el ámbito de f
    en el heap

    Monografias.com

    12
    Llamada a una Función con el ámbito en el Heap
    Código Llamada
    Calcular los argumentos y ponerlos en la pila de argumentos
    Llamar a la función
    Código Función
    Guardar EP en la pila
    Crear nodo de ámbito en el heap e inicializarlo
    EP apunta al nodo de ámbito
    Copiar argumentos de la pila de argumentos al ámbito
    Cuerpo de la función
    Poner el valor de retorno en un registro
    Recuperar EP de la pila de contexto
    retornar

    Monografias.com

    13
    Ámbito en la Pila y en el Heap
    PC
    EP
    Display
    Argumentos
    Variables
    EP
    Env
    nulo
    Display
    Argumentos
    Variables
    EP
    PC
    EP
    Pila de contexto
    Heap
    Ambito en el Heap
    Ambito en la pila
    Pila de contexto
    CSP
    CSP

    Monografias.com

    14
    Llamada a una Clausura
    Código Llamada
    Calcular los argumentos y ponerlos en la pila de argumentos
    Clo=Clausura
    Llamar a la función
    Código Función
    Guardar EP en la pila de contexto
    Crear el Display a partir del EP de Clo
    Copiar argumentos de la pila de argumentos a la pila de contexto
    Inicializar espacio de variables en la pila de contexto
    Cuerpo de la función
    Poner el valor de retorno en un registro
    Recuperar EP de la pila de contexto
    retornar

    Monografias.com

    15
    Implementación de un Interprete de LISP Basado en Precompilación
    Organización de la memoria
    EP: apuntador al ámbito activo
    CSP: apuntador a la cabeza de la pila de contexto
    ASP: apuntador a la cabeza de la pila de argumentos
    PC: contador de programa
    Heap
    Pila de
    Contexto
    Pila de
    Argumentos
    EP
    CSP
    AP
    PC

    Monografias.com

    16
    Pila de Contexto y Pila de Argumentos
    En la pila de contexto se guarda
    PC de retorno
    Bloques de ámbito (bloques de activación de las funciones)
    En la pila de argumentos se guarda
    Los argumentos de las funciones
    El valor de retorno
    Los resultados intermedios de la evaluación de expresiones
    En el Heap se guarda
    Nodos de listas, símbolos, paquetes, etc.
    Código de las funciones (puede estar en un segmento de memoria aparte si no puede variar)
    Clausuras
    Bloques de ámbito accesibles desde fuera de la función que los ha creado

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter