OCaml - like patternmatcher in D (Re: Ocaml...) (page 3) - D Programming Language Discussion Forum

December 29, 2002

OCaml - like patternmatcher in D (Re: Ocaml...)

Posted by Ilya Minkov
in reply to Mark Evans

Permalink

Ilya Minkov

Posted in reply to Mark Evans

Permalink

Mark Evans wrote:
>>The developer who writes this doesn't seem to be experienced.
> 
> 
> He's a Ph.D. computer scientist working as a high-level consultant for a large
> corporation, with a working knowledge of probably a dozen languages, and at
> least two decades of experience.  He coordinates with various engineers across
> his company in many disciplines.  So he has serious real-world experience.
> 
I only referred to his experience in OLE/COM. People tend to make mistakes - especially I do. :)

I've analyzed the way OCaml works. The basic underlying ideas are as simple as genious. But after you know that, you can also implement such things in C, and reach yet higher performance.

I somehow doubt about the test correctness. That depends on how you view it. It was eratosthenes sieve, right? I bet he chose the recursive solution in all langueges. OCaml does some magic: if it encounters a linear recursive function, it is converted into a loop... one of the basic C constructs. It is the breakthrough point, else a simple stepping through the linked list would take an age and eat up the whole stack. But that also means that if the one who wrote the benchmark chose the "naive" implementation, OCaml would with some luck make more out of it as "naive" C. However, for non-linear problems an additional effort must be taken, although OCaml code would still stay shorter than C. Besides, i guess C version chose an array for simplicity, and OCaml the linked list.

OCaml is absolutely wonderful for writing parsers and such. There is an example in the manual, which shows a small basic interpreter. If you look at the source file, it looks almost like a YACC source! I'm not really sure there's a need to integrate YACC into D, but i'll think if it's possible to think out some syntax which would be OK within D.

A most feature is a pattern matcher, which serves as an if-elsif-else sequence. You write something like:

(*1*)	let rec lSub first second = match (first, second) with
(*2*)	  | ([],_)  -> []
(*3*)	  | (xs,[]) -> xs
(*4*)	  | (xs,ys) when not (beginsWith ys xs) -> failwith "undefined"
(*5*)	  | (a::xs,b::ys) -> lSub xs ys ;;

I've marked line numbers in as comments for the convenience. You can see there are no types. They are all implicit. Let's take it apart.

1. Make a recursive function "lsub", which takes parameters "first" and "second" and let it return the result of pattern matching. The pattern matched object is a tuple (kind of a structure), composed of "first and second"
2. First pattern, applies when "first" is an empty list and "second" is anything. Then return an empty list.
NOTE: list is always a single-linked list, not an array.
TYPE DEDUCTION: "first" must be a list. Return must be a list.
NOTE: if the type of some later statement is different, you get an error.
3. If "second" is an enpty list, return "first".
TYPE DEDUCTION: "second" must be a list.
4. Calls the function "beginsWith" with parameters "first" and "second" and if it returns 'false' then an exception is raised.
5. Here happens an interesting thing: each of the lists is separated into 2 parts, the "head" element and the "tail" - the rest of the list. The syntax head::tail is both for joining, and for separating. So, the heads are discarded in this line, and tails are passed to the next instance of this function, a reult of which is returned.

The pattern matching cases apply from top to bottom, so you start with less general cases, and end with generally more common ones, so that usually the last one(or more) does the recursive call. Of course, as soon as some case actually applies, the pattermatching is finished and its result is returned. As opposed to the C fall-through. :)

Although it saves a couple of lines of code, every line simply contains more information. As soon as you've seen it, you can also simulate such a technique in C, evaluating the pattern to an scalar in a simple form and applying the "case" statement. BTW, it might be good to standardise this evaluation for a number of "big" types, not just for strings. Say, for "smart unions", using the information about current type, zero/nonzero or other things requiered by the "cases".
Maybe (anonymous) struct in case statement, evaluated to an extent requiered by the cases? How about it?

*Walter, your opinion?*

As you can see, the underlying basic types in OCaml are very powerful, and have a short operator synatax. Another powerful thing is, you can easily define trees of any configuration. I'll think a bit about how similar things can be implemented in D. In OCaml you do it by defining a "smart union":

typa 'a bintree = Empty | Node of ('a * 'a * 'a bintree);;

or something in that manner. "Empty" and "Node" are constructors, which initialize a bintree, which is a union, to one of the states, either "Empty", storing nothing, or a "Node", storing two values of an unknown type "'a" and one value of a type "bintree" based on the same type.

Maybe it doesn't look as good, but handling of this thing is really very simple! You can, for example

match mytree with
| Empty -> false
| Node (a,b,tree) -> true;;

Please note that the identifiers which appear after the with statement are not references to data, but "copies" of it, so that you don't tamper with it. They need not necessarily be real copies if not changed.

When I say "smart union" I mean a union which knows its current state.

> Mathematica offers hybrid features and I've certainly heard people complain
> about it being "hard" and "confusing."  But I know it as one of the most
> productive tools in my chest.  The best Mathematica programs are roughly 80%
> functional and 20% imperative.  I've personally instructed engineers and
> mathematicians in Mathematica and learned, to my dismay, that some folks simply
> have a mental block toward functional programming.  I find them writing the
> equivalent of FORTRAN in Mathematica.  When it reaches that point, they might as
> well use FORTRAN instead.  In those cases, the deficiency is really in the
> programmer, not the language.  It's a bit like someone using a wrench as a
> hammer and a hammer as a screwdriver.
:)

> I expect the same holds true of OCaml.  Software gurus who grok hybrid
> programming use Mathematica and love it.  That's why I find it on the shelf of
> software experts.  Then I walk across the aisle and find klunky old MATLAB on
> the shelves of EEs who don't know programming very well. It's more "friendly"
> but a whole lot less powerful, too.
Sure. But since there's no other really good C-descendant other than D, a lot of care must be taken not to break it apart.

Though i'm not sure, i guess there's a flaw in OCaml: when using double-linked lists and such it forces you to step out of the functional domain. I thought it causes some kind of trouble, i'm not really sure what.

> 
> What all of this means for D is that functional features are good, and OCaml may
> have some things to offer in terms of specific implementation concepts.  I'm
> sure the syntax could be improved but its heart is in the right place.
> 
> Mark
> 
> OCaml performance second only to C
> http://www.bagley.org/~doug/shootout/craps.shtml
To my opinion OCaml stuctures are a bit of a too high amount of indirection. When working with trees and lists, it's the best. I'm pretty much conserned, that C allows to reach a yet higher performance. But the improvement might not be that important, if it's hard to develop. Or if it doesn't work at all in the end :)

Errh... i've noticed i've been using "C" too much here. It would usually mean "C or C-like programmimg in D".

> 
> OCaml rapid application development
> http://www.ocaml.org/
> "10/2002. An Objective Caml program wins first prize at the ICFP 2002
> programming contest....09/2000. Two Objective Caml programs win first and second
> prizes at the ICFP programming contest. "
> 
> http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html
> "This paper is an attempt to demonstrate to the 'real world' that functional
> programming is vitally important, and also to help functional programmers
> exploit its advantages to the full by making it clear what those advantages
> are."
> 
> http://www.mysternetworks.com/gmarceau/functional-programming.html
> "If functional programming style is not more widely used, it is mostly because
> of its higher bar of entry. As natural as they become, recursion, lambda's and
> currying are challenging concepts the first time you meat them - not unlike
> pointers (which most visual basic programmer still struggle with)."
> 
> http://www.cs.ait.ac.th/~kitt/caml/
> "You might be surprised if I tell you that ML/OCaml is quite popular and being
> used to develop software in many leading companies. Nortel, AT&T, Ericsson use
> ML or some other functional languages to implement their telephone switching
> firmware. Motorola uses ML to develop a symbolic simulation tool. They throwed
> their original 3500-line fragile C code away, and rewrote the whole program in
> ML. The result was 700-line ML code performing the same functions without bugs.
> The process spent only a couple of weeks. Most people start to write ML without
> knowing how to debug ML programs, but they still get bug-free programs."
I just threw a 200 lines of C code away to write 50 lines of C code which do the same, but this time without bugs. :)

Yes, C is extremely bug-prone. C with spLint is already much better than Delphi and alike. I wrote almost bug-free programms in Delphi from the beginning on, and couldn't get out of the bugs in the first days... weeks of C development. The design flaws are simply too obvious, bit D is even now much better than Delphi. And there may still be room for improvement.

> 
> "Functional programming is quite difficult for me, how is it important? ... This
> is the classic question; students from all batches ask this question.... In the
> past, you have learnt to program using imperative languages. Now, we change to
> functional language, which is completely different programming paradigm. That's
> why it is difficult -- if you already know some imperative language, you have to
> change the way of thinking to write a program using functional language."
> 
> Newbie comments
> http://opensource.lineo.com/~beppu/prose/ocaml.html
> 
> OCaml and COM
> http://caml.inria.fr/camlidl/
hmmm... i didn't know that it has such a tool for COM. this might save a bit of work. However, i'm usually against COM for performsnce reasons. I still code in C, not C++ you know. :)

> 
> Developing with OCaml (online book, discusses functional style)
> http://caml.inria.fr/oreilly-book/html/index.html
> 
>

Walter wrote:
> <user@domain.invalid> wrote in message news:aulg0s$1toh$1@digitaldaemon.com...
> 
>> COM/OLE Capabilities? The developer who writes this doesn't seem to
>> be experienced. An OO language is not requiered at all to access
>> them. They can be accessed even through C. As far as i'm conserned,
>> there might be no automatic tool to do that, but wrapping COM C
>> interface into an Eiffel class should be a snap.
> 
> 
> Doing OLE in C is of course doable, but I'd question the sanity of
> choosing that route over using C++ to do OLE <g>. It's very tedious
> and error-prone, just not worth it.
> 
> D has a sweet way to do OLE as interfaces map right onto OLE classes.
> 
Right. One of the things I like D for. Although this feature is not
important to me, the general design of interoperability appeals me a
lot. As well as all the other things. But using C as a "glue" between
Eiffel and OLE would still be an OK option, as the library user would access OLE wrapped into a native class. An automatic interface
generator should not be too hard to write. I'm actually not interested
in Eiffel anymore, i was just very surprised the man had *such* bad
experiences with it and OLE.

-i.

Forums