[sicp] Порядок вычислений.

При аппликативном порядке аргументы функции вычисляются перед тем, как отправить их внутрь функции.
При нормальном порядке аргументы отправляются внутрь функции эээ... целиком. Скажем, в f(1+2,3) выражение 1+2 будет «целиком» передано вовнутрь.
В книжке Филда и Харрисона «Функциональное программирование» более понятно и подробно объяснено

Аналогия с лямбда-исчислением вроде такая:
аппликативный порядок - бета-контракция по самим внутренним редексам
нормальный порядок - бета-контракция по самим внешним редексам

s/самим/caмым/

при нормальном порядке аргументы при аппликации функции не вычисляются, вычисляется сначала функция, ну, т.е. грубо говоря, «самый наружный терм».

при аппликативном порядке вычисления, как следует из названия, вычисление аргументов происходит при аппликации функции, т.е. вычисляются сначала все аргументы, а потом функция применяется к ним, т.е. сначала вычисляются все «внутренние термы».

В Common Lisp разница довольно ясно видна, там у функций - аппликативный порядок вычисления, а у макросов - нормальный.

Да, действительно, думаю так ТС лучше поймёт...

на примера мат. ф-ции: f(x) = x + x

Аппликативный п.в.:
f(1 + 2)
-> f(3)
-> 3+3
-> 6 

Нормальный п.в.:
f(1 + 2)
-> (1+2) + (1+2)
-> 3 + (1+2)
-> 3+3
-> 6

если также построить f(x) = x+x+x будет лучше видно, какое из этих вычислений затратит меньше шагов и на сколько

если также построить f(x) = x+x+x будет лучше видно, какое из этих вычислений затратит меньше шагов и на сколько

только давайте честно, а? во втором случае будет нормальная редукция графов, а не то что на примере

*поперхнулся кофе* Ну нельзя же ТАК передёргивать?

хз, это усложнение и, наверное, далеко не единственное в реальном алгоритме, а то что в примере главная суть алгоритма. или нет?

хз

на этом стоило остановиться. если не разбираешься - зачем пишешь?

или нет?

нет

>В Common Lisp разница довольно ясно видна, там у функций - аппликативный порядок вычисления, а у макросов - нормальный.

хуйня.

>Я не могу понять разницу между аппликативным и нормальным порядком вычисления.

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

(λx. y) ((λx. x x x) (λx. x x x))

на этом стоило остановиться. если не разбираешься - зачем пишешь?

чтобы узнать как правильно

(λx. y) ((λx. x x x) (λx. x x x))

а в чём суть то?

чтобы узнать как правильно

во-первых, как уже отметили выше, нормальный порядок редукции всегда приведёт к нормальной форме (в отличие от аппликативного); во-вторых, редукция графов никогда не требует больше шагов вычислений, чем аппликативный порядок. а, собственно, реализация ленивых вычислений всегда предполагает outermost graph reduction

а в чём суть то?

суть в том, что

лучше видно, какое из этих вычислений затратит меньше шагов и на сколько

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

ага, понятно, спасибо, вот только не очень понял что есть нормальная форма? и

тут оверхед на санки

на что?

что есть нормальная форма?

A normal form is an equivalent expression which cannot be reduced any further

конец вычислений, иными словами

>тут оверхед на санки

на что?

http://en.wikipedia.org/wiki/Thunk#Thunk_as_delayed_computation

В каком месте?
Ты, вообще, в курсе что такое макросы и как раскрываются?

>В каком месте?

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

В какое время они работают - не имеет значения, это вообще параллельно. Можно, в принципе, считать, что в macroexpansion time cl превращается в такой отдельный язык программирования, со своими правилами вычисления.

Редукция в макросах происходит от внешних термов к внутренним, это и есть главный признак нормального порядка вычислений. Насчет «не вычисляют» - так, собственно, normal order это разновидность non-strict вычислений, все так и есть, аргументы могут вообще не вычислиться.

Ну, т.е. конкретнее.

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

(defmacro m-plus (a b)
  (list (quote +) a b))

(defun f-plus (a b)
  (+ a b))

(plus (plus 1 2) (plus 3 4))

(f-plus (f-plus 1 2) (f-plus 3 4))

(f-plus 3 7)

10

С макросами дело совсем по-другому:

(m-plus (m-plus 1 2) (m-plus 3 4))

(+ (m-plus 1 2) (m-plus 3 4))

(+ (+ 1 2) (+ 3 4))

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

При чем тут цитирование, и, тем более, отсутствие рекурсии? Перечитай пост.

При чем тут цитирование

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

отсутствие рекурсии

нет самих вычислений.

p.s. пример с цитированием:

(defmacro fail (a x (b y (c z1 z2)))
           `(,c ,z2 (,b ,z1 (,a ,x ,y))))


(macroexpand-1 '(fail m-plus 1 (m-plus 2 (m-plus 3 4))))

(M-PLUS 4 (M-PLUS 3 (M-PLUS 2 1)))


(macroexpand-1 '(fail f1 1 (f2 2 (f3 3 4))))

(F3 4 (F2 3 (F1 2 1)))



(defmacro fail2 (a b c d)
           `(,d ,c ,b ,a))

(macroexpand-1 '(fail2 1 2 3 +))

(+ 3 2 1)



(defmacro fail3 (a b c d)
           `(,d ,a ,c ,a ,b ,a))

(macroexpand-1 '(fail3 1 2 3 +))

(+ 1 3 1 2 1)


(defmacro epic-fail (a x (b y (c z1 z2)))
           `(,a ,z2 (,a ,z1 (,a ,y ,x))))

с его помощью легко менять порядок и число вычислений аргументов и даже раскрытия форм.

Ты совсем дурак?
Перечитай мой пост, потом перечитай где-нибудь определение «normal order of evaluation» - в SICP, в википедии или на c2.com, к примеру.

> в SICP,

это же задумывалась для первого знакомства с программированием школьникам/первокурсникам. там многие сложные вопросы очень такчино обходят.

перечитай где-нибудь определение «normal order of evaluation»

ты бы для сначала определение evaluation осилил.

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

где ты видел цитирование в лямбда исчислении? что будет с (defmacro x () (x))?