Парадигмы программирования, 03 лекция (от 08 октября)

Материал из eSyr's wiki.

Тема сегодняшней и следующей лекций: язык lisp.

Это классический язык, один из двух выживших реликтов. В 50-е годы придумали 4 языка прогр., потом наступили 60-е, там придумали неск. сотен языков, в 70-х несколько тысяч, потом запал пропал.

Первый доживший --- фортран, второй --- лисп.

Что такое лисп, не очень понятно. Вот, есть common lisp, он принят стандартизационными комитетами, практи. применим и так далее. Но в нём не видно самой парадигмы, за деревьями не видно леса. Описание CL занимает 1029 страниц потому, что в язык внесено много возможностей. Хорошо ли это? Не очень, например, язык С описывается на десятках страниц, всё остальное в библиотеке. В лисп же внесено много всего. Например, в лиспе есть CLOS, возможно использование ООП, но лектор считает, что не стоит это делать на нём, для этого есть другие языки. Другое дело, что есть люди, которые постулируют, что на лиспе нужно делать всё. Например, среди них автор PCL (practical common lisp).

Пока нас интересует парадигмальная составляющая, точнее, какой комплекс парадигм развился вокруг лиспа. Есть культура программирования на лиспе, и в сообществе программистов на лиспе возник такой комплекс традиций, состоящий из парадигм программирования, подходов к осм. программ. Редко бывают чистые языки.

Например, lisp — язык ФП. Нет, это не так, там есть императивные конструкции. Он стимулирует ФП, но не принадлежит к нему. Вот haskell, miranda - это да.

...

Первое, что нужно понять: лисп — язык, в котором есть фунд. понятие --- s-выражение (s-expression).

Это выражение вызывает некоторую путаницу. МакКарти ввёл его чисто синтаксически. Как:

• у нас есть атомарные выражения- они являются s-выражениями — например, 25
• Символ — SYMBOL — тоже s-выражение. В привычных нам языках мы бы сказали, что это ижент, другое дело, что в имени меньше ограничений. В частности, если
• Строка — "This is a string" . Появились не сразу, раньше просто перечисляли отдельные символы,

Есть ещё некое количество атомов. Из них инт. один, который попадает в категорию символов — nil. Он немного специальный, и его можно записать как ()- пустой список. Кроме того, в классических версиях лиспа он обозначает логическую ложь. От этого (и ещё от ...) отошли в scheme — там для обозначения лжи отдельный символ.

Чтобы оторваться от атомарных выражений, вводим ещё одну фундаментальную вещь — точечная пара.

• s-выражением является точечная пара: ( _ . _ ). Заметим, что у нас практ. получ.. бинарные деревья. Пример: (( a . b) . (1 . ("abc" . d). Кроме того, есть специальный случай комбинации точечных пар: (a . (b . (c . … (y . z)…) названный точечным списком. Что это такое: это дерево, сильно несбалансированное. Его можно записать как (a b c … y . z) — точечный или неправильный список. Чтобы был правильный, в качестве последнего элемента нужно использовать nil: (a . (b . (c . … (y . (z . nil))…), эта строка уже называется списком и записывается как (a … z). Именно эта структура определяет всю парадигматику лиспа.

Lisp — list processing. Для чего нужны были списки в 50-х годах? Для символьных вычислений. В частности, у МакКарти в 58 году была статья , на которую своим считают долгом сослаться все, пишущие о лиспе.

Чем интересно это выражение? Своей гетерогенностью- в любом месте может стоять любой атом, любой список, и так далее. Может быть использована и точечная пара, но они исп. реже.

Зачем нужны списки и почему МакКарти за них ухватился? Потому что мат. формула представляет именно такую динамическую и весьма гетерогенную структуру. Попробуйте сделать аналогичное представление формул в языке С? Это можно сделать, С это позволяет, там есть структуры, юнионы, ссылки. И вот для этого это всё было предназначено. Понятно, что формулами область применения гетерогенных структур данных не ограничена.

Например, есть XML, сейчас он очень модный. Что же представляет собой XML? Это то же самое, только другой синтаксис. Xml можно преобразовать в s-выражения и обратно за линейное время.

Чем полезна структурированность? Тем, что мы не огр. тип., не всегда это хорошо. Например, это полезно при работе со слабоструктурированными данными. Например, web-страница. Она может легко менять свою структуру.

...

Есть такая категория языков, как командно-скриптовые языки, shell и иже. Там есть универсальное представление --- текст. Сейчас от этого начинают отказываться, поскольку их начали использовать не совсем по назначению. Тем не менее, тут есть универсальное представление --- текст. Аналогично в лиспе --- s-выражение, где им является и программа и данные.

Какую бы мы структуру данных мы не втащили, мы должны сделать её s-выражением. Для того, чтобы превратить s-выражение в нечто другое, чтобы превратить это в язык программирования, вводится операция вычисления, условно говоря, отображение из s-выражения в s-выражение. Это не совсем так, поскольку в совр. CL есть такие s-выражения, которые не могут быть вычислены.

Осознав, что у нас есть операция над s-выражением, введём её:

• все атомы, кроме символов, вычисляются сами в себя. nil также отображается сам в себя.
• Символ при вычислении даёт значение, которое с ним ассоциировано. Если с ним не связано никакое значение,

товозникнет ошибка.

Пример: например, запустили мы интерпретатор лиспа, он дал приглашение к вводу:

> 25
25
> NIL
()
> "abc"
"abc"
> x
*ERROR: ...
> (setq x 25) #	Это выр. будет вычислено, у него будет побочный эффект, но и будет результат
25
> x
25

Было смело заявить, что у нас отображение- в отображениях нет побочных эффектов.

Чтобы было понятно, можно сделать вот так:

> (setq x 'x)
x
> x
x

То есть, с символом x ассоциирован он сам.

Зачем лектор это показал. Он показал, чтобы проиллюстрировать эту гетерогенность, нетипизированность переменных. Да, каждое значение типизировано, но не переменные. В ком.-скр., кстати, и то, и другое не типизировано.

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

> (+ 1 2)
3
> (+ (* 2 3) 4)
10

вот так вычисляются формы.

Считается, что точечные списки некорректно вычислять. Считается, что точечные списки формами не являются. Это пример s-выражения, которое не может быть вычислено.

Как ввести свою функцию? Можем ли мы это? Конечно. Вообще, вся программа есть функция. Для определения функции есть ещё одна специальная штука, типа setq, она вычисляет аргумент, но иначе. Это defun. Вообще, штуки, которые вычисляются специальным образом называются специальными формами. На этом месте бы сторонник CL вскочил и сказал бы, что это не специальная форма, а макрос. Разница понятна становится далеко не сразу. Кроме того, есть диалекты, где setq есть диалект.

Тут у символа может быть значение и с ним может быть связана функция, в схеме, например, это не так.

(defun f1 (a) (+ a 1))

Данная функция делает инкремент. Если это введено в интерпретатор, то результат этого выражения будет имя функции, `f1`. Теперь можно сделать вот так:

> (f1 15)
16

Теперь можно использовать это имя функции в формах. Лектор должен сказать, что спец. формы в большинстве лиспов вводить нельзя. Есть промежуточная шутка --- макросы, но это отдельное происшествие, и их мы вряд ли будем рассматривать.

После списка аргументов может быть сколько угодно форм. Например:

(defun f1 (a) (setq glob_var a) (+ a 1))

Таких форм может быть сколько угодно. Результатом будет только последняя форма.

Обратим внимание вот на что: эта форма (defun) существовала с первых версий лиспа. Такая послед. вычислений в случае отсутствия побочных эффектов была бы ни к чему. Такой синтаксис формы defun показывает, что лисп никогда не был ФП. Он стимулирует ФП, но он императивный. Это не было внесено под давлением злых императивных программеров, нет, никаких злых программеров не было, эта гадость тут была изначально.

И вообще, оно было придумано для обработки списков. То, что оно функционально, придумали позже.

Чтобы писать на лиспе, нужно знать ещё несколько вещей.

* Блокирование вычислений. 

Если у нас есть некое выражение, и если мы хотим передать его, а не результат, то мы предваряем его апострофом. Для этого служит спец. форма, наз. quote: (quote a). Она не выч. свой арг., и результатом является аргумент. Поскольку она используется постоянно, у неё есть синоним: 'a. Это чистой воды синт. сахар.

Поскольку у нас есть s-выражение, надо понять, как работать с s-выражениями. Для них есть для выр.: созд. точ. пару из s-выр, и разобрать точ. пару на две части.

• cons: (cons 'a 'b). Результатом будет (a . b)
• car и cdr. Car и cdr это названия подрегистров процессора той машины, где делали первый лисп. Там был большущий регистр, куда умещались два адреса и что-то ещё. И точечную пару хранили в этом регистре. И в автокоде были команды car reg и crd reg (adress register, data register). И так они в лисп не перешли. Никто бы сейчас не вспоминал автокод этого умершего процессора, если бы не лисп. car --- выделение левого эл-та, cdr --- правого.

(car '(a . b)) -> a
(cdr '(a . b)) -> b
(car '(1 2 3)) -> 1
(cdr '(1 2 3)) -> (2 3)

Функции и операции мы ввели, но программировать не можем - не хватает средств.

Условие:

(if (выр) (форма1) [(форма2)])

Как это вычисляется: сначала вычисл. выражение. Если рез-том явл. nil, то будет выч. форма2, если она есть, иначе возвернётся nil. Если будет что-то другое, то будет выч. форма1 и рез-том будет рез-т выч. формы.

(cond
  ((выр)  (...))
  ((выр)  (...))
)

Форма cond имеет сколько угодно выражений- cond clauses. Выч. первое выр., если не nil, то вып. ост. формы. и результатом будет посл. Так будет, пока не случится true, или пока clauses не кончатся, тогда возвр. nil.

Если взять код на лиспе, то там не будет if ,но будет много cond. А всё потому, что неудобно, когда только одна форма. Это к тому, какой функц. язык лисп.

Есть предикат (null l). Этот предикат возвр. ложь, если его арг. был не nil, и истину, если nil.

t — константа, обозн. истину. Можно исп. 1, но обычно исп. t для того, чтобы легко можно было читать.

Напишем функцию, считающую длину списка.

(defun list_len (l)
  (cond
    ((null l) 0)
    (t (+ 1 (list_len (cdr l))))
  )
)

Хвостовая рекурсия здесь не работает. Как сделать это с помощью хвостовой рекурсии:

(defun list_len (l)
  (do_list_len l 0)
)
(defun do_list_len (l n)
  (cond
    ((null l) n)
    (t (do_list_len (cdr l) (+ n 1)))
  )
)

Как это будет работать:

(list_len ''(1 2 3)) -> (do_list_ken '(1 2 3) 0) -> '(2 3) 1 -> '(3 2) -> () 3

Это функция обычная, первого порядка. Но дело в том, что ф-ция есть объект первого порядка. Над ним опр. операции. Функцию можно передавать в кач. паметра. Можно оплучить её тело, изменить его. Функцию можно на лету сделать новую.

Обычно, в этом месте фанаты лиспа могут сказать, что вот, какой хороший язык лисп, что тут можно на лету функцию генерировать. Но, на самом деле, при наличии компилятора в С такое можно сделать, но это скорее хак, а в лиспе это штатно, и это освершенно замеч. штука.

Есть такое понятие, функционал. Самый поплуярный --- mapcar. У него может быть сколько угодно арг, но не менее двух. Первый элемент --- функция, ост. списки. Этих списков должно быть столько , сколько аргументов. Причём, эти списки должны быть одинаковой длины.

#' — сокр. для (function f). Будучи применённым к символы, она выдир. ассоц. с ним функцию.

Теперь пишем так:

> (mapcar #'+ '(1 2 3) '(10 20 30))
(11 22 33)

Что делает mapcar: берёт соотв. элементы списков и применяет к ним функцию.

Это не прост. функционал, но то, что самый частоисп., это точно.

Что ещё можно делать с mapcar --- поменять знаки всех чисел.

> (mapcar #'- '(1 2 3))
(-1 -2 -3)

Можно применять любую функцию. А если нужно сднлать более сложное, как такое сложное? Например, возв. в квадрат и вычесть единицу в кажд. эл-те списка:

(defun f (x) (+ (* x x) 1))
(mapcar #'f '(1 2 3 4))

Но так обычно не делают, не надо присв. имя функции, если оно нам нужно тодлько в одном месте.

(mapcar #'(lambda (x) (+ (* x x) 1)) '(1 2 3 4))

Загадочное слово lambda. Это назыв. анонимная или безымянная функция. Функция может быть без имени.

Далко было имя ввести? Жалко. Настолько, что большинство не стало бы исп. mapcar. Вместо этого программисты бы изв., делали рекурсию, лишь бы не вводить функцию:

(defun proc(lst)
  (cond ((null lst) nil)
        (t (cons (+ (* (car lst) (car lst)) 1) (proc (cdr lst))))
  )
)

[править] Иллюстрации

S-выражения, точечные пары, точечные списки, списки.	Значения атомов, setq	defun
car, cdr, cons	Функция вычисления длины списка.