Здравствуйте, FR, Вы писали:

FR>Ты похоже главного не заметил это модуль для Camlp4

Нет, это я, разумеется, заметил. И главное я тоже заметил — Hashtbl. Вы всерьез элементы последовательности собираетесь в хештаблице мемоизировать? Ах да, я же забыл — производительность не нужна.

FR>так что поможет, притом практически без усложнений в прикладном коде.

Вы не рекламные лозунги выдавайте, а перепишите код — там три строчки всего. А потом посмотрим.

Здравствуйте, FR, Вы писали:

FR>Это не оговорка.
FR>Ленивость она не только плюшки дает и не всегда лучший вариант.

Ленивость дает не только плюшки, разумеется. Она дорого обходится для разработки реализации языка, требует серьезно переменить мышление и не бесплатна в смысле производительности. Но для поддержки ФП от ленивости одни плюсы.

FR>Хотя выразительность может обеспечить не только ленивость, например и term rewriting + динамика как в Pure
FR>Или макросы + динамика как в схемах и лиспах.

Отлично, давайте здесь еще и холивор динамика vs. статика устроим. Только мне тогда в отпуск уходить придется — на работу времени не останется.

Здравствуйте, Klapaucius, Вы писали:

K>Нет, это я, разумеется, заметил. И главное я тоже заметил — Hashtbl. Вы всерьез элементы последовательности собираетесь в хештаблице мемоизировать? Ах да, я же забыл — производительность не нужна.

Да ладно сколько всего этих простых чисел-то.

FR>>так что поможет, притом практически без усложнений в прикладном коде.

K>Вы не рекламные лозунги выдавайте, а перепишите код — там три строчки всего. А потом посмотрим.

Пока лень, да и надо хардкорный С++ из головы флудом вытеснить

Здравствуйте, Klapaucius, Вы писали:

K>Ленивость дает не только плюшки, разумеется. Она дорого обходится для разработки реализации языка, требует серьезно переменить мышление и не бесплатна в смысле производительности. Но для поддержки ФП от ленивости одни плюсы.

Судя по pure у term rewriting плюсов не меньше.

FR>>Хотя выразительность может обеспечить не только ленивость, например и term rewriting + динамика как в Pure
FR>>Или макросы + динамика как в схемах и лиспах.

K>Отлично, давайте здесь еще и холивор динамика vs. статика устроим. Только мне тогда в отпуск уходить придется — на работу времени не останется.

Ты мелко смотришь, выше же есть гораздо более сильное колдунство

Здравствуйте, Klapaucius, Вы писали:
K>Сезон синтаксического оверхеда был бы, если бы сравнивались функции отличающиеся только синтаксически, т.е.

K>

K>let rec map f = function
K>    [] -> []
K>  | a::l -> let r = f a in r :: map f l
K>

K>Но я-то как раз сравниваю функции, главные различия между которыми совсем не синтаксические.

а так не будет проще и читабельнее ?

 let rec map f = function
    | [] -> []
    | x :: xs -> f x :: map f xs;;

Или вообще

let map = List.map

У меня вообще всего одна строчка

Здравствуйте, Klapaucius, Вы писали:

DM>>Проблема в том, что долгое время над окамлом работало полчеловека из INRIA, комьюнити никак не участвовало в разработке компилятора и оптимизаций в нем по чисто бюрократическим причинам.

K>Кстати, интересный вопрос, как думаете, почему самым популярным ML-ем стал окамл, а не SML, если борократы комьюнити улучшать реализацию не давали?

Я не знаю. Возможно, потому что у него рантайм хороший. На тормоза SML тут выше жаловались. А вы как думаете?

K>Что, к тому времени, когда NEC выпустил mlton на свободу (это ведь был где-то 99-2000 год?) комьюнити уже слишком большую энерцию набрало, чтоб переметнуться?

Гугл по запросу ocaml vs mlton одной из первых ссылок дал такую:
http://mlton.org/pipermail/mlton/2000-October/017987.html
Там окамл их всех делает. В других местах жалуются, что скорость компиляции у mlton удручающая.

K> Нет, я отдаю себе отчет в том, что ocaml и sml языки не особенно похожие, но основные принципы-то у них общие. Это не хаскель, где надо сознание перестраивать и все что выучил — обратно разучивать.

Да вроде весьма похожи, братья практически.

Здравствуйте, D. Mon, Вы писали:

DM>Там окамл их всех делает. В других местах жалуются, что скорость компиляции у mlton удручающая.

Это да реальный ужас, С++ с рекурсивными шаблонами отдыхает. Главное даже мелкие программки очень
медленно компилировались.

Здравствуйте, Klapaucius, Вы писали:

K>Вы не рекламные лозунги выдавайте, а перепишите код — там три строчки всего. А потом посмотрим.

open Batteries_uni
open Std
open Enum
open Printf

let primes n =
  let primes' = Dllist.create 2 in
  let is_prime x = Dllist.enum primes' |> take_while (fun i -> i*i <= x) |> for_all (fun i -> (x mod i) != 0) in
  [? Dllist.get (Dllist.prepend primes' a) | a <- 2 -- n; is_prime a ?]
  
let _ = printf "%d\n" (hard_count (primes 5_000_000))

Отрабатывает у меня примерно за 4.5 секунды.
Код правда не функциональный (при желании можно похаливарить на тему одиночной мутабельной переменной),
но сама функция вполне чистая.

DM>>Где? Модуль вектора? Нет там никакого стека.

K>Если алгоритм обходится только стековыми операциями — он использует стек. Не очередь, не словарь, не последовательность. Стек. Для того, чтоб посчитать модуль вектора — стековых операций достаточно. Но вам их, по какой-то причине, не достаточно — вот я и спрашиваю, в который раз уже, что именно вам не хватает?

заболевание похоже на хаскель головного мозга

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

не хватать будет скорости (либо памяти, если компенсировать это памятью), т.к. обращение к элементу будет за О(М) вместо О(1)

при этом именно ТВОЯ обязанность доказывать, что любой алгоритм, использующий вычисление модуля вектора на стеках будет не медленнее алгоритма на массивах, т.к. ТЫ утверждаешь, что "стековых операций достаточно"

несмотря на то, что это твоя обязанность, я приведу один намек, почему ты не прав

допустим, у нас есть вектор, модуль которого мы хотим считать в 2 потока (раз уж речь про ФП, то потоки самое то)

вариант с массивом: поделить массив на 2 части

element* middle = begin+(end-begin)/2;

и отдать каждую потоку, cчитая там квадрат модуля, затем

return sqrt(module_sq_1+module_sq_2);

если ты будешь снимать со стека элементы, то для того, чтобы разделить его на 2 стека, и скормить 2 потокам, тебе придется прокачать через процессор вдвое больше памяти, а поскольку умножение (особенно с SSE) быстрое, ты фактически будешь работать в 2 раза медленнее (memory bound, короче)

есть еще вариант "снимать по одному элементу и отдавать налево и направо", но навскидку он будет еще тормознее, если не сводится к предыдущему путем "наделать много работы, а затем..."

кроме того, еще раза в 2 ты вероятно тормознешся из-за перерасхода памяти, если хаскель не умеет оптимизировать списки, кладя каждый новый элемент вслед за предидущим и не тратя место на указатель на следующий... кстати, он умеет это делать? для произвольных элементов, а не только для char?

насчет memory bound, которое может быть понято немного неверно -- уточняю:

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

это довольно близко к тому, что есть в реальности

Здравствуйте, Аноним, Вы писали:

А>при этом именно ТВОЯ обязанность доказывать, что любой алгоритм, использующий вычисление модуля вектора на стеках будет не медленнее алгоритма на массивах, т.к. ТЫ утверждаешь, что "стековых операций достаточно"

Это уже дебри пошли. Достаточно вспомнить, что "In computer science, a stack is a last in, first out (LIFO) abstract data type and linear data structure", и вектор определенно им не является.

DM>Это уже дебри пошли. Достаточно вспомнить, что "In computer science, a stack is a last in, first out (LIFO) abstract data type and linear data structure", и вектор определенно им не является.

слово "определенно" доказательством не является

можешь предложить свое доказательство, не такое сложное

кстати, в моем имеются ошибки, вот мы и посмотрим, найдет их Klapaucius или он диванный теоретик

Здравствуйте, D. Mon, Вы писали:

DM>Я не знаю. Возможно, потому что у него рантайм хороший. На тормоза SML тут выше жаловались. А вы как думаете?

Я сам не наю. У меня просто сложилось впечатление (не из личного опыта), что разработчики MLton охотнее идут на сотрудничество с комьюнити, и сформируйся активное комьюнити вокруг SML — всякие тормоза были бы уже чисто техническими проблемами. Ситуация "работало полчеловека" не сложилась бы. Ну и именно это и должно было положительно на популярность повлиять. SML в вузах изучают, в 90-е о нем было много книг написано. Несколько реализаций (хотя это можно и минусом посчитать).

DM>скорость компиляции у mlton удручающая.

Это еще очень мягко сказано.

DM>Да вроде весьма похожи, братья практически.

Ну, я же говорю — основа то у них общая. А вот в деталях они сильно различаются. Все что в одном делается так — в другом обязательно иначе.

Здравствуйте, Слоноежик, Вы писали:

С>а так не будет проще и читабельнее ?
С>

С> let rec map f = function
С>    | [] -> []
С>    | x :: xs -> f x :: map f xs;;
С>

Ну да, теперь можете считать оверхед. Но уж как-нибудь без меня.

С>Или вообще
С>

С>let map = List.map
С>

Это не реализация.

Здравствуйте, FR, Вы писали:

FR>Код правда не функциональный (при желании можно похаливарить на тему одиночной мутабельной переменной),

Одиночной? А по-моему тут кол-во переменных прямо пропорционально кол-ву простых чисел. Вообще, я считаю, что работа напрасно проделана: очевидно, что в данном случае можно и от рекурсии избавиться и изменяемую структуру данных использовать — вот только пример-то должен был продемонстрировать сложности с конвейером отличным от простого линейного.

Здравствуйте, FR, Вы писали:

FR>Судя по pure у term rewriting плюсов не меньше.

Не знаком с этим языком даже поверхностно — потому не могу ничего ответить. Когда составлю представление — прокомментирую.

Здравствуйте, <Аноним>, Вы писали:

А>не хватать будет скорости (либо памяти, если компенсировать это памятью), т.к. обращение к элементу будет за О(М) вместо О(1)

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

А>ccode
А>отдать каждую потоку
А>прокачать через процессор
А>SSE
А>хаскель

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

А>если хаскель не умеет оптимизировать списки, кладя каждый новый элемент вслед за предидущим и не тратя место на указатель на следующий... кстати, он умеет это делать? для произвольных элементов, а не только для char?

Нет, GHC так не делает.

Здравствуйте, Klapaucius, Вы писали:

K>Одиночной? А по-моему тут кол-во переменных прямо пропорционально кол-ву простых чисел. Вообще, я считаю, что работа напрасно проделана: очевидно, что в данном случае можно и от рекурсии избавиться и изменяемую структуру данных использовать — вот только пример-то должен был продемонстрировать сложности с конвейером отличным от простого линейного.

По моему пример должен был продемонстрировать выразительность кода, притом кода написанного в функциональнообразном ( )
стиле. Да доказываю твой тезис что ocaml неплохой императивный язык. Но с уточнением что код получается и по виду и по
стилю скорее функциональным.

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

open Batteries_uni
open Std
open Enum
open Printf

let primes n =
  let is_prime x = 
    let rec loop i = 
      if i * i <= x then 
        if (x mod i) = 0 then false 
        else loop (i + 1)
      else true
    in loop 2  
  in
  [? a | a <- 2 -- n; is_prime a ?]
  
let _ = printf "%d\n" (hard_count (primes 5_000_000))

особенно если сравнить с чисто функциональным:

open Batteries_uni
open Std
open Enum
open Printf

let primes n =
  let is_prime x = 2 -- x |> take_while (fun i -> i*i <= x) |> for_all (fun i -> (x mod i) != 0) in
  [? a | a <- 2 -- n; is_prime a ?]
  
let _ = printf "%d\n" (hard_count (primes 5_000_000))

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

#include <iostream>
#include <deque>

using namespace std;

bool is_prime(int x)
{
for(int i = 2; i * i <= x; ++i)
    if(x % i == 0)
        return false;

return true;
}

deque<int> primes(int n)
{
deque<int> result;

for(int i = 2; i <= n; ++i)
    if(is_prime(i))
        result.push_back(i);

return result;
}

int main()
{
deque<int> r = primes(5000000);

cout << r.size() << endl;
}

бьет что хаскель с его ленивостью и оптимизациями что окамл с кешированием.

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

а не проще ли тебе признать, что ты не прав?

объясни, какие такие алгоритмы "требуют" обращения к произвольному элементу в твоем понимании?

умело используя придуманную тобой "минимальность", можно *вообще* обойтись без обращения к произвольному элементу

вот так: вместо a[i] пишем get_element(a, i), где

int get_element(stack a, int i) {
  if( i==0 )
    return a.head();
  else
    return get_element(a.tail(), i-1);
}

если бы ты различал общерекурсивные алгоритмы от примитивно рекурсивных, тогда бы разговор о "минимальности" имел бы смысл, а сейчас он не имеет смысла БЕЗ указания скорости работы

K>Нет, GHC так не делает.

тогда похоже он томознет еще вдвое, как я и говорил

теперь на более глобальную тему

почему ты решил, что в *практическом* программировании map всегда должна выражаться через стековые операции, назовем их head и tail, или, что наверно то же, через forward iterator для обхода?

я считаю рациональным у любого контейнера иметь forward iterator для его обхода, но это не значит, что функция map не нужна, или что она не должна юзать random access iterator, *если он есть*

дальше, map может быть достаточно сложно устроена, чтобы она работала быстро, особенно в многопоточной программе

твои восторги "ах, мы можем написать map в две строчки!!!1111111" -- это какой-то детсад

если бы ты теоретически обосновал возможность свести map к стековым операциям (пусть даже и чуть расширенным) без потери производительности на современных архитектурах, тогда, может быть, имел бы смысл вообще забыть про map... может быть... а может и нет, т.к. вполне возможно

f(x) = map g x

точнее передает намерения программиста, чем непосредственная запись

f(x:xs) = g(x):f(xs)

которая вдобавок требует еще и второй строки для пустого списка