Введение в Лисп

Июль 24, 2022

Главная
Информатика
Введение в Лисп

Содержание

2. Основоположник Джон Маккарти предложил проект языка Лисп (LISP - LISt Processing) в качестве средства исследования границ
3. Математические основы Сформулированная Джоном Маккаpти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и
4. Лямбда-исчисление Лямбда-исчисление (λ-исчисление) - формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия
5. Чистое лямбда-исчисление Это простейший из семейства прототипных языков программирования, чистое λ-исчисление, термы которого, называемые также объектами
6. Универсальность понятия «функция» Универсальность понятия "функция" и разнообразие видов его применения позволяет унифицировать используемые при описании
7. Основные особенности ЛИСПа Унификация понятий "функция" и "значение" – представление функций можно строить из их частей
8. Основные особенности ЛИСПа Одинаковая форма данных и программ – списочные структуры. ЛИСП-программы могут обрабатывать не только
9. Основные особенности ЛИСПа Нестрогая типизация данных – типы сопровождают лишь сами объекты, а не имена символов,
10. Структура данных в ЛИСПе
11. Чем ошибочна данная схема? S-выражения Атомы Символ Константы Число T NIL Списки
12. Примеры Символы: x, u-1997, символ, function Числа: 24, 35.6, 6.3е5 Списки: (а в (с о) р),
13. Базис ЛИСПа Примитивные функции: сons – строит списки из бинарных узлов. Первый аргумент произвольного вида –
14. Примеры вычисления по примитивным функциям (CAR (CONS x y)) = x (CDR (CONS x y)) =
15. Примеры вычисления по примитивным функциям (CAAR ((A) B C)) = A (CADR (A B C)) =
16. Специальные функции quote – объявление константы, предохраняющее аргумент от вычисления label / defun / de /
17. Примеры вычисления по специальным функциям (QUOTE A) – константа A объявлена (QUOTE (A B C)) –
19. Скачать презентацию

Слайд 2

Основоположник
Джон Маккарти предложил проект языка Лисп (LISP - LISt Processing) в

качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта.
Существует и активно применяется более трехсот диалектов Лиспа и родственных ему языков: Interlisp, muLisp, Clisp, Scheme, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др.

Слайд 3

Математические основы
Сформулированная Джоном Маккаpти (1958) концепция символьной обработки информации компьютером восходит

к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов прошлого века. Выбирая лямбда-исчисление как теоретическую модель, Маккарти предложил рассматривать функции как общее базовое понятие, к которому достаточно естественно могут быть сведены все другие понятия, возникающие при программировании

Слайд 4

Лямбда-исчисление
Лямбда-исчисление (λ-исчисление) - формальная система, разработанная американским математиком Алонзо Чёрчем, для

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

Слайд 5

Чистое лямбда-исчисление
Это простейший из семейства прототипных языков программирования, чистое λ-исчисление, термы

которого, называемые также объектами («обами»), или λ-термами, построены исключительно из переменных применением аппликации и абстракции. Изначально наличие каких-либо констант не предполагается.
В основу λ-исчисления положены две фундаментальные операции: аппликация (означает применение или вызов функции по отношению к заданному значению) и абстракция (конструирует новые функции по заданным выражениям).

Слайд 6

Универсальность понятия «функция»
Универсальность понятия "функция" и разнообразие видов его применения позволяет

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

Слайд 7

Основные особенности ЛИСПа
Унификация понятий "функция" и "значение" – представление функций можно

строить из их частей и вычислять по мере поступления и обработки информации.
Интерпретирующий и компилирующий режим работы – в одной программе могут иметься как откомпилированные, так и интерпретируемые функции.
Интегральность ограничений – если не хватает памяти, то не отдельные блоки данных, а на всю задачу. При этом «мусорщик» автоматически будет искать свободное место.
Уточняемость решений – реализация языка обычно содержит списки свойств объектов, приспособленные к внешнему доопределению отдельных элементов.
Множественность определений имен – обеспечение полиморфизма и более общих схем обработки вариантов функциональных построений.

Слайд 8

Основные особенности ЛИСПа
Одинаковая форма данных и программ – списочные структуры. ЛИСП-программы

могут обрабатывать не только данные, но и другие ЛИСП-программы и самих себя. При трансляции можно сформировать выражение и проинтерпретировать его в качестве программы и выполнить ее.
Хранение данных, не зависящее от места размещения в ОЗУ – порядок следования в памяти списочных ячеек с программами и данными не существенен. Добавление/удаление элементов производится без переноса всего списка в другие ячейки памяти.
Функциональная направленность – в результате каждого действия возникает некоторое значение, которое становится элементом следующих действий.

Слайд 9

Основные особенности ЛИСПа
Нестрогая типизация данных – типы сопровождают лишь сами объекты,

а не имена символов, списков, функций (позднее связывание). Одни и те же переменные могут представлять объекты разных типов.
Пошаговое программирование – программирование и тестирование осуществляются функция за функцией, которые последовательно определяются и тестируются.
ЛИСП одновременно является языком и прикладного, и системного программирования.

Слайд 10

Структура данных в ЛИСПе

Слайд 11

Чем ошибочна данная схема?
S-выражения
Атомы
Символ
Константы
Число
T
NIL Списки

Слайд 12

Примеры
Символы: x, u-1997, символ, function
Числа: 24, 35.6, 6.3е5
Списки: (а в (с

о) р), (+ 3 6), ((А В) (D C))
Равнозначность списков:
(А B C) = (A (B (C Nil)))
((A B) C) = ((A (B Nil)) (C Nil))
(A) = (A Nil)
((A)) = ((A Nil) Nil)
(A (B C)) = (A ((B C) Nil))
() = Nil
(()) = (Nil Nil)

Слайд 13

Базис ЛИСПа
Примитивные функции:
сons – строит списки из бинарных узлов. Первый аргумент

произвольного вида – в левой части узла, второй аргумент (список) – в правой части узла.
car – доступ к первому элементу списка
cdr – доступ к части списка после удаления его первого элемента
atom – позволяет различать составные (результат – «ложь») и атомарные (результат – «истина») объекты
eq – проверка атомарных объектов на равенство

Слайд 14

Примеры вычисления по примитивным функциям
(CAR (CONS x y)) = x
(CDR (CONS

x y)) = y
(ATOM (CONS x y)) = Nil
(CONS (CAR x) (CRD x)) = x – для неатомарных x
(EQ x x) = T – если x – атом
(EQ x y) = Nil

Слайд 15

Примеры вычисления по примитивным функциям
(CAAR ((A) B C)) = A
(CADR (A

B C)) = B вычисляется CDR, затем СAR
(CADDR (A B C)) = С вычисляется дважды CDR, затем CAR
(CADADR (A (B C) D)) = C вычисляется два раза (CDR, затем CAR)

Слайд 16

Специальные функции
quote – объявление константы, предохраняющее аргумент от вычисления
label / defun

/ de / csetq – конструктор функций, первый аргумент – имя функции (результат), второй – определение функции
lambda – определение функции (lambda (x1 x2 … xn) fn) fn – тело функции xi – параметры определения, которые имеют аргументы в теле функции
cond – ветвление (cond (условие действие по первой ветке) (T действие по второй ветке))

Слайд 17

Примеры вычисления по специальным функциям
(QUOTE A) – константа A объявлена
(QUOTE (A

B C)) – константа (А В С) объявлена
(ATOM (QUOTE A)) = T – аргументом предиката является атом А
(АТОМ (QUOTE (A B C))) = Nil – аргументом предиката является список (А В С)
(АТОМ А) – значение не определено, т.к. оно зависит от вхождения переменной А, а ее значение зависит от контекста и должно быть определено или задано до попытки выяснить, атом ли это
(COND ((EQ (CAR x) (QUOTE A)) (CONS (QUOTE B) (CDR x))) (T x))

Введение в Лисп

Содержание

ОсновоположникДжон Маккарти предложил проект языка Лисп (LISP - LISt Processing) в

Математические основыСформулированная Джоном Маккаpти (1958) концепция символьной обработки информации компьютером восходит

Лямбда-исчислениеЛямбда-исчисление (λ-исчисление) - формальная система, разработанная американским математиком Алонзо Чёрчем, для

Чистое лямбда-исчислениеЭто простейший из семейства прототипных языков программирования, чистое λ-исчисление, термы

Универсальность понятия «функция»Универсальность понятия "функция" и разнообразие видов его применения позволяет

Основные особенности ЛИСПаУнификация понятий "функция" и "значение" – представление функций можно

Основные особенности ЛИСПаОдинаковая форма данных и программ – списочные структуры. ЛИСП-программы

Основные особенности ЛИСПаНестрогая типизация данных – типы сопровождают лишь сами объекты,

Структура данных в ЛИСПе

Чем ошибочна данная схема?S-выраженияАтомыСимволКонстантыЧислоTNIL Списки

ПримерыСимволы: x, u-1997, символ, functionЧисла: 24, 35.6, 6.3е5Списки: (а в (с

Базис ЛИСПаПримитивные функции:сons – строит списки из бинарных узлов. Первый аргумент

Примеры вычисления по примитивным функциям(CAR (CONS x y)) = x(CDR (CONS

Примеры вычисления по примитивным функциям(CAAR ((A) B C)) = A(CADR (A

Специальные функцииquote – объявление константы, предохраняющее аргумент от вычисленияlabel / defun

Примеры вычисления по специальным функциям(QUOTE A) – константа A объявлена(QUOTE (A

Похожие презентации