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

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

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

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

<div class="comment">Вообще, есть набор книг, которые обозначены аббревиатурами, и все эти аббревиатуры понимают. Например, SICP-классический учебник по информатике в MIT. Который, кстати, тоже основан на лиспе(диалект scheme). Также, такой книгой является PCL.</div>

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

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

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

* у нас есть атомарные выражения- они являются s-выражениями — например, 25

* Строка — "This is a string" . Появились не сразу, раньше просто перечисляли отдельные символы,

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

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

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

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

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

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

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

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

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

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

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

* все атомы, кроме символов, вычисляются сами в себя. nil также отображается сам в себя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обратим внимание вот на что: эта форма (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 --- правого.

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

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

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

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

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

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

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

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

== Иллюстрации ==

<gallery widths="200" heights="140" perrow="3">

Изображение:Paradigm 091008 01.jpg|S-выражения, точечные пары, точечные списки, списки.

Изображение:Paradigm 091008 02.jpg|Значения атомов, setq

Изображение:Paradigm 091008 03.jpg|defun

Изображение:Paradigm 091008 04.jpg|car, cdr, cons

Изображение:Paradigm 091008 05.jpg|Функция вычисления длины списка.

</gallery>