if else ненужно

будь они либо с однойВсеСтороныОнли либо
СлюбойстороныНоВсегдаИзвестноВкакомПорядке то
вместо лишних скобок мона было бы цепочкой и случай a*() отличается от a()* , а не (*a)() и *(a()) - вот как произвол дедов мешает то

хвостовая рекурсия и есть цикл

Хвостовая рекурсия это хвостовая рекурсия (частный случай линейной рекурсии, частный случай рекурсии общего вида), циклом она не является и связана с ним только косвенно (тем, что её можно в него преобразовывать, при подходящем target).

При том, что GCC и так прекрасно умеется tail call.

Можно взглянуть на толковый код, который кому то нужен и его написал ты?

Нет. NDA may be :)

такого кода не существует

такого кода не существует

Ну, стало быть, и if else нужно.

эээ всякий цикл сводим к хвостовой.

про обратное(всякоя хвостовая к повтору ) хм - вроде тоже.

т.е цикл и хвостовая рекурсия это одно и тоже

мужико то и не знали

да, однозначно.

затруднения(не охота на прямую адресса возврата писать) в реализации break из концевой рекурсии как замены цыкла . чё подскажите?

изучи русский для начала...

gcc умеет, а стандарт - нет.

тем, что её можно в него преобразовывать, при подходящем target

Примеры неприводимых targets в студию.

В языке могут быть только циклы, только рекурсия или и то и другое. Всякий цикл в языке A (с поддержкой циклов) можно переписать как хвостовую рекурсию в языке B (с поддержкой рекурсивных функций), и наоборот (в том числе, в случае A = B языка с поддержкой и циклов и рекурсивных функций). Ну, с точностью до изоморфизма, одно и то же. Но на уровне конкретных языковых конструкций (языков A и B) - очень разные вещи, просто разные термы, часто без гарантий TCO, стилистически разные, конвенционально разные (вот не принято в си вместо циклов писать хвостово-рекурсивные функции и кивать на то, что большинство компиляторов всё равно умеют TCO). А то так и машины Тьюринга с нейронными сетями определённого вида это «одно и то же», при этом, совершенно разное с точки зрения реализации и предпочтительности. Короче, сходство (изоморфизм) позволяет смотреть на разные вещи как на идентичные, под определённым углом, но разные вещи от этого разными быть не перестают.

Вообще, «хвостовая рекурсия» это свойство рекурсивного терма, то есть предикат - терм либо рекурсивный, либо нет, рекурсия либо линейная, либо нет, хвостовая, или нет. При этом линейная рекурсия всегда преобразуется в хвостовую, а для хвостовой можно написать TCO в target с циклами/jmp-ами/etc.

чё подскажите?

ПальцЫ сдвинь, школота.

А уже сказали, что если false = 0, а true != 0? Другими словами если первый аргумент true - то там хрен знает что может быть.

если первый аргумент true - то там хрен знает что может быть.

true при приведении к int равен 1

Примеры неприводимых targets в студию.

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

Вот хвостовая рекурсия:

int tc(int a, int n) { return n < 2 ? a : tc(a * n, n - 1); }

Вот цикл:

int loop(int n) { int a = 1; for (int i = n; i > 1; i--) a *= i; return a; }

А вот целевое «одно и то же»:

tc:
	pushl	%ebp
	movl	%esp, %ebp
	movl	12(%ebp), %edx
	movl	8(%ebp), %eax
	cmpl	$1, %edx
	jg	.L5
	jmp	.L2
.L4:
	movl	%ecx, %edx
.L5:
	leal	-1(%edx), %ecx
	imull	%edx, %eax
	cmpl	$1, %ecx
	jne	.L4
.L2:
	popl	%ebp
	ret

loop:
	pushl	%ebp
	movl	$1, %eax
	movl	%esp, %ebp
	movl	8(%ebp), %edx
	cmpl	$1, %edx
	jle	.L8
.L9:
	imull	%edx, %eax
	subl	$1, %edx
	cmpl	$1, %edx
	jne	.L9
.L8:
	popl	%ebp
	ret

Называть цикл хвостовой рекурсией или хвостовую рекурсию циклом неправильно. Но можно говорить, что один и тот же алгоритм [может быть] реализуем как две [разные!] программы - одна с циклом, другая с хвостовой рекурсией.

С точки зрения свойств термов - вот нерекурсивный терм:

λ m n . m + n

терм с хвостовой рекурсией (с оговоркой про if):

λ f a n . if (n = 0) a (f (n × a) (n - 1))

с хвостовой рекурсией (без оговорок):

λ f n . f n

с линейной:

λ f n . if (n = 0) 1 (n × f (n - 1))

с древовидной:

λ f n . if (n < 2) n (f (n - 1) + f (n - 2))

то в какие инструкции будет (если будет) преобразовываться первый терм, будет ли ко второму и третьему применена TCO, будет ли четвёртый приведён ко второму и будет ли пятый автоматически мемоизироваться - всё это не касается самого этого языка, а касается только его компилятора (реализации).

во-вторых хвостовая рекурсия и есть цикл.

Ничего подобного. man продолжения, F# Async, Haskell Cont.

тэг [вещества] забыл

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

J оператор ландина не?

Я считаю, что любой циклический алгоритм можно свести к хвостовой рекурсии и наоборот.

А не существует строго универсального критерия «хвостовости» и «цикличности». Например, хвостовая рекурсия может быть через if, через let, через cons, через цикл :) Будет ли вызов хвостовым - зависит от компилятора (мало кто, например, умеет через cons). И то же самое про «цикличность» - не определённая вещь, чтобы её определить, нужно взять конкретный язык и сказать, что вот эта часть абстрактного синтаксиса есть циклы (а это может быть что-то вроде tagbody из CL), точно также нужно брать конкретный язык и вводить предикат устанавливающий хвостовой вызов или нет в данном терме (такой «предикат» сам по себе реализуется ad-hoc компилятором умеющим TCO).

В качестве опровержения прошу привести контрпример.

Хвостовой вызов всегда можно свести к линейному циклу. Линейный цикл (ну типа for) - к хвостовой рекурсии (по крайней мере это интуитивно кажется верным), «циклы» вроде tagbody и условные переходы вообще не сводимы к хвостовой рекурсии, но сводимы к рекурсии вообще (тезис Чёрча-Тьюринга).

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

Хвостовой вызов всегда можно свести к линейному циклу. Линейный цикл (ну типа for) - к хвостовой рекурсии (по крайней мере это интуитивно кажется верным),

Я об этом и говорю. Остальные случаи, «рекурсия вообще», не рассматриваются.

Всё равно, писать goto и говорить, что это хвостовая рекурсия нельзя.

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

int f_(int a, int i)
{
	if (i > 0) {
		a *= i--;
                f_(a, i);
	} else {
		return a;
	}
}

Когда пьешь - закусывай.

Хвостовой вызов всегда можно свести к линейному циклу.

Если только к внешнему как в трамплине. А так попробуй сведи к циклу вложенное вычисление Async! Нобелевскую могут дать.

Если бы все было так просто, то в .NET IL не стали бы вводить специальный тег, который бы умела распознавать виртуальная машина. Она как раз выступает в роли внешнего вычислителя. Поэтому некоторым ее версиям (не всем!) удается правильно разрулить хвостовой вызов. Причем, команда .NET шла к этому довольно долго. И не все у них получалось. По-моему абсолютной гарантии правильного хвостового вызова в .NET нет до сих пор.

Ну, ладно. За сим оставляю вас.

J оператор ландина не?

Увы, я не знаю, что это такое.

Нобелевскую могут дать.

Интересно, в какой номинации: литературы или м.б. мира?

Увы, не понимаю. Вот в GCC/LLVM/SBCL/Scheme/GHC все хвостовые вызовы превращаются в циклы, и хвостовые вызовы это либо внешние рекурсивные вызовы вроде (defun foo (...) (foo ...)), либо внешние рекурсивные вызовы под специальными формами вроде (defun foo (...) (if (...) (foo ...) (...))). Тут никаких проблем.

Если при этом с какой-то замороченной специальной формой так не получается - проблемы жирного языка (с замороченными специальными формами со сложной семантикой) и компилятора (вот у SBCL же получается с unwind-protect?).

Если только к внешнему как в трамплине.

Ну, дык, если рекурсивный вызов не внешний, а под одной или более функцией - вот так (defun foo (...) (g (h (... (foo ...))))), - то это уже не хвостовая рекурсия, а рекурсия общего вида. Если там вызов foo единственный (как в самом простом факториале, и _не_ как в самой простой фибоначи, где вызова два и там дерево вызовов образуется), то такая рекурсия это линейная рекурсия. Всё остальное - нелинейная рекурсия общего вида.

Нобелевскую могут дать.

Стандарт Scheme требует чтобы все внешние вызовы и внешние вызовы под специальными формами (= хвостовые вызовы) преобразовывались в циклы? Да.

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

Ну а нелинейную рекурсию можно оптимизировать мемоизациями.

Насколько я знаю, две последние вещи никто толком не делает в сурьёзных компиляторах.

Увы, я не знаю, что это такое.

Это из статьи Peter J. Landin. The next 700 programming languages. (Перечислена тут - http://www.cis.upenn.edu/~bcpierce/courses/670Fall04/GreatWorksInPL.shtml - среди The greatest of the great).

судя по имени ( Async) - дело в многопроцессности контекста (у глобального стэйта несколько точек(«сопрограмм») которые стэйт меняют и при рекурсии передаваемый стэйт отличается от стэйта(инварианта) сохраняющегося в цикле )

человек Async' ом проникся и уникальностью .Net абстактной машины

Хотя нет, не из этой (http://en.wikipedia.org/wiki/J_operator).

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

(defun test (fun)
  ...
  (funcall fun some-arg))

Вот, тут и начинается свисто-пляска

В приведённом коде нет рекурсии.

Представь, что fun зависит от test.

Такая рекурсивная зависимость возникает, например, при реализации конструкции while в F# Async:

        /// Implement the while loop
        let rec whileA gd prog =
            if gd() then 
                bindA prog (fun () -> whileA gd prog) 
            else 
                doneA

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

(defun while (gd prog)
  (when (funcall gd)
    prog
    (while gd prog)))

вот тут хвостовая (будут прыжки в ассемблере без вызовов while).

bindA - это монадическая связка для Async. Устроена по подобию такой же для Cont. Посыл в том, что там передается вызов whileA через продолжение внутрь bindA. При выполнении bindA вызывает whileA, который в свою очередь снова вызывает bindA, пока условие gd не станет ложным. То есть имеем рекурсию.

Вся фишка в то, что все вызовы внутри whileA и bindA - хвостовые. А поэтому при соответствующей поддержке со стороны .NET CLR не съедается стек, зато активно кушается куча. В общем, бесконечный цикл через while должен работать внутри async вечно.

Кстати, если запустить что-то содержащее async на mono, то сразу резко просядет производительность, что говорит о том, что поддержка оптимизации хвостового вызова далась им с трудом ;)

Подведем итог:

1. Имеем рекурсивные вызовы (whileA -> bindA -> whileA -> ...).

2. Все вызовы внутри whileA и bindA хвостовые.

Следствия:

1. Не сдъедается стек.

2. Активно потребляется куча, но выделенная память может быть возвращена обратно, если такое возможно (кстати, возможны и утечки памяти в async)

Задача достойная Нобелевской: переписать whileA через цикл. Кто возьмется?

P.S. А твой вариант while не годится. Вычисление async нужно уметь прерывать в любой момент, а потом возобновлять позже. Увы, у тебя нет возможности прервать цикл while, а затем продолжить его. Кстати, продолжить, может быть, на другом ядре другого процессора (почему async называется именно так?)

Все вызовы внутри whileA и bindA хвостовые

Не сдъедается стек

переписать whileA через цикл

Ну так если вызовы хвостовые и вычисление не съедает стек, значит .NET _уже_ переписывает этот код в удобное ему (ей, VM) цикло-подобное представление, так?

if else ненужно

Убейся.

А хрен его знает, как они делают в .NET. В самом начале я написал, что через внешний цикл можно написать, да через тот же трамплин. Речь идет о переписывании самого whileA через цикл, т.е. без посторонней помощи. Ведь именно о таких циклах шла речь. Так?

С Cont домучил до такого состояния:

while :: Bool -> (r -> r) -> r -> r
while p f x = if p then f (while p f x) else x

не хвостовая рекурсия - линейная.

P.S. Cont/Async/CPS для меня тёмный лес, если что.

И твой пример работает? :)

Красота всех этих продолжений в том, что там любое вычисление раскладывается в хвостовые вызовы. Это происходит даже с первоначально вложенными рекурсивными нехвостовыми вызовами. Вообще, все рекурсивные вызовы в рамках вычисления Cont внезапно становятся хвостовыми.

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

Кстати, это есть и в Common Lisp: пакет cl-cont. Только там вложенные рекурсивные функции нужно определять как defun/cc. Ну, еще я заметил, что если SBCL отлично справляется с хвостовой рекурсией, то CCL начинает лажать. Но это поправимо через внешний трамплин.

Что касается самого while, то в F# его построитель имеет тип:

While: (unit -> bool) -> M<unit> -> M<unit>

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

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

Если быть точным, то там еще применяется функция Delay:

Delay: (unit -> M<'a>) -> M<'a>

но это уже борьба с энергичностью самого F#.

Короче, рекомендую ознакомиться с F# :) Там есть интересные идеи, которых нет в других языках. Жаль, что для .NET :(

И твой пример работает?

Это, в принципе, тот же whileA в котором bindA заменён на >>=, а doneA на return () и потом раскрыты комбинаторы и типы для случая Cont.

В общем случае будет:

while :: Monad m => m Bool -> m a -> m ()
while p k = p >>= flip when (k >> while p k)

не похоже на хвостовой вызов (та самая линейная рекурсия), но если расписать так:

while :: Monad m => m Bool -> m a -> m ()
while p k = do
  t <- p 
  if t
    then do 
      k
      while p k
    else
      return ()

то от этого уже хочется ожидать компиляции в цикл.

Ну и работать будет как в банальном IO (), так и, например, в (Monad m => ContT r m):

test :: ContT r IO ()
test = 
  while (liftIO $ ("exit" /=) <$> getLine) $ liftIO $ do
    putStrLn "a number?"
    m :: Int <- read <$> getLine
    putStrLn $ "receive " ++ show m
    putStrLn "what's next?"

-- > runContT test $ const $ putStrLn "the end"

-- a number?
-- 1
-- receive 1
-- what's next?

-- a number?
-- 2
-- receive 2
-- what's next?
-- exit
-- the end

хотя смысла этого я всё ещё не понимаю - в хаскеле while получается обычной хвостовой рекурсией через do (которую нужно посчитать за специальную форму) и явной связи с Cont тут нет (в Control.Monad вместе с when, guard, unless, forever и т.п. мог бы быть и такой while).

А чем это по сути отличается от if?

Но ведь не всякий do дает хвостовой вызов. Наверное, в этом дело.

Вообще, Haskell - не самый удачный язык для изучения этой штуки. Я попробовал составить пример, но тут вмешалась ленивость. С нею труднее получить StackOverflowException, а если и получишь, то совсем не в том месте, в котором ожидал :)

Хвостовой вызов в Haskell не так полезен, как в других энергичных языках, а иногда может быть и вреден (foldl).

Между прочим, у тебя проскакивало уж очень мудренное определение монадической связки для Cont, что может спутать. Я чаще оперирую более простым из знаменитой статьи Вадлера «Essence of functional programming»:

type Cont a = (a -> Answer) -> Answer

unitC a     = \c -> c a
m `bindC` k = \c -> m (\a -> k a c)

На нем видны все хвостовые вызовы, но как я написал, конкретно для Haskell это не так существенно, как, например, для энергичных языков типа F#.

Я чаще оперирую более простым из знаменитой статьи Вадлера «Essence of functional programming»

Императивное объяснение:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef void* dyn;
typedef dyn(arrow)(dyn);                // void*(*)(void*)
typedef dyn(continuation)(arrow);       // void*(*)(void*(*)(void*))
typedef dyn(binding)(dyn, arrow);       // void*(*)(void*, void*(*)(void*))

#define debug(fun, format, args...) \
    printf("%-20s " format , fun, ##args)

/* (void*(*)(void*(*)(void*)))(*)((void*)(*)((void*)(*)(void*)), void*(*)(void*, void*(*)(void*)))
 * ^ ~~~~~~~~~~~~~~~~~~~~~~~ ^
 * This is an allocation, brother, so don't put the code for nested functions on the stack, put it
 * in the heap instead and collect via GC (duh), or infer the region that uses this function and
 * emit an explicit `free' for the function code at compile-time.
 */
/* continuation */ dyn /* or garbage */ bind(continuation cont, binding binder)
{
    debug("bind", "cont = %p, binder = %p\n", cont, binder);
    dyn lambda(arrow func) { // nested function is ok
        debug("bind, l1", "cont = %p, binder = %p, func = %p\n", cont, binder, func);
        dyn yet_lambda(dyn val) { // nested in nested is ok
            debug("bind, l2", "cont = %p, binder = %p, func = %p, val = %p\n", cont, binder, func, val);
            return binder(val, func);
        }
        debug("bind, l1", "cont = %p, binder = %p, l2 = %p\n", cont, binder, yet_lambda);
        return cont(yet_lambda);
    }
    debug("bind, l1", "cont = %p, bind = %p, l1 = %p\n", cont, binder, lambda);
    return lambda; // wtf, gcc, where is your gc? xD
}

int main(void)
{
    int x;

    /* continuation */ dyn /* yet garbage */ add(dyn x, dyn y) {
        debug("add", "x = %p, y = %p\n", x, y);
        dyn add_cps(arrow kont) {
            debug("add, add_cps", "x = %p, y = %p, kont = %p\n", x, y, kont);
            return kont((dyn)((intptr_t)x + (intptr_t)y));
        }
        return add_cps;
    }

    dyn then(dyn res, arrow func) {
        debug("then", "res = %p, func = %p\n", res, func);
        return func(res);
    }

    dyn print(dyn val) {
        debug("print", "val = %p\n", val);
        return NULL;
    }

    debug("main", "main = %p\n", main);
    debug("main", "bind = %p\n", bind);
    debug("main", "stack ~ %p\n\n", &x);
    debug("main", "add = %p\n", add);
    debug("main", "then = %p\n", then);
    debug("main", "print = %p\n\n", print);

    dyn cont = bind(add((dyn)1, (dyn)2), then);

    debug("main", "cont = %p\n", cont);

    (*(dyn(*)(dyn))cont)(print);

    return 0; 
}

main                 main = 0x400830
main                 bind = 0x400720
main                 stack ~ 0x7fff14f39fbc

main                 add = 0x4006c0
main                 then = 0x4005c0
main                 print = 0x400590

add                  x = 0x1, y = 0x2
bind                 cont = 0x7fff14f39fa0, binder = 0x4005c0
bind, l1             cont = 0x7fff14f39fa0, bind = 0x4005c0, l1 = 0x7fff14f39f70
main                 cont = 0x7fff14f39f70
bind, l1             cont = 0x7fff14f39fa0, binder = 0x4005c0, func = 0x400590
bind, l1             cont = 0x7fff14f39fa0, binder = 0x4005c0, l2 = 0x7fff14f39f20
add, add_cps         x = 0x1, y = 0x2, kont = 0x7fff14f39f20
bind, l2             cont = 0x7fff14f39fa0, binder = 0x4005c0, func = 0x400590, val = 0x3
then                 res = 0x3, func = 0x400590
print                val = 0x3

работать совсем не должно - функции лежат на стеке и могут портится (у меня работает только с -O3), может быть segmentation fault, illegal hardware instruction и мусор в результате.

В языке с HOFами, lambdaми и сборкой мусора будет проще:

(define (bind-continuation continuation binder)
  (lambda (function)
    (continuation
      (lambda (value)
        (binder value function)))))

В хаскеле, за счёт point free, ещё проще:

m `bindC` k = \c -> m (\a -> k a c)
bindC m k = \c -> m (\a -> k a c)
bindC m k c = m (\a -> k a c)
bindC m k c = m (\a -> flip k c a)
bindC m k c = m (flip k c)
bindC m k = m . flip k
bindC m k = (.) m (flip k)
bindC m = (.) m . flip
bindC = ?

А чем это по сути отличается от if?

Вот так нельзя написать:

T x = if (p) a else b;
T y = if (p) { a; b } else { c; d };
return if (p) a else b;

так можно:

T x = p ? x : y;
T y = p ? (a, b) : (c, d);
return p ? x : y;