Презентация на тему Системы исполнения функциональных программ

программ.
Рассмотрим программу вычисления факториала.
Пример программы.
begin f := 1;

В начальном состоянии существенно только значение переменной n; в конце работы результат определяется значением переменной f.

Прежде всего, переведем программу в вид, удобный для обработки.

data Expression = { представление выражений } data Operator = { представление операторов } data Context = { представление контекста переменных }

Два способа обработки и исполнения программы:

Интерпретация:

interpret :: Operator -> Context -> Context

Компиляция:

compile :: Operator -> (Context -> Context)

На самом деле оба способа представлены одной и той же карринговой функцией!

программ.
Представление выражений и программ.
data Expression = Integral Int |

data Operator = Skip | Assignment String Expression | Sequence [Operator] | If Expression Operator Operator | While Expression Operator

type Context = [(String, Expression)]

interpret :: Operator -> Context -> Context

eval :: Expression -> Context -> Expression

eval v@(Integral n) _ = v eval v@(Logical b) _ = v eval (Variable x) ctx = assoc x ctx eval (Unary op ex) ctx = intrinsic op [eval ex ctx] eval (Binary e1 op e2) ctx = intrinsic op [eval e1 ctx, eval e2 ctx]

intrinsic "+" [(Integral a), (Integral b)] = Integral (a+b)

intrinsic "-" [(Integral a)] = Integral (-a)

intrinsic "and" [(Logical a), (Logical b)] = Logical (a && b)

intrinsic :: String -> [Expression] -> Expression

программ.
Исполнение операторов.
replace :: String -> Expression -> Context ->

replace x val = map (\(y,v) -> (y,if x == y then val else v))

replace "f" (Integral 20) [("n", (Integral 4)), ("f", (Integral 5))]

Например:

даст в результате

[("n", (Integral 4)), ("f", (Integral 20))]

interpret :: Operator -> Context -> Context

interpret Skip ctx = ctx interpret (Assignment x expr) ctx = replace x (eval expr ctx) ctx interpret (Sequence []) ctx = ctx interpret (Sequence (s:seq)) ctx = interpret (Sequence seq) (interpret s ctx) interpret (If expr s1 s2) ctx = case (eval expr ctx) of (Logical True) -> interpret s1 ctx (Logical False) -> interpret s2 ctx interpret oper@(While expr s) ctx = case (eval expr ctx) of (Logical True) -> interpret oper (interpret s ctx) (Logical False) -> ctx