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

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

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

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

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

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

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

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

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

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

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

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.

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

«pure language»?

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

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

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

http://en.wikipedia.org/wiki/Academic_genealogy_of_computer_scientists

http://en.wikipedia.org/wiki/Generational_list_of_programming_languages

okay :)

http://en.wikipedia.org/wiki/Fexpr#Mainstream_use_and_deprecation

http://en.wikipedia.org/wiki/Fexpr#Fexprs_since_1980

Суперресёрч прям :)

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

Между тем, актуальные (?) тезисы про эти ваши ф-выражения — 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.

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

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

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

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

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

macro-function

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

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

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

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

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

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

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

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

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

Являются

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Имеет. Для 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). Или давай пример.

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

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

Имеет.

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

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

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

или макрос + eval

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

но если в макрораскрытии будет еще и 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)))

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

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

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

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

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

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

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

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

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

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

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

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

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

сформированное динамическим связыванием, которого в схеме просто нет

4.2, есть make-parameter и parameterize.

Оно вот так работает?

(define (outer x inner) (inner))
(define (inner) x)
(println (outer 1 inner)) ; 1
(println (let (x 10) (inner))) ; 10

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

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

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

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

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

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

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

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

(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

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

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

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

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

(display (outer 1 inner))                       ; ==> 0

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

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

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

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

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

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

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

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

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

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

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

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

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

Надо

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

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

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

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

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

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

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

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

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

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

Скорее всего ты имел в виду 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.

Скорее всего ты имел в виду 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).

И я имел в виду не только 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. Последнее один-в-один компилируется если не учитывать продолжения.

на Common Lisp нет ни одной программы для конечного пользователя

stumpwm, maxima