VPF::Imperative v. Functional - Форум программистов

setq

Дата 2.11.2005, 22:41 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

собственно "религиозная война" по сабжу проходит в данный момент здесь.

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

* скорость разработки
* производительность
* читаемость и элегантность
* ещё чего-нибудь

Void

Дата 2.11.2005, 22:55 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(setq @ 3.11.2005, 00:41)

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

Зачем ограничиваться двумя языками? Сколько найдется желающих реализовать тестовую задачу, столько и языков. Функциональный мир тоже довольно разнообразен.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

LSD

Дата 2.11.2005, 23:55 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538

Цитата(setq @ 2.11.2005, 22:41)

* скорость разработки

Чтобы корректно сравнить данный параметр, надо вести разработку двумя командами разработчиков равными по уровню, и задание должно быть достаточно объемным на пол года год. А когда пишет один человек, да еще в свободное от работы/учебы время, сравнивать этот параметр нельзя. Да и уровень знания языка разный, что опять оказывает влияние.

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

Cr@$h

Дата 30.1.2006, 02:45 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Профиль
Группа: Участник Клуба
Сообщений: 1693
Регистрация: 3.4.2005
Где: Санкт-Петербург, Россия

Репутация: нет
Всего: 41

Цитата(setq @ 2.11.2005, 23:41

)

скорость разработки

Слмневаюсь в объективности, будут большие погрешности. А при большом интервале еще больше внешних условий и причин.
Лучше сравнить, сколько кода содержит программа. Она не должна быть большой.

Void

Дата 30.1.2006, 19:24 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(Cr@$h @ 30.1.2006, 04:45

)

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

Тот еще критерий... Краткость кода не всегда является однозначным преимуществом. Классический антипример — Perl. То есть нужен разумный баланс с понятностью и эффективностью. Правда, проблема с первым — весьма субъективный параметр smile

Ну так как, никто еще не придумал сравнительных тестов? smile

Я могу найти тесты заведомо выигрышные как для ИЯ, так и для ФЯ. А вот нейтральные что-то не получается smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Cr@$h

Дата 30.1.2006, 19:38 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Цитата(Void @ 30.1.2006, 20:24

)

Тот еще критерий... Краткость кода не всегда является однозначным преимуществом.

Я не про преимущество. Вообще, "птичие" языки не очень люблю за их }}}}. Просто можно сравнить объективно по громоздкости кода.

LSD

Дата 30.1.2006, 21:26 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538

Цитата(Cr@$h @ 30.1.2006, 19:38

)

Просто можно сравнить объективно по громоздкости кода.

Это как?

--------------------

Void

Дата 30.1.2006, 21:36 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

LSD
Методом экспертных оценок, гы smile

На самом деле объективно сравнивать тут не получится по любому, да мы ведь вроде бы и не преследуем такие цели?

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Cr@$h

Дата 30.1.2006, 23:03 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Одно из решений может оказаться громоздким, значит язык для этого не подходит.

LSD

Дата 31.1.2006, 11:52 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: нет
Всего: 538

Цитата(Void @ 30.1.2006, 21:36

)

Методом экспертных оценок, гы

Где здесь в эксперты записывают? smile

Цитата(Void @ 30.1.2006, 21:36

)

А тогда какие цели преследуем? Очередные "религиозные войны"?
Я понимаю, что полной объективности мы не получим, но попытаться стоит.

--------------------

Void

Дата 31.1.2006, 12:07 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Объективно нам удастся сравнить только быстродействие: эффективность по времени и по памяти. Все остальные метрики субъективны. Можно конечно ещепосчитать число строк, число лексем, отношение времени, потраченного программистом к норме осадков в Зимбабве... smile

Субъективные выводы каждый сделает для себя сам.

Цитата(LSD @ 31.1.2006, 13:52

)

Где здесь в эксперты записывают?

Здесь и записывают smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Cr@$h

Дата 26.2.2006, 00:05 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Что-то глухо как-то, а? Для начала, думаю, нужна задачка незатейливая...

Void

Дата 27.2.2006, 23:21 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Ну хорошо, держите задачку, не знаю правда, насколько незатейливую smile

Реализовать ассоциативный контейнер (map, dictionary) на базе AVL-деревьев.
Поскольку все тестируемые языки, я так понимаю, либо поддерживают статический полиморфизм, либо динамически типизированы, контейнер должен быть универсален — пользователь должен иметь возможность задать тип ключа и значения и метод сравнения ключей.
Обязательная функциональность: вставка и удаление элемента, проверка на наличие заданного ключа, перебор всех ключей по порядку.
Посмотрим на объем реализации, оценим эффективность по времени и по памяти; заодно сравним mutable vs immutable структуры данных и насколько велик проигрыш последних.

Объем кода около 100-300 строк. Чтобы реально что-то замерять, меньше не пойдет. Если хотите сначала просто прицениться к языкам, можно придумать что-нибудь попроще... Правда пока в голову ничего не идет. Не копировать же тесты с shootout smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 27.2.2006, 23:46 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

ТУПОЙ вопрос по теме можно? smile

Какие именно языки у нас функциональные. Названия.

Void

Дата 28.2.2006, 00:03 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Цитата(setq @ 28.2.2006, 01:46

)

Какие именно языки у нас функциональные. Названия.

Тебе все перечислять? smile

Википедия знает много.
Имеет место некоторая путаница. Есть языки чисто функциональные, т.е. без побочных эффектов, например, Haskell, Clean и... все остальные smile

Т.е. причислять язык к сонму функциональных или нет — вопрос не совсем формальный. Например, ML-оиды привыкли считать функциональными, хотя в них есть полноценные императивные возможности, а Python или Ruby — императивными, хотя там есть замыкания и функции как first-class values.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Cr@$h

Дата 28.2.2006, 20:02 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

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

ДобренькийПапаша

Дата 28.2.2006, 21:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1278
Регистрация: 14.1.2006
Где: г.Москва

Репутация: нет
Всего: 7

А правда то, что 90% прог написаны на С++?

--------------------

Меня зовут Себастьян Парейра, торговец чёрным деревом.

Cr@$h

Дата 28.2.2006, 21:12 (ссылка)

(нет голосов)

Загрузка ...

Исследователь

Конечно, нет. Спасибо за флуд темы.

setq

Дата 2.3.2006, 17:03 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Выкладываю реализацию словарей на базе AVL деревьев на языке Hope.

Цитата(Wikipedia)

Hope is a small functional programming language, with strong polymorphic typing, algebraic data types, pattern matching, and higher-order functions. It has call-by-pattern evaluation. The first implementation of Hope was strict, but since that one there have been lazy versions and strict versions with lazy constructors. Hope is purely functional.

На языке написаны примеры к книге "Функциональное программирование" Филда & Харрисона, так что я его немного знаю.

Подкупило слово small smile

Модуль с функциями для списков:

Код


! list.hop
! list related functions



typevar a ;

dec break : list(a) # num -> list(a) # list(a) ;
! break([x1,...xn], i) <= [x1,...xi], [x(i+1),...xn]
--- break(P, 0) <= [], P ;
--- break(p::P, succ(n)) <=
  p::Q, R where
    Q, R == break(P, n) ;


dec break2 : list(a) -> list(a) # list(a) ;
--- break2(P) <= break(P, length(P)/2) ;


! there must be a standard implementation
! of sort()... anyway

dec merge : list(a) # list(a) -> list(a) ;
--- merge([], Q) <= Q ;
--- merge(P, []) <= P ;
--- merge(p::P, q::Q) <=
  if p=<q then p::merge(P, q::Q) else
  q::merge(p::P, Q) ;


dec sort : list(a) -> list(a) ;
--- sort([]) <= [] ;
--- sort(P) <=
  let Q, R == break2(P) in
    merge(sort(Q), sort(R)) ;

"Деревья":

Код


! tree.hop
! tree and AVL tree data types

use list ;



typevar a ;


data tree(a) == Tip ++ Node(tree(a) # a # tree(a)) ;


dec find_node : tree(a) # a -> tree(a) ;
--- find_node(Tip, _) <= Tip ;
--- find_node(T, p) <=
  let Node(lt, p', rt) == T in
    if p<p' then find_node(lt, p) else
    if p=p' then T else
    find_node(rt, p) ;  ! if p>p'


dec flatten : tree(a) -> list(a) ;
--- flatten(Tip) <= [] ;
--- flatten(Node(l, p, r)) <= flatten(l) <> [p] <> flatten(r) ;



type avl(a) == tree(a) ;


dec toAvl : list(a) -> avl(a) ;
dec _toAvl : list(a) -> avl(a) ;

--- _toAvl([]) <= Tip ;
--- _toAvl(P) <=
  let Q, r::R == break2(P) in
    Node(_toAvl(Q), r, _toAvl(R)) ;
--- toAvl(P) <= _toAvl(sort(P)) ;

Модуль с типом Association (Как в Smalltalk'е. Почти.)

Код


! association.hop
! association data type (Blank -- is kind of
! empty constructor for comparison purposes)



typevar a, b ;


infix ## : 9 ;
data assoc(a, b) == Blank(a)  ++  a ## b ;


! association is compaired by keys
--- compare(Blank(p), Blank(q)) <= compare(p, q) ;
--- compare(Blank(p), q ## _) <= compare(p, q) ;
--- compare(p ## _, Blank(q)) <= compare(p, q) ;
--- compare(p ## _, q ## _) <= compare(p, q) ;

Собственно, модуль с определением словаря:

Код


! dictionary.hop
! dictionary data type

use association, tree ;



typevar a, b ;

type dict(a, b) == avl(assoc(a, b)) ;


dec add : dict(a, b) # a # b -> dict(a, b) ;
--- add(D, k, v) <= toAvl(k##v :: flatten(D)) ;


dec has : dict(a, b) # a -> bool ;
--- has(D, k) <= find_node(D, Blank(k)) = Tip ;


dec del : dict(a, b) # a -> dict(a, b) ;
--- del(D, k) <= toAvl(filter(flatten(D), lambda x => x=Blank(k))) ;


dec get : dict(a, b) # a -> b ;
--- get(D, k) <=  v where Node(_, _ ## v, _) == find_node(D, k) ;


dec toDict : list(a # b) -> dict(a, b) ;
--- toDict(P) <= toAvl(map(P, lambda(x, y) => x ## y)) ;

С сессией пользователя у меня проблемы — не помню я как shell у hop'а выглядит, а UNIX'а под рукой нету. Так что даю только начальные предложения:

Код


use dictionary ;

! let's extend standard function compare()
! to compare strings (because i'm not sure
! wether Hope can do it)

--- compare([], []) <= EQUAL ;
--- compare(p::P, []) <= GREATER ;
--- compare([], q::Q) <= LESS ;
--- compare(p::P, q::Q) <=
  if p>q then GREATER else
  if p=q then compare(P, Q) else
  LESS ;  ! if p<q


: myList <= [("Beatles", "Because"),
             ("Distillers", "Black Heart"),
             ("My Bloody Valentine", "Soon"),
             ("Portishead", "Roads"),
             ("Blonde Redhead", "Falling Man")] ;

: myDict <= toDict(map(myList, lambda(x, y) => (y, x))) ;

: get(myDict, "Black Heart") ;
"Distillers" : list(char)

Наверно так.
Повторюсь, не прогонял, не тестировал. Готов в принципе по первому требованию установить себе FreeBSD и отладить...

Интересно... Сколько всё-таки % прог написано на C++? smile

Это сообщение отредактировал(а) setq - 3.3.2006, 21:43

Void

Дата 2.3.2006, 21:17 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

setq, увидев столь краткий код, я основательно перепугался и подумал, что пропустил в Hope что-то очень интересное. Но, оказывается, ты реализовал обычные бинарные деревья. Или я все-таки потерял где-то в этих 84 строчках балансировку? smile

Цитата(setq @ 2.3.2006, 19:03

)

Сколько всё-таки % прог написано на C++?

С точки зрения дзен, гораздо интереснее вопрос: сколько еще ненаписанных программ не будет написано на C++? smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 3.3.2006, 18:17 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Цитата(Void @ 2.3.2006, 21:17

)

Но, оказывается, ты реализовал обычные бинарные деревья.

Я это самое... того... список забыл отсортировать smile

Задумка была такая:
# Берём дерево
# Делаем из него список
# Модифицируем
# Сортируем
# Выращиваем обратно -- функцией toAvl()

В соответствии с принципом "что, а не как", никто не гарантирует, что это оптимально smile

Void

Дата 3.3.2006, 20:08 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

setq, оригинально smile

Цитата(setq @ 3.3.2006, 20:17

)

никто не гарантирует, что это оптимально

Гонять списки туда и обратно + O(N) сплайсинг списка по номеру элемента… Да, пожалуй ты прав smile

В ближайшие дни постараюсь выкроить часик и дать реализацию на OCaml и, возможно, на C++ или C#.

P.S. Ты бы помимо красных патчей, сам код поправил. А то словно опасаешься инсинуаций каких-то smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

setq

Дата 3.3.2006, 21:51 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Код подправил и вставил сортировку в функцию toAvl().

Цитата(Void @ 3.3.2006, 20:08

)

В ближайшие дни постараюсь выкроить часик и дать реализацию на OCaml и, возможно, на C++ или C#.

Окей. Ждём. smile

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Разное тестирование \| Следующая тема »