Здравствуйте, artelk, Вы писали: A>Пожалуйста! Но я все же настаиваю, что для Хаскела тот факт, что возвращается именно трансформация, а не ее результат, не принципиален в вопросе о чистоте. Внутренняя гипотетическая функция transform там тоже чиста. Она детерминирована (весь Мир передается ей в качестве параметра) и не делает никаких сайд-эффектов (т.к. все ее "эффекты" вовсе не "сайд", а включены в возвращаемое значение).
Эмм, просто наше определение сайд-эффектов — это как раз взаимодействие с "миром".
В приведённом коде world играет чисто номинальное значение; в более строгом подходе (как я его понимаю) у нас нет класса Console.
У нас есть что-то типа
public struct World
{
private string[] _out;
private string[] _in;
private World(string[] in, string[] out)
public World PutStr(string line)
{
var newOut = new string[_out.Count+1];
Array.Copy(_out, newOut, _out.Count);
newOut[_out.Count] = line;
return new World(_in, newOut);
}
public (string, World) GetStr()
{
var newIn = new string[_in.Count-1];
Array.Copy(_in, newIn, 1, _in.Count-1);
return (_in[0], new World(newIn, _out);
}
}
Это, конечно, условно — но для иллюстрации поведения сойдёт.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, samius, Вы писали:
S>Dump-то безусловно грязная. Я не о ней, я о foo, которая грязная без обращения к постулированно грязным функциям.
Это ошибочная трактовка. Вы думаете не в ту сторону. Дело не в возможности придумать метод детектирования количества "реальных исполнений" функции (что бы это ни значило).
А в возможности полагаться на побочные эффекты.
Функция foo — чистая, в том смысле, что компилятор и среда не гарантируют зависимости результатов от порядка исполнения.
То есть сегодня у вас эта программа выводит два разных числа в Dump, а завтра вышел апдейт компилятора или рантайма — и волшебным образом все массивы нулевой длины стали показывать на один и тот же интернированный экземпляр.
Именно чистота foo даёт компилятору свободу делать такие штуки.
Собственно, никакой ценности в изоляции побочных эффектов, кроме вот этих возможностей оптимизации, и нету.
Если бы мы говорили об императивном языке, то информация о чистоте функциии позволяла бы компилятору делать всякие полезности типа:
for(int i=0; i<a.GetLength(); i++)
average += a[i]/a.GetLength();
=>
var tmp = a.GetLength();
for(int i=0; i<tmp; i++)
average += a[i]/tmp;
Современный CLR устраняет только первый вызов (и сравнение) для встроенных типов — то есть имеем хардкод. Не существует способа, кроме инлайнинга, который бы помог сделать loop invariant reduction в подобных сценариях.
Наличие pure как двустороннего контракта позволяет делать такие трансформации.
При этом ещё раз подчеркну: такая функция вполне может быть не-чистой внутри. Это её личное дело.
Просто результат исполнения подобного цикла может оказаться "не вполне таким", как если бы функция была по-честному размечена грязной.
Например, если GetLength() собирается писать в лог свои параметры (как наш несчастный синус), то мы рискуем увидеть от 0 до N+1 записей. И это нормально — запись в лог не является её основной обязанностью, эту часть логики программист намеренно не уточнил.
Зато если мы нечаянно пометим флагом чистоты функцию Random(), то вот такой код может иметь некорректный (с т.з. программиста) результат:
Т.е. Random() надо помечать грязной, т.к. её основная работа — выдавать разные значения, и редуцировать её к константе нельзя (какая бы случайная эта константа ни была ).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, samius, Вы писали:
S>>Dump-то безусловно грязная. Я не о ней, я о foo, которая грязная без обращения к постулированно грязным функциям. S>Это ошибочная трактовка. Вы думаете не в ту сторону. Дело не в возможности придумать метод детектирования количества "реальных исполнений" функции (что бы это ни значило). S>А в возможности полагаться на побочные эффекты.
Я лишь продемонстрировал недостаток подхода о заключении чистоты на основе отсутствия вызова явно грязных функций. Т.е. нам нужно сначала определиться, что считать грязью, а что нет, чем могут отличаться результаты наших чистых функций, т.е. какие отличия нами допустимы для утверждения о чистоте, какие — нет. Без этого нет смысла говорить ни об автоматической разметке, ни об автоматической проверке ручной разметки.
S>Функция foo — чистая, в том смысле, что компилятор и среда не гарантируют зависимости результатов от порядка исполнения.
В этом смысле — да. Но условие детерминированности результата не выполнено. О чистоте не может быть речи. S>То есть сегодня у вас эта программа выводит два разных числа в Dump, а завтра вышел апдейт компилятора или рантайма — и волшебным образом все массивы нулевой длины стали показывать на один и тот же интернированный экземпляр. S>Именно чистота foo даёт компилятору свободу делать такие штуки.
Здесь поправка. У меня массив единичной длины. И т.к. массив — это изменяемый объект, то он "бай десигн" не может иметь реализацию GetHashCode(), заточенную на свое структурное содержимое, т.к. изменение содержимого будет приводить к изменению результата GetHashCode(), что сломает возможность помещения таких массивов в качестве ключей в словари и хэшсеты. Вобщем-то это так же является причиной того, что нам не следует бояться интернированных эксземпляров даже пустых массивов. Это ломающее изменение. Сломается возможность помещения множества пустых массивов в HashSet; сломается Monitor.Enter/Exit, выполненная на массивах. Возможно, что-то еще.
S>Собственно, никакой ценности в изоляции побочных эффектов, кроме вот этих возможностей оптимизации, и нету.
S>Если бы мы говорили об императивном языке, то информация о чистоте функциии позволяла бы компилятору делать всякие полезности типа:
S>
S>for(int i=0; i<a.GetLength(); i++)
S> average += a[i]/a.GetLength();
S>
S>Современный CLR устраняет только первый вызов (и сравнение) для встроенных типов — то есть имеем хардкод. Не существует способа, кроме инлайнинга, который бы помог сделать loop invariant reduction в подобных сценариях. S>Наличие pure как двустороннего контракта позволяет делать такие трансформации. S>При этом ещё раз подчеркну: такая функция вполне может быть не-чистой внутри. Это её личное дело. S>Просто результат исполнения подобного цикла может оказаться "не вполне таким", как если бы функция была по-честному размечена грязной. S>Например, если GetLength() собирается писать в лог свои параметры (как наш несчастный синус), то мы рискуем увидеть от 0 до N+1 записей. И это нормально — запись в лог не является её основной обязанностью, эту часть логики программист намеренно не уточнил.
Вот, да. Верно! Если GetLength будет незаметно писать в какой-то лог во временном каталоге и временном файле — мы рискуем это вообще никак не заметить и не обратить внимание на такое недоразумение, считать его чистым. Но если при этом будет хвататься какой-то файл в режиме монопольной записи и мешать выполняться GetLength() из других потоков (а то и процессов), вот это нам серьезно помешает.
S>Зато если мы нечаянно пометим флагом чистоты функцию Random(), то вот такой код может иметь некорректный (с т.з. программиста) результат: S>
S>Т.е. Random() надо помечать грязной, т.к. её основная работа — выдавать разные значения, и редуцировать её к константе нельзя (какая бы случайная эта константа ни была ).
Согласен. Но к вопросу об автоматической разметке (либо проверки разметки), компилятор не может и не должен принимать решение о том, что является основным результатом, а что — нет. Т.е. если с Console.WriteLine(string) еще все понятно, то с ее версией, возвращающей длину строки, понять, что же именно основное (вывод или возврат длины строки) — мы уже не можем однозначно.
Таким образом, int WriteLine() рискуем записать в чистые "по основной обязанности" и с небольшой записью в качестве вспомогательной.
Здравствуйте, samius, Вы писали:
S>В этом смысле — да. Но условие детерминированности результата не выполнено. О чистоте не может быть речи. S>Здесь поправка. У меня массив единичной длины.
А, пардон, не там увидел ноль. Ну как бы да — в языке с изменяемыми типами крайне сложно сочинить реально чистую функцию.
Ваша функция — полноценно грязная, т.к. она меняет мир.
S>Вот, да. Верно! Если GetLength будет незаметно писать в какой-то лог во временном каталоге и временном файле — мы рискуем это вообще никак не заметить и не обратить внимание на такое недоразумение, считать его чистым. Но если при этом будет хвататься какой-то файл в режиме монопольной записи и мешать выполняться GetLength() из других потоков (а то и процессов), вот это нам серьезно помешает.
А чему именно помешает? Чего именно мы хотим добиться? Ок, допустим, функция по-прежнему захватывает файл, но продекларирована как грязная — это же ничего ни от чего не спасёт.
Единственная особенность — теперь количество захватов и отпусканий файла, а также их порядок, будет строже соответствовать написанному в программе.
Даже если мы избавимся от наступания на самих себя в параллельных потоках — приложение всё ещё можно будет сломать при помощи второго приложения, которое заблокирует таки этот файл.
Тут же речь о том, что доступ к миру в чистой функции — он unreliable. То есть писать функцию, чувствительную к порядку вызовов, и объявлять её pure — это такой способ выстрелить себе в ногу.
S>Согласен. Но к вопросу об автоматической разметке (либо проверки разметки), компилятор не может и не должен принимать решение о том, что является основным результатом, а что — нет. Т.е. если с Console.WriteLine(string) еще все понятно, то с ее версией, возвращающей длину строки, понять, что же именно основное (вывод или возврат длины строки) — мы уже не можем однозначно. S>Таким образом, int WriteLine() рискуем записать в чистые "по основной обязанности" и с небольшой записью в качестве вспомогательной.
Без разметки компилятор должен выводить тип автоматически на основании тела. Есть вызовы грязного кода — считаем функцию грязной; нету — чистой.
Если мы пометили функцию чистой, то компилятор (в зависимости от вкусов разработчика) должен выдавать warning либо error, встретив грязный вызов.
Так что по умолчанию компилятор считает побочные эффекты важными. Пометка pure означает, что нам наплевать на побочные эффекты, и их может вовсе не быть.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Если бы мы говорили об императивном языке, то информация о чистоте функциии позволяла бы компилятору делать всякие полезности типа:
S>
S>for(int i=0; i<a.GetLength(); i++)
S> average += a[i]/a.GetLength();
S>
S>Современный CLR устраняет только первый вызов (и сравнение) для встроенных типов — то есть имеем хардкод. Не существует способа, кроме инлайнинга, который бы помог сделать loop invariant reduction в подобных сценариях. S>Наличие pure как двустороннего контракта позволяет делать такие трансформации.
Тут на самом деле не всё так просто — надо чтобы компилятор мог гарантированно видеть неизменность переменной "a" внутри цикла. Например в C++ компилятор проводит эту оптимизацию для любых пользовательских типов без всяких модификаторов чистоты. Однако при этом в некоторых специфических случаях она не срабатывает, т.к. компилятор видит потенциальную возможность изменения переменной (хотя на самом деле никаких изменений естественно нет).
Так что лучше сразу писать for(int i=0, е=a.GetLength(); i<е; i++), ну или использовать range for, которые транслируется (во всяком случае в C++) как раз в такую конструкцию.
P.S. Если вдруг кто-то думает, что оптимизация выше — это какая то непринципиальная ерунда с экономией пары процессорных тиков, то это совсем не так. Например если мы всё же используем запись цикла в первом варианте и оптимизация с a.GetLength не пройдёт, то это автоматически заблокирует нам автовекторизацию этого цикла. А это уже может быть реальным провалом в быстродействие в десятки раз.
Здравствуйте, alex_public, Вы писали:
_>Тут на самом деле не всё так просто — надо чтобы компилятор мог гарантированно видеть неизменность переменной "a" внутри цикла. Например в C++ компилятор проводит эту оптимизацию для любых пользовательских типов без всяких модификаторов чистоты. Однако при этом в некоторых специфических случаях она не срабатывает, т.к. компилятор видит потенциальную возможность изменения переменной (хотя на самом деле никаких изменений естественно нет).
Основной инструмент, которым пользуется компилятор C++ — это инлайнинг.
А дальше — строим SSA-форму, в которой видно, что и где изменяется, и что остаётся инвариантом. _>Так что лучше сразу писать for(int i=0, е=a.GetLength(); i<е; i++), ну или использовать range for, которые транслируется (во всяком случае в C++) как раз в такую конструкцию.
Для кого лучше? Например, на C# такой код для встроенных массивов — явная пессимизация. Потому что JIT умеет распознавать паттерн i<a.Count и устраняет проверки границ. А паттерн i<e требует значительно более длинного пути для доказательства невыхода за границы, поэтому проверки будут оставлены. _>P.S. Если вдруг кто-то думает, что оптимизация выше — это какая то непринципиальная ерунда с экономией пары процессорных тиков, то это совсем не так. Например если мы всё же используем запись цикла в первом варианте и оптимизация с a.GetLength не пройдёт, то это автоматически заблокирует нам автовекторизацию этого цикла. А это уже может быть реальным провалом в быстродействие в десятки раз.
Ну вот в том-то и дело: декларация a.GetLength() как pure означает, что она не меняет мир — значит и a остаётся неизменной, поэтому можно оптимизировать всё.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, samius, Вы писали:
S>>В этом смысле — да. Но условие детерминированности результата не выполнено. О чистоте не может быть речи. S>>Здесь поправка. У меня массив единичной длины. S>А, пардон, не там увидел ноль. Ну как бы да — в языке с изменяемыми типами крайне сложно сочинить реально чистую функцию. S>Ваша функция — полноценно грязная, т.к. она меняет мир.
Конечно, но дело не в неизменяемости. Нужно оговаривать набор инструментов, которыми мы можем познавать изменения. string в дотнете достаточно неизменяемый, но функция, возвращающая string, точно так же будет полноценно грязной, т.к. будет менять мир. Способ измерения изменений — функции, следящие за памятью процесса, пиннед-поинтеры и т.п.
S>>Вот, да. Верно! Если GetLength будет незаметно писать в какой-то лог во временном каталоге и временном файле — мы рискуем это вообще никак не заметить и не обратить внимание на такое недоразумение, считать его чистым. Но если при этом будет хвататься какой-то файл в режиме монопольной записи и мешать выполняться GetLength() из других потоков (а то и процессов), вот это нам серьезно помешает. S>А чему именно помешает? Чего именно мы хотим добиться? Ок, допустим, функция по-прежнему захватывает файл, но продекларирована как грязная — это же ничего ни от чего не спасёт.
Это не дает нам использовать ее как чистую (руками или компилятором), заставляет посмотреть, что в ней не так, попытаться обойти, либо проложиться каким-то образом.
S>Единственная особенность — теперь количество захватов и отпусканий файла, а также их порядок, будет строже соответствовать написанному в программе. S>Даже если мы избавимся от наступания на самих себя в параллельных потоках — приложение всё ещё можно будет сломать при помощи второго приложения, которое заблокирует таки этот файл.
S>Тут же речь о том, что доступ к миру в чистой функции — он unreliable. То есть писать функцию, чувствительную к порядку вызовов, и объявлять её pure — это такой способ выстрелить себе в ногу.
В этом же и цель. Дать выстрелить себе в ногу, но остаться с пальцами. Мы хотим каких-то оптимизаций, при этом, готовы закрыть глаза на определенные нюансы.
S>>Согласен. Но к вопросу об автоматической разметке (либо проверки разметки), компилятор не может и не должен принимать решение о том, что является основным результатом, а что — нет. Т.е. если с Console.WriteLine(string) еще все понятно, то с ее версией, возвращающей длину строки, понять, что же именно основное (вывод или возврат длины строки) — мы уже не можем однозначно. S>>Таким образом, int WriteLine() рискуем записать в чистые "по основной обязанности" и с небольшой записью в качестве вспомогательной. S>Без разметки компилятор должен выводить тип автоматически на основании тела. Есть вызовы грязного кода — считаем функцию грязной; нету — чистой. S>Если мы пометили функцию чистой, то компилятор (в зависимости от вкусов разработчика) должен выдавать warning либо error, встретив грязный вызов. S>Так что по умолчанию компилятор считает побочные эффекты важными. Пометка pure означает, что нам наплевать на побочные эффекты, и их может вовсе не быть.
Мы не договорились, что должен означать модификатор pure, а значит, каждый думал о своей интерпретации. Объявление функции истинно чистой невозможно без перечня контроллируемых сайд-эффектов и способов их обнаружения, т.е. модификатор pure в моей интерпретации несет мало смысла. Но есть смысл в вашей интерпретации, что это инструкция компилятору забить на все обозримые нечистоты и использовать функцию, как будто она в полной мере pure. Т.е. не доказывать чистоту, но забить на все, что бы позволить определенные оптимизации.
Может быть стоит рассмотреть явный перечень эффектов, которые должен проигнорировать компилятор? Например, я хочу указать, что при операциях с памятью, я не буду обращать внимание на прямое или косвенное обнаружение эффектов типа new int[1].GetHashCode()
Вообще, как мне кажется, это лишь гимнастика ума. Вряд ли что-то такое можно будет ожидать в обозримом будущем.
Здравствуйте, Sinclair, Вы писали:
_>>Тут на самом деле не всё так просто — надо чтобы компилятор мог гарантированно видеть неизменность переменной "a" внутри цикла. Например в C++ компилятор проводит эту оптимизацию для любых пользовательских типов без всяких модификаторов чистоты. Однако при этом в некоторых специфических случаях она не срабатывает, т.к. компилятор видит потенциальную возможность изменения переменной (хотя на самом деле никаких изменений естественно нет). S>Основной инструмент, которым пользуется компилятор C++ — это инлайнинг. S>А дальше — строим SSA-форму, в которой видно, что и где изменяется, и что остаётся инвариантом.
Это да. Я просто уточнил, что вот не всегда он может это корректно определить. В большинстве случаев может, но иногда ошибается.
_>>Так что лучше сразу писать for(int i=0, е=a.GetLength(); i<е; i++), ну или использовать range for, которые транслируется (во всяком случае в C++) как раз в такую конструкцию. S>Для кого лучше? Например, на C# такой код для встроенных массивов — явная пессимизация. Потому что JIT умеет распознавать паттерн i<a.Count и устраняет проверки границ. А паттерн i<e требует значительно более длинного пути для доказательства невыхода за границы, поэтому проверки будут оставлены.
Ну я то писал про C++. Забавно, что в C# ситуация обратная. Кстати, а в какой код транслируется range for в C#? )
_>>P.S. Если вдруг кто-то думает, что оптимизация выше — это какая то непринципиальная ерунда с экономией пары процессорных тиков, то это совсем не так. Например если мы всё же используем запись цикла в первом варианте и оптимизация с a.GetLength не пройдёт, то это автоматически заблокирует нам автовекторизацию этого цикла. А это уже может быть реальным провалом в быстродействие в десятки раз. S>Ну вот в том-то и дело: декларация a.GetLength() как pure означает, что она не меняет мир — значит и a остаётся неизменной, поэтому можно оптимизировать всё.
Не значит. Если в теле цикла есть другой (модифицирующий) вызов a. Вот в случае константного a всё однозначно. А когда константности нет, то компилятор должен сам отслеживать и не всегда у него это удаётся верно.
Причём ещё нюанс: нам не обязательно требовать именно чистоты функций, вызываемых в теле цикла. Главное чтобы они не меняли a (т.е. если вдруг у a есть функция, печатающая некую отладочную информацию в консоль, то это не должно помешать такой оптимизации).
Здравствуйте, samius, Вы писали:
S>Я лишь продемонстрировал недостаток подхода о заключении чистоты на основе отсутствия вызова явно грязных функций. Т.е. нам нужно сначала определиться, что считать грязью, а что нет, чем могут отличаться результаты наших чистых функций, т.е. какие отличия нами допустимы для утверждения о чистоте, какие — нет. Без этого нет смысла говорить ни об автоматической разметке, ни об автоматической проверке ручной разметки.
Вот что подумалось. Функции исполняются грязным исполнителем. Тут вопрос в том, влияет ли состояние исполнителя на результат foo. Грязные уши исполнителся торчат из функции GetHashCode у массивов, именно поэтому foo недетерминирована. Результат GetHashCode зависит от адреса только что выделенного массива, а это случайная величина. Неявно вызываемый аналог malloc(SIZE) является недетерминированной функцией и влияет на результат foo.
Здравствуйте, samius, Вы писали: S>Конечно, но дело не в неизменяемости. Нужно оговаривать набор инструментов, которыми мы можем познавать изменения. string в дотнете достаточно неизменяемый, но функция, возвращающая string, точно так же будет полноценно грязной, т.к. будет менять мир. Способ измерения изменений — функции, следящие за памятью процесса, пиннед-поинтеры и т.п.
Не-не-не-не-не, дэвид блейн. Это не тот мир, который нас интересует. Есть определённые договорённости, в рамках которых мы действуем.
Понятно, что на самом деле при вычислении функции происходят какие-то модификации состояния в потрошках машины. Но наша цель — собственно разделить эффекты на желательные и неважные.
Ну, как volatile в плюсах, которым мы подавляем "умничание" компилятора, чтобы он перестал считать повторные чтения из памяти, замапленной на аппаратный регистр, безопасными. И повторные записи — идемпотентными.
Если для нас важны побочные эффекты, то мы явно описываем это как "вот тут изменения мира являются важной частью функциональности", а если нет — то явно описываем как "вот тут изменения мира введены для просто так".
И сделано это ровно из практических соображений — потому что иначе, к примеру, невозможно было бы построить трассировку исполнения. Ведь если функция чистая, то ей доступ к миру запрещён, а если грязная — то исполняется всё совсем не так, как в чистом случае.
S>>А чему именно помешает? Чего именно мы хотим добиться? Ок, допустим, функция по-прежнему захватывает файл, но продекларирована как грязная — это же ничего ни от чего не спасёт. S>Это не дает нам использовать ее как чистую (руками или компилятором), заставляет посмотреть, что в ней не так, попытаться обойти, либо проложиться каким-то образом.
Продолжаю не понимать. Куда мы будем смотреть? Всё, что это даст — наша функция, которая её вызывает, тоже станет грязной. Ну, как бы имеем расползание грязи по программе — и что? Практическая цель какая у этой порнографии?
S>В этом же и цель. Дать выстрелить себе в ногу, но остаться с пальцами. Мы хотим каких-то оптимизаций, при этом, готовы закрыть глаза на определенные нюансы.
Ну, это, по-хорошему, требует отдельного рассмотрения. Потому что либо у нас есть эдакий unsafe(), который позволяет выполнять любой грязный код внутри чистой функции, или у нас есть "усечённый вариант мира", который можно использовать без получения грязной сигнатуры, но при этом сделать можно не всё.
S>Мы не договорились, что должен означать модификатор pure, а значит, каждый думал о своей интерпретации. Объявление функции истинно чистой невозможно без перечня контроллируемых сайд-эффектов и способов их обнаружения, т.е. модификатор pure в моей интерпретации несет мало смысла. Но есть смысл в вашей интерпретации, что это инструкция компилятору забить на все обозримые нечистоты и использовать функцию, как будто она в полной мере pure. Т.е. не доказывать чистоту, но забить на все, что бы позволить определенные оптимизации.
S>Может быть стоит рассмотреть явный перечень эффектов, которые должен проигнорировать компилятор? Например, я хочу указать, что при операциях с памятью, я не буду обращать внимание на прямое или косвенное обнаружение эффектов типа new int[1].GetHashCode() S>Вообще, как мне кажется, это лишь гимнастика ума. Вряд ли что-то такое можно будет ожидать в обозримом будущем.
Тут принципиальный вопрос — в том, поддерживаем ли мы вообще мутабельность. Это для начала.
Если её нет, то никаких парадоксов с new int[1] у нас нету — не бывает изменяемых массивов, поэтому результаты new int[1]{0} эквивалентны до неразличимости.
Если она есть, то надо очень внимательно смотреть на то, что мы называем "миром". Потому что мир теперь — это не только условная консоль (которую в целях математической абстракции мы можем считать замапленной на два списка строк), а ещё и состояние всех "активных в данный момент" переменных. В итоге у нас понятие "грязи" становится очень широким; написать чистый код становится тяжело, и его роль резко уменьшается.
В итоге мы, скорее всего, быстро упрёмся в то, что уже и так есть: области "чистого кода" будут крайне малого размера, сопоставимого по масштабам со способностями современных компиляторов/сред к инлайнингу и анализу.
Тогда ценности от дополнительной разметки у нас не будет никакой — те места, где можно что-то выиграть на чистоте кода, уже и так детектируются и оптимизируются; а те места, где нет оптимизации — вот эта вот полуручная разметка не поможет.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, alex_public, Вы писали: _>Ну я то писал про C++. Забавно, что в C# ситуация обратная. Кстати, а в какой код транслируется range for в C#? )
В С# range нету. Вместо них — Span<T>.
Он прекрасен тем, что позволяет сослаться на более-менее любую память. Наиболее популярный сценарий — кусок массива.
Так вот — он решает проблемы с детектированием границ:
public static void foo(int[] arr)
{
int64 sum = 0;
for(int i=0; i<arr.Count; i++)
sum+=arr[i]; // проверка устранена
int64 sum = 0;
for(int i=0; i<arr.Count-1; i++)
sum+=arr[i]; // проверка не устранена!var subarray = new Span<int>(arr, 0, arr.Count-1); // один раз проверили границы здесь
int64 sum = 0;
for(int i=0; i<subarray.Count; i++)
sum+=subarray[i]; // проверка устранена!
}
_>Не значит. Если в теле цикла есть другой (модифицирующий) вызов a. Вот в случае константного a всё однозначно. А когда константности нет, то компилятор должен сам отслеживать и не всегда у него это удаётся верно.
Зависит от толщины тела. В простых случаях компилятор просто видит, что модифицирующих вызовов нет — всё, константность нам монопенисуальна.
Кстати, что будет, если a — константен, но внутри цикла мы имеем const_cast и принудительную модификацию? Всё падает, или компилятор видит палево и отменяет оптимизацию? _>Причём ещё нюанс: нам не обязательно требовать именно чистоты функций, вызываемых в теле цикла. Главное чтобы они не меняли a (т.е. если вдруг у a есть функция, печатающая некую отладочную информацию в консоль, то это не должно помешать такой оптимизации).
Да. Понятия чистоты, детерминированности, константности — все разные, близкие, но могут применяться компилятором в различных сценариях.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, artelk, Вы писали: A>>Пожалуйста! Но я все же настаиваю, что для Хаскела тот факт, что возвращается именно трансформация, а не ее результат, не принципиален в вопросе о чистоте. Внутренняя гипотетическая функция transform там тоже чиста. Она детерминирована (весь Мир передается ей в качестве параметра) и не делает никаких сайд-эффектов (т.к. все ее "эффекты" вовсе не "сайд", а включены в возвращаемое значение). S>Эмм, просто наше определение сайд-эффектов — это как раз взаимодействие с "миром". S>В приведённом коде world играет чисто номинальное значение; в более строгом подходе (как я его понимаю) у нас нет класса Console. S>У нас есть что-то типа S>
S>public struct World
S>{
S> private string[] _out;
S> private string[] _in;
S> private World(string[] in, string[] out)
S> public World PutStr(string line)
S> {
S> var newOut = new string[_out.Count+1];
S> Array.Copy(_out, newOut, _out.Count);
S> newOut[_out.Count] = line;
S> return new World(_in, newOut);
S> }
S> public (string, World) GetStr()
S> {
S> var newIn = new string[_in.Count-1];
S> Array.Copy(_in, newIn, 1, _in.Count-1);
S> return (_in[0], new World(newIn, _out);
S> }
S>}
S>
S>Это, конечно, условно — но для иллюстрации поведения сойдёт.
Согласен. Но у меня World вообще internal, как в Хаскеле. Так что пишем мой вариант, а имеем ввиду ваш — главное, чтоб для вызывающего кода работало как ваш вариант.
Для клиенсткого кода нужно запретить использовать класс Console (и прочие I/O классы) напрямую, без нашей IO обертки, и вот мы уже на полпути к Хаскелу.
Впринципе, можно сделать World открытым.
(По сигнатурам и семантике идентично вашему, а в реализации другое.)
public struct World
{
private World()
public World PutStr(string line)
{
Console.WriteLine(line);
return new World();
}
public (string, World) GetStr()
{
return (Console.ReadLine(), new World());
}
}
При наличие хаскелообразного ленивого (upd: а также считающего все функции чистыми и агрессивно кэшируещего их результаты) исполнителя (чтобы только одна ветка исполнения отрабатывала в рантайме), все будет так же чисто и стерильно.
Здравствуйте, Sinclair, Вы писали:
_>>Ну я то писал про C++. Забавно, что в C# ситуация обратная. Кстати, а в какой код транслируется range for в C#? ) S>В С# range нету. Вместо них — Span<T>.
Эм, я имел в виду foreach. )
S>Он прекрасен тем, что позволяет сослаться на более-менее любую память. Наиболее популярный сценарий — кусок массива. S>Так вот — он решает проблемы с детектированием границ: S>
public static void foo(int[] arr)
S>{
S> int64 sum = 0;
S> for(int i=0; i<arr.Count; i++)
S> sum+=arr[i]; // проверка устранена
S> int64 sum = 0;
S> for(int i=0; i<arr.Count-1; i++)
S> sum+=arr[i]; // проверка не устранена!
S> var subarray = new Span<int>(arr, 0, arr.Count-1); // один раз проверили границы здесь
S> int64 sum = 0;
S> for(int i=0; i<subarray.Count; i++)
S> sum+=subarray[i]; // проверка устранена!
S>}
S>
Да, выглядит не плохо, хотя было бы красивее иметь что-то вроде foreach для Span.
_>>Не значит. Если в теле цикла есть другой (модифицирующий) вызов a. Вот в случае константного a всё однозначно. А когда константности нет, то компилятор должен сам отслеживать и не всегда у него это удаётся верно. S>Зависит от толщины тела. В простых случаях компилятор просто видит, что модифицирующих вызовов нет — всё, константность нам монопенисуальна.
Ну я так и писал, что константность не обязательна — это скорее гарантия. А так, компилятор смотрит сам и почти всегда правильно. Но почти... Ошибки естественно всегда в сторону перестраховки.
S>Кстати, что будет, если a — константен, но внутри цикла мы имеем const_cast и принудительную модификацию? Всё падает, или компилятор видит палево и отменяет оптимизацию?
Контроль работает где-то на уровне потенциального доступа к указателям. Так что если есть шанс модифицирующего доступа, то оптимизации не будет.
Здравствуйте, artelk, Вы писали:
A>Здравствуйте, samius, Вы писали:
A>Вот что подумалось. Функции исполняются грязным исполнителем. Тут вопрос в том, влияет ли состояние исполнителя на результат foo. Грязные уши исполнителся торчат из функции GetHashCode у массивов, именно поэтому foo недетерминирована. Результат GetHashCode зависит от адреса только что выделенного массива, а это случайная величина. Неявно вызываемый аналог malloc(SIZE) является недетерминированной функцией и влияет на результат foo.
Дело не в исполнителе. Даже если мы будем память выделять в бумажной тетрадке, сама постановка задачи подразумевает что мы не должны выдать два байта в одном адресе. Есть задачи, где не важно, где именно выделен байт, им важно лишь содержимое. Для них выделение можно считать чистым. Потому я и настаиваю, что прежде чем заниматься анализом чистоты, нужно договориться, какие именно изменения глобального состояния мы будем считать грязными. И вполне может быть что для одной функции будет определен один набор, для соседней — другой.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, samius, Вы писали: S>>Конечно, но дело не в неизменяемости. Нужно оговаривать набор инструментов, которыми мы можем познавать изменения. string в дотнете достаточно неизменяемый, но функция, возвращающая string, точно так же будет полноценно грязной, т.к. будет менять мир. Способ измерения изменений — функции, следящие за памятью процесса, пиннед-поинтеры и т.п. S>Не-не-не-не-не, дэвид блейн. Это не тот мир, который нас интересует. Есть определённые договорённости, в рамках которых мы действуем. S>Понятно, что на самом деле при вычислении функции происходят какие-то модификации состояния в потрошках машины. Но наша цель — собственно разделить эффекты на желательные и неважные.
Верно. Я лишь о том, что в каждом конкретном случае у нас будут разные наборы желательных и неважных эффектов.
S>Ну, как volatile в плюсах, которым мы подавляем "умничание" компилятора, чтобы он перестал считать повторные чтения из памяти, замапленной на аппаратный регистр, безопасными. И повторные записи — идемпотентными.
S>Если для нас важны побочные эффекты, то мы явно описываем это как "вот тут изменения мира являются важной частью функциональности", а если нет — то явно описываем как "вот тут изменения мира введены для просто так". S>И сделано это ровно из практических соображений — потому что иначе, к примеру, невозможно было бы построить трассировку исполнения. Ведь если функция чистая, то ей доступ к миру запрещён, а если грязная — то исполняется всё совсем не так, как в чистом случае.
Об этом и речь, что даже функцию форматирования (иммутабельной дотнетовской) строки мы можем считать чистой в одном случае и грязной в другом, т.к. она изменяет глобальное состояние память, еще и результат с точки зрения физического адреса недетерминирован.
S>>>А чему именно помешает? Чего именно мы хотим добиться? Ок, допустим, функция по-прежнему захватывает файл, но продекларирована как грязная — это же ничего ни от чего не спасёт. S>>Это не дает нам использовать ее как чистую (руками или компилятором), заставляет посмотреть, что в ней не так, попытаться обойти, либо проложиться каким-то образом. S>Продолжаю не понимать. Куда мы будем смотреть? Всё, что это даст — наша функция, которая её вызывает, тоже станет грязной. Ну, как бы имеем расползание грязи по программе — и что? Практическая цель какая у этой порнографии?
Исключительно помощь в принятии решения о том, можно ли использовать данную конкретную функцию таким-то образом. Сейчас мы смотрим на каждую редмондовскую функцию и не знаем о ней ничего в плане чистоты. В лучшем случае, видим исключения, которые она может выкинуть. Но что и как она может менять — приходится угадывать по контексту и контракту. Если бы у нас была разметка, было бы проще делать анализ.
S>>Вообще, как мне кажется, это лишь гимнастика ума. Вряд ли что-то такое можно будет ожидать в обозримом будущем. S>Тут принципиальный вопрос — в том, поддерживаем ли мы вообще мутабельность. Это для начала. S>Если её нет, то никаких парадоксов с new int[1] у нас нету — не бывает изменяемых массивов, поэтому результаты new int[1]{0} эквивалентны до неразличимости.
У меня не было цели использовать именно GetHashCode для демонстрации. Это был просто простейший способ выразить недетерминированность выделения памяти (на которую в большинстве случаев можно закрыть глаза). Так, что, взятие хэшкода и структурная эквивалентность имеют значение, но не на первом месте. Сначала надо разобраться с возможностью обнаружить различия между результатами функции в плане физического адреса, как и возможность изменения глобального состояния "карты доступной памяти". Эти вопросы выходят за рамки модификации уже существующих языков (например, C#), платформ и т.п. Либо научиться составлять списки допустимой грязи, как списки вероятных исключений. S>Если она есть, то надо очень внимательно смотреть на то, что мы называем "миром". Потому что мир теперь — это не только условная консоль (которую в целях математической абстракции мы можем считать замапленной на два списка строк), а ещё и состояние всех "активных в данный момент" переменных. В итоге у нас понятие "грязи" становится очень широким; написать чистый код становится тяжело, и его роль резко уменьшается.
Согласен
S>В итоге мы, скорее всего, быстро упрёмся в то, что уже и так есть: области "чистого кода" будут крайне малого размера, сопоставимого по масштабам со способностями современных компиляторов/сред к инлайнингу и анализу. S>Тогда ценности от дополнительной разметки у нас не будет никакой — те места, где можно что-то выиграть на чистоте кода, уже и так детектируются и оптимизируются; а те места, где нет оптимизации — вот эта вот полуручная разметка не поможет.
Верно. Я не настаиваю на том, что она должна быть. Я о том, какой она должна быть что бы иметь хоть какой-то смысл и пользу.
Здравствуйте, alex_public, Вы писали:
_>Эм, я имел в виду foreach. ) _>Да, выглядит не плохо, хотя было бы красивее иметь что-то вроде foreach для Span.
С foreach немного проще, т.к. в теле цикла у нас нет индексного обращения, и мы работаем только с самим элементом.
Правила компиляции foreach весьма просты:
foreach(var t in span) sum+= t;
раскрывается в
Span<int>.Enumerator e = span.GetEnumerator();
try
{
while (e.MoveNext())
{
ref int t = e.Current;
sum += t; // original body
}
}
finally
{
(if e is IDisposable d)
d.Dispose();
}
Здесь я уже подставил те типы, которые получаются для Span<int>.
Код спановского енумератора можно посмотреть вот тут: https://github.com/dotnet/coreclr/blob/master/src/System.Private.CoreLib/shared/System/Span.cs
Там всё выглядит хорошо: агрессивный инлайнинг, ref struct означает, что прикопать енумератор нельзя (и велик шанс разместиться в регистрах).
Но если честно, я код такого foreach не дизассемблировал, не знаю, насколько там всё хорошо оптимизируется по сравнению с честным перебором массива.
А, ну и надо учитывать, что автовекторизации в дотнете нет. Если хочется чего-то векторного — будьте любезны руками кастить Span<int> к Vector<int> и выполнять loop unrolling.
Выглядит страшненько. Я в прошлом году пробовал напилить библиотеку, которая бы преобразовывала запросы на linq поверх двумерных массивов к оптимальному векторному коду автоматически, но упёрся.
В простых случаях код векторизовался, но работал медленнее скалярного; в сложных там порождённый код просто ломал CLR и вылетал. _>Контроль работает где-то на уровне потенциального доступа к указателям. Так что если есть шанс модифицирующего доступа, то оптимизации не будет.
Ну вот то-то и оно. const, получается, нужен программисту — чтобы он нечаянно не занёс модификации туда, куда не надо.
Ну и, потенциально, для кросс-модульных оптимизаций.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Но если честно, я код такого foreach не дизассемблировал, не знаю, насколько там всё хорошо оптимизируется по сравнению с честным перебором массива.
Здравствуйте, Sinclair, Вы писали:
_>>Эм, я имел в виду foreach. ) _>>Да, выглядит не плохо, хотя было бы красивее иметь что-то вроде foreach для Span. S>С foreach немного проще, т.к. в теле цикла у нас нет индексного обращения, и мы работаем только с самим элементом. S>Правила компиляции foreach весьма просты: S>foreach(var t in span) sum+= t; S>раскрывается в S>
S>Span<int>.Enumerator e = span.GetEnumerator();
S>try
S>{
S> while (e.MoveNext())
S> {
S> ref int t = e.Current;
S> sum += t; // original body
S> }
S>}
S>finally
S>{
S> (if e is IDisposable d)
S> d.Dispose();
S>}
S>
S>Здесь я уже подставил те типы, которые получаются для Span<int>.
А, понятно. Я просто забыл, что foreach работает только через IEnumerator и соответственно ограничен его подходом (только последовательный доступ).
S>А, ну и надо учитывать, что автовекторизации в дотнете нет. Если хочется чего-то векторного — будьте любезны руками кастить Span<int> к Vector<int> и выполнять loop unrolling. S>Выглядит страшненько. Я в прошлом году пробовал напилить библиотеку, которая бы преобразовывала запросы на linq поверх двумерных массивов к оптимальному векторному коду автоматически, но упёрся. S>В простых случаях код векторизовался, но работал медленнее скалярного; в сложных там порождённый код просто ломал CLR и вылетал.
Автовекторизация — это вообще сложный и спорный вопрос. ) Например в C++ это здоровенная и очень сложная часть компилятора. Но при этом срабатывающая далеко не всегда. И редко когда генерирующая идеальный код (в отличие от остальной кодогенерации, которую человеку уже крайне сложно превзойти). На мой взгляд её основной бонус в бесплатном автоматическом ускорение всего приложения, а не в использование для исправления узких мест.
При этом на C++ есть решения, позволяющие писать реально эффективный SIMD код не руками. Обычно такое пишется через создание нескольких базовых "builtin" функций на ассемблере. И потом высокуровневой генерацией кода на базе этих функций под пользовательские типы с помощью метапрограммирования.
_>>Контроль работает где-то на уровне потенциального доступа к указателям. Так что если есть шанс модифицирующего доступа, то оптимизации не будет. S>Ну вот то-то и оно. const, получается, нужен программисту — чтобы он нечаянно не занёс модификации туда, куда не надо. S>Ну и, потенциально, для кросс-модульных оптимизаций.
Да, когда мы сейчас выбираем себе какие-то инструменты (и даже возможно потом "защищаем" их на форумах ), то обычно это выбор лучшего из предложенного на рынке. Но совсем не реально удовлетворяющего всем пожеланием. Ну хотя не буду говорить за всех, может какого-нибудь программиста на JS и устраивает абсолютно всё. Но лично для меня, языка удовлетворяющего всем пожеланиям, не видно даже на горизонте...
Здравствуйте, samius, Вы писали: A>>Вот что подумалось. Функции исполняются грязным исполнителем. Тут вопрос в том, влияет ли состояние исполнителя на результат foo. Грязные уши исполнителся торчат из функции GetHashCode у массивов, именно поэтому foo недетерминирована. Результат GetHashCode зависит от адреса только что выделенного массива, а это случайная величина. Неявно вызываемый аналог malloc(SIZE) является недетерминированной функцией и влияет на результат foo. S>Дело не в исполнителе. Даже если мы будем память выделять в бумажной тетрадке, сама постановка задачи подразумевает что мы не должны выдать два байта в одном адресе. Есть задачи, где не важно, где именно выделен байт, им важно лишь содержимое. Для них выделение можно считать чистым. Потому я и настаиваю, что прежде чем заниматься анализом чистоты, нужно договориться, какие именно изменения глобального состояния мы будем считать грязными. И вполне может быть что для одной функции будет определен один набор, для соседней — другой.
Обычный подход — такой, что важными считаются эффекты, обнаружимые при помощи некоторого подмножества нашего языка/рантайма.
В первом приближении это нетрудно получить: ну, вот есть у нас, допустим, некоторое "публичное" разделяемое состояние. Изменения в нём "видимы" для гражданского кода. Вот они-то и являются побочными эффектами.
Если мы хотим математической строгости, то никакого другого состояния у нас и нет.
Ну, вот пример мира, оборудованного "консолью", я уже приводил.
Можно расширить этот мир до abstract memory, которая представлена в виде mutable hashmap.
Тогда одна функция может "положить" в этот мир значение Memory["Hello"]="World!", а другая — соответственно, достать.
Даже если мы сделаем мир immutable, а функции будут всего лишь принимать его в аргументах, и возвращать трансформированную версию, мы всё равно сможем отличать чистые функции от грязных.
Ну, то есть математически они будут вполне себе чистыми, т.к. возвращаемые значения будут зависеть строго от аргументов; но для практической пользы мы как раз будем называть чистыми только те функции, которые не занимаются трансформацией вот этого мира.
Всё будет посложнее, если мы начнём приделывать взаимодействие с настоящим миром — банально, функция читающая системное время, даёт нам способ детектировать порядок выполняемых операций без прямой зависимости.
Но опять же, я бы начал с другого конца — все эти термины важны только в той мере, в которой мы их используем. Классический RPC проектировали идеалисты, поэтому в нём была важна похожесть на C API, а не практическая полезность.
Поэтому в нём нет никаких различий между unsafe, safe, idempotent методами. А вот REST проектировали люди, которых интересовало построение надёжных систем поверх ненадёжных коммуникаций. Поэтому там есть вот эти варианты.
При этом, скажем, понятия детерминизма в REST нету. В его модели из того, что какой-то глагол будет детерминированным, пользу извлечь не удастся.
Вот и с чистотой — она нам полезна только тогда, когда у нас есть какой-то вычислитель с различными стратегиями исполнения в зависимости от чистоты/нечистоты функции.
В зависимости от реализации этого исполнителя нам может быть интересно различать функции "читающие" мир, и функции "пишущие" в мир. А может — неинтересно. Как я понимаю, в Хаскеле нет разницы между такими видами грязи.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
).
), то обычно это выбор лучшего из предложенного на рынке. Но совсем не реально удовлетворяющего всем пожеланием. Ну хотя не буду говорить за всех, может какого-нибудь программиста на JS и устраивает абсолютно всё. Но лично для меня, языка удовлетворяющего всем пожеланиям, не видно даже на горизонте...
