LINUX.ORG.RU

Go lang. TCO. defer.

 , ,


0

3

А кто-нибудь реализовывал хвостовую рекурсию через defer? Просто любопытно.есть ли какие-то особенности. Не покидает ощущение, что рекурсивный вызов самого себя через defer все равно гадит в стек.

PS: проверить, конечно, и сам могу, но вдруг кто-то уже ресерчил или встречал в инете дискуссию на эту тему. мои вопросы гуглу не принесли результата.

Update

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

Deleted

Последнее исправление: Deleted (всего исправлений: 2)

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

PolarFox ★★★★★
()
Ответ на: комментарий от PolarFox

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

Deleted
()
Ответ на: комментарий от Deleted

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

Bad_ptr ★★★★★
()
Последнее исправление: Bad_ptr (всего исправлений: 1)

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

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

proud_anon ★★★★★
()
Ответ на: комментарий от Bad_ptr

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

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 - это не какая-то конструкция языка. это скорее синтаксический сахар.

Deleted
()
Ответ на: А если так? от Bad_ptr

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

Bad_ptr ★★★★★
()
Ответ на: комментарий от Deleted

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

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

ee1337a
()

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

mix_mix ★★★★★
()
Ответ на: комментарий от mix_mix

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

anonymous
()
Ответ на: комментарий от loz

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

anonymous
()
Ответ на: комментарий от mix_mix

Common Lisp

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

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

loz ★★★★★
()
Ответ на: комментарий от loz

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

mix_mix ★★★★★
()
Ответ на: комментарий от Deleted

делаем вывод: 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.

anonymous
()
Ответ на: комментарий от anonymous

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

знаю, читал.

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

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

Deleted
()
Ответ на: комментарий от Deleted

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

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

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

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

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

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

proud_anon ★★★★★
()
Последнее исправление: proud_anon (всего исправлений: 2)
Ответ на: комментарий от Deleted

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

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

tensai_cirno ★★★★★
()
Ответ на: комментарий от Deleted

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

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

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

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

emulek
()
Ответ на: комментарий от proud_anon

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

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

Deleted
()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Deleted

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

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

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

proud_anon ★★★★★
()
Последнее исправление: proud_anon (всего исправлений: 1)
Ответ на: А если так? от Bad_ptr

А если так?

Ничего не получится, из 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))
}
korvin_ ★★★★★
()
Ответ на: комментарий от proud_anon

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

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

Deleted
()
Ответ на: А если так? от korvin_

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

проще:

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

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

Deleted
()
Ответ на: комментарий от Deleted

проще:

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

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

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

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

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

korvin_ ★★★★★
()
Последнее исправление: korvin_ (всего исправлений: 1)
Ответ на: комментарий от Deleted

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

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

proud_anon ★★★★★
()
Ответ на: комментарий от loz

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

dave ★★★★★
()
Ответ на: комментарий от korvin_

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

Deleted
()
Ответ на: комментарий от Deleted

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

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

korvin_ ★★★★★
()
Последнее исправление: korvin_ (всего исправлений: 1)
Ответ на: комментарий от Deleted

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

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

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
korvin_ ★★★★★
()
Последнее исправление: korvin_ (всего исправлений: 2)
Ответ на: комментарий от Deleted

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

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

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

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

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

dave ★★★★★
()
Ответ на: А если так? от korvin_

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

anonymous
()
Ответ на: комментарий от korvin_

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

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

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

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

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

korvin_ ★★★★★
()
Ответ на: комментарий от korvin_

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

korvin_ ★★★★★
()
Последнее исправление: korvin_ (всего исправлений: 1)
Ответ на: комментарий от Deleted

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

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) }

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.