В go по спецификации TCO нет. Если вдруг в реализации есть, то это оптимизация на наличие которой не стоит полагаться.

Я знаю, что TCO нет в языке. Иначе бы и не возникал подобный вопрос. Также я знаю, что можно через цикл или goto реализовать нужный механизм. Но меня интересует именно близкая по своей сути реализация к хвостовой рекурсии. Собственно потому и заинтересовал такой вопрос.

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

А кто-нибудь реализовывал хвостовую рекурсию через defer?

defer вроде как всего лишь откладывает вызов функции до возврата. То есть перед возвратом будет выполнен отложенный вызов. Оптимизации хвостового вызова никто не обещал.

defer не так работает, как ты думаешь.

А можно не столь загадочный ответ? :)

не поленился, добрался до ноута и проверил. а то в треде словоблудие началось. вот что получил

func tco(a int) (ret int) {
    fmt.Printf("call tco: %d\n", a+1)
    defer tco(a+1)
    
    return 0
}

func main() {
    tco(0)
}

вот результат

<skipped>
call tco: 3947563
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

теперь простая рекурсия

func tco(a int) (ret int) {
    fmt.Printf("call recoursive: %d\n", a+1)
    return tco(a+1)    
}

func main() {
    tco(0)
}

выхлоп

call recoursive: 3947563
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

делаем вывод: defer - это не какая-то конструкция языка. это скорее синтаксический сахар.

А если так?

func tco(a int) (ret int) {
    defer func(){
        x := recover()
        return tco(x+1)
    }
    fmt.Printf("call tco: %d\n", a+1)
    panic(a)
    return 0
}

да, анонимную функцию после дефер, нужно вызвать:
}()
на 5 строке

defer нужен лишь только для запуска перед выходом. Всё. Например, гораздо удобнее написать так, как ниже, нежели в самом конце всё прописывать.

foo, err := bar()
if err != nil { log.Fatal(err) }
defer foo.cleanup()

как можно серьезно кодить на языке где даже нет TCO? понятно что цепочка deferred'ов будет растягиваться в длину рекурсии и все полетит к чертям.

ещё recover().(int) на 3й строке

как можно серьезно кодить на языке где даже нет TCO?

ггг расскажи это джавистам.

как можно серьезно кодить на языке где даже нет TCO?

TCO нет в C, C++, Python, Java, Common Lisp etc. Компилятор может проводить оптимизацию (как gcc, sbcl), но по стандарту не обязан. С go точно та же ситуация: требования нет, но по факту в каких-то случаях TCO совершается.

Я и имел в виду отсутствие TCO в компиляторе(ах). Имхо, для любого языка где есть рекурсивные функции должна быть реализована TCO.

как будто на жабе кто-то кроме индусов пишет

Common Lisp

Несерьезно, требую убрать его из списка:

The following implementations were found to provide full TCO:
CMUCL
SBCL
CCL
Allegro
LispWorks

Так стандарт не обязывает же (в отличии от схемы), об этом речь шла, gcc и clang тоже оптимизируют, но ты же не будешь говорить, что в си есть TCO?

делаем вывод: defer - это не какая-то конструкция языка. это скорее синтаксический сахар.

Странный какой-то вывод. Почитай, что ли: http://blog.golang.org/defer-panic-and-recover

A defer statement pushes a function call onto a list. The list of saved calls is executed after the surrounding function returns.

Странный какой-то вывод. Почитай, что ли: http://blog.golang.org/defer-panic-and-recover

знаю, читал.

The list of saved calls is executed after the surrounding function returns.

когда читаю такой текст, подразумеваю, что стек вызова минусуется (очищается). но как я показал в примере, defer самого себя ничем не отличается от рекурсивного вызова. т.е. стек не очищается, а напротив, наращивается новыми данными. вот это я называю синтаксическим сахаром. если б они у рекурсивного defer'а подчищали стек возврата, то это бы стало конструкцией языка (т.е. это бы стало ТСО по смыслу).

The list of saved calls is executed after the surrounding function returns.

когда читаю такой текст, подразумеваю, что стек вызова минусуется (очищается).

А, вот откуда ты это взял! Я всё думал, почему ты вообще решил, что тут хвостовой вызов должен оптимизироваться.

Да, с точки зрения синтаксиса языка вызов defer'нутых функций выполняется после исполнения return, при вылете из функции при панике или по достижении конца функции. Таков синтаксис языка в вакууме. Но какой машинный код должен получаться из кода на Go, в том числе, должна ли функция очищать стек перед defer'нутыми вызовами, и вообще должен ли у машины быть стек, который можно очищать, о том спецификация вообще ничего не говорит.

вот это я называю синтаксическим сахаром.

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

делаем вывод: defer - это не какая-то конструкция языка. это скорее синтаксический сахар.

А документацию почитать слабо?

когда читаю такой текст, подразумеваю, что стек вызова минусуется (очищается). но как я показал в примере, defer самого себя ничем не отличается от рекурсивного вызова.

при чём тут стек? Может его и нет вовсе. Да и вообще, TCO вовсе не обязано быть _всегда_ оптимальным. Особенно в этом вашем многопоточным golang, там выгоднее иметь изолированный контекст, а адрес возврата вообще говоря — часть контекста.

defer - это не какая-то конструкция языка. это скорее синтаксический сахар.

return в C/C++ — тоже «синтаксический сахар», т.к. очищает стек от локальных переменных и выполняет RET (а в плюсах ещё и деструкторы вызывает).

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

PS: есть ощущение, что defer таки эволюционирует до TCO. и вот тогда это будет реально крутая фича.

PS: есть ощущение, что defer таки эволюционирует до TCO. и вот тогда это будет реально крутая фича.

Во-первых, TCO если и появится, то прежде всего в очевидной конструкции

return next_function()

А если так?

Ничего не получится, из deferred процедуры нельзя ничего возвращать (точнее оно вернётся в никуда). Можно только изменить результат:

func tco(a int) (ret int) {
    defer func() {
        if x, ok := recover().(int); ok {
            ret = tco(x+1)
        }
    }
    fmt.Printf("call tco: %d\n", a+1)
    panic(a)
}

Но, как понимаешь, никаким TCO тут и не пахнет.

BTW, return после panic не нужен. Типичная конструкция:

func toInt(m time.Month) int {
    switch m {
    case time.January:  return 1
    ...
    case time.December: return 12
    }
    panic("not reachable")
}

Но, вообще, всё проще:

package main

import "fmt"

func tco(res chan int, x int) {
	fmt.Printf("call recursive: %d\n", x)
	if x > 2000000000 {
		res <- x
		return
	}
	go tco(res, x+1)
}

func TCO(x int) int {
	res := make(chan int)
	go tco(res, x)
	return <-res
}

func main() {
	fmt.Println(TCO(1))
}

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

а чем сложно? defer'ы складываются в стек, и для реализации ТСО нужно лишь оптимизировать верхушку стека. А какая «высота стопки отложенных вызовов» - не важно

Но, вообще, всё проще:

проще:

с каналами и гоурутинами :).

я бы этот термин употребил в реализации с goto

проще:

с каналами и гоурутинами :).

А что в них непростого? Зачем вообще браться за Go, если они для тебя недостаточно просты?

я бы этот термин употребил в реализации с goto

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

Вообще можно конечно просто воспользоваться циклом с состояниями, но и в этом случае понадобится «внешняя» процедура а ля TCO, которая будет реализовывать переходы. Вызов горутины с передачей канала для возврата значения выглядит проще и ближе к хвостовому вызову, ИМХО.

defer'ы складываются в стек, и для реализации ТСО нужно лишь оптимизировать верхушку стека

defer'ы в большинстве случаев используют локальные переменные. Таким образом, фрейм текущей функции просто нельзя удалить из стека, пока defer' не кончатся. Конечно, можно было бы, наверное, слегка его оптимизировать, но это если и появится, то, наверное, только в виде приятной, но не особо важной оптимизации в отдельных компиляторах, потому что «частичное TCO» в виде фичи языка не имеет смысла.

Насколько знаю из опыта «full TCO» действительно у SBCL, но его точно нет у CCL, Allegro и LispWorks. Также же как нет «full TCO» у Scalа, к примеру.

А что есть full TCO? Чем он отличается от просто ТСО?

Мне кажется каналы с рутинами дадут серьёзное проседание в производительности из-за накладных расходов на механизм обмена через канал.

Мне кажется каналы с рутинами дадут серьёзное проседание в производительности из-за накладных расходов на механизм обмена через канал.

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

Выше я имел в виду расходы на канал.

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

package main

import (
	"fmt"
	"time"
)

const N = 10000000



func tco1(res chan int, x int) {
	if x > N {
		res <- x
		return
	}
	go tco2(res, x+1)
}

func tco2(res chan int, x int) {
	go tco1(res, x+2)
}

func tco(x int) int {
	res := make(chan int)
	go tco1(res, x)
	return <-res
}



type stateF func(int) (int, stateF)

func state(x int) int {
	x, f := state1(x)
	for {
		if f == nil {
			break
		}
		x, f = f(x)
	}
	return x
}

func state1(x int) (int, stateF) {
	if x > N {
		return x, nil
	}
	return x+1, state2
}

func state2(x int) (int, stateF) {
	return x+2, state1
}



func test(title string, f func(int) int) {
	fmt.Printf("%s: ", title)
	start := time.Now()
	res   := f(1)
	fmt.Printf("%d, %v\n", res, time.Since(start))
}

func main() {
	test("goroutine", tco)
	test("stateloop", state)
}

% go run tco.go
goroutine: 10000003, 2.220127s
stateloop: 10000003, 52.003ms

Термин «full TCO» сам увидел здесь в первый раз и удивился) А так, нужно еще уметь оптимизировать так называемый косвенный хвостовой рекурсивный язык, который может передаваться через лямбду вниз по рекурсии. На уровне компилятора косвенный вызов не оптимизируется, по крайней мере, не оптмизируется эффективно.

Косвенная рекурсия важна, например, для продолжений и монад, основанных на продолжениях, да тех же асинхронных вычислений в F#.

С языками типа Scala и F# проблема в том, что косвенную рекурсию должна поддерживать еще виртуальная машина. В случае нативных языков все проще - там достаточно правильно определить соглашение о вызовах, например, как это описано в знаменитой книге PAIP. Но если соглашение о вызовах другого вида существует уже десятилетиями и противоречит TCO, то это уже большая проблема для таких языков.

Явовская виртуальная машина оптимизировать хвостовой вызов не умеет. Объясняют какими-то соображениями секьюрности. В детали особо не вдавался.

В виртуальной машине .NET есть зарезервированная метка для обозначения хвостового вызова, чтобы виртуальная машина иначе раскрывала вызов. Не все реализации .NET умеет обрабатывать такую метку. Причем, насколько могу судить, компилятор C# такую метку не использует. Она нужна именно для F#, и как понимаю, само наличие такой метки на уровне IL - это во многом заслуга создателя F#, Дона Сайма.

Ну ты отжег. Ты хоть представляешь себе, во что это выльется? Создал очередь, напихал туда кучку говна, потом запустил поток для чтения этого говна. Круто, чо. Вот только тема про рекурсивные функции и TCO. Если бы реализация с TCO в такое рекурсивные функции разворачивала, ты был бы рад?

Круто, если у тебя это «лёгкое проседание»=) Теперь представь проект нормального объёма с заменой вот на это вот. Гуй делаешь?

Создал очередь, напихал туда кучку говна

Это ты про канал? Если да, то о какой куче говна речь?

Если бы реализация с TCO в такое рекурсивные функции разворачивала, ты был бы рад?

Ты наркоман или это юмор такой?

Теперь представь проект нормального объёма с заменой вот на это вот.

Угу, уже представил проект нормального объёма на императивном языке с подобной глубиной рекурсии. Шути дальше.

Угу, уже представил проект нормального объёма на императивном языке с подобной глубиной рекурсии.

Там была бы не рекурсия. Но и не твой вариант, явно=)

Там была бы не рекурсия. Но и не твой вариант, явно=)

Ага, но ТС зачем-то спрашивал про (хвостовую) рекурсию, так что вот ему пару вариантов на выбор.

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

package main

import «fmt»

func tco(a int) (ret int) { fmt.Printf(«call recoursive: %d\n», a+1) if a < 100 { return tco(a + 1) } return }

func main() { tco(0) }

package main

import «fmt»

func tco(a int) (ret int) { fmt.Printf(«call tco: %d\n», a+1) if a < 100 { defer tco(a + 1) }

return 0 }

func main() { tco(0) }