## Re: "ocaml_beginners"::[] CPS unleashed?

Expand Messages
• ... and I think you are wrong, it will use more place than the whole list. More precisely The closure will use 4 word, while the list use 3. In fact the main
Message 1 of 10 , Sep 3, 2002
Stalkern 2 <stalkern2@...> writes:

> After a previous thread we know that the @ operator leads to non tail
> recursive programs.
> Gerd said "@ is O(n)", and by the way he said also, for a problem with reverse
> lists, "One optimization would be to accumulate by "head :: accum" instead of
> "accum @ [head]", and to reverse the resulting list afterwards (List.rev is
> O(n), and tail-recursive)."
>
> Here http://www.cs.utah.edu/classes/cs6520/cps.pdf uses CPS, by writing:
>
>
> let rec makeList3 =
> fun n ->
> fun aFun ->
> if (n = 0) then
> (aFun [])
> else
> (makeList3 (n - 1) (fun partialList -> aFun (n::partialList)));;
>
> _______________________
> Actually a function is added, both fetching over the partialList and using it
> to accumulate the main argument, while the main argument decreases.
> I think that this function will take as much space as the whole list, because
> it fetches the partialList around, but not more.

and I think you are wrong, it will use more place than the whole
list. More precisely The closure will use 4 word, while the list
use 3.

In fact the main concern if we compare to the Gerd solution :
let rec makeList4 n acc =
if n = 0 then List.rev acc
else makeList4 (n - 1) (n::acc)

is that the makeList3 will be less efficient in term of speed : the
use of closure in place of "real function" is less efficient (at least
when compiled with ocamlopt).

[...]

by the way, I believe that
let rec makeList4 n acc =
if n = 0 then List.rev acc
else makeList4 (n - 1) (n::acc)

let rec makeList4 =
fun n ->
fun acc ->
if n = 0 then List.rev acc
else makeList4 (n - 1) (n::acc)

because you remove the syntactic overhead that come from the fun an -> thing.
--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
• ... What do you mean by word ? I can t see this. ... OK, I see that you can measure times exactly. Are you using a timer like the one that Doug Bagley s
Message 2 of 10 , Sep 4, 2002
Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
> and I think you are wrong, it will use more place than the whole
> list. More precisely The closure will use 4 word, while the list
> use 3.
>

What do you mean by "word"? I can't see this.

>
> In fact the main concern if we compare to the Gerd solution :
> let rec makeList4 n acc =
> if n = 0 then List.rev acc
> else makeList4 (n - 1) (n::acc)
>
>
> is that the makeList3 will be less efficient in term of speed : the
> use of closure in place of "real function" is less efficient (at least
> when compiled with ocamlopt).
>

OK, I see that you can measure times exactly. Are you using a timer like the
one that Doug Bagley's suggested once upon a time?
>
>
> [...]
>
>
> by the way, I believe that
> let rec makeList4 n acc =
> if n = 0 then List.rev acc
> else makeList4 (n - 1) (n::acc)
>
>
> is more easily readable than
>
>
> let rec makeList4 =
> fun n ->
> fun acc ->
> if n = 0 then List.rev acc
> else makeList4 (n - 1) (n::acc)
>
>
> because you remove the syntactic overhead that come from the fun an ->
> thing.

Hey hey, I started writing things like that to put some order.
The synthetic style makes indentation useless and indendation helps
Moreover, extended writings like "fun n ->" etc. are meaningful in
distinguishing clearly the name of a function and its arguments.
In my opinion, "f(x) =" is clear, "f = fun x ->" is clear, but "f x =" is a
shame.
I'm not paid for the lines of code (then I'd change language!), nor for the
contrary. I just think that a few recyclable bytes more can be used for
pretty-printing, especially in this list.
Apart from that, as a nominalist I can't stand the sight of neutral names. I
praise the use of different sort of names for elements with different roles,
so calling a function "k" is to me not only a matter of inadvertance but an
attempt to fake the reality...
Imagine that I write *mails in english* in a twelve-words, non new-lined
zipped style. Would you read me?

Bye
Ernesto
PS to take a look at the pragmatical aspects of speaking, one can read for
instance "Ce que parler veut dire" by the philosopher Pierre Bourdieu.
• ... I am assuming he means words of memory? That while writing something in the CPS way does not use lots of stack space like a normal recursive function
Message 3 of 10 , Sep 4, 2002
>From: Stalkern 2 <stalkern2@...>
>Subject: Re: "ocaml_beginners"::[] CPS unleashed?
>
>Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
> > and I think you are wrong, it will use more place than the whole
> > list. More precisely The closure will use 4 word, while the list
> > use 3.
> >
>
>What do you mean by "word"? I can't see this.

I am assuming he means words of memory? That while writing something in the
CPS way does not use lots of stack space like a normal recursive function
often does, it needs quite a bit of heap space. More heap space than the
resulting list will need. Possibly more heap space than the original
function used stack space?

>
>...
> > because you remove the syntactic overhead that come from the fun an ->
> > thing.
>
>Hey hey, I started writing things like that to put some order.
>...
>

To each his own, I say! It's much too easy to have your own opinions
concerning OCaml's syntax. Let's not even get started over the revised
syntax... ;)

Ryan Tarpine, rtarpine@...
"To err is human, to compute divine. Trust your computer but not its
programmer."
- Morris Kingston

_________________________________________________________________
Join the world�s largest e-mail service with MSN Hotmail.
http://www.hotmail.com
• ... This is not only a matter of syntax, it s a matter of beginning with ocaml. In the ocaml-beginners list, that could be a harbour of peace e.g. for those
Message 4 of 10 , Sep 4, 2002
Il Wednesday 04 September 2002 13:41, Ryan Tarpine ha scritto:
> It's much too easy to have your own opinions
> concerning OCaml's syntax. Let's not even get started over the revised
> syntax... ;)

This is not only a matter of syntax, it's a matter of beginning with ocaml. In
the ocaml-beginners' list, that could be a harbour of peace e.g. for those
who have spent their life so far doing things completely different from fp
and so on, one should find IMHO some ocaml-for-beginners or

otherwise it could be called "ocaml-support" and close in a few mails. I
don't have an extensive knowledge of Ocaml, but when I learnt something in
Ocaml I write it here trying to explain it.
We could also skip the Yahoo Archives, that are stuffed with ads, by putting
the hundreds of messages that have been produced here so far on a site, ASA I
have time to take a look at those php forum management programs. In the
meanwhile, please don't get bothered by my idiot-proof pretty parsing, the
intention is the same, to let anyone learn ocaml without too much pain.

Cheers
Ernesto
PS BTW About pain I heard a joke: a sadist goes towards a masochist and plays
like hitting him; the masochist says "Yes!" then the sadist stops and says
"No-o!" (sorry it must be a side-effect of cps;-))) )
• ... a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer, and so one... ... I haven t measure the time. But I do know that call of closure is
Message 5 of 10 , Sep 4, 2002
Stalkern 2 <stalkern2@...> writes:

> Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
>> and I think you are wrong, it will use more place than the whole
>> list. More precisely The closure will use 4 word, while the list
>> use 3.
>>
>
> What do you mean by "word"? I can't see this.

a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
and so one...

>
>>
>> In fact the main concern if we compare to the Gerd solution :
>> let rec makeList4 n acc =
>> if n = 0 then List.rev acc
>> else makeList4 (n - 1) (n::acc)
>>
>>
>> is that the makeList3 will be less efficient in term of speed : the
>> use of closure in place of "real function" is less efficient (at least
>> when compiled with ocamlopt).
>>
>
> OK, I see that you can measure times exactly. Are you using a timer like the
> one that Doug Bagley's suggested once upon a time?

I haven't measure the time. But I do know that call of closure is less
efficient than call to "real function" (I don't like this name,
closure are function too, but I don't know how to name those, may be
direct function ?). Well to be more precise :
with ocamlopt (a list of 2000 element is created):

-- makeList3: iterations:10000 avg time:3.400000E-01 msec
-- makeList4: iterations:10000 avg time:2.260000E-01 msec

with ocamlc :
-- makeList3: iterations:10000 avg time:6.020000E-01 msec
-- makeList4: iterations:10000 avg time:7.240000E-01 msec

[...]

> Hey hey, I started writing things like that to put some order.
> The synthetic style makes indentation useless and indendation helps
> Moreover, extended writings like "fun n ->" etc. are meaningful in
> distinguishing clearly the name of a function and its arguments.
> In my opinion, "f(x) =" is clear, "f = fun x ->" is clear, but "f x =" is a
> shame.

I strongly disagree. But it a question of taste. For me the fun x -> put
a lot of unneeded things. The second problem is that it is not
idiomatic ocaml code. idiomatic ocaml code make the code easier to
read for other ocaml programmer, and if you are use to read idiomatic
code, it make reading code of other more easy for you.

> I'm not paid for the lines of code (then I'd change language!), nor for the
> contrary. I just think that a few recyclable bytes more can be used for
> pretty-printing, especially in this list.
> Apart from that, as a nominalist I can't stand the sight of neutral names. I
> praise the use of different sort of names for elements with different roles,
> so calling a function "k" is to me not only a matter of inadvertance but an
> attempt to fake the reality...

are you talking of my use of aux ? I use aux function for local
function when the name of the local function should be the same than
the name of the global function :

let sum n =
let rec sum n accu =
if n = 0 then accu
else sum (n - 1) (accu + n) in
sum n 0

is correct, but I prefer the version with the aux function.

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
• ... Well, you know that one could rather write things like let sum n = let rec sum1 n accu = if n = 0 then accu else sum1 (n - 1) (accu + n) in sum n 0 and
Message 6 of 10 , Sep 4, 2002
Il Wednesday 04 September 2002 15:06, Remi VANICAT ha scritto:
> let sum n =
> let rec sum n accu =
> if n = 0 then accu
> else sum (n - 1) (accu + n) in
> sum n 0
>
>
> is correct, but I prefer the version with the aux function.

Well, you know that one could rather write things like
let sum n =
let rec sum1 n accu =
if n = 0 then accu
else sum1 (n - 1) (accu + n) in
sum n 0

"aux".

BTW I was speaking about something else:
imagine that one writes a book about a man and the man's first name is not,
say, Ernesto but Médor (or other pet's name) or, say, "Car". I can tell you
that either the reader can get puzzled, or Ernesto gets angry |:-[: :]

That's it.
BTW you're quite right from a structural point of view, as well as one could
call "x" or "atasu" the structuralist "empty case" and apply this name to a
whole world of unknown things, but pointers in my memory need some hints
especially when I don't use ocaml for a while or plan to do so many things in
my life that I'll forget everything as in that book by Garcia Marquez.

Actually, do you mind "fun ->" - code? I can change it if we get a general
agreement on syntactic sugar in this list. Or we can take as granted the

Greetings
Ernesto
• ... of course every auxiliary function shouldn t be called aux. The true is that, in the case of tail rec : let sum n = let rec aux n accu = if n = 0 then accu
Message 7 of 10 , Sep 4, 2002
Stalkern 2 <stalkern2@...> writes:

> Il Wednesday 04 September 2002 15:06, Remi VANICAT ha scritto:
>> let sum n =
>> let rec sum n accu =
>> if n = 0 then accu
>> else sum (n - 1) (accu + n) in
>> sum n 0
>>
>>
>> is correct, but I prefer the version with the aux function.
>
> Well, you know that one could rather write things like
> let sum n =
> let rec sum1 n accu =
> if n = 0 then accu
> else sum1 (n - 1) (accu + n) in
> sum n 0
>
> function "aux".

of course every auxiliary function shouldn't be called aux. The true
is that, in the case of tail rec :

let sum n =
let rec aux n accu =
if n = 0 then accu
else aux (n - 1) (accu + n) in
aux n 0

do exactly the same thing than :

int f(int n) {
int accu = 0;
while (n <> 0) {
accu = accu + n;
n = n - 1;
};
return accu
}

(this is tail rec optimization)

so I see aux mostly as a keyword in my code (that is aux is the tail
rec function that do the job).

other auxiliary function should have more explicit name.

by the way, you should read http://caml.inria.fr/FAQ/pgl-eng.html for
guideline. The main thing I don't follow in those guideline is :

let f = function
| 0 -> ...
| 1 -> ....

I prefer to write it as :

let f x =
match x with
| 0 -> ...
| 1 -> ....

like that each function definition are of the form

let f x1 x2 ... xn =
...

where n is the number of argument of f.
(and the fact is that both ocamlc and ocamlopt will compile the
2 function the same way).

(and may be some other small difference).

[...]

>
> Actually, do you mind "fun ->" - code? I can change it if we get a general
> agreement on syntactic sugar in this list. Or we can take as granted the

I believe that for a lot of thing, it will be difficult (even
impossible) to agree on it. But I firmly believe that the best way to
write a function with two argument in ocaml is :

let f arg1 arg2 =
...

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
• ... Notice that this definition is a little bit confuse for people used to programming in C/C++ under Windows because of the following : typedef unsigned short
Message 8 of 10 , Sep 4, 2002
> > Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
> >> and I think you are wrong, it will use more place than the whole
> >> list. More precisely The closure will use 4 word, while the list
> >> use 3.
> >>
> >
> > What do you mean by "word"? I can't see this.
>
> a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
> and so one...

Notice that this definition is a little bit confuse for people used to
programming in C/C++ under Windows because of the following :

typedef unsigned short WORD; // 16-bit

I don't know about *Nix but that definition is largely used by most of the
Win32 API's.

Best regards,
Nicolas Cannasse
• ... well : word A fundamental unit of storage in a computer. The size of a word in a particular computer architecture is one of its chief
Message 9 of 10 , Sep 4, 2002
"Nicolas Cannasse" <warplayer@...> writes:

>> > Il Wednesday 04 September 2002 04:20, Remi VANICAT ha scritto:
>> >> and I think you are wrong, it will use more place than the whole
>> >> list. More precisely The closure will use 4 word, while the list
>> >> use 3.
>> >>
>> >
>> > What do you mean by "word"? I can't see this.
>>
>> a word is 32 Bit on a 32 bit computer, 64 Bit on a 64 bit computer,
>> and so one...
>
> Notice that this definition is a little bit confuse for people used to
> programming in C/C++ under Windows because of the following :
>
> typedef unsigned short WORD; // 16-bit
>
> I don't know about *Nix but that definition is largely used by most of the
> Win32 API's.

well :

word

<storage> A fundamental unit of storage in a computer. The
size of a word in a particular computer architecture is one of
its chief distinguishing characteristics.

The size of a word is usually the same as the width of the
computer's {data bus} so it is possible to read or write a
word in a single operation. An instruction is usually one or
more words long and a word can be used to hold a whole number
of characters. These days, this nearly always means a whole
number of {bytes} (eight bits), most often 32 or 64 bits. In
the past when six bit {character sets} were used, a word might
be a multiple of six bits, e.g. 24 bits (four characters) in
the {ICL 1900} series.

So the use of the term "word" for 16 bit value come from the time when
ix86 machine where 16 bit machine.

--
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
Your message has been successfully submitted and would be delivered to recipients shortly.