[oliver: Re: [Caml-list] Strings as arrays or lists...]

[oliver: Re: [Caml-list] Strings as arrays or lists...]

[Oliver Bandel]

ooops,

forgotten to Cc: to the list.


Ciao,
   Oliver

----- Forwarded message from oliver -----

To: brogoff@speakeasy.net
Subject: Re: [Caml-list] Strings as arrays or lists...

On Mon, Mar 03, 2003 at 09:12:32AM -0800, brogoff@speakeasy.net wrote:
> Yes, Xavier is right here, and I apologize for posting an "explode" function 
> on this list. I'll appeal for leniency, mentioning that I didn't post 
> "implode", and that I only posted the former function to demonstrate that 
> it could be done, and to point out that one of the many reasons strings as 
> char lists is wrong as a basic type is that you get an abstraction inversion. 


What is an abstraction inversion?
Sounds very interesting, but I don't understand, waht this means.


What I first have written about the string-stuff,
was: It's not FP-like, but I also would be happy
with a syntax, that would allow me, to use Array-functions
for the Strings.

If there maybe is a typing-reason, why not strings AND
arrays should have same syntax
( e.g. both <name>.[index]  or both <name>.(index) )
then maybe it would be possible to add the typical
Array-functions (or List-functions) to the String-Library?

Why not converting a string to a list with
String.to_list
or to an array with
String.to_array

Arrays can be converted with Array.to_list (or vice versa
with Array.of_list). Why not such stuff for strings?
If they are already array-like, why not using such
functions?

Why not using a  String.map  for application of
char-based functions to each char?

To write more abstract String-manipulation is also ok,
so that the char-wise stuff would be on a lower level
(inside the library, maybe implemented in C or is some
imperative Ocaml-stuff, which the user of the library does not
see).

OK, strings are not char-lists, and they are not char-arrays.
At least not to the user.


But it would help, to have such powerful functions like

<Module>.map
<Module>.iter
<Module>.fold_left
<Module>.fold_right
<Module>.filter

Where Module here would be one of:  Array, List, String.

If this is not very senseful, because the functions
are only applied to char#s and not to any type ('a)
(like in Array- or List-module), and this powerful
functions are bored, when used only at one type (char),
then it would make sense to have at least these two
functions in the Array.module:

Array.to_string
Array.of_string

If you think, this is not necessary in the stdlib,
because it is easy to convert strings to arrays
(very similar notation/syntax), then I can answer:
Well, it is also easy to implement functions like
Array.to_list
Array.of_list

So why having them in the stdlib?

If there are conversion-functions between the
fundamental data-types (Array.to_list, Array.of_list,
string_of_int, string_of_float, int_of_string, int_of_float)
why are there no conversions between (at least) string and Array?



Ciao,
   Oliver

P.S.: Another thing, where I think about, is:
      Shouldn't it be possible to handle
      strings as Lists for the user, even if it is implemented
      array-based somewhere deep in the basement of the code-base?
      So, that it would be possible to handle strings like
      [char], even if they are implemented array-based (and therefore
      perfromant)?
      Isn't one of the major goals of Languages like Ocaml,
      to have a clear distinction between implementation and interface?

      (Or does your "abstraction inversion" here says "No!" to such
      a thing?)


P.P.S.: The reason, why I asked for R-Tree/R+-Tree/Quad-Tree-
        Implementation in Ocaml: They are very good tools for
        *very* highlevel textprocessing.

        So maybe some Tree-libraries would be a good thing for
        Ocaml, but IMHO such stuff is better suited on a COAN,
        and should not be part of the Ocaml-language/-standard-
        libraries itself.
        But it's good to have such libraries too, even if it
        should be relatively easy to implement it in Ocaml.
        I think, when some OCaml-gurus would implement them, they would
        be more performant and easy to use, than if any other
        Ocaml-programmer would write his/her own solution.
        And such basic (often called) stuff should be performant...


----- End forwarded message -----

-- 
  Why Ocaml is programmer's heaven?
     http://www.win.tue.nl/~lhol/projects/pargen/ocaml.html

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[brogoff]

On Mon, 3 Mar 2003, Oliver Bandel wrote:
> What is an abstraction inversion?
> Sounds very interesting, but I don't understand, waht this means.

I'm abusing the term a bit, as I understand it. I'm pretty sure it comes from 
the Ada community. Roughly, it refers to implementing a low level abstraction on 
top of a higher level abstraction. In this case, I was using it as "representing 
an efficient abstraction on top of an inefficient one", as I claim you would 
have to do if you try to build strings on top of char lists. 

(PS: you can try using Google, www.google.com, or another search engine, when 
you se a term you don't understand)

(PPS: someone reminded me that Erlang also botched strings)

> What I first have written about the string-stuff,
> was: It's not FP-like, but I also would be happy
> with a syntax, that would allow me, to use Array-functions
> for the Strings.

That's why I said "Agitate for extensional polyorphism!". You really want a 
way to overload similar notations. As you must now know, OCaml has no 
overloading. Extensional polymorphism gives you that overloading, on top of 
ML, in a way that even people who hate overloading should find fairly 
nonthreatening. 

Incidentally, I think substrings are the right FP-like way to handle strings. 
Substring operations are recursions on integer indices, and you can build them 
on top of OCaml's string type by adding two indices to a string. see either 
the SML Basis Library, or 

http://www-2.cs.cmu.edu/~wjh/publications.html#Hans1992a

> If there maybe is a typing-reason, why not strings AND
> arrays should have same syntax
> ( e.g. both <name>.[index]  or both <name>.(index) )
> then maybe it would be possible to add the typical
> Array-functions (or List-functions) to the String-Library?
>
> Why not converting a string to a list with
> String.to_list

St. Xavier has rightly declared that blasphemous, and I've already done penance 
for showing it to you. I'm typing with my left hand, as all of the fingers on my 
right are broken. 

More seriously, I'm having a hard time coming up with realistic programming 
scenarios in which treating a string as a list is "the right thing". And while 
it is easy enough to convert using explode and implode, having it in the 
standard library would encourage bone headed programming. No one can stop you 
from doing it, but no one should help you do it, either. 

> or to an array with
> String.to_array

Strings are already array-like, and, even better, they are packed. 

> Arrays can be converted with Array.to_list (or vice versa
> with Array.of_list). Why not such stuff for strings?
> If they are already array-like, why not using such
> functions?
> 
> Why not using a  String.map  for application of
> char-based functions to each char?

The only time I ever want to map to a string is when I'm uppercasing or 
lowercasing. Those are already there!

> To write more abstract String-manipulation is also ok,
> so that the char-wise stuff would be on a lower level
> (inside the library, maybe implemented in C or is some
> imperative Ocaml-stuff, which the user of the library does not
> see).
> 
> OK, strings are not char-lists, and they are not char-arrays.
> At least not to the user.
> 
> 
> But it would help, to have such powerful functions like
> 
> <Module>.map
> <Module>.iter
> <Module>.fold_left
> <Module>.fold_right
> <Module>.filter
> 
> Where Module here would be one of:  Array, List, String.

Not for me. There are similarities between strings and arrays (more generally, 
random access sequences) of characters, but strings are such an important 
special case that they deserve their own library. Intuitively, lists and arrays 
are containers of things, but strings are not. 

Anyways, that's my story, and I'm sticking to it. If you don't like it, you know 
where to find Haskell! ;-)

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[William Lovas]

On Mon, Mar 03, 2003 at 12:10:45PM -0800, brogoff@speakeasy.net wrote:
> On Mon, 3 Mar 2003, Oliver Bandel wrote:
> > What I first have written about the string-stuff,
> > was: It's not FP-like, but I also would be happy
> > with a syntax, that would allow me, to use Array-functions
> > for the Strings.
> 
> That's why I said "Agitate for extensional polyorphism!". You really want a 
> way to overload similar notations. As you must now know, OCaml has no 
> overloading. Extensional polymorphism gives you that overloading, on top of 
> ML, in a way that even people who hate overloading should find fairly 
> nonthreatening. 

You keep skirting around this question by saying that what he really wants
is extensional polymorphism, but overloading is not the only way to get the
same syntax for strings and arrays.  Another way is to have them simply *be
the same thing*.  That is, is there any deep reason not to do

    type string = char array

right up front, and inherit all the Array module's functions?  We could
still keep a String library with all string-specific functions in it, but
we'd gain a unification of many function implementations, and the same
notation for random access to boot.

You mentioned that strings are packed -- meaning that they're more
efficient than generic arrays?  But doesn't O'Caml already have compiler
magic for making float arrays fast and efficient?  Why not just do the same
thing for char arrays?

You indicated towards the end of your email that you feel that strings and
arrays are different enough to warrant different representations, but i'm
not convinced yet.  What's the good reason for separating these two ideas
that are clearly very similar in interface, and probably not too different
in implementation?

William

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[Basile STARYNKEVITCH]

>>>>> "William" == William Lovas <wlovas@stwing.upenn.edu> writes:

[...]

    William> You keep skirting around this question by saying that
    William> what he really wants is extensional polymorphism, but
    William> overloading is not the only way to get the same syntax
    William> for strings and arrays.  Another way is to have them
    William> simply *be the same thing*.  That is, is there any deep
    William> reason not to do

    William>     type string = char array

    William> right up front, and inherit all the Array module's
    William> functions?  We could still keep a String library with all
    William> string-specific functions in it, but we'd gain a
    William> unification of many function implementations, and the
    William> same notation for random access to boot.

It could be interesting, but I guess that adding such specifical
implementation may seriously increase the compiler complexity and
could even explode (or at least seriously increase) the generated
code.

    William> You mentioned that strings are packed -- meaning that
    William> they're more efficient than generic arrays?  But doesn't
    William> O'Caml already have compiler magic for making float
    William> arrays fast and efficient?  Why not just do the same
    William> thing for char arrays?

I do share the wish but would tend to believe that it is programmer
time consuming. For example, grep-ing (case insensitively) for float
in the compilers gives a lot of occurrences.

Perhaps a long term dream might be to be able to provide specific
implementations for different instances of variable types,
e.g. different implementations for sets of float versus sets of object
instances.

Regarding strings I would tend to think that separating mutable
strings from read-only strings could be useful, and 16bits or 32bits
unicode strings might be desirable.

Does any one have ideas on how to implement localisation &
internationalisation of applications?


-- 

Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
alias: basile<at>tunes<dot>org 
8, rue de la Faïencerie, 92340 Bourg La Reine, France

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[Nicolas George]

[-- Attachment #1: Type: text/plain, Size: 1351 bytes --]

Le tridi 13 ventôse, an CCXI, William Lovas a écrit :
>     type string = char array

BTW, *this* is the worst conceptual bug in OCaml, directly imported from
the C. Strings and arrays are totally different concept.

- Strings need fast concatenation and parts extraction, arrays do not
  need that.

- Arrays need fast random access by numeric index, strings do not need
  that.

My dream for a future release of OCaml would be something like that:

- string is an abstract type, with fast concatenation (especially when
  one of the operands is not used anymore; this is like tail-recursion
  optimisation, but for strings);

- there is also a `cursor' type, which is something like a pair
  (string, index in that string);

- there are functions to move cursors forward and backward, take
  substrings between two cursors, etc.;

- while we're at breaking compatibility, strings are fully Unicode
  capable;

- there is a buffer type which is a byte array for low-level operations,
  and conversion functions between buffers and strings, with several
  possible encodings;

- there is a regular expression module with a syntax as near as perl's
  as possible (because perl's regexps are great, and we do not want to
  have to remember yet another regexps variant), which returns cursors
  for matched substrings.

[-- Attachment #2: Type: application/pgp-signature, Size: 185 bytes --]

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[Diego Olivier Fernandez Pons]

    Bonjour,

Some of the features you wish are 'not so hard to implement', at least
if you already have 'conceptually bugged low-level' strings :

> - Strings need fast concatenation and parts extraction, arrays do
> not need that.

Any 'fast mergeable' data structure will do it :

- trees of strings
- fast catenable lists

> - Arrays need fast random access by numeric index, strings do not
> need that.

You can easily hava a (log n/k + 1) acces where n is the total size of
the string and k is the size of each bucket (if you choose a data
structure with constant buffer size)

> - string is an abstract type, with fast concatenation (especially
> when one of the operands is not used anymore; this is like
> tail-recursion optimisation, but for strings);

You just have to free the unused buckets of you string. If you really
want tail recursive functions try a 'list' based data structure. That
seems to be what Alain Frisch did in CDuce.

> - there is also a `cursor' type, which is something like a pair
> (string, index in that string);

Easy... You can even do better : using a zipper you have constant
acces to the pointed element (instead of log n), with some bookkeeping
every time you move the index.

> - there are functions to move cursors forward and backward, take
>   substrings between two cursors, etc.;

Zippers only allow one (functional) pointer by data structure. For
this you will have to stick to an index with logarithmic time acces.
You can of course mix both (zippers + indexes)

> - there is a buffer type which is a byte array for low-level
> operations, and conversion functions between buffers and strings,
> with several possible encodings;

Yes... strings.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[William D. Neumann]

On Tue, 4 Mar 2003, Diego Olivier Fernandez Pons wrote:

> > - there is a buffer type which is a byte array for low-level
> > operations, and conversion functions between buffers and strings,
> > with several possible encodings;
>
> Yes... strings.

Unfortunately strings don't act like byte arrays (to the best of my
knowledge anyway -- I'd love to find out I'm wrong).  If you want to do
any low level operations on the bytes, you first need to convert the chars
to ints (and by low level, I'm talking about shifts, rotates, ands, ors,
xors, etc), perform your ops, then convert back to chars before
re-inserting them into the string, and this is slooooow.

Since I do crypto for a living, I run into these problems all the time.
fortunately, they haven't forced me to drop OCaml for C in general, but I
have had to step back into C for a couple of programs that really needed
the extra speed boost.  Efficient byte and word arrays would be wonderful
tools to add to my chest.

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[Xavier Leroy]

> Unfortunately strings don't act like byte arrays (to the best of my
> knowledge anyway -- I'd love to find out I'm wrong).  If you want to do
> any low level operations on the bytes, you first need to convert the chars
> to ints (and by low level, I'm talking about shifts, rotates, ands, ors,
> xors, etc), perform your ops, then convert back to chars before
> re-inserting them into the string, and this is slooooow.

Actually, Char.code (the conversion from char to int) is a no-op, but
it's true that Char.chr (the conversion from int to char) is slower
because it checks that its argument lies within [0..255].

An alternative is Char.unsafe_chr, which is a no-op (but doesn't
perform the range check).

A better alternative is to declare

external get_byte: string -> int -> int = "%string_safe_get"
external set_byte: string -> int -> int -> unit = "%string_safe_set"

and use these two functions to access strings as if they were byte
arrays.  set_byte will store the low 8 bits of its third argument, so
you'd save on "land 0xFF" operations too.

> Since I do crypto for a living, I run into these problems all the time.

Sure.  The two declarations above should help both with performance
and legibility of your code.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[William D. Neumann]

On Tue, 4 Mar 2003, Xavier Leroy wrote:

<A message chock-full of wonderful suggestions regarding strings/byte
arrays>

Fabulous!  This information ought to make my life a lot happier.  Well, my
work life at least.  I doubt any of it will make for a great pick-up line
with the ladies...

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[Nicolas George]

[-- Attachment #1: Type: text/plain, Size: 1106 bytes --]

Le quartidi 14 ventôse, an CCXI, Diego Olivier Fernandez Pons a écrit :
> Some of the features you wish are 'not so hard to implement', at least
> if you already have 'conceptually bugged low-level' strings :

Of course it is possible to do it in "userland". But having it as part
of language has several advantages: cleaner syntax, compile-time
optimizations, code uniqueness.

> You can easily hava a (log n/k + 1) acces where n is the total size of
> the string and k is the size of each bucket (if you choose a data
> structure with constant buffer size)

I really feel that strings do not need fast random access by integer
index at all.

>> - there is also a `cursor' type, which is something like a pair
>> (string, index in that string);
> Easy... You can even do better : using a zipper you have constant
> acces to the pointed element

The cursors I was speaking _must_ provide constant-time access! And
(mean-)constant incrementation/decrementation.


Le quartidi 14 ventôse, an CCXI, David Chase a écrit :
>         sb.append(...);

This is really imperative style.

[-- Attachment #2: Type: application/pgp-signature, Size: 185 bytes --]

Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[David Chase]

At 01:43 PM 3/4/2003 +0100, Diego Olivier Fernandez Pons wrote:
>    Bonjour,
>
>Some of the features you wish are 'not so hard to implement', at least
>if you already have 'conceptually bugged low-level' strings :

I hope you aren't proposing that everyone implement the "String" data
structure that they wish they really had.  Strings are too basic, and
too common, to be left to this.

Consider Java's approach of String and StringBuffer.  My main gripe
(after years of use) is that too many functions should take a StringBuffer
(which should probably be an abstract type, though there is indeed some
loss of efficiency) and return a StringBuffer, rather than simply returning
a String.  From an optimization point-of-view, the most useful thing
for performance would be to find a way to have an abstract type with
non-abstract synchronization.  All StringBuffer ops are synchronized,
and probably should be, but a compiler and idioms can help IF THE
SYNCHRONIZATION IS EXPOSED.  That is, in Java, this code

  StringBuffer sb ...
  synchronized (sb) { // I know that sb is thread-private
     while (...) {
        sb.append(...);
     }
  }

is likely to run faster than it would without the outer synchronization
because the JIT compiler can see that the (non-abstract, exposed, final)
StringBuffer synchronizations are redundant.

On-the-other-hand, multithreaded programming appears to be so hard
for the typical and even good-typical programmer, that I'd be interested
in seeing if there were better ways to do it (say, threads communicating
only through queues).

>> - Arrays need fast random access by numeric index, strings do not
>> need that.
>
>You can easily hava a (log n/k + 1) acces where n is the total size of
>the string and k is the size of each bucket (if you choose a data
>structure with constant buffer size)

That will be noticeably slower.  In the Java compiler that I worked
on, the String operations were specially recognized by the compiler
so that it could infer success of string bounds checks, and that
"minor" optimization was noticeably beneficial.  On the other hand,
with some cleverness and a biggish K, you might be able to get most
of the benefit simply from the "bounds check" (as in, small strings
fit in their first and only bucket, illegal indices necessarily also
overflow off the end of the first bucket).

David Chase


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[Issac Trotts]

William Lovas wrote:

>On Mon, Mar 03, 2003 at 12:10:45PM -0800, brogoff@speakeasy.net wrote:
>  
>
>>On Mon, 3 Mar 2003, Oliver Bandel wrote:
>>    
>>
>>>What I first have written about the string-stuff,
>>>was: It's not FP-like, but I also would be happy
>>>with a syntax, that would allow me, to use Array-functions
>>>for the Strings.
>>>      
>>>
>>That's why I said "Agitate for extensional polyorphism!". You really want a 
>>way to overload similar notations. As you must now know, OCaml has no 
>>overloading. Extensional polymorphism gives you that overloading, on top of 
>>ML, in a way that even people who hate overloading should find fairly 
>>nonthreatening. 
>>    
>>
>
>You keep skirting around this question by saying that what he really wants
>is extensional polymorphism, but overloading is not the only way to get the
>same syntax for strings and arrays.  Another way is to have them simply *be
>the same thing*.  That is, is there any deep reason not to do
>
>    type string = char array
>
>right up front, and inherit all the Array module's functions?  We could
>still keep a String library with all string-specific functions in it, but
>we'd gain a unification of many function implementations, and the same
>notation for random access to boot.
>
>You mentioned that strings are packed -- meaning that they're more
>efficient than generic arrays?  But doesn't O'Caml already have compiler
>magic for making float arrays fast and efficient?  Why not just do the same
>thing for char arrays?
>
Char arrays take up four times as much space as strings, but there is a 
tradeoff
of space versus time.  The statement

  let a = Array.make 2000000 ' ';;

takes no noticable time, but
 
  let s = String.make 2000000 ' ';;

takes about 7 seconds to run on my computer.

Issac Trotts

>
>You indicated towards the end of your email that you feel that strings and
>arrays are different enough to warrant different representations, but i'm
>not convinced yet.  What's the good reason for separating these two ideas
>that are clearly very similar in interface, and probably not too different
>in implementation?
>
>William
>
>-------------------
>To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
>Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
>Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>
>
>  
>



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[Alain.Frisch]

On Mon, 3 Mar 2003, Issac Trotts wrote:

> Char arrays take up four times as much space as strings, but there is a
> tradeoff
> of space versus time.  The statement
>
>   let a = Array.make 2000000 ' ';;
>
> takes no noticable time, but
>
>   let s = String.make 2000000 ' ';;
>
> takes about 7 seconds to run on my computer.


Oh really ?  I'm interested in your benchmark methodology. Hint: it may
be the case that the pretty-printing of s in the toplevel is slower that
the pretty-printing of a, but this is not relevant, is it ?

As for me, I get:

glouglou ~/tmp $ cat a.ml
let a = Array.make 2000000 ' ';;
glouglou ~/tmp $ time ocaml a.ml
ocaml a.ml  0,16s user 0,01s system 101% cpu 0,167 total
glouglou ~/tmp $ cat s.ml
let s = String.make 2000000 ' ';;
glouglou ~/tmp $ time ocaml s.ml
ocaml s.ml  0,04s user 0,02s system 102% cpu 0,058 total
glouglou ~/tmp $ cat x.ml
glouglou ~/tmp $ time ocaml x.ml
ocaml x.ml  0,03s user 0,01s system 108% cpu 0,037 total

(x.ml is an empty file, to evaluate ocaml toplevel startup time)
Which seems to indicate that String.make is unsurpisingly a lot faster
than Array.make.

-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[Issac Trotts]

Alain.Frisch@ens.fr wrote:

>On Mon, 3 Mar 2003, Issac Trotts wrote:
>
>  
>
>>Char arrays take up four times as much space as strings, but there is a
>>tradeoff
>>of space versus time.  The statement
>>
>>  let a = Array.make 2000000 ' ';;
>>
>>takes no noticable time, but
>>
>>  let s = String.make 2000000 ' ';;
>>
>>takes about 7 seconds to run on my computer.
>>    
>>
>
>
>Oh really ?  I'm interested in your benchmark methodology. Hint: it may
>be the case that the pretty-printing of s in the toplevel is slower that
>the pretty-printing of a, but this is not relevant, is it ?
>
>
>As for me, I get:
>
>glouglou ~/tmp $ cat a.ml
>let a = Array.make 2000000 ' ';;
>glouglou ~/tmp $ time ocaml a.ml
>ocaml a.ml  0,16s user 0,01s system 101% cpu 0,167 total
>glouglou ~/tmp $ cat s.ml
>let s = String.make 2000000 ' ';;
>glouglou ~/tmp $ time ocaml s.ml
>ocaml s.ml  0,04s user 0,02s system 102% cpu 0,058 total
>glouglou ~/tmp $ cat x.ml
>glouglou ~/tmp $ time ocaml x.ml
>ocaml x.ml  0,03s user 0,01s system 108% cpu 0,037 total
>
>(x.ml is an empty file, to evaluate ocaml toplevel startup time)
>Which seems to indicate that String.make is unsurpisingly a lot faster
>than Array.make.
>
>-- Alain
>  
>
You're right.  Thanks for catching my error.  

Issac





-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[Olivier Andrieu]

 Issac Trotts [Monday 3 March 2003] :
 > Char arrays take up four times as much space as strings, but there is a 
 > tradeoff
 > of space versus time.  The statement
 > 
 >   let a = Array.make 2000000 ' ';;
 > 
 > takes no noticable time, but
 >  
 >   let s = String.make 2000000 ' ';;
 > 
 > takes about 7 seconds to run on my computer.

Er ... what are you talking about ? If you're talking about the
toplevel, that's completely irrelevant because what takes time then is
merely the _printing_ of the value. Strings are printed entirely by
the toplevel (not very smart for long strings), whereas only the first
values of arrays are printed. 

String.make and Array.make still do the same thing : allocate some
space and fill it with an initial value. But array of chars take up
four times as much space and thus it usually takes longer to allocate
such a big array.

-- 
   Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [oliver: Re: [Caml-list] Strings as arrays or lists...]

[brogoff]

On Mon, 3 Mar 2003, William Lovas wrote:
> On Mon, Mar 03, 2003 at 12:10:45PM -0800, brogoff@speakeasy.net wrote:
> > That's why I said "Agitate for extensional polyorphism!". You really want a 
> > way to overload similar notations. As you must now know, OCaml has no 
> > overloading. Extensional polymorphism gives you that overloading, on top of 
> > ML, in a way that even people who hate overloading should find fairly 
> > nonthreatening. 
> 
> You keep skirting around this question by saying that what he really wants
> is extensional polymorphism, but overloading is not the only way to get the
> same syntax for strings and arrays.  Another way is to have them simply *be
> the same thing*.  That is, is there any deep reason not to do
> 
>     type string = char array

Because strings are packed, and OCaml has no facility for expressing that the 
char array should be packed. I mentioned Clean earlier, and I'm pretty sure I 
mentioned that Clean strings are UNBOXED arrays of characters. No way to express 
that in OCaml now. If you really want that, you would ask for Bigarrays instead 
of arrays, but there may be performance problems there, as the Bigarray 
representation is tuned for different uses. 

> right up front, and inherit all the Array module's functions?  We could
> still keep a String library with all string-specific functions in it, but
> we'd gain a unification of many function implementations, and the same
> notation for random access to boot.

Even if this were a good idea, which I don't think it is, I'd probably still 
have an Array module and a String module with different interfaces. The 
similarity between Arrays and Strings is that their elements are accessed by 
integers in constant time. 

> You mentioned that strings are packed -- meaning that they're more
> efficient than generic arrays?  

It means that characters are packed; which means that you can put more of them 
into the array, which means that strings can be bigger than arrays. Of course, 
if we had 32bit chars that wouldn't be true. 

> But doesn't O'Caml already have compiler
> magic for making float arrays fast and efficient? 

Yup. 

>  Why not just do the same thing for char arrays?

Compiler complexity? I'll let an implementor answer, if they're not already 
bored to tears by this thread. I understand what you want, and if it were no 
problem to just pack everything, that would be great, but I think it's a bit 
more complex than that.

> You indicated towards the end of your email that you feel that strings and
> arrays are different enough to warrant different representations, 

Actually, no. I indicated that they are different enough to warrant different 
interfaces, though I suppose from there you could infer from that that different 
representations may be warranted as well. 

In fact, as I stated earlier (I hope?), I don't think one, single string 
representation will satisfy everyone. It certainly won't satisfy me, and I'm 
only one person. Given that, and given that I do understand the OP's desire to 
share notation, I think some amount of overloading would be a good 
way to address this problem, as well as many others. Aren't hash tables kind of 
like arrays too? Can't we use the same notation to access them as for arrays and 
strings? Ditto for association lists. The tool for addressing this problem is 
overloading (of the access function), not shoehorning all of these things into 
one representation.

> What's the good reason for separating these two ideas
> that are clearly very similar in interface, and probably not too different
> in implementation?

I don't think they're all that similar in interface. I do agree with you that 
the representations could be pretty close though, at least for the simplest kind 
of string. But ropes (for example) have a very different representation than 
simple strings, yet an almost identical interface. What to do? 

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] extensional polymorphism

[james woodyatt]

On Monday, Mar 3, 2003, at 12:10 US/Pacific, brogoff@speakeasy.net 
wrote:
>
> That's why I said "Agitate for extensional polyorphism!". You really 
> want a
> way to overload similar notations.

If "extensional polymorphism" is what I want in order to be able to 
define an operator ( >>= ) that performs the monad bind operation on 
arbitrary monads, then yeah-- I'm all for it.

I recently discovered the power of monadic programming, but I am in no 
hurry to switch to Haskell in order to get a nice clean syntax for it.

If "extensional polymorphism" will get me a cleaner syntax for monadic 
programming without forcing me to give up all the things that make 
Ocaml the best language in the universe for imperative programming, 
then sign me up right here right now.

How would extensional polymorphism get me what I want?


-- 
j h woodyatt <jhw@wetware.com>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] extensional polymorphism

[brogoff]

On Mon, 3 Mar 2003, james woodyatt wrote:
> On Monday, Mar 3, 2003, at 12:10 US/Pacific, brogoff@speakeasy.net 
> wrote:
> >
> > That's why I said "Agitate for extensional polyorphism!". You really 
> > want a
> > way to overload similar notations.
> 
> If "extensional polymorphism" is what I want in order to be able to 
> define an operator ( >>= ) that performs the monad bind operation on 
> arbitrary monads, then yeah-- I'm all for it.
> 
> I recently discovered the power of monadic programming, but I am in no 
> hurry to switch to Haskell in order to get a nice clean syntax for it.

You can do a fair bit of monadic programming in OCaml now, using the module 
system. If you are interested, I'll show you, but you'll learn more by just 
translating Wadler's early papers into OCaml. If you want to do complicated 
monadics with several different monad types intertwined in the same section of 
code, that may be tricky. 

Also, OCaml is an imperative language, so you have lots of monads built in :-). 
One of the problems I have with Haskell is that while there are a few examples 
where it just suits the problem so well that the solution is magically 
concise and beautiful, I find that there are more places where the emphasis on 
purity transforms trivial programming problems into a PhD level research 
problems. 

> If "extensional polymorphism" will get me a cleaner syntax for monadic 
> programming without forcing me to give up all the things that make 
> Ocaml the best language in the universe for imperative programming, 
> then sign me up right here right now.
>
> How would extensional polymorphism get me what I want?

It may ameliorate the problem I cited above in which you're juggling many monads 
in the same section of code and you don't want to use (module) qualified types 
to distinguish your bindMs and returnMs or whatever you want to call your 
operations. 

-- Brian

PS: Here's a signature, use it to constrain modules, and use functors over these 
modules to express some monadic ops.

module type MONAD =
  sig
    type 'a t 
    val returnM : 'a -> 'a t 
    val bindM : 'a t -> ('a -> 'b t) -> 'b t
    val mapM : ('a -> 'b) -> 'a t -> 'b t
    val joinM : 'a t t -> 'a t 
    (* Ad-hoc show function *)
    val showM : 'a t -> ('a -> string) -> string
  end

and a List monad

module List_monad : MONAD = 
  struct
    type 'a t = 'a list
    let returnM x = [x]
    let bindM m f = List.flatten (List.map f m)  
    let mapM f m = List.map f m
    let joinM mm = List.flatten mm

    let showM m f = 
      List.fold_right 
	(fun x s -> 
	  if s = "" then (f x) ^ s 
	  else (f x) ^ "; " ^ s)
	m ""
  end




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] extensional polymorphism

[james woodyatt]

On Monday, Mar 3, 2003, at 17:10 US/Pacific, brogoff@speakeasy.net 
wrote:
> On Mon, 3 Mar 2003, james woodyatt wrote:
>> On Monday, Mar 3, 2003, at 12:10 US/Pacific, brogoff@speakeasy.net  
>> wrote:
>>>
>>> That's why I said "Agitate for extensional polyorphism!". You really 
>>> want a way to overload similar notations.
>>
>> If "extensional polymorphism" is what I want in order to be able to 
>> define an operator ( >>= ) that performs the monad bind operation on 
>> arbitrary monads, then yeah-- I'm all for it.
>>
>> I recently discovered the power of monadic programming, but I am in 
>> no hurry to switch to Haskell in order to get a nice clean syntax for 
>> it.
>
> You can do a fair bit of monadic programming in OCaml now, using the 
> module
> system. If you are interested, I'll show you, but you'll learn more by 
> just
> translating Wadler's early papers into OCaml. If you want to do 
> complicated
> monadics with several different monad types intertwined in the same 
> section of
> code, that may be tricky.

I want to do the tricky stuff.  I've moved beyond the toys, and I'm 
beginning to discover all the interesting ways you can combine monads 
of different types.  So far, I've been able to get away with limiting 
the scope of my monad types, but I'm wondering about what I can do when 
I don't have to worry about those limits.

I tend to collect multiple monad types, each with a different number of 
type parameters to them.

> Also, OCaml is an imperative language, so you have lots of monads 
> built in :-).

Yeah, and I prefer them when I can use them.  It's just that I've 
encountered a problem where I really want to avoid using the "built-in 
monad" types in fairly specific *parts* of my program.  And I don't 
want to be constrained by the requirement of Haskell to maintain 
referential transparency *everywhere* in my program.

> One of the problems I have with Haskell is that while there are a few 
> examples
> where it just suits the problem so well that the solution is magically
> concise and beautiful, I find that there are more places where the 
> emphasis on
> purity transforms trivial programming problems into a PhD level 
> research
> problems.
>
>> If "extensional polymorphism" will get me a cleaner syntax for monadic
>> programming without forcing me to give up all the things that make
>> Ocaml the best language in the universe for imperative programming,
>> then sign me up right here right now.
>>
>> How would extensional polymorphism get me what I want?
>
> It may ameliorate the problem I cited above in which you're juggling 
> many monads
> in the same section of code and you don't want to use (module) 
> qualified types
> to distinguish your bindMs and returnMs or whatever you want to call 
> your
> operations.

I just read the G'CAML readme and the Jun Furuse thesis on its home 
page.  It looks like it would basically work for what I want.   Sign me 
up for wanting extensional polymorphism in the Ocaml core language.


-- 
j h woodyatt <jhw@wetware.com>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners