Вопрос по компиляции

Term rewriting никакого отношения ни к компайл-тайму, ни к фп, ни к скоупам не имеет.

как бы, объяснение процесса, что, якобы ф-ция «ищет» значения свободных переменных в локальном скопе, когда вызывается

Это «как бы объяснение» называется семантикой языка. Оно не имеет никакого отношения к компеляторам-шмопеляторам.

И вообще,

(let ((a (list '1)))
  (lambda (b)
    (append (cons 'x a) (cons 'y a)) ) )

А если нет компилятора?

Ну ты понел. Тут должны быть не чистые функции, а (set-cdr! a (cons 'x a)) и прочие безобразия.

Все-таки имеет, в том смысле, что такая семантика обеспечивает «ссылочную прозрачность» для компилятора/оптимизатора. Только вот само понятие «переменная» тут извращается. Что это за переменная, значение которой заведомо известно. Как то глуповато это выглядит, особенно, в простых случаях. Когда куча кода, это как-то нивелируется, а в простых, наглядно отсвечивает идиотизмом: «определи переменную и сразу запрети менять ее значение». Тут же возникает вопрос, а нахрен она тогда нужна.

А если нет компилятора?

А если нет компилятора, фп вообще не нужно.

В выражении «f(x) = x² + 3x – 42» икс тоже вроде как нельзя менять, но ты же об этом не ноешь. Переменная в том смысле, что внутри функции её значение не связано с какой-либо конкретной величиной, а может принимать произвольное значение.

В ФП нет понятия «переменная». Есть понятие «связь», «binding».

В выражении «f(x) = x² + 3x – 42

Я про свободные переменные. В Вашем выражении никаких вопросов не возникает, x тут меняется при каждом вызове, его значение (в теле) - это параметр при вызове.

а может принимать произвольное значение

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

В ФП нет понятия «переменная». Есть понятие «связь», «binding».

Это все словоблудие. Нет понятия переменная, зато есть понятия связанная и свободная переменная. Феерично.

Не нравится - не ешь.

Зависит от языка. В некоторых замыкание всегда схватывается по значению (haskell, f#), в других - всегда по ссылке (common lisp, c#), а бывает, когда этим можно управлять (scala, c++).

В некоторых замыкание всегда схватывается по значению (haskell, f#), в других - всегда по ссылке (common lisp, c#)

А разве не наоборот? Если понимать «схватывание по значению» энергичные вычисления? Или как правильно понять?

Ну ты понел. Тут должны быть не чистые функции, а (set-cdr! a (cons 'x a)) и прочие безобразия.

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

И? let — это макрос:

((lambda (a)
   (lambda (b)
     (+ a b) ) )
 1 )

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

(let ((a (list '1)))
  (lambda (b)
    (append (cons 'x a) (cons 'y a)) ) )

(lambda(b)'('x 1 'y 1))

Компилятор, естественно, не будет

SBCL:

(lambda (b) (+ 1 b))
; #<FUNCTION (LAMBDA (B)) {100490C6CB}>

(let ((a 1)) (lambda (b) (+ a b)))
; #<FUNCTION (LAMBDA (B)) {10048C808B}>

(let ((a (f))) (lambda (b) (+ a b)))
; #<CLOSURE (LAMBDA (B)) {10048F2C8B}>

(declaim (inline f))

(let ((a (f))) (lambda (b) (+ a b)))
; #<FUNCTION (LAMBDA (B)) {100499C4FB}>

CCL:

(lambda (b) (+ 1 b))
; #<Anonymous Function #x3020006E87EF>

(let ((a 1)) (lambda (b) (+ a b)))
; #<COMPILED-LEXICAL-CLOSURE #x3020006E15EF>

(let ((a (f))) (lambda (b) (+ a b)))
; #<COMPILED-LEXICAL-CLOSURE #x30200071696F>

(declaim (inline f))

(let ((a (f))) (lambda (b) (+ a b)))
; #<COMPILED-LEXICAL-CLOSURE #x30200070ABEF>

(всё с максимальными оптимизациями).

Капитан: Есть разница между

(define x 0)
(let ((a (begin (set! x (+ x 1)) 1)))
  (lambda (b)
    (+ a b a) ) )

(define x 0)
(lambda (b)
  (+ (begin (set! x (+ x 1)) 1)
     b
     (begin (set! x (+ x 1)) 1) ) )

И вообще, лексическая область видимости это противопоставление динамической.

(define foo
  (let ((a 1))
    (lambda (b)
      (+ a b) ) ) )

; лексическая область видимости:
(let ((a 2))
  (foo 5) ) ; ===> (+ 1 5)

; динамическая область видимости:
(let ((a 2))
  (foo 5) ) ; ===> (+ 2 5)

Значение a в (+ a b) меняется при каждом вызове внешней функции.

Значение a не меняется. Как можно говорить, что оно меняется, если оно всегда гарантированно вычисляется в одно и то же? Это просто пятое колесо.

Естественно, компилятор не может быть уверен, что (f) не использует грязные переменные. А вот в чистом языке, мне кажется, он сможет редуцировать подобное выражение.

И вообще, лексическая область видимости это противопоставление динамической.

Все верно, и, если в динамической у свободных переменных есть вполне конкретный смысл — они выдергивают свои значения из контекста, то в лексической смысла практически нет, это все равно, что сказать (+ x 1), где x=2, проще сразу написать (+ 2 1), или, чего уж там мелочиться, 3.

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

SBCL там встраивает (f), если попросить inline. А вот CCL не делает даже того о чём ты говоришь в ОП — (lambda (b) (+ 1 b)) это анонимная функция, (let ((a 1)) (lambda (b) (+ a b))) — лексическое замыкание, т.е. функция + данные, отсылки к «a» в коде lambda превращаются в ссылки (чтение которых = «поиск» «а») в коде функции на внешние данные (которые замкнуты, там лежит значение «а»).

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

В Haskell семантически нет разницы, по значению ты схавал или по ссылке. А твоё утверждение о нем неверно.

Это смысл для компилятора, который анализирует код, но не для пишущего программы. Представьте себе, что Вы говорите: «2-го числа будет дождь». Я Вас прошу записать это выражение по-другому «X-го числа будет дождь» и тут же уточнить, что X=2. Вы это пишете, и теперь я легко могу проанализировать Ваш код: установить что Вы имели в виду под «X-го числа будет дождь» «2-го числа будет дождь». Очевидно, что это извращение тут не нужно, но зато я, компилятор, становлюсь на этом фоне о-о-очень нужной персоной, ибо никто не знает, что-такое X, кроме меня.

зануда

В Haskell семантически нет разницы, по значению ты схавал или по ссылке. А твоё утверждение о нем неверно.

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

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

В первом примере, мы могли бы безо всяких замыканий написать вместо a 1, от этого ни хрена не изменится, правильно?

Неправильно.

В общем случае мы имеем не

(let ((a 1)) ...)

(let ((a <expression>)) ...)

Но a на <expression> мы в любом случае можем заменить. А это не снижает градус идиотизма при использовании переменных.

в любом случае можем заменить

Не в любом.

<expression> := (begin (display "I am not pure") 1)

Но a на <expression> мы в любом случае можем заменить.

Нет, потому что тогда <expression> будет вычислен столько раз, сколько будет использован.

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

Да, я имел в виду ситуацию, когда <expression> чистая.

Частный случай не влияет на подход к общему. В общем случае скоп создается.

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

Не, я сейчас говорю о чистом ФП

Видимо поэтому на примере схемы. Подучись грамотно задавать вопросы.

Я синтаксис хаскеля не знаю. Какое это имеет значение, в контексте вопроса?

ФП-адепт: локальный скоп, свободные переменные, подстановки в compile time, лексический скоп, замыкания, term rewriting, семантика языка, чистые функции, ссылочная прозрачность, связанные переменные, энергичные вычисления, ленивые вычисления, контекст макроса, динамическая область видимости, грязные переменные, бета-редукция, монады, лямбды, лямбды, лямбды...
Программист: (пишет код)

контекст макроса, динамическая область видимости,

Не, это не отсюда, по крайней мере, не из современной трактовки ФП:)

Как ты можешь говорить о чистом ФП и при этом не зная ни одного ФЯ, м? Очень странно, очень

http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects#Funct...

http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/GeneratedCode

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729

ghc -O<n> -S <file>.hs; cat <file>.s | grep closure | wc -l (static closures).

http://community.haskell.org/~simonmar/papers/eval-apply.pdf

Что-нибудь вроде

loop ... a ... = go ... where
  go ... n ... = ... a, n, go (...) ...

в итоге на каждое использование (loop ...) будет генерировать (статично) вариант Module_zdwgo<n>_closure.

А вот в чистом языке, мне кажется, он сможет редуцировать подобное выражение.

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

А вот в чистом языке, мне кажется, он сможет редуцировать подобное выражение.

Внимание! Бесконечная рекурсия без выхода тоже чистая, но редуцировать её в компил-тайме не стоит. Прежде чем что-то редуцировать в компил-тайме было бы неплохо вспомнить о том что произвольное вычисление может и не завершиться.

Да ты упоротый!

Правила lexical scoping определяются \beta-редукцией. Тупо. Чего тебе еще надо? Любая компиляция, любой constant folding и lambda lifting это тупо оптимизация этого процесса.

Нет, ты не упоротый, я ошибся. Ты ебанутый.

Слышь, ебанутый, прочитало бы ты для начала хотя бы http://en.wikipedia.org/wiki/Lambda_calculus#Beta_reduction

Зачем что-то читать и разбирать? Главное вбросить же Концептуальная дыра ФП.