🚀 go-pugleaf

On Mon, 2 Dec 2002 16:59:27 +0000 (UTC), Arek Paterek wrote:
> 
> Oczywiście można zapisać rekurencję w postaci ogonowej i pewnie
> wtedy stos nie będzie używany, ale co robić w większych programach?
> Nie zawsze chcę/potrafię zapisać rekurencję ogonową, nie zawsze
> łatwo jest mi przewidzieć głębokość stosu. A funkcji rekurencyjnych
> używa się w językach funkcyjnych często-gęsto.

Nie wydaje mi się, żeby istniało jakieś uniwersalne rozwiązanie.
Zawsze możesz podać problem o takim rozmiarze, dla którego dany
program nie zadziała.  Na ogół rekurencja nie jest aż tak głęboka.
Jeśli są podejrzenia, że będzie to można stosować rekurencję ogonową
(coś za coś), albo zwykłe pętle (o ile dany język je ma).


> W Ocamlu jest to problem (i w innych językach funkcyjnych pewnie też),
> w językach imperatywnych problemu nie ma (jest w mniejszej skali,
> bo w nich się nie używa rekurencji do wszystkiego).

W językach funkcyjnych też nie używa się rekurencji do wszystkiego
(o ile język tego jakoś nie wymusza).


> Wydaje mi się, że skoro programowanie funkcyjne jest takie dobre i piękne,
> funkcje rekurencyjne są lepsze od lamerskich pętli,

Niby dlaczego lepsze?


> a Ocaml jest pięknym językiem i ma najlepszy kompilator,

Dlaczego uważasz, że ma najlepszy kompilator?  Z języków mających
cechy funkcyjne, to podobno najlepsze kompilatory ma Lisp.


-- 
<>> kristof@swissmail.org <Krzysztof Parzyszek>    9/2/2002
<<> "If you can't convince them, confuse them" -- HS Truman

Krzysztof Parzyszek wrote:

> >a Ocaml jest pięknym językiem i ma najlepszy kompilator,
>
>
> Dlaczego uważasz, że ma najlepszy kompilator?  Z języków mających
> cechy funkcyjne, to podobno najlepsze kompilatory ma Lisp.


Wiele zależy od tego co rozumiemy przez "najlepsze" oraz jak i kto tę 
"lepszość" będzie mierzyć/badać :) Ja nie spotkałem się z benchmarkami 
porównującymi OCamla i komercyjne Lispy i nie słyszałem o ich istnieniu. 
Również brakuje jakichkolwiek rzetelnych danych o ich możliwosciach. A w 
bajeczki opowiadane przez panów od marketingu, jak to ich super-hiper 
kompilator bije na głowę ręcznie optymalizowane C nie wierzę, bo wiem 
jak się kompiluje Lispy... ;)
A z tym "podobno" to bardzo różnie bywa. "Podobno" Clean ma najlepszy 
kompilator wśród języków leniwych i gdy zapytasz na clean-list o jego 
możliwości to znajdą sie tacy, którzy będa twierdzić, że w ich 
zastosowaniach jest zawsze szybszy niż OCaml, co jest dość zabawne jeśli 
weźmiemy pod uwagę rzeczywiste możliwosci tego kompilatora... ;)

Arek Paterek wrote:

> Oczywiście można zapisać rekurencję w postaci ogonowej i pewnie
> wtedy stos nie będzie używany, ale co robić w większych programach?


Oszacować czy istnieje niebezpieczeństwo przepełnienia stosu i jeśli 
istnieje zapisz rekurencję w postaci ogonowej :)
Jeśli nie jesteś w stanie oszacować - przyjmij, że się przepełni i 
zapisz ogonowo :)
Jeśli nie umiesz zapisać rekurencyjnie, a umiesz to prosto zapisać za 
pomocą pętli, to znaczy że  musisz jeszcze troszkę poćwiczyć ;)

> W Ocamlu jest to problem (i w innych językach funkcyjnych pewnie też),
> w językach imperatywnych problemu nie ma (jest w mniejszej skali,


Nie ma problemu, bo "odpowiednikiem" iteracji z języka imperatywnego 
jest rekurencja ogonowa, a nie rekurencja w ogóle ;)

> Wydaje mi się, że skoro programowanie funkcyjne jest takie dobre i 
> piękne, funkcje rekurencyjne są lepsze od lamerskich pętli,
> a Ocaml jest pięknym językiem i ma najlepszy kompilator,
> to powinien poradzić sobie z przepełnieniem stosu przynajmniej
> w swoim kompilatorze bajtkodowym.


Nie tylko nie powinien, ale nawet nie ma prawa sobie z tym poradzić. 
Pomyś chwilę co, poza adresem powrotu, ląduje na stosie w Twoim 
programiku...

On Mon, 02 Dec 2002 21:10:00 +0100, Mariusz K. Grzeca wrote:
> Krzysztof Parzyszek wrote:
> 
>> >a Ocaml jest pięknym językiem i ma najlepszy kompilator,
>>
>> Dlaczego uważasz, że ma najlepszy kompilator?  Z języków mających
>> cechy funkcyjne, to podobno najlepsze kompilatory ma Lisp.
> 
> Wiele zależy od tego co rozumiemy przez "najlepsze" oraz jak i kto tę 
> "lepszość" będzie mierzyć/badać :)

Tyle to ja wiem :)  Tak naprawdę to nie podoba mi się ten zachwyt OCamlem
i stąd to pytanie/stwierdzenie... :) A o Lispie (o CMUCL w szczególności)
to już nie pamiętam gdzie słyszałem, ale opinie były pozytywne albo wręcz
bardzo pozytywne.


-- 
<>> kristof@swissmail.org <Krzysztof Parzyszek>    9/2/2002
<<> "If you can't convince them, confuse them" -- HS Truman

Arek Paterek napisał:
> W Ocamlu jest to problem (i w innych językach funkcyjnych pewnie też),

W Haskellu, GHC 5.04.1:

y.hs:

  module Main where

  import System

  f :: Int -> Int
  f n =
      if n == 1 then
	  1
      else
	  1 + f (n-1)

  main :: IO ()
  main =
      do
	  args <- getArgs
	  mapM_ (print.f.read) args

$ ghc -O --make y -o y
$ strace -o s ./y 100000000 +RTS -K1G	# 1G stosu !
100000000
$ grep mmap s
old_mmap(0x50000000, 1048576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50000000
old_mmap(0x50100000, 1048576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50100000
old_mmap(0x50200000, 1048576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50200000
old_mmap(0x50300000, 2097152, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50300000
old_mmap(0x50500000, 4194304, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50500000
old_mmap(0x50900000, 8388608, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x50900000
old_mmap(0x51100000, 16777216, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x51100000
old_mmap(0x52100000, 33554432, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x52100000
old_mmap(0x54100000, 67108864, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x54100000
old_mmap(0x58100000, 134217728, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x58100000
old_mmap(0x60100000, 267386880, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x60100000
old_mmap(0x70000000, 533725184, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x70000000

Jak uruchomie tak:
  $ ./y 1 +RTS -K1G
nie alokuje od razu jednogigowego stosu.

Niech no jeszcze ktoś powie, że Haskell jest mniej praktyczny niż OCaml ;)

PS. Jeśli OCaml też potrafi inkrementalnie alokować stos, chętnie się o
    tym dowiem.

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

> let rec f a =
>   if a == 1 then
>     1
>   else
>     1 + f (a - 1)
> in
>   f 100000

Jak programowac funkcyjnie, to tylko leniwie! W jezyku leniwym odpowiednikiem

takiego for-a jest fold. Dodawanie w kolko jedynki zapiszemy jakos tak:

( "\" to lambda)
fold ( \a \i a+1) 0 [1..100000]

W jezyku funkcyjnym leniwym bedzie to sie odbywalo w pamieci stalej.

Pozdrawiam,
Tomek

On Fri, 6 Dec 2002, Tomek Czajka wrote:

> Jak programowac funkcyjnie, to tylko leniwie!

Dlaczego? Leniwość jest bardzo droga i utrudnia wnioskowanie o
złożoności pamięciowej programów.

> W jezyku leniwym odpowiednikiem takiego for-a jest fold

Nie wiem w jakim. W znanych mi nie ma funkcji fold dla list. Są między
innymi foldl i foldr.

> W jezyku funkcyjnym leniwym bedzie to sie odbywalo w pamieci stalej.

Nie będzie. Prześledź sobie jak wygląda redukcja wyrażenia:

foldl (+) 0 [a1, a2, a3, a4, a5, ...]

foldl (+) (0 + a1) [a2, a3, a4, a5, ...]
foldl (+) (0 + a1 + a2) [a3, a4, a5, ...]
foldl (+) (0 + a2 + a3 + a4) [a5, ...]
...

Po pierwsze foldl generuje wyrażenie reprezentowane przez łańcuch
thunków o długości liniowej względem rozmiaru danych wejściowych. Po
drugie ewaluacja tego wyrażenia wymaga liniowego stosu :)
Po trzecie foldl i foldr, lub ich odpowiedniki są również w gorliwych
językach funkcyjnych :)

> > W jezyku leniwym odpowiednikiem takiego for-a jest fold
>
> Nie wiem w jakim. W znanych mi nie ma funkcji fold dla list. S± miêdzy
> innymi foldl i foldr.

No coz, jesli nie ma w bibliotece standardowej, to trzeba samemu
zdefiniowac.
Ale chyba sie i tak zrozumielismy, o jaka funkcje chodzi.


>
>
> > W jezyku funkcyjnym leniwym bedzie to sie odbywalo w pamieci stalej.
>
> Nie bêdzie. Prze¶led¼ sobie jak wygl±da redukcja wyra¿enia:
> [...]

Rzeczywiscie - masz racje.

Sklania mnie to do wycofania sie - juz nie uwazam, ze jezyki leniwe sa
fajne.

Podam jeszcze inne rozwiazanie problemu dodawania jedynki, juz raczej w
stalej pamieci, ale
juz nie w jezyku leniwym:

zlozenie 100000 ( \n n+1) 0

Tak, wiem ze w bibliotece standardowej zadnego ze znanych Ci (ani mi)
jezykow programowania nie
ma funkcji "zlozenie", ale chodzi mi o taka (choc pewnie sie wszyscy
domyslaja):

let rec zlozenie n f a =
  if n=0 then a else zlozenie (n-1) f (f a)


Pozdrawiam,
Tomek

Mariusz K. Grzeca napisał:
> On Fri, 6 Dec 2002, Tomek Czajka wrote:
> 
>> W jezyku leniwym odpowiednikiem takiego for-a jest fold
> 
> Nie wiem w jakim. W znanych mi nie ma funkcji fold dla list. Są między
> innymi foldl i foldr.

Chyba niepotrzebnie się czepiasz szczegółów.

>> W jezyku funkcyjnym leniwym bedzie to sie odbywalo w pamieci stalej.
> 
> Nie będzie. Prześledź sobie jak wygląda redukcja wyrażenia:
> 
> foldl (+) 0 [a1, a2, a3, a4, a5, ...]
> 
> foldl (+) (0 + a1) [a2, a3, a4, a5, ...]
> foldl (+) (0 + a1 + a2) [a3, a4, a5, ...]
> foldl (+) (0 + a2 + a3 + a4) [a5, ...]
> ...

> Po pierwsze foldl generuje wyrażenie reprezentowane przez łańcuch
> thunków o długości liniowej względem rozmiaru danych wejściowych.

> Po drugie ewaluacja tego wyrażenia wymaga liniowego stosu :)

A to niby dlaczego?

Nie będę powtarzał tego, co już zostało powiedziane:

     * From: Ketil Malde
     * Subject: Re: foldl, tail recursion, and strictness (was: stack
     * overflow)
     * Date: Mon, 26 Feb 2001 06:42:57 -0800

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

 "C.Reinke" <C.Reinke@ukc.ac.uk> writes:

 > So foldl is indeed tail recursive, but this doesn't help if its
 > operator isn't strict because the tail recursion only builds up the
 > expression to be evaluated. Making strictness explicit by defining a
 > variant of foldl that evaluates its accumulator at each step helps to
 > solve the problem and documents programmer intentions.

 > This is quite common a trap for Haskellers to fall into

 It makes me wonder if it's common enough that strict foldl should be
 the default?  Are there (many) cases where a partial foldl makes
 sense?

 -kzm

Foldl gorliwy na argumencie akumulatora można zapisać np. tak:

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc (x:xs) = (foldl' f $! (f acc x)) xs
foldl' _ acc []     = acc

> Po trzecie foldl i foldr, lub ich odpowiedniki są również w gorliwych
> językach funkcyjnych :)

Tak, ale one są gorliwe aż do przesady, więc trudno mówić, że jest to
odpowiednik pętli for. Pętla for nie musi budować w pamięci całej listy
elementów po których będzie iterować.

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links

Tomasz Zielonka wrote:

> A to niby dlaczego?

Dlatego, że foldl jest w Haskellu leniwy względem drugiego argumentu, a 
wśród istniejących implementacji tylko GHC jest w stanie czasami coś z 
tym zrobić.

>  > So foldl is indeed tail recursive, but this doesn't help if its
>  > operator isn't strict

Gorliwość operatora nie ma tu znaczenia, bo aplikacja nieznanej funkcji 
jest zawsze leniwa. A ta funkcja zrobi się znana dopiero wtedy, gdy 
kompilator rozwinie sobie ciało foldla w miejscu użycia...

> Foldl gorliwy na argumencie akumulatora można zapisać np. tak:

Zgoda, można. Tyle że foldl domyślnie nie jest gorliwy...