Alumno: Saul Adan Aguilar Vera

Por ejemplo: mult (1+2,2+3)

Aplicamos el primer + mult (3,2+3) Aplicamos el + mult (3,5)

Aplicamos mult 3*5

Aplicamos *15

Esta estrategia asegura que los parámetros de una función están completamente evaluados antes de que la función sea aplicada. Por eso se dice que los parámetros se pasan por valor

• De adentro hacia afuera o call-by-value: esta estrategia elige el redex que esta “más a dentro” entendiendo por esto al redex que no contiene otro redex. Si existe más de un redex que cumple dicha condición se elige el que está más a la izquierda.

• De afuera hacia a dentro o call-by-name: elige el redex que está “más afuera” entendiendo por esto al redex que no está contenido en otro redex. Si existe más de un redex que cumple dicha condición se elige el que está más a la izquierda.

Alumno: Saul Adan Aguilar Vera

Unidad 3. EVALUACION PEREZOSA

3.1 Estrategia de la evaluación perezosa

3.2 Técnicas de la programación funcional perezosa

Ejemplo

Aplicamos inf

1+inf

Aplicamos inf (porque + es estricta) 1+(1+inf)

Aplicamos inf (porque + es escritura) …1+(1+(1+(1+(1+(1+….+inf)))))

Por ende, está evaluación nunca terminaría.

Sabiendo que

Fst(x,_)=x

Consideremos la expresión fst(0,inf)

• Evaluaciones que no terminan

Tenga en cuenta la siguiente definición

inf=1+inf

Intentar reducir la expresión inf siempre nos va a dar como resultado una expresión mas y mas grande (independientemente de la estrategia de evaluacio que usemos) inf

Datos no deterministas

Requiere tipo de datos diferente como son

Data list m a = nil(cons(m a)(m(list a))

Puede representar lista perezosa no determinista

Cons[2][NII.cons [1]]::list[]int

Los argumentos de cons representan computación no determinista, permute y lsSorted se puede adaptar a la lista de tipo permute y genera permutaciones perezosamente los rendimientos IsSorted [true, false] es aplicada por encima de la lista(s)

Búsqueda no determinística

Un algoritmo no determinista

• Ofrece muchos posibles resultados.

• Emplean modelos de computación tales como la máquina de Turing probabilística, que no son deterministas

• Puede simularse utilizando la lista de éxitos como por ejemplo:

• Soluciones x=x, x candidatos, validos

En el no-determinismo existen varias técnicas como son:

• Técnica de backtracking (Prolog): Si una alternativa “falla”, el flujo retorna hasta la última decisión e intenta otra.

• Técnica de guardias (guards): si más de una es cierta, se escoge cualquiera de ellas.

• Técnica de aprendizaje reforzado(A-LISP): Recordar decisiones exitosas y aumentar su prioridad así como considerar las decisiones en el contexto del estado mutable

3.2 TECNICAS DE PROGRAMACION FUNCIONAL PEREZOSA

La semántica adoptada para el no determinismo es la de elección en la invocación (call-time choice), por resultar más natural para la programación y más eficaz en la ejecución al corresponderse con el mecanismo de compartición.

Ejercicio

Dado un numero entero separar el primer digito haciendo uso de la función mod n 10 para luego sumar al cociente de la división del numero n entre 10,(div n 10).

Ejercicios en Haskell

Haskell es un lenguaje de programación estandarizado multi-propósito funcional tipificado, con funciones de orden superior, polimorfismo, sistema de clases de tipos, evaluación perezosa... con semánticas no estricas y fuertes tipificación estática

Usemos call-by-name:

Fst(0,inf)

Aplicamos fst

0

Si existe alguna secuencia de evaluación que haga terminar la evaluación de la expresión entonces con la estrategia call-by-name también se termina la evaluación.

Usando la estrategia call-by-value

Fst(0,inf)

Aplicamos inf

Fst(0,1+inf)

Aplicamos inf

Fst(0,1+(1+inf))

Aplicamos inf

Fst(0,1+(1+inf)))

Aplicamos inf

…

Usando call-by-value la evaluación de la expresión no termina.

Estrategias básicas

Una expresión que consta de una función aplicada a uno o mas parámetros y que puede ser “reducida” aplicando dicha función la vamos a llamar Redex (Reducible Expression).

Tipos:

* De adentro hacia afuera o call-by-value

* De afuera hacia a dentro o call-by-name

* Evaluaciones que no terminan

Ejemplo: mult(1+2,2+3)

Aplicamos mult (1+2)*(2+3)

Aplicamos el primer + 3*(2+3)

Aplicamos + 3*5

Aplicamos * 15

El operador * y el + no pueden ser aplicados hasta que sus dos parámetros hayan sido evaluados a números.

A las funciones que cumplen con esta propiedad las vamos a llamar funciones estrictas.

Las estrategias de la evaluación se dividen en dos grupos básicos, estrictos y no estrictos, basados en cómo se manejan los argumentos de una función.

3.1 Estrategia de la evaluación perezosa

Una estrategia de evaluación es un conjunto de reglas para evaluar expresiones en un lenguaje de programación.

Una estrategia de evaluación define cuando y en qué orden los argumentos a una función son evaluados, cuando se sustituyen en la función, y lo que la sustitución se forman.