Can anyone write this recursion for simple regexp more beautifullyand clearly than the braggarts

Discussion in 'C Programming' started by bolega, Aug 29, 2009.

  1. bolega

    bolega Guest

    This braggart admits that he had to put this code in TWO books and
    visit it twice to be explained. I am puting the excerpt from pp2-4 of
    this book and the C code. The C code will become indented and syntax
    highlighted once you paste in emacs etc. It is my belief and
    observation on a lot of problems by these so called "demi gods" that
    they are actually all average and no more intelligent. Its all that
    they got some opportunities to study some things at opportune time and
    facilities and also spent a lot of time in a productive environment
    and team.

    I know that lisp eval is written more clear than this recursion below
    because I am able to read it easily. and that code is almost self
    explanatory. C is more quirky. When you really mean recursively call
    another function, you are using return so you can have tail
    recursion ???? .

    Anyway, its your chance to show how clear C/C++/lisp/Scheme code you
    can write that is clearer. Also, i dont exclude pseudocode but it
    should be clear enough to be instantly translatable to a programming
    language. The real goal is to learn how to write or DERIVE recursion,
    how to enumerate cases, order them, and build recursion. You may even
    put some introductory tuturial and dont have to reply here in ascii
    but can upload a pdf at some link in rapidshare etc. Look how he put
    the code after problem statement and then has the need to explain it.
    Ideally, the discussion should be such that the student or reader
    himself jumps to the solution. That is why I give these unix school of
    pike/thomson/kernighan low grade in almost all their expositions
    except that they wrote earliest books to make millions of dollars in
    royalties and since now they are nobody due to linux, they are poorly
    regurgitating old material.

    Enjoy .............

    ============================

    The Practice of Programming

    In 1998, Rob Pike and I were writing The Practice of Programming
    (Addison-Wesley). The
    last chapter of the book, “Notation,” collected a number of examples
    where good notation
    led to better programs and better programming. This included the use
    of simple data specifications
    (printf, for instance), and the generation of code from tables.
    Because of our Unix backgrounds and nearly 30 years of experience with
    tools based on
    regular expression notation, we naturally wanted to include a
    discussion of regular
    expressions, and it seemed mandatory to include an implementation as
    well. Given our
    emphasis on tools, it also seemed best to focus on the class of
    regular expressions found in
    grep—rather than, say, those from shell wildcards—since we could also
    then talk about the
    design of grep itself.
    The problem was that any existing regular expression package was far
    too big. The local
    grep was over 500 lines long (about 10 book pages) and encrusted with
    barnacles. Open
    source regular expression packages tended to be huge—roughly the size
    of the entire
    book—because they were engineered for generality, flexibility, and
    speed; none were
    remotely suitable for pedagogy.
    I suggested to Rob that we find the smallest regular expression
    package that would illustrate
    the basic ideas while still recognizing a useful and nontrivial class
    of patterns. Ideally,
    the code would fit on a single page.
    Rob disappeared into his office. As I remember it now, he emerged in
    no more than an
    hour or two with the 30 lines of C code that subsequently appeared in
    Chapter 9 of The
    Practice of Programming. That code implements a regular expression
    matcher that handles
    the following constructs.

    Character Meaning
    c Matches any literal character c.
    .. (period) Matches any single character.
    ^ Matches the beginning of the input string.
    $ Matches the end of the input string.
    * Matches zero or more occurrences of the previous character.

    This is quite a useful class; in my own experience of using regular
    expressions on a day-today
    basis, it easily accounts for 95 percent of all instances. In many
    situations, solving the
    right problem is a big step toward creating a beautiful program. Rob
    deserves great credit
    for choosing a very small yet important, well-defined, and extensible
    set of features from
    among a wide set of options.
    Rob’s implementation itself is a superb example of beautiful code:
    compact, elegant,
    efficient, and useful. It’s one of the best examples of recursion that
    I have ever seen, and it
    shows the power of C pointers. Although at the time we were most
    interested in conveying
    the important role of good notation in making a program easier to use
    (and perhaps
    easier to write as well), the regular expression code has also been an
    excellent way to
    illustrate algorithms, data structures, testing, performance
    enhancement, and other
    important topics.

    Implementation
    In The Practice of Programming, the regular expression matcher is part
    of a standalone program
    that mimics grep, but the regular expression code is completely
    separable from its
    surroundings. The main program is not interesting here; like many Unix
    tools, it reads
    either its standard input or a sequence of files, and prints those
    lines that contain a match
    of the regular expression.
    This is the matching code:
    /* match: search for regexp anywhere in text */
    int match(char *regexp, char *text)
    {
    if (regexp[0] == '^')
    return matchhere(regexp+1, text);
    do { /* must look even if string is empty */
    if (matchhere(regexp, text))
    return 1;
    } while (*text++ != '\0');
    return 0;
    }
    /* matchhere: search for regexp at beginning of text */
    int matchhere(char *regexp, char *text)
    {
    if (regexp[0] == '\0')
    return 1;
    if (regexp[1] == '*')
    return matchstar(regexp[0], regexp+2, text);
    Character Meaning
    c Matches any literal character c.
    .. (period) Matches any single character.
    ^ Matches the beginning of the input string.
    $ Matches the end of the input string.
    * Matches zero or more occurrences of the previous character.
    4 C H A P T E R O N E
    if (regexp[0] == '$' && regexp[1] == '\0')
    return *text == '\0';
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
    return matchhere(regexp+1, text+1);
    return 0;
    }
    /* matchstar: search for c*regexp at beginning of text */
    int matchstar(int c, char *regexp, char *text)
    {
    do { /* a * matches zero or more instances */
    if (matchhere(regexp, text))
    return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
    }
     
    bolega, Aug 29, 2009
    #1
    1. Advertising

  2. bolega

    bolega Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    let me paste the code separately since it has some garbage that
    inserted in the middle although it was just one block of text.

    This is the matching code:
    /* match: search for regexp anywhere in text */
    int match(char *regexp, char *text)
    {
    if (regexp[0] == '^')
    return matchhere(regexp+1, text);
    do { /* must look even if string is empty */
    if (matchhere(regexp, text))
    return 1;
    } while (*text++ != '\0');
    return 0;
    }
    /* matchhere: search for regexp at beginning of text */
    int matchhere(char *regexp, char *text)
    {
    if (regexp[0] == '\0')
    return 1;
    if (regexp[1] == '*')
    return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
    return *text == '\0';
    if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
    return matchhere(regexp+1, text+1);
    return 0;
    }
    /* matchstar: search for c*regexp at beginning of text */
    int matchstar(int c, char *regexp, char *text)
    {
    do { /* a * matches zero or more instances */
    if (matchhere(regexp, text))
    return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
    }


    By the way did you note the spicy style of narration by which they
    promote each other ? and can you abstract the technique of narration
    for image building ? Another scum in electronic, Bob Pease of national
    semiconductor writes in the same style. I know all their basic ideas
    in that field, which are trivial. The only art is the art of writing
    and propaganda.

    The one man I have real respect for and is humble is McCarthy. He
    really put some original ideas together but still did not give any
    clue how he constructed them. However, in lisp recursion is lucidly
    clear. You test if a thing is nil. Else you check if it is an atom and
    act appropriately to call a handler and otherwise recursion.
     
    bolega, Aug 29, 2009
    #2
    1. Advertising

  3. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 29, 12:35 pm, bolega <> wrote:
    > This braggart admits that he had to put this code in TWO books and
    > visit it twice to be explained. I am puting the excerpt from pp2-4 of
    > this book and the C code. The C code will become indented and syntax
    > highlighted once you paste in emacs etc. It is my belief and
    > observation on a lot of problems by these so called "demi gods" that
    > they are actually all average and no more intelligent. Its all that
    > they got some opportunities to study some things at opportune time and
    > facilities and also spent a lot of time in a productive environment
    > and team.
    >
    > I know that lisp eval is written more clear than this recursion below
    > because I am able to read it easily. and that code is almost self
    > explanatory. C is more quirky. When you really mean recursively call
    > another function, you are using return so you can have tail
    > recursion ???? .
    >
    > Anyway, its your chance to show how clear C/C++/lisp/Scheme code you
    > can write that is clearer. Also, i dont exclude pseudocode but it
    > should be clear enough to be instantly translatable to a programming
    > language. The real goal is to learn how to write or DERIVE recursion,
    > how to enumerate cases, order them, and build recursion. You may even
    > put some introductory tuturial and dont have to reply here in ascii
    > but can upload a pdf at some link in rapidshare etc. Look how he put
    > the code after problem statement and then has the need to explain it.
    > Ideally, the discussion should be such that the student or reader
    > himself jumps to the solution. That is why I give these unix school of
    > pike/thomson/kernighan low grade in almost all their expositions
    > except that they wrote earliest books to make millions of dollars in
    > royalties and since now they are nobody due to linux, they are poorly
    > regurgitating old material.
    >
    > Enjoy .............
    >
    > ============================
    >
    > The Practice of Programming
    >
    > In 1998, Rob Pike and I were writing The Practice of Programming
    > (Addison-Wesley). The
    > last chapter of the book, “Notation,” collected a number of examples
    > where good notation
    > led to better programs and better programming. This included the use
    > of simple data specifications
    > (printf, for instance), and the generation of code from tables.
    > Because of our Unix backgrounds and nearly 30 years of experience with
    > tools based on
    > regular expression notation, we naturally wanted to include a
    > discussion of regular
    > expressions, and it seemed mandatory to include an implementation as
    > well. Given our
    > emphasis on tools, it also seemed best to focus on the class of
    > regular expressions found in
    > grep—rather than, say, those from shell wildcards—since we could also
    > then talk about the
    > design of grep itself.
    > The problem was that any existing regular expression package was far
    > too big. The local
    > grep was over 500 lines long (about 10 book pages) and encrusted with
    > barnacles. Open
    > source regular expression packages tended to be huge—roughly the size
    > of the entire
    > book—because they were engineered for generality, flexibility, and
    > speed; none were
    > remotely suitable for pedagogy.
    > I suggested to Rob that we find the smallest regular expression
    > package that would illustrate
    > the basic ideas while still recognizing a useful and nontrivial class
    > of patterns. Ideally,
    > the code would fit on a single page.
    > Rob disappeared into his office. As I remember it now, he emerged in
    > no more than an
    > hour or two with the 30 lines of C code that subsequently appeared in
    > Chapter 9 of The
    > Practice of Programming. That code implements a regular expression
    > matcher that handles
    > the following constructs.
    >
    > Character Meaning
    > c Matches any literal character c.
    > . (period) Matches any single character.
    > ^ Matches the beginning of the input string.
    > $ Matches the end of the input string.
    > * Matches zero or more occurrences of the previous character.
    >
    > This is quite a useful class; in my own experience of using regular
    > expressions on a day-today
    > basis, it easily accounts for 95 percent of all instances. In many
    > situations, solving the
    > right problem is a big step toward creating a beautiful program. Rob
    > deserves great credit
    > for choosing a very small yet important, well-defined, and extensible
    > set of features from
    > among a wide set of options.
    > Rob’s implementation itself is a superb example of beautiful code:
    > compact, elegant,
    > efficient, and useful. It’s one of the best examples of recursion that
    > I have ever seen, and it
    > shows the power of C pointers. Although at the time we were most
    > interested in conveying
    > the important role of good notation in making a program easier to use
    > (and perhaps
    > easier to write as well), the regular expression code has also been an
    > excellent way to
    > illustrate algorithms, data structures, testing, performance
    > enhancement, and other
    > important topics.
    >
    > Implementation
    > In The Practice of Programming, the regular expression matcher is part
    > of a standalone program
    > that mimics grep, but the regular expression code is completely
    > separable from its
    > surroundings. The main program is not interesting here; like many Unix
    > tools, it reads
    > either its standard input or a sequence of files, and prints those
    > lines that contain a match
    > of the regular expression.
    > This is the matching code:
    > /* match: search for regexp anywhere in text */
    > int match(char *regexp, char *text)
    > {
    > if (regexp[0] == '^')
    > return matchhere(regexp+1, text);
    > do { /* must look even if string is empty */
    > if (matchhere(regexp, text))
    > return 1;} while (*text++ != '\0');
    > return 0;
    > }
    >
    > /* matchhere: search for regexp at beginning of text */
    > int matchhere(char *regexp, char *text)
    > {
    > if (regexp[0] == '\0')
    > return 1;
    > if (regexp[1] == '*')
    > return matchstar(regexp[0], regexp+2, text);
    > Character Meaning
    > c Matches any literal character c.
    > . (period) Matches any single character.
    > ^ Matches the beginning of the input string.
    > $ Matches the end of the input string.
    > * Matches zero or more occurrences of the previous character.
    > 4 C H A P T E R O N E
    > if (regexp[0] == '$' && regexp[1] == '\0')
    > return *text == '\0';
    > if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
    > return matchhere(regexp+1, text+1);
    > return 0;}
    >
    > /* matchstar: search for c*regexp at beginning of text */
    > int matchstar(int c, char *regexp, char *text)
    > {
    > do { /* a * matches zero or more instances */
    > if (matchhere(regexp, text))
    > return 1;
    >
    >
    >
    > } while (*text != '\0' && (*text++ == c || c == '.'));
    > return 0;
    > }- Hide quoted text -
    >
    > - Show quoted text -


    Many people seem to have been upset with this article in Beautiful
    Code. I emailed Kernighan about it and received a reply (I'd met the
    guy), but no real answer to the basic problem, which is that C cannot
    express programming ideas clearly.

    The first problem is that by being so "simple" it fails to implement a
    recognizable "regular expression" processor.

    I thought a second problem was that it used a value parameter as a
    work area, which isn't something I would do in my languages of choice
    (C Sharp and VB in recent years), but I found myself doing this in C
    when I returned to the language mostly to kick the shit out it.

    A third problem is praising a programmer for fast work. There's enough
    slipshod work in our industry, and enough programmer overwork as it
    is.

    I think Brian Kernighan would be the first to admit that Lisp as
    opposed to C made a more far-reaching contribution to computer science.
     
    spinoza1111, Aug 29, 2009
    #3
  4. bolega

    JustBoo Guest

    bolega wrote:
    > This braggart admits that he had to put this code in TWO books and
    > visit it twice to be explained. I am puting the excerpt from pp2-4
    > of this book and the C code.

    [...]

    Well, witness yet another way, boy and girls, to market a book. We'll
    be seeing a lot of it from now on I'm sure. Meh. Enjoy.
     
    JustBoo, Aug 29, 2009
    #4
  5. bolega

    bolega Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 29, 2:51 am, spinoza1111 <> wrote:

    > Many people seem to have been upset with this article in Beautiful
    > Code. I emailed Kernighan about it and received a reply (I'd met the
    > guy), but no real answer to the basic problem, which is that C cannot
    > express programming ideas clearly.


    I admire the fact that someone brought all this in the public
    discussion because a lot of sleazy people (not referring in particular
    to this troika) have been able to propagate crap and kept it immune to
    academic critique just due to people afraid of criticizing it which
    leads to a lot of newbie sheeple.

    Do you think C syntax is brain damaged ? Can you explain your second
    point in more detail and clearly as I could not understand any of it.

    > The first problem is that by being so "simple" it fails to implement a
    > recognizable "regular expression" processor.
    >
    > I thought a second problem was that it used a value parameter as a
    > work area, which isn't something I would do in my languages of choice
    > (C Sharp and VB in recent years), but I found myself doing this in C
    > when I returned to the language mostly to kick the shit out it.
    >
    > A third problem is praising a programmer for fast work. There's enough
    > slipshod work in our industry, and enough programmer overwork as it
    > is.
    >
    > I think Brian Kernighan would be the first to admit that Lisp as
    > opposed to C made a more far-reaching contribution to computer science.- Hide quoted text -


    Actually, in C all they did was to borrow parens and braces from math
    to delimit blocks - BUT lisp already had the idea in the prefix
    notation. The other contribution is the for loop with all the loop
    elements at the top in the interface. The declaration syntax of
    pointers is poor and ugly. switch-case has fall thru. break and
    continue is new unless PL1 or BCPL had it.

    BUT YOU HAVE NOT SHOWN how to structure the recursion. Does it need
    NFA ? I need a tutorial because C is to stay and I can avoid some of
    its ugliness by using C++ as pretty C.

    > - Show quoted text -


    I admire the fact that you
     
    bolega, Aug 29, 2009
    #5
  6. bolega

    Ed Morton Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 28, 11:35 pm, bolega <> wrote:
    > This braggart admits that he had to put this code in TWO books and
    > visit it twice to be explained. I am puting the excerpt from pp2-4 of
    > this book and the C code.


    You should post this to comp.lang.c.

    Ed.
     
    Ed Morton, Aug 29, 2009
    #6
  7. bolega

    bolega Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 29, 8:53 am, A.L. <> wrote:
    > On Sat, 29 Aug 2009 07:10:59 -0700, JustBoo <> wrote:
    > >bolega wrote:
    > >> This braggart admits that he had to put this code in TWO books and
    > >> visit it twice to be explained. I am puting the excerpt from pp2-4
    > >> of this book and the C code.

    > >[...]

    >
    > >Well, witness yet another way, boy and girls, to market a book. We'll
    > >be seeing a lot of it from now on I'm sure. Meh. Enjoy.

    >
    > Very good way to market a book. Something criticized on c.l.l. must be
    > really good.
    >
    > Ordered from Amazon 5 minutes ago.
    >
    > A.L.


    please dont derail my thread, BUT, you ordered the wrong book. The one
    you SHOULD have ordered is this one:

    Book Review
    ---------------------------------------------------------------------------­-----
    Advanced C Struct Programming by John W.L. Ogilvie
    Highly Recommended
    ISBN: 0-471-51943-X Publisher: Wiley Pages: 405pp
    Price: £22.95

    Categories: advanced c data structures
    Reviewed by Francis Glassborow in C Vu 3-2 (Jan 1991)


    This is the kind of book that I might easily miss on a casual visit
    to
    my local bookshop. In all honesty my first impression when I opened
    it
    was not that good. It is aimed at people who wish to take programming
    seriously yet it first seemed more like the kind of text that I am
    used to finding on the hobbyists shelves. It is much better than
    that.
    When you have mastered the foothills of programming in C, have a good
    runtime library reference on your shelf and, perhaps, have invested
    in
    a book on data structures and another on programming algorithms or
    techniques what do you get to help you develop good medium size
    programs (all right large ones if you must)?


    If you had asked my advice a month ago, I would have hummed and hawed
    and come up with a couple of titles and then suggested that what you
    really wanted was a book on program/data design rather than one on C.


    Advanced C Struct Programming tackles this need. The author's
    declared
    intent is to present a practical method for designing and
    implementing
    complex (complicated) data structures in C. In doing so he leads you
    through experience (sometimes of false trails) in tackling a number
    of
    different programming problems.


    The book does not include complete applications or libraries of
    source
    code. It is a book to be worked through. By the time you have
    finished
    it you should be a much better programmer. Let me warn you that it is
    not a book to dip into in that odd spare moment. If that is all you
    have time for then go and do something else.


    On the other hand it is not like some of the books above that will
    take you years to fully grasp (if ever). Buy this book, set aside a
    regular time to work at it, stick to your routine and find yourself
    becoming far more professional in your programming.


    Yes, I like it and it is not machine dependant. For once I am glad
    that the supporting discs are relatively expensive ($39.95 in IBM and
    Apple Mac formats) as I think that you will only get the full benefit
    by grafting at the keyboard yourself.


    ---------------------------------------------------------------------------­-----
    Last Update - 13 May 2001.


    To link to this review, please use the URL:
    http://www.accu.org/bookreviews/public/reviews/a/a000142.htm


    Copyright © The Association of C & C++ Users 1998-2000. All rights
    reserved.
    Mirrored from http://www.accu.org/
     
    bolega, Aug 29, 2009
    #7
  8. Re: Can anyone write this recursion for simple regexp more beautifully and clearly than the braggarts

    Ed Morton <> writes:

    >On Aug 28, 11:35=A0pm, bolega <> wrote:
    >> This braggart admits that he had to put this code in TWO books and
    >> visit it twice to be explained. I am puting the excerpt from pp2-4 of
    >> this book and the C code.


    >You should post this to comp.lang.c.


    > Ed.


    He did, and I smelt a Bilges sock puppet.

    --
    Chris.
     
    Chris McDonald, Aug 30, 2009
    #8
  9. bolega

    w_a_x_man Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 28, 11:35 pm, bolega <> wrote:
    > Look how he put
    > the code after problem statement and then has the need to explain it.
    > Ideally, the discussion should be such that the student or reader
    > himself jumps to the solution. That is why I give these unix school of
    > pike/thomson/kernighan low grade in almost all their expositions
    > except that they wrote earliest books to make millions of dollars in
    > royalties and since now they are nobody due to linux, they are poorly
    > regurgitating old material.


    Kernighan fails to correct the bugs in his programs.

    Download his awk here:
    http://cm.bell-labs.com/cm/cs/who/bwk/awk95.exe

    Test it with this program:

    BEGIN {
    # Specify the field-separator.
    FS = "!"
    text = "foo!bar"
    $0 = text
    # Should print "foo".
    print $1
    printf "Press <ENTER>: "
    getline junk
    $0 = text
    print $1
    }
     
    w_a_x_man, Aug 30, 2009
    #9
  10. bolega

    pk Guest

    Re: Can anyone write this recursion for simple regexp more beautifully and clearly than the braggarts

    w_a_x_man wrote:

    > On Aug 28, 11:35 pm, bolega <> wrote:
    >> Look how he put
    >> the code after problem statement and then has the need to explain it..
    >> Ideally, the discussion should be such that the student or reader
    >> himself jumps to the solution. That is why I give these unix school of
    >> pike/thomson/kernighan low grade in almost all their expositions
    >> except that they wrote earliest books to make millions of dollars in
    >> royalties and since now they are nobody due to linux, they are poorly
    >> regurgitating old material.

    >
    > Kernighan fails to correct the bugs in his programs.
    >
    > Download his awk here:
    > http://cm.bell-labs.com/cm/cs/who/bwk/awk95.exe
    >
    > Test it with this program:
    >
    > BEGIN {
    > # Specify the field-separator.
    > FS = "!"
    > text = "foo!bar"
    > $0 = text
    > # Should print "foo".
    > print $1
    > printf "Press <ENTER>: "
    > getline junk
    > $0 = text
    > print $1
    > }


    That program triggers several undefined behaviors, so I'd not say bwk's awk
    is buggy based only on the outcomes of that code.
     
    pk, Aug 30, 2009
    #10
  11. Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    w_a_x_man <> wrote:
    >Kernighan fails to correct the bugs in his programs.


    Somewhat contrary to this, Kernighan's awk source comes with a 1000-line
    file describing 20 years-worth of awk bugfixes. (I don't doubt there
    are still bugs in awk, however.)

    -Beej
     
    Beej Jorgensen, Aug 30, 2009
    #11
  12. bolega

    mjc Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 30, 1:29 pm, Beej Jorgensen <> wrote:
    > w_a_x_man  <> wrote:
    > >Kernighan fails to correct the bugs in his programs.

    >
    > Somewhat contrary to this, Kernighan's awk source comes with a 1000-line
    > file describing 20 years-worth of awk bugfixes.  (I don't doubt there
    > are still bugs in awk, however.)
    >
    > -Beej


    Works fine with gawk, which is what most of us use anyway.
     
    mjc, Aug 30, 2009
    #12
  13. bolega

    Chris Dollin Guest

    Re: Can anyone write this recursion for simple regexp more beautifully and clearly than the braggarts

    spinoza1111 wrote:

    (re: the Beautiful Code RE matcher)

    > The first problem is that by being so "simple" it fails to implement a
    > recognizable "regular expression" processor.


    False. It implements a /useful subset/ of REs and provides a framework
    for adding more features -- it's an educational tool, not a library
    component.

    --
    "I have travelled far and wide upon this journey." - The Reasoning,
    /A Musing Dream/

    Hewlett-Packard Limited registered office: Cain Road, Bracknell,
    registered no: 690597 England Berks RG12 1HN
     
    Chris Dollin, Sep 1, 2009
    #13
  14. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 29, 10:38 pm, bolega <> wrote:
    > On Aug 29, 2:51 am,spinoza1111<> wrote:
    >
    > > Many people seem to have been upset with this article in Beautiful
    > > Code. I emailed Kernighan about it and received a reply (I'd met the
    > > guy), but no real answer to the basic problem, which is that C cannot
    > > express programming ideas clearly.

    >
    > I admire the fact that someone brought all this in the public
    > discussion because a lot of sleazy people (not referring in particular
    > to this troika) have been able to propagate crap and kept it immune to
    > academic critique just due to people afraid of criticizing it which
    > leads to a lot of newbie sheeple.
    >
    > Do you think C syntax is brain damaged ? Can you explain your second
    > point in more detail and clearly as I could not understand any of it.


    Read this excellent article: Software Fault Prevention by Language
    Choice: Why C is Not My Favorite Language, Richard Fateman. Fateman is
    on the faculty of the rather C-centric Univ of California at Berkeley.
    http://www.eecs.berkeley.edu/~fateman/papers/software.pdf.

    My current language C Sharp addresses some but not all of Fateman's
    points.

    >
    > > The first problem is that by being so "simple" it fails to implement a
    > > recognizable "regular expression" processor.

    >
    > > I thought a second problem was that it used a value parameter as a
    > > work area, which isn't something I would do in my languages of choice
    > > (C Sharp and VB in recent years), but I found myself doing this in C
    > > when I returned to the language mostly to kick the shit out it.

    >
    > > A third problem is praising a programmer for fast work. There's enough
    > > slipshod work in our industry, and enough programmer overwork as it
    > > is.

    >
    > > I think Brian Kernighan would be the first to admit that Lisp as
    > > opposed to C made a more far-reaching contribution to computer science.- Hide quoted text -

    >
    > Actually, in C all they did was to borrow parens and braces from math
    > to delimit blocks - BUT lisp already had the idea in the prefix
    > notation. The other contribution is the for loop with all the loop
    > elements at the top in the interface. The declaration syntax of
    > pointers is poor and ugly. switch-case has fall thru. break and
    > continue is new unless PL1 or BCPL had it.
    >
    > BUT YOU HAVE NOT SHOWN how to structure the recursion. Does it need
    > NFA ? I need a tutorial because C is to stay and I can avoid some of
    > its ugliness by using C++ as pretty C.


    Is C here to stay?
    No way.
    In 2038, lemme tellya straight,
    C's inability to get a date
    Right will cause the thousand years of darkness.
    Ever wonder why spam sorts high, and makes you cry?
    You're looking at the answer, my oh my.

    >
    > > - Show quoted text -

    >
    > I admire the fact that you
     
    spinoza1111, Sep 1, 2009
    #14
  15. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Sep 1, 3:17 pm, Chris Dollin <> wrote:
    > spinoza1111wrote:
    >
    > (re: the Beautiful Code RE matcher)
    >
    > > The first problem is that by being so "simple" it fails to implement a
    > > recognizable "regular expression" processor.

    >
    > False. It implements a /useful subset/ of REs and provides a framework
    > for adding more features -- it's an educational tool, not a library
    > component.


    It's not extensible unless you're a C bigot who's comfortable with
    things like using parameters as work areas. Now, I have learned (more
    precisely relearned) a thing or two by bantering with some of the Fat
    Bastards here who run the show, and I can see why certain idioms are
    used in C. But there's any number of better languages available.
    >
    > --
    > "I have travelled far and wide upon this journey."             - The Reasoning,
    >                                                                /A Musing Dream/
    >
    > Hewlett-Packard Limited registered office:                Cain Road, Bracknell,
    > registered no: 690597 England                                    Berks RG12 1HN
     
    spinoza1111, Sep 1, 2009
    #15
  16. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 31, 12:32 am, (Richard Harter) wrote:
    > On Sun, 30 Aug 2009 06:30:45 +0000, Richard Heathfield
    >
    > <> wrote:
    > >In <h7cc1a$>, Chris McDonald wrote:

    >
    > <snip>
    >
    > >In the current case, bolega (unknown name, to me at least) is slagging
    > >off Brian Kernighan and Rob Pike (both names known to me) and their
    > >book (which I've read). He starts with the word "braggart", and the
    > >rest is similar ranting. It's just perfectly normal bilgewater of the
    > >sort you often find on the Internet, but I don't see why we need to
    > >accuse it of being nilgewater as well.

    >
    > Just so.  The two styles are quite distinct.  Generally speaking
    > those who use the internet for ranting have quite individual and
    > distinct styles.  Thus Nilges is clearly well educated and well
    > read, using many post modern and progressive tropes along with
    > pop psychology.  On the other hand Bolega (I thought it might be
    > a sausage but apparently it is a brand of socks) is less well
    > read and less literate.


    I'd ask you to lay off personalities. You people have taken entirely
    too long to figure out that I'm a class act, and Bolega may very well
    be a class act. I wouldn't myself start off by calling Kernighan a
    braggart, but I did have problems with O'Reilly's selecting some
    fairly humdrum examples of "Beautiful Code" in the book containing
    Kernighan's code. I was offended by Kernighan's praising programmer
    for taking an hour.

    >
    > Incidentally, in my opinion the term "troll" isn't appropriate
    > for such persons.  Trolls are like malicious little children who
    > stir up trouble for the pleasure of seeing people get all
    > excited.  These ranters have a different agenda.


    Thank you for clearing that up at long last. I really appreciate it.

    Trolls don't admit they are wrong to their worst enemies, but
    Heathfield, who knows C if little else that I can discern, did prove
    to me (along with my own experiments) that all parameters in C are
    really and truly call be value, period, and as soon as I realized it,
    I admitted it. I still have a problem with the fact that I had to beat
    the answer out of him as well as mess with C.

    >
    > Richard Harter, ://home.tiac.net/~cri,http://www.varinoma.com
    > No one asks if a tree falls in the forest
    > if there is no one there to see it fall.
     
    spinoza1111, Sep 1, 2009
    #16
  17. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 30, 3:10 pm, w_a_x_man <> wrote:
    > On Aug 28, 11:35 pm, bolega <> wrote:
    >
    > >                            Look how he put
    > > the code after problem statement and then has the need to explain it.
    > > Ideally, the discussion should be such that the student or reader
    > > himself jumps to the solution. That is why I give these unix school of
    > > pike/thomson/kernighan low grade in almost all their expositions
    > > except that they wrote earliest books to make millions of dollars in
    > > royalties and since now they are nobody due to linux, they are poorly
    > > regurgitating old material.

    >
    > Kernighan fails to correct the bugs in his programs.


    We all have bugs in significant programs.
    >
    > Download his awk here:http://cm.bell-labs.com/cm/cs/who/bwk/awk95.exe
    >
    > Test it with this program:
    >
    > BEGIN {
    >   # Specify the field-separator.
    >   FS = "!"
    >   text = "foo!bar"
    >   $0 = text
    >   # Should print "foo".
    >   print $1
    >   printf "Press <ENTER>: "
    >   getline junk
    >   $0 = text
    >   print $1
    >
    >
    >
    > }- Hide quoted text -
    >
    > - Show quoted text -
     
    spinoza1111, Sep 1, 2009
    #17
  18. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 30, 2:30 pm, Richard Heathfield <> wrote:
    > In <h7cc1a$>, Chris McDonald wrote:
    >
    > > Ed Morton <> writes:

    >
    > >>On Aug 28, 11:35=A0pm, bolega <> wrote:
    > >>> This braggart admits that he had to put this code in TWO books and
    > >>> visit it twice to be explained. I am puting the excerpt from pp2-4
    > >>> of this book and the C code.

    >
    > >>You should post this to comp.lang.c.

    >
    > >>    Ed.

    >
    > > He did, and I smelt a Bilges sock puppet.


    Don't make mock of my patronym, punk.
    >
    > By the walks-like,swims-like,quacks-like theorem, I do see why you
    > think so, but I think we should be slow to make such accusations,
    > since they are so often wrong. I have never actually been accused of
    > being a sock puppet as far as I am aware, but I have certainly been
    > accused of running them (which I have never done, but of course those
    > who accuse me don't believe that).


    Wise words, for wisdom crieth in the streets. The only time I have
    used a sock puppet was once on wikipedia.
    >
    > People can and often do use similar styles, especially when responding
    > to people with whom they're perhaps not the best of friends. The
    > other day, an irregular poster, a guy - who'd been away for a while
    > and is unlikely to have become familiar with my occasional habit of
    > marking nilgewater with "nonsense snipped - nothing left" - made


    Don't make mock of my patronym or I will make mock of you as I have in
    the past. You **** with me I fight back, you dig? My relatives are war
    heroes and professionals and they don't deserve this shit.

    > precisely the same response. It would be easy to accuse /him/ of
    > being a sock puppet... and yet his name has been well-known in
    > another group for many years and he knows far more about that group's
    > subject than I do, and I vaguely recall having a few extended
    > disagreements with him in the past. He also posts from a different
    > continent, by the way.
    >
    > Sock puppets undoubtedly happen, but they don't really matter because
    > what counts is not who says what, but what they say (and, to a
    > certain extent, how they say it). We might pay a lot of attention to
    > a name we recognise (e.g. if Donald Knuth started posting, we'd sit
    > up and take notice) - but *only* after it became obvious that it
    > wasn't some spotty teenager mucking about. And we judge that by
    > content. "By their fruits you shall know them" and all that.
    >
    > In the current case, bolega (unknown name, to me at least) is slagging
    > off Brian Kernighan and Rob Pike (both names known to me) and their
    > book (which I've read). He starts with the word "braggart", and the
    > rest is similar ranting. It's just perfectly normal bilgewater of the


    Don't make mock of my patronym, since it's an insult not so much to me
    as to my relatives. If you must make mock, my first name is Edward and
    my handle is spinoza1111.

    My uncle, Edward Joseph NILGES, was killed in Italy in March 1945
    leading Japanese American Nisei against the Germans. Don't mock him.

    My father, Richard G Nilges, fought unethical practises in medicine.
    Don't mock him.

    Mock my first name or posting handle. Lay off "Nilges".

    > sort you often find on the Internet, but I don't see why we need to
    > accuse it of being nilgewater as well.
    >
    > --
    > Richard Heathfield <http://www.cpax.org.uk>
    > Email: -http://www. +rjh@
    > "Usenet is a strange place" - dmr 29 July 1999
    > Sig line vacant - apply within
     
    spinoza1111, Sep 1, 2009
    #18
  19. bolega

    spinoza1111 Guest

    Re: Can anyone write this recursion for simple regexp morebeautifully and clearly than the braggarts

    On Aug 29, 10:38 pm, bolega <> wrote:
    > On Aug 29, 2:51 am,spinoza1111<> wrote:
    >
    > > Many people seem to have been upset with this article in Beautiful
    > > Code. I emailed Kernighan about it and received a reply (I'd met the
    > > guy), but no real answer to the basic problem, which is that C cannot
    > > express programming ideas clearly.

    >
    > I admire the fact that someone brought all this in the public
    > discussion because a lot of sleazy people (not referring in particular
    > to this troika) have been able to propagate crap and kept it immune to
    > academic critique just due to people afraid of criticizing it which
    > leads to a lot of newbie sheeple.
    >
    > Do you think C syntax is brain damaged ? Can you explain your second
    > point in more detail and clearly as I could not understand any of it.
    >
    > > The first problem is that by being so "simple" it fails to implement a
    > > recognizable "regular expression" processor.

    >
    > > I thought a second problem was that it used a value parameter as a
    > > work area, which isn't something I would do in my languages of choice
    > > (C Sharp and VB in recent years), but I found myself doing this in C
    > > when I returned to the language mostly to kick the shit out it.

    >
    > > A third problem is praising a programmer for fast work. There's enough
    > > slipshod work in our industry, and enough programmer overwork as it
    > > is.

    >
    > > I think Brian Kernighan would be the first to admit that Lisp as
    > > opposed to C made a more far-reaching contribution to computer science.- Hide quoted text -

    >
    > Actually, in C all they did was to borrow parens and braces from math
    > to delimit blocks - BUT lisp already had the idea in the prefix
    > notation. The other contribution is the for loop with all the loop
    > elements at the top in the interface. The declaration syntax of
    > pointers is poor and ugly. switch-case has fall thru. break and
    > continue is new unless PL1 or BCPL had it.
    >
    > BUT YOU HAVE NOT SHOWN how to structure the recursion. Does it need
    > NFA ? I need a tutorial because C is to stay and I can avoid some of


    If by NFA you mean an NDFA (non-deterministic finite automaton), no.
    If you go down that road, you need to convert the regex first to an
    NDFA and then to a deterministic DFA by treating groups of possible
    symbols to single "symbols". A problem I have with the article is that
    it doesn't confront this need.

    Aho Sethi et al.'s COMPILERS (Dragon book) addresses how to do this.

    But for individual regexes it's straightforward to code them directly.



    > its ugliness by using C++ as pretty C.
    >
    > > - Show quoted text -

    >
    > I admire the fact that you
     
    spinoza1111, Sep 1, 2009
    #19
  20. bolega

    Chris Dollin Guest

    Re: Can anyone write this recursion for simple regexp more beautifully and clearly than the braggarts

    spinoza1111 wrote:

    > On Sep 1, 3:17 pm, Chris Dollin <> wrote:
    >> spinoza1111wrote:
    >>
    >> (re: the Beautiful Code RE matcher)
    >>
    >> > The first problem is that by being so "simple" it fails to implement a
    >> > recognizable "regular expression" processor.

    >>
    >> False. It implements a /useful subset/ of REs and provides a framework
    >> for adding more features -- it's an educational tool, not a library
    >> component.

    >
    > It's not extensible unless you're a C bigot


    You mis-spelled "programmer".

    > who's comfortable with things like using parameters as work areas.


    IE, using variables as variables. The style is iffy, but the usage
    is easy.

    > ... and I can see why certain idioms are
    > used in C. But there's any number of better languages available.


    Better than what, for what? Surely you don't believe that there's
    a single meaning for "better", even in the relatively small field
    of computer programming languages.

    Also, whether or not C is "better" than some other language doesn't
    affect whether or not "it fails to implement a recognizable "regular
    expression" processor." and hardly affects "is extensible".

    --
    "I have travelled far and wide upon this journey." - The Reasoning,
    /A Musing Dream/

    Hewlett-Packard Limited registered no:
    registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England
     
    Chris Dollin, Sep 1, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page