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

1 1 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Глава 5. Системы исполнения функциональных программ 5.1. Интерпретаторы и компиляторы. Программа (функция) Аргументы Результат применения функции Интерпретатор Схема интерпретации Исходная программа (функция) Компилятор Результирующая (эквивалентная) программа Схема компиляции В обоих случаях исходная функция служит в качестве входных данных; в случае компиляции результатом также является функция. Для получения результата необходима интерпретация аппаратным или программным интерпретатором.

2 2 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ Представление функциональных программ. Вводим простой функциональный язык – расширенное лямбда-исчисление; покажем, что все основные конструкции языка типа Haskell могут быть легко скомпилированы в это расширенное лямбда-исчисление. 1. Константы – целые числа, логические значения. c : 0 25 TRUE 2. Константы – примитивные функции. f : + = IF TUPLE-n INDEX 3. Лямбда-выражения. (λx.e) : λx.+ x x 4. Применение примитивной функции или лямбда-выражения к аргументу. (e1 e2) : (λx.+ x x) 2 5. Простой блок. (let x = e1 in e2) : let f = (λx.+ x x) in (f 2) 6. Рекурсивный блок. (letrec x1 = e1; x2 = e2;... xn = en in e) : letrec f = λn.IF (= n 0) 1 (* n (f (- n 1))) in (f 5) Таким образом, в чистое лямбда-исчисление введены константы, функции, связывание имен со значениями и рекурсия.

3 3 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ Представление функциональных программ. Компиляция с языка Haskell в расширенное лямбда-исчисление. 1. Исключаем все конструкции, связанные с определением и контролем типов: type, data, ::, class, instance 2. Многие конструкции переводятся (почти) без изменения: константа: c c примитивная функция: f f лямбда-выражение: (\x->e) (λx.e'), где e' – результат компиляции e переменная: x x применение функции: (e1 e2) (e1' e2'); e1+e2 (+ e1' e2') блоки: (e where f = e1) (let f = e1' in e') 3. Кортежи переводятся в применения примитивной функции TUPLE-n : кортеж: (e1, e2, e3) (TUPLE-3 e1' e2' e3') 4. Применение конструкторов переводится в применение примитивной функции TUPLE-n, первым аргументом которого служит номер конструктора в определении типа: например: [3] 3 : [] (TUPLE (TUPLE-1 0)) 5. Многие конструкции, такие как фильтры, арифметические прогрессии и т.п. переводятся в вызовы соответствующих примитивных функций.

4 4 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Компиляция с языка Haskell в расширенное лямбда-исчисление. 6. Определения функций, включающие образцы и условия, сначала переводятся в лямбда-выражения, содержащие конструкцию case в определяющем выражении. например: assoc x ((y,e):lst) | x == y = e | otherwise = assoc x lst assoc x [] = [] переходит в: assoc = \a1 -> \a2 -> case (a1, a2) of (x, ((y,e):lst)) | x == y -> e | otherwise -> assoc x lst (_, []) -> [] Конструкция case затем транслируется в расширенное лямбда-исчисление (далее). 7. Программный модуль (серия определений) транслируется в заголовок блока letrec. name_1 = expr_1 name_2 = expr_2... name_k = expr_k letrec name_1 = expr_1'; name_2 = expr_2';... name_k = expr_k' in Перед исполнением программы вычисляемое выражение компилируется и помещается в блок letrec после in.

5 5 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Компиляция case -выражения case param of pattern_1 | cond_11 -> expr_11 | cond_12 -> expr_12... pattern_2 | cond_21 -> expr_ pattern_k | cond_k1 -> expr_k1... letrec f1 = λa.IF (образец_1) let (связывание_1) in IF cond_11' expr_11' IF cond_12' expr_12'... (f2 a) (f2 a) f2 = λa.IF (образец_2) let (связывание_2) in IF cond_21' expr_21' IF cond_22' expr_22'... (f3 a) (f3 a)... fk = λa.IF (образец_k)... error error in f1 param'

6 6 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Компиляция сопоставления с образцом и связывания case y) of ([], (e:_)) -> expr Аргумент arg, удовлетворяющий образцу, должен иметь вид: ( [], ( (:) e _ )) (TUPLE-2 (TUPLE-1 0) (TUPLE-3 1 e foo)) (AND (EQ (INDEX 1 (INDEX 1 arg)) 0) (EQ (INDEX 1 (INDEX 2 arg)) 1)) arg[1,1] == 0 && arg[2,1] == 1 Возможно также сопоставление с константой: case arg of [25] -> expr ((:) 25 []) arg[1] == 1 && arg[2] == 25 && arg[3,1] == 0 Связывание: x = arg[1]; y = arg[2]; e = arg[2,2]

7 7 Кубенский А.А. Функциональное программирование. Глава 5. Системы исполнения функциональных программ. Представление программ расширенного лямбда-исчисления data Expr = Integral Integer | Logical Bool -- константы | Function String -- примитивные функции | Variable String -- переменные | Lambda String Expr -- лямбда-выражение | Application Expr Expr -- применение функции | Let String Expr Expr -- простой блок | Letrec [(String, Expr)] Expr -- рекурсивный блок например: let plus = (λx.λy.x+y) in (plus 1 2) будет представлено в виде: (Let "plus" (Lambda "x" (Lambda "y" (Application (Application (Function "+") (Variable "x")) (Variable "y")))) (Application (Application (Variable "plus") (Integral 1)) (Integral 2)) )