Редактирование: Парадигмы программирования, 03 лекция (от 08 октября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | Тема сегодняшней и | + | Тема сегодняшней и след. лекции: язык лисп. |
- | Это | + | Это классич. язык, один из двух выживщих реликтов. В 50-е годы придумали 4 языка прогр., потом наступили 60-е, там придумали неск. сотен языков, в 70-х нес.к тысяч, потом запал пропал. |
Первый доживший --- фортран, второй --- лисп. | Первый доживший --- фортран, второй --- лисп. | ||
- | Что такое лисп, не очень понятно. Вот, есть common lisp, он принят стандартизационными | + | Что такое лисп, не очень понятно. Вот, есть common lisp, он принят стандартизационными коммитетами, практи. применим и так далее. Но в нём не видно саой парадигмы, за деревьями не видно леса. ОПисани CL занимает 1029 страниц. Потому, что в язык внесено много возм. Хорошо ли это? Не очень. Например, язык С описывается на десятках страниц, всё остальное в библиотеке. В лисп же внесено много всего. Например, в лиспе есть CLOS, возм. исп. ООП, но лектор считает, что не стоит это делать на нём, для этого есть другие языки. Другое дело, что есть люди, которые постулируют, что на лиспе нужно делать всё. Например, среди них автор PCL (practical common lisp). |
- | <div class="comment">Вообще, есть набор книг, которые | + | <div class="comment">Вообще, есть набор книг, которые обозн. аббревиатурами, и все эти аббр. понимают. Например, SICP. Он явля. учебником инф. в MIT. Который, кстати, тоже осн. на лиспе. Также, такой книгой является PCL.</div> |
- | Пока нас интересует | + | Пока нас интересует парадигм. составляющая, точнее, каккой кмплекс прадигм развился вокруг лиспа. Есть культура прогр. на лиспе, и в сообщ. программистов на лиспе возник такой комплекс традиций, сост. из парадигм прогр., подходов к осм. программ. Редко быавают чистые языки |
- | Например, 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 также отобр. сам в себя. |
- | * Символ при | + | * Символ при выч. даёт значение, которое с ним ассоциировано. Если с ним не связ. никакое значение, то возн. ошибка. |
- | + | ||
- | Пример: например, запустили мы интерпретатор лиспа, он дал | + | Пример: например, запустили мы интерпретатор лиспа, он дал приглаш. к вводу: |
<pre> | <pre> | ||
> 25 | > 25 | ||
Строка 63: | Строка 62: | ||
</pre> | </pre> | ||
- | Было смело заявить, что у нас | + | Было смело заявить, что у нас отображеине, в отобр. нет побочных эффектов. |
Чтобы было понятно, можно сделать вот так: | Чтобы было понятно, можно сделать вот так: | ||
Строка 73: | Строка 72: | ||
</pre> | </pre> | ||
- | То есть, с символом x | + | То есть, с символом x ассоц. он сам. |
- | Зачем лектор это показал. Он показал, чтобы проиллюстрировать эту гетерогенность, | + | Зачем лектор это показал. Он показал, чтобы проиллюстрировать эту гетерогенность, нетипизир. переменных. Да, каждое знач. типизировано, но не переменные. В ком.-скр., кстати, и то, и другое нетипизир. |
- | Уже можно догадаться, что | + | как выч. список? Уже можно догадаться, что спис. выч. след. обр: первый жлемент --- имя функции (символ), ост. элементы списка воспр. как аргументы функции. Причём, большинство воспр. как аргументы. Выч. функция от получ. значений. setq это исключение. А так, обычно функции сначала вычисляют свои аргументы. Проще всего это проилл. на арифметике: |
<pre> | <pre> | ||
> (+ 1 2) | > (+ 1 2) | ||
Строка 87: | Строка 86: | ||
вот так вычисляются ''формы''. | вот так вычисляются ''формы''. | ||
- | Считается, что точечные списки некорректно вычислять. Считается, что точечные списки формами не являются. Это пример s- | + | Считается, что точечные списки некорректно вычислять. Считается, что точечные списки формами не являются. Это пример s-выр, которое не может быть вичслено. |
- | Как ввести свою функцию? Можем ли мы это? Конечно. Вообще, вся | + | Как ввести свою функцию? Можем ли мы это? Конечно. Вообще, вся программма есть функция. Для опр. функции есть ещё одна спец. штука, типа setq, она выч. арг, но иначе. Это defun. Вообще, штуки, которые вычисляются спец. обр. наз. спец. формами. На этом месте бы сторонник CL DCRJXBK? HDFYEK ,S HE,F[E и сказл бы, что это не спец. форма, это макрос. Правда, чтобы понять разницу, понятна становится далеко не сразу. Кроме того, есть диалекты, где setq есть диалект. |
- | Тут у символа может быть | + | Тут у символа может быть знач. и с ним может быть связана функция, в схеме, напр., это не так. |
<pre> | <pre> | ||
(defun f1 (a) (+ a 1)) | (defun f1 (a) (+ a 1)) | ||
</pre> | </pre> | ||
- | Данная функция делает инкремент. Если это введено в интерпретатор, то | + | Данная функция делает инкремент. Если это введено в интерпретатор, то рез. этого выраж. будет имя функции, `f1`. Тперь можно сдлеать вот так: |
<pre> | <pre> | ||
> (f1 15) | > (f1 15) | ||
16 | 16 | ||
</pre> | </pre> | ||
- | Теперь можно | + | Теперь можно исп. это имя функции в формах. Лектор должен сказать, что в спецформы в больш. лиспов вводить нельзя. Есть промежуточная шутка --- макросы, но это отдельное происшествие, и их мы вряд ли будем рассматривать. |
- | После списка | + | После списка арг. может быть сколько угодно форм. Например: |
<pre> | <pre> | ||
(defun f1 (a) (setq glob_var a) (+ a 1)) | (defun f1 (a) (setq glob_var a) (+ a 1)) | ||
</pre> | </pre> | ||
- | Таких форм может быть сколько угодно. Результатом будет | + | Таких форм может быть сколько угодно. Результатом будет тольк. посл. форма. |
- | + | Обр. внимание вот на что: эта форма (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 --- правого. |
<pre> | <pre> | ||
(car '(a . b)) -> a | (car '(a . b)) -> a | ||
Строка 127: | Строка 125: | ||
</pre> | </pre> | ||
- | Функции и | + | Функции и опер. мы ввели, но прогр. не можем, не хватает средств. |
Условие: | Условие: | ||
Строка 133: | Строка 131: | ||
(if (выр) (форма1) [(форма2)]) | (if (выр) (форма1) [(форма2)]) | ||
</pre> | </pre> | ||
- | Как это | + | Как это вычисл.: сначала вычисл. выражение. Если рез-том явл. nil, то будет выч. форма2, если она есть, иначе возвернётся nil. Если будет что-то другое, то будет выч. форма1 и рез-том будет рез-т выч. формы. |
<pre> | <pre> | ||
(cond | (cond | ||
- | ((выр) | + | ((выр) .... (...)) |
- | ((выр) | + | ((выр) .... (...)) |
) | ) | ||
</pre> | </pre> | ||
- | Форма cond имеет сколько угодно | + | Форма cond имеет сколько угодно выр., cond clauses. Выч. первое выр., если не nil, то вып. ост. формы. и рез-том будет посл. Так бедт, пока не случится true, или пока клаузы не кончатся, тогда возвр. nil. |
- | Если взять код на лиспе, то там | + | Если взять код на лиспе, то там небудет if и будет много cond. А всё потому, что неудобно, когда только одна форма. Это к тому, какой функц. язык лисп. |
- | Есть предикат (null l). Этот предикат возвр. | + | Есть предикат (null l). Этот предикат возвр. лозь, если его арг. был не nil, и истину, если nil. |
- | t — константа, обозн. истину. Можно исп. | + | t — константа, обозн. истину. Можно исп. 13, но обычно исп. t для того, чтобы легко можно было читать. |
Напишем функцию, считающую длину списка. | Напишем функцию, считающую длину списка. | ||
Строка 228: | Строка 226: | ||
== Иллюстрации == | == Иллюстрации == | ||
- | <gallery widths="200" heights="140" perrow=" | + | <gallery widths="200" heights="140" perrow="5"> |
Изображение:Paradigm 091008 01.jpg|S-выражения, точечные пары, точечные списки, списки. | Изображение:Paradigm 091008 01.jpg|S-выражения, точечные пары, точечные списки, списки. | ||
Изображение:Paradigm 091008 02.jpg|Значения атомов, setq | Изображение:Paradigm 091008 02.jpg|Значения атомов, setq |