1 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Глава 3. Стили функционального программирования 3.1. Язык ЛИСП (John McCarthy, 1960) Две формы представления данных: атомы: A 123 B_12 + T NIL списки: (A) (PLUS 12 25) (LAMBDA (X Y) (PLUS X Y)) () С помощью атомов представляются «атомарные» объекты – числа, символы и логические значения; С помощью списков представляются составные объекты – структуры, выражения и функции; Вызов функции – применение функции к списку аргументов: (PLUS 12 15) (PLUS (MINUS 12 5) 15) (COND ((LT X Y) (MINUS 0 1)) ((EQ X Y) 0) (T 1)) (QUOTE (LAMBDA (X) (PLUS 1 X)))' (LAMBDA (X) (PLUS 1 X)) (LET (FACT 5) (FACT '(LAMBDA (N) (COND ((EQ N 0) 1) (T (MULT N (FACT (MINUS N 1))))))) )

2 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Основные примитивные функции в ЛИСПе Арифметические и логические функции: PLUS, MULT, LE, EQ, AND Специальные функции: COND, QUOTE, LET Функции обработки списков: CAR, CDR, CONS (CONS 'A '(B C)) (A B C) (CONS 'A (CONS 'B NIL)) (A B) (CAR '(A B C)) A (CDR '(A B C)) (B C) (CDR '(A)) NIL (CONS '(A B) '(C D)) ((A B) C D) (CAR (CDR '(A B C D))) B (CADDR '(A B C D))) C (CONS 'LAMBDA (CONS '(X) '((PLUS X 1)))) (LAMBDA (X) (PLUS X 1)) Функции высших порядков в ЛИСПе: (DEFINE MAP (LAMBDA (F L) (COND (L (CONS (F (CAR L)) (MAP F (CDR L)))) (T NIL) ))) (MAP '(LAMBDA (X) (PLUS X 1)) '(1 3 8)) (2 4 9)

3 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Подведение итогов: основные черты и особенности языка ЛИСП Простой синтаксис – скобочная запись данных и программ. Энергичная схема вычислений (кроме специальных функций). Нет образцов и конструкторов – определение функций построено на суперпозиции примитивных и ранее определенных функций; построение сложных объектов также использует функцию CONS. Возможность определения функций высших порядков, в которых аргументами и/или результатом работы являются функции. Возможность динамического построения фрагментов программы непосредственно в ходе ее выполнения. Определение «контекста переменных» с помощью блочной структуры (LET). Язык ЛИСП послужил прообразом и идейной основой большой группы языков. В той или иной степени он лежит в основе всех современных функциональных языков программирования и многих других языков.

4 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования Система комбинаторного программирования FP (John Backus, 1978) Теоретически любую функцию можно получить из базовых с помощью комбинаторных преобразований. FP – система, реализующая этот принцип. Набор констант не определен, но предполагается, что есть списки и логические значения. Набор базовых функций не определен, но предполагается, что он достаточно богат. Также предполагается, что принята энергичная схема вычислений (все функции – строгие). Определим следующие комбинаторы: Композиция f g ( f g) x = f (g x) Условие f g; h ( f g; h) x = Константа k k x = Конструкция [ f 1, f 2,..., f n ] [ f 1, f 2,..., f n ] x = { g x, если f x - истинно h x, если f x - ложно не опр., если f x – не определено { k, если x – определено не опр., если x – не определено

5 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Еще несколько важных комбинаторов Отображение α f (α f) : = Правая вставка / f (/ f) : = x (/ f) : = f : > Левая вставка \ f (\ f) : = x (\ f) : = f :, x n > (map) (foldr) (foldl) Вариант правой вставки с базовой константой / k f (/ k f) : = k (/ k f) : = f : > Вариант левой вставки с базовой константой \ k f (\ k f) : = k (\ k f) : = f :, x n >

6 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Определим типичный язык программирования на основе FP-системы Введем набор констант и базовых функций Константы: Функции: Арифметические функции: +, -, *, add1, mul5, sub3: + : = 7 add1 : 3 = 4 Логические функции: =, /=,,..., and, or, not,... eq0, neq5, lt2: = : = F = T lt2 : 5 = T or : = T Функции-селекторы: 1, 2,..., 1r, 2r,...: 2 : = 5 1r : = 8 Тождественная функция: id: id : = в программах в явном виде не присутствуют! гетерогенные списки ( ,, T>,…) целые числа ( 0, 1, 2,..., -1, -2,...); логические значения ( T и F ); символы ( 's', '*',…);

7 hd : = 3 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Функции обработки списков tl : = hr : = 8 tr : = cons : > = consr :, 3> = null : = T null : = F distl : > =,, > distr :, 3> =,, > ι : 5 = ι : 0 = Программа в FP – это определение функций: def sqr = * [id, id] sqr : 5 = * : = 25 def pow4 = * [sqr, sqr] pow4 : 3 = * : = 81

8 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Примеры программ в языке программирования на базе FP Haskell: fact n = if n = 0 then 1 else n * fact (n-1) FP: def fact = eq0 1; (* [id, fact (- [id, 1])]) def fact = (/ 1 *) ι Haskell: test elem [] = False test elem (x:lst) | x == elem = True | otherwise = test elem lst FP: def test = null 2 F; eq [1, hd 2] T; test [1, tl 2] def test = (/ F or) (α eq) distl Haskell: fact n = foldr (*) 1 [1..n] Haskell: test elem = (foldr (||) False). (map (== elem)) test : > (/ F or) : ((α eq) : (distl : >)) (/ F or) : ((α eq) :,,, >) (/ F or) : T