Clojure 1.2

> нет, в ФЯ полного копирования не происходит - новые структуры эффективно используют предыдущие данные. Это только в С++ для гарантии неизменяемости надо скопировать весь объект

В случае к примеру добавления элемента к списку вы правы. Но есть варианты, когда происходит копирование, например склейка 2-х списков.

> Превратился ли Оракл в обезьяну с гранатой, с которой лучше не связываться? Почему ушёл Гослинг?

Кто убил Кеннеди? Почему затонул Курск? Когда повысят пенсию?

Эти и многие другие вопросы в передаче «Очевидное невероятное».

JVM слишком поздно очнулась, всё уже схавал .NET; Я даже на Дельфи готов поставить больше, чем на Жабо.

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

нет

Одна из необходимых вещей для немутабельных структур - хвосторекурсивная оптимизация. Нихрена это не удобнее строить их там где ее нет.

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

> Такие вещи, как графические и звуковые редакторы, игры и многое др. являются мутабельными по определению.

Там до черта подзадач, где можно с выгодой использовать немутабельность. Нет противоречия между немутабельностью и необходимостью произвести побочный эффект. Эти эффекты можно выразить и немутабельными данными в том числе. Здесь самое сложное - понять эту простую вещь ;)

>> нет, в ФЯ полного копирования не происходит - новые структуры эффективно используют предыдущие данные. Это только в С++ для гарантии неизменяемости надо скопировать весь объект

Ога. Покажи как с таким типом data Tree a = Node a (Tree a) (Tree a) | Empty эффективно использовать предыдущие куски дерева при вставке нового элемента.

> новые структуры эффективно используют предыдущие данные.

наверное поэтому программы на CL едят столько памяти

Это только в С++ для гарантии неизменяемости надо скопировать весь объект

толсто, в С++ сам решаешь где использовать COW( в том числе во вложенных структурах ), а где нет, в этом и есть принцип, что если ты не используешь «эффективные» фичи, то они не будут тормозить работу

В случае с ерлангом у вас етсь готовый механизм. В случае я явой его надо еще реализовать.

Насколько могу судить, в Скале (JVM) есть похожий механизм актеров (акторов). В F# (.NET) его близкий аналог - MailboxProcessor вместе с async workflow.

f# вообще годный.

> Но есть варианты, когда происходит копирование, например склейка 2-х списков.

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

>> новые структуры эффективно используют предыдущие данные.

наверное поэтому программы на CL едят столько памяти

С каких пор CL стал функциональным?

> С каких пор CL стал функциональным?

а вы таки можете привести пример чистого функционального языка?

>Такие вещи, как графические и звуковые редакторы, игры и многое др. являются мутабельными по определению.

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

И распаралелить там есть что.

Там все четко сегментируется. Нет конкурентного доступа.

>А сможет ли подобный подход сработать в случае, к примеру, файла, в который пишут/читают разные потоки?

А что в этом случае должно представляться немутабельным - файл чтоле?

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

Вы имеете в виду что-то типа генератора?

> Ога. Покажи как с таким типом data Tree a = Node a (Tree a) (Tree a) | Empty эффективно использовать предыдущие куски дерева при вставке нового элемента.

А зиппер для дерева слабо определить?

> Но есть варианты, когда происходит копирование, например склейка 2-х списков.

При склейке двух списков копируются не все данные. Часть их шарится.

> как с таким типом data Tree a = Node a (Tree a) (Tree a) | Empty эффективно использовать предыдущие куски дерева при вставке нового элемента.

Если дерево сбалансировано, то нужно создать примерно O(log2 n) элементов. Вот и считай. На миллион элементов где-то 20*C новых элементов, где C зависит от типа дерева (AVL, черно-белые и т.п.). Зато имеем многоверсионность, потоко-безопасность и прочие прелести функциональных структур данных. А все стандартные Map и Set используют именно сбалансированные деревья.

Я бы тебя понял, если бы ты нападал на хеш-таблицы или двусвязные списки. Вот там монада IO.

>Производительность за счет in-place изменений данных.

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

О таких ситуация и как их разруливать написано в каждом первом учебнике по Java, это не бог весть какая сложность.

Ага. Collections.unmodifiedList или list.clone().

Что ты там говорил про память и производительность?

При чем здесь ленивость?

При том что в случае немутабельных структур данных становиться очевидным и безопасным решением, берегущим процессор и память автоматически, не писать фильтр списка путем отбора элементов в другой список - а созданием проекции списка. А в мутабельных структурах обычно (for x in) и понеслось условное копирование.

Элементарный пример вставки элемента в дерево приводит к его полному копированию.

От дерева зависит это раз. Зато исследовние структур никогда не приводит к копированию. В отличии от.

> Вы имеете в виду что-то типа генератора?

Я не знаю, как это называется. Тип ShowS определен так:

type ShowS = String -> String

Когда мы склеиваем два списка, то мы возвращаем функцию типа ShowS, которой потом передаем на вход пустой список []. Смысл в том, что левую часть склейки нужно копировать только единожды в тот самый момент, когда понадобился результат. Даже если склеек много в одной цепочке, то копирование все равно происходит только один раз.

Google так и сделал. Помогло им это?

Видать они лицензирование не проходили, да и не jvm у них.

Ничего-ничего, суд разберётся что там у них.

Так проблема вообще не в jvm же, а в нарушение патентов. Сам подумай, если пройти лицензирование jvm у Оракла, будет ли Оракл подавать в суд?

>>>> новые структуры эффективно используют предыдущие данные.

наверное поэтому программы на CL едят столько памяти

С каких пор CL стал функциональным?

а вы таки можете привести пример чистого функционального языка?

Нет, но какое это ввобще имеет отношение к теме? Программы на Java тоже жрут память потому что новые структуры после вызова clone() «используют» предыдущие данные? Нет, в Java, как и CL и С++, это невозможно из-за выбранных создателями решений в дизайне языка.

Это можно реализовать самому много на чем. Какая-то реализация есть даже в Emacs Lisp «из коробки», называется bindat. Я сейчас этот bindat использую для одной идейки. Можно по спеку распаковывать и запаковывать бинарные данные. Так как Emacs Lisp — это средство весьма узкоспециализированное и ограниченное, то привел просто как пример. Как альтернативу твоему инструменту рассматривать не предлагаю. Скорее всего, подобное есть и для других языков. Google в руки.

>> От дерева зависит это раз. Зато исследовние структур никогда не приводит к копированию. В отличии от.

Поподробнее можно как оно зависит от деоева и про то, что исследование структуры приводит к копированию в том самом «отличии от». На примере бинарного дерева можно?

А в мутабельных структурах обычно (for x in) и понеслось условное копирование.

Ну я не спорю, только я не о том, что «понеслась», а том, что некоторые сдвинулись на ФЯ настолько, что STM это, чиста, фича ФЯ, что в С++, Java или, там, Lisp нет и не может быть STM (хотя именно на примере Лиспа оно и появилось), и что только благодаря диктатуре немутабельности в некторых язычках STM возможен только в них и ни где больше.

С чего ты взял что там есть производительность?

А с чего ты взял что ее там нет? Возьми любимый функциональщиками ряд Фибоначчи и посчитай триллионный элемент на Хаскеле. Слабо дистигнуть Си-шной производительности без unsafe-функций? А мьютексы и проч., ну я тебе уже написал про STM.

но касательно оптимизации хвостовой рекурсии в C++ читать здесь

Разворачивание простой рекурсии в циклы - это еще не хвостовая оптимизация.

#include <stdio.h>

unsigned long long factorial(int x) {
   if (x > 1) return x * factorial(x-1);
     else return 1;
}

int main(int argc, char ** argv) {
    printf("fact %s: %ld\n", argv[1] ,factorial(atoi(argv[1])));
    return 0;
}

:~> gcc fac.c -o fac -O3
:~> ./fac 10
fact 10: 3628800
:~> ./fac 100000000
[1]    6740 segmentation fault  ./fac 100000000

Большинство реализаций JVM, опять же, стековые штуки, поэтому с рекурсией там, в принципе, неплохо.

С рекурсией там все плохо.

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

Разворачивание простой рекурсии в циклы - это еще не хвостовая оптимизация.

Я не очень понял, откуда взялся SEGSIGV. Скомпилировал твой кусок кода как есть:

$ gcc -o a.exe -O3 a.c
$ ./a.exe 10
fact 10: 3628800
$ ./a.exe 10000
fact 10000: 0
$ ./a.exe 100000000
fact 100000000: 0
$ gcc --version
gcc (Debian 4.4.4-7) 4.4.4
$ gcc -S -O3 a.c
$ cat a.s
...
main:
.LFB12:
        .cfi_startproc
        pushq   %rbx
        .cfi_def_cfa_offset 16
        movq    8(%rsi), %rdi
        xorl    %eax, %eax
        movq    %rsi, %rbx
        .cfi_offset 3, -16
        call    atoi
        cmpl    $1, %eax
        movl    $1, %edx
        jle     .L11
        movslq  %eax,%rsi
        subl    $2, %eax
        leaq    -1(%rsi), %rcx
        movq    %rcx, %rdx
        subq    %rax, %rdx
        movq    %rdx, %rax
        movl    $1, %edx
        jmp     .L12
        .p2align 4,,10
        .p2align 3
.L15:
        subq    $1, %rcx
.L12:
        imulq   %rsi, %rdx
        cmpq    %rax, %rcx
        movq    %rcx, %rsi
        jne     .L15
.L11:
        movq    8(%rbx), %rsi
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        xorl    %eax, %eax
        popq    %rbx
        ret
        .cfi_endproc

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

Не вижу корреляции. Там проблемы были не в мутабильности, а в ограниченности STM как модели. Ну и производительность проседает, причем прилично, т.к. транзакционность ресурсоемкая вещь.

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

>Построить немутабельный список можно и итеративно

Немутабельность этого списка будет выражаться в том что ты договорился сам с собой его не мутировать крестнапузе? Тогда конечно пожалуйста.

а что либо сложнее списка, любое дерево например, уже как правило и не предполагает алгоритмов, сводящихся к хвостатой рекурсии.

Серьезно?

>То есть сабж не нужен?

Тебе может и не нужен.

>Google так и сделал. Помогло им это?

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

Покажи как с таким типом data Tree a = Node a (Tree a) (Tree a) | Empty


let t = Tree 1 Empty Empty in Tree 2 t t

подойдет?:)

>толсто, в С++ сам решаешь где использовать COW( в том числе во вложенных структурах ), а где нет, в этом и есть принцип,

Наверное ты никогда не писал больших проектов.

> Нет, но какое это ввобще имеет отношение к теме?

вот именно, ТС говорил про реальные программы и языки, я тоже, а ты решил поумничать

> Наверное ты никогда не писал больших проектов.

писал, и как раз использовал тот самый COW

>Поподробнее можно как оно зависит от деоева и про то,

Приведенная строчка на хаскеле чем не устраивает?

что исследование структуры приводит к копированию в том самом «отличии от».

Список четных элементов на С пожалста.

А с чего ты взял что ее там нет?

Список нечетных элементов умноженных на 2 пожалста.

Возьми любимый функциональщиками ряд Фибоначчи и посчитай триллионный элемент на Хаскеле.

Да - числодробильня подобного типа - типичный код конечно.

Создай грамотный фреймворк списков общего назначения - и ты увидишь где иммутабельность рулит.

>писал, и как раз использовал тот самый COW

Наверно у тебя большой проект это там где многокода - что в жабе и с++ не новость. Для меня большой проект это там где много разработчиков и библиотек общего назначения которые могут использоваться как угодно кемугодно. И вариант записи в доке «мутировать возвращаемые данные нельзя потому что это расхерит внутренне состояние» - не вариант.

> Наверно у тебя большой проект это там где многокода - что в жабе и с++ не новость

наверное ты слишком часто фантазируешь

И вариант записи в доке «мутировать возвращаемые данные нельзя потому что это расхерит внутренне состояние» - не вариант.

ты вообще с понятием Copy-on-write знаком?

> ты вообще с понятием Copy-on-write знаком?

Да - это такая фишка которая везде работает на немутабельных структурах данных.

А да - gcc умеет (я не тот код запостил).

> Да - это такая фишка которая везде работает на немутабельных структурах данных.

нет - эта такая фишка, которая имеет смысл только для мутабельных объектов

>> Нет, но какое это ввобще имеет отношение к теме?

вот именно, ТС говорил про реальные программы и языки, я тоже, а ты решил поумничать

В очередной раз убеждаюсь, что тов. ahonimous разговаривает исключительно сам с собой.

наверное поэтому программы на CL едят столько памяти

Так кто решил поумничать? Кто говорил про реальные (ввп) языки?

> нет - эта такая фишка, которая имеет смысл только для мутабельных объектов.

И что же ты там мутируешь в COW?

ты нереально тупишь, забей

Слишком очевидная последняя попытка спасти лицо после всеми замеченного фэйла.

> Слишком очевидная последняя попытка спасти лицо

«Никогда не кончай спор первым. Дождись, когда оппоненты поймут, что с тобой говорить бесполезно и свалят, а потом заяви о своей победе.» (с)