Ответ на »сообщение 708« (Денис Зайцев)
___________________________
Господа, вы неправы. При хвостовой оптимизации стек вообще не заполняется, хоть при ста миллиардах повторениях.
Приведенный вами код рекурсии не может быть оптимизирован.
Необходимым условием хвостовой оптимизации рекурсии является то что перед передачей вызова дальше, функция не должна иметь локальную переменную от которой зависит результат.
В вашем коде такая переменная есть. В результате хвостовая оптимизация невозможна.

Перепишите вашу рекурсивную функцию так чтобы она соответствовал требованиям хвостовой оптимизации.
И тогда можете гонять ее на любых числах.
А без хвостовой оптимизации не имеет значения ФЯ или ИЯ, стек все равно переполнится.

Ответ на »сообщение 708« (Денис Зайцев)
___________________________

Так что размер стека всё-таки нужно настраивать и в LispWorks.

Да, есть такая проблема...
Я тоже как-то попытался вычислить факториал 10 000 - CLisp, LispWorks, NewLisp дали сбой из-за переполнения стека...
А вот DrScheme с трудом, с натягом, но подсчитал даже факториал 100 000!

С Хаскеллем тоже не всё так круто, как хотелось бы: хотя и WinHugs и GHC справились с расчётом 10000!, с 100000! уже не сладили...

Факториал даже 10000 создаёт огромную нагрузку на стек - хотя всего 10 тыс вызовов, но с выходом из каждой функции на стек помещается всё большее и большее число, и все они хранятся на стеке...

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

DrScheme, например, активно использовал виртуальную память - HDDLed горел не переставая...

>>>Хотя рекурсия вроде концевая. Так что размер стека всё-таки нужно
>>>настраивать и в LispWorks.

Вы правы - чудес в нашем мире не бывает :)
Попробовал в Hugs факториал 10000.
Скушал!
Попробовал факториал 100000.
Stack overflow.

>>>а матрица 1000x10000 - статическая структура. А переварить ее она не
>>>может, потому что Hugs - это игрушка, а не серьёзная реализация

Правильно ли я Вас понял:
1) Надо попробовать это в более серьезных системах типа GHC - там "физика" модуля Array может отличаться от реализации, использованной в Hugs.
2) Реализация массива в чистом функциональном языке, каковым является Haskell, - это не динамический список, а "примитивный" статический массив, память для которого выделяется сразу и целиком в соответствии с его границами (кстати здесь возникает еще один вопрос - Вы действительно знаете как физически устроены массивы в реализациях Haskell или это Ваша гипотеза? Дело в том, что в имеющихся у меня материалах по Haskell я об этом ничего не могу найти)

P.S.

Мне кажется, что Вы несколько упрощаете сложный вопрос. Статический массив и сообщение системы исполнения об ошибке, связанной со сборкой мусора - это очень странно. Сборка мусора - это понятие, связанное с управлением динамическими структурами данных, при работе со статическим массивом никакого мусора быть не может в принципе!

Ответ на »сообщение 695« (Geniepro)
___________________________

Почему Я должен увеличивать размер стека??? :-x
Почему компилятор об этом не заботится??? :-x
Почему программа в скомпилированном виде сама не увеличит стек при необходимости? :-x

Попробуйте в LispWorks набрать уже набившую оскомину программу:

(defun fact (n)
  (cond ((eq n 1) 0)
        (t      (* n (fact (1- n))))
  )
)

(fact 10000)

Результат:

Stack overflow (stack size 16000).
  1 (abort) Return to level 0.
  2 Return to top loop level 0.

Хотя рекурсия вроде концевая. Так что размер стека всё-таки нужно настраивать и в LispWorks. Видимо, это плата за производительность (меня уже почти убедили, что производительность в современных реализациях компилирующих ФЯ таки на высоте).

Ответ на »сообщение 699« (hugi)
___________________________
Средства реализации инкапсуляции различаются для каждого ОО языка. 

О том и речь. Цель одна, средства достижения этой цели разные. Разные даже в разных реализациях ООП, не говоря уж о других способах (без ООП)

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

Я думаю если бы эти гуру творили сегодня, имея за плечами опыт более чем 30 лет ООП, то фраза эта выглядела бы по другому.
ООП это инкапсуляция, полиморфизм и абстракция. (то есть реализация этих концепций, достижение этих целей)
А вот средства реализации этих концепций в ООП, это
1. Области видимости private, public, protected и различные другие варианты типа internal (инкапсуляция)
2. Переопределение методов virtual, overloaded (полиморфизм)
3. Наследование (абстракция и полиморфизм)


Главная же цель у ООП одна: борьба со сложностью. Всё остальное -- средства!


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

После чего вы садитесь и думаете, каким механизмом реализовать эти три концепции.
Инкапуляцию можно реализовать модульностью. А можно и классами.
Полиморфизм (переопределение функций) тоже не нуждается в ООП. Он присутствует практически во всех языках отдельно.
Абстракцию можно реализовать наследованием. А можно и higher order functions и closures.

Какие средства конкретно зависит от того что создает язык. Алан Кей, Гослинг, Макарти, Мейер, Вирт, Simon Peyton Jones, и многие многие другие. Все они гоняются за одними и теми же целями - абстракция, инкапсуляция, полиморфизм. Но механизмы реализации этих целей конструируют разные.


Постойте, а откуда в этой цитате взялись такие термины, как "instance", "class", "superclass"?

Эти термины совсем не то что вы под этим понимаете.
В конце концов в хаскеле тоже есть термин type classes , что совсем не означает что в хаскеле есть классы.

Речь идет о иерархии типов. Термином class в теории рипов обозначают тип.
Не обязательно с той конструкцией к которой вы привыкли (свойства, методы).
Superclass это общий тип.
То есть Number - это общий тип, а Integer и Real это его подтипы.
Вас вводят в заблуждение "знакомые" слова.

Ответ на »сообщение 703« (SJ)
___________________________
А в том же Дельфи вы можете определить такую структуру:

TMyArray= array of array of Integer;

И изменять ее размеры по мере необходимости. А параметры функций и свойства этого типа - это в принципе и есть бесконечные структуры.

Ответ на »сообщение 704« (Артем)
___________________________
а матрица 1000x10000 - статическая структура. А переварить ее она не может, потому что Hugs - это игрушка, а не серьёзная реализация.

Ответ на »сообщение 703« (SJ)
___________________________
Определения бесконечных структур должны быть рекурсивными. Например, бинарное дерево:

data Tree a = Leaf a | Branch (Tree a) (Tree a) Branch :: Tree a -> Tree a -> Tree a Leaf :: a -> Tree a

Ну, раз аудитории интересны проблемы "сверхбольшого", то есть у меня еще один вопрос на эту тему.
Haskell - это ФЯ с "ленивой" моделью вычислений. Т.е. функция вычисляется только тогда, когда откладывать вычисление уже невозможно. Например, можно определить список бесконечной длины - если нам потребуется только конечное число его элементов, то они и будут вычислены в соответствующий момент времени.
Возникает соблазн определить массив огромного размера. Если язык будет следовать "ленивой" модели, то само определение не должно привести к проблемам - реально элементы массива (значения функции) будут вычисляться только тогда, когда в них возникнет реальная потребность.
Проведем эксперимент. Дадим определение "гигантской" матрицы с нулями, например, 1000 на 1000. А потом выведем на экран один элемент (1,1).
По идее все должно пройти. Нам реально требуется только один элемент, а определение 1000000-элементной матрицы - это, всего лишь, "ленивое" определение функции, которое в реальности не осуществляется в полном объеме.

module Giantmatrix where
import Array

main = do
  print "Гигинтская матрица"
  print (a!(1,1))

a = array ((1,1),(1000,1000)) [((i,j),0)|i<-[1..1000],j<-[1..1000]]

Запускаем модуль в Hugs. При загрузке (компиляции в байт-код) все нормально. Формальных ошибок система не фиксирует. А вот при выполнении кода получаю:
ERROR - Garbage collection fails to reclaim sufficient space.
Иду дальше - сокращаю диапазон индекса до 1..100. Теперь все нормально!

Вопрос такой. При чем тут сборка мусора и почему "ленивый" функциональный язык все-таки не может "переварить" список из предыдущего примера (при том, что бесконечные рекурсивные последовательности переваривает и "не кашляет") ? Кто понимает, в чем тут дело ?