Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Реализация рекурсивной функции при нынешней архитектуре есть неявный цикл на стеке.

GN>А какая разница, как это реализуется, неужели от этого поменяется суть Впрочем, посмотрим, как...

GN>Не знаю, что понимается под нынешней архитектурой... на примере x86

GN>

GN>    mov eax, 5
GN>@@: nop     ;
GN>    dec eax ; тело цикла
GN>    jnz @b  ;
GN>

GN>В ассемблере нет функций или процедур, есть подпрограммы — участки кода, предназначенные для многократного вызова. В примере выше такой подпрограммой является команды обозначенные анонимной меткой @@. Вызывавется она (то есть, её адрес загружается в указатель инструкций IP) командой условного перехода jnz. Выход из подпрограммы осуществляется этой же командой, естественным инкрементом IP. Это возможно, поскольку подпрограмма вызывается только из одного места (поэтому же нет нужды использовать для вызова call, сохраняя в стеке адрес возврата).

Я бы все-таки предпочел не играть с терминологией. Для асма x86 подпрограмма — это все же то, что заканчивается командой ret (или iret — для подпрограммы обработки прерывания). То, что ты написал, можно , конечно, при желании назвать подпрограммой... В философском плане оно верно, а в руководстве по асму будет не кошерно.

GN>Цикл — это просто короткое название вышеописанного рекурсивного вызова, один из частных случаев. Термин придумали, что бы проще понять рекурсию (т.к. для этого можно не понимать рекурсию).

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

GN>Параметры в подпрограмму могут передаваться например так:
<skipped>

На ассемблере делать можно как угодно и что угодно. Можно, например, вызвать подпрограмму с помощью команды ret , надеюсь, тебе этот способ известен. Можно выйти из нее без ret. Можно параметры передать твоим способом или вообще как-то еще. Но все это не более чем упражнения, может, и любопытные в плане обучения хакерству, но не имеющие отношения к реальному программированию, где параметры надо передавать в соответствии с calling convention, иначе получите все, что вам причитается


GN>В последнем случает стек и для сохранения адреса возврата не используется. Да и что такое стек, адресуемая регистром общего назначения esp память? А почему именно esp, только потому, что в CISC x86 есть удобные команды для этого?

Именно. Потому что команды push и pop работают с esp, а с другими регистрами не работают.

>Вот в самом первом примере стек значений от 5 до 0 реализован всего на одном регистре eax без посторонней памяти.

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

А он уже должен быть "встроен" в свойства

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Я бы все-таки предпочел не играть с терминологией. Для асма x86 подпрограмма — это все же то, что заканчивается командой ret (или iret — для подпрограммы обработки прерывания).

Осторожнее. Если двигаться в этом направлении, то можно показать, что inline фнукции в С вовсе не функции

В принципе, при чём здесь x86? Я выбрал его, т.к. это наиболее известный из ассемблеров, соответсвенно большее количество людей смогут понять код. В других архитектурах команды ret может не быть вовсе. Не вижу причин обобщать этот частный случай.

PD> То, что ты написал, можно , конечно, при желании назвать подпрограммой... В философском плане оно верно, а в руководстве по асму будет не кошерно.

Я бы сказал, что такое кошерное руководство будет учить не асму, а С с нетрадиционным синтаксисом.

PD>Формально с этим аргументом можно согласиться. Я бы так сказал — в теории цикл сводится к рекурсии. Но это формально, а в реальности... команду LOOP придумали тоже, чтобы лучше понять рекурсию ?

LOOPcc придумана с единственной целью: получить более компактный бинарный код. Подобно ret, call и т.п. CISC командам.

PD>На ассемблере делать можно как угодно и что угодно. Можно, например, вызвать подпрограмму с помощью команды ret , надеюсь, тебе этот способ известен. Можно выйти из нее без ret. Можно параметры передать твоим способом или вообще как-то еще. Но все это не более чем упражнения, может, и любопытные в плане обучения хакерству, но не имеющие отношения к реальному программированию, где параметры надо передавать в соответствии с calling convention, иначе получите все, что вам причитается

Если бы я начинал с x86, вероятно, думал бы так же. Однако я видел приличное количество "коробочного" софта изнутри, где использовались именно такие "экзотические" способы передачи данных. Тяжело на том же Z80 передавать параметры через стек, а регистров мало.

PD>Потому что команды push и pop работают с esp, а с другими регистрами не работают.

Иными словами, ничего не мешает использовать другие регистры, если отказаться от call\ret. Разве что, получим больший по объёму машкод, приблизившись к RISC.

PD>Твои примеры любопытны, но , мягко выражаясь, надуманны, и к реальному коду имеют весьма косвенное отношение. Даже если этот код не сгенерирован компилятором, а написан вручную на асме.

Похожий код может произвести, например, транслятор forth. Примеры приводились с единственной целью — показать, что в ассеблере нет каких-то определённых рамок, кроме тех, что мы сами себе навязываем (определение цикла, в данном случае).

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

GN>Осторожнее. Если двигаться в этом направлении, то можно показать, что inline фнукции в С вовсе не функции

Совершенно верно. Они являются функциями языка С/C++, но не подпрограммами в машинном коде.

GN>В принципе, при чём здесь x86? Я выбрал его, т.к. это наиболее известный из ассемблеров, соответсвенно большее количество людей смогут понять код. В других архитектурах команды ret может не быть вовсе. Не вижу причин обобщать этот частный случай.

Ну так мы далеко уйдем. Если нет ret, то, наверное, нет и call, так ? Или они есть, но иначе. Если уж на то пошло, то в архитектуре IBM-360/370 не было аппаратного стека, и мое утверждение насчет рекурсии как цикла на стеке там явно неприменимо. В общем, обсуждать все платоформы на свете я не буду. А ret все же существует. Как и call . Пусть только на x86/x64

PD>> То, что ты написал, можно , конечно, при желании назвать подпрограммой... В философском плане оно верно, а в руководстве по асму будет не кошерно.

GN>Я бы сказал, что такое кошерное руководство будет учить не асму, а С с нетрадиционным синтаксисом.

Руководство, которое можно бы написать по твоим советам насчет асма, будет не руководством по асму, а руководством по трюкам на асме. Не обижайся.


PD>>Формально с этим аргументом можно согласиться. Я бы так сказал — в теории цикл сводится к рекурсии. Но это формально, а в реальности... команду LOOP придумали тоже, чтобы лучше понять рекурсию ?

GN>LOOPcc придумана с единственной целью: получить более компактный бинарный код.

По сравнению с чем ? jne и т.п ? Да. Но дело-то не в этом, а в том, что машинные команды включают в себя специальную команду цикла. Как понятие он есть. И не абстрактный цикл, а именно цикл с инкрементом или декрементом. В конце концов я вполне могу обойтись без цикла и в С++ с презренным goto, но есть же в языке цикл!

>Подобно ret, call и т.п. CISC командам.

ret и call вообще из иной оперы, не смешивай. И уж loop делалась отнюдь не из философский идей насчет CISC и RISC. Не забывай — этой команде и этой архитектуре скоро 30 лет будет

GN>Если бы я начинал с x86, вероятно, думал бы так же. Однако я видел приличное количество "коробочного" софта изнутри, где использовались именно такие "экзотические" способы передачи данных. Тяжело на том же Z80 передавать параметры через стек, а регистров мало.

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

mov, eax,0

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

Но это все трюки. Хорошие или нет — можно обсуждать. А традиционное программирование все же к трюкам относится не очень хорошо.

PD>>Потому что команды push и pop работают с esp, а с другими регистрами не работают.

GN>Иными словами, ничего не мешает использовать другие регистры, если отказаться от call\ret. Разве что, получим больший по объёму машкод, приблизившись к RISC.

Может, и да, правда, приблизившись на 1 мм, не более . Отказаться от call/ret можно, можно отказаться от многих команд, например, от всего, что появилось в 386 и позже , например, сканирование битов и т.д. — писали же такое раньше без этих команд! Можно в С++ отказаться от цикла for, неужели while на мне хватит ? Можно переделать архитектуру, обеспечив полную ортогональность регистров. Можно просто на Итаниум перейти. Но пока мы в рамках x86/64, давай будем исходить из того, что там есть.

PD>>Твои примеры любопытны, но , мягко выражаясь, надуманны, и к реальному коду имеют весьма косвенное отношение. Даже если этот код не сгенерирован компилятором, а написан вручную на асме.

GN>Похожий код может произвести, например, транслятор forth. Примеры приводились с единственной целью — показать, что в ассеблере нет каких-то определённых рамок, кроме тех, что мы сами себе навязываем (определение цикла, в данном случае).

Вполне согласен. Я же и писал — на нем можно все. Но при одном условии — проект и будет целиком на асме. Как только здесь примет участие C++ или Delphi — извольте соблюдать calling convention. Если с Фортом будешь сопрягать — извольте его правила соблюдать, я их не знаю, но они обязательно есть.

Здравствуйте, AndrewVK, Вы писали:

VD>>На мой взгляд было бы интересно обсудить какие просчеты были сделаны в виртуальных машинах и языках.

AVK>Ну вот из свеженького — в FW 4.0, в mscorlib добавлены интерфейсы IObservable/IObserver,

А можешь показать, когда и конкретно куда добавлены Я как-то ни рефлектором в сборке mscorlib (от десятки, 10.0.20506.1 Beta1) найти не могу, ни в МСДН.

AVK>что, на мой взгляд, является фактически признанием ошибочности внесения в CLR событий. Осталось слегка подрихтовать C#/VB, чтобы можно было использовать оператор += и синтаксис VB, и события станут полностью бесполезными . А там можно заодно и делегаты приговорить.

+1

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну так мы далеко уйдем. Если нет ret, то, наверное, нет и call, так ? Или они есть, но иначе. Если уж на то пошло, то в архитектуре IBM-360/370 не было аппаратного стека, и мое утверждение насчет рекурсии как цикла на стеке там явно неприменимо.

Интересно получается — в одном случае утверждение верно, в другом нет. В то же время, моя интерпретация подходит во всех случаях

PD>Руководство, которое можно бы написать по твоим советам насчет асма, будет не руководством по асму, а руководством по трюкам на асме. Не обижайся.

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

Кстати, вот такой пример на тему циклов (я употребляю это слово, т.к. оно короче, но подразумеваю описанное ранее)

Есть 32 бита в регистре (не конь в вуккуме, а, например, маска пикселей) нужно их как-то обработать по-одному. Как будет решаться задача императивно, циклом? В лоб:

    mov eax, [pixels]  
    mov ecx, 32  
@@: shr eax, 1  ; копируем очередной бит в Carry Flag
    ;
    ; тут что-то делаем с битом
    ;
    dec ecx  ; итерируем цикл
    jnz @b

Если немного подумать, то на ассемблере это делается так:

    mov eax, [pixels]
    stc    ; используем Carry Flag как "маркер" конца битовой последовательности.
@@: rcr eax, 1 ; копируем очередной бит в Carry Flag. за счёт цикличности сдвига, меркер перейдёт в младший бит на первом проходе.
    ;
    ; тут что-то делаем с битом
    ;
    or  eax, eax  ; проверяем, остался ли бит маркера.
    jnz @b

Счётчик цикла убран за не надобностью тратить лишний регистр. Как бы так "императивно" объяснить вышепроисходящее, без упоминаний о битах? С другой стороны, можно сказать что здесь рекурсивный вызов, где параметром передаётся "остаток" последовательности.

GN>>LOOPcc придумана с единственной целью: получить более компактный бинарный код.

PD>По сравнению с чем ? jne и т.п ? Да. Но дело-то не в этом, а в том, что машинные команды включают в себя специальную команду цикла.

В этом именно и дело. Отдельный опкод — для экономии памяти. Отдельное определение для частного случая рекурсии — для кратости изложения.

Здравствуйте, _FRED_, Вы писали:

_FR>А можешь показать, когда

Нет

_FR> и конкретно куда

mscorlib, System namespace

_FR> добавлены Я как-то ни рефлектором в сборке mscorlib (от десятки, 10.0.20506.1 Beta1) найти не могу, ни в МСДН.

Скоро будет beta 2.

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Ну так мы далеко уйдем. Если нет ret, то, наверное, нет и call, так ? Или они есть, но иначе. Если уж на то пошло, то в архитектуре IBM-360/370 не было аппаратного стека, и мое утверждение насчет рекурсии как цикла на стеке там явно неприменимо.

GN>Интересно получается — в одном случае утверждение верно, в другом нет. В то же время, моя интерпретация подходит во всех случаях

Подумал еще раз.

Вообще-то, коль скоро речь идет о дефинициях, то их можно создавать как кому угодно. Ты — свои, я свои. Так что если хочешь определять подпрограмму как некий произвольный код, я тебе в этом воспрепятствовать не могу . Что же касается меня, то я считаю, что подпрограмма тем и отличается от всякого другого кода, что a)может быть вызвана из нескольких мест (и вообще говоря, любых мест) и b) как следствие из этого, не хранит в себе явно адрес возврата в вызывающий код. Этот адрес передается ей каким-то иным способом, вследствие чего он может быть различным. Не обязательно через стек, может, через регистры (с сохранением их для рекурсии) или еще как-то. Но тот факт, что ее можно вызвать не из одного места и что она сама не знает адреса возврата — ИМХО обязателен. Еще раз — все это игры в дефиниции, так что ты впроаве завести понятие подпрограммы, не удовлетоворяющее этим правилам. Если ты это сделаешь — мы будем иметь 2 вида подпрограмм

PD>>Руководство, которое можно бы написать по твоим советам насчет асма, будет не руководством по асму, а руководством по трюкам на асме. Не обижайся.

GN>Не дождётесь И вот почему смешно: в ассемблере континуации — "трюк", а в других языках — "мегафича".

Не понял. Можно пример ?

GN>Кстати, вот такой пример на тему циклов (я употребляю это слово, т.к. оно короче, но подразумеваю описанное ранее)

GN>Есть 32 бита в регистре (не конь в вуккуме, а, например, маска пикселей) нужно их как-то обработать по-одному. Как будет решаться задача императивно, циклом? В лоб:
GN>

GN>    mov eax, [pixels]  
GN>    mov ecx, 32  
GN>@@: shr eax, 1  ; копируем очередной бит в Carry Flag
GN>    ;
GN>    ; тут что-то делаем с битом
GN>    ;
GN>    dec ecx  ; итерируем цикл
GN>    jnz @b
GN>

GN>Если немного подумать, то на ассемблере это делается так:
GN>

GN>    mov eax, [pixels]
GN>    stc    ; используем Carry Flag как "маркер" конца битовой последовательности.
GN>@@: rcr eax, 1 ; копируем очередной бит в Carry Flag. за счёт цикличности сдвига, меркер перейдёт в младший бит на первом проходе.
GN>    ;
GN>    ; тут что-то делаем с битом
GN>    ;
GN>    or  eax, eax  ; проверяем, остался ли бит маркера.
GN>    jnz @b
GN>

Счётчик цикла убран за не надобностью тратить лишний регистр.

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

>Как бы так "императивно" объяснить вышепроисходящее, без упоминаний о битах? С другой стороны, можно сказать что здесь рекурсивный вызов, где параметром передаётся "остаток" последовательности.

Да, конечно, при желании можно все свести или псевдосвести к рекурсии. Например, длину ASCIIZ строки можно вычислить рекурсивно. Примерно так

int len(char*p)
{
if(!*p)
return 0;
else return len(p+1) + 1;
}

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Да, конечно, при желании можно все свести или псевдосвести к рекурсии. Например, длину ASCIIZ строки можно вычислить рекурсивно. Примерно так

PD>int len(char*p)
PD>{
PD>if(!*p)
PD> return 0;
PD>else return len(p+1) + 1;
PD>}

PD>Но я все же ни писать такое, ни учить студентов писать такое не буду, а если они такое напишут — устрою им выволочку. Ибо нечего ерундой заниматься.
Конечно, такая рекурсия не является хвостовой и может вызвать переполнение стека даже там где есть оптимизация хвостовой рекурсии.

Здравствуйте, gandjustas, Вы писали:


PD>>Да, конечно, при желании можно все свести или псевдосвести к рекурсии. Например, длину ASCIIZ строки можно вычислить рекурсивно. Примерно так

PD>>int len(char*p)
PD>>{
PD>>if(!*p)
PD>> return 0;
PD>>else return len(p+1) + 1;
PD>>}

PD>>Но я все же ни писать такое, ни учить студентов писать такое не буду, а если они такое напишут — устрою им выволочку. Ибо нечего ерундой заниматься.
G>Конечно, такая рекурсия не является хвостовой и может вызвать переполнение стека даже там где есть оптимизация хвостовой рекурсии.

Это-то как раз меня не столь уж и волнует. Переполнение стека в С++ устроить очень несложно, но с этим как-нибудь справимся. Дело не в этом, а в том, что рекурсивное решение здесь просто ни к чему. Оно здесь за уши притянуто.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, gandjustas, Вы писали:


PD>>>Да, конечно, при желании можно все свести или псевдосвести к рекурсии. Например, длину ASCIIZ строки можно вычислить рекурсивно. Примерно так

PD>>>int len(char*p)
PD>>>{
PD>>>if(!*p)
PD>>> return 0;
PD>>>else return len(p+1) + 1;
PD>>>}

PD>>>Но я все же ни писать такое, ни учить студентов писать такое не буду, а если они такое напишут — устрою им выволочку. Ибо нечего ерундой заниматься.
G>>Конечно, такая рекурсия не является хвостовой и может вызвать переполнение стека даже там где есть оптимизация хвостовой рекурсии.

PD>Это-то как раз меня не столь уж и волнует. Переполнение стека в С++ устроить очень несложно, но с этим как-нибудь справимся. Дело не в этом, а в том, что рекурсивное решение здесь просто ни к чему. Оно здесь за уши притянуто.

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

Вот как-то так

int len(char *p)
{
  return *p?(len(p+1) + 1):0;
}

Здравствуйте, gandjustas, Вы писали:

G>Ничего не притянуто. Рекурсивное решение требует меньше знания языка, чем решение с циклом

Это не аргумент.


>кроме того обладает семантикой выражения, что лучше понимается математиками


Это тоже. Какое мне дело, как они понимают, лучше или хуже.

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

И этот аргумент сомнителен.

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, gandjustas, Вы писали:

G>>Ничего не притянуто. Рекурсивное решение требует меньше знания языка, чем решение с циклом
PD>Это не аргумент.
Если вопрос касается обучения, то очень даже аргумент. В том же SICP в одном семестре умещается полезных знаний програмимрования гораздо больше, чем в среднестатистическом курсе на с\паскаль.


>>кроме того обладает семантикой выражения, что лучше понимается математиками
PD>Это тоже. Какое мне дело, как они понимают, лучше или хуже.
Ну да, читаемость программ — совершенно неважное свойство.

>> И самое главное не содержит изменяемых значений, поэтому очень сложно написать неправльно в таком виде.
PD>И этот аргумент сомнителен.
Да ты че? Корректные программы писать уже не надо?

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

PD>...потому что если цикл может быть реализован по регистру, рекурсия (если ее реализовать как положено) — это работа со стеком, то есть с памятью.
Если рекурсию реализовать как положено, то она тоже прекратится в цикл в машинных кодах. Только не все компиляторы так умеют.

Здравствуйте, Pavel Dvorkin, Вы писали:


PD>А вот эффективность его ниже, потому что если цикл может быть реализован по регистру, рекурсия (если ее реализовать как положено) — это работа со стеком, то есть с памятью.

Правильная хвостовая рекурсия современными C++ компиляторами компилируется не менее эффективно чем цикл:

int len(char *p, size_t l = 0)
{
if(!*p)
    return l;
    
return len(p + 1, l + 1);
}

?len@@YAHPADI@Z PROC                    ; len
; _p$ = ecx
; _l$ = eax

; 5    : if(!*p)

    cmp    BYTE PTR [ecx], 0
    je    SHORT $LN7@len
$LL4@len:

; 6    :     return l;
; 7    :     
; 8    : return len(p + 1, l + 1);

    inc    ecx
    inc    eax
    cmp    BYTE PTR [ecx], 0
    jne    SHORT $LL4@len
$LN7@len:

; 9    : }

    ret    0
?len@@YAHPADI@Z ENDP                    ; len

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Здравствуйте, gandjustas, Вы писали:

G>>>Ничего не притянуто. Рекурсивное решение требует меньше знания языка, чем решение с циклом
PD>>Это не аргумент.
G>Если вопрос касается обучения, то очень даже аргумент. В том же SICP в одном семестре умещается полезных знаний програмимрования гораздо больше, чем в среднестатистическом курсе на с\паскаль.

До сих пор никаких проблем с обучением не было. Рекурсия была, роль ее подчиненная. Не надо на ровном месте проблемы создавать.


>>>кроме того обладает семантикой выражения, что лучше понимается математиками
PD>>Это тоже. Какое мне дело, как они понимают, лучше или хуже.
G>Ну да, читаемость программ — совершенно неважное свойство.

Опять не надо так. Во-первых, эффективность важнее, по крайней мере для меня. Во-вторых, что такого нечитаемого и непонятного в обычном цикле ты нашел. Если он не понятен — тому, кто его читает надо профессию сменить, потому что он должен быть понятен после 2 месяцев обучения. Раз и навсегда.

>>> И самое главное не содержит изменяемых значений, поэтому очень сложно написать неправльно в таком виде.
PD>>И этот аргумент сомнителен.
G>Да ты че? Корректные программы писать уже не надо?

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

PD>>А вот эффективность его ниже
G>А вот это действительно сомнительный агрумент, так как очевидно пример с таким вычислением длины строки к реально жизни отношения не имеет.

Безусловно. Я его и привел как пример искусственный.

>Во многих случаях длина строки хранится вместе со строкой

Только при этом ее посчитали. Впрочем, мне дискуссии на эту тему уже очень надоели.



PD>>...потому что если цикл может быть реализован по регистру, рекурсия (если ее реализовать как положено) — это работа со стеком, то есть с памятью.
G>Если рекурсию реализовать как положено, то она тоже прекратится в цикл в машинных кодах. Только не все компиляторы так умеют.

Точнее сказать, никто не умеет. Потому что по calling convention, которые надо соблюдать, можно, конечно, аргументы передавать и через регистры, если их хватит, а вот адрес возврата всегда заносится в стек. По крайней мере в x86.

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Pavel Dvorkin, Вы писали:


PD>>А вот эффективность его ниже, потому что если цикл может быть реализован по регистру, рекурсия (если ее реализовать как положено) — это работа со стеком, то есть с памятью.

FR>Правильная хвостовая рекурсия современными C++ компиляторами компилируется не менее эффективно чем цикл:

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Да, впечатляет. Но ты пошел на искусственный прием — добавил новый аргумент к функции, которой он совсем не нужен. И не надо ссылаться на то, что у него есть дефолтное значение — это функция языка С вообще-то, а не С++. Все равно игра не стоит свеч. И во имя рекурсии портить сигнатуры функций я не готов.

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

Здравствуйте, FR, Вы писали:

FR>Не порти, для этого есть и перегрузка (для C++) и просто вспомогательная функция с другим названием (для си).

То есть на С придется еще одну функцию завести ? А из программы какую вызывать — рекурсивную или вспомогательную ? Вспомогательная ведь нерекурсивная.

FR>Да я и не призываю тебя писать в этом стиле просто показываю что эффективность уже не проблема.

Я согласен с тем, что ты показал возможность реализации рекурсии без стека. Если быть точнее, то компилятор реализовал рекурсивную функцию С++ без рекурсивной подпрограммы в машинных кодах. Но заплатил ты за это ИМХО слишком дорого. А в реальной ситуации мне либо придется портить таким образом сигнатуры и тем самым вносить массу непонятности в код (исходники мало кто смотрит, а внешний интерфейс должен быть ясен и логичен), либо оставить сигнатуры как есть, но тогда компилятор реализует рекурсивный вызов в кодах. И то и другое вряд ли хорошо. Игра не стои свеч.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>То есть на С придется еще одну функцию завести ? А из программы какую вызывать — рекурсивную или вспомогательную ? Вспомогательная ведь нерекурсивная.

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

static int len_r(char *p, size_t l)
{
if(!*p)
    return l;
    
return len_r(p + 1, l + 1);
}

int len(char *p)
{
return len_r(p, 0);
}

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

FR>>Да я и не призываю тебя писать в этом стиле просто показываю что эффективность уже не проблема.

PD>Я согласен с тем, что ты показал возможность реализации рекурсии без стека. Если быть точнее, то компилятор реализовал рекурсивную функцию С++ без рекурсивной подпрограммы в машинных кодах.

Для функциональных языков развертка хвостовой рекурсии норма.

PD>Но заплатил ты за это ИМХО слишком дорого.

По моему практически бесплатно.

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

Нет все разрешимо, смотри выше.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, gandjustas, Вы писали:

G>>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>>Здравствуйте, gandjustas, Вы писали:

G>>>>Ничего не притянуто. Рекурсивное решение требует меньше знания языка, чем решение с циклом
PD>>>Это не аргумент.
G>>Если вопрос касается обучения, то очень даже аргумент. В том же SICP в одном семестре умещается полезных знаний програмимрования гораздо больше, чем в среднестатистическом курсе на с\паскаль.
PD>До сих пор никаких проблем с обучением не было. Рекурсия была, роль ее подчиненная. Не надо на ровном месте проблемы создавать.
Аргумент в духе "мы всегда так делаем"?

>>>>кроме того обладает семантикой выражения, что лучше понимается математиками
PD>>>Это тоже. Какое мне дело, как они понимают, лучше или хуже.
G>>Ну да, читаемость программ — совершенно неважное свойство.

PD>Опять не надо так. Во-первых, эффективность важнее, по крайней мере для меня. Во-вторых, что такого нечитаемого и непонятного в обычном цикле ты нашел. Если он не понятен — тому, кто его читает надо профессию сменить, потому что он должен быть понятен после 2 месяцев обучения. Раз и навсегда.
Вопрос не в конкретном цикле, а в общем подходе.
Важно ведь не написать конкретное вычисление длины строки в цикле, а понять общение подходы к обработке последовательностей.

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


PD>>>А вот эффективность его ниже
G>>А вот это действительно сомнительный агрумент, так как очевидно пример с таким вычислением длины строки к реально жизни отношения не имеет.
PD>Безусловно. Я его и привел как пример искусственный.

>>Во многих случаях длина строки хранится вместе со строкой
PD>Только при этом ее посчитали. Впрочем, мне дискуссии на эту тему уже очень надоели.
Да ну? Строковые литералы в программе уже компилируются вместе с длиной, все функции, которые читают строки из вне уже знают её длину на момент возврата управления программе. Любюые операции со строками оперируют уже известной длиной.


PD>>>...потому что если цикл может быть реализован по регистру, рекурсия (если ее реализовать как положено) — это работа со стеком, то есть с памятью.
G>>Если рекурсию реализовать как положено, то она тоже прекратится в цикл в машинных кодах. Только не все компиляторы так умеют.

PD>Точнее сказать, никто не умеет. Потому что по calling convention, которые надо соблюдать, можно, конечно, аргументы передавать и через регистры, если их хватит, а вот адрес возврата всегда заносится в стек. По крайней мере в x86.
Много кто умеет оптимизировать хвостовую рекурсию.