Редактирование: Парадигмы программирования, 03 лекция (от 08 октября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | Тема сегодняшней и | + | Тема сегодняшней и след. лекции: язык лисп. |
- | Это | + | Это классич. язык, один из двух выживщих реликтов. В 50-е годы придумали 4 языка прогр., потом наступили 60-е, там придумали неск. сотен языков, в 70-х нес.к тысяч, потом запал пропал. |
Первый доживший --- фортран, второй --- лисп. | Первый доживший --- фортран, второй --- лисп. | ||
- | Что такое лисп, не очень понятно. Вот, есть common lisp, он принят стандартизационными | + | Что такое лисп, не очень понятно. Вот, есть common lisp, он принят стандартизационными коммитетами, практи. применим и так далее. Но в нём не видно саой парадигмы, за деревьями не видно леса. ОПисани CL занимает 1029 страниц. Потому, что в язык внесено много возм. Хорошо ли это? Не очень. Например, язык С описывается на десятках страниц, всё остальное в библиотеке. В лисп же внесено много всего. Например, в лиспе есть CLOS, возм. исп. ООП, но лектор считает, что не стоит это делать на нём, для этого есть другие языки. Другое дело, что есть люди, которые постулируют, что на лиспе нужно делать всё. Например, среди них автор PCL (practical common lisp). |
- | + | Вообще, есть набор книг, которые обозн. аббревиатурами, и все эти аббр. понимают. Например, SICP. Он явля. учебником инф. в MIT. Который, кстати, тоже осн. на лиспе. Также, такой книгой является PCL. | |
- | Пока нас интересует | + | Пока нас интересует парадигм. составляющая, точнее, каккой кмплекс прадигм развился вокруг лиспа. Есть культура прогр. на лиспе, и в сообщ. программистов на лиспе возник такой комплекс традиций, сост. из парадигм прогр., подходов к осм. программ. Редко быавают чистые языки |
- | Например, lisp — | + | Например, lisp — ФП. Нет, это не так, там есть императивные конструкции. Он стимулирует ФП, но не принцжд. к нему. Вот haskell, miranda это да. |
... | ... | ||
Строка 17: | Строка 17: | ||
Первое, что нужно понять: лисп — язык, в котором есть фунд. понятие --- s-выражение (s-expression). | Первое, что нужно понять: лисп — язык, в котором есть фунд. понятие --- s-выражение (s-expression). | ||
- | Это | + | Это выраж. вызывает некоторую путанницу. МаКарти ввёл его чисто синтаксически. Как: |
- | * у нас есть атомарные | + | * у нас есть атомарные выраж., они явл. s-выр. — нарпимер, 25 |
* Символ — SYMBOL — тоже s-выражение. В привычных нам языках мы бы сказали, что это ижент, другое дело, что в имени меньше ограничений. В частности, если | * Символ — SYMBOL — тоже s-выражение. В привычных нам языках мы бы сказали, что это ижент, другое дело, что в имени меньше ограничений. В частности, если | ||
- | * Строка — "This is a string" . Появились не сразу, раньше просто | + | * Строка — "This is a string" . Появились не сразу, раньше просто пересисляли отдельные символы, |
- | Есть ещё некое количество атомов. Из них инт. один, который попадает в | + | Есть ещё некое количество атомов. Из них инт. один, который попадает в кат. символов — nil. Он немного специальный, и его можно записать как (), пустой список. Кроме того, в классич. версиях лиспа он обозн. логич. ложь. От этого (и ещё от ...) отошли в scheme — там для обозн. лжи отдельный символ. |
- | Чтобы оторваться от | + | Чтобы оторваться от атомар. выраж., вводим ещё одно фунд. вещь — точечная пара. |
- | * s- | + | * 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? Это же самое, только другой синтаксис. Xml можно преобр. в s-выр и обр. за линейное время, там, правда, есть навороты, но это сути дела не меняет. |
- | Чем полезна структурированность? Тем, что мы не огр. тип., не всегда это хорошо. Например, это полезно при работе со слабоструктурированными данными. Например, web-страница. Она может легко менять свою структуру. | + | Чем полезна структурированность? Тем, что мы не огр. тип., не всегда это хорошо. Например, это полезно при работе со слабоструктурированными данными же. Например, web-страница. Она может легко менять свою структуру. |
... | ... | ||
- | Есть такая категория языков, как командно-скриптовые языки, shell и иже. Там есть универсальное представление --- текст. Сейчас от этого начинают отказываться, | + | Есть такая категория языков, как командно-скриптовые языки, shell и иже. Там есть универсальное представление --- текст. Сейчас от этого начинают отказываться, поск. их начали исп. не совсем по назначению. Тем не менее, тут есть универс. представление --- текст. Аналогично в лиспе --- s-выражение, где им явл. и прогр. и днные. |
- | Какую бы мы структуру данных мы не втащили, мы должны сделать её s-выражением. Для того, чтобы превратить s-выражение в нечто другое, чтобы | + | Какую бы мы структуру данных мы не втащили, мы должны сделать её s-выражением. Для того, чтобы превратить s-выражение в нечто другое, чтобы превр. это в язык прогр., вводится операция вычисления, условно говоря, отображение из s-выр в s-выр. Это не совсем так, поск. в совр. CL есть такие s-выр, которые выч. быть не могут. |
- | Осознав, что у нас есть | + | Осознав, что у нас есть опер. s-выр. Введём её: |
- | * все атомы, кроме символов, вычисляются сами в себя. nil также | + | * все атомы, кроме символов, вычисляются сами в себя. nil также отобр. сам в себя. |
- | * Символ при | + | * Символ при выч. даёт значение, которое с ним ассоциировано. Если с ним не связ. никакое значение, то возн. ошибка. |
- | + | ||
- | Пример: например, запустили мы интерпретатор лиспа, он дал | + | Пример: например, запустили мы интерпретатор лиспа, он дал приглаш. к вводу: |
- | < | + | <div> |
> 25 | > 25 | ||
25 | 25 | ||
Строка 61: | Строка 60: | ||
> x | > x | ||
25 | 25 | ||
- | </ | + | </div> |
- | Было смело заявить, что у нас | + | Было смело заявить, что у нас отображеине, в отобр. нет побочных эффектов. |
Чтобы было понятно, можно сделать вот так: | Чтобы было понятно, можно сделать вот так: | ||
- | < | + | <div> |
> (setq x 'x) | > (setq x 'x) | ||
x | x | ||
> x | > x | ||
x | x | ||
- | </ | + | </div> |
- | То есть, с символом x | + | То есть, с символом x ассоц. он сам. |
- | Зачем лектор это показал. Он показал, чтобы проиллюстрировать эту гетерогенность, | + | Зачем лектор это показал. Он показал, чтобы проиллюстрировать эту гетерогенность, нетипизир. переменных. Да, каждое знач. типизировано, но не переменные. В ком.-скр., кстати, и то, и другое нетипизир. |
- | Уже можно догадаться, что | + | как выч. список? Уже можно догадаться, что спис. выч. след. обр: первый жлемент --- имя функции (символ), ост. элементы списка воспр. как аргументы функции. Причём, большинство воспр. как аргументы. Выч. функция от получ. значений. setq это исключение. А так, обычно функции сначала вычисляют свои аргументы. Проще всего это проилл. на арифметике: |
- | < | + | <div> |
> (+ 1 2) | > (+ 1 2) | ||
3 | 3 | ||
> (+ (* 2 3) 4) | > (+ (* 2 3) 4) | ||
10 | 10 | ||
- | </ | + | </div> |
вот так вычисляются ''формы''. | вот так вычисляются ''формы''. | ||
- | Считается, что точечные списки некорректно вычислять. Считается, что точечные списки формами не являются. Это пример s- | + | Считается, что точечные списки некорректно вычислять. Считается, что точечные списки формами не являются. Это пример s-выр, которое не может быть вичслено. |
- | Как ввести свою функцию? Можем ли мы это? Конечно. Вообще, вся | + | Как ввести свою функцию? Можем ли мы это? Конечно. Вообще, вся программма есть функция. Для опр. функции есть ещё одна спец. штука, типа setq, она выч. арг, но иначе. Это defun. Вообще, штуки, которые вычисляются спец. обр. наз. спец. формами. На этом месте бы сторонник CL DCRJXBK? HDFYEK ,S HE,F[E и сказл бы, что это не спец. форма, это макрос. Правда, чтобы понять разницу, понятна становится далеко не сразу. Кроме того, есть диалекты, где setq есть диалект. |
- | Тут у символа может быть | + | Тут у символа может быть знач. и с ним может быть связана функция, в схеме, напр., это не так. |
- | < | + | <div> |
(defun f1 (a) (+ a 1)) | (defun f1 (a) (+ a 1)) | ||
- | </ | + | </div> |
- | Данная функция делает инкремент. Если это введено в интерпретатор, то | + | Данная функция делает инкремент. Если это введено в интерпретатор, то рез. этого выраж. будет имя функции, `f1`. Тперь можно сдлеать вот так: |
- | < | + | <div> |
> (f1 15) | > (f1 15) | ||
16 | 16 | ||
- | </ | + | </div> |
- | Теперь можно | + | Теперь можно исп. это имя функции в формах. Лектор должен сказать, что в спецформы в больш. лиспов вводить нельзя. Есть промежуточная шутка --- макросы, но это отдельное происшествие, и их мы вряд ли будем рассматривать. |
- | После списка | + | После списка арг. может быть сколько угодно форм. Например: |
- | < | + | <div> |
(defun f1 (a) (setq glob_var a) (+ a 1)) | (defun f1 (a) (setq glob_var a) (+ a 1)) | ||
- | </ | + | </div> |
- | Таких форм может быть сколько угодно. Результатом будет | + | Таких форм может быть сколько угодно. Результатом будет тольк. посл. форма. |
- | + | Обр. внимание вот на что: эта форма (defun) существовала с первых версий лиспа. Такая посл. выч. в случае отсутствия побочных эффектов была бы ни к чему. Такой синтаксис формы defun показывает, что лисп никогда не был ФП. Он стимулирует ФП, но он императивный. Это не было внесено под давлением злых императивных прогр. Нет, никаких злых прогр. не было, эта гадость тут была изначально. | |
- | И вообще, оно было придумано для обработки списков. То, что оно | + | И вообще, оно было придумано для обработки списков. То, что оно функц., придумали позже. |
- | Чтобы писать на лиспе, нужно знать ещё | + | Чтобы писать на лиспе, нужно знать ещё неск. вещей. |
- | * Блокирование | + | * Блокирование выч. Если у нас есть некое выраж., и если мы хотим передать его, а не резльутат, то мы предваряем его апострофом. Для этого служит спец. форма, наз. quote: (quote a). Она не выч. свой арг., и результатом явл. аргумент. Поск. она исп. постоянно, у неё есть синоним: 'a. Это чистой воды синт. сахар. |
- | Если у нас есть некое | + | |
- | + | Поск. у нас есть s-выр., надо понять, как работать с s-выр. Для них есть для выр.: созд. точ. пару из s-выр, и разобрать точ. пару на две части. | |
- | * cons: (cons 'a 'b). Результатом будет (a . b) | + | * Первая опер. наз. cons: (cons 'a 'b). Результатом будет (a . b) |
- | * car и cdr. Car и cdr это | + | * Другие две функции --- car и cdr. Car и cdr это назв. подрегистров процессора той машины, где делали первый лисп. Там был большущий регистр, куда умешались два адреса и что-то ещё. И точ. пару зранили в этом регистре. И в автокоде были команды car reg и crd reg (adress segister, data register). И так они в лисп не перешли. Никто бы сейчас не вспоминал автокод этого умершего процессора, елси бы не лисп. car --- выделение левого эл-та, cdr --- правого. |
- | < | + | <div> |
(car '(a . b)) -> a | (car '(a . b)) -> a | ||
(cdr '(a . b)) -> b | (cdr '(a . b)) -> b | ||
(car '(1 2 3)) -> 1 | (car '(1 2 3)) -> 1 | ||
(cdr '(1 2 3)) -> (2 3) | (cdr '(1 2 3)) -> (2 3) | ||
- | </ | + | </div> |
- | Функции и | + | Функции и опер. мы ввели, но прогр. не можем, не хватает средств. |
Условие: | Условие: | ||
- | < | + | <div> |
(if (выр) (форма1) [(форма2)]) | (if (выр) (форма1) [(форма2)]) | ||
- | </ | + | </div> |
- | Как это | + | Как это вычисл.: сначала вычисл. выражение. Если рез-том явл. nil, то будет выч. форма2, если она есть, иначе возвернётся nil. Если будет что-то другое, то будет выч. форма1 и рез-том будет рез-т выч. формы. |
- | < | + | <div> |
(cond | (cond | ||
- | ((выр) | + | ((выр) .... (...)) |
- | ((выр) | + | ((выр) .... (...)) |
) | ) | ||
- | </ | + | </div> |
- | Форма cond имеет сколько угодно | + | Форма cond имеет сколько угодно выр., cond clauses. Выч. первое выр., если не nil, то вып. ост. формы. и рез-том будет посл. Так бедт, пока не случится true, или пока клаузы не кончатся, тогда возвр. nil. |
- | Если взять код на лиспе, то там | + | Если взять код на лиспе, то там небудет if и будет много cond. А всё потому, что неудобно, когда только одна форма. Это к тому, какой функц. язык лисп. |
- | Есть предикат (null l). Этот предикат возвр. | + | Есть предикат (null l). Этот предикат возвр. лозь, если его арг. был не nil, и истину, если nil. |
- | t — константа, обозн. истину. Можно исп. | + | t — константа, обозн. истину. Можно исп. 13, но обычно исп. t для того, чтобы легко можно было читать. |
Напишем функцию, считающую длину списка. | Напишем функцию, считающую длину списка. | ||
- | < | + | <div> |
(defun list_len (l) | (defun list_len (l) | ||
(cond | (cond | ||
Строка 158: | Строка 156: | ||
) | ) | ||
) | ) | ||
- | </ | + | </div> |
Хвостовая рекурсия здесь не работает. Как сделать это с помощью хвостовой рекурсии: | Хвостовая рекурсия здесь не работает. Как сделать это с помощью хвостовой рекурсии: | ||
- | < | + | <div> |
(defun list_len (l) | (defun list_len (l) | ||
(do_list_len l 0) | (do_list_len l 0) | ||
Строка 171: | Строка 169: | ||
) | ) | ||
) | ) | ||
- | </ | + | </div> |
Как это будет работать: | Как это будет работать: | ||
- | < | + | <div> |
(list_len ''(1 2 3)) -> (do_list_ken '(1 2 3) 0) -> '(2 3) 1 -> '(3 2) -> () 3 | (list_len ''(1 2 3)) -> (do_list_ken '(1 2 3) 0) -> '(2 3) 1 -> '(3 2) -> () 3 | ||
- | </ | + | </div> |
Это функция обычная, первого порядка. Но дело в том, что ф-ция есть объект первого порядка. Над ним опр. операции. Функцию можно передавать в кач. паметра. Можно оплучить её тело, изменить его. Функцию можно на лету сделать новую. | Это функция обычная, первого порядка. Но дело в том, что ф-ция есть объект первого порядка. Над ним опр. операции. Функцию можно передавать в кач. паметра. Можно оплучить её тело, изменить его. Функцию можно на лету сделать новую. | ||
Строка 184: | Строка 182: | ||
Есть такое понятие, функционал. Самый поплуярный --- mapcar. У него может быть сколько угодно арг, но не менее двух. Первый элемент --- функция, ост. списки. Этих списков должно быть столько , сколько аргументов. Причём, эти списки должны быть одинаковой длины. | Есть такое понятие, функционал. Самый поплуярный --- mapcar. У него может быть сколько угодно арг, но не менее двух. Первый элемент --- функция, ост. списки. Этих списков должно быть столько , сколько аргументов. Причём, эти списки должны быть одинаковой длины. | ||
- | + | #' — сокр. для (function f). Будучи применённым к символы, она выдир. ассоц. с ним функцию. | |
Теперь пишем так: | Теперь пишем так: | ||
- | < | + | <div> |
> (mapcar #'+ '(1 2 3) '(10 20 30)) | > (mapcar #'+ '(1 2 3) '(10 20 30)) | ||
(11 22 33) | (11 22 33) | ||
- | </ | + | </div> |
Что делает mapcar: берёт соотв. элементы списков и применяет к ним функцию. | Что делает mapcar: берёт соотв. элементы списков и применяет к ним функцию. | ||
Строка 199: | Строка 197: | ||
Что ещё можно делать с mapcar --- поменять знаки всех чисел. | Что ещё можно делать с mapcar --- поменять знаки всех чисел. | ||
- | < | + | <div> |
> (mapcar #'- '(1 2 3)) | > (mapcar #'- '(1 2 3)) | ||
(-1 -2 -3) | (-1 -2 -3) | ||
- | </ | + | </div> |
Можно применять любую функцию. А если нужно сднлать более сложное, как такое сложное? Например, возв. в квадрат и вычесть единицу в кажд. эл-те списка: | Можно применять любую функцию. А если нужно сднлать более сложное, как такое сложное? Например, возв. в квадрат и вычесть единицу в кажд. эл-те списка: | ||
- | < | + | <div> |
(defun f (x) (+ (* x x) 1)) | (defun f (x) (+ (* x x) 1)) | ||
(mapcar #'f '(1 2 3 4)) | (mapcar #'f '(1 2 3 4)) | ||
- | </ | + | </div> |
Но так обычно не делают, не надо присв. имя функции, если оно нам нужно тодлько в одном месте. | Но так обычно не делают, не надо присв. имя функции, если оно нам нужно тодлько в одном месте. | ||
- | < | + | <div> |
(mapcar #'(lambda (x) (+ (* x x) 1)) '(1 2 3 4)) | (mapcar #'(lambda (x) (+ (* x x) 1)) '(1 2 3 4)) | ||
- | </ | + | </div> |
Загадочное слово lambda. Это назыв. анонимная или безымянная функция. Функция может быть без имени. | Загадочное слово lambda. Это назыв. анонимная или безымянная функция. Функция может быть без имени. | ||
Далко было имя ввести? Жалко. Настолько, что большинство не стало бы исп. mapcar. Вместо этого программисты бы изв., делали рекурсию, лишь бы не вводить функцию: | Далко было имя ввести? Жалко. Настолько, что большинство не стало бы исп. mapcar. Вместо этого программисты бы изв., делали рекурсию, лишь бы не вводить функцию: | ||
- | < | + | <div> |
(defun proc(lst) | (defun proc(lst) | ||
(cond ((null lst) nil) | (cond ((null lst) nil) | ||
Строка 225: | Строка 223: | ||
) | ) | ||
) | ) | ||
- | </ | + | </div> |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
{{Парадигмы программирования}} | {{Парадигмы программирования}} | ||
{{Lection-stub}} | {{Lection-stub}} |