Русский
Русский
English
Статистика
Реклама

Лисп

Частичное применение и каррирование функций в Лиспе

30.09.2020 10:08:50 | Автор: admin
Одно из известных преимуществ Лиспа над другими языками программирования состоит в том, что в Лиспе проще, чем где бы то ни было, реализуются различные новые механизмы, появляющиеся в современных языках программирования. Причин тому несколько: это и гомоиконность Лиспа (единая форма представления программ и данных) и уникальная по своим возможностям система макро. В общем, Лисп не зря называют программируемым языком программирования.

В этой небольшой заметке мы рассмотрим, как можно реализовать в Лиспе такие, весьма популярные ныне программные механизмы, как частичное применение и каррирование функций. При этом я буду использовать свою реализацию Homelisp (это чистый интерпретатор Лиспа с некоторыми дополнительными возможностями).
Вероятно, использование частичного применения в Common Lisp будет не очень простым (в связи с тем, что для вызова вычисляемого функционального объекта нужно использовать funcall/apply); в Scheme дело должно обстоять проще. В ближайшее время я планирую опубликовать новую версию HomeLisp, в котором для вызова вычисляемого функционального объекта не требуется funcall/apply. В тех случаях, когда поведение кода отличается, я буду это подчёркивать.

Частичное применение и каррирование это строгие математические операции. Но мы рассмотрим их на пальцах, без обращения к лямбда-исчислению и комбинаторной логике.

Частичное применение функции f это получение из функции f новой функции f', которая уже приняла заданные аргументы, и готова принять остальные. Для чего нужно частичное применение? Например, для того, чтобы из функции можно было вернуть функциональное значение.

Рассмотрим частичное применение на простом примере. Пусть функция f задана формулой:

f(x,y,z)=x+y**2+z**3

тогда частичное применение этой функции с аргументами x=1 и y=2 должно породить функцию:

f'(z) = 1+4+z**3 = 5+z**3

В языке Хаскелл частичное применение ничего не стоит программисту:

Prelude> f x y z = x+y**2+z**3  -- задаем функциюf :: Floating a => a -> a -> a -> aPrelude> f 1 2 3 -- проверим...32.0 -- верно!it :: Floating a => aPrelude> f' = f 1 2  -- частично применяем её при x=1 y=2 и сохраняем новую функцию f'f' :: Floating a => a -> aPrelude> f' 3 -- функция f' принимает один аргумент32.0 -- и даёт верный результатit :: Floating a => a

Однако, в Лиспе такая попытка приведет к неудаче:
(defun f (x y z) (+ x (* y y) (* z z z))) ;; Определяем функцию==> F(f 1 2 3) ;; Проверяем работоспособность==> 32 ;; Верно(f 1 2) ;; Пробуем задать не все аргументы...PairLis: Слишком мало фактических параметров Функция: FФормальные  параметры: (X Y Z)Фактические параметры: (1 2)==> ERRSTATE

Конечно, в Лиспе существует механизм создания функций с любым числом аргументов (конструкция &rest); можно создать функцию, которая будет принимать два или три (или десять) параметров:
(defun s (&rest x) ;; неопределенное к-во параметров собирается в список x  (apply '+ x)) ;; и этот список суммируется==> S(s 1 2) ;; два параметра==> 3(s 1 2 3) ;; три параметра==> 6

Но важно понимать разницу: эта функция обрабатывает все параметры и возвращает результат вычисления, тогда как частичное применение дает в результате новую функцию, которая готова продолжить вычисления.

Посмотрим, как можно реализовать на Лиспе механизм частичного применения функции. И поможет нам в этом да-да, аппарат анонимных функций (lambda). Некоторые программисты думают, что анонимные функции нужны только для экономии имен (мол, их место во всяких stream-map-filter-reduce для того, чтобы выполнить короткое действие над элементом последовательности). На самом же деле анонимные функции способны на гораздо большее, в чем мы сейчас и убедимся.

Начнем с того, что рассмотрим, как функция может вернуть другую функцию как результат. В Лиспе это очень просто:
(defun func-gen (x)   (lambda (y) (+ x (* y y))))==> FUNC-GEN(func-gen 5)==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))

Как видим, функция возвращает замыкание, в котором значение свободной переменной x зафиксировано (равно 5). Результат функции можно вызвать как функцию. Для этого в Common Lisp и HomeLisp (с редакцией ядра <= 15.53) придется использовать funcall:
(funcall (func-gen 5) 7)==> 54

Теперь понятно, как можно действовать, если мы хотим взять функцию f от n аргументов и одно значение x, а в результате получить функцию от (n-1) аргумента. Обозначим список формальных параметров нашей функции через plist. Тогда все, что нужно сделать, это построить вот такое лямбда-выражение:
(lambda (хвост-plist) (apply f (cons x хвост-plist)))

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

Значит, для частичного применения функции нужно на базе этой функции построить лямбда-выражение, у которого аргументов будет на единицу меньше, а аргумент, заданный при частичном применении, будет учтен во внутреннем вызове нашей функции в теле лямбда-выражения.
Как это реализовать? Несложно В HomeLisp есть функция getd, которая обеспечивает доступ к определяющему выражению функции или макро:
(defun g (x y z) (+ x (* x y) (* x y z)))==> G(getd 'g)==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))

Как видим, getd возвращает определяющее выражение функции, в котором вместо лямбда находится специальный атом EXPR. Мы можем взять список параметров нашей функции (второй элемент результата) и построить лямбда-выражение, параметрами которого будет хвост исходного списка параметров, а в теле лямбда-выражения мы вызовем исходную функцию с полным списком параметров.
(defun part-apply (f a)  (let* ((plist (cadr (getd f))) ;; исходный список параметров         (rlist (cdr plist))     ;; список параметров без первого          (clist (cons a rlist))) ;; список для вызова с заданным a        `(lambda ,rlist (apply (quote ,f) (list ,@clist)))))

Из приведенного кода легко понять, что plist это исходный список функции f, которую мы хотим применить частично. rlist исходный список без первого элемента, а clist полный список параметров, в котором первый элемент заменен на значение x. Конкретно, для функции g, приведенной выше plist = (x y z), rlist=(y z), а clist=(a y z). Проверим теперь, как работает частичное применение:
(part-apply 'g 111)==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))

Можно убедиться, что это именно то, что и планировалось: part-apply вернула новую функцию, с числом аргументов, на единицу меньшим. Если эту новую функцию вызвать с параметрами y и z, то результат будет в точности такой же, как и вызов исходной функции g с тремя аргументами: 111 y и z:
(g 111 1 2)==> 444 ;; исходный результат(funcall (part-apply 'g 111) 1 2) ;; вызов "по-коммон-лисповски"==> 444 ((part-apply 'g 111) 1 2) ;; вызов "по-схемному"==> 444


Ниже я (для краткости) не буду указывать funcall. В следующем ядре HomeLisp будет изменена схема вычисления функций станет доступным схемный синтаксис.

Пойдем дальше. Теперь возникнет естественное желание повторно применить результат повторного применения. Это оказывается уже совсем простым делом ведь результат частичного применения это лямбда-выражение, а оно устроено почти идентично с результатом, который возвращает getd. Список параметров лямбда-выражения это второй элемент списка. Все эти соображения позволяют построить окончательное решение поставленной задачи:
(defun part-apply (f a)  (cond ((and (atom f) (member 'expr (proplist f))) ;; *** функция ***         (let* ((plist (cadr (getd f))) ;; исходный список параметров                (rlist (cdr plist))          ;; список параметров без первого                 (clist (cons a rlist)))    ;; список для вызова с заданным a                `(lambda ,rlist (apply (quote ,f) (list ,@clist)))))        ((eq 'lambda (car f))   ;; *** лямбда-выражение ***         (let* ((plist (cadr f))        ;; исходный список параметров                (rlist (cdr plist))       ;; список параметров без первого                 (clist (cons x rlist))) ;; список для вызова с заданным x               `(lambda ,rlist (apply (quote ,f) (list ,@clist)))))        (t (raiseerror "part-apply: неверен функциональный аргумент"))))

Здесь добавлен анализ первого параметра: если это атом, то он должен представлять функцию (типа EXPR); если первый параметр не является ни правильным атомом, ни лямбда-выражением, то возбуждается состояние ошибки. Код, разумеется, можно было бы еще подсократить, две почти идентичные ветви оставлены для наглядности. Посмотрим теперь, на что способна эта функция:
(part-apply (part-apply 'g 1) 2) ;; двукратное применение возвращает функцию одного аргумента==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))((part-apply (part-apply 'g 1) 2) 3) ;; ее можно вызвать и получить верный результат==> 9(part-apply (part-apply (part-apply 'g 111) 1) 2) ;; трехкратное применение возвратит безаргументную функцию==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ее тоже можно вызвать...==> 444(setq u (part-apply 'g 111)) ;; результат частичного применения можно присвоить переменной==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)));; Создана глобальная переменная U(part-apply u 1) ;; частичное применение можно продолжить==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))((part-apply u 1) 2) ;; а можно вызвать==> 444


Теперь займемся каррированием. Каррированная функция, принимая недостаточное число аргументов, возвращает функцию, способную обработать остальные. Главное предназначение каррирования это как раз обеспечение частичного применения. Мы зашли с другого конца: рассмотрим теперь, как можно реализовать каррирование, если имеется частичное применение.

Пусть дана функция g нескольких аргументов. Мы построим ее каррированный вариант под другим именем !g. Суть построения будет такой: функция !g будет примать неопределенное число аргументов. После вызова она должна проверить количество переданных аргументов. Если это количество равно количеству аргументов исходной функции g, то следует из передать на вход g. Если количество аргументов больше, чем способна принять g, то следует возбудить состояние ошибки. А вот если количество аргументов меньше, чем у функции g, то да-да нужно выполнить последовательное частичное применение. Результат этого применения вернуть.

В данном случае удобно использовать макро. Код с комментариями приведен ниже:

(defmacro curry (f)   (let* ((parmlist (cadr (getd f))) ;; список параметров f           (body      (cddr (getd f))) ;; тело функции f   (lp          (length parmlist)) ;; длина списка параметров f   (cf          (implode (cons '! (explode f))))) ;; новое имя для результата каррирования`(defun ,cf (&rest x)   (let ((lx (length x))) ;; длина актуального списка параметров        (cond  ((= lx ,lp) ;; полное применение                    (let ((e `(lambda ,parmlist ,@body)))                          (apply e x)))                  ((> lx ,lp) ;; параметров слишком много                          (raiseerror "curry: Слишком много фактических параметров"))                  (t (let ((tmp nil)) ;; здесь будет результат                (iter (for a in x) ;; частично применяем заданные параметры    (setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))                       tmp)))))))


Здесь следует прокомментировать построение нового имени функции. Для этого используются функции HomeLisp explode, которая из атома строит список составляющих его символов, и implode, которая сжимает символы списка в один, порождая новый атом.

Проверим теперь наш макро в деле:
(curry g) ;; каррируем g==> !G ;; каррированный вариант(!g 1 2 3) ;; при обычном вызове==> 9 ;; ведет себя как g(!g 1 2) ;; если аргументов недостаточно - вернет функцию для обработки остальных==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)));; Можно сразу и вычислить результат:((!g 1 2) 3) ;; остался один аргумент==> 9((!g 1) 2 3) ;; осталось два аргумента==> 9(!g 1 2 3 4) ;; лишние аргументы вызовут ошибкуcurry: Слишком много фактических параметров==> ERRSTATE


Каррирование у нас выполнено без дополнительного контроля. И мы не реализовали каррирования лямбда-выражение. При желании все это можно сделать

Вот так можно без большого напряжения сил реализовать в Лиспе частичное применение функций и каррирование. Лисп замечательный язык!

Спасибо за внимание.
Подробнее..

Краткая история Chaosnet

06.07.2020 20:09:26 | Автор: admin
Мы решили совершить еще один вояж в прошлое сетевых технологий. На сей раз мы поговорим о Chaosnet, специфическом сетевом протоколе, который использовался в 1970-х годах в Lisp-машинах. Исходным материалом для статьи послужила заметка на TwoBitHistory, которую мы расширили и дополнили собственными находками и иллюстрациями.

Если с помощью dig отправить к DNS запрос о каком-то сайте, например, it-grad.ru, мы получим примерно такой ответ:

$ dig it-grad.ru



В строке Answer Section содержится информация о записи типа A.

Приглядимся к полю IN. Возможно, кто-то думает, будто IN это такой предлог: it-grad.ru IN (внутри) A и имеет IP-адрес 212.116.122.3. На самом же деле IN значит Internet. Это класс записи.

Возникает закономерный вопрос: а какие, собственно, еще варианты здесь могут быть? Как можно получить доступ к хосту, который находится не в Интернете? Может показаться, что IN это вообще единственное значение, которое имеет смысл в современном мире. К тому же, если пробить тот же it-grad.ru и явно указать, что вы хотите получить запись с классом, отличным от IN, DNS-сервер вернет ошибку. Давайте сделаем еще один запрос и посмотрим, к чему приведет явное указание класса. Например, HS (Hesoid). Сервер вернет статус SERVFAIL.

$ dig -c HS it-grad.ru



Классы, отличные от IN, практически не используются в современном мире. Но это вовсе не означает, что их нет: например, существуют HS или CH. HS зарезервирован для использования в информационной службе Hesoid, названной в честь древнегреческого поэта. А вот класс CH зарезервирован под нужды героя статьи, Chaosnet. На текущий момент он представляет разве что историческую, мемориальную ценность.


Остальные классы DNS

Сегодня мир принадлежит TCP/IP. Этот протокол (вместе с UDP) управляет подавляющим числом сетевых подключений. Но, как видите, кое-где еще остались следы другой, давно исчезнувшей системы, и это по-своему замечательно. Что такое Chaosnet? Каким он был и кем использовался? Почему он канул в Лету? Давайте разберемся.

Всё началось в MIT


Chaosnet был создан сотрудниками лаборатории по изучению искусственного интеллекта MIT в 1970-х. Он был сопутствующим продуктом проекта машины, которая могла бы работать на языке программирования Lisp более эффективно, чем компьютеры общего назначения.

Lisp это детище профессора MIT и лауреата премии Тьюринга 1971 года Джона Маккарти. Он является основоположником функционального программирования и автором термина (порицаемого в некоторых кругах) искусственный интеллект.


Джон Маккарти собственной персоной

Самой ранней версией Lisp принято считать интерпретатор 1958 года для IBM 704. Фактически, это один из старейших актуальных языков программирования наряду с Фортраном.

Первое публичное упоминание о Lisp (версия 1) датируется 1960-м годом. А к 1962-му была готова продвинутая и усовершенствованная версия 1.5. Lisp включал в себя массу инструментов и функций, которые присутствуют в подавляющем большинстве современных языков программирования.

Это был первый язык, в котором была реализована система сборки мусора и автоматическое управление памятью. Он получил огромную популярность и любовь среди программистов, работавших над ИИ. Вот только один из известных примеров: SHRDLU, программа Терри Винограда, которая позволяла обращаться к компьютеру на естественном языке и заставлять его решать простые логические задачи. Была написана на DEC PDP-6 с использованием языков Lisp и Micro Planner.


Пример, иллюстрирующий SHRDLU

Единственной проблемой Lisp была его скорость. Простейшие операции занимали вдвое больше времени, чем в других языках, поскольку переменные проходили двойную проверку: и в процессе выполнения, и на этапе компиляции. Сборщик мусора работал более секунды на тогдашнем IBM 7090, находившемся в распоряжении MIT. Проблема производительности стояла чрезвычайно остро: ИИ-программисты строили системы, взаимодействовавшие с пользователем в реальном времени.

В конце 1970-х было решено построить специальный компьютер для Lisp с учетом всех особенностей языка. У компьютера должно было быть больше памяти и компактный набор инструкций, подходящих для Lisp. Предполагалось, что для проверки типов будет использоваться самостоятельная электрическая цепь, и это многократно ускорит работу кода. Еще одна особенность Lisp-машин состояла в том, что ни о каком разделении процессорного времени и речи быть не могло: амбициозные программы задействовали все ресурсы компьютера без остатка. Каждому пользователю приписывался отдельный центральный процессор. Вот как сотрудники Lisp Machine Group описывали перспективы работы с таким компьютером:
Lisp Machine это персональный компьютер. Это значит, что процессор и основная память не разделяются между пользователями. Система состоит из пула процессоров, каждый из которых имеет собственную основную память и собственный диск. Когда пользователь входит в систему, ему назначается процессор, и он эксклюзивно использует его в течение сеанса. При выходе из системы процессор возвращается в пул и может быть использован следующим человеком. Таким образом, нет конкуренции за память, а страницы, на которые часто ссылается пользователь, остаются в ядре, и накладные расходы значительно уменьшаются.
Разумеется, понятие персональный компьютер в отношении Lisp-машин употребляется в несколько ином значении, чем мы привыкли теперь.


Лисп-машина


Промо-фотография терминала

Предполагалось, что пользователи будут работать не непосредственно с компьютером, а со специальными терминалами. Каждый пользователь получит выделенные мощности, а сам компьютер будет находиться в машинном зале, чтобы не докучать всему офису звуками вычислений. Процессоры будут иметь доступ к файловой системе и к периферийным устройствам, таким как принтеры, через высокоскоростную локальную сеть с полностью распределенным управлением. Так и появился Chaosnet. Его создатели Томас Найт (биография на русском языке) и Джек Холлоуэй.

Chaosnet одновременно являлся и железным стандартом, и программным протоколом. В части оборудования этот стандарт был похож на Ethernet, а программный протокол в конечном итоге и работал по Ethernet. Но в отличие от TCP/IP, предполагалось управление исключительно локальными сетями. Один из сотрудников MIT Artificial Intelligence Lab рассказывал, что при разработке Chaosnet основное внимание было уделено написанию протокола, который в пределах небольшой сети показывал бы лучшие результаты, чем его конкуренты.

Скорость была крайне важна, поскольку Chaosnet был промежуточным звеном между процессором Lisp и файловой системой. Сетевые задержки сказались бы на скорости выполнения базовых операций. Для обеспечения максимального быстродействия за основу была взята (а в дальнейшем доработана) Network Control Program, применявшаяся тогда в Arpanet. Chaosnet, как и современный TCP/IP, использовал пакетные подтверждения сообщений, что позволило сократить общее количество пересылаемых пакетов на 30-50%.

Chaosnet также мог обойтись без алгоритмов маршрутизации, поскольку большинство хостов в сети Lisp-машин были связаны одним коротким проводом (CATV, коаксиальный кабель). Дэвид Мун, участник Lisp Machine Group писал, что схема маршрутизации Chaosnet основана на предположении, что сеть достаточно проста и в ней существует всего несколько коротких путей. Сложные схемы здесь не нужны. В результате управляющая программа Chaosnet весила вдвое меньше, чем Network Control Program для Arpanet.

Протокол Chaosnet имел и другие особенности. Так, длина адреса составляла всего 16 бит, что вдвое меньше длины адреса IPv4. Вполне разумный подход, учитывая, что Chaosnet предназначался только для локальных сетей. Первые 8 бит указывали на подсеть, вторые на конкретный хост.

Также Chaosnet не использовал номера портов. Вместо этого процесс, который хотел подключиться к другому процессу на другом компьютере, осуществлял запрос, в котором указывалось контактное имя цели. Зачастую название конкретной службы. Например, один хост мог попытаться подключиться к другому хосту, используя контактное имя TELNET. Это весьма похоже на TCP: например, к порту 80 можно обратиться по имени HTTP.

DNS-класс CH, Chaosnet, был добавлен в DNS в 1986 году. Он заменил другой класс, CSNET (Computer Science Network). Теперь уже сложно выяснить, почему именно Chaosnet получил свое место в DNS. Существовали и другие семейства протоколов, которые почему-то не были в неё добавлены. Например, Пол Мокапетрис (Paul Mockapetris), один из главных архитекторов DNS, писал, что изначально предполагалось включить в систему доменных имен класс сетевого протокола Xerox. Но по неизвестным причинам этого не произошло. А Chaosnet, возможно, был добавлен только потому, что большая часть работы над Arpanet и Интернетом производилась в BBN Technologies. Сотрудники этой компании были тесно связаны с MIT и, вероятно, многое слышали о Chaosnet.

Поначалу Lisp-машины имели коммерческий успех и продавались Symbolics и Lisp Machines Inc. Но с течением времени надобность в них отпала. Их вытеснили микрокомпьютеры, которым по силам было работать с Lisp, но уже без специальных схем. Затем на сцену вышел TCP/IP, в котором были исправлены недоработки Arpanet, и Chaosnet потерял актуальность.

Призрак прошлого


К сожалению, информации о Chaosnet сейчас не так уж и много. RFC 675, который, по сути, является первой версией TCP/IP, был опубликован в 1974 году. Chaosnet же появился на год позже. TCP/IP в конце концов завоевал мир, а Chaosnet развития не получил. Есть вероятность, что какие-то практики Chaosnet оказали влияние на разработку TCP/IP, но никаких подтверждающих или опровергающих это фактов нет. Интересный факт: в первоначальной версии Манифеста GNU упоминается поддержка протокола Chaosnet.

Различные имплементации Chaosnet и интересные ссылки:


Единственным заметным следом Chaosnet в мировой паутине является класс CH DNS. Это не более, чем призрак альтернативного сетевого протокола в мире победившего TCP/IP. Забавный артефакт цифровой археологии. Но он является живым напоминание о том, что интернет не появился в одночасье, а TCP/IP не единственный способ соединять компьютеры между собой.

А еще это повод задуматься над тем, что интернет это далеко не самое крутое слово, которым можно было окрестить нашу глобальную коммуникационную систему.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru