1 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. 5.3. Eval / Apply-интерпретатор Интерпретация, основанная. - презентация

1 1 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ Eval / Apply-интерпретатор Интерпретация, основанная на контексте. Контекст – иерархический ассоциативный список связей имен переменных со значениями. type Context = [(String, Expr)] assoc :: String -> Context -> Expr assoc x ((y,e):ctx) | x == y = e | otherwise = assoc x ctx eval :: Context -> Expr -> Expr apply :: Expr -> Expr -> Expr -- вычисление значения выражения в контексте (приведение к СЗНФ): -- вычисление результата применения функции к аргументу: interpreter :: Expr -> Expr -- интерпретация: interpreter = eval []

2 2 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ Eval / Apply-интерпретатор (продолжение) data Expr = Integral Integer | Logical Bool | Function String -- константы | Variable String -- переменная | Lambda String Expr -- лямбда-выражение | Application Expr Expr -- применение функции | Let String Expr Expr | Letrec [(String, Expr)] Expr -- блоки | Closure String Expr Context -- замыкание | Oper Int String [Expr] -- сечение eval _ _) = e eval _ _) = e eval _ (Function f) = Oper (arity f) f [] eval ctx (Lambda x e) = Closure x e ctx eval _ _ _ _) = e eval _ _ _ _) = e eval ctx (Variable x) = assoc x ctx eval ctx (Application f a) = apply (eval ctx f) (eval ctx a) apply (Closure x body ctx) arg = eval nc body where nc = (x, arg) : ctx apply (Oper n f la) a | n == 1 = intrinsic f newListArgs | otherwise = Oper (n-1) f newListArgs where newListArgs = la ++ [a]

3 3 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ Eval / Apply-интерпретатор (продолжение) eval ctx (Let x arg body) = eval newCtx body where newCtx = ((x, (eval ctx arg)):ctx) let x=arg in body ~ (λx.body) arg (Let x arg body) ~ (Application (Lambda x body) arg) eval ctx (Let x arg body) = apply (eval ctx (Lambda x body)) (eval ctx arg) = apply (Closure x body ctx) (eval ctx arg) eval ctx (Letrec args body) = eval newCtx body where newCtx = (map (\(x,arg) -> (x, eval newCtx arg)) args) ++ ctx

4 4 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Энергичный vs. ленивый интерпретатор Механизм интерпретации определяет реализованную схему! eval ctx (Application f a) = apply (eval ctx f) (eval ctx a) Вычисление аргумента происходит до вызова a pply при энергичной реализации, но задерживается до первого обращения к нему при ленивой реализации инструментального языка. Если инструментальный язык энергичный, то дополнительные проблемы – это: реализация стандартной функции I F ; реализация рекурсивного блока. data Expr =... | If Expr Expr Expr -- условное выражение eval ctx (If p t e) = if (eval ctx p) == (Logical True)then eval ctx t else eval ctx e eval ctx (If p t e) = eval ctx (if eval ctx p then t else e) «Зацикленный» контекст, использующийся для реализации рекурсивного блока, вообще не реализуем в чисто энергичном функциональном языке! В языке Haskell энергичный интерпретатор можно реализовать с помощью «строгих» применений: eval ctx (Application f a) = (apply $ (eval ctx f)) $ (eval ctx a)

5 5 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Реализация встроенных функций intrinsic "+" [Integral(a), Integral(b)] = Integral (a+b) intrinsic "-" [Integral(a), Integral(b)] = Integral (a-b) intrinsic "*" [Integral(a), Integral(b)] = Integral (a*b) intrinsic "/" [Integral(a), Integral(b)] = Integral (a `div` b) intrinsic "EQ0" [Integral(a)] = Logical (a==0) intrinsic "SUCC" [Integral(a)] = Integral (a+1) intrinsic "PRED" [Integral(a)] = Integral (a-1) apply (Oper nArgs f argsList) arg | nArgs == 1 = intrinsic f newList | otherwise = Oper (nArgs-1) f newList where newListArgs = argsList ++ [arg] eval _ (Function f) = Oper (arity f) f [] arity "+" = 2 arity "-" = 2 arity "*" = 2 arity "/" = 2 arity "EQ0" = 1 arity "SUCC" = 1 arity "PRED" = 1

6 6 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Пример интерпретации простой программы На языке Haskell: sqr :: Integer -> Integer sqr x = x*x interpret: sqr 3 В расширенном лямбда-исчислении: let sqr = λx.* x x in (sqr 3) prog :: Expr prog = (Let "sqr" (Lambda "x" (Application (Application (Function "*) (Variable "x")) (Variable "x"))) (Application (Variable "sqr") (Integral 3))) Представление в виде выражения типа Expr в языке Haskell: interpreter prog Что получится в результате вызова?

7 7 Пример интерпретации простой программы interpreter prog eval [] prog eval [] (Let "sqr" (Lambda...) (Application...)) apply (Closure "sqr" (Application...) []) (eval [] (Lambda "x"...)) apply (Closure "sqr" (Application...) []) (Closure "x" (Application...) []) prog = (Let "sqr" (Lambda "x" (Application (Application (Function "*") (Variable "x")) (Variable "x"))) (Application (Variable "sqr") (Integral 3))) eval [("sqr",(Closure "x" (Application...) []))] (Application (Variable "sqr") (Integral 3)) apply (eval [("sqr",(Closure "x" (Application...) []))] (Variable "sqr") (eval [("sqr",(Closure "x" (Application...) []))] (Integral 3)) apply (Closure "x" (Application...) []) (Integral 3)) eval [("x",(Integral 3)] (Application (Application (Function "*") (Variable "x")) (Variable "x")) apply (eval [("x",(Integral 3)] (Application (Function "*") (Variable "x"))) (eval [("x",(Integral 3)] (Variable "x")) Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ.

8 8 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Пример интерпретации простой программы (продолжение) apply (apply (eval [("x",(Integral 3)] (Function "*")) (eval [("x",(Integral 3)] (Variable "x"))) (Integral 3) apply (apply (Oper (arity "*") "*" []) (Integral 3)) (Integral 3) apply (apply (Oper 2 "*" []) (Integral 3)) (Integral 3) apply (Oper 1 "*" [(Integral 3)]) (Integral 3) intrinsic "*" [(Integral 3),(Integral 3)] (Integral 9) apply (eval [("x",(Integral 3)] (Application (Function "*") (Variable "x"))) (eval [("x",(Integral 3)] (Variable "x"))