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

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

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

Это классич. язык, один из двух выживщих реликтов. В 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). Именно эта структура опред. всю парадигматику лиспа

Лисп — 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 DCRJXBK? HDFYEK ,S HE,F[E и сказл бы, что это не спец. форма, это макрос. Правда, чтобы понять разницу, понятна становится далеко не сразу. Кроме того, есть диалекты, где 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 segister, 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, или пока клаузы не кончатся, тогда возвр. nil.

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

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

t — константа, обозн. истину. Можно исп. 13, но обычно исп. 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

Функция вычисления длины списка.