www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - const and phobos string functions

reply Regan Heath <regan netmail.co.nz> writes:
I wanted to post this real/concrete case of where 'const' and the 
current phobos implementation of certain string routines combine to 
cause a few irritations, inefficiencies and some IMO illogical behaviour.

Note in the code below 'remove' is a template function which uses 
'memmove' to remove an item from the array.

(The code):

char[][] tmp;

tmp = cast(char[][])splitlines(cast(string)read(a[3..$]));
foreach(ref line; tmp) line = cast(char[])strip(line);
for(int i = 0; i < tmp.length; i++)
{
   if (tmp[i].length == 0)
     tmp.remove(i);
}

(The problem):

Notice all the cast()'s required above.  I am of the belief that casting 
should only be done in exceptional circumstances, and this shouldn't be 
one of them.

If you consider char[] as being a a string which you are the full owner 
of, you can change it at will, and 'string' as being a string which you 
are not the full owner of, as you can only read it then in many cases it 
doesn't make sense to pass a char[] to a function and get a 'string' 
back, unless the function has 'taken ownership' of the string data or is 
returning different string data which you are not the owner of.

The obvious case where it make sense is a property setter which might 
copy the input and return a 'string' reference to the copy.

In the cases above (splitlines, strip) it doesn't make sense for the 
function to 'take ownership' of the strings as they do not store them 
beyond the lifetime of the function call.

Therefore if passed a char[] they should return char[][] and char[] 
respectively.

Of course if passed 'string' they should return 'string[]' and 'string' 
respectively.

(The solution):

Given the requirements it seems templating is the obvious solution.  I 
have described in earlier posts (though these relate to tolower 
specifically):

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=55335
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=55337

All the phobos routines should likely be templated in the same fashion.

Regan
Aug 01 2007
parent reply Kirk McDonald <kirklin.mcdonald gmail.com> writes:
Regan Heath wrote:

 I wanted to post this real/concrete case of where 'const' and the 
 current phobos implementation of certain string routines combine to 
 cause a few irritations, inefficiencies and some IMO illogical behaviour.
 
 Note in the code below 'remove' is a template function which uses 
 'memmove' to remove an item from the array.
 
 (The code):
 
 char[][] tmp;
 
 tmp = cast(char[][])splitlines(cast(string)read(a[3..$]));
 foreach(ref line; tmp) line = cast(char[])strip(line);
 for(int i = 0; i < tmp.length; i++)
 {
   if (tmp[i].length == 0)
     tmp.remove(i);
 }
 
 (The problem):
 
 Notice all the cast()'s required above.  I am of the belief that casting 
 should only be done in exceptional circumstances, and this shouldn't be 
 one of them.
 
 If you consider char[] as being a a string which you are the full owner 
 of, you can change it at will, and 'string' as being a string which you 
 are not the full owner of, as you can only read it then in many cases it 
 doesn't make sense to pass a char[] to a function and get a 'string' 
 back, unless the function has 'taken ownership' of the string data or is 
 returning different string data which you are not the owner of.
 
 The obvious case where it make sense is a property setter which might 
 copy the input and return a 'string' reference to the copy.
 
 In the cases above (splitlines, strip) it doesn't make sense for the 
 function to 'take ownership' of the strings as they do not store them 
 beyond the lifetime of the function call.
 
 Therefore if passed a char[] they should return char[][] and char[] 
 respectively.
 
 Of course if passed 'string' they should return 'string[]' and 'string' 
 respectively.
 
 (The solution):
 
 Given the requirements it seems templating is the obvious solution.  I 
 have described in earlier posts (though these relate to tolower 
 specifically):
 
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmar
.D&article_id=55335 
 
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmar
.D&article_id=55337 
 
 
 All the phobos routines should likely be templated in the same fashion.
 
 Regan


A lot of those casts go away if tmp is a string[].

-- 
Kirk McDonald
http://kirkmcdonald.blogspot.com
Pyd: Connecting D and Python
http://pyd.dsource.org
Aug 01 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Kirk McDonald wrote:

 Regan Heath wrote:

 Note in the code below 'remove' is a template function which uses 
 'memmove' to remove an item from the array.

 (The code):

 char[][] tmp;

 tmp = cast(char[][])splitlines(cast(string)read(a[3..$]));
 foreach(ref line; tmp) line = cast(char[])strip(line);
 for(int i = 0; i < tmp.length; i++)
 {
   if (tmp[i].length == 0)
     tmp.remove(i);
 }


 
 A lot of those casts go away if tmp is a string[].


True.  I knew someone would realise/spot that.  ;)  I don't think it 
solves the basic problem however, which is why I didn't mention it in me 
original post, perhaps I should have.  Let me explain further...

Imagine calling splitlines on char[] getting string[] then calling 
tolower on each line.

Because you have a string[], tolower always has to dup any line it wants 
to change.

If you template tolower and splitlines so that they accept const and 
non-const input and return the same then in the case where it gets 
non-const input tolower can avoid duplication (AKA *performance gain*)

The same is true for any function (phobos or otherwise) which will (or 
even might) modify the input data.

In the case of splitlines or strip they don't need to modify the input 
data so there is no performance gain by templating them and handling 
string and char[] differently.

However, what you do get is a function which no longer 'takes ownership' 
of the array passed and can then be used in a sequence of modifications 
without having to cast or dup to 'take ownership back' by brute force 
(the problem my code illustrates)

To think of it in the abstract sense, by passing a char[] you're passing 
ownership of the data to the function, when it returns it is passing 
ownership back again in the form char[] or char[][].

When you pass string you're not passing ownership and the function has 
no other option but to duplicate the input when it wants to modify it.

In the current case of tolower it returns string and therefore retains 
ownership of the string, despite the fact that it promptly forgets it 
ever existed.  Not much we can do about this case because we cannot 
decide what to return from a function at runtime.

Regan
Aug 02 2007
parent reply Kirk McDonald <kirklin.mcdonald gmail.com> writes:
Regan Heath wrote:

 Kirk McDonald wrote:

 Regan Heath wrote:

 Note in the code below 'remove' is a template function which uses 
 'memmove' to remove an item from the array.

 (The code):

 char[][] tmp;

 tmp = cast(char[][])splitlines(cast(string)read(a[3..$]));
 foreach(ref line; tmp) line = cast(char[])strip(line);
 for(int i = 0; i < tmp.length; i++)
 {
   if (tmp[i].length == 0)
     tmp.remove(i);
 }


 A lot of those casts go away if tmp is a string[].


 
 True.  I knew someone would realise/spot that.  ;)  I don't think it 
 solves the basic problem however, which is why I didn't mention it in me 
 original post, perhaps I should have.  Let me explain further...
 
 Imagine calling splitlines on char[] getting string[] then calling 
 tolower on each line.
 
 Because you have a string[], tolower always has to dup any line it wants 
 to change.
 
 If you template tolower and splitlines so that they accept const and 
 non-const input and return the same then in the case where it gets 
 non-const input tolower can avoid duplication (AKA *performance gain*)
 
 The same is true for any function (phobos or otherwise) which will (or 
 even might) modify the input data.
 
 In the case of splitlines or strip they don't need to modify the input 
 data so there is no performance gain by templating them and handling 
 string and char[] differently.
 
 However, what you do get is a function which no longer 'takes ownership' 
 of the array passed and can then be used in a sequence of modifications 
 without having to cast or dup to 'take ownership back' by brute force 
 (the problem my code illustrates)
 
 To think of it in the abstract sense, by passing a char[] you're passing 
 ownership of the data to the function, when it returns it is passing 
 ownership back again in the form char[] or char[][].
 
 When you pass string you're not passing ownership and the function has 
 no other option but to duplicate the input when it wants to modify it.
 
 In the current case of tolower it returns string and therefore retains 
 ownership of the string, despite the fact that it promptly forgets it 
 ever existed.  Not much we can do about this case because we cannot 
 decide what to return from a function at runtime.
 
 Regan


In this particular case, you could call this mutating form of tolower() 
on the buffer returned from read(), and then split it afterwards 
(perhaps yielding strings). This makes a certain degree of logical 
sense: If you'd wanted to keep the original contents of the buffer, 
you'd have to duplicate it at some point anyway. Since you don't, you 
can alter it immediately.

I submit the following Python idiom: Functions which mutate their 
arguments should return nothing. That is:

// Return new string
string tolower(string);
// Mutate argument
void tolower(char[]);

This rather strictly highlights the difference between char[] and 
string, and makes it essentially impossible to mix up library functions 
differentiated in this way.

-- 
Kirk McDonald
http://kirkmcdonald.blogspot.com
Pyd: Connecting D and Python
http://pyd.dsource.org
Aug 02 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Kirk McDonald wrote:

 In this particular case, you could call this mutating form of tolower() 
 on the buffer returned from read(), and then split it afterwards 
 (perhaps yielding strings). This makes a certain degree of logical 
 sense: If you'd wanted to keep the original contents of the buffer, 
 you'd have to duplicate it at some point anyway. Since you don't, you 
 can alter it immediately.


Sure, that solves this particular case.  But, do you agree there is 
generally a problem, or shall I continue to dream up example cases for 
you to solve in some other manner :)


 I submit the following Python idiom: Functions which mutate their 
 arguments should return nothing. That is:
 
 // Return new string
 string tolower(string);
 // Mutate argument
 void tolower(char[]);
 
 This rather strictly highlights the difference between char[] and 
 string, and makes it essentially impossible to mix up library functions 
 differentiated in this way.


That's all well and good until you want to write:

char[] s;
...
foo(tolower(s));

If you template tolower in the manner I described it's not possible to 
mix it up and call the wrong one anyway (as it selects the correct one 
based on the input) so it's a non-problem.

Regan
Aug 02 2007
parent reply Reiner Pope <some address.com> writes:
Regan Heath wrote:

 Kirk McDonald wrote:

 In this particular case, you could call this mutating form of 
 tolower() on the buffer returned from read(), and then split it 
 afterwards (perhaps yielding strings). This makes a certain degree of 
 logical sense: If you'd wanted to keep the original contents of the 
 buffer, you'd have to duplicate it at some point anyway. Since you 
 don't, you can alter it immediately.


 
 Sure, that solves this particular case.  But, do you agree there is 
 generally a problem, or shall I continue to dream up example cases for 
 you to solve in some other manner :)
 

 I submit the following Python idiom: Functions which mutate their 
 arguments should return nothing. That is:

 // Return new string
 string tolower(string);
 // Mutate argument
 void tolower(char[]);

 This rather strictly highlights the difference between char[] and 
 string, and makes it essentially impossible to mix up library 
 functions differentiated in this way.


 
 That's all well and good until you want to write:
 
 char[] s;
 ...
 foo(tolower(s));
 
 If you template tolower in the manner I described it's not possible to 
 mix it up and call the wrong one anyway (as it selects the correct one 
 based on the input) so it's a non-problem.
 
 Regan


I think the code you gave here would be misleading. For instance, 
suppose you had your templated overloads, effectively giving you

    // copy-on-write
    string tolower(string);
    // in-place
    char[] tolower(char[]);

Then you would get surprising results if you did this:

char[] s = "Hello World!".dup;
int a = howManyLettersDiffer(tolower(s), s);
assert (a == 2); // assert failed, a is actually 0

I think avoiding this is exactly why Kirk suggested his overloads.

   -- Reiner
Aug 02 2007
parent reply Regan Heath <regan netmail.co.nz> writes:
Reiner Pope wrote:

 Regan Heath wrote:

 Kirk McDonald wrote:

 I submit the following Python idiom: Functions which mutate their 
 arguments should return nothing. That is:

 // Return new string
 string tolower(string);
 // Mutate argument
 void tolower(char[]);

 This rather strictly highlights the difference between char[] and 
 string, and makes it essentially impossible to mix up library 
 functions differentiated in this way.


 That's all well and good until you want to write:

 char[] s;
 ...
 foo(tolower(s));

 If you template tolower in the manner I described it's not possible to 
 mix it up and call the wrong one anyway (as it selects the correct one 
 based on the input) so it's a non-problem.

 Regan


 
 I think the code you gave here would be misleading. For instance, 
 suppose you had your templated overloads, effectively giving you
 
    // copy-on-write
    string tolower(string);
    // in-place
    char[] tolower(char[]);
 
 Then you would get surprising results if you did this:
 
 char[] s = "Hello World!".dup;
 int a = howManyLettersDiffer(tolower(s), s);
 assert (a == 2); // assert failed, a is actually 0
 
 I think avoiding this is exactly why Kirk suggested his overloads.


Good point.

Using Kirk's Python'esque function signatures you'd have:

char[] s = "Hello World!".dup;
tolower(s);
int a = howManyLettersDiffer(s, s);
assert (a == 2); // assert failed, a is actually 0

which is immediately and obviously a pointless operation, requring a 
re-code to:

char[] s = "Hello World!".dup;
char[] s2 = s.dup
tolower(s2);
int a = howManyLettersDiffer(s2, s);
assert (a == 2); // assert failed, a is actually 0

And the 'string' case:

string s = "Hello World!";
int a = howManyLettersDiffer(tolower(s), s);
assert (a == 2); // assert failed, a is actually 0

which would already behave as desired.

It seems that tolower is always going to have to 'copy on write' and 
return that copy.

But, that doesn't stop you templating it so that it returns the copy as 
char[] when you pass char[] (which is all I really wanted in the first 
place) :)

Unfortunately as we cannot overload on return type it would prevent an 
inplace tolower in the form (given by Kirk):

void tolower(char[])

Instead perhaps we need a naming convention for inplace modifying 
functions, options:

void <func>Inplace(<args>)
void <func>IP(<args>)       // "IP" stands for inplace
void <func>M(<args>)        // "M" stands for mutates

or something like those.

Regan
Aug 02 2007
next sibling parent reply Reiner Pope <some address.com> writes:
Regan Heath wrote:

 Reiner Pope wrote:

 Regan Heath wrote:

 Kirk McDonald wrote:

 I submit the following Python idiom: Functions which mutate their 
 arguments should return nothing. That is:

 // Return new string
 string tolower(string);
 // Mutate argument
 void tolower(char[]);

 This rather strictly highlights the difference between char[] and 
 string, and makes it essentially impossible to mix up library 
 functions differentiated in this way.


 That's all well and good until you want to write:

 char[] s;
 ...
 foo(tolower(s));

 If you template tolower in the manner I described it's not possible 
 to mix it up and call the wrong one anyway (as it selects the correct 
 one based on the input) so it's a non-problem.

 Regan


 I think the code you gave here would be misleading. For instance, 
 suppose you had your templated overloads, effectively giving you

    // copy-on-write
    string tolower(string);
    // in-place
    char[] tolower(char[]);

 Then you would get surprising results if you did this:

 char[] s = "Hello World!".dup;
 int a = howManyLettersDiffer(tolower(s), s);
 assert (a == 2); // assert failed, a is actually 0

 I think avoiding this is exactly why Kirk suggested his overloads.


 
 Good point.
 
 Using Kirk's Python'esque function signatures you'd have:
 
 char[] s = "Hello World!".dup;
 tolower(s);
 int a = howManyLettersDiffer(s, s);
 assert (a == 2); // assert failed, a is actually 0
 
 which is immediately and obviously a pointless operation, requring a 
 re-code to:
 
 char[] s = "Hello World!".dup;
 char[] s2 = s.dup
 tolower(s2);
 int a = howManyLettersDiffer(s2, s);
 assert (a == 2); // assert failed, a is actually 0
 
 And the 'string' case:
 
 string s = "Hello World!";
 int a = howManyLettersDiffer(tolower(s), s);
 assert (a == 2); // assert failed, a is actually 0
 
 which would already behave as desired.
 
 It seems that tolower is always going to have to 'copy on write' and 
 return that copy.
 
 But, that doesn't stop you templating it so that it returns the copy as 
 char[] when you pass char[] (which is all I really wanted in the first 
 place) :)
 
 Unfortunately as we cannot overload on return type it would prevent an 
 inplace tolower in the form (given by Kirk):
 
 void tolower(char[])
 
 Instead perhaps we need a naming convention for inplace modifying 
 functions, options:
 
 void <func>Inplace(<args>)
 void <func>IP(<args>)       // "IP" stands for inplace
 void <func>M(<args>)        // "M" stands for mutates
 
 or something like those.
 
 Regan


A lot of functions just to do the string operation efficiently, though, 
isn't it? It's easy to see in cases like this why Walter cites the 
Pareto principle, saying mostly this isn't the bottleneck.

But still, isn't D supposed to give you fast code _easily_ ?

I must say, I *like* the simplicity of overloading with a mutable and a 
readonly version, although we have established that it can certainly 
lead to some confusion. Mind you, D arrays ignore that potential 
confusion (in the .sort and .reverse properties).

I also had some fancy ideas for a CoW wrapper, which looks something like:

struct CoW_Wrapper(T)
{
   const(T) val;
   private bool isMutable;

   void opAssign(T t)
   {
     val = t;
     isMutable = true;
   }

   void opAssign(const(T) t)
   {
     val = t;
     isMutable = false;
   }

   T mutable()
   {
     if (!isMutable)
     {
       val = val.dup;
       isMutable = true;
     }
     return cast(T) val;
   }
}

This would make using CoW quite simple, and would also solve the problem 
of keeping track across function boundaries of whether it's been duped, 
for things like:

    string s = ...;
    string s2 = s.tolower().replace("foo", "bar").entab();

which could potentially involve 3 dups. (I'm aware of the easier 
solution of templating to support char[]->char[] and string->string 
overloads, but let's have some fun going the extra way :-) )

You would write something like tolower as (ignoring unicode stuff):

alias CoW_Wrapper!(char[]) cow_string;

cow_string tolower(cow_string s)
{
   foreach (i; 0..s.val.length)
   {
     if (s.val[i] >= 'A' && s.val[i] <= 'Z')
       s.mutable[i] = s.val[i] + 'a' - 'A';
   }
   return s;
}

The neat feature is that the cow_string returned knows whether it 
isMutable, so you will always have the fewest required dups: 0 or 1.

Unfortunately, it doesn't currently look very nice because of the lack 
of opImplicitCast, which means you'd have to write:

   string s2 = s.tolower.val;

instead of

   string s2 = s.tolower;

(there's also problems with the type of s, but that can be solved with 
some template stuff on the tolower side; those template manipulations 
can also bypass the cow_string struct if the parameter type is char[], 
by defining
    char[] mutable(char[] s) { return s; }
)

   -- Reiner
Aug 02 2007
parent Regan Heath <regan netmail.co.nz> writes:
Reiner Pope wrote:

 I must say, I *like* the simplicity of overloading with a mutable and a 
 readonly version, although we have established that it can certainly 
 lead to some confusion. 


Provided it always performs a .dup when it modifies the input it should 
be fine.  i.e. take the existing tolower in std.string and simply change 
the function signature to:

T tolower(T)(T s)

and make no other changes and your example:

char[] s = "Hello World!".dup;
int a = howManyLettersDiffer(tolower(s), s);
assert (a == 2); // assert failed, a is actually 0

will work as expected.


 Mind you, D arrays ignore that potential
 confusion (in the .sort and .reverse properties).


True.


 I also had some fancy ideas for a CoW wrapper, which looks something like:


<snip>

I wrote something like that once too.

Regan
Aug 02 2007
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Regan Heath wrote:

 Instead perhaps we need a naming convention for inplace modifying
 functions, options:
 
 void <func>Inplace(<args>)
 void <func>IP(<args>)       // "IP" stands for inplace
 void <func>M(<args>)        // "M" stands for mutates
 
 or something like those.
 
 Regan


I actually tried doing this in a math library of mine, but I didn't like
using normal letters; I wanted to use a Unicode character that was easy
to type, showed up in Vim, and would visually distinguish the functions.

Sadly, all I could come up with[1] for "in place" was '¶', and the
compiler didn't like that :(

Sometimes, I wonder if it wouldn't help a lot to be able to define
function overloads based on argument decoration.  So, you could have
something like:

  tolower(str);
  tolower(inplace str);
  tolower(takecopy str);

There are so many times where you have several functions that do the
exact same thing (semantically speaking), but have different
implementations.

Maybe I could fake it with structs...

struct tolower
{
    string opCall(string str);
    void inplace(char[] str);
    char[] takecopy(char[] str);
    char[] takecopy(string str);
}

Something to think about, anyway...

	-- Daniel

[1] That's what you get if you type ^KIP in Vim.  If you type ^Kip, you
get 'ぴ', and ^KiP is 'ピ' :P
Aug 02 2007
parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Daniel Keep wrote:

 struct tolower
 {
     string opCall(string str);
     void inplace(char[] str);
     char[] takecopy(char[] str);
     char[] takecopy(string str);
 }


Those members should, of course, be static.  me.duh();
Aug 02 2007