Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 1352 21-10-2006 16:38 | |
Ответ на »сообщение 1351« (Geniepro)
___________________________
Отлично! Выложите сжатый текстовый тест файл куда нибудь на рапидшару.
Я попробую у себя.
Во первых у меня памяти 2 гига, так что можно попробовать ByteString вместо Lazy
Во вторых попробую дать ключ SMP на два процессора.
№ 1351 21-10-2006 16:32 | |
Ответ на »сообщение 1349« (Jack Of Shadows)
___________________________
Переделал программу на со String на ByteString.
Вначале попытался использовать тип ByteString из модуля Data.ByteString, но при попытке обработки 2-гигабайтного файла память переполнилась (ОЗУ 512 МБт), и программа дала сбой, хотя на мелких файлах работала...
Пришлось использовать тип ByteString из модуля Data.ByteString.Lazy. Получил двухкратное ускорение по сравнению со String.
GHC 6.6 ByteString - 128 cек
GHC 6.6 String - 253 cек
GHC 6.5 String - 230 cек
Напомню, на C# - 52 сек.
ByteString в GHC 6.5 нет, так что сравнить не удалось...
Может быть, моя программа не оптимальна, можно улучшить её производительность?
import IO
import qualified Data.ByteString.Lazy as B
import qualified Data.Word as W
main = do fromHandle <- openFile "E:\\fiblist.out" ReadMode
contents <- B.hGetContents fromHandle
putStr "Number of commas = "
print (calcCommas contents)
hClose fromHandle
calcCommas :: B.ByteString -> Int
calcCommas s = calcCommast s 0
where
calcCommast :: B.ByteString -> Int -> Int
calcCommast s v = if B.null s then v else
if B.head s == toEnum (fromEnum ',')
then calcCommast (B.tail s) (v+1)
else calcCommast (B.tail s) v
№ 1350 20-10-2006 19:10 | |
Ответ на »сообщение 1348« (Geniepro)
___________________________
Увы, маленький патч. Я не учёл переход с Юлианского календаря на Григорианский, поэтому получились ошибки в определении дней недели, да ещё и 13 лишних дней в список дат попали...
Но проблема в том, что разные страны переходили на Григорианский календарь (новый стиль) в разные века... Я взял в качестве этой даты 31 янв. 1918 г. -> 14 фев. 1918 г.
Теперь правильно работает не только после 1918 г, но и до него.
13 oct 1430, 13 mar 1500, 13 jan 1520, 13 jan 2006, 13 oct 2006,
13 may 2011, 13 apr 2012, 13 dec 2013, 13 feb 2032, 13 jan 2051,
Исправление: -- Проверка возможности такой даты
--
isValidDate (y, m, d) = if y == 1918 && m == 2 && d < 14 then False
else d <= ((daysInMonth !! (m-1)) +
if m == 2 && isLeapYear then 1 else 0)
where
-- Янв Фев Мар Апр Май Июн Июл Авг Сен Окт Ноя Дек
daysInMonth = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ]
-- Дата перехода России с Юлианского календаря на Григорианский :
-- после 1918-I-31, ср, сразу идёт 1918-II-14, чт.
--
isLeapYear = if (y < 1918) || (y == 1918 && m == 1) then (y `rem` 4) == 0
else isLeap1918
isLeap1918 = if (y `rem` 4) /= 0 then False
else if (y `rem` 400) == 0 then True
else (y `rem` 100) /= 0
-- Список дней недели, начиная с 1 янв. 1 г.
-- Будем считать, что 1 янв. 1 г. был субботой (по Юлианскому календарю)
--
weekDays = cycle [ Sat, Sun, Mon, Tue, Wed, Thu, Fri ]
Ответ на »сообщение 1349« (Jack Of Shadows)
___________________________
JoS> А как насчет предыдущей программы по подсчету запятых ?
JoS> Было бы интересно узнать какая будет разница от замены String на ByteSTring
Я пока не разобрался с ByteString, просто так вроде не переведёшь.
Попробую завтра разобраться и проверить.
№ 1349 20-10-2006 13:51 | |
Ответ на »сообщение 1348« (Geniepro)
___________________________
А как насчет предыдущей программы по подсчету запятых ?
Было бы интересно узнать какая будет разница от замены String на ByteSTring
№ 1348 20-10-2006 13:31 | |
Смастерил программку, которую, вообще-то, надо было бы приурочить к прошлой пятнице, 13 октября.
Ну да ладно, лучше поздно, чем никогда... :-))
Прожка печатает даты, которые приходятся не просто на пятницу, 13-ое, но ещё и в которых сумма цифр равна 13.
Например, 13 окт. 2006 г. -> 1+3 + 1+0 + 2+0+0+6 = 13
Таких дат не так уж и много. В этом году, правда, было две такие пятницы (в январе и в октябре), зато перед этим было аж в 1511 году (и тоже в январе и в октябре :)) Следующая будет в мае 2011 г.
module Main where
type Date = (Int, Int, Int)
data WeekDay = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving (Show, Eq)
-------------------------------------------------------------------------------
--
-- Список дат с днями недели с 1 янв. 1 г. по 31 дек. 3000 г.
--
dateList :: [(Date, WeekDay)]
dateList = zip [(y, m, d) | y <- [1..maxYear],
m <- [1..12],
d <- [1..31],
isValidDate (y, m, d)] -- Даты
weekDays -- Дни недели
where
-- Максимальный интересный для нас год
--
maxYear = 3000
-- Проверка возможности такой даты
--
isValidDate (y, m, d) = d <= ( (daysInMonth !! (m-1)) +
if m == 2 && isLeapYear y then 1 else 0 )
where
-- Янв Фев Мар Апр Май Июн Июл Авг Сен Окт Ноя Дек
daysInMonth = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ]
isLeapYear y | (y `rem` 4 ) /= 0 = False
| (y `rem` 400) == 0 = True
| otherwise = (y `rem` 100) /= 0
-- Список дней недели, начиная с 1 янв. 1 г.
-- Будем считать, что 1 янв. 1 г. был понедельник (по нынешнему календарю)
--
weekDays = cycle [ Mon, Tue, Wed, Thu, Fri, Sat, Sun ]
-------------------------------------------------------------------------------
--
-- Список дат, приходящихся на пятницу 13-ое число :-)
--
fridays13List :: [Date]
fridays13List = map fst (filter (\((_,_,d), w) -> d == 13 && w == Fri) dateList)
-------------------------------------------------------------------------------
--
-- Список дат, приходящихся на пятницу 13-ое число,
-- и сумма цифр которых равна 13 [Бррр! Ужжассс!!! :-))]
--
date13List :: [Date]
date13List = filter isDate13 fridays13List
where
isDate13 (y, m, d) = (sumDigs y + sumDigs m + sumDigs d) == 13
sumDigs 0 = 0
sumDigs n = (n `rem` 10) + sumDigs (n `div` 10)
-------------------------------------------------------------------------------
--
-- Печатаем в таком виде:
--
-- 13 jan 1511, 13 oct 1511, 13 jan 2006, 13 oct 2006, 13 may 2011,
-- 13 apr 2012, 13 dec 2013, 13 feb 2032, 13 jan 2051, 13 oct 2051,
--
main = printDates date13List 5 5
where
printDates :: [Date] -> Int -> Int -> IO ()
printDates [ ] _ _ = putStr "\n"
printDates (x:xs) n 1 = do putStrLn (showDate x)
printDates xs n n
printDates (x:xs) n k = do putStr (showDate x)
printDates xs n (k-1)
showDate :: Date -> String
showDate (y, m, d) = showDay d ++ (month !! (m-1)) ++ showYear y ++ ", "
where
showDay d = (if d < 10 then " " else "") ++ (show d)
showYear y = drop ((length sy) - 4) sy where sy = " " ++ show y
-- Почему трансляторы Хаскелла не любят русских букв? :-(
--
month = [ " jan ", " feb ", " mar ", " apr ", " may ", " jun ",
" jul ", " aug ", " sep ", " oct ", " nov ", " dec "]
Вот такой вот " just for fun" :o)
№ 1347 16-10-2006 13:09 | |
Ответ на »сообщение 1346« (Geniepro)
___________________________
Вместо String используйте Data.ByteString
String они не трогали для совместимости.
№ 1346 16-10-2006 11:51 | |
Услышав, что в GHC 6.6 сильно улучшена работа со строками, и вообще быстродействие программ, попробовал сравнить работу со строками, символами и текстовыми файлами с С#.
В качестве входных данных взял файл размером 1.95 ГБт; этот файл получился при попытке распечатать бесконечный список чисел Фибоначчи (прервал попытку, так как надоело ждать переполнения памяти), то есть содержал символы '[', цифры '0'..'9' и запятые...
Задача заключалась в подсчёте этих запятых.
Код на Хаскелле: import IO
main = do fromHandle <- openFile' "E:\\fiblist.out" ReadMode
contents <- hGetContents fromHandle
putStr "Number of commas = "
print (calcCommas contents)
hClose fromHandle
openFile' :: String -> IOMode -> IO Handle
openFile' name mode =
do catch (openFile name mode)
(\_ -> error ("Cannot open "++ name ++ "\n"))
calcCommas :: String -> Int
calcCommas l = calcCommas' l 0
where calcCommas' :: String -> Int -> Int
calcCommas' [] v = v
calcCommas' (',':xs) v = calcCommas' xs (v+1)
calcCommas' ( _ :xs) v = calcCommas' xs v
Код на C#: using System;
using System.IO;
namespace СalcCommas
static void Main(string[] args)
f = DateTime.Now;
Console.WriteLine("Number of commas = , time = msec", num, Time(f) - Time(s));
}
}
catch (Exception e)
}
}
}
Интересные результаты получил: программа на C# отработала за 52 сек, на Хаскелле за 255 сек.
При этом интересная статистика у проги на Хаскелле (запускал с параметрами +RTS -sstderr -RTS) :
Полное время работы: 255 сек,
чистое время работы: 157 сек (62% всего времени),
время, потраченное на выделение памяти: 98 сек (38% всего времени),
время, потраченное на сборку мусора: 4.8 сек ( 2% всего времени),
было выделено памяти аж 43 ГБт...
Интереса ради протестил предыдущую версию GHC - 6.5:
Полное время работы: 230 сек,
чистое время работы: 150 сек (65% всего времени),
время, потраченное на выделение памяти: 80 сек (35% всего времени),
время, потраченное на сборку мусора: 4.5 сек ( 2% всего времени),
было выделено памяти 43 ГБт...
Что-то наоборот, новый компилятор выдал код, который стал медленнее, чем у старого... :-((
Ну и в пять раз медленнее, чем на C#...
ЗЫ. Тестил на: Celeron 1.7 GHz, AsRock P4i65PE, RAM 512 MB DualDDR266, HDD Seegate Barracuda 80 GB
Файл был один и тот же; возможно, фрагментирован, но это не так важно...
ЗЗЫ. Интересно, насколько сильно замедляет программу на Хаскелле сбор статистики?
№ 1345 16-10-2006 00:18 | |
Ответ на »сообщение 1344« (Geniepro)
___________________________
...но, по крайней мере, не хуже Менуэта... :-))
Ну, вообще-то, справедливости ради нужно заметить, что MenuetOS - система с вытесняющей многозадачностью, а в House многозадачностью, похоже, и не пахнет...
Если задать, например, расчёт, скажем, 40-го числа Фибоначчи (есть там такая апплетка, куда ж без этих чисел :0)), то вся система стопорится, даже мышь не двигается.
Странно, я думал, раз использован Concurent Haskell, значит, система многопотчна, наверное... :-?
№ 1344 15-10-2006 06:54 | |
Haskell User's Operating System and Environment
( http://programatica.cs.pdx.edu/House/ )
Демонстрационная операционная система, написанная на Хаскелле, работает на голом железе.
"A Principled Approach to Operating System Construction in Haskell"
http://www.cse.ogi.edu/~hallgren/ICFP2005/
Грузится с дискетки, имеет графический интерфейс (мышь, окна, кнопки...), может отображать GIF-картинки, имеет минимум драйверов (клава, мышь, сеть, сетевые протоколы)
Образ дискеты: http://programatica.cs.pdx.edu/House/download/hOp-0.8.flp
Конечно, до комерческих систем (Вин/Лин) далеко, но, по крайней мере, не хуже Менуэта... :-))
ЗЫ. Хаскелл - вот на чём надо делать Русскую ОС, а вы всё - Паскаль, Си... :-))
№ 1343 13-10-2006 17:17 | |
Ответ на »сообщение 1342« (Geniepro)
___________________________
Еще не ставил.
Найду время попозже, попробую поиграться.
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|