Eder

Derivaci´n de programas o

13 de septiembre de 2010

Derivaci´n de programas o

Derivaci´n y transformaci´n de programas o o

Derivaci´n de programas o
Desarrollar la prueba de correci´n del programa y el programa o conjuntamente. Incluye transformaci´n o

Transformaci´n de programas o
Consiste en obtener un programa a partir de otro preservando su sem´ntica. a En general, elprograma que se obtiene es m´s eficiente, pero a no necesariamente. La transparencia referencial facilita la transformaci´n de o programas.

Derivaci´n de programas o

Transformaci´n o

Existe una gran variedad de t´cnicas de transformaci´n de e o programas cuyo objetivo es optimizar c´digo. o Veremos algunas:
Recursi´n de cola. o Tupling. Fusi´n. o

Derivaci´n de programas o

Recursi´n decola o

Un aspecto que influye en la ineficiencia de algunas funciones recursivas es el tiempo asociado a las llamadas recursivas. Una funci´n es recursiva de Cola cuando no hay ning´n o u c´mputo despu´s de la llamada recursiva. o e La recursi´n de cola ahorra espacio y tiempo si el compilador o optimiza autom´ticamente las llamadas recursivas de cola. a La importancia de la recursi´n de cola esque cuando se o realiza una llamada de una funci´n de este tipo, la posici´n o o del return de la funci´n llamadora necesita grabarse en la pila o de ejecuci´n; cuando la funci´n recursiva retorna, o o continuar´ directamente a partir de la posici´n de retorno a o grabada previamente.

Derivaci´n de programas o

Ejemplo 1

fact 0 = 1 fact (n + 1) = n ∗ fact (n) ¿por qu´ es ineficiente? e ¿C´mopodemos transformarla a una recursiva de cola? o

Derivaci´n de programas o

Ejemplo 1

fact 0 = 1 fact (n + 1) = n ∗ fact (n) ¿por qu´ es ineficiente? e ¿C´mo podemos transformarla a una recursiva de cola? o Proponemos una especificaci´n para ifact (generaliza la o funci´n factorial y es recursiva de cola) y derivamos una o definici´n que la satisfaga. o ifact r n = r ∗ fact n

Derivaci´nde programas o

Ejemplo 1

fact 0 = 1 fact (n + 1) = n ∗ fact (n) ¿por qu´ es ineficiente? e ¿C´mo podemos transformarla a una recursiva de cola? o Proponemos una especificaci´n para ifact (generaliza la o funci´n factorial y es recursiva de cola) y derivamos una o definici´n que la satisfaga. o ifact r n = r ∗ fact n Luego escribimos fact en t´rminos de ifact. e fact n = ifact 1 n

Derivaci´nde programas o

Transformaci´n o
Caso n = 0 : ifact r 0 {espec} r∗fact .0 = {fact.1} r∗1 = {aritm´tica } e r ifact r n = {espec} r∗fact n = {fact.2 } r∗(n∗fact (n−1)) = {asoc. de ∗} (r∗n)∗fact (n−1) = {espec} ifact (r∗n) (n−1) =
Derivaci´n de programas o

Caso n > 0:

Resultado

ifact r 0 = r ifact r n = ifact (r ∗ n) (n − 1) fact n = ifact 1 n

Derivaci´n de programas o

Ejemplo2

reverse [] = [] reverse (x:xs) = reverse xs ++ [x] ¿por qu´ es ineficiente? e

Derivaci´n de programas o

Ejemplo 2

reverse [] = [] reverse (x:xs) = reverse xs ++ [x] ¿por qu´ es ineficiente? e Proponemos la siguiente generalizaci´n: o irev rs xs = reverse xs ++ rs

Derivaci´n de programas o

Ejemplo 2

reverse [] = [] reverse (x:xs) = reverse xs ++ [x] ¿por qu´ es ineficiente? eProponemos la siguiente generalizaci´n: o irev rs xs = reverse xs ++ rs Escribimos reverse en t´rminos de irev: e reverse xs = irev [] xs

Derivaci´n de programas o

Transformaci´n o
irev rs [] {espec.} reverse []++rs = {reverse.1} []++rs = {++.1 } rs Caso (x:xs): irev rs (x: xs) = {espec.} reverse (x: xs)++rs = {reverse.2} ( reverse xs ++ [x])++rs = {asoc. (++)} reverse xs ++ ([x]++rs) ={++.1 y 2} reverse xs ++ (x:rs) = {espec.} irev (x: rs ) xs =
Derivaci´n de programas o

Caso []

Tupling

Generaliza la funci´n incluyendo un resultado adicional. o Veamos un ejemplo: fib 0 = 1 fib 1 = 1 fib n = fib (n − 1)

+

fib (n − 2)

Derivaci´n de programas o

Tupling

Generaliza la funci´n incluyendo un resultado adicional. o Veamos un ejemplo: fib 0 = 1 fib 1 = 1 fib...