Re: Simple question, err... I think



Logan Shaw wrote:
Jon Harrop wrote:
OOP isn't such a big leap. Closures and pattern matching are much more
involved. Again, it is difficult to retrofit them onto C (e.g. the former
essentially requires GC).

Oh, as long as we're on that subject, I've noticed that the documentation
of Haskell made sort of a big deal out of pattern matching, but as far
as I could tell, it was just syntactic sugar that allows you to write
certain "if" statements differently. I didn't think it really added
much to the language except the ability to write certain things with
a slightly (not hugely) more concise syntax. Did I miss something
about patterns?

Pattern matching offers advantages both to the programmer and to the
compiler. The programmer can use it as a much more concise way to pull data
structures apart. For example, look at this RB tree rebalancer written in
OCaml:

let rec ins x t = match t with
`E -> `R(`E, x, `E)
| `R(a, y, b) ->
if x < y then `R(ins x a, y, b) else
if x > y then `R(a, y, ins x b) else t
| `B(a, y, b) ->
if x < y then match ins x a, y, b with
`R(`R(a, x, b), y, c), z, d -> `R(`B(a, x, b), y, `B(c, z, d))
| `R(a, x, `R(b, y, c)), z, d -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, b -> `B(a, x, b) else
if x > y then match a, y, ins x b with
a, x, `R(`R(b, y, c), z, d) -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, `R(b, y, `R(c, z, d)) -> `R(`B(a, x, b), y, `B(c, z, d))
| a, x, b -> `B(a, x, b) else t

and compare it to the C code:

struct Node {
int is_red;
struct Node *l, *r;
int n;
};

typedef struct Node * Set;

struct Node *alloc() { return (struct Node *)malloc(sizeof(struct Node)); }

Set E=0;
Set R(Set l, int n, Set r) {
struct Node *p=alloc();
p->is_red = -1;
p->l = l;
p->n = n;
p->r = r;
return p;
}
Set B(Set l, int n, Set r) {
struct Node *p=alloc();
p->is_red = 0;
p->l = l;
p->n = n;
p->r = r;
return p;
}

Set ins(const int x, Set p);

Set ins_red(const int x, Set p) {
if (x < p->n) {
Set l=ins(x, p->l);
if (l == p->l) return p;
free(p->l);
return R(l, p->n, p->r);
}
if (x > p->n) {
Set r=ins(x, p->r);
if (r == p->r) return p;
free(p->r);
return R(p->l, p->n, r);
}
return p;
}

Set ins_black(const int x, Set p) {
if (x < p->n) {
Set l2 = ins(x, p->l);
if (l2 == p->l) return p;
free(p->l);
if (l2->is_red && l2->l && l2->l->is_red)
return R(B(l2->l->l, l2->l->n, l2->l->r), l2->n, B(l2->r, p->n,
p->r));
if (l2->is_red && l2->r && l2->r->is_red)
return R(B(l2->l, l2->n, l2->r->l), l2->r->n, B(l2->r->r, p->n,
p->r));
return B(l2, p->n, p->r);
}
if (x > p->n) {
Set r2 = ins(x, p->r);
if (r2 == p->r) return p;
free(p->r);
if (r2->is_red && r2->l && r2->l->is_red)
return R(B(p->l, p->n, r2->l->l), r2->l->n, B(r2->l->r, r2->n,
r2->r));
if (r2->is_red && r2->r && r2->r->is_red)
return R(B(p->l, p->n, r2->l), r2->n, B(r2->r->l, r2->r->n,
r2->r->r));
return B(p->l, p->n, r2);
}
return p;
}

or the C++:

Set E=0;
Set R(Set l, int n, Set r) { return new Node(true, l, n, r); }
Set B(Set l, int n, Set r) { return new Node(false, l, n, r); }

struct Found { Found() {} };

Set ins(const int x, Set p) {
if (!p) return R(E, x, E);
const int y = p->n;
if (p->is_red) {
if (x < y) {
Set l2=ins(x, p->l);
if (l2 == p->l) throw Found();
delete p->l;
return R(l2, y, p->r);
}
if (x > y) {
Set r2=ins(x, p->r);
if (r2 == p->r) throw Found();
delete p->r;
return R(p->l, y, r2);
}
}
else {
if (x < y) {
Set l2 = ins(x, p->l);
if (l2 == p->l) throw Found();
delete p->l;
if (l2->is_red && l2->l && l2->l->is_red)
return R(B(l2->l->l, l2->l->n, l2->l->r), l2->n, B(l2->r, y, p->r));
if (l2->is_red && l2->r && l2->r->is_red)
return R(B(l2->l, l2->n, l2->r->l), l2->r->n, B(l2->r->r, y, p->r));
return B(l2, y, p->r);
}
if (x > y) {
Set r2 = ins(x, p->r);
if (r2 == p->r) throw Found();
delete p->r;
if (r2->is_red && r2->l && r2->l->is_red)
return R(B(p->l, y, r2->l->l), r2->l->n, B(r2->l->r, r2->n, r2->r));
if (r2->is_red && r2->r && r2->r->is_red)
return R(B(p->l, y, r2->l), r2->n, B(r2->r->l, r2->r->n, r2->r->r));
return B(p->l, y, r2);
}
}
throw Found();
}

Even this simple example shows pattern matching as more than nested ifs: the
patterns are used to extract parts of the data structure and bind them to
variable names. Moreover, the OCaml compilers will statically check pattern
matches, improving reliability as well as performance.

To see the utility of pattern matching when things get a little more
complicated, try translating this symbolic simplifier into a language
without pattern matching:

let rec simplify = function
| Int _ | Var _ as e -> e
| Plus(e1, e2) -> begin match simplify e1, simplify e2 with
| Int n, Int m -> Int (n + m)
| Plus(Int n, e), Int m | Int m, Plus(Int n, e) ->
Plus(Int (n + m), e)
| e1, Plus(Int _ as n, e2) -> Plus(n, Times(e1, e2))
| e, Int 0 | Int 0, e -> e
| e, (Int _ as n) | (Int _ as n), e -> Plus(n, e)
| e1, e2 -> if e1=e2 then Times(Int 2, e1) else Plus(e1, e2)
end
| Times(e1, e2) -> begin match simplify e1, simplify e2 with
| Int n, Int m -> Int (n * m)
| Times(Int n, e), Int m | Int m, Times(Int n, e) ->
Times(Int (n * m), e)
| e1, Times(Int _ as n, e2) -> Times(n, Times(e1, e2))
| _, Int 0 | Int 0, _ -> Int 0
| e, Int 1 | Int 1, e -> e
| e, (Int _ as n) | (Int _ as n), e -> Times(n, e)
| e1, e2 -> Times(e1, e2)
end

Your questions are perfectly reasonable except, why have you given C
special status as the mother of all programming languages? Why not
assembler, or Lisp?

I thought he was saying that, based on observation, it seems that many
languages seems to be copying C. I would say that's a true statement.

C++, Java and C# certainly mimic C but most new languages do not, IMHO.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html
.



Relevant Pages

  • Re: Simple question, err... I think
    ... int is_red; ... struct Node *l, *r; ... Your C++ example is not an example of natural coding in C++, and I doubt the other examples are natural. ... Regardless of whether you have a point about pattern matching, your examples therefore do not illustrate that, or anything. ...
    (comp.programming)
  • Re: memset o/p not correct
    ... int main ... char pat; ... void findmaxpat ... pattern matching is strstr. ...
    (comp.lang.c)
  • Re: addup intenest ->int
    ... datatype intnest = INT of int | LIST of intnest list ... fun addup = x ... just rewrite it to have only one level of pattern matching, ...
    (comp.lang.ml)
  • Re: The Advantage of Macros
    ... which is usually a single source file, can consist of external declarations ... void fx(int *x, int *y) { ... Also, if you think C is complicated, just take a look at languages like C++, ... C pushes to wrong programming styles. ...
    (alt.lang.asm)
  • Re: Interview with Mr Stroustrup
    ... extern int enumer; ... C90 compilers, the behavior is exactly as if it were not a reserved ... comparisons will have the same value in both languages only in the ...
    (comp.lang.c)