Основы языков семейства Lisp Денис С. Мигинский. Абстрактное синтаксическое дерево int main (void){ int a = 1; if(a > 1){ //block1 } else{ //block2 } - презентация

1 Основы языков семейства Lisp Денис С. Мигинский

2 Абстрактное синтаксическое дерево int main (void){ int a = 1; if(a > 1){ //block1 } else{ //block2 } return 0; } function id: main params res: int body var: int id: a init: 1 return: 0 if pred: > a a 1 1 then: block1 else: block2 … … … … Результат работы синтаксического анализатора:

3 Исторический экскурс в Lisp Первая реализация – конец 1950-х, IBM 704. Автор – John McCarthy Базовая структура данных – регистр из двух слов. Основные операции (asm macros): car reg – первое слово регистра (CAR = Contents of the Address part of Register number) cdr reg – второе слово регистра (CDR = Contents of the Decrement part of Register number)

4 Влияние Lisp на современные языки Первый динамический язык Первый функциональный язык Первый язык со сборкой мусора (1959 г. !!!) Первый язык с абстрактными типами данных Первый язык представления данных Первый (и до сих пор один из немногих) язык с поддержкой макрогенерации Первая среда с REPL (shell-оболочкой)

5 Read-Eval-Print Loop (REPL) REPL – интерактивная среда программирования, основанная на бесконечном цикле выполнения перечисленных функций Единица исполнения – одна инструкция (она же – естественная единица модульности) Образ – набор скомпилированных символов (переменные, функции и т.д.) Виды инструкций: Вычислительные – порождают результат, не влияют на образ (кроме изменения значений глобальных переменных) Определяющие/компилирующие – компилируют новое определение (байт-код, иногда – нативный код) и помещают его в образ (возможно, переопределяют старое) Интроспекция – необходимый инструмент управления образом

6 Синтаксис Lisp S-выражение, S(-ymbolic)-expression – выражение вида a1 или (a1 a2 … ), где a1 a2 – атомы или другие S-выражения Атом: идентификаторы константы (строковые, числовые, рег. выражения и т.д.) Синтаксический макрос – синтаксический сахар Интерпретация S-выражений ;Lisp (f a b c) //C f(a,b,c)

7 Историческое представление пары и списка в Lisp «Аксиоматика»: (a. b) – конструирование пары (car (a. b)) -> a (cdr (a. b)) -> b (a. (b. c)) – почти список (a b c) (a. (b. (c. nil))) – список (a b c) a a b b c c a a b b c c

8 Списки в Lisp современное представление (Clojure) (a b c) – конструирование списка (first (a b c)) -> a – «голова» списка (~car) (rest (a b c)) -> (b c) – «хвост» списка (~cdr) (cons a (b c)) -> (a b c) – construct

9 Деревья (a (b c) (d e f)) Интерпретации a a d d c c b b f f e e a a b b c c d d e e f f

10 Связь с абстрактным синтаксическим деревом (if (> a 1) (print >) (print a a 1 1 then: print else: print > > <

11 Функции и специальные формы Интерпретация S-выражения: вычисляется первый элемент списка, результат вычислений должен быть либо функцией, либо специальной формой (в противном случае – ошибка компиляции или времени исполнения). Функция – вычисляются все последующие элементы списка, после чего происходит вызов функции (аппликативный порядок вычислений) Специальная форма – происходит вызов специальной формы без вычисления аргументов. Спец. форма сама инициирует вычисление аргументов (отложенный порядок вычислений). Примеры : управляющие конструкции, логические связки.

12 Язык Clojure Первый релиз: 2009 г. Автор: Richard Hickey Платформа: JVM (компиляция в Java byte-code) Классификация: диалект Lisp промышленного назначения (или претендующий на таковое) Особенности: чистая функциональная основа, эффективная многопоточность Отношение к Java: не будем чинить то, что в Java не ломалось

13 Инструментарий Clojure Язык: Рекомендуемая среда разработки: Eclipse + CounterClockwise plugin Сборка: Leiningen + Apache Maven

14 Особенности записи арифметических операции В Lisp нет арифметических (и других) операторов. Все операции являются вызовами функций (или спец. форм) и записываются в префиксной форме. Отсутствует понятие приоритета операций, т.к. оно имеет смысл только для инфиксной записи. C: a*x*x + b*x + c Lisp: (+ (* a x x) (* b x) c)

15 Определение функции (defn sqr Square root [x] (:pre [(>= x 0)]) (* x x)) (defn fact [n] (if (> n 1) (reduce * (range 2 (inc n))) 1)) (defn fname doc? [args] prepostmap? forms) fname – имя функции args – список аргументов forms – тело, одно или несколько S-выражений

16 Функции с переменным числом параметров, анонимные функции ;функция с переменным числом параметров (defn poly [x & coeffs] (reduce ;анонимная функция (fn [acc coef] (+ (* acc x) coef)) 0 coeffs)) (println (poly )) ;определение анонимной функции и ее применение ((fn [x] (+ x 5)) 3) ;эквивалентная сокращенная запись (#(+ % 5) 3)

17 « Перегрузка » функций ;замечание: библиотечная функция + дает тот же эффект (defn sum ([] 0) ([x] x) ([x y & rest] (+ x (apply sum (cons y rest))))) (println (sum 1 2 3))

18 Основные типы и структуры данных числа (целые, вещественные, рациональные) cтроки, регулярные выражения keywords списки массивы ассоциативные массивы множества

19 Числа Представление целых и вещественных чисел – по аналогии с Java Рациональные числа: (println (/ )) >>0.5 (println (/ 1 2)) >>1/2 (println (+ 1/2 1/3)) >>5/6 1/2 – это форма записи числа, а не применение операции деления!

20 Строки, регулярные выражения Some string ;строка #[\w\s]+ ;regex Используется преимущественно Java-API (println (class "Some string")) >> java.lang.String (println (.toUpperCase "Some string")) >>SOME STRING > java.lang.String (println (.toUpperCase "Some string")) >>SOME STRING">

21 Списки : конструирование (f a b) - определение списка и его вычисление (list a, b, c) – определение списка из значений a, b, c. Запятая – обычный разделитель, как и пробел. (a b c) – определение списка и блокирование его вычисления (прямой апостроф). Будет определен список из символов (не значений!) a, b, c (cons a (b c)) -> (a b c) ;construct (conj (b c) a) -> --//-- ;conjoin (concat (a b) (c d)) -> (a b c d) ;concatenate

22 Доступ к списку (first (a b c)) -> a (rest (a b c)) -> (b c) (nth 2 (a b c)) -> c (take 2 (a b c)) -> (a b)

23 Модификация структур данных Модификация всех структур данных, а также переменных в Clojure запрещена (кроме особых случаев) Примечание: использование java.lang.String не нарушает это правило Все мутаторы создают новую структуру данных вместо модификации существующей Проблема 1: потенциальная утечка памяти в цепочках вычислений Решение: Garbage Collector, обязательный для всех функциональных языков Проблема 2: перерасход памяти за счет дублирования данных Решение: Persistent Data Structures

24 Persistent Data Structures Persistent – постоянный, неизменный PDS – структура данных, которая при изменении сохраняет свое предыдущее состояние. Принцип организации: 1.Для двух разных состояний общая часть хранится в памяти в единственном экземпляре. Для каждого состояния хранится отдельно уникальная часть. 2.Принцип обобщается на произвольное количество состояний

25 Пример : Persistent List :a :b a b (let [a (list :a :a :a) b (list :b :b :b) c (cons :c a) d (rest a) e (concat b a) … :a a :c dc :b e :a a a :b e b e b

26 Обработка списков (map f coll) – порождение нового списка путем поэлементного преобразования coll посредством применения f (эквивалентно map в Ruby) (reduce f coll) (reduce f val coll) - свертка списка заданной функцией (эквивалентно inject в Ruby) (filter f coll) ~ select (Ruby) (remove f coll) ~ reject (Ruby)

27 Генератор for (for [x ["a" "b" "c"] y ["a" "b" "c"] :when (not (= x y))] (.concat x y)) >> ("ab" "ac" "ba" "bc" "ca" "cb") > ("ab" "ac" "ba" "bc" "ca" "cb")">

28 Массивы (vector) В отличие от списка массив не интерпретируется как применение функции (специальной формы) [1 2 3] – объявление массива (vector 1 2 3) - --//-- (vec (1 2 3)) – порождение массива из списка (assoc [1 2 3] 1 4) -> [1 4 3] ;associate (conj [1 2 3] 4) -> [ ] ;добавляет элемент в конец (cons 4 [1 2 3]) -> ( ) ;добавляет элемент в начало, возвращает список

29 Ассоциативные массивы {:a 1, :b 2} (hash-map :a 1, :b 2) – объявление хэш-таблицы (sorted-map &keyvals) (sorted-map-by comparator &keyvals) - объявление сортированного ассоциативного массива (assoc {:a 1} :b 2) -> {:a 1 :b 2} (dissoc {:a 1 :b 2} :b) -> {:a 1} ({:a 1 :b 2} :a) -> 1 (:a {:a 1 :b 2}) -> 1 (map (fn [x] x) {:a 1 :b 2}) -> ([:a 1] [:b 2])

30 Множества #{:a :b :c} (hash-set :a :b :c) (sorted-set & entries) (sorted-set-by comparator & entries) (conj #{:a :b} :c) -> #{:a :b :c} (disj #{:a :b :c} :c) -> #{:a :b} (contains? #{:a :b} :b) -> true (ns test (:use clojure.set)) (intersection #{:a :b} #{:b :c}) -> #{:b} ;...

31 Ветвления (if (> a 0) ;condition (println pos) ;then (println non-pos)) ;else (optional) ;множественный if-else (println (cond (> a 0) pos (< a 0) neg true nil))

32 Последовательное исполнение ;do объединяет несколько форм в одну ;и исполняет их, возвращая результат ;последней формы (if (> a 0) (do (println pos) true) (do (println neg) false))

33 Спец. форма : цепочка операция (-> {} (assoc :a 1) (assoc :b 2) (assoc :c 3)) ;эквивалентная запись (assoc (assoc {} :a 1) :b 2) :c 3) ;->> - то же самое что и ->, но объект ;подставляется на последние позиции форм

34 Определение лексического контекста : let ;let определяет лексический ;и привязывает значения к символам (let [a 10 ;определение символов b (+ a 10)] (println a) ;формы (println b))

35 Destructuring ( реорганизующее присваивание ) (let [v [1 [2 3 4] 5 6 7] [a [b & c] d & e] v]] (println a) ;1 (println b) ;2 (println c) ;(3 4) (println d) ;5 (println e)) ;(6 7) (defn my-f [[x y & rest] val] …) (my-f [ ] 5)

36 Map-Based Destructuring (let [m {:a 1, :b 2, :c 3} {a :a, b :b} m] ;a=1, b=2 v [1 2 3] {fst first rst rest avg #(/ (sum %) (count %))} m] …)

37 Определение лексического контекста : другие формы ;defn, fn ;letfn (letfn [(my-f [x] (+ 5 x))] (my-f 6)) ;почти эквивалентно предыдущему, ;но имя функции my_f не будет доступно ;для рекурсивного вызова (let [my-f (fn [x] (+ 5 x))] (my-f 6)) ;loop – эквивалентно let, но при этом ;определяется точка возврата для recur

38 Хвостовая рекурсия ;в форме цикла (loop [i 0] (println i) (if (< i 10) (recur (inc i)))) ;в форме рекурсивной функции (letfn [(my_loop [i] (println i) (if (< i 10) (recur (inc i))))] (my_loop 0))

39 Задача С 1 Реализовать решение 1-ой задачи из раздела Ruby на языке Clojure. Демонстрацию работоспособности обеспечить с помощью модульных тестов.

40 Элементарное взаимодействие с Java (ns ru.nsu.fit.dt ;clojure namespace (:use clojure.test) ;Java classes (:import (java.io File PrintWriter))) ;вызов Clojure с полной квалификацией имени (clojure.xml/parse file.xml) ;вызов статического метода/обращение к статическому ;атрибуту Java-класса (Math/sin Math/PI) ;присваивание (только для Java-атрибутов) (set! MyClass/someStaticVar 42)

41 Элементарное взаимодействие с Java ( продолжение ) ;вызов метода (.toUpperCase Ordinary java string) (. Ordinary java string toUpperCase) ;инстанцирование (new HashMap) ;цепочка вызовов (.. str (getClass) (getName)) ; java.lang.String (.getName (.getClass str )) ;эквивалентная запись ;последовательные манипуляции объектом (doto (new HashMap) (.put a 1) (.put b 2) (let [m new HashMap] (.put a 1) (.put b 2))

42 Модульное ( компонентное ) тестирование (unit-testing) Концепция модульного тестирования подразумевает автоматическую проверку функциональности каждой минимальной программной единицы, для которой это возможно. В данном контексте модуль, это: функция группа связанных функций метод интерфейс класс Каждый модуль покрывается набором тестов, покрывающих всю функциональность, в т.ч. Проверку ошибок.

43 Модульное тестирование : тест Тест – это функция, возвращающая true, если и только если тест прошел успешно. Тесты разрабатываются параллельно с основным кодом, иногда даже раньше самого кода. Все тесты запускаются при каждой сборке, среда тестирования выдает сводный отчет по всем тестам. Тесты запускаются последовательно. По возможности правило обеспечивается изоляция тестов, т.е. если один «упал», остальные продолжат выполнение.

44 Модульное тестирование, пример : основной код (ns ru.nsu.fit.dt.defpackage (:gen-class)) (defn fact [n] (if (> n 1) (reduce * (range 2 (inc n))) 1))

45 Модульное тестирование, пример : тестирующий код (ns ru.nsu.fit.dt.defpackage-test (:use ru.nsu.fit.dt.defpackage) (:require [clojure.test :as test])) (test/deftest defpackage-test (test/testing "Testing defpackage" (test/is (= (fact 0) 1)) (test/is (= (fact 1) 1)) (test/is (= (fact 2) 2)) (test/is (= (fact 5) 120))))

46 Мемоизация Мемоизация – оптимизация производительности путем кэширования возвращаемых значений функций. Применима только для функций, не имеющих побочных эффектов (чистых функций). Имеет смысл для «тяжелых» функций, когда время вычислений функции заведомо превышает время поиска по хэш-таблице. Расходует память пропорционально количесту комбинаций параметров.

47 Мемоизация в действии (def fact-mem (memoize fact)) (defn -main [& args] (time (fact 100)) (time (fact-mem 100)) (time (fact-mem 100))) >> "Elapsed time: msecs" "Elapsed time: msecs" "Elapsed time: msecs" "Elapsed time: msecs" "Elapsed time: msecs"

48 Задача С 2: численное интегрирование