Комментарии 105
хотелось бы статистику по использованию памяти тремя способами
ведь похоже именно из-за этого падает нативный C#?
ведь похоже именно из-за этого падает нативный C#?
Интересно было бы сравнить реализацию тех же чисел Фиббоначи с помощью цикла и сравнить время выполнения.
Кстати прокрутив несколько примеров в голове, у меня возникло очень уверенное подозрение, что любую хвостовую рекурсию можно завернуть в цикл.
Кстати прокрутив несколько примеров в голове, у меня возникло очень уверенное подозрение, что любую хвостовую рекурсию можно завернуть в цикл.
Любую вообще рекурсию можно развернуть в цикл.
Возможно это и так, но вот если ваша рекурсия будет ветвиться, то представление ее в виде цикла ой как много времени займет. С хвостовой все гораздо очевиднее.
Если мы про работу компилятора, то у него столько сложных забот помимо «циклевания» рекурсий, что врядли это сильно повлияет на скорость компиляции.
Нет, я не об уровне компилятора, а об уровне создания алгоритма и ее кодирования.
Я просто к тому написал первый пост, что автор пишет про оптимизацию хвостовой рекурсии и за счет нее говорит про преимущество одной платформы перед другой. Я же считаю, что такую штуку как хвостовая рекурсия вообще рассматривать не стоит, т.к. человек за несколько секунд может переделать хвостовую рекурсию в цикл, и поэтому подвергаю это преимущество .Net, как и все исследование проведенное в данной статье, сомнению.
Я просто к тому написал первый пост, что автор пишет про оптимизацию хвостовой рекурсии и за счет нее говорит про преимущество одной платформы перед другой. Я же считаю, что такую штуку как хвостовая рекурсия вообще рассматривать не стоит, т.к. человек за несколько секунд может переделать хвостовую рекурсию в цикл, и поэтому подвергаю это преимущество .Net, как и все исследование проведенное в данной статье, сомнению.
Да ладно — причём тут программист? В языках на основе JVM подержка хвостовой рекурсии появилась задолго до .NET (скажем Kawa в 1996 году уже её точно имела, а .NET в то время вообще ещё ничего не имел). Зачем она вообще в виртуальной машине? Этим компилятор должен заниматься…
А любой цикл FOR можно превратить в набор IF и GOTO.
Речь-то идет именно о преимуществе в выразительности, а не о принципиально недостижимых возможностях.
Речь-то идет именно о преимуществе в выразительности, а не о принципиально недостижимых возможностях.
Так дело-то в том, что при переходе от хвостовой рекурсии к циклу, вы в выразительности нисколько не потеряете
Да, но при декомпозиции императивной программы цикл придется завернуть в процедуру. В случае ФЯ такого не нужно делать — это и есть выразительность. По вашей логике, можно и от циклов и от процедур отказаться — они реализуются при помощи GOTO=)
Так я кажется понял, я слово «выразительность», употребил совсем в другом контексте — как «понимание того что делает данный кусок кода при беглом взгляде на него». Так что, по моей логике это совсем не следует.
Кстати, если уж взялись доказывать, что хвостовая рекурсия сравнима с циклами, то потрудитесь найти пример, который бы это показал. 5 процентов разницы — это не «сравнимо», например в криптографии такая вот «сравнимая» разница между новым и старым алгоритмом будет позиционироваться как прорыв тянущий на докторскую диссертацию.
Кстати, если уж взялись доказывать, что хвостовая рекурсия сравнима с циклами, то потрудитесь найти пример, который бы это показал. 5 процентов разницы — это не «сравнимо», например в криптографии такая вот «сравнимая» разница между новым и старым алгоритмом будет позиционироваться как прорыв тянущий на докторскую диссертацию.
Вас волнует выразительность кода на ЯВУ, или байт-кода? )
Развернет компилятор в результирующем байт-коде все хвостовые рекурсии в циклы, а их поменяет на if+goto, или в байт-коде будет инструкция «tail call» — мне как-то это пофигу, просто разворот рекурсии сделается чуть позже )
Развернет компилятор в результирующем байт-коде все хвостовые рекурсии в циклы, а их поменяет на if+goto, или в байт-коде будет инструкция «tail call» — мне как-то это пофигу, просто разворот рекурсии сделается чуть позже )
Ну, собственно, это то как раз обычно компилятор и делает. Скажем, GHC разворачивает. Правда, он не всегда может определить, что рекурсия хвостовая.
Ну и работу по переводу обычной рекурсии в хвостовую приходиться делать самостоятельно. Вместо:
приходится писать что-то вроде:
Ну и работу по переводу обычной рекурсии в хвостовую приходиться делать самостоятельно. Вместо:
length [] = 0 length x:xs = 1 + length xs
приходится писать что-то вроде:
length_helper [] n = n length_helper x:xs n = length_helper xs (n + 1) length xs = length_helper xs 0
Есть гораздо более приятный способ определить такую функцию:
length = foldr (const (+1)) 0 :)
Некоторые компиляторы умеют устранять рекурсию и в таком виде, вводя переменные-аккумуляторы, так же как сделал бы человек. Другой вопрос, что это сработает негарантированно, в отличие от явной хвостовой рекурсии. Поэтому пока, наверное, в реальном коде закладываться на такое не стоит, благо библиотечные ФВП (foldl, map и т.д.) покрывают достаточно много часто встречающихся случаев.
Раз уж мы ниже заговорили об LLVM, вот пример, как их оптимизатор, работающий на уровне SSA-представления, развернёт наивную рекурсивную реализацию факториала:
превращается в
Раз уж мы ниже заговорили об LLVM, вот пример, как их оптимизатор, работающий на уровне SSA-представления, развернёт наивную рекурсивную реализацию факториала:
define i32 @factorial(i32 %n)
{
%ifzero = icmp eq i32 %n, 0
br i1 %ifzero, label %Return1, label %Recursion
Return1:
ret i32 1
Recursion:
%tmp1 = sub i32 %n, 1
%tmp2 = tail call i32 @factorial(i32 %tmp1)
%result = mul i32 %n, %tmp2
ret i32 %result
}
превращается в
define i32 @factorial(i32 %n) {
%ifzero3 = icmp eq i32 %n, 0
br i1 %ifzero3, label %Return1, label %Recursion
Return1:
%accumulator.tr.lcssa = phi i32 [ 1, %0 ], [ %result, %Recursion ]
ret i32 %accumulator.tr.lcssa
Recursion:
%indvar = phi i32 [ 0, %0 ], [ %indvar.next, %Recursion ]
%accumulator.tr1 = phi i32 [ 1, %0 ], [ %result, %Recursion ]
%n.tr2 = sub i32 %n, %indvar
%result = mul i32 %n.tr2, %accumulator.tr1
%indvar.next = add i32 %indvar, 1
%exitcond = icmp eq i32 %indvar.next, %n
br i1 %exitcond, label %Return1, label %Recursion
}
Извиняюсь за безграмотность, а что это за язык?
Это не язык. По крайней мере не язык высокого уровня. «Ассемблер» LLVM. Грубо говоря, что-то вроде MSIL, только на основе SSA, а не стековой машины, и без высокоуровневых ООП фич.
Ребята молодцы, очень неплохо поработали.
В свете дискуссии, хочу всё-таки обратить внимание на инструкцию
Всё-таки, tail call это бесполезная инструкция или нет — вот в чём вопрос!!! ;)
В свете дискуссии, хочу всё-таки обратить внимание на инструкцию
%tmp2 = <strong>tail</strong> call i32 @factorial(i32 %tmp1)
Всё-таки, tail call это бесполезная инструкция или нет — вот в чём вопрос!!! ;)
Реализовано. см UPD.
Да и еще хотелось бы видеть реализацию этого алгоритма циклом, что бы точно видеть разницу между производительностью. А тот как-то вы сравниваете просто рекурсивные алгоритмы между языками, а изначально говорите, что хвостовая рекурсия сравнима по ресурсопотреблению с циклом. Уж приведите примеры пожалуйста.
Я конечно извиняюсь, но не в зуб ногой в Nemerlie. Но будут ли равнозначна ли коснтрукции def F2 объявлению метода класса?
Вообще-то, я как раз показывал примеры, где невооруженным глазом заметна «декомпозиция», просто в статье явного упоминания не было. :)
Тут еще такая вещь есть: рекурсивный алгоритм (над деревом, например) можно реализовать с помощью, стека и goto (выполняя работу компилятора).
Проблема в том, что такая реализация будет менее понятной, более длинной и сложнее в понимании, нежели рекурсивный вариант. К тому же, современные оптимизирующие компиляторы сведут на нет различия в этих двух реализациях, я почти уверен в этом.
PS кажется, я таки добился своего — заставил кого-то задуматься ^_^
Тут еще такая вещь есть: рекурсивный алгоритм (над деревом, например) можно реализовать с помощью, стека и goto (выполняя работу компилятора).
Проблема в том, что такая реализация будет менее понятной, более длинной и сложнее в понимании, нежели рекурсивный вариант. К тому же, современные оптимизирующие компиляторы сведут на нет различия в этих двух реализациях, я почти уверен в этом.
PS кажется, я таки добился своего — заставил кого-то задуматься ^_^
Я зачем вообще виртуальной машине нужно понятие о хвостовой рекурсии? Это ж задача компилятора. Отсуствие хвостовой рекурсии в JVM не мешает реализовывать на JVM языки с её поддержкой.
Наверное для того что бы сто раз не реализовывать то что можно один раз реализовать в виртуальной машине.
Тогда в VM можно понапихать вообще всего подряд, вплоть до quicksort-а, например. Зачем его каждый раз реализовывать…
Ну… VM вообще-то предполагает наличие стандартной библиотеки. QuickSort реализуется там. :)
> VM вообще-то предполагает наличие стандартной библиотеки.
Не уверен, что это обязательно.
В любом случае, вместо QuickSort можно подставить кучу других алгоритмов посика, сортировки и т.п. Что, их всех в VM пихать?
Не уверен, что это обязательно.
В любом случае, вместо QuickSort можно подставить кучу других алгоритмов посика, сортировки и т.п. Что, их всех в VM пихать?
> Не уверен, что это обязательно.
Не обязательно. Но реализаций VM без SL я ещё не видел. :)
> В любом случае, вместо QuickSort можно подставить кучу других алгоритмов посика,
> сортировки и т.п. Что, их всех в VM пихать?
Затем, что это конструкции разного уровня: алгоритм из ассемблерная инструкция. Можно ведь и в обратную сторону Ваш вопрос повернуть: зачем реализовывать на уровне процессора, например, арифметику с плавающей запятой, если компилятор прекрасно справляется?
Не обязательно. Но реализаций VM без SL я ещё не видел. :)
> В любом случае, вместо QuickSort можно подставить кучу других алгоритмов посика,
> сортировки и т.п. Что, их всех в VM пихать?
Затем, что это конструкции разного уровня: алгоритм из ассемблерная инструкция. Можно ведь и в обратную сторону Ваш вопрос повернуть: зачем реализовывать на уровне процессора, например, арифметику с плавающей запятой, если компилятор прекрасно справляется?
Поэтому, имхо, и надо разделять сферы влияния. Что-то реализует VM, что-то компилятор. Иначе какой смысл в компиляторе — можно руками писать в байт-код.
И осталось теперь обратить внимание на одну деталь: с течением времени самые часто-используемые техники реализуются на нижнем уровне, на уровне машинного кода, а в случае нашей дискуссии — на уровне байт-кода.
За счёт этого и компилятор упрощается.
За счёт этого и компилятор упрощается.
И возрастает сложность VM.
Компромисс, видимо, найден в том, что люди реализуют это в компиляторах, а не в VM.
Компромисс, видимо, найден в том, что люди реализуют это в компиляторах, а не в VM.
Сложность VM практически не возрастает, а сложность создания компилятора растет в разы. Просто создатели Java ступили при её создании. Ниже пример, который развернуть компилятор не может, но VM на раз плюнуть.
Если сложность перенести из компилятора в VM, то сложнее станет одна VM и проще — множество компиляторов. В случае .NET этих компиляторов уже несколько штук (F#, Nemerle, возможно, IronPython и IronRuby).
> Компромисс, видимо, найден в том, что люди реализуют это в компиляторах,
> а не в VM.
Ровно наоборот. С течением времени, набор команд даже железных процессоров растёт — в том числе для того, чтобы упростить и ускорить всё, что выше микропроцессора. Что уж тут говорить о VM?
> Компромисс, видимо, найден в том, что люди реализуют это в компиляторах,
> а не в VM.
Ровно наоборот. С течением времени, набор команд даже железных процессоров растёт — в том числе для того, чтобы упростить и ускорить всё, что выше микропроцессора. Что уж тут говорить о VM?
> Не обязательно. Но реализаций VM без SL я ещё не видел. :)
Знакомьтесь: LLVM.
Знакомьтесь: LLVM.
Экий Вы хитрый. :)
Там своей библиотеки нет, это верно. Но с VM идёт компилятор C/C++, в котором, естественно, есть стандартная библиотека.
Там своей библиотеки нет, это верно. Но с VM идёт компилятор C/C++, в котором, естественно, есть стандартная библиотека.
llvm-gcc и clang не «идут с LLVM». Это просто фронтенды, которые развиваются той же командой. Статический компилятор и JIT порождают из LLVM IR нативный код, который не зависит ни от какого рантайма. Точнее, только от того рантайма, который вы написали для своего языка или компилятора.
> Это просто фронтенды, которые развиваются той же командой.
Скажем так, у меня мнение на этот счёт несколько отличается. Тем более если речь идёт о той же команде.
> Статический компилятор и JIT порождают из LLVM IR нативный код, который не
> зависит ни от какого рантайма. Точнее, только от того рантайма, который вы
> написали для своего языка или компилятора.
Там есть рефлексия? Если есть, какими методами можно получить описание класса, например? Если нет, тогда всё понятно.
Скажем так, у меня мнение на этот счёт несколько отличается. Тем более если речь идёт о той же команде.
> Статический компилятор и JIT порождают из LLVM IR нативный код, который не
> зависит ни от какого рантайма. Точнее, только от того рантайма, который вы
> написали для своего языка или компилятора.
Там есть рефлексия? Если есть, какими методами можно получить описание класса, например? Если нет, тогда всё понятно.
Нет там рефлексии, и понятия классов вообще. Это Low Level Virtual Machine.
Почитайте публикацию Криса Латнера, ссылка на которую висит на главной странице. Introduction на одну страничку даёт ответы на большую часть вопросов. Посмотрите на набор инструкций. Представление не ориентировано на какую-то языковую парадигму, просто типизированная SSA-форма.
Почитайте публикацию Криса Латнера, ссылка на которую висит на главной странице. Introduction на одну страничку даёт ответы на большую часть вопросов. Посмотрите на набор инструкций. Представление не ориентировано на какую-то языковую парадигму, просто типизированная SSA-форма.
> Нет там рефлексии, и понятия классов вообще. Это Low Level Virtual Machine.
И всё-таки, Вы надо мной издеваетесь, признайтесь. :)
Я залез в набор инструкций и с удивлением обнаружил там, например, такую инструкцию, как malloc. На мой взгляд, это высокоуровневая инструкция, гораздо более высокоуровневая, чем tail call. Про GC я просто говорить не буду.
Как говорится, «и эти люди запрещают мне ковыряться в носу!» ;)
И всё-таки, Вы надо мной издеваетесь, признайтесь. :)
Я залез в набор инструкций и с удивлением обнаружил там, например, такую инструкцию, как malloc. На мой взгляд, это высокоуровневая инструкция, гораздо более высокоуровневая, чем tail call. Про GC я просто говорить не буду.
Как говорится, «и эти люди запрещают мне ковыряться в носу!» ;)
malloc там по историческим причинам. Крис Латтнер недавно признался, что можно бы и выкинуть уже.
GC в LLVM нет. Есть аннотации, которые позволяют прикрутить точный (в смысле, precise, а не conservative) GC. Никакой алгоритм не навязывается, как и сама необходимость сборки мусора. В этом вся философия LLVM: ничего не навязывать, предоставить платформу для реализации оптимизирующих компиляторов максимально широкого множества языков, пожертвовав высокоуровневыми абстракциями.
В общем, мне сложно назвать «стандартной библиотекой» скудный набор примитивов, которые практически всегда превращаются напрямую в инструкции целевой платформы, а не вызовы какого-то рантайма.
GC в LLVM нет. Есть аннотации, которые позволяют прикрутить точный (в смысле, precise, а не conservative) GC. Никакой алгоритм не навязывается, как и сама необходимость сборки мусора. В этом вся философия LLVM: ничего не навязывать, предоставить платформу для реализации оптимизирующих компиляторов максимально широкого множества языков, пожертвовав высокоуровневыми абстракциями.
В общем, мне сложно назвать «стандартной библиотекой» скудный набор примитивов, которые практически всегда превращаются напрямую в инструкции целевой платформы, а не вызовы какого-то рантайма.
Там есть tail call, из-за которого, собственно, весь сыр-бор. Ну, признайте уже, что инструкция полезная и нужная, и что Sun действительно отстаёт! :)
Теперь мой черёд спросить, не издеваетесь ли вы. Я слова не говорил про ненужность или наоборот, необходимость, инструкции tail call, равно как и преимущества и недостатки CLR по сравнению с JVM.
Замечу, однако, что сложно сравнивать наборы инструкций, предназначенные только для JIT-компиляции и интерпретации, с LLVM IR, над которым выполняются ещё и промежуточные трансформации.
Замечу, однако, что сложно сравнивать наборы инструкций, предназначенные только для JIT-компиляции и интерпретации, с LLVM IR, над которым выполняются ещё и промежуточные трансформации.
Ну, тут вся ветка обсуждения началась из-за того, что в CLR tail call есть, а в JVM её нет. Затем уже пошло — настолько ли она нужна, и на каком уровне нужно её реализовывать, на уровне компилятора, виртуальной машины, библиотеки, и т.д.
Наборы же инструкций сравнивать — наверное, можно, но смотря с какой целью. Скажем так, я не вижу принципиальной сложности трансформировать код на ilasm. Другое дело, что, насколько я понимаю, такая задача перед авторами CLR не стояла, и сейчас никто её не ставит.
А LLVM мне напомнила давнюю разработку, которая использовала похожие принципы, но на другом уровне. Речь идёт о компиляторах TopSpeed, которые переводили сначала код в промежуточный формат, которые уже оптимизировался и переводился в машинный код. Фишка была в том, что на всё семейство языков был один единственный, но очень мощный оптимизатор.
Наборы же инструкций сравнивать — наверное, можно, но смотря с какой целью. Скажем так, я не вижу принципиальной сложности трансформировать код на ilasm. Другое дело, что, насколько я понимаю, такая задача перед авторами CLR не стояла, и сейчас никто её не ставит.
А LLVM мне напомнила давнюю разработку, которая использовала похожие принципы, но на другом уровне. Речь идёт о компиляторах TopSpeed, которые переводили сначала код в промежуточный формат, которые уже оптимизировался и переводился в машинный код. Фишка была в том, что на всё семейство языков был один единственный, но очень мощный оптимизатор.
Речь идёт о компиляторах TopSpeed, которые переводили сначала код в промежуточный формат, которые уже оптимизировался и переводился в машинный код.
В GCC сейчас то же самое: независимые от языка оптимизации выполняются над промежуточным представлением GIMPLE.
Вообще, трудно представить, что разрабатывая семейство компиляторов, можно прийти к другой архитектуре :-)
> реализаций VM без SL я ещё не видел
LLVM?
LLVM?
А сможет компилятор соптимизировать хвостовой вызов функции, находящейся в другой библиотеке, и написанной на другом языке, который такую оптимизацию не поддерживает?
А что ему помешает? Хвостовая рекурсия — это замена CALL'а на JMP. Концептуально — штука простая: её даже gcc умеет делать:
$ cat Fibonacci.cОбратите внимание на вполне себе хвостовой вызов функции printf — она как раз находится в другой библиотеке написанной на языке о котором компилятор понятия не имеет (в реальности, конечно, всё равно на C — но этого не требуется).
#include <stdio.h>
int F2(int counter, int a, int b) {
if (counter == 0) return a;
return F2(counter - 1, b, (a + b)%100000);
}
int last5(int number) {
return F2(number, 1, 1);
}
int main(void) {
printf("%d\n",last5(1000));
}
$ gcc -O3 -S Fibonacci.c
$ cat Fibonacci.s
.file «Fibinacci.c»
.text
.p2align 4,,15
.globl F2
.type F2, @function
F2:
.LFB13:
testl %edi, %edi
movl %esi, %r9d
movl %edx, %r10d
je .L3
movl %edi, %r8d
subl $1, %r8d
je .L5
leal (%r10,%r9), %esi
movl $351843721, %edx
movl %esi, %eax
imull %edx
jmp .L26
.p2align 4,,7
.L28:
leal (%r10,%rsi), %edi
movl $351843721, %r11d
movl %edi, %eax
movl %edi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %edi
cmpl $2, %r8d
je .L12
leal (%rdi,%rsi), %esi
movl %esi, %eax
movl %esi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %esi
cmpl $3, %r8d
je .L14
leal (%rsi,%rdi), %edi
movl %edi, %eax
movl %edi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %edi
cmpl $4, %r8d
je .L16
leal (%rdi,%rsi), %esi
movl %esi, %eax
movl %esi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %esi
cmpl $5, %r8d
je .L18
leal (%rsi,%rdi), %edi
movl %edi, %eax
movl %edi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %edi
cmpl $6, %r8d
je .L20
leal (%rdi,%rsi), %esi
movl %esi, %eax
movl %esi, %ecx
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %esi
cmpl $7, %r8d
je .L22
leal (%rsi,%rdi), %edi
movl %edi, %eax
movl %edi, %ecx
movl %edi, %r9d
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %r9d
cmpl $8, %r8d
je .L3
leal (%r9,%rsi), %edi
movl %edi, %eax
movl %edi, %ecx
movl %edi, %r10d
imull %r11d
sarl $31, %ecx
sarl $13, %edx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %r10d
subl $9, %r8d
je .L5
leal (%r10,%r9), %esi
movl %esi, %eax
imull %r11d
.L26:
movl %esi, %ecx
sarl $13, %edx
sarl $31, %ecx
subl %ecx, %edx
imull $100000, %edx, %edx
subl %edx, %esi
cmpl $1, %r8d
jne .L28
.p2align 4,,7
.L10:
movl %esi, %r10d
.L5:
movl %r10d, %r9d
.L3:
movl %r9d, %eax
ret
.L22:
movl %esi, %edi
.L20:
movl %edi, %esi
.L18:
movl %esi, %edi
.L16:
movl %edi, %esi
.L14:
movl %esi, %edi
.L12:
movl %edi, %esi
jmp .L10
.LFE13:
.size F2, .-F2
.section .rodata.str1.1,«aMS»,@progbits,1
.LC0:
.string "%d\n"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB15:
subq $8, %rsp
.LCFI0:
movl $1, %esi
movl $1000, %edi
movl $1, %edx
call F2
movl $.LC0, %edi
movl %eax, %esi
addq $8, %rsp
xorl %eax, %eax
jmp printf
.LFE15:
.size main, .-main
.p2align 4,,15
.globl last5
.type last5, @function
last5:
.LFB14:
testl %edi, %edi
jne .L37
movl $1, %eax
ret
.p2align 4,,7
.L37:
subl $1, %edi
movl $2, %edx
movl $1, %esi
jmp F2
.LFE14:
.size last5, .-last5
.section .eh_frame,«a»,@progbits
.Lframe1:
.long .LECIE1-.LSCIE1
.LSCIE1:
.long 0x0
.byte 0x1
.string «zR»
.uleb128 0x1
.sleb128 -8
.byte 0x10
.uleb128 0x1
.byte 0x3
.byte 0xc
.uleb128 0x7
.uleb128 0x8
.byte 0x90
.uleb128 0x1
.align 8
.LECIE1:
.LSFDE1:
.long .LEFDE1-.LASFDE1
.LASFDE1:
.long .LASFDE1-.Lframe1
.long .LFB13
.long .LFE13-.LFB13
.uleb128 0x0
.align 8
.LEFDE1:
.LSFDE3:
.long .LEFDE3-.LASFDE3
.LASFDE3:
.long .LASFDE3-.Lframe1
.long .LFB15
.long .LFE15-.LFB15
.uleb128 0x0
.byte 0x4
.long .LCFI0-.LFB15
.byte 0xe
.uleb128 0x10
.align 8
.LEFDE3:
.LSFDE5:
.long .LEFDE5-.LASFDE5
.LASFDE5:
.long .LASFDE5-.Lframe1
.long .LFB14
.long .LFE14-.LFB14
.uleb128 0x0
.align 8
.LEFDE5:
.ident «GCC: (GNU) 4.2.4 (Ubuntu 4.2.4-1ubuntu3)»
.section .note.GNU-stack,"",@progbits
Если я правильно понял, поддержка заключается в том, что используется сокращённый вариант вызова. Вместо CALL, по сути, используется обычный GOTO. Таким образом, если компилятор обнаруживает хвостовую рекурсию, он использует готовую инструкцию, а не занимается переводом в цикл самостоятельно.
Проздравляю вас: именно так ведёт себя KAWA с JVM, GCC с кучей реальных процессоров и т.д. Спрашивается: зачем особая конструкция в .Net?
Затем, вероятно, что KAWA с JVM ведёт себя не именно так.
Именно так. Правда это не умолчальный режим ибо некоторые tools'ы (не JVM — c JVM проблем нету: всякие отладчики, профайлеры, etc.) от такого дуреют. Ну так ежели в C# этого нет — эта проблема и в .Net будет.
Проблема в том, что пример, приведенный в статье компилятор развернет в цикл, но следующий уже не сможет:
class A
{
public virtual int Foo(int a)
{
return Bar(a-1);
}
public virtual int Bar(int a)
{
if (a<0) return a;
return Foo(a-1);
}
}
так другой класс, например B, может наследовать A и перегрузить метод Foo. Если хвостовую рекурсию поддерживает VM, а не компилятор, то такой пробелы не возникает.
class A
{
public virtual int Foo(int a)
{
return Bar(a-1);
}
public virtual int Bar(int a)
{
if (a<0) return a;
return Foo(a-1);
}
}
так другой класс, например B, может наследовать A и перегрузить метод Foo. Если хвостовую рекурсию поддерживает VM, а не компилятор, то такой пробелы не возникает.
Совершенно верно: в этом случае нельзя развернуть вызов в цикл. Но можно скомпилировать код так что рекурсия будет хвостовой. KAWA ровно это и делает. Без всякой поддежки со стороны VM. Спрашивается: зачем нужна особая конструкция в .Net?
Я не верю. Каким образом? Если и можно, то скорее всего ломается прозрачное взаимодействие с Java кодом, что-нибудь типа интерпретатора схемы на Java.
Придумал как код выше можно оптимизировать компилятором:
class A
{
private int OptimizedFoo(int a) {… }
private int OptimizedBar(int a) {… }
public virtual int Foo(int a)
{
if (this.GetType()==typeof(A)) return OptimizedFoo(a);
return Bar(a-1);
}
public virtual int Bar(int a)
{
if (a<0) return a;
if (this.GetType()==typeof(A)) return OptimizedBar(a);
return Foo(a-1);
}
}
Правда если функция Foo или Bar определены в сборке, доступ к кодам которой нету, то компилятор не сможет произвести оптимизацию, а .NET сможет.
{
private int OptimizedFoo(int a) {… }
private int OptimizedBar(int a) {… }
public virtual int Foo(int a)
{
if (this.GetType()==typeof(A)) return OptimizedFoo(a);
return Bar(a-1);
}
public virtual int Bar(int a)
{
if (a<0) return a;
if (this.GetType()==typeof(A)) return OptimizedBar(a);
return Foo(a-1);
}
}
Правда если функция Foo или Bar определены в сборке, доступ к кодам которой нету, то компилятор не сможет произвести оптимизацию, а .NET сможет.
Спасибо, интересная статья.
Лично сам Haskell таки изучаю, наравне с F#. Практика практикой, а упражнения для головы тоже не помешают. :)
Лично сам Haskell таки изучаю, наравне с F#. Практика практикой, а упражнения для головы тоже не помешают. :)
Я думал на Haskell посмотреть, но потом забил. Уж очень он строгий, а я не вижу причин, которые сейчас эту строгость оправдывают. Если она даст реальные преимущества, то перейду на нем. Реально преимущество это как в старой рекламе: пока жители Вилларибо мучаются с мьютексами в Java, жители Виллабаджо пожимают плоды автоматического распараллеливания программы на языке haskell на intel core i7 (cell или что там еще есть).
Выбирая из F# и Nemerle, нашел плюс у F# только в том, что можно будет использовать наследие кода на OCaml, но так как с OCaml я не сталкивался выбрал Nemerle, у которого синтаксис более человечный и есть поддержка умных макросов.
Выбирая из F# и Nemerle, нашел плюс у F# только в том, что можно будет использовать наследие кода на OCaml, но так как с OCaml я не сталкивался выбрал Nemerle, у которого синтаксис более человечный и есть поддержка умных макросов.
> Я думал на Haskell посмотреть, но потом забил. Уж очень он строгий, а я не вижу причин, которые сейчас эту строгость оправдывают.
У хаскелоидов есть очень весомые аргументы, касающиеся практически любого решения в языке.
IO там тоже неспроста так отделено от всего остального.
> Реально преимущество это как в старой рекламе: пока жители Вилларибо мучаются с мьютексами в Java, жители Виллабаджо пожимают плоды автоматического распараллеливания программы на языке haskell на intel core i7 (cell или что там еще есть).
STM видывали когда-нибудь? Это, конечно, еще не автоматическое распараллеливание, но тоже очень неплохо. Еще надо заметить, что программы на Хаскеле по-умолчанию потокобезопасны, в то время как в нечистых языках все наоборот.
У хаскелоидов есть очень весомые аргументы, касающиеся практически любого решения в языке.
IO там тоже неспроста так отделено от всего остального.
> Реально преимущество это как в старой рекламе: пока жители Вилларибо мучаются с мьютексами в Java, жители Виллабаджо пожимают плоды автоматического распараллеливания программы на языке haskell на intel core i7 (cell или что там еще есть).
STM видывали когда-нибудь? Это, конечно, еще не автоматическое распараллеливание, но тоже очень неплохо. Еще надо заметить, что программы на Хаскеле по-умолчанию потокобезопасны, в то время как в нечистых языках все наоборот.
Ну, после прочтения статей, я тоже Nemerle буду изучать. В конечном итоге, много не мало. По поводу F# есть подозрение, что он станет официальным функциональным языком от Microsoft. Сейчас изучим, года через 3 будем модными востребованными специалистами. :)
У меня такое было с C++, который изучать я начал в 93-м, и мне знакомые говорили — на хрена он тебе нужен, он же медленней Си, никогда он не будет востребованным. А в 98-м во время кризиса на работу взяли безо всяких вопросов. :)
У меня такое было с C++, который изучать я начал в 93-м, и мне знакомые говорили — на хрена он тебе нужен, он же медленней Си, никогда он не будет востребованным. А в 98-м во время кризиса на работу взяли безо всяких вопросов. :)
Хотелjсь бы увидеть результаты теста F#.
Я F# не умею. Напишите код — я его исполню на той же машине, что и все остальные тесты.
Вот обычная рекурсия:
Вот хвостовая (по Вашему исходнику писал):
По ощущениям — компилятор F# хвостовую рекурсию понимает и разворачивает, вторая функция считает значительно быстрее первой.
let rec fib_mod10 n = match n with
| 1 -> 1
| 2 -> 2
| _ -> fib_mod10 (n - 1) + fib_mod10 (n - 2)
Вот хвостовая (по Вашему исходнику писал):
let rec fib_helper counter a b = if counter = 0
then a
else fib_helper (counter - 1) b ((a + b)%100000)
let fib_mod10_2 n = fib_helper n 1 1
По ощущениям — компилятор F# хвостовую рекурсию понимает и разворачивает, вторая функция считает значительно быстрее первой.
Интересно, а сколько реальных задач (именно в веб-программировании), требующих таких глубоких рекурсий, чтобы программа падала из-за переполнения стека?
А нельзя ли проверить сколько «милисекондов» будет, если так:
?
public class FibonacciArrayOptimized2
{
static public int Last5(int number)
{
int a, b, c;
a = 1;
b = 1;
c = 2;
number -= 2;
while (number > 0)
{
a = (b + c) % 100000;
number--;
if (number == 0)
{
return a;
}
b = (a + c) % 100000;
number--;
if (number == 0)
{
return b;
}
c = (a + b) % 100000;
number--;
}
return c;
}
}
* This source code was highlighted with Source Code Highlighter.?
Я тестировал похожий код — результат в конце статьи
static public int Last5(int number)
{
int a = 1;
int b = 1;
int c;
while (number > 0)
{
c = b;
b = (a + b) % 100000;
a = c;
number--;
}
return a;
}
* This source code was highlighted with Source Code Highlighter.
Ну, если уж оптимизировать алгоритм, то можно сделать намного эффективнее. Например быстрым возведением матрицы 2х2 в степень.
Этот метод ищет 5 последних цифр 10^18 числа Фибоначи быстрее, чем любой из тестированных вариантов для 100000.
В топике идет сравнение рекурсии и циклов, а не самых алгоритмов.
class FibonacciCalc
{
static private long[,] tempMatrix = new long[2, 2]{{0, 0},
{0, 0}};
// matr1 = matr1 * matr2
static private void matrixMult(long [,] matr1, long [,] matr2)
{
int i, j, k;
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
{
tempMatrix[i,j] = 0;
for (k = 0; k < 2; k++)
tempMatrix[i,j] += matr1[i,k] * matr2[k,j];
}
for (i = 0; i < 2; i++)
for (j = 0; j < 2; j++)
matr1[i,j] = tempMatrix[i,j] % 100000;
}
static public int Last5(long number)
{
long[,] pow2Matrix = new long[2, 2]{{1, 1},
{1, 0}};
long[,] multMatrix = new long[2, 2]{{1, 0},
{0, 1}};
while (number > 0)
{
if (number % 2 == 1)
{ // multMatrix = multMatrix * pow2Matrix
matrixMult(multMatrix, pow2Matrix);
}
{ // pow2Matrix = pow2Matrix * pow2Matrix
matrixMult(pow2Matrix, pow2Matrix);
}
number = number / 2;
}
return (int)multMatrix[0,0];
}
}
}
* This source code was highlighted with Source Code Highlighter.Этот метод ищет 5 последних цифр 10^18 числа Фибоначи быстрее, чем любой из тестированных вариантов для 100000.
В топике идет сравнение рекурсии и циклов, а не самых алгоритмов.
Вот так вот мы с комрадом shai_xylyd'ом сначала теоретицки, а потом и практицки опровергли миф о тормознутости рекурсии.
Благодарю всех участников эксперимента. Вы свободны, передавайте это сакральное знание другим программистам.
Нет пути мифам!
Благодарю всех участников эксперимента. Вы свободны, передавайте это сакральное знание другим программистам.
Нет пути мифам!
Думаю, что еще много чего можно написать о ФП. Я только начал его касаться.
Я давно уже пишу здесь на хабре, что архиватор freearc работает быстрее 7zip. При этом 7zip написан на C++/C, а freearc на haskell/C. Булат, автор freearc, утверждает, что скорость программирования больше на порядок.
Единственное, чего пока не хватает ф/я, это развитых фреймворков. Скажем, пока написать Windows-style application на haskell нереально, по крайней мере, с использованием всех возможностей висты.
Но вот в Nemerle/F# эта проблематика уже снята, что очень радует.
Единственное, чего пока не хватает ф/я, это развитых фреймворков. Скажем, пока написать Windows-style application на haskell нереально, по крайней мере, с использованием всех возможностей висты.
Но вот в Nemerle/F# эта проблематика уже снята, что очень радует.
> Булат, автор freearc, утверждает, что скорость программирования больше на порядок.
Bulat Ziganshin? Он часто на Haskell-Cafe пишет. И я дваждую его слова.
> Единственное, чего пока не хватает ф/я, это развитых фреймворков.
В этом как раз и заключается фишка. Фреймворки не нужны! Нужны способы создавать абстракции с четкой семантикой и возможностью их композиции — а вот это как раз и реализуется гораздо проще в ФП, чем в обычном ООП.
> Скажем, пока написать Windows-style application на haskell нереально, по крайней мере, с использованием всех возможностей висты.
Хаскелоиды не любят Windows (большая их часть). Во всяком случае, с GHC на Windows придется сильно попариться (а потом и с Cabal, etc).
Bulat Ziganshin? Он часто на Haskell-Cafe пишет. И я дваждую его слова.
> Единственное, чего пока не хватает ф/я, это развитых фреймворков.
В этом как раз и заключается фишка. Фреймворки не нужны! Нужны способы создавать абстракции с четкой семантикой и возможностью их композиции — а вот это как раз и реализуется гораздо проще в ФП, чем в обычном ООП.
> Скажем, пока написать Windows-style application на haskell нереально, по крайней мере, с использованием всех возможностей висты.
Хаскелоиды не любят Windows (большая их часть). Во всяком случае, с GHC на Windows придется сильно попариться (а потом и с Cabal, etc).
> Bulat Ziganshin?
Он самый.
> В этом как раз и заключается фишка. Фреймворки не нужны! Нужны способы создавать абстракции с
> четкой семантикой и возможностью их композиции — а вот это как раз и реализуется гораздо
> проще в ФП, чем в обычном ООП.
Вот тут бы я подискутировал. :) Речь идёт даже не о красивой обёртке, а о функциональности, которую приходится всё время дублировать. Скажем, при разработке веб-приложения не хочется очередной раз писать поддержку структуры сайта, или методы url_encode, url_decode или работу с базами данных.
Почему, например, .NET так понравился после PHP? Бог с ним, с языком, с человеческой инкапсуляцией, с внятной модульной системой. Самое главное — оказалось, что не надо заново писать велосипеды в большом количестве, можно сконцентрироваться сразу на высокоуровневых задачах.
> Хаскелоиды не любят Windows (большая их часть).
Тот же Булат прекрасно понимает, что как бы ни был быстр freearc, он не станет популярным без внятного виндового интерфейса. Так вот пока, к сожалению, интерфейс приходиться писать на C++ или C#. Так что с моей личной точки зрения, любовь/нелюбовь — чуждая категория. Элитность не способствует распространению идей, а способствует, наоборот, доступность.
Помню, Руби я изучал так — взял реальную задачу, где надо было из Active Directory вытащить пользователей, что-то там с ними сделать и записать обратно. Руби прекрасно справился. Чем тут же и понравился — нормальный, рабочий инструмент.
Он самый.
> В этом как раз и заключается фишка. Фреймворки не нужны! Нужны способы создавать абстракции с
> четкой семантикой и возможностью их композиции — а вот это как раз и реализуется гораздо
> проще в ФП, чем в обычном ООП.
Вот тут бы я подискутировал. :) Речь идёт даже не о красивой обёртке, а о функциональности, которую приходится всё время дублировать. Скажем, при разработке веб-приложения не хочется очередной раз писать поддержку структуры сайта, или методы url_encode, url_decode или работу с базами данных.
Почему, например, .NET так понравился после PHP? Бог с ним, с языком, с человеческой инкапсуляцией, с внятной модульной системой. Самое главное — оказалось, что не надо заново писать велосипеды в большом количестве, можно сконцентрироваться сразу на высокоуровневых задачах.
> Хаскелоиды не любят Windows (большая их часть).
Тот же Булат прекрасно понимает, что как бы ни был быстр freearc, он не станет популярным без внятного виндового интерфейса. Так вот пока, к сожалению, интерфейс приходиться писать на C++ или C#. Так что с моей личной точки зрения, любовь/нелюбовь — чуждая категория. Элитность не способствует распространению идей, а способствует, наоборот, доступность.
Помню, Руби я изучал так — взял реальную задачу, где надо было из Active Directory вытащить пользователей, что-то там с ними сделать и записать обратно. Руби прекрасно справился. Чем тут же и понравился — нормальный, рабочий инструмент.
> Скажем, при разработке веб-приложения не хочется очередной раз писать поддержку структуры сайта, или методы url_encode, url_decode или работу с базами данных.
Наверное, я неправильно выразился. Просто те же url_encode/url_decode можно выразить с помощью комбинирования других функций, при этом собсно практически не вводится лишний код, иногда это просто несколько аппликаций функций, и больше ничего. :)
> Тот же Булат прекрасно понимает, что как бы ни был быстр freearc, он не станет популярным без внятного виндового интерфейса.
Вроде бы во FreeArc используется wxHaskell или Gtk2Hs, ну а виндовую версию собрать проблематично из-за того, что подавляющее количество разработчиков пользуется линуксом. Не знаю, есть ли здесь элитность, или это просто преобладающее мнение в их сообществе.
Наверное, я неправильно выразился. Просто те же url_encode/url_decode можно выразить с помощью комбинирования других функций, при этом собсно практически не вводится лишний код, иногда это просто несколько аппликаций функций, и больше ничего. :)
> Тот же Булат прекрасно понимает, что как бы ни был быстр freearc, он не станет популярным без внятного виндового интерфейса.
Вроде бы во FreeArc используется wxHaskell или Gtk2Hs, ну а виндовую версию собрать проблематично из-за того, что подавляющее количество разработчиков пользуется линуксом. Не знаю, есть ли здесь элитность, или это просто преобладающее мнение в их сообществе.
> Просто те же url_encode/url_decode можно выразить с помощью комбинирования других
> функций, при этом собсно практически не вводится лишний код, иногда это просто несколько
> аппликаций функций, и больше ничего. :)
Эти, пожалуй, да, несложно и самому написать. Но вот со структурой сайта уже сложнее. В .NET с этим всё уже продумано и реализовано — есть SiteMapProvider, абстрактный класс. Он представляет сайт просто как дерево страниц без подробностей, откуда оно берётся. Есть конкретная реализация, где страницы описываются в XML-файле. Всё это расширямо — можно сделать хранение в любом формате или в БД. Есть контролы, которые умеют показывать дерево сайта, или хлебные крошки, или ещё что-то, пользуясь методами SiteMapProvider.
И всё это вместе оказывается очень удобным. Нужен мне свой контрол — я его пишу, и он будет работать с любым провайдером, пусть даже самописным. Нужен свой провайдер (страницы лежат в БД) — наследую SiteMapProvider и все контролы, даже самописные, будут прекрасно с ним работать. Ничего не нужно — беру стандартную реализацию и трачу время только на то, чтобы описать структуру сайта в XML-формате.
И вот, скажем, для F# и Nemerle всё это богатство уже доступно. Я могу заниматься действительно важными вещами, а остальное пусть делает фреймворк.
> Вроде бы во FreeArc используется wxHaskell или Gtk2Hs, ну а виндовую версию собрать
> проблематично из-за того, что подавляющее количество разработчиков пользуется
> линуксом.
Есть она, эта версия, просто страшная и не Windows-style. Нормальные пользователи не клюнут. Потому и пришлось мне окошки для SFX-модуля писать на C++ на чистом Windows API. Теперь хоть SFX-модули freearc выглядят как родные виндовые приложения.
Ну и видимо, придётся Windows-версию архиватора писать на C#, чтобы выглядела она нормально и интегрировалась с Проводником, как это в виндах принято. А вот когда будет Haskell под .NET, тогда будем работать напрямую. :)
> функций, при этом собсно практически не вводится лишний код, иногда это просто несколько
> аппликаций функций, и больше ничего. :)
Эти, пожалуй, да, несложно и самому написать. Но вот со структурой сайта уже сложнее. В .NET с этим всё уже продумано и реализовано — есть SiteMapProvider, абстрактный класс. Он представляет сайт просто как дерево страниц без подробностей, откуда оно берётся. Есть конкретная реализация, где страницы описываются в XML-файле. Всё это расширямо — можно сделать хранение в любом формате или в БД. Есть контролы, которые умеют показывать дерево сайта, или хлебные крошки, или ещё что-то, пользуясь методами SiteMapProvider.
И всё это вместе оказывается очень удобным. Нужен мне свой контрол — я его пишу, и он будет работать с любым провайдером, пусть даже самописным. Нужен свой провайдер (страницы лежат в БД) — наследую SiteMapProvider и все контролы, даже самописные, будут прекрасно с ним работать. Ничего не нужно — беру стандартную реализацию и трачу время только на то, чтобы описать структуру сайта в XML-формате.
И вот, скажем, для F# и Nemerle всё это богатство уже доступно. Я могу заниматься действительно важными вещами, а остальное пусть делает фреймворк.
> Вроде бы во FreeArc используется wxHaskell или Gtk2Hs, ну а виндовую версию собрать
> проблематично из-за того, что подавляющее количество разработчиков пользуется
> линуксом.
Есть она, эта версия, просто страшная и не Windows-style. Нормальные пользователи не клюнут. Потому и пришлось мне окошки для SFX-модуля писать на C++ на чистом Windows API. Теперь хоть SFX-модули freearc выглядят как родные виндовые приложения.
Ну и видимо, придётся Windows-версию архиватора писать на C#, чтобы выглядела она нормально и интегрировалась с Проводником, как это в виндах принято. А вот когда будет Haskell под .NET, тогда будем работать напрямую. :)
> В .NET с этим всё уже продумано и реализовано — есть SiteMapProvider, абстрактный класс.
У меня аллергия на слова «абстрактный класс». :) Вот серьезно, так и не нашел применения ООП в стиле Simula.
> Он представляет сайт просто как дерево страниц без подробностей, откуда оно берётся. Есть конкретная реализация, где страницы описываются в XML-файле.
Ну, тут еще надо подумать, как лучше будет представить сайт. Можно ведь отталкиваться от функции URI -> HTML.
> Всё это расширямо — можно сделать хранение в любом формате или в БД. Есть контролы, которые умеют показывать дерево сайта, или хлебные крошки, или ещё что-то, пользуясь методами SiteMapProvider.
Хлебные крошки можно реализовать довольно просто: с помощью zipper'а (это такая структура данных, которая представляет собой «курсор» для другой структуры данных). Причем, заметь, что знать о методах SiteMapProvider даже не совсем нужно. :)
> Потому и пришлось мне окошки для SFX-модуля писать на C++ на чистом Windows API. Теперь хоть SFX-модули freearc выглядят как родные виндовые приложения.
Клево, респект!
> А вот когда будет Haskell под .NET, тогда будем работать напрямую. :)
Вроде уже есть мост: Salsa, что ли. Я не сильно этим интересовался.
У меня аллергия на слова «абстрактный класс». :) Вот серьезно, так и не нашел применения ООП в стиле Simula.
> Он представляет сайт просто как дерево страниц без подробностей, откуда оно берётся. Есть конкретная реализация, где страницы описываются в XML-файле.
Ну, тут еще надо подумать, как лучше будет представить сайт. Можно ведь отталкиваться от функции URI -> HTML.
> Всё это расширямо — можно сделать хранение в любом формате или в БД. Есть контролы, которые умеют показывать дерево сайта, или хлебные крошки, или ещё что-то, пользуясь методами SiteMapProvider.
Хлебные крошки можно реализовать довольно просто: с помощью zipper'а (это такая структура данных, которая представляет собой «курсор» для другой структуры данных). Причем, заметь, что знать о методах SiteMapProvider даже не совсем нужно. :)
> Потому и пришлось мне окошки для SFX-модуля писать на C++ на чистом Windows API. Теперь хоть SFX-модули freearc выглядят как родные виндовые приложения.
Клево, респект!
> А вот когда будет Haskell под .NET, тогда будем работать напрямую. :)
Вроде уже есть мост: Salsa, что ли. Я не сильно этим интересовался.
> У меня аллергия на слова «абстрактный класс». :) Вот серьезно, так и не нашел
> применения ООП в стиле Simula.
Пусть будет интерфейс, чем он, по сути, и является. :) Абстрактный класс там появился, если я ничего не путаю, просто потому, что нужны были статические методы, ну, их там же и разместили.
> Ну, тут еще надо подумать, как лучше будет представить сайт. Можно ведь
> отталкиваться от функции URI -> HTML.
Чем метод хорош — расширяемый. Можно как угодно сделать, можно даже смешивать — скажем, часть страниц брать из XML, а часть (новости за последние 10 лет, которых 10 тысяч) — из БД. На то он и фреймворк. :)
> Причем, заметь, что знать о методах SiteMapProvider даже не совсем нужно. :)
Тут фишка в том, что это контрол. Если Delphi видел, то вот такая вот удобная штука. И работать будет с любой реализацией провайдера и с их смесью.
И если всё это совместить, мощность ФП и мощность фреймворков, уровень решаемых задач сразу поднимается. Не надо парсить query string (пусть несложно это, но не нужно). С другой стороны — насколько декларативность возрастает.
> Вроде уже есть мост: Salsa, что ли. Я не сильно этим интересовался.
Я пока тоже. Мучаю в основном ghc, иногда winhug, но так, очень слабо пока. Не хватает же времени сразу на всё. :)
> применения ООП в стиле Simula.
Пусть будет интерфейс, чем он, по сути, и является. :) Абстрактный класс там появился, если я ничего не путаю, просто потому, что нужны были статические методы, ну, их там же и разместили.
> Ну, тут еще надо подумать, как лучше будет представить сайт. Можно ведь
> отталкиваться от функции URI -> HTML.
Чем метод хорош — расширяемый. Можно как угодно сделать, можно даже смешивать — скажем, часть страниц брать из XML, а часть (новости за последние 10 лет, которых 10 тысяч) — из БД. На то он и фреймворк. :)
> Причем, заметь, что знать о методах SiteMapProvider даже не совсем нужно. :)
Тут фишка в том, что это контрол. Если Delphi видел, то вот такая вот удобная штука. И работать будет с любой реализацией провайдера и с их смесью.
И если всё это совместить, мощность ФП и мощность фреймворков, уровень решаемых задач сразу поднимается. Не надо парсить query string (пусть несложно это, но не нужно). С другой стороны — насколько декларативность возрастает.
> Вроде уже есть мост: Salsa, что ли. Я не сильно этим интересовался.
Я пока тоже. Мучаю в основном ghc, иногда winhug, но так, очень слабо пока. Не хватает же времени сразу на всё. :)
> Чем метод хорош — расширяемый. Можно как угодно сделать, можно даже смешивать — скажем, часть страниц брать из XML, а часть (новости за последние 10 лет, которых 10 тысяч) — из БД. На то он и фреймворк. :)
Ну так это, берем, значиццо, один iteratee, и подставляем его во сколько угодно enumerator'ов, комбинируя по ходу дела… ^_^
> И работать будет с любой реализацией провайдера и с их смесью.
Сомневаюсь, ибо побочные эффекты не располагают к plug'n
'play-коду.
> И если всё это совместить, мощность ФП и мощность фреймворков, уровень решаемых задач сразу поднимается.
В принципе, подойдет для плана минимум (мощный вин над обычным C#/Java). :) А план максимум потребует жесткого разделения чистых и нечистых функций, как это сделано в Хаскеле.
Ну так это, берем, значиццо, один iteratee, и подставляем его во сколько угодно enumerator'ов, комбинируя по ходу дела… ^_^
> И работать будет с любой реализацией провайдера и с их смесью.
Сомневаюсь, ибо побочные эффекты не располагают к plug'n
'play-коду.
> И если всё это совместить, мощность ФП и мощность фреймворков, уровень решаемых задач сразу поднимается.
В принципе, подойдет для плана минимум (мощный вин над обычным C#/Java). :) А план максимум потребует жесткого разделения чистых и нечистых функций, как это сделано в Хаскеле.
Слов нема… Вот смотрю я на всё это и думаю. Какой же я баран был, что в универе «забивал» на вышку, не на всё забивал, но на часть. Смотрю тут на формулки, как баран на новые ворота. Поеду завтра книжку покупать и знания подтягивать, а то стыдно аж стало :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизация хвостовой рекурсии в .NET и Nemerle