LINUX.ORG.RU

Алан Keй: deep flows in Lisp's logical foundations

 


1

5

I could hardly believe how beautiful and wonderful the idea of LISP was. I say it this way because LISP had not only been around enough to get some honest barnacles, but worse, there were deep flaws in its logical foundations. By this, I mean that the pure language was supposed to be based on functions, but its most important components — such as lambda expressions, quotes, and conds — were not functions at all, and instead were called special forms ... My next questions was, why on Earth call it a functional language? Why not just base everything on FEXPRs and force evaluation on the receiving side when needed? I could never get a good answer

Далее Кей пишет о том, что эти размышления привели его к идее создания модели Ъ-ООП

А, все же интересно, кто-нибудь, таки, дал ответ на вопрос Алана Кея?

My next questions was, why on Earth call it a functional language?
Lisp
setq
functional language

И правда, почему вы его называете функциональным и почему это проблема Лиспа?

anonymous
()

Первый вопрос - риторика и демагогия

Второй: потому что тормоз (интерпретатор) никому не нужен, а писать оптимизирующий компилятор (чтобы не было потерь в RT на тех бранчах, которые можно было отсеять во время компиляции на макросах, которых, «очевидно», на фэкспрах не будет) jff никому не упёрлось.

Хотя ты не согласишься :)

yyk ★★★★★
()

А я вот недавно перестал видеть грань между парадигмами. Либо просто забыл теорию, либо приблизился к дзену.

Debasher ★★★★★
()
Ответ на: комментарий от Debasher

У тебя зрение ослабло. Воспользуйся lens'ами из Haskell.

Virtuos86 ★★★★★
()

Тем, кто пытается ответить аргументированно: просмотрите список тем ТС. Это уже n+1 -ая тема с троллингом лиспа/FP.

И да, вообще-то «flaws», а то получается «глубокие потоки в логических основах Lisp».

Cheater
()

Чудесные слова «синтаксис», «семантика», не? Специальные формы есть везде.

http://github.com/pi8027/lambda-calculus/blob/master/agda/Lambda/Core.agda

http://www.cse.chalmers.se/~nad/repos/codata/Lambda/Syntax.agda

http://www.iis.sinica.edu.tw/~scm/2008/typed-lambda-calculus-interprete/

http://www.cs.cmu.edu/~rwh/plbook/book.pdf

http://www.cis.upenn.edu/~bcpierce/sf/current/toc.html

«pure language»?

http://www.pps.univ-paris-diderot.fr/~saurin/Enseignement/LMFI/articles/Hindl...

«functional language» — в такой же мере, в какой C++11 <functional>, современник фортрана с HOF.

motto
()
Ответ на: комментарий от motto

Тут, видимо, имеется в виду, мы можем сделать язык, где нет никаких функций, в обычном понимании, а все есть фэкспры. Через фэкспры можно описать сам язык, выразить язык в терминах самого языка. Язык концептуально упрощается, он отражается в себе самом, вот об этом тут речь. Все выражения в языке — есть первоклассные объекты языка. Короче, фэкспры как основа на порядки мощней. В этом и заключается мессага, что обычные функции — заведомо более слабая концепция, и в то же время, абсолютно не нужная, так как легко выразима фэкспрами.

terminator-101
() автор топика
Ответ на: комментарий от motto

Чудесные слова «синтаксис», «семантика», не? Специальные формы есть везде.

Вот именно, что в лиспе изначальном не было никакого синтаксиса, кроме скобок, разве что, поскольку синтаксис выразим средствами языка чуть более чем полностью.

terminator-101
() автор топика
Ответ на: комментарий от terminator-101

Здесь имеется в виду концептуальная чистота, а не то, что ты подумал.

Между тем, актуальные (?) тезисы про эти ваши ф-выражения — http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf.

In the setting of computational semantics and calculi, pure means without side-effects.

Также посмотрим на 8.4.1 Trivialization of theory и 8.4.2 Computation and logic (натурально — нафиг нам рассуждать о вычислениях, вычислять нада, с метапрограммированием во все поля) — то есть если кто-то хочет двигаться в сторону Curry-Howard-Lambek-Seely-Voevodsky (и более типичного статического анализа), то кто-то должен двигаться в обратном направлении? :)

Overall, fp-calculus has three parts: a set of terms representing S-expressions (pairs, symbols, and constants), with a trivial equational theory; a subcalculus representing pure fexpr-call structure, which has isomorphically the equational theory of λ-calculus; and machinery for evaluation, connecting the first two components and determining what mixture of the weak and strong theories of those components will bear on a given situation.

motto
()
Ответ на: комментарий от motto

Вообще в лиспе можно же звать macro-function — кидаем невычисляющиеся аргументы, получаем невычисленное выражение, потом можно заевалить (про окружение ХЗ).

Так же в квазицитировании TH (и что-то там для *ML было) можно писать функции из/в Q и сплайсить по желанию (хотя много неудобных ограничений).

Если системы типов это ограниченная форма метапрограммирования ((с) anonymous), то можно и на них посмотреть (http://www.cl.cam.ac.uk/~ok259/agda-course-13/).

motto
()
Ответ на: комментарий от motto

то кто-то должен двигаться в обратном направлении? :)

Да, думаю тот, кто хочет программировать, а не быть обезьяной, подчиненной исполнителю языка. Статика интересна инженеру лишь тогда, когда он пишет компилятор, интересна с точки зрения возможностей парсинга и анализа текста.

terminator-101
() автор топика
Ответ на: комментарий от motto

macro-function

если ты про современные лиспы, то это макросы, они сливают вобще то фэкспрам, так как не являются первоклассными объектами.

Так же в квазицитировании

Квазицитирование — это сущий ад. Просто цитирование может заменить фэкспры, в принципе, при наличии полноценного эвала, который, как раз таки

про окружение ХЗ

про окружение. Если есть нормальный эвал, функции с квотированием будут семантически эквивалентны фекспрам, просто не так удобны.

terminator-101
() автор топика
Ответ на: комментарий от terminator-101

Парсинг ни при чём. Примитивный статический анализ — да.

Ещё оно мозги ломает, так что пациенты больше не мыслят написания нормального кода в универсуме «динамических говноязычков» (с) (true story :)).

Про ф-выражения — не знаю, пока что им заслуженно премию Дарвина нужно давать :)

motto
()
Ответ на: комментарий от terminator-101

они сливают вобще то фэкспрам, так как не являются первоклассными объектами.

Являются

> (macro-function 'loop)
#<COMPILED-FUNCTION LOOP>

monk ★★★★★
()
Ответ на: комментарий от terminator-101

Если есть нормальный эвал, функции с квотированием будут семантически эквивалентны фекспрам, просто не так удобны.

Верно. Фекспры эквивалентны эвалу. Но макросы почти всегда лучше эвала

1) скорость: макрос выполняется только при компиляции

2) безопасность: макрос во время компиляции проверяет синтаксическую корректность своих аргументов

3) модульность: макрос связывает те переменные в окружении которых он определяется, а не запускается => нет случайных поломок, если в окружении выполнения нет нужной переменной (хотя так можно при большом желании и фекспры переделать)

monk ★★★★★
()
Ответ на: комментарий от monk

Первый два пункта, что ты приводишь, произносятся точно так же в споре о динамической/статической типизации. Ты, вот, интересно, на какой стороне?

макрос связывает те переменные в окружении которых он определяется, а не запускается

Макрос как функция определен в каком-то лексическом окружении. Но он не имеет доступа к лексическому окружению времени исполнения. Тем не менее он может эмитировать переменные в лексическое окружение своих подформ. Причем безопасность этой эмиссии зависит целиком и полностью от ридера.

Фэкспрами можно делать множество вещей, которые невозможны с макросами. Кроме того, они решают множество теоретических проблем макросов. Макросы, если они кому-то еще нужны, могут быть оптимизацией фэкспров, как compiler macro.

komputikisto
()
Ответ на: комментарий от terminator-101

если ты про современные лиспы, то это макросы, они сливают вобще то фэкспрам, так как не являются первоклассными объектами.

Являются. Не сливают. Фекспры не сильнее обычных ф-й с выразительной точки зрения. Макросы строго сильнее.

anonymous
()
Ответ на: комментарий от komputikisto

Фэкспрами можно делать множество вещей, которые невозможны с макросами.

Что, например? В реальности все наоборот - т.к. фекспры вычисляются в рантайме, их выразителньая способность падает до нуля.

Кроме того, они решают множество теоретических проблем макросов.

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

anonymous
()
Ответ на: комментарий от komputikisto

Но он не имеет доступа к лексическому окружению времени исполнения.

Имеет. Для CL:

(defmacro setit (val) `(setf it ,val))

> (let ((it 1)) (setit 2) it)
2

Для Scheme:

(define-syntax (setit! stx)
  (let ((it (datum->syntax stx 'it)))
    (syntax-case stx ()
      ((_ val) #`(set! #,it val)))))

> (let ((it 1)) (setit! 2) it)
2

Фэкспрами можно делать множество вещей, которые невозможны с макросами.

Не больше, чем то, что возможно с eval (или макрос + eval). Или давай пример.

monk ★★★★★
()
Ответ на: комментарий от anonymous

Что, например?

Раскрытие формы в разный код в зависимости от значения переменной в рантайме. Что-то типа (defview get-vars-1-2 (input var1) (input var2) (submit)), которое даёт либо GTK форму, либо ncurses в зависимости от переменной окружения $DISPLAY.

monk ★★★★★
()
Ответ на: комментарий от monk

Имеет.

Макрос не имеет. Макрораскрытие имеет доступ. Давай различать.

Не больше, чем то, что возможно с eval

Согласен. Преимущества фекспров в том, что они устраняют излишнюю сложность вот того, о чем ты говоришь (макрос + eval). Бритва Оккама! Макросы - двухуровневая идея, а фекспры - одноуровневая. Когда тебе надо определить что-то простое типа cond, то подход макросов работает, но если в макрораскрытии будет еще и eval, то зачем плодить сущности...

komputikisto
()
Ответ на: комментарий от monk

или макрос + eval

Eval бывает разный. В CL он имеет один аргумент, что почти ничего нового не вносит в язык. John Shutt использовал eval с двумя аргументами. На самом деле в языке, который поддерживает полную рефлексию eval должен принимать все состояние вычислительного процесса. Вот эти аргументы: выражение, окружение, динамическое окружение, континуация. Наличие последнего аргумента означает, что такой eval ведет себя как черная дыра, т.е. ничего не возвращает, а передает значение в континуацию. Единственный диалект с таким eval'ом — 3-Lisp.

komputikisto
()
Ответ на: комментарий от komputikisto

но если в макрораскрытии будет еще и eval, то зачем плодить сущности...

Чтобы разделить работу с исходным кодом (макросы) и выполнение произвольного кода (eval). В fexpr'ах eval и так явно вызывается.

Если хочется «всё в одном», то никто не мешает сделать

(defmacro define-fexpr (name params &body body)
  `(defmacro ,name ,params
      `(funcall (lambda ,',params ,',@body) 
         ,@(mapcar (lambda (x) (list 'quote x)) 
                   (list ,@params)))))

И далее писать

(define-fexpr my-if (cond do1 do2) 
   (if (eval cond) (eval do1) (eval do2)))

monk ★★★★★
()
Ответ на: комментарий от komputikisto

Вот эти аргументы: выражение, окружение, динамическое окружение, континуация.

Продолжение ничего нового не даёт. В Racket я могу написать

(define (eval2 expr env cont) 
  (define res (eval expr env)
  (if cont (cont res) res))

Чем отличается «окружение» и «динамическое окружение»? Почему их нельзя объединить (как в Racket)?

monk ★★★★★
()
Ответ на: комментарий от monk

Продолжение ничего нового не даёт.

(продолжение (eval выражение))
(eval выражение продолжение)

Я опустил окружения для простоты. В первом случае после вычисления выражения произойдет возврат в континуацию, которая ждет значение первого аргумента. Далее формируется список аргументов, и он передается в продолжение.

Вторая строка работает не так. После вычисления выражения его значение сразу передается в продолжение. Таким образом, первый eval не поддерживает proper tail call, а второй поддерживает.

Чем отличается «окружение» и «динамическое окружение»?

Про dynamic/lexical scope ты же знаешь. И как их комбинируют в Лиспах, думаю, тебе известно.

Почему их нельзя объединить (как в Racket)?

Как в Racket это сделано? Я не знаю, не программировал на нем.

komputikisto
()
Ответ на: комментарий от monk

Рискну предположить, что «окружение» — это всего лишь лксический скоп, а динамичское окружение — окружение, сформированное динамическим связыванием, которого в схеме просто нет.

anonymous
()
Ответ на: комментарий от anonymous

Нет, лол. Ну что за «сам придумал, сам обиделся». let и lambda выполняют связывание в лексическом окружении. Естественно, они не будут создавать динамические переменные.

ilammy ★★★
()
Ответ на: комментарий от ilammy

Согласно этому документу make-parameter лишь эмулирует динамические переменные при помощи dynamic-wind. Очень плохое решение! Уж лучше тогда без динамических переменных жить. Динамические переменные — это то, что реализация языка должна поддерживать изначально (динамическое окружение должно быть параметром взаимной рекурсии apply/eval).

komputikisto
()
Ответ на: комментарий от ilammy

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

anonymous
()
Ответ на: комментарий от anonymous

fluid-let, который, якобы, имитировал динамическое связывание

make-parameter — тоже имитация. Не понимаю я, почему разработчики Scheme так боятся динамических переменных? При этом они не боятся dynamic-wind. Как реализовать последний очень тяжело въехать, а в динамических переменных нет ничего сложного. Мало того, что dynamic-wind — спорная конструкция, так и еще трудно реализуемая. Почитать можно, например, Pitman «UNWIND-PROTECT vs. Continuations».

komputikisto
()
Ответ на: комментарий от komputikisto

Большинство схемок имеют current-input-port, current-output-port, так что у них есть динамические переменные в том или ином виде.

Кроме того, в SRFI приводятся примеры максимально переносимых реализаций описываемого функционала, чтобы их можно было предоставить библиотекой, которая будет работать где угодно. R7RS вон вообще включает в себя этот SRFI. Конкретные реализации вовсе не обязаны сооружать динамические переменные через dynamic-wind.

ilammy ★★★
()
Ответ на: комментарий от anonymous

Вот имитировать разве что. Параметры функций в схемке всегда лексические.

(define *x* (make-parameter 0))

(define (outer *x* inner) (inner))
(define (inner) (*x*))

(display (outer 1 inner))                       ; ==> 0
(display (inner))                               ; ==> 0
(display (parameterize ((*x* 10)) (inner)))     ; ==> 10

ilammy ★★★
()
Ответ на: комментарий от komputikisto

Не понимаю я, почему разработчики Scheme так боятся динамических переменных

потому что такой язык невозможно компилировать эффективно. Схемеры — это компилодрочеры, вот почему. И схема — это не лисп, это алгол.

anonymous
()
Ответ на: комментарий от ilammy

Вот имитировать

Ну где же Вы сымитировали?

(display (outer 1 inner))                       ; ==> 0
единица то все равно не забиндилась, несмотря на костыли звездочки.

anonymous
()
Ответ на: комментарий от anonymous

И схема — это не лисп, это алгол.

Да, есть такое ощущение, что единственное, что схема взяла от классических Лиспов — это скобки. Лисп — это не просто язык программирования, это философия языка и окружения. Нераздельность отладчика и реализации, принципиальное отсутствие категории ошибок. То, что обычно называют ошибкой в Лиспе является просто задействованием альтернативных путей выполнения. В Лиспе нет понятия программы, а есть концепция Лисп системы в которую могут подгружаться отдельные куски кода. Всего этого нет в схеме, а есть довольно примитивный язык программирования с макросами.

komputikisto
()
Ответ на: комментарий от anonymous

Параметры функций в схемке всегда лексические.

Вообще все переменные лексические. Можно сделать parameterize в outer и *x* (внутри inner) будет связываться с аргументом outer.

ilammy ★★★
()
Ответ на: комментарий от komputikisto

Вы так говорите, как будто бы это что-то плохое и в мире катастрофически не хватает лиспов с поддержкой разработки в образе.

ilammy ★★★
()
Ответ на: комментарий от ilammy

Вы так говорите, как будто бы это что-то плохое

Нет, я не против Scheme. Учитывая AI witer, лучше иметь Схему, чем ничего.

мире катастрофически не хватает лиспов с поддержкой разработки в образе

Я не только про образы говорю. В мире катастрофически не хватает Лиспов вообще. Когда-то их было много и было много экспериментов. Сейчас все сводится к CL и Scheme, которые лишь частично отражают открытия золотого века Лиспа.

komputikisto
()
Ответ на: комментарий от anonymous

почему разработчики Scheme так боятся динамических переменных

потому что такой язык невозможно компилировать эффективно.

Разработчики SBCL доказывают обратное. Нет ни одной реализации Scheme, которая работала бы хотя бы со скоростью SBCL.

monk ★★★★★
()
Ответ на: комментарий от anonymous

единица то все равно не забиндилась

Надо

(define (outer x inner)
  (parameterize ((*x* x)) (inner)))
тогда работает

monk ★★★★★
()
Ответ на: комментарий от anonymous

динамичское окружение — окружение, сформированное динамическим связыванием

Так оно является неотъемлемой частью продолжения. Хотя, при большом желании, вытащить в виде значений параметров тоже можно

monk ★★★★★
()
Ответ на: комментарий от komputikisto

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

Именно это не приемлют разработчики Scheme.

В Лиспе нет понятия программы, а есть концепция Лисп системы в которую могут подгружаться отдельные куски кода.

И именно поэтому на Common Lisp нет ни одной программы для конечного пользователя (даже на Haskell есть xmonad и какой-то архиватор, а на Erlang — ejabberd).

В общем, Анализ пользователей Common Lisp и Racket

monk ★★★★★
()
Ответ на: комментарий от monk

Почитал тот твой пост. Согласен со всем, кроме вот этого утверждения:

Поэтому из языка намеренно исключены сложные для понимания конструкции (пользователь не обязательно квалифицированный программист)

Скорее всего ты имел в виду call-with-current-continuatin. Не думаю, что его там нет т.к. она сложна для понимания. И вообще вряд ли составители стандарта CL думали об этом. First-class продолжения плохо совмещаются с другими конструкциями CL, которые считались важными по той причине, что были унаследованы от старых Лиспов. Семантика block/return-from, catch/throw рушится в присутствии first-class продолжений. Конструкция unwind-protect вообще принципиально с ними не совместима. Разработчики CL не могли отказаться от наследия классических Лиспов и, поэтому, не включили в стандарт call-with-current-continuatin. А больше я не знаю конструкций, которых нет в CL, но есть в Scheme. Ну, еще dynamic-wind, который нужен как раз для first-class продолжений. Продолжения — важная концепция и будущий тру-Лисп будет основан на них и не будет в базовый набор специальных операторов включать block/return-from, catch/throw.

komputikisto
()
Ответ на: комментарий от komputikisto

Скорее всего ты имел в виду call-with-current-continuation.

block + return-from = call/cc + return, catch/throw прекрасно живёт в Racket, unwind-protect могло бы запрещать call/cc внутри своего тела (как это есть в cl-cont). Это всё технические решаемые проблемы.

А причина: «Be aware that many view CallWithCurrentContinuation not as a cool feature, but as a fatal flaw. It's like having a nuclear bomb in your garage. Cool, sure, but do you really want one? Specially when the neighbor's kids might drop in? Call-cc is the ultimate minimalism; sure, it replaces goto, block, throw, catch, etc, but not in a controlled way.» http://c2.com/cgi/wiki?CallWithCurrentContinuation

И из-за этого подхода появляются «решения» в виде cl-cont и https://formlis.wordpress.com/2010/08/20/hack-co-routines-in-sbcl-lisp/

И я имел в виду не только call/cc. Ещё есть синтаксические объекты (syntax object), привязки (binding), set-преобразователи (set! transformer), хвостовая оптимизация (tail-call optimization).

Если брать Racket, то стоит упомянуть сторожей (custodian), инспекторов (inspector), эфемероны (ephemeron), юниты (unit).

monk ★★★★★
()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

И я имел в виду не только call/cc.

Давай иметь в виду исторический контекст. Все те фичи, что ты перечислил (кроме proper tail call) на момент разработки стандарта не существовали. CL хорошо отражает state of the art того времени. Scheme тогда имел только две новые фичи - proper tail call и продолжения. Цитата, что ты приводишь, никакого отношения к CL не имеет. Все это печально, что большинство программистов мыслят так, как в цитате, но я не думаю, что точно этими соображениями руководствовались разработчики CL.

block + return-from = call/cc + return

Это оно так сейчас понятно. Но в историческом контексте надо учитывать, что были уступки разработчикам компиляторов, которым трудно совместить это. Из-за соображений компиляции, видимо, все циклы в CL раскрываются в go + tagbody. Последнее один-в-один компилируется если не учитывать продолжения.

komputikisto
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.