# a word-wrap problem

## stevan apter — 2003-12-07 14:03:00

    this is a cute little problem (and a nice break from contemplating

    questions about "yahoo group programming languages" and other bizarre

    messages emanating from beyond the orbit of neptune.)

    you have a string containing blanks:

        "this has blanks in it"

    and an integer denoting maximum width

        10

    and you want to cut the string into substrings on the blanks, each of

    max length x:

        ("this has "

         "blanks "

         "in it ")

    there is a lovely little k function for doing this:

      wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}

    here's how it works:

      y:"this has blanks in it"

      x:10

      wrap[x;y]

    ("this has "

     "blanks "

     "in it ")

    / append a blank:

      y,:" "

      y

    "this has blanks in it "

    / indices of positions just following the blanks (pretend y[0] follows a blank):

      b:0,1+&" "=y

      b

    0 5 9 16 19 22

    / add maximum-substring-width:

      x+b

    10 15 19 26 29 32

    / "bucketize" each of those:  e.g. 10 occurs in bucket b[3] (9 < 10 <= 16):

      b _binl x+b

    3 3 4 6 6 6

    / subtract 1:

      -1+b _binl x+b

    2 2 3 5 5 5

    / chase pointers (scan):  0 -> 2, 2 -> 3, 3 -> 5

      (-1+b _binl x+b)\0

    0 2 3 5

    / drop off the last:

      -1_(-1+b _binl x+b)\0

    0 2 3

    / index out the corresponding b-positions (1+where the blanks are in y):

      b -1_(-1+b _binl x+b)\0

    0 9 16

    / cut the string into substrings at those positions:

      (b -1_(-1+b _binl x+b)\0)_ y

    ("this has "

     "blanks "

     "in it ")

    and here is the cK version:

      [[" " , dup] dip swap " " = &: 1 + 0 ,.

       dup [+] dip swap [dup] dip binl

       -1 + 0 swap Converge

       -1 _. @ _.] `wrap def;

      "this has blanks in it" 10 wrap

    ["this has " "blanks " "in it "]

    the k version is a lambda (arguments x and y) and contains an internal

    local variable (b:...) and a reassignment (y,:" ").  the cK version

    contains multiple uses of dup, dip, and swap to similar effect.

    i'm not sure how to write the pure joy version.  iterate over y

    until x, then back up to the last blank, then go forward from

    there ...?  that's how i'd probably write it in a loopy language,

    but is there a better solution in joy?

## Slava Pestov — 2003-12-07 20:33:05

    Where can I find more information about k and cK? How is cK different

    from Joy?

     On Sun, 2003-12-07 at 09:03, stevan apter wrote:

    > this is a cute little problem (and a nice break from contemplating

    > questions about "yahoo group programming languages" and other bizarre

    > messages emanating from beyond the orbit of neptune.)

    >

    > you have a string containing blanks:

    >

    >     "this has blanks in it"

    >

    > and an integer denoting maximum width

    >

    >     10

    >

    > and you want to cut the string into substrings on the blanks, each of

    > max length x:

    >

    >     ("this has "

    >      "blanks "

    >      "in it ")

    >

    > there is a lovely little k function for doing this:

    >

    >   wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}

    >

    > here's how it works:

    >

    >   y:"this has blanks in it"

    >   x:10

    >

    >   wrap[x;y]

    > ("this has "

    >  "blanks "

    >  "in it ")

    >

    > / append a blank:

    >

    >   y,:" "

    >   y

    > "this has blanks in it "

    >

    > / indices of positions just following the blanks (pretend y[0] follows a blank):

    >

    >   b:0,1+&" "=y

    >   b

    > 0 5 9 16 19 22

    >

    > / add maximum-substring-width:

    >

    >   x+b

    > 10 15 19 26 29 32

    >

    > / "bucketize" each of those:  e.g. 10 occurs in bucket b[3] (9 < 10 <= 16):

    >

    >   b _binl x+b

    > 3 3 4 6 6 6

    >

    > / subtract 1:

    >

    >   -1+b _binl x+b

    > 2 2 3 5 5 5

    >

    > / chase pointers (scan):  0 -> 2, 2 -> 3, 3 -> 5

    >

    >   (-1+b _binl x+b)\0

    > 0 2 3 5

    >

    > / drop off the last:

    >

    >   -1_(-1+b _binl x+b)\0

    > 0 2 3

    >

    > / index out the corresponding b-positions (1+where the blanks are in y):

    >

    >   b -1_(-1+b _binl x+b)\0

    > 0 9 16

    >

    > / cut the string into substrings at those positions:

    >

    >   (b -1_(-1+b _binl x+b)\0)_ y

    > ("this has "

    >  "blanks "

    >  "in it ")

    >

    > and here is the cK version:

    >

    >   [[" " , dup] dip swap " " = &: 1 + 0 ,.

    >    dup [+] dip swap [dup] dip binl

    >    -1 + 0 swap Converge

    >    -1 _. @ _.] `wrap def;

    >

    >   "this has blanks in it" 10 wrap

    > ["this has " "blanks " "in it "]

    >

    > the k version is a lambda (arguments x and y) and contains an internal

    > local variable (b:...) and a reassignment (y,:" ").  the cK version

    > contains multiple uses of dup, dip, and swap to similar effect.

    >

    > i'm not sure how to write the pure joy version.  iterate over y

    > until x, then back up to the last blank, then go forward from

    > there ...?  that's how i'd probably write it in a loopy language,

    > but is there a better solution in joy?

    >

    >

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    --

    Slava Pestov

## stevan apter — 2003-12-07 20:55:36

    like joy, k is a "real" language:

    http://www.kx.com/download.htm

    you can download a free copy, which is size- and message-

    limited.  (i recommend using version 3.1t)

    cK is an interpreter written in k.  i wanted to explore

    the effect of adding k's array primitives to joy.  once

    you have k, you can download the cK script from nsl.com.

    two papers you might want to read are:

    http://www.nsl.com/papers/ck.htm

    http://www.nsl.com/papers/k.htm

    have fun!

     ----- Original Message -----

    From: "Slava Pestov" <slava@...>

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, December 07, 2003 3:33 PM

    Subject: Re: [stack] a word-wrap problem

    > Where can I find more information about k and cK? How is cK different

    > from Joy?

    >

    > On Sun, 2003-12-07 at 09:03, stevan apter wrote:

    > > this is a cute little problem (and a nice break from contemplating

    > > questions about "yahoo group programming languages" and other bizarre

    > > messages emanating from beyond the orbit of neptune.)

    > >

    > > you have a string containing blanks:

    > >

    > >     "this has blanks in it"

    > >

    > > and an integer denoting maximum width

    > >

    > >     10

    > >

    > > and you want to cut the string into substrings on the blanks, each of

    > > max length x:

    > >

    > >     ("this has "

    > >      "blanks "

    > >      "in it ")

    > >

    > > there is a lovely little k function for doing this:

    > >

    > >   wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}

    > >

    > > here's how it works:

    > >

    > >   y:"this has blanks in it"

    > >   x:10

    > >

    > >   wrap[x;y]

    > > ("this has "

    > >  "blanks "

    > >  "in it ")

    > >

    > > / append a blank:

    > >

    > >   y,:" "

    > >   y

    > > "this has blanks in it "

    > >

    > > / indices of positions just following the blanks (pretend y[0] follows a blank):

    > >

    > >   b:0,1+&" "=y

    > >   b

    > > 0 5 9 16 19 22

    > >

    > > / add maximum-substring-width:

    > >

    > >   x+b

    > > 10 15 19 26 29 32

    > >

    > > / "bucketize" each of those:  e.g. 10 occurs in bucket b[3] (9 < 10 <= 16):

    > >

    > >   b _binl x+b

    > > 3 3 4 6 6 6

    > >

    > > / subtract 1:

    > >

    > >   -1+b _binl x+b

    > > 2 2 3 5 5 5

    > >

    > > / chase pointers (scan):  0 -> 2, 2 -> 3, 3 -> 5

    > >

    > >   (-1+b _binl x+b)\0

    > > 0 2 3 5

    > >

    > > / drop off the last:

    > >

    > >   -1_(-1+b _binl x+b)\0

    > > 0 2 3

    > >

    > > / index out the corresponding b-positions (1+where the blanks are in y):

    > >

    > >   b -1_(-1+b _binl x+b)\0

    > > 0 9 16

    > >

    > > / cut the string into substrings at those positions:

    > >

    > >   (b -1_(-1+b _binl x+b)\0)_ y

    > > ("this has "

    > >  "blanks "

    > >  "in it ")

    > >

    > > and here is the cK version:

    > >

    > >   [[" " , dup] dip swap " " = &: 1 + 0 ,.

    > >    dup [+] dip swap [dup] dip binl

    > >    -1 + 0 swap Converge

    > >    -1 _. @ _.] `wrap def;

    > >

    > >   "this has blanks in it" 10 wrap

    > > ["this has " "blanks " "in it "]

    > >

    > > the k version is a lambda (arguments x and y) and contains an internal

    > > local variable (b:...) and a reassignment (y,:" ").  the cK version

    > > contains multiple uses of dup, dip, and swap to similar effect.

    > >

    > > i'm not sure how to write the pure joy version.  iterate over y

    > > until x, then back up to the last blank, then go forward from

    > > there ...?  that's how i'd probably write it in a loopy language,

    > > but is there a better solution in joy?

    > >

    > >

    > >

    > >

    > >

    > > To unsubscribe from this group, send an email to:

    > > concatenative-unsubscribe@egroups.com

    > >

    > >

    > >

    > > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    > --

    > Slava Pestov

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## stevan apter — 2003-12-09 00:56:00

    > wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}

     :

     > and here is the cK version:

    >

    >   [[" " , dup] dip swap " " = &: 1 + 0 ,.

    >    dup [+] dip swap [dup] dip binl

    >    -1 + 0 swap Converge

    >    -1 _. @ _.] `wrap def;

    >

    >   "this has blanks in it" 10 wrap

    > ["this has " "blanks " "in it "]

    >

    > the k version is a lambda (arguments x and y) and contains an internal

    > local variable (b:...) and a reassignment (y,:" ").  the cK version

    > contains multiple uses of dup, dip, and swap to similar effect.

     and here is the "shuffle notation" version:

    [ "yx--yxy"   shuffle     " " , " " = &: 1 + 0 ,.

     "yxb--ybbxb" shuffle     + binl -1 + 0

     "ybz--yzb"   shuffle     Converge -1 _. @ _.     ] `wrap def;

    (thanks billy)

## Slava Pestov — 2003-12-09 06:00:59

    On Mon, 2003-12-08 at 19:56, stevan apter wrote:

     > and here is the "shuffle notation" version:

    >

    > [ "yx--yxy"   shuffle     " " , " " = &: 1 + 0 ,.

    >  "yxb--ybbxb" shuffle     + binl -1 + 0

    >  "ybz--yzb"   shuffle     Converge -1 _. @ _.     ] `wrap def;

    >

    > (thanks billy)

     Can you explain exactly what this "shuffle notation" is? It looks

    interesting.

    --

    Slava Pestov

## Nick Forde — 2003-12-09 10:36:28

    Hi Stevan,

    stevan apter writes:

      > this is a cute little problem (and a nice break from contemplating

     > questions about "yahoo group programming languages" and other bizarre

     > messages emanating from beyond the orbit of neptune.)

     >

     > you have a string containing blanks:

     >

     >     "this has blanks in it"

     >

     > and an integer denoting maximum width

     >

     >     10

     >

     > and you want to cut the string into substrings on the blanks, each of

     > max length x:

     >

     >     ("this has "

     >      "blanks "

     >      "in it ")

     >

     > [...]

     >

     > i'm not sure how to write the pure joy version.  iterate over y

     > until x, then back up to the last blank, then go forward from

     > there ...?  that's how i'd probably write it in a loopy language,

     > but is there a better solution in joy?

     Some time ago I wrote some string manipulation functions in Joy. One

    of these was spliti below:

    DEFINE str-spliti == (* Si Cb -> Ao : Inclusive split. *)

      [] rolldown ""

      [ [rolldownd =]

        [swonsd "" cons swons ""]

        ["" cons concat] ifte

      ] fold swons reverse popd.

    This takes an input string and breaks it into substrings using a

    specified character divider. This implementation differs from the

    associated str-split in that it includes the dividers as discrete

    strings in the result. e.g.

      "this has blanks in it" 's str-spliti.

    ["thi" "s" " ha" "s" " blank" "s" " in it"]

    or if we use space as a delimeter:

      "this has blanks in it" '  str-spliti.

    ["this" " " "has" " " "blanks" " " "in" " " "it"]

    One alternative solution to your wrap problem is to use the above and

    then concatenate strings together up to the maximum size. e.g.

    DEFINE wrap == (* Si Ix -> Ao : *)

      swap '  str-spliti [] swap ""

      [ dup2 size swap size +

        [swap rolldown [swap pop >=] dip2 rolldown]

        [pop concat]

        [pop swonsd] ifte

      ] fold swons popd reverse.

      "this has blanks in it" 10 wrap.

    ["this has " "blanks in " "it"]

    OK, so this isn't particlarly efficient, and the implementation above

    needs to be made more robust and could probably be improved. But why

    does the K version not split the example text as above? Am I missing

    something?

    Regards,

    Nick.

    P.S. Thanks for your recent problem postings. I've enjoyed thinking

         about them, even if I haven't had enough free time to actually

         implement any solutions.

## stevan apter — 2003-12-09 12:31:08

    >   "this has blanks in it" 10 wrap.

    > ["this has " "blanks in " "it"]

    >

    > OK, so this isn't particlarly efficient, and the implementation above

    > needs to be made more robust and could probably be improved. But why

    > does the K version not split the example text as above? Am I missing

    > something?

     hi nick

    for a minute i thought there was a bug in 'wrap', but no - the

    bug was in my description:  "blank in " contains 10 characters,

    and the substring-lengths produced by wrap[10] must be strictly less

    than 10.  to get the result you (and i!) expected, use 11.

    best

    sa

     >

    > Regards,

    >

    > Nick.

    >

    > P.S. Thanks for your recent problem postings. I've enjoyed thinking

    >      about them, even if I haven't had enough free time to actually

    >      implement any solutions.

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## sa@dfa.com — 2003-12-09 13:27:06

    shuffle takes a string of the form "X--Y" where X is a diagram of the

    top of the stack as it is, and Y is a diagram of the stack as you want

    it to be.  The result of shuffle is a stack which conforms to Y.

    so e.g.

          "a--aa" shuffle

    is dup,

          "ab--ba" shuffle

    is swap, &c.

    in extended shuffle notation, the diagram can express list structure:

          10 20 30 "abc--[ab][cba]" shuffle

        [10 20][30 20 10]

    billy tanksley first suggested shuffle notation, and i've implemented the

    extended version in cK.

    -------

     On Mon, 2003-12-08 at 19:56, stevan apter wrote:

    > and here is the "shuffle notation" version:

    >

    > [ "yx--yxy"   shuffle     " " , " " = &: 1 + 0 ,.

    >  "yxb--ybbxb" shuffle     + binl -1 + 0

    >  "ybz--yzb"   shuffle     Converge -1 _. @ _.     ] `wrap def;

    >

    > (thanks billy)

    Can you explain exactly what this "shuffle notation" is? It looks

    interesting.

    --

    Slava Pestov

    To unsubscribe from this group, send an email to:

    concatenative-unsubscribe@egroups.com

    Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

## sa@dfa.com — 2003-12-09 13:29:16

    > "blank in " contains 10 characters,

     that is, "blanks in " contains 10 characters.

## stevan apter — 2003-12-11 12:05:34

    it's worth pointing out that there's a denser form of stack

    diagram, namely an (arbitrarily nested) list of integers:

        [0 0] shuffle

    is dup

        [0 1] shuffle

    is swap

    &c.  0 denotes the top of the stack, 1 the item just below

    that, &c.

    the advantage over the string representation is that integer

    lists are easier to manipulate, the disadvantage is that

    they are less useful in conveying information about the

    program's behavior to the programmer.

     ----- Original Message -----

    From: <sa@...>

    To: <concatenative@yahoogroups.com>

    Sent: Tuesday, December 09, 2003 8:27 AM

    Subject: Re: [stack] a word-wrap problem

    >

    > shuffle takes a string of the form "X--Y" where X is a diagram of the

    > top of the stack as it is, and Y is a diagram of the stack as you want

    > it to be.  The result of shuffle is a stack which conforms to Y.

    >

    > so e.g.

    >

    >       "a--aa" shuffle

    >

    > is dup,

    >

    >       "ab--ba" shuffle

    >

    > is swap, &c.

    >

    > in extended shuffle notation, the diagram can express list structure:

    >

    >       10 20 30 "abc--[ab][cba]" shuffle

    >     [10 20][30 20 10]

    >

    > billy tanksley first suggested shuffle notation, and i've implemented the

    > extended version in cK.

    >

    >

    > -------

    >

    >

    >

    >

    > On Mon, 2003-12-08 at 19:56, stevan apter wrote:

    > > and here is the "shuffle notation" version:

    > >

    > > [ "yx--yxy"   shuffle     " " , " " = &: 1 + 0 ,.

    > >  "yxb--ybbxb" shuffle     + binl -1 + 0

    > >  "ybz--yzb"   shuffle     Converge -1 _. @ _.     ] `wrap def;

    > >

    > > (thanks billy)

    >

    > Can you explain exactly what this "shuffle notation" is? It looks

    > interesting.

    > --

    > Slava Pestov

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

    >

    >

    >

    >

    >

    >

    >

    > To unsubscribe from this group, send an email to:

    > concatenative-unsubscribe@egroups.com

    >

    >

    >

    > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

    >

    >

## Heiko.Kuhrt@t-online.de — 2003-12-11 14:00:09

    On Thursday December 11 2003 13:05, stevan apter wrote:

     > it's worth pointing out that there's a denser form of stack

    > diagram, namely an (arbitrarily nested) list of integers:

    >

    >     [0 0] shuffle

    >

    > is dup

    >

    >     [0 1] shuffle

    >

    > is swap

    >

    > &c.  0 denotes the top of the stack, 1 the item just below

    > that, &c.

    >

    > the advantage over the string representation is that integer

    > lists are easier to manipulate, the disadvantage is that

    > they are less useful in conveying information about the

    > program's behavior to the programmer.

    >

     Once I invented functions like

    ABCDE = id;

    BACDE = swap;

    BBCDE = dup;

    ABBCD = dupd;

    or

    EDCBA == id;

    EDCAB == swap;

    DCBAA == dup;

    ...

    BCDAA == rotated dup;

    ...

    This is of course limited to the few tops of stack. I don't see a way to

    extent it to usage on aggregates.

    But it's fast and simple.

## Tanksley, William D. Jr. — 2003-12-11 17:34:55

    From: Heiko.Kuhrt@... [mailto:Heiko.Kuhrt@...]

     >Once I invented functions like

    >ABCDE = id;

    >BACDE = swap;

    >BBCDE = dup;

    >ABBCD = dupd;

     ...

    Got you beat. I wrote and used a defining word for Pygmy Forth (DOS-x86)

    which compiled my shuffle notation to assembly language. I even tried (and

    failed) to build an inline version of the same thing (so I didn't have to

    define words to do the shuffling, I could just use them).

    -Billy