When functional languages can be accepted by industry?

When functional languages can be accepted by industry?

[Dennis (Gang) Chen]

Hi,

Functional languages have not been very successful in industry. Why?

When writing database applications, we use Access, Oracle and languages
which support interfeaces to these database systems.

When writing an application which needs user friendly interface,  one can use Delphi,
or Java,  Visual Basic, Visual C++, C++ Builder etc.

When writing text manipulation programs, perl is a good choice.

For internet application, one use Java, perl, Deplhi, Visual C++ etc.

When higher order functions are required, we can use any OO language, because
an object with one method can be viewed as a function, so if a function can accept
objects as  inputs and output an object, then this function is a higher order function.

To write polymorphic functions, one can use templates in C++.

For data structures which require dynamic memory allocation, one can consider
Standard Template Library (STL) in C++.  From STL, you can choose list, set,
map, tree templates, which are sufficient for most purposes.

The templates in STL are more efficient than list in functinal languages.  For example,
if you use list to implement  set, then a deletion of an element from a set will require
reconstruction of a part of the list, which has  significant memory cost. In STL
templates, this is a simple pointer operation.

To write a parser, I prefer to use ocaml as I'm aware  of its adavantage
in this aspect. But I've learnt that there are other compiler tools available.

Functional languages in ML family are equiped with a much better type system
than C++, this reduce errors in programs, but industry has its own procedure to
ensure the reliability of program. So the weakness in C++ does not bother too
much.

Module in ocaml is an attractive feature.  Large applications are built in a refinement
way,
and different implementations for a given interface will be experimented. Module
should be good  for this, and it is not available in C++.

The size of functional language program is usually small, this feature probably would give
a chance
for functinal language to enter industry. A program stored in a smart card or in a mobile
phone
can not be a big one.

Are there other features of functional language which will attract industry?

--
Dennis Gang CHEN    Senior Software Engineer
Motorola Australia Software Centre, Electronic Design Automation
2 Second Avenue, Mawson Lakes, SA 5095, Australia
phone: +61 8 8203 3560,  mailto: Dennis.G.Chen@motorola.com

Re: When functional languages can be accepted by industry?

[Jean-Christophe Filliatre]

In his message of Mon April 3, 2000, Dennis (Gang) Chen writes: 

> Are there other features of functional language which will attract industry?

- Garbage Collection. (how many memory  leaks in C++ programs? how many
  bugs related to  memory unsafely de-allocated?) And ocaml's  GC is a
  very good one.

- Strong Typing. (how many bugs  are related to unsafe type assumptions
  about pointers in other languages?)

  Above all, strong  typing allows you to develop  and experiment with
  your code very quickly. Let me explain that point.

  When  you add  a  constructor to  a  type, or  when  you change  the
  definition of  a type, or the type  of a function, you  just have to
  recompile and  the compiler will find  all the places  which are now
  ill-typed, or  where a pattern-matching is  non-exhaustive, etc. and
  this is possible because of strong-typing.

  In practice, it appears to be  one of the most important property of
  ocaml's compiler. I use it hundreds of times every day. Whatever the
  size and the complexity of your code are, the compiler will find the
  needed  changes. With  other languages,  you have  to think  hard to
  remember  the places  where changes  are  now needed,  and that's  a
  reason for code inertia (and for bugs, too).

- Recursive data-types.  I didn't follow your arguments  about C++ STL
  versus lists in functional  programming. Of course, lists are almost
  always bad  data-structures. But  a good functional  programmer does
  not use lists as data-structures  (a Lisp programmer, may be :-) but
  rather balanced trees,  Patricia trees, binomial heaps, hash-tables,
  etc. Moreover, most of  these datatypes are persistent, an essential
  property  is  several  applications  (whether  in-place  destructive
  datastructures  require explicit  copies, which  are time  and space
  consuming). You should read  Chris Okasaki's book "Purely Functional
  Data Structures".

Strong typing, recursive data-types and  a good GC are essential tools
for the programmer: you develop  quicker, your code is safer (does not
crash on a seg fault) and is  easier to maintain and to modify. Do you
still need other arguments?

-- 
Jean-Christophe Filliatre    
  Computer Science Laboratory   Phone (650) 859-5173
  SRI International             FAX   (650) 859-2844
  333 Ravenswood Ave.           email  filliatr@csl.sri.com
  Menlo Park, CA 94025, USA     web    http://www.csl.sri.com/~filliatr

  

Re: When functional languages can be accepted by industry?

[Dennis (Gang) Chen]

Jean-Christophe Filliatre wrote:

> - Recursive data-types.  I didn't follow your arguments  about C++ STL
>   versus lists in functional  programming. Of course, lists are almost
>   always bad  data-structures. But  a good functional  programmer does
>   not use lists as data-structures  (a Lisp programmer, may be :-) but
>   rather balanced trees,  Patricia trees, binomial heaps, hash-tables,
>   etc. Moreover, most of  these datatypes are persistent, an essential
>   property  is  several  applications  (whether  in-place  destructive
>   datastructures  require explicit  copies, which  are time  and space
>   consuming). You should read  Chris Okasaki's book "Purely Functional
>   Data Structures".

I have not found a method to implement a  set

with an efficient element removal operation.

To my knowledge, the implementation of set based on balanced tree is efficient for

union, difference etc, but does not seem to be reasonably

efficient for deleting an element. Besides, the tree-based

implementation of set requires that the elements have an ordered type,

it is not clear to me how to extend these techniques

to build a set of unordered elements, say, set of sets.

--
Dennis Gang CHEN    Senior Software Engineer
Motorola Australia Software Centre, Electronic Design Automation
2 Second Avenue, Mawson Lakes, SA 5095, Australia
phone: +61 8 8203 3560,  mailto: Dennis.G.Chen@motorola.com

Re: When functional languages can be accepted by industry?

[John Max Skaller]

"Dennis (Gang) Chen" wrote:

> Functional languages have not been very successful in industry. Why?
> 
> When writing database applications, we use Access, Oracle and languages
> which support interfeaces to these database systems.
> 
> When writing an application which needs user friendly interface,  one can use Delphi,
> or Java,  Visual Basic, Visual C++, C++ Builder etc.
> 
> When writing text manipulation programs, perl is a good choice.
> 
> For internet application, one use Java, perl, Deplhi, Visual C++ etc.
> 
> When higher order functions are required, we can use any OO language, because
> an object with one method can be viewed as a function, so if a function can accept
> objects as  inputs and output an object, then this function is a higher order function.

	This is not really the case,  in my opinion.
We can do polymorphism with higher order functions in C. By following
a protocol. But it is truly laborious. :-)
 
> To write polymorphic functions, one can use templates in C++.

	C++ templates provides superior performance, but less
functionality. More precisely, they don't scale well.
 
> For data structures which require dynamic memory allocation, one can consider
> Standard Template Library (STL) in C++.  From STL, you can choose list, set,
> map, tree templates, which are sufficient for most purposes.
> 
> The templates in STL are more efficient than list in functinal languages.  

	No. For list operations -- as understood in functional languages,
functional lists are MUCH faster than C++ STL. In particular,
'applicative'
data structures such as lists provides superb performance in functional
languages. The problem comes when one wants mutable structures: then
STL provides superb performance.

>For example,
> if you use list to implement  set, then a deletion of an element from a set will require
> reconstruction of a part of the list, which has  significant memory cost. In STL
> templates, this is a simple pointer operation.

	Of course, and the same is true if you are silly enough to use
an STL vector to implement a set.  Have a look at ocaml's Set module:
it provides efficient applicative sets. Hashtables provide reasonable
mutable sets.

> To write a parser, I prefer to use ocaml as I'm aware  of its adavantage
> in this aspect. But I've learnt that there are other compiler tools available.
> 
> Functional languages in ML family are equiped with a much better type system
> than C++, this reduce errors in programs, but industry has its own procedure to
> ensure the reliability of program. So the weakness in C++ does not bother too
> much.

	The weaknesses in C++ worry the smart people in
industry I know a lot. My current job is to design a language which
allows safer, more convenient writing of a certain class of programs
which requires ultra lightweight threading. I would not have been
asked to do this in a C++ shop if C++ were thought to be adequate 
(at least, the hand coding of it).

> Module in ocaml is an attractive feature.  Large applications are built in a refinement
> way,
> and different implementations for a given interface will be experimented. Module
> should be good  for this, and it is not available in C++.

	As usual in C++, one can obtain just about any effect you want,
with the right combination of tools. The  problem, as I see it, is that

	1) you must design some kind of architecture supported by a 
certain protocol of usage (not enforced by the type system)

	2) You must write code accoring to this protocol (which is difficult
without tools to check protocol adherence).

	For example, an ordinary module is easily emulated by a C++
namespace -- but while with care you can define 'modules' this way,
you cannot force clients to use them correctly.
 
	This is like memory management in C++: it is possible to design
protocols (and supporting tools) which if used correctly assure correct
memory management -- but not so easy to enforce correct usage.
[This is easy in ocaml .. just don't use Obj or any C, and GC will do
the
job automatically]

> Are there other features of functional language which will attract industry?

	In many cases, it is NOT the language itself which is the obstacle.
It is often 'meta-lingual' problems: compilation model, performance,
ability to interface to other systems, library, etc.

	Ocaml scores fairly well on these counts, but despite the 
nasty problems with the C++ compilation model, ocaml's is still more
limited.

	Note that ocaml ISN'T a functional language, but an 'simula like'
language just like C++ is: a mix of functional, procedural, and object
oriented features.

---------------------------------------------------------------------------

	I'll be generating C++ using a tool written in ocaml.
This has some advantages -- many of the advantages of C++ are retained,
whereas one of the applications that ocaml shines at: developing
language translators -- will be put to good use.

	I have no interested in 'promoting' functional languages
as a better alternative than, say, C++: rather of finding ways to
use tools together, to be able to build better software.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[Dennis (Gang) Chen]

Jean-Christophe Filliatre wrote:

> > I  have not  found a  method to  implement a  set with  an efficient
> > element removal  operation. To  my knowledge, the  implementation of
> > set based on  balanced tree is efficient for  union, difference etc,
> > but  does  not seem  to  be  reasonably  efficient for  deleting  an
> > element. Besides, the tree-based implementation of set requires that
> > the elements  have an  ordered type, it  is not  clear to me  how to
> > extend these techniques  to build a set of  unordered elements, say,
> > set of sets.
>
> Ocaml sets come with a comparison function, so that you can build sets
> of sets. See   http://caml.inria.fr/ocaml/htmlman/manual053.html.
>
> If you can  manage with sets of integers,  you could consider Patricia
> trees  instead  of  balanced  trees,  as  suggested  in  that  article
> http://www.cs.columbia.edu/~cdo/papers.html#ml98maps
>
> As  I already  wrote,  Okasaki's  book is  marvelous,  and gives  many
> different implementations  of efficient datastructures,  together with
> tools to analyze theire complexity.

Thanks for the suggestion, it sounds to be interesting to consider the ocaml
comparison function on sets to build sets of sets.

For the deletion operation, I've contacted Okasaki, who has also proposed
balanced tree and Patricia tree, as well as the above paper and the following one:
http://www-swiss.ai.mit.edu/~adams/BB/index.html

The deletion operation described in these papers will rebuild a tree. Therefore,
it does not seem to be comparably efficient with those implementations in
imperative languages.

Best regards.

Gang Chen

Re: When functional languages can be accepted by industry?

[Pierre Weis]

> The deletion operation described in these papers will rebuild a tree. Therefore,
> it does not seem to be comparably efficient with those implementations in
> imperative languages.

Don't forget that there is (almost) no restriction on side-effects in
Caml: if this is crucial for your program, you can implement lists as
an imperative data type of your own, and then use destructive update
to perform the deletion operation in the required complexity. Just be
aware that list sharing will be difficult as for any other imperative
implementation of lists.

Best regards,

-- 
Pierre Weis

INRIA, Projet Cristal, http://pauillac.inria.fr/~weis

Re: When functional languages can be accepted by industry?

[Dennis (Gang) Chen]

> Don't forget that there is (almost) no restriction on side-effects in
> Caml: if this is crucial for your program, you can implement lists as
> an imperative data type of your own, and then use destructive update
> to perform the deletion operation in the required complexity. Just be
> aware that list sharing will be difficult as for any other imperative
> implementation of lists.

This is true. But such an approach does not make ocaml

more attractive than C++. In ocaml, there are arrays, structures

and objects etc, but no such things like pointers in C.

For a company or an ordinary programmer,

a simple and safe solution could be just

to pick up the set template from C++ STL.

The purpose of my original message:

"When functional languages can be accepted by industry?"

is not to ignore the advantages of functional languages. I only

want to point out the current challenges to FL. These challenges

can be classified in three groups:

1. Current functional languages do not have enough library support:

so it is not convenient to use FL for database management, programming

friendly user interface etc. Without industry support, these libraries

 would take a long time to implement

2. Functional languages do not well support the use of dynamic

data structures which requires mutable operations for achieving the

efficiency;

3. Morden imperative languages are equiped with certain functional

features, e.g. higher order functions can be simulated by objects,

a certain level of polymorphism can be achieved by using templates,

common dynamic data structures have been built in STL etc.

What are the implications of these challenges?

Neither functional languages nor imperative languages are perfect.

A language designer can choose to add imperative features into a functional

language, and to develop smart algorithms to improve the efficiency;

Alternatively, he can choose to add functional features into an imperative

language, and to develop a better type checker for all or a subset of

of the imperative language, or he can, as described by John Max,  put a functional

language on top of, say C++, and permitting the user to use C++

when necessary.

It is no doubt that functional languages will continue to succeed in

eduacation, research, high level specification, formal program verification,

fast prototyping, etc. But, it appears to me that, in industry, the second approach might

succeed in most cases.

Best regards.

--
Dennis Gang CHEN    Senior Software Engineer
Motorola Australia Software Centre, Electronic Design Automation
2 Second Avenue, Mawson Lakes, SA 5095, Australia
phone: +61 8 8203 3560,  mailto: Dennis.G.Chen@motorola.com

Re: When functional languages can be accepted by industry?

[Daniel de Rauglaudre]

> 1. Current functional languages do not have enough library support:
> so it is not convenient to use FL for database management, programming
> friendly user interface etc. Without industry support, these libraries
>  would take a long time to implement

let rec industry_support () = library_support ()
and library_support () = industry_support ();;

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/

Re: When functional languages can be accepted by industry?

[David Brown]

On Wed, Apr 12, 2000 at 11:15:04AM +0930, Dennis (Gang) Chen wrote:
> > Don't forget that there is (almost) no restriction on side-effects in
> > Caml: if this is crucial for your program, you can implement lists as
> > an imperative data type of your own, and then use destructive update
> > to perform the deletion operation in the required complexity. Just be
> > aware that list sharing will be difficult as for any other imperative
> > implementation of lists.
> 
> This is true. But such an approach does not make ocaml
> more attractive than C++. In ocaml, there are arrays, structures
> and objects etc, but no such things like pointers in C.

I'm not sure I understand what features of pointers in C you want.  Yes,
arbitrary pointer arithmetic is not available.  But, when you work with
mutable data structures in ocaml, the things you assign behave a lot like
pointers in C or C++.

Dave Brown

Re: When functional languages can be accepted by industry?

[Dennis (Gang) Chen]

> I'm not sure I understand what features of pointers in C you want.  Yes,
> arbitrary pointer arithmetic is not available.  But, when you work with
> mutable data structures in ocaml, the things you assign behave a lot like
> pointers in C or C++.

Thank you very much. Now I find that a mutable linked list can indeed be elegantly
implemented in ocaml, e.g.:

type 'a mlist = Empty | Node of 'a mlist ref * 'a ref;;

This is what I didn't realized before.

Cheers.


--
Dennis Gang CHEN    Senior Software Engineer
Motorola Australia Software Centre, Electronic Design Automation
2 Second Avenue, Mawson Lakes, SA 5095, Australia
phone: +61 8 8203 3560,  mailto: Dennis.G.Chen@motorola.com

Re: When functional languages can be accepted by industry?

[Jean-Christophe Filliatre]

> more attractive than C++. In ocaml, there are arrays, structures
> and objects etc, but no such things like pointers in C.

Wrong. You have references, which are quite better than pointers (they
are typed, and necessarily initialized)

> 1. Current functional languages do not have enough library support:

Please. ocaml has  the most wonderful standard library  that any other
language  has ever had.  Have a  look in  the reference  manual before
stating such non-sense.

> 2. Functional languages do not well support the use of dynamic
> data structures which requires mutable operations for achieving the
> efficiency;

Wrong. And you should stop thinking that efficiency means mutable data
structures. Once again, read Okasaki's book.

> It is no doubt that functional languages will continue to succeed in
> eduacation,  research,  high  level  specification,  formal  program
> verification, fast prototyping, etc. But,  it appears to me that, in
> industry, the second approach might succeed in most cases.

Your arguments  are not the good  ones. People in industry  do not use
functional programming for other reasons: because this is not in their
culture, because  they don't know,  because they have not  been taught
functional programming. Some of  them, like you, think that functional
programming languages are inefficient, but they are wrong.

-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

Re: When functional languages can be accepted by industry?

[Pierre Weis]

I cannot resist to answer to your message:

> The purpose of my original message:
> 
> "When functional languages can be accepted by industry?"

[...]
> It is no doubt that functional languages will continue to succeed in
> eduacation, research, high level specification, formal program verification,
> fast prototyping, etc. But, it appears to me that, in industry, the
> second approach might succeed in most cases.

by a mere copy of another message I received just at the same time, from
Chris Tilt:

-------------------------------------------------------------
From: Chris Tilt <cet@webcriteria.com> 
To: Pierre Weis <Pierre.Weis@inria.fr> 
Subject: Industrial use of Caml 

Dear sir,

[...]

I would just like to let you and your team know that we use
the CAML dialect (v2.4) in the development of some of our
production software here at WebCriteria. We are an Internet
startup of about 30 people (6 programmers) and provide a
service for the automatic reviewing of the User Experience
on Websites. 

We use CAML to program the core modeling and analysis module
within our data center. CAML has proven to be a very effective
and efficient programming language for the construction of
this part of the product. We have constructed a Model Human 
Browser based on the GOMS modeling system in combination with
graph theoretic analysis.

My use of CAML was inspired by Andrew Tolmach, a professor at
PSU and OGI in Portland, Oregon, USA.

Please express my deepest appreciation to your team for the  
development of a language that can support an industrial
application. We benefitted from it's ability to quickly and
concisely express a solution to a difficult problem. Although
we base most of our command and control software in Java, ML
is still the choice for modeling and graph theory. 

Best regards, Chris

[...]
--
Chris Tilt                      mailto:cet@webcriteria.com
CTO, WebCriteria, Inc.          http://www.webcriteria.com
-------------------------------------------------------------

I also express my personal ``deepest appreciation to the Caml team''
for our great language that can support hairy academic programming as
well as industrial developments.

Best regards,

-- 
Pierre Weis

INRIA, Projet Cristal, http://pauillac.inria.fr/~weis

Re: When functional languages can be accepted by industry?

[Frank Atanassow]

If you really care about this subject, please read the article by Phil Wadler,
"Why no one uses functional languages",

  http://cm.bell-labs.com/cm/cs/who/wadler/papers/sigplan-why/sigplan-why.ps.gz

and then take your discussion to comp.lang.functional, which is a better forum
for religious wars, with plenty of people who love to waste their time on this
stuff.

-- 
Frank Atanassow, Dept. of Computer Science, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-1012, Fax +31 (030) 251-3791

Re: When functional languages can be accepted by industry?

[Steve Stevenson]

I may have missed some of the below ideas in the discussion.

Let me pass along the notes from a discussion that I had with Jim
McGraw who was one of the true guiding lights of the Sisal effort. You 
can huff and puff at this, but in my experience (11 years at the old
Bell Labs), these ideas ring true. FYI, ASCI is the Accelerated
Strategic Computing Intitiative (simulation support for the US nuclear 
weapons program.)

Best regards,

steve
-----
Steve (really "D. E.") Stevenson           Assoc Prof
Department of Computer Science, Clemson,   (864)656-5880.mabell
Support V&V mailing list: ivandv@cs.clemson.edu

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

The following information is drawn from an exchange with Jim McGraw of 
LLNL on the whys and wherefores of the failure of SISAL to win the
hearts and minds of the programmerate. This is a LaTeX file. The
paragraphs in \em are my comments --- steve
      
\begin{outline}
\item No Commerical Support*\footnote{
Items marked with an asterisk (*) identified by Jim as key
      issues. Italicized text is my response to his comments.
}%
      Code developers want assurance that their codes can be moved to
      different platforms and the language will be supported there.
      This requires vendor concurance and support that Sisal never
      achieved.  This is the standard chicken and egg problem, because
      vendors want to see apps users demanding a product before they
      support it.  This is a very real and very difficult hurdle for
      anyone -- nothing specific to Sisal or functional languages.

      {\em Agreed. You might add academic support. In fact, I'm not
      sure that isn't first sometimes. The grads coming out are not
      going to change languages and systems unless they have to.}

\item We want Fortran*:  Until the ASCI demands came along, there was a
      clear preferance to evolving current codes, which were all
      written in Fortran.  The argument was that we had too much
      invested to rewrite codes and to really get the benefit of
      Sisal, you need to rewrite and rethink your code design.
      Interestingly, the new breed of programmers and the ASCI demands
      have overcome this argument.  Programmers are using many
      variants of Fortran and C.  C++ is coming into vogue and also
      many different front-end control languages, like Eiffel and
      JAVA.  Moreover, many first wanted MPI as the model for
      parallelism, but now they are being forced to use threads and
      OpenMP, to get concurrency within these nodes.  They chose MPI,
      not because it was good, but because it was perceived as the
      ONLY option that would give them long term portability (even
      though to this day, the performance cost of such portability is
      still in serious doubt).  So what they really want is minimal
      change.

      {\em This last sentence would seem to capture it all. We see it
      when we try  to get the students to add a new language.}

\item Unstable compilers for Sisal*:  This is a very legitimate
      argument.
   
\item The programming model did have some serious weaknesses.
      Foremost was I/O.  The whole concept of streams was included to
      have some way of doing I/O, but it was an awkward hack at best.

      {\em I must admit, I find the current spate of implementations
      of streams unintuitive. However, CAML and OCAML seem a bit
      easier to use. Much of this is experience, though, isn't it?
      Streams are really natural for some problems.}

      We ended up making more progress by permitting calls from Sisal
      to C, where we did I/O.  But that approach has some severe
      technical difficulties that programmers must use with great
      care.  Another example of model weaknesses is parallel
      operations like bucket-sort that we could not easily express
      with their natural concurrency.  There were a whole set of
      issues about what we should or should not allow in the language,
      relative to things that were determinant.

      {\em It seems to me that this problem of how to write
      parallelism is ubiquitous and I'm not sure I understand what the
      real problem is from either a cognitive or conceptual
      viewpoint. I did a lot of discrete event simulation work at BTL
      and I find that experience the key to understanding parallelism
      but I don't see the linguistic solution either. }

\item *Programmers did not want to turn control of key things over to a 
      compiler, because they did not trust the compiler to do the
      right thing.  One good example is data layout.  For parallel
      machines with distributed memories, we did not have a good
      solution, although our most likely idea was to use some form of
      pragma from users.  They did not like The idea that the compiler
      would decide where in memory things would go or when various
      thing would be scheduled for execution.  Interestingly, they are
      now discovering that for these complex cache-based machines,
      they must have the compiler do more, or the performance of the
      codes drops through the floor even on single processors.  The
      best performance is achieved by setting up data layout on a node
      based on the exact variable reference patterns across different
      (unnested) loops.

      {\em I wrote a preprocessor for a biophysics group. It took
      chemical stoichiometry notation and developed the functions. I
      realized later that they were using it to generate the code and
      then handchecking the Fortran. Is the problem that we're too
      opaque to the scientists? A more collaborative effort?}

\item I think there is no doubt that the functional programming style
      caused concern among possible programmers.  They are accustomed
      to thinking sequentially and this change was awkward.  Even now,
      many folks still want to stick to SPMD mode, where everything
      has a vector view.  for some kinds of code, this works great.
      However, when we get to codes that need more concurrency and
      require effective load-balancing, the solutions will be very
      hard.  Right now, programmers want to manage their concurency in
      understandable ways.  Sisal did not permit much of this type of
      control.

      {\em My academic colleagues don't seem to be able to make the
      switch to functional, either.}

\item Determinant behavior.  The language definition for Sisal
      required determinacy.  However, to insure this property, we had
      to make sure we had the exact replicatable order of execution
      followed.  This was a VERY high cost in terms of performance.
      Morever, when we went to compare performance with other codes
      that did not guarantee determinacy, we would lose badly.  So our
      implementations had an option to ignore the determinacy
      constraint.  When we did that, we got better performance than
      our competition, but we had lost a key feature, because now we
      could get race conditions.

      {\em How much of this should be fodder for academic
      research. Good old computability theory?}

\item *And the ever present: Politics.  <Understand the points>
   
\item I am not sure this is all of the reasons for our problems, but
      it is certainly the overwhelming majority of them.  It's
      impossible for me to rank their importance, because no one else
      ever tried. 

\item The totality of the issues just weighed us down too much to
      change things.  The key point to me is that many of these issues
      are not unique to Sisal.  ASCI and even the President's PITAC
      report say that "software" is the issue and that we still need
      to consider new programming models and styles.   
              
\item The roots of MPI have been around for a lot longer than that.
      This is any area that moves at a snail's pace and yet users
      demand robust and reliable tools and upward compatibility from
      their current codes.  I am not sure there is any technically
      good solution possible.

\item {\em You may be exactly correct. The problem is not a technical
      one. The desire to change languages seems worse now than ever
      before. Maybe that's how one get ones project out of trouble:
      "We're in the wrong language, let's rewrite."}
\end{outline}
\end{document}

-- 
Best regards,

steve
-----
Steve (really "D. E.") Stevenson           Assoc Prof
Department of Computer Science, Clemson,   (864)656-5880.mabell
Support V&V mailing list: ivandv@cs.clemson.edu

Re: When functional languages can be accepted by industry?

[jean-marc alliot]

I don't want to be caught in a religion war, but I think that our own
experience can be interesting.

We are a small laboratory working inside a much larger structure (the
Centre d'Etudes de la Navigation Aérienne, or CENA), which belongs
itself to a much larger structure (the Direction Générale de l'Aviation
Civile, or DGAC).
For people who do not know the french system, you can consider  the CENA
somewhat like a small MITRE Corporation in the USA, and the DGAC is the
french equivalent of the Federal Aviation Administration.

Software development is a vital concern for our administration. Air
Trafic Control systems are highly dependant on computers and computer
programs. Very large amount of money are spent for software development
and software support (I don't have the exact figures, but it should be
around  50 M$ (million dollars). I can be wrong but the magnitude is
correct).

Currently, CAML is not used in what we call industrial development. On
the opposite it is used for R&D. Inside our lab we all develop in CAML
and some of the softwares we have developped are now used in other R&D
ATC centers, but also used for some more operational applications, like
the evaluation of airspace sectoring.

Here is an extremely (IMHO) interesting example, which was out first
real experience  in CAML. We had an arithmetic traffic simulator written
in C a few years ago (a traffic simulator is something which reads raw
flight plans, makes aircraft fly, and writes lot of interesting
statistics about air traffic sector overloading, air traffic conflicts
and can even solve conflicts).
This software had become difficult to maintain over the years. It was
quite large, with lot of features. We decided to rewrite it completely
in CAML.
The results were better than anything we might have expected. The size
of the code was reduced by a factor of 4, lot of bugs were solved and it
became only slightly slower (10%).

I don't think that CAML needs anything more to be accepted by industry,
from a technical point of view. I have developped applications in many
different languages(ADA, C, C++,...), and I began to use CAML much
later. Even if I would not be as harsh as Jean-Christophe Filliatre, I
agree with him very much. CAML is fast, easy to use, reliable, its
standard library is powerful, strong typing corrects lot of bugs,
dynamic typing is a real comfort compared to ADA.
Moreover, the CAML team is certainly one of the most brilliant and
efficient development team I have dealt with. The language has always
evolved smoothly and (according to me) in the right direction. Questions
are always answered quickly and with a real kindness. You can't ask for
more.

I think that what CAML needs is time. When some of my (and others) young
students will become software project managers, it will be easier for
CAML to become an industry standard.
Let's go teaching CAML !

Re: When functional languages can be accepted by industry?

[T. Kurt Bond]

Note that what I am about to say is *not* intended as a criticism of
OCaml; I use OCaml every day, and enjoy using it.

Jean-Christophe Filliatre writes:
> > 1. Current functional languages do not have enough library support:
> 
> Please. ocaml has  the most wonderful standard library  that any other
> language  has ever had.  Have a  look in  the reference  manual before
> stating such non-sense.

As much as I enjoy using OCaml, I think that this may be overstating
the case.  OCaml has a very good standard library that is very well
documented; however, it does not have everything.  Just a few examples
of things that are missing from the standard library:

* Parsing and manipulating RFC 822 mail headers
* Parsing and manipulating MIME documents
* Parsing and downloading URLs
* A FTP client
* An HTTP Server
* An HTTP Client
* An IMAP Client
* An SMTP Client
* A POP Client
* A NNTP Client
* A Telnet Client
* Parsing, manipulating, and generating HTML
* Parsing, manipulating, and generating SGML
* Audio data creation and manipulation
* Image data creation and manipulation
* High-level file operations (copy file, copy directory tree, 
  delete directory tree)

Now, one could justifiably argue that such things don't belong in the
standard library, but current a lot of programmers expect things like
this to be in the standard library; this list, for instance, was
generated by quickly scanning the Python documentation, and the Perl
and Java libraries include similar functionality.

It is true that many of these things can be obtained by downloading
contributed packages for OCaml, but that's an extra step that
programmers accustomed to other languages may not bother with when
evaluating OCaml.  They want a quick solution to their specific
problems, and if they don't have to program large chunks of that
solution because some other language includes that functionality in
their standard library, they'll happily use *that* language.

I personally will happily continue to use OCaml for very practical
reasons, and I will continue to recommend to other programmers, but I
will not fool myself into thinking it is perfect and that no-one will
need things that it doesn't currently provide out-of-the-box.

[As a side note, I must commend the OCaml team on their documentation
of the language and standard libraries; every time I have to referee
to the documentation I am impressed again by how succinctly yet
clearly the documentation is written, and by how well organized it
is.]
-- 
T. Kurt Bond, tkb@tkb.mpl.com

Re: When functional languages can be accepted by industry?

[Pierre Weis]

> Thank you very much. Now I find that a mutable linked list can
> indeed be elegantly implemented in ocaml, e.g.:
> 
> type 'a mlist = Empty | Node of 'a mlist ref * 'a ref;;

If efficiency is really crucial, you could also write

type 'a mlist = Empty | Node of 'a mcell
and 'a mcell = {mutable hd : 'a; mutable tl : 'a mlist}

You may have a look at the Caml FAQ, where the existence and
manipulation of pointers in Caml is discussed:

http://pauillac.inria.fr/caml/FAQ/pointers-eng.html

(Fresh english translation written for the occasion).

Best regards,
-- 
Pierre Weis

INRIA, Projet Cristal, http://pauillac.inria.fr/~weis

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Daniel de Rauglaudre wrote:
> 
> > 1. Current functional languages do not have enough library support:
> > so it is not convenient to use FL for database management, programming
> > friendly user interface etc. Without industry support, these libraries
> >  would take a long time to implement
> 
> let rec industry_support () = library_support ()
> and library_support () = industry_support ();;

You have left out the important ingredient: politics.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[William Chesters]

jean-marc alliot writes:
 > I don't think that CAML needs anything more to be accepted by industry,
 > from a technical point of view.

 > Moreover, the CAML team is certainly one of the most brilliant and
 > efficient development team I have dealt with.

Steve Stevenson writes:
 > \item Unstable compilers for Sisal*:  This is a very legitimate
 >       argument.
 >    
 > \item The programming model did have some serious weaknesses.
 >       Foremost was I/O.  The whole concept of streams was included to
 >       have some way of doing I/O, but it was an awkward hack at best.

   I don't think it can be emphasised too often that some functional
languages (ocaml perhaps chief among them) are of *extremely* high
quality when it comes to the bread and butter usability issues which
concern real-world developers.

   ocaml's compiler/runtime are 99% solid, as reliable as any
commercial system I've worked with.  The I/O and other libraries are
splendidly down-to-earth and effective.  The documentation is helpful
and mercifully concise.

   Criticism of the "functional" idiom per se simply misses the point,
since ocaml supports imperative data structures very well (the only
possible niggle being the "write" overhead associated with the
generational GC, but that's only an issue for certain kinds of inner
loop, and only in comparison with C/C++).

   (All this is a consequence of the skill and hard work of the ocaml
team---and the rightness of their vision of how the pretty ideas
floating around functional languages could best be exploited in a
practical system.)

   So there is no need to look inwards at ocaml, and the handful of
other good and well-implemented minority languages out there, for an
answer to the question of why industry hasn't accepted them on a wide
scale.  Just look outwards to industry itself.  To get Java accepted
required an extremely singular event, namely the rise of the 'net and
Sun's agreement with Netscape; without that kind of earthquake, you
are in a chicken and egg situation.  E.g. I love ocaml and appreciate
its advantages vis-a-vis Java and C++ very well, but I can't foist it
on my colleagues for lots of good reasons to do with its current
(relatively) narrow user base: customer credibility, second-sourcing
for maintenance, learning curve, ...

   But look, the industry is very big, and there is room for minority
languages to live quite nicely at the "margins" where chicken/egg
isn't such a big problem---and maybe one day emerge and achieve world
domination ;).

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Jean-Christophe Filliatre wrote:
> 
> > more attractive than C++. In ocaml, there are arrays, structures
> > and objects etc, but no such things like pointers in C.
> 
> Wrong. You have references, which are quite better than pointers (they
> are typed, 

	So are C/C++ ones ..

> and necessarily initialized)

	.. which is a serious problem. And C++ also has 'necessarily
initialised' references :-)

> > 1. Current functional languages do not have enough library support:
> 
> Please. ocaml has  the most wonderful standard library  that any other
> language  has ever had.  Have a  look in  the reference  manual before
> stating such non-sense.

	Oh come on. Have a look at a real library before making
such non-sense claims. Considerable functionality is missing,
the library is inconsistent, the documentation is incomplete,
and it is less generic than C++ STL, which is also probably
more efficient on almost every operation.

	Many of us who know STL wonder how to fit it into the
ocaml type system! 
 
> > 2. Functional languages do not well support the use of dynamic
> > data structures which requires mutable operations for achieving the
> > efficiency;
> 
> Wrong. And you should stop thinking that efficiency means mutable data
> structures. Once again, read Okasaki's book.

	The statement said 'functional languages do not
well support use of dynamic data structures which _require mutable
operations for efficiency_'. you cannot say the conditional
is wrong, only the claim that functional languages do not
provide good support for mutable data structures.

	You could argue that the argument is void, since the
assumptions are vacuous 'there are no such data structures',
but reality would prove you wrong very quickly. The vast majority
of data structures are collections of interrelated objects
reflecting or controlling state, and where changes are propagated
throughout the data structures in such a way that efficient
functional modelling would be worthless -- since the application
domain is clearly one in which state transformation is the whole point.
 
> Your arguments  are not the good  ones. People in industry  do not use
> functional programming for other reasons: because this is not in their
> culture, because  they don't know,  because they have not  been taught
> functional programming. Some of  them, like you, think that functional
> programming languages are inefficient, but they are wrong.

	Show me a functional programming language that is as fast
as C++ and I will give up C++. :-)

	Until then, I will use ocaml where speed is not essential,
but power is important, and confidence in the result crucial
(such as a compiler).

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[Julian Assange]

Pierre Weis <Pierre.Weis@inria.fr> writes:

> concisely express a solution to a difficult problem. Although
> we base most of our command and control software in Java, ML
> is still the choice for modeling and graph theory. 

Speaking of graph theory, does anyone know of a collection of
*caml code to deal with least path, clustering, etc?

-- 
Stefan Kahrs in [Kah96] discusses the
   notion of completeness--programs which never go wrong can be
   type-checked--which complements Milner's notion of
   soundness--type-checked programs never go wrong [Mil78].

Re: When functional languages can be accepted by industry?

[Julian Assange]

"T. Kurt Bond" <tkb@tkb.mpl.com> writes:

> Note that what I am about to say is *not* intended as a criticism of
> OCaml; I use OCaml every day, and enjoy using it.
> 
> Jean-Christophe Filliatre writes:
> > > 1. Current functional languages do not have enough library support:
> > 
> > Please. ocaml has  the most wonderful standard library  that any other
> > language  has ever had.  Have a  look in  the reference  manual before
> > stating such non-sense.
> 
> As much as I enjoy using OCaml, I think that this may be overstating
> the case.  OCaml has a very good standard library that is very well
> documented; however, it does not have everything.  Just a few examples
> of things that are missing from the standard library:
> 
> * Parsing and manipulating RFC 822 mail headers
> * Parsing and manipulating MIME documents
> * Parsing and downloading URLs
> * A FTP client
> * An HTTP Server
> * An HTTP Client
> * An IMAP Client
> * An SMTP Client
> * A POP Client
> * A NNTP Client
> * A Telnet Client
> * Parsing, manipulating, and generating HTML
> * Parsing, manipulating, and generating SGML
> * Audio data creation and manipulation
> * Image data creation and manipulation
> * High-level file operations (copy file, copy directory tree, 
>   delete directory tree)

If these things ever end up in the standard library, I will pack my bags and
go home.

If you read the links of The Hump, you will see that there are indeed
libraries to do most of these things in ocaml. The problem is that The
Hump is poorly organised, and the 3rd party library code is often
poorly documented. A lot could be done to mitigate this situation, by
making the 3rd party libraries look much closer to caml.inria.fr, than
the brief reference we see on The Hump. python.org's indexing of 3rd
party libraries is an excellent example of this. 

That said, one excellent catalytic change, would be to bring in
seperate compilation library version dependency analysis (i.e an ocaml
3rd party package manager) into the main ocaml distribution. I believe
there is an ocaml package to do this already, although I'm not sure
how sound it is.

As the number of inter-dependent ocaml packages increases, I'm
increasingly hit by version conflicts.

A library calculus system which was URL name space aware would be
particularly interesting. NetBSD and FreeBSD take this approach in
their own package source dependency system for instance. Compiling one
package recursively pulls in, uncompresses, patches, compilies and
installs the dependencies.

Such technology strongly fosters co-operative community.

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Frank Atanassow wrote:
> 
> If you really care about this subject, please read the article by Phil Wadler,
> "Why no one uses functional languages",
> 
>   http://cm.bell-labs.com/cm/cs/who/wadler/papers/sigplan-why/sigplan-why.ps.gz
> 
> and then take your discussion to comp.lang.functional, which is a better forum
> for religious wars, with plenty of people who love to waste their time on this
> stuff.

	I do not think this is a waste of time.
I think it is important for people who are in industry to tell
the ocaml team what they think. This is no religous war: the readers
of this list all like ocaml :-)

	Furthermore, because it supports object orientation and
imperative style -- as well as throwing in ( .. he ducks quickly .. )
functional stuff, one cannot throw the 'functional language are XXXX'
argument at ocaml. It ISN'T a functional language.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

The beginning of a library for Formal algebra and numerical Analysis

[Christophe Raffalli]

I am please to make available The beginning of a library for Formal
algebra and numerical Analysis
for Ocaml. It fully uses functor, provides matrices, solver, polynomial,
expressions, complex numbers, ...

Personnaly I think it is very nice and could go quite far if we started
a cooperative development of that project.
 
Visit http://www.lama.univ-savoie.fr/~RAFFALLI/formel.html for more
details and download !

I will post in another mail a wish list for OCaml to make that library
even nicer !

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Caml wish list

[Christophe Raffalli]

Here is a list of request for Ocaml that would really make the libray
for formal and numerical calculus better (see
http://www.raffalli.univ-savoie.fr/~RAFFALLI/formel.html) : 


- include with ...

	would allow multiple inheritance in signature !

- include in structure.

	We should also think about multiple inheritance and
	even override in this case. But a simple implementation 
	would already be useful.

- typing of structure containing modules is problematic:

	if you write:

	module F = functor(M:M) -> 
	struct 
	  module M =M
	end

	Then you have a module Q:Q where Q is a subtype of M.

	If you type R = F(Q) then
	the type of R.M is M even if the type system knows that
	R.M = Q.

	This makes it impossible in some cases to put modules as member 
	of structure ! It was for instance impossible to put the Ring of 
	scalar as a member of the structure Vector, because when this
	Ring is a Field, we may loose this information and fail to
	type-check perfectly correct program.

- Infix operator like + ...

	Every body will agree that infix operator are needed. So
	R.+ should be allowed as an infix operator and R.(+) would
	be prefix.

	One could event think to reuse symbols like + for many functions.
	Here is a simple proposal on how to do it that I would really enjoy to 
	see working :

	Two new commands in OCaml structure (the syntax can be changed):

	share + : 'a -> 'a -> 'a

	this makes that + exists and is type-checked with type 'a -> 'a -> 'a

 	share + = add_int
	share + = add_float
	...

	this means that, after type checking, + will take the first value 
	among  add_int, add_float, ... whose type matches the infered type for
+.

	If add_int is tested first, this will be compatible with existing code.
	This is easy to implement (I think).

	One could even allow some kind of recursive macros !

	share + = fun (x,y) (x',y') -> (x+x', y+y')
	share + = List.map2 (+)
	share + = Array.map2 (+)

	This is a bit mode difficult to implement, but it seems feasible.

- The library is too slow when using floating points.

	One need to add inlining for functor and functions 
	before doing the floating point optimisations. 

	A function or functor that is used only once 
	should be inlined regardless of its size (no huge code size 
	explosion even if the function is used once in every .ml files)

	A syntax for inlining on demand (when applying and/or) defining the
	function should be provided. A way would be to have three new
	choices when defining a function or functor:
	- normal
	- always inlined
	- inlined on demand



-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: When functional languages can be accepted by industry?

[John Max Skaller]

One barrier to acceptance of ocaml in industry:
lack of programmers. This requires training.
Who can help?

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[William Chesters]

John Max Skaller writes:
 > > Wrong. You have references, which are quite better than pointers
 > > (they are typed, and necessarily initialized)
 > 
 > 	.. which is a serious problem.

   We've talked about this before ...  Yes, initialising a value
sometimes means a certain number of clock cycles "wasted", but it
seems to me that any program in which those cycles are non-negligible
compared with the cycles you are going to spend on actually using the
value in question is probably a poorly written program.  It's only if
you construct a huge array of zeroes and then discard it that
initialisation can have a serious impact (?).

 > 	Oh come on. Have a look at a real library before making
 > such non-sense claims. Considerable functionality is missing,
 > the library is inconsistent, the documentation is incomplete,
 > and it is less generic than C++ STL, which is also probably
 > more efficient on almost every operation.

   STL-completeness is not the touchstone of a library's value.  I
think most people who used Java for real work found that we hardly
ever missed it (pre-1.2, Java's libraries were very unpretentious),
and enjoyed not having to spend time explaining it to co-workers ...
The STL is yet another manifestation of the terribly 80s
more-is-better (and cleverer-is-better) philosophy which permeates the
world of C++.

   To put it succinctly: have a look at what is really used (and
useful) before making such claims.  Having said that I agree the
ocaml library could usefully be grown a bit.

 > 	Show me a functional programming language that is as fast
 > as C++ and I will give up C++. :-)

   It's perfectly true that C++ is the only language in which there is
often a way to code your solution in such a way that (a) the source is
written in concise high-level terms, and (b) the object code is as
fast as it can possibly be.  Leaving aside the fact that there are
also dozens of much slower ways to code your solution---onto which all
but the most expert C++ programmers are bound by Sod's law to
light---that's wonderful and impressive.  I agree, sometimes C++ is
the only way.  But how much of the code that gets written fails to
meet the following conditions:

   -- it can run 50% (or 3 times, whatever) slower than C and it just
doesn't matter (think Java, Perl, VB, ...); or

   -- it can be written as easily, with less palaver, in plain old C; or

   -- if it's written in C++, it's done quickly and defensively, so
there's little danger of it ending up unmaintainably clever or
unstable, but also little danger of it running fast.

   I honestly don't think it's raw speed relative to C++ that's
standing in the way of the acceptance of functional languages in
industry.  However, ...

 > One barrier to acceptance of ocaml in industry: lack of
 > programmers.

... is surely spot on.

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Julian Assange wrote:

> > * Parsing and manipulating RFC 822 mail headers
> > * Parsing and manipulating MIME documents
> > * Parsing and downloading URLs
> > * A FTP client
> > * An HTTP Server
> > * An HTTP Client
> > * An IMAP Client
> > * An SMTP Client
> > * A POP Client
> > * A NNTP Client
> > * A Telnet Client
> > * Parsing, manipulating, and generating HTML
> > * Parsing, manipulating, and generating SGML
> > * Audio data creation and manipulation
> > * Image data creation and manipulation
> > * High-level file operations (copy file, copy directory tree,
> >   delete directory tree)
> 
> If these things ever end up in the standard library, I will pack my bags and
> go home.

[...]

> As the number of inter-dependent ocaml packages increases, I'm
> increasingly hit by version conflicts.
> 
> A library calculus system which was URL name space aware would be
> particularly interesting. NetBSD and FreeBSD take this approach in
> their own package source dependency system for instance. Compiling one
> package recursively pulls in, uncompresses, patches, compilies and
> installs the dependencies.
> 
> Such technology strongly fosters co-operative community.

	Yeah, but failing to recognize that the technology 
for inter-networking such shared library modules is required
before it can be implemented: namely the components you
said will send you packing your bags were they fundamental. :-)

	There's a difference between 'standard library' and
'standard distribution' too: the "Unix" module, for example,
is part of the latter but not the former.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[Nickolay Semyonov]

John Max Skaller wrote:
>         Show me a functional programming language that is as fast
> as C++ and I will give up C++. :-)
> 

On what type of applications?

Nickolay

Re: When functional languages can be accepted by industry?

[jean-marc alliot]

John Max Skaller wrote:

>
> > > 1. Current functional languages do not have enough library support:
> >
> > Please. ocaml has  the most wonderful standard library  that any other
> > language  has ever had.  Have a  look in  the reference  manual before
> > stating such non-sense.
>
>         Oh come on. Have a look at a real library before making
> such non-sense claims. Considerable functionality is missing,
> the library is inconsistent, the documentation is incomplete,
> and it is less generic than C++

I don't think there are lot of things missing in the STANDARD library. I
don't see why it is inconsistent. I don't see why documentation is
incomplete. Things might be missing in the general library, yes.

>

>
>         Show me a functional programming language that is as fast
> as C++ and I will give up C++. :-)
>

CAML. Just try programming the fibonacci function in both languages...  -:)

CAML becomes slow when you use some of the nice functional features of the
language. But if you write CAML as you write C code you won't lose much
speed. Over the years, students and development programmers have developped
thousand of lines of code in many different languages in my team and
writing or rewriting in CAML had  a limited impact on the speed of the
program.

Again, I don't like religious opinions, but I am anyway going to explain a
few things. I am sorry to use personal examples, but I know them very well
-:)

I understand that for highly time critical fragment of codes that are
extremely closed to machine architecture, C is a reasonable choice. I am an
old game programmer, and once had a program (otage) based on pattern
recognition, who had its 15 minutes of glory on the Internet Othelo Server
and entered the top 5 list. It is written in C and assembly language, it is
using each and every bit of every byte of memory; it is fast indeed, and C
is efficient.
But I stopped maintaining it, because it has become a real pain. Even when
the code is documented, the program is extremely complex, and when I stop
working on it for a few months, it is almost impossible to re-enter the
code. I am too old and too busy now to work on it anymore. And I don't like
programs core dumping anymore either.
C should be only used by experienced programmers, who are extremely careful
of everything they write, with unitary tests for each and every function,
and only for time critical functions.
On the opposite, I wrote a chinese checkers program in CAML this year in a
few days (it was a challenge with some friends). It is in no way
ridiculous, and is extremely easy to maintain.

I understand also people using ADA for programs that need to be highly
portable, easy to maintain and whose life span will be long. The ADA code I
wrote with ALSYS and VERDIX compiler for my PhD thesis 15 years ago (an
extension of PROLOG to modal logic) is still compiling without any
modification on the gnat compiler today. ADA includes representation clause
that makes it almost independant to anything including machine
architecture.
ADA is not as fast as C or as easy to use as CAML, but it is definitely a
decent compromise for many industrial applications. It suffered from a very
bad integration with UNIX (always worked well with VMS) at the beginning,
especially when I/O and multi-tasking were both involved. This is quite
solved now (thanks to clone()...)

I am extremely sorry to say that I don't understand people using C++when
they have a choice.
This language is, according to me, a collection of every little thing that
should never be done. Templates are, from a theoritical point of view, a
matter of laugh, and generally not compatible between different compilers
(I have examples every year with students coming back from training periods
with programs written in C++, and who speend hours to make them compile
with the University compilers and machines). For people knowing object
theory and its EIFFEL implementation, the C++ object system looks at least
shaky. Operators overloading has been pushed to its ugliest limit (it does
exist in ADA, but WITH and USE clauses give at least meaningfull
informations) : I saw once an experienced programmer who was using a
library developped by someone who had left the development team spending
two days to find a "core dumping" bug in the C++ library left by this
former developper. The fragment of code looked like this:
void f(foobar *ival)
{
foobar *l;
for (l=ival; l<>NULL;l++) {...}
}
Unfortunately, the ++ operator had been overloaded for type foobar
somewhere else and was no more a pointer incrementation, but was in fact:

l = l->next
where next was a field of the foobar structure : the problem was an
incorrectly initialized field and not an "incorrectly" terminated pointer
array.
I could write endlessly about C++  problems ; I had to use it for a few
years for development purpose, and, if I first began to like it, I soon
learned to hate it.
JAVA has corrected many problems, such as memory allocation or the infamous
core dumping behaviour. But it is not that fast...

I love programming. I began when i was 15 (almost 25 years ago) on small
machines, I learned assembly language, BASIC, FORTRAN and C before learning
anything about computer science theory. To summarize, I  did mathematics at
the University and hacking at home ; I went back to University to learn
computer science when I was 26, and I had then lot of bad programming
habits.
It took me a long time to understand that there were more proper ways to
write programs.
I also had to realize that speed is far from being the only concern, and
that fast but buggy/unmaintanaible programs are useless in team
development. Functional programming is painful to learn (and it was painful
for me) when you are used to imperative programming. You have to learn to
think differently before you can really master the language. But it is
worth the effort.

JMA

Re: When functional languages can be accepted by industry?

[Markus Mottl]

> That said, one excellent catalytic change, would be to bring in
> seperate compilation library version dependency analysis (i.e an ocaml
> 3rd party package manager) into the main ocaml distribution. I believe
> there is an ocaml package to do this already, although I'm not sure
> how sound it is.

There are certainly a few "social" technologies that could significantly
boost the usability of OCaml in real-world projects, a good version
management tool for third party sources probably ranking among the "most
missing" ones.

I am highly convinced that the success of some "modern" (?) languages
(Perl, Python, Java) was strongly supported by a (more or less) standard
way of incorporating third-party libraries.

The current state of OCaml is definitely advanced enough to pay more
attention to some "not-so-academic" goals like providing for tools aimed at
extending the user base. I believe this would benefit the whole process a
lot in the future.

> A library calculus system which was URL name space aware would be
> particularly interesting. NetBSD and FreeBSD take this approach in
> their own package source dependency system for instance. Compiling one
> package recursively pulls in, uncompresses, patches, compilies and
> installs the dependencies.

It need not be an "overkill" version right from the beginning - a nice,
clean and (important!) standard way to safely add, update and remove
libraries would surely be a good start.

> Such technology strongly fosters co-operative community.

Taking a look at the Hump and Gerd's link database, I have the impression
that there is already enough "critical mass" of contributors, but most of
the contributions are "one-man-efforts", i.e. nice, but they don't have
enough "punch". Maybe we should really think more about ways to "unleash
the forces of cooperative development". As it seems: easily said, difficult
to do...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: When functional languages can be accepted by industry?

[John Max Skaller]

jean-marc alliot wrote:
> 
> John Max Skaller wrote:
> 
> >
> > > > 1. Current functional languages do not have enough library support:
> > >
> > > Please. ocaml has  the most wonderful standard library  that any other
> > > language  has ever had.  Have a  look in  the reference  manual before
> > > stating such non-sense.
> >
> >         Oh come on. Have a look at a real library before making
> > such non-sense claims. Considerable functionality is missing,
> > the library is inconsistent, the documentation is incomplete,
> > and it is less generic than C++
> 
> I don't think there are lot of things missing in the STANDARD library. I
> don't see why it is inconsistent. I don't see why documentation is
> incomplete. Things might be missing in the general library, yes.

	The order of arguments is perverse. Obvious functions are missing,
such as finding the number of elements in a map. The documentation
fails to tell how fast the functions are, and the specifications are
sometimes imprecise.

> >         Show me a functional programming language that is as fast
> > as C++ and I will give up C++. :-)
> >
 
> CAML. Just try programming the fibonacci function in both languages...  -:)

	:-)
 
> CAML becomes slow when you use some of the nice functional features of the
> language. 

	It's one heck of a lot slower using the imperative features,
and even slower using object oriented ones. My not very carefully
coded Python interpreter (which uses a combination of all these
features)
is at least 10 times slower than CPython.

	Mind you -- it implements a much better language. :-)

> But if you write CAML as you write C code you won't lose much
> speed. 

	Sorry. You lose HEAPS. Even 10% is significant, CAML can
be over a decimal order of magnitude slower. C++ generics are 
generally much faster (being automatically specialised -- which
also causes code bloat :-(

> Over the years, students and development programmers have developped
> thousand of lines of code in many different languages in my team and
> writing or rewriting in CAML had  a limited impact on the speed of the
> program.
 
	No doubt the compiler I'm writing in Ocaml will be fast enough.
But there is no way CAML will compete with the C++ code the compiler
generates.
[At least not the way the CAML bytecode interpreter is written]

> Again, I don't like religious opinions, but I am anyway going to explain a
> few things. I am sorry to use personal examples, but I know them very well
> -:)
 
> I understand that for highly time critical fragment of codes that are
> extremely closed to machine architecture, C is a reasonable choice.

> Even when
> the code is documented, the program is extremely complex, and when I stop
> working on it for a few months, it is almost impossible to re-enter the
> code. I am too old and too busy now to work on it anymore. And I don't like
> programs core dumping anymore either.

	No dispute. [I'm an 'old' game programmer too]. I'd write
the main game play engine of a strategy game in ocaml in preference
to C/C++, but there's no doubt I do the graphics in C/C++.
There, every ounce of performance is absolutely critical.

> C should be only used by experienced programmers, who are extremely careful
> of everything they write, with unitary tests for each and every function,
> and only for time critical functions.

	Sure. And that is what the company I work for does.
Almost all the code being written is time critical: when you're
talking huge volumes, every percentage point of extra performance
is a many percentage points of lower CPU costs.

> I am extremely sorry to say that I don't understand people using C++when
> they have a choice.

> This language is, according to me, a collection of every little thing that
> should never be done. 

	Sure: it is mainly a consequence of the abysmal base language, C.

>Templates are, from a theoritical point of view, a
> matter of laugh,

	No. They're not perfect. They generate very fast code.
On the contrary, it is the boxed values of functional languages
which are the laugh: they kill performance.

> and generally not compatible between different compilers
> (I have examples every year with students coming back from training periods
> with programs written in C++, and who speend hours to make them compile
> with the University compilers and machines). For people knowing object
> theory and its EIFFEL implementation, the C++ object system looks at least
> shaky. 

	What object theory? There isn't one. Object orientation
is a mess. Eiffel is every bit as bad as C++ here: the fact is that
C++ trades off beauty and correctness for speed and compatibility.

	It is faster than C though, and much easier to use.

> I could write endlessly about C++  problems ; I had to use it for a few
> years for development purpose, and, if I first began to like it, I soon
> learned to hate it.

	So could I, I worked on the design of it :-)

> JAVA has corrected many problems, such as memory allocation or the infamous
> core dumping behaviour. But it is not that fast...

	Java is rubbish. It is a compromise: bad type system, poor performance.
C++ is not a compromise: no features was added that compromised
performance.
	 
> I went back to University to learn
> computer science when I was 26, and I had then lot of bad programming
> habits.

	Sigh. I never wasted my time with so-called computer science.
I learned a lot more doing mathematics than any silly CS course. :-)
[This is more a reflection of the local academic institutions than
anything else :-(

> It took me a long time to understand that there were more proper ways to
> write programs.

	Sure. And hopefully, that no one has the faintest idea what these
ways are. But at least now, theorists finally have a tool to begin
a serious study (category theory).

	So I can put to you that Ocaml is a mish-mash and grab bag
of functional, imperative, and OO features, just like C++: C++ is
faster,
whereas Ocaml provides better -- but by no means perfect -- structure.

	Remember -- I _like_ Ocaml. I do _not_ like C++.
I did my best to make it better, with little result.
But the fact remains, it is the language of choice for most applications
simply because it provides reasonable power, reasonable safety,
and there is an assurance that it can be as fast as you can bother
to take care to make it.

	C++ breaks down with higher order problems, where Ocaml excels.
But it stands up to large scale programming of complex tasks, which
Ocaml does not. Most of the problems I encounter are annoying 
implementation details such as the requirement to link things in order,
with lousy diagnostics when the order is wrong (why doesn't the
diagnostic tell me which module requires the one with the
'missing' implementation?)

	So, in my view, Ocaml is reasonable for the purpose
I've been writing it -- compiler development. But it isn't
so hot at numerical programming, operating system interaction,
or high speed communications.

	It would be nice to have some real genericity,
of the kind that FISh promises, or some real integration
of stateless (functional) and stately (object oriented),
programming, of the kind Charity promises.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[John Prevost]

>>>>> "mm" == Markus Mottl <mottl@miss.wu-wien.ac.at> writes:

    mm> There are certainly a few "social" technologies that could
    mm> significantly boost the usability of OCaml in real-world
    mm> projects, a good version management tool for third party
    mm> sources probably ranking among the "most missing" ones.
        {...}
    mm> Taking a look at the Hump and Gerd's link database, I have the
    mm> impression that there is already enough "critical mass" of
    mm> contributors, but most of the contributions are
    mm> "one-man-efforts", i.e. nice, but they don't have enough
    mm> "punch". Maybe we should really think more about ways to
    mm> "unleash the forces of cooperative development". As it seems:
    mm> easily said, difficult to do...

I agree that this is the most significant "hump" in the way of O'Caml
at the moment.  Whenever I become enthused about working on a major
interesting project in O'Caml, I first start looking at what other
people have done.  I go to the hump, and the link database.  There, I
discover that I could perhaps reuse code from three other people.

But what's this?--one of them uses findlib, one of them has a Makefile
they rolled by hand (which is broken), and one of them just gives you
source code, no library at all.

So I sort of sit there and stare at these three useful libraries,
thinking about how I can build my system/library in such a way that
it'll work with all three, and...  it's just a mess.  I eventually
sort of roll over and take a big sigh, then leave to do something
else.

Needless to say, I don't get much code written.

Perl has it's problems, and the quality of modules varies
immensely--but when I find a module, I can install it and try it out
in about 20 seconds.  That lets me get on to the more important
problems of writing code.


While this sort of thing might, by a number of arguments, not be the
sort of thing that should be considered part of the "core language",
I'd like to argue that such an official blessing would be enough to
get people to start using the tools consistantly, rather than
everybody doing things their own way.  And it's only when everybody's
working in approximately the same way that this kind of simplicity of
working with third-party modules becomes possible.

>>>>> "xl" == Xavier Leroy <Xavier.Leroy@inria.fr> writes:

    xl> In OCaml, you have excellent I/O (better than Java's in my
    xl> opinion) in the standard library, TK and GTK bindings for
    xl> GUIs, and a couple of bindings to existing database libraries
    xl> (see the Caml hump at http://caml.inria.fr).  I agree the
    xl> database stuff needs more work and the GUI stuff needs more
    xl> documentation, but it's a start.

Mmm.  I actually have one minor gripe about the I/O stuff--not being
able to turn a set of functions into an in_channel or out_channel has
bit me a number of times.  It's not so bad, until you want to do
something like implement an encrypting network stream and then use
stuff from Printf to write to it.

(This could also simplify the code somewhat, since things like bprintf
and sprintf could be written in terms of such a primitive.  This would
probably lose some speed, though.)

    xl> I certainly can't disagree with you.  The main problem here is
    xl> human resources.  But we are looking at ways for big
    xl> industrial users to help fund that kind of developments.

I think that if you took something like, say, Findlib, and asked if
you could integrate it into O'Caml, you'd discover at least a few
people who would make time to go over things looking for issues and
warts to clean up.  It's hard to be enthused if it's not going to be
"official".

Even though I've been waiting for a good solution for consistent
handling of third party modules almost as long as I've been using
O'Caml, the fact that only a few people use findlib cuts down on its
usefulness to me.  If Findlib were accepted into O'Caml, I would go
out of my way to send findlibifying patches to authors of various
packages, instead of just getting depressed.

John.

Re: When functional languages can be accepted by industry?

[Brian Rogoff]

On Tue, 18 Apr 2000, John Max Skaller wrote:
> jean-marc alliot wrote:
> > I don't think there are lot of things missing in the STANDARD library. I
> > don't see why it is inconsistent. I don't see why documentation is
> > incomplete. Things might be missing in the general library, yes.
> 
> 	The order of arguments is perverse. Obvious functions are missing,
> such as finding the number of elements in a map. The documentation
> fails to tell how fast the functions are, and the specifications are
> sometimes imprecise.

The standard library is improving though, and additional libraries could 
certainly be written by users. My main concern here is that the best
libraries make it into the standard distribution. In particular I prefer 
Pcre to the Str library, and would like to see it become the standard 
distribution. Note that I'm not using *distribution* and *library* 
interchangeably. 

In order to get an STL-like library in OCaml, I think we'd need some form
of overloading. This comes up on this list every now and again, and it is 
clear that the Caml team is working on it, so we'll see. I particularly
liked the last discussion here on type classes where Pierre Weis mentioned 
that he was interested in an overloading scheme which could unify the 
notations for array and string access; I'd be overjoyed if he is
successful! Until some form of overloading is in OCaml though, I wouldn't 
look to the STL as a library to emulate, though I suppose its most
important idea, the expression of algorithms in terms of iterators rather
than specific data structures, doesn't depend on overloading. 

> > >         Show me a functional programming language that is as fast
> > > as C++ and I will give up C++. :-)
> > >
>  
> > CAML. Just try programming the fibonacci function in both languages...  -:)
> 
> 	:-)

I believe that the Stalin compiler for Scheme, which is a whole program
compiler (you give up separate compilation) has done better than C on some 
much more significant programs than fibonacci. I suspect that any compiler 
which abandons separate compilation and does aggressive whole program
analysis may have problems with extremely large programs, but I don't have 
evidence to back this up. 

I presume that a similar compiler for an ML variant could be written. Given 
that the Caml team has limited resources, I'd rather they spend them
elsewhere, as I am satisfied with the performance of OCaml for the problems 
I apply it to. I realize that others have different priorities.

Another potential area for performance improvement would be the elimination
of GC using the region system or something like it. 

There are probably other places in the implementation where choosing a 
different strategy could close the gap with C++ in speed, at the cost of 
code bloat. 

Also, the claim is made that C++ with templates generates code with run
time performance comparable to hand coded C. Several studies that I've
read call that into question; Richard O'Keefe's usenet comparison of a few 
years ago, the book by Kernighan and Pike "The Practice of Programming" and 
Anh Vo's papers on the Cdt library which compare it with the STL.

> > CAML becomes slow when you use some of the nice functional features of the
> > language. 
> 
> 	It's one heck of a lot slower using the imperative features,
> and even slower using object oriented ones. 

Once again, if you're willing to subject your entire program to analysis
then I bet the OO parts of OCaml could be made to run much
faster. SmallEiffel seems to be running pretty fast these days. 

Don't get me wrong; I think separate compilation is important, and would
prefer that the default compiler operate as it does now. I just think that 
some of the performance hits you see could be eliminated without changing
the language but by changing the compiler. 

> > But if you write CAML as you write C code you won't lose much
> > speed. 

Huh? What if you write crypto code, or a BDD library, or numerics, or 
a regex library, or ...

> 	Sorry. You lose HEAPS. Even 10% is significant, CAML can
> be over a decimal order of magnitude slower. C++ generics are 
> generally much faster (being automatically specialised -- which
> also causes code bloat :-(

I don't think you see an order of magnitude for the most part though...

> 	No dispute. [I'm an 'old' game programmer too]. I'd write
> the main game play engine of a strategy game in ocaml in preference
> to C/C++, but there's no doubt I do the graphics in C/C++.
> There, every ounce of performance is absolutely critical.

If every ounce of performance is truly "absolutely critical", then go to 
assembler. Even C won't compete :-)

Also, for numerics, Fortran compilers are still probably better than C,
though I don't know how much longer that will hold true. 

> >Templates are, from a theoritical point of view, a
> > matter of laugh,
> 
> 	No. They're not perfect. They generate very fast code.
> On the contrary, it is the boxed values of functional languages
> which are the laugh: they kill performance.

See above on templates. I agree that boxed values suck for high
performance code. 

> 	What object theory? There isn't one. Object orientation
> is a mess. Eiffel is every bit as bad as C++ here: the fact is that
> C++ trades off beauty and correctness for speed and compatibility.
> 
> 	It is faster than C though, and much easier to use.

Faster than C? I doubt that. Where is your evidence? 

> 	Remember -- I _like_ Ocaml. I do _not_ like C++.
> I did my best to make it better, with little result.
> But the fact remains, it is the language of choice for most applications
> simply because it provides reasonable power, reasonable safety,
> and there is an assurance that it can be as fast as you can bother
> to take care to make it.

I'd say simply because it is perceived as a better C, and C was already
the language of choice for most applications. 

OCaml is not riding anyone's coattails, so it really has to be better at 
something, or, more likely, we have to create a niche in which OCaml is
the best language (read "The 22 Immutable Laws of Marketing ;-). I think
that writing compilers and associated tools is one such niche, since it
plays off of MLs strengths.

-- Brian

Re: When functional languages can be accepted by industry?

[Max Skaller]

Nickolay Semyonov wrote:
> 
> John Max Skaller wrote:
> >         Show me a functional programming language that is as fast
> > as C++ and I will give up C++. :-)
> >
> 
> On what type of applications?

	Thank you. This is the right answer. And I use both languages.
Although I much prefer ocaml :-)

-- 
John (Max) Skaller at OTT [Open Telecommications Ltd]
mailto:maxs@in.ot.com.au      -- at work
mailto:skaller@maxtal.com.au  -- at home

Re: When functional languages can be accepted by industry?

[Sven LUTHER]

On Tue, Apr 18, 2000 at 03:49:23AM +1000, John Max Skaller wrote:
> 	No doubt the compiler I'm writing in Ocaml will be fast enough.
> But there is no way CAML will compete with the C++ code the compiler
> generates.
> [At least not the way the CAML bytecode interpreter is written]

Bytecode, ...

what about the native code compiler ? 

If you are comparing Ocaml to C++, at least use similar stuff. Or else you
should compare to bytecode java, or interpreted C++ (if such a thing exists).

Friendly,

Svne LUTHER

Re: Caml wish list

[thierry BRAVIER]

[-- Attachment #1: Type: text/plain, Size: 1804 bytes --]

Dear ocamlers,

Christophe Raffalli a écrit:

> Here is a list of request for Ocaml that would really make the libray
> for formal and numerical calculus better (see
> http://www.raffalli.univ-savoie.fr/~RAFFALLI/formel.html) :
>
> - include with ...

and

> - include in structure.

would be great.

> - Infix operator like + ...
>         R.+ should be an infix operator and R.(+) would be prefix.

I would like that too.

>         One could event think to reuse symbols like + for many functions.
>         Here is a simple proposal on how to do it that I would really enjoy to
>         see working :
>
>         Two new commands in OCaml structure (the syntax can be changed):
>
>         share + : 'a -> 'a -> 'a
>
>         this makes that + exists and is type-checked with type 'a -> 'a -> 'a
>
>         share + = add_int
>         share + = add_float
>         ...
>

I fear that your share proposal will not interact well with separate compiling of
modules:
how can the list of all share definition be completely know to the compiler ?
It reminds me of the now obsolete overload keyword in C++.


>         One could even allow some kind of recursive macros !
>
>         share + = fun (x,y) (x',y') -> (x+x', y+y')
>         share + = List.map2 (+)
>         share + = Array.map2 (+)
>
>         This is a bit mode difficult to implement, but it seems feasible.

This, I think, is inspired by C++ templates and specialisation issues;
I don't think it is in the spirit of ML because for instance adding a new share
definition
could totally change the meaning of another previous share definition.

Maybe there is anyhow a way to find a strict, satisfying meaning to share.

Does somebody have insights ?

Cheers.

Thierry Bravier

[-- Attachment #2: Type: text/html, Size: 2654 bytes --]

Re: Caml wish list

[William Chesters]

thierry BRAVIER writes:
 > >         One could event think to reuse symbols like + for many functions.
 > >         Here is a simple proposal on how to do it that I would really enjoy to
 > >         see working :
 > >
 > >         Two new commands in OCaml structure (the syntax can be changed):
 > >
 > >         share + : 'a -> 'a -> 'a
 > >
 > >         this makes that + exists and is type-checked with type 'a -> 'a -> 'a
 > >
 > >         share + = add_int
 > >         share + = add_float
 > >         ...
 > >
 > 
 > I fear that your share proposal will not interact well with separate compiling of
 > modules:
 > how can the list of all share definition be completely know to the compiler ?

Well, I can't remember offhand how SMJ/NJ handles overloading, but it
seems to work reasonably well.  On the other hand, I am nowadays a
convert to ocaml's hard line on overloading---it's an absolute curse
of many, many C++ programs by coders whose enthusiasm outruns their
judgement.

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Brian Rogoff wrote:
> >       It is faster than C though, and much easier to use.
> 
> Faster than C? I doubt that. Where is your evidence?

	C++ supports several optimisations not possible in C89:
inline functions, and object orientation important amoung them.
Inline has been added to C9X. This was not gratuitously, but for a
reason :-)
.. there's no doubt C++ is faster than C89. 
How much depends on the compiler of course, but what the compiler is
able to do also depends on the language being implemented :-))

[Why C++ is popular]

> I'd say simply because it is perceived as a better C, and C was already
> the language of choice for most applications.

	Yes. This is a large part of the appeal. And a valid one.
The C++ committee worked hard to minimise any loss of compatibility
or performance.

	C++ is a compromise. It is a compromise involving theory,
industry, and politics. A large part of it's success must be attributed
to an unashamed requirement to appeal to the market.
 
> OCaml is not riding anyone's coattails, so it really has to be better at
> something, 

	Oh: it is. No doubt of it. It is unequivocably better at
symbol manipulation, compiler development, and managing abstraction.

	Let's put it this way: my Python interpreter Vyper, written in ocaml,
is 
_currently_ 10 times slower than CPython. But I am working
(slowly) on improving the technology, and I can do that much
better in ocaml than C. I guess it is possible to make it _faster_ than
CPython
eventually. Quite apart from being a better language (supporting
functional
style nested scopes, an algebraic matching construction, and a few other
interesting things). This stuff is likely to outperform the equivalent
Python
if used for suitable problems.

	What it lacks most isn't performance, but a way of separately
compiling and linking native library modules (to be loaded dynamically).
CPython can do this. It is an important strength.

> or, more likely, we have to create a niche in which OCaml is
> the best language (read "The 22 Immutable Laws of Marketing ;-). I think
> that writing compilers and associated tools is one such niche, since it
> plays off of MLs strengths.

	Yes. And it would gain many more users if some of the
industrial weaknesses were addressed. Such as being able to generate
dynamically linkable shared libraries, have the compiler find an order
for linking modules from a given set ... Note I'm not complaining here:
these things require resources .. typically lacking from the environment
in which the ocaml developers work :-(

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Sven LUTHER wrote:
> 
> On Tue, Apr 18, 2000 at 03:49:23AM +1000, John Max Skaller wrote:
> >       No doubt the compiler I'm writing in Ocaml will be fast enough.
> > But there is no way CAML will compete with the C++ code the compiler
> > generates.
> > [At least not the way the CAML bytecode interpreter is written]
> 
> Bytecode, ...
> 
> what about the native code compiler ?

	Too hard I guess. The bytecode compiler can probably
be modified to be stackless, and thus support a huge number
of concurrent threads via continuations. It is not so easy to
generate native code with these properties.

> If you are comparing Ocaml to C++, at least use similar stuff. Or else you
> should compare to bytecode java, or interpreted C++ (if such a thing exists).

	I am. I am generating C++ code which could well be the
same performance as a bytecode interpreter, if it didn't use the 
'C' stack, since that is the reason I'm generating C++ code
rather than using the bytecode interpreter. :-)

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[Michael Hicks]

> I believe that the Stalin compiler for Scheme, which is a whole program
> compiler (you give up separate compilation) has done better than C on some 
> much more significant programs than fibonacci. I suspect that any compiler 
> which abandons separate compilation and does aggressive whole program
> analysis may have problems with extremely large programs, but I don't have 
> evidence to back this up. 
> 
> I presume that a similar compiler for an ML variant could be written. Given 
> that the Caml team has limited resources, I'd rather they spend them
> elsewhere, as I am satisfied with the performance of OCaml for the problems 
> I apply it to. I realize that others have different priorities.

In fact, researchers at NECI have developed a whole-program Standard ML
compiler, called MLton.  You can read about it at

http://external.nj.nec.com/PLS/MLton/

In general, its programs run 2-3x faster than SML/NJ, but occasionally they
are a bit slower.

Mike

-- 
Michael Hicks
Ph.D. Candidate, the University of Pennsylvania
http://www.cis.upenn.edu/~mwh            mailto://mwh@dsl.cis.upenn.edu
"Every time someone asks me to do something, I ask if they want French
 fries with that." -- testimonial of a former McDonald's employee

Re: Caml wish list

[Christophe Raffalli]

>  >
>  > I fear that your share proposal will not interact well with separate compiling of
>  > modules:
>  > how can the list of all share definition be completely know to the compiler ?

It is not the case if you consider that two modules sharing the same
symbol 
should declare it with the same type and then you merge the list of
possible values. Some value may be hiden by other, but this is already
the case for usual module field.

> Well, I can't remember offhand how SMJ/NJ handles overloading, but it
> seems to work reasonably well.  On the other hand, I am nowadays a
> convert to ocaml's hard line on overloading---it's an absolute curse
> of many, many C++ programs by coders whose enthusiasm outruns their
> judgement.

I agree with you that one should not abuse overloading. The problem of
C++
is that you can even overload operator such as = ! I would live happy if
there was a finite, fixed and short lists of overloadable operator (In
fact  arithmetic operators are the most needed).

The pb is that if you use twice the same functors declaring + (which is 
unavoidable if you do formal calculus). You can never have access to
both symbols with their short names. So sharing/overloading
is really needed as soon as you use and reuse functors in complex ways.

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: When functional languages can be accepted by industry?

[Markus Mottl]

> In order to get an STL-like library in OCaml, I think we'd need some form
> of overloading. This comes up on this list every now and again, and it is 
> clear that the Caml team is working on it, so we'll see. I particularly
> liked the last discussion here on type classes where Pierre Weis mentioned 
> that he was interested in an overloading scheme which could unify the 
> notations for array and string access; I'd be overjoyed if he is
> successful!

Over the time I have adapted to the "lack" of overloading and do not find
it so missing for arithmetic operations. However, there is one application
domain where I really feel "bitten" by not being allowed to overload
operators: monads.

I would like to use them more often for structuring code and trying out
some new styles of functional programming, but it's a pain using different
kinds of monads at the same time: you'd always have to specify module names
for "bind"-operators, which puts the otherwise very convenient infix
operators quite out of the question. But I wonder whether this specific
application justifies a complication of the type system...

> I presume that a similar compiler for an ML variant could be written. Given 
> that the Caml team has limited resources, I'd rather they spend them
> elsewhere, as I am satisfied with the performance of OCaml for the problems 
> I apply it to. I realize that others have different priorities.

What concerns me, I also consider the performance of OCaml programs fair
enough for nearly all purposes. Since interfacing to C-code is so easy, one
can always eliminate bottlenecks on a lower level.

> There are probably other places in the implementation where choosing a 
> different strategy could close the gap with C++ in speed, at the cost of 
> code bloat. 

I do not think that C++ is competing with OCaml in the same niche so there
is probably no point in addressing differences here. In fact, although it
was surely not designed for this purpose, I believe that OCaml could be a
serious threat to some scripting languages: partly due to its high
performance, partly, because it is much saner = easier to maintain, and
highly portable! The Unix-library is very complete and would also play an
important role here.

> Also, the claim is made that C++ with templates generates code with run
> time performance comparable to hand coded C. Several studies that I've
> read call that into question; Richard O'Keefe's usenet comparison of a few 
> years ago, the book by Kernighan and Pike "The Practice of Programming" and 
> Anh Vo's papers on the Cdt library which compare it with the STL.

Programs on modern architectures depend so heavily on cache behaviour that
performance claims for code-bloating techniques seem to be rather
suspicious. I'd also like to see substantial benchmarks that prove the
merits...

> > 	Sorry. You lose HEAPS. Even 10% is significant, CAML can
> > be over a decimal order of magnitude slower. C++ generics are 
> > generally much faster (being automatically specialised -- which
> > also causes code bloat :-(
> 
> I don't think you see an order of magnitude for the most part though...

Considering the improvements on the hardware side in terms of processor
performance, 10% seems very insignificant to me (a few months of hardware
development at most), especially if you take into account that for many
non-numeric applications the limiting factor is most often I/O-bandwidth.
Correctness, maintainability and portability are (well, should be) the
primary concerns in a world that changes fast - not "fast" programs...

If your employer says that you should switch to lower-level, unsafe
programming languages to get 10% more performance, tell him that he
should rather buy new hardware (if you dare to! ;-)
If he doesn't want, present him an estimate of the costs of more errors...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: When functional languages can be accepted by industry?

[Brian Rogoff]

On Thu, 20 Apr 2000, Markus Mottl wrote:
> > In order to get an STL-like library in OCaml, I think we'd need some form
> > of overloading. This comes up on this list every now and again, and it is 
> > clear that the Caml team is working on it, so we'll see. I particularly
> > liked the last discussion here on type classes where Pierre Weis mentioned 
> > that he was interested in an overloading scheme which could unify the 
> > notations for array and string access; I'd be overjoyed if he is
> > successful!
> 
> Over the time I have adapted to the "lack" of overloading and do not find
> it so missing for arithmetic operations. 

In another life I wrote lots of numerical linear algebra programs, and I 
find that a little overloading would make the code a lot nicer. It's also 
the case that lots of prefix functions, like "print", are perfectly fine 
to overload, and I hate having to explicitly tag these names with their
type, probably the way fans of type inference hate writing explicit types. 
Can't we have the best of both worlds?

Also, I suspect that many people who are negative about overloading are 
coming from C++, where the combination of overloading and implicit
coercion is nightmarish. Coming from Ada, I haven't had any such problems, 
so I still miss overloading. 

> However, there is one application domain where I really feel
> "bitten" by not being allowed to overload operators: monads.

Funny that you should say that, I've been spending a bit more of my spare 
time hacking Haskell for the same reasons you describe below. I translated 
almost all of the monads in Wadler's "Essence of FP" paper to OCaml but 
ended up using regular prefix syntax. Yes, if you use different monads 
simultaneously you have to use qualified names. Bummer.

No, I haven't got to Hughes "arrows" yet; its taking enough effort to get 
comfortable with monads ;-)

> I would like to use them more often for structuring code and trying out
> some new styles of functional programming, but it's a pain using different
> kinds of monads at the same time: you'd always have to specify module names
> for "bind"-operators, which puts the otherwise very convenient infix
> operators quite out of the question. But I wonder whether this specific
> application justifies a complication of the type system...

... snip ...

> I do not think that C++ is competing with OCaml in the same niche so there
> is probably no point in addressing differences here. In fact, although it
> was surely not designed for this purpose, I believe that OCaml could be a
> serious threat to some scripting languages: partly due to its high
> performance, partly, because it is much saner = easier to maintain, and
> highly portable! The Unix-library is very complete and would also play an
> important role here.

Absolutely! This is a point I have been making for a while, that the point 
of comparison should be Perl, Python, and even Java. OCaml performance is 
excellent when compared to these languages.

The main problems here are 

(1) The enormous number of existing libraries (and tools for managing them) 
    for these other languages
(2) The extensive documentation they have
(3) The OCaml error messaging, which makes worse the problem most people 
    already have with the unfamiliar type system

> > > 	Sorry. You lose HEAPS. Even 10% is significant, CAML can
> > > be over a decimal order of magnitude slower. C++ generics are 
> > > generally much faster (being automatically specialised -- which
> > > also causes code bloat :-(
> > 
> > I don't think you see an order of magnitude for the most part though...
> 
> Considering the improvements on the hardware side in terms of processor
> performance, 10% seems very insignificant to me (a few months of hardware
> development at most), especially if you take into account that for many
> non-numeric applications the limiting factor is most often I/O-bandwidth.
> Correctness, maintainability and portability are (well, should be) the
> primary concerns in a world that changes fast - not "fast" programs...
> 
> If your employer says that you should switch to lower-level, unsafe
> programming languages to get 10% more performance, tell him that he
> should rather buy new hardware (if you dare to! ;-)
> If he doesn't want, present him an estimate of the costs of more errors...

Fortunately for me, my employer really likes OCaml :-)

-- Brian

Re: When functional languages can be accepted by industry?

[Markus Mottl]

> In another life I wrote lots of numerical linear algebra programs, and I 
> find that a little overloading would make the code a lot nicer.

I admit: I don't write this much numerical code so I don't have many
opportunities to complain about missing operator overloading there...

> Funny that you should say that, I've been spending a bit more of my spare 
> time hacking Haskell for the same reasons you describe below. I translated 
> almost all of the monads in Wadler's "Essence of FP" paper to OCaml but 
> ended up using regular prefix syntax. Yes, if you use different monads 
> simultaneously you have to use qualified names. Bummer.

It is of course possible to use "regular" (?) prefix syntax, but there are
other problems, too: e.g. if you want to "move" from a state transformer to
a state reader, you might be forced to update some module names, whereas
resolution of operator overloading might change meaning (= the "right"
monad to use) automatically as required.

> The main problems here are 
> 
> (1) The enormous number of existing libraries (and tools for managing them) 
>     for these other languages
>
> (2) The extensive documentation they have

Well, there is not much one can do against this unless you can pay a very
big development team that just focuses on these things...

On the other hand, a "slowly" growing library is more likely to be
well-designed.

> (3) The OCaml error messaging, which makes worse the problem most people 
>     already have with the unfamiliar type system

Except in the cases when OCaml prints out some kilometers of conflicting
module signatures, I am quite content with the error messages.

> Fortunately for me, my employer really likes OCaml :-)

Lucky you! ;-)

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Markus Mottl wrote:

>I believe that OCaml could be a
> serious threat to some scripting languages: partly due to its high
> performance, partly, because it is much saner = easier to maintain, and
> highly portable! The Unix-library is very complete and would also play an
> important role here.

For me, it has deficiency as a scripting language: interactive
(command prompt) use is clumbsy because gnu-readline isn't integrated:
no history or editing. [This should be easy to fix: there's some code
in the Vyper.sourceforge.net repository which might be adapted.]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Markus Mottl wrote:
> Programs on modern architectures depend so heavily on cache behaviour that
> performance claims for code-bloating techniques seem to be rather
> suspicious. I'd also like to see substantial benchmarks that prove the
> merits...

	Code bloat can be expensive, however so can boxed values.
 
> Considering the improvements on the hardware side in terms of processor
> performance, 10% seems very insignificant to me 

	Sure it does. But you are not thinking rationally. 
You're thinking emotionally. So try this: in doing your job,
you find a 10% productivity improvement. Not much eh?
Try _over_ an extra months holiday! Are you kidding 10% isn't
significant?

> Correctness, maintainability and portability are (well, should be) the
> primary concerns in a world that changes fast - not "fast" programs...

	It is for those who commission and pay for the code to determine
what their strategic goals are. We have code written in _assembler_.
 
> If your employer says that you should switch to lower-level, unsafe
> programming languages to get 10% more performance, tell him that he
> should rather buy new hardware (if you dare to! ;-)

	My employer isn't the user of the software but the puveryor of it.

> If he doesn't want, present him an estimate of the costs of more errors...

	At present, the cost of C++ errors is much lower. That is because
the company employs a lot of expert C++ programmers. And only one,
nonexpert, ocaml programmer.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[John Max Skaller]

Brian Rogoff wrote:
 
> Absolutely! This is a point I have been making for a while, that the point
> of comparison should be Perl, Python, and even Java. OCaml performance is
> excellent when compared to these languages.

	I don't agree with this. The reason is: ocaml has a much nicer
type system than C++. I would rather write code in it, than C++.
So I'd like it to be faster than C++ as well as nicer :-)
 
> (3) The OCaml error messaging, which makes worse the problem most people
>     already have with the unfamiliar type system

	This can be improved with time I imagine.
[Error handling is a lot of work]


-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: When functional languages can be accepted by industry?

[Markus Mottl]

> For me, it has deficiency as a scripting language: interactive
> (command prompt) use is clumbsy because gnu-readline isn't integrated:
> no history or editing. [This should be easy to fix: there's some code
> in the Vyper.sourceforge.net repository which might be adapted.]

I have already nearly forgotten about this problem: I use the "ile"-tool
(input line editor - some age old piece of software) as "wrapper" around
the OCaml-toplevel, which gives me all these nice features back. Works with
just about any terminal program!

For those of you who don't have it yet, I have put a link to the
source-tarball into Gerd Stolpmann's link database (name: ILE):

  http://www.npc.de/ocaml/linkdb

After compilation, just start it with "ile ocaml" (even better: assign an
alias!)

Especially useful for teaching/demonstration purposes...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: When functional languages can be accepted by industry?

[Brian Rogoff]

On Sat, 22 Apr 2000, John Max Skaller wrote:
> Markus Mottl wrote:
> >I believe that OCaml could be a
> > serious threat to some scripting languages: partly due to its high
> > performance, partly, because it is much saner = easier to maintain, and
> > highly portable! The Unix-library is very complete and would also play an
> > important role here.
> 
> For me, it has deficiency as a scripting language: interactive
> (command prompt) use is clumbsy because gnu-readline isn't integrated:
> no history or editing. [This should be easy to fix: there's some code
> in the Vyper.sourceforge.net repository which might be adapted.]

I use ile on Solaris and that fixes that. There is an OCaml line editor
"ledit" which has this functionality too, but seeing as there is now 
version skew between CamlP4 and OCaml that may not work for you, as it 
uses the Righteous syntax.

BTW, I'd also like OCaml to be faster in general than C++ (and Fortran and 
hand coded assembler :-) but I don't buy the claim that 10% is significant 
for most applications. In general, OCaml is far faster than C++: to write 
and debug. Thats the reason I use a high level language. Debugging C++ is
no fun, especially those crazy error messages that heavy template usage 
seems to bring. 

-- Brian

Re: When functional languages can be accepted by industry?

[Michael Hohn]

>> ...
>>    From: Markus Mottl <mottl@miss.wu-wien.ac.at>
>>    Date: Thu, 20 Apr 2000 20:52:34 +0200 (MET DST)
>>    Cc: caml-list@inria.fr (OCAML)
>>    Content-Type: text/plain; charset=us-ascii
>>    Sender: Pierre.Weis@inria.fr
>> 
>>    > In another life I wrote lots of numerical linear algebra programs, and I 
>>    > find that a little overloading would make the code a lot nicer.
>> 
>>    I admit: I don't write this much numerical code so I don't have many
>>    opportunities to complain about missing operator overloading there...
>> ...

Overloading is not needed in caml:  remember that you can define your
own infix operators.  I have done this for a minimalistic complex
number type, using +: -: /: and *:  Since the first (or first 2)
characters determine both precedence and associativity, this works
well. 
This also avoids the mixed-arithmetic errors, such as 
     x = 1/2 * y
which in e.g. Python will always return 0, but give type errors in
caml (when x and y are not integers)

Cheers,
Michael

Re: When functional languages can be accepted by industry?

[Chris Tilt]

Ok, if I may please add my rambling thoughts. XL posted a reponse
from myself regarding our industrial success with CAML. In fact, I
am thrilled with the core language and user/supplier community.

With respect, my wish list is as such:

1. consistent expressiveness in .mli files as .ml files for functors
2. agreed upon/blessed modules (library?) format
3. work bench (IDE) tool

On 1, I was stumped until MM showed me a trick for using .ml files
as interface files with functors. However, it is tricky and difficult
to document. I understand that there are problems with functors over
interfaces, but I emplore the authors to find a compromise. This would
facilitate larger projects and code reuse.

On 2, the included note describes this problem very well. I will please
request that we adopt some standard; I will happily code to it and share
my miserable functorized graph theory module.

On 3, I have always used emacs. It is great for one developer. However,
we are also spoiled by Visual Age for Java (from IBM), which uses the
old
Envy database from SmallTalkV and is brilliant. We love this IDE because
it supports excellent team programming. I can not (sadly) convince
others
in my office to use emacs on their WinNT/Win2000 computers. I understand
their position. Also, I know it is very difficult to produce an IDE for
a
language as a research work. It is not so interesting, but a lot of
work.
However, perhaps someone could develop a model of team development for
ML as a research project. VA for Java has a clear model that I think is
far superior to other Java tools. It is the OO development paradigm and
Envy that make it so powerful. There is probably such a model for our
functional languages (sorry if it's obvious and I just don't see it). I
will do whatever I can to support such development. Has there already
been
a thread of discussion on the topic of development model that I can
study?

Thank you all very much for this excellent language and discussion
group.

Best regards,
 Chris Tilt

John Prevost wrote:
> 
> >>>>> "mm" == Markus Mottl <mottl@miss.wu-wien.ac.at> writes:
> 
>     mm> There are certainly a few "social" technologies that could
>     mm> significantly boost the usability of OCaml in real-world
>     mm> projects, a good version management tool for third party
>     mm> sources probably ranking among the "most missing" ones.
>         {...}
>     mm> Taking a look at the Hump and Gerd's link database, I have the
>     mm> impression that there is already enough "critical mass" of
>     mm> contributors, but most of the contributions are
>     mm> "one-man-efforts", i.e. nice, but they don't have enough
>     mm> "punch". Maybe we should really think more about ways to
>     mm> "unleash the forces of cooperative development". As it seems:
>     mm> easily said, difficult to do...
> 
> I agree that this is the most significant "hump" in the way of O'Caml
> at the moment.  Whenever I become enthused about working on a major
> interesting project in O'Caml, I first start looking at what other
> people have done.  I go to the hump, and the link database.  There, I
> discover that I could perhaps reuse code from three other people.
> 
> But what's this?--one of them uses findlib, one of them has a Makefile
> they rolled by hand (which is broken), and one of them just gives you
> source code, no library at all.
> 
> So I sort of sit there and stare at these three useful libraries,
> thinking about how I can build my system/library in such a way that
> it'll work with all three, and...  it's just a mess.  I eventually
> sort of roll over and take a big sigh, then leave to do something
> else.
> 
> Needless to say, I don't get much code written.
> 
> Perl has it's problems, and the quality of modules varies
> immensely--but when I find a module, I can install it and try it out
> in about 20 seconds.  That lets me get on to the more important
> problems of writing code.
> 
> While this sort of thing might, by a number of arguments, not be the
> sort of thing that should be considered part of the "core language",
> I'd like to argue that such an official blessing would be enough to
> get people to start using the tools consistantly, rather than
> everybody doing things their own way.  And it's only when everybody's
> working in approximately the same way that this kind of simplicity of
> working with third-party modules becomes possible.
> 
> >>>>> "xl" == Xavier Leroy <Xavier.Leroy@inria.fr> writes:
> 
>     xl> In OCaml, you have excellent I/O (better than Java's in my
>     xl> opinion) in the standard library, TK and GTK bindings for
>     xl> GUIs, and a couple of bindings to existing database libraries
>     xl> (see the Caml hump at http://caml.inria.fr).  I agree the
>     xl> database stuff needs more work and the GUI stuff needs more
>     xl> documentation, but it's a start.
> 
> Mmm.  I actually have one minor gripe about the I/O stuff--not being
> able to turn a set of functions into an in_channel or out_channel has
> bit me a number of times.  It's not so bad, until you want to do
> something like implement an encrypting network stream and then use
> stuff from Printf to write to it.
> 
> (This could also simplify the code somewhat, since things like bprintf
> and sprintf could be written in terms of such a primitive.  This would
> probably lose some speed, though.)
> 
>     xl> I certainly can't disagree with you.  The main problem here is
>     xl> human resources.  But we are looking at ways for big
>     xl> industrial users to help fund that kind of developments.
> 
> I think that if you took something like, say, Findlib, and asked if
> you could integrate it into O'Caml, you'd discover at least a few
> people who would make time to go over things looking for issues and
> warts to clean up.  It's hard to be enthused if it's not going to be
> "official".
> 
> Even though I've been waiting for a good solution for consistent
> handling of third party modules almost as long as I've been using
> O'Caml, the fact that only a few people use findlib cuts down on its
> usefulness to me.  If Findlib were accepted into O'Caml, I would go
> out of my way to send findlibifying patches to authors of various
> packages, instead of just getting depressed.
> 
> John.

Re: Caml wish list

[Pierre Weis]

> Well, I can't remember offhand how SMJ/NJ handles overloading, but it
> seems to work reasonably well.  On the other hand, I am nowadays a
> convert to ocaml's hard line on overloading---it's an absolute curse
> of many, many C++ programs by coders whose enthusiasm outruns their
> judgement.

We think many Caml users feel that using different addition function
(+) and (+.) for integers and floats is a safe way of programming, but
really frustrating at the same time.

So do we. Therefore we are currently in the effort of adding some kind
of limited overloading to Caml. This is not a trivial problem, if you
want something really good both at the expressiveness and the
efficiency levels.

      *  *  * 

As you mentioned, SML provides a set of overloaded functions such as
(+), but it is quite limited. In addition, for the sake of efficiency
and simplicity of the typing and compilation schemes, the overloaded
functions in SML have a restricted ``functional'' status: you cannot
abstract pieces of code containing overloaded operators. Hence, you
cannot define derived overloaded functions using already existing
overloaded functions.

A simple example that novice SML users often encounter is the double
function using overloaded (+):

# let double = fun x -> x + x;;

In SML, this double function is not an overloaded function for
integers and floats, because the type of (+) must always be statically
deduced from the context, which is impossible here. This definition is
just either rejected (SML '90), or resolved using a default type
assignment for overloaded symbols (SML '97): then (+) is typed as its
default type int -> int -> int, and consequently double gets type int
-> int.

This way, the compiler always has the precise type of use for each
occurrence of (+). Therefore occurrences of (+) can be replaced by 
the corresponding primitives, for example:

        # 1 + 2            ====>   add_int 1 2
        # 1.0 + 2.0        ====>   add_float 1.0 2.0
        # fun x -> x + x   ====>   fun x -> add_int x x

Therefore overloaded functions are just "typeful macros" in SML.

We think this is one reasonable solution, since the users will feel
much less frustration than using the separated functions (+) and (+.),
and the compilation for these overloaded functions is straightforward
and has no run time overhead.

      *  *  * 

However, we are not promoting this simple overloading facility,
because we think the ``abstraction restriction'' to be unnatural in a
functional setting: even if the definition of new overloaded symbols
is prohibited, the abstraction over overloaded operators (as in double
above) should be possible in higher-order functional languages like
SML or Caml!

Our "extensional polymorphism" framework is a bit more complicated
than the ``default assigment'' static scheme, but it provides
abstraction and "real" overloaded functions. (By the way, we call
those "generic" functions.) Using extensional polymorphism, the double
function is polymorphic, being defined for ``any argument whose type
is suitable for (+)''. Thus, you can use it for integers and floats!

# let double = fun x -> x + x;;
val double : $a -> $a = <fun>

# double 1;;
- : int = 2 

# double 3.14;;
- : float = 6.28

We use special type variables $a, $b, ..., called dynamic type
variables, to denote type parameters abstracted into type schemes for
polymorphic generic functions. In the definition of double, the
context of (+) is left unresolved, and double becomes polymorphic. The
compilation of double abstracts the type context for the internal (+),
and dynamically passes it to (+) to select the appropriate addition
primitive.

You may worry about efficient compilation of this feature, since, as
examplify by the double generic function, some information from the
typing context has to be passed at run time, and hence double involves
an extra argument (a type) to be provided to (+) at run time, and also
an additional pattern matching selection to apply the proper addition
primitive; undoubtedly, the generic double function is a bit slower
than its direct non-overloaded counterpart definitions for integers
and floats, like

# let double_int x = x + x;;
# let double_float x = x +. x;;

However, writing those two definitions means twice more code, hence
twice more possibilities of bugs, twice more maintenance, and twice
more identifiers to remember. This simplification is worth a slight
efficiency loss ...

Note also that usual simple overloading of operators is still as
efficient as it can be, since static type annotations allow the
inlining of the corresponding primitives, at least for the predefined
set of usual arithmetic operators (+, -, *, ...).

Polymorphic uses of overloaded operators in generic functions need an
extra type book keeping for dynamic resolution, but there is no
possible efficiency comparison with other compilation schemes, since
these functions are completely new in ML and cannot be expressed
neither in SML nor in Caml.

As a side effect of the extensional polymorphism discipline, we
manipulate types at run time, and this provides various benefits and
new features to the lasnguage:

        * safe value I/O (persistent value I/O between different
          programs, or safe usage of input_value/output_value),
        * dynamic values,
        * some limited polymorphic print facility,
        * a new kind of computation mixing types and values ...

The current prototype is an extension of the 2.04 version of Objective
Caml; we are planning to release it when it will be fully stable, like
the label extension in 2.99. We don't know yet which version of
Objective Caml it will be 3.0, 3.x or 3.99...

Hope this helps,

Jun Furuse & Pierre Weis

reference initialization

[Hongwei Xi]

> Wrong. You have references, which are quite better than pointers
> (they are typed, and necessarily initialized)

I have given some thoughts on this one.

I find that it is really not a good design choice to initialize
every reference in all ML-like languages (yes, I well realize
the difficulty in not doing so). Here is my argument.

The common wisdom is that if we initialize every reference
immediately after it is created then we shall never read from
an uninitialized reference. But this is a lame argument.

Suppose I use a reference 'x'. If I know what the initial value
of 'x' should be, I'll of course prefer to initialize it with that
value. Now suppose I don't, that is, I intend to assign a value
to 'v' later (maybe in a loop or in a conditional branch)

(1) ML strategy: initialize x with any value 'v' of an appropriate
type (sometimes, such a 'v' is difficult to find or takes time to
construct (consider 'x' to be a large array)).

Now suppose I make a mistake, forgetting to assign a value to 'x'
later. What happens is that the computation now happily use the
*wrong* initial value and sings the song "well-typed-program-can-
never-go-wrong" until a (most likely) wrong answer or exception is
returned.

(2) Java Strategy: let us say we have the same scenario as before
but 'x' is not initialized. If I read from x before assigning a value
to 'x', the execution abnormally stops (yes, we need run-time checking).
I think this is much better than to carry the execution further until a
wrong answer or exception is returned.

Can you still say that the ML strategy is better than the Java
strategy? I thus argue that it is better using dynamic checking
to detect reading from uninitialized reference than simply
assigning a value to every reference upon its creation.

To summarize, my bottom line question is: what is really achieved
by assigning a reference a (wrong) initial value? Isn't this just
like an ostrich solving its problem by burying its head in sand?

Of course, another problem with the ML strategy is efficiency loss
(which, though, is often negligible as discussed here before)

--Hongwei Xi

\~~~~/ \\   //  \\    //    @       Mail: hwxi@ececs.uc.edu
C-o^o,  ))__||   \\__//_  // \\     Url: http://www.ececs.uc.edu/~hwxi
(  ^ )  ))__||    \--/-\\     \\    
/ \V\   ))  ||     //   \\     \\   Tel: +1 513 556 4762 (office)
------ //   || o  //     \\     \\//Fax: +1 513 556 7326 (department)

Re: reference initialization

[Pierre Weis]

> I find that it is really not a good design choice to initialize
> every reference in all ML-like languages (yes, I well realize
> the difficulty in not doing so). Here is my argument.
[...]

> (1) ML strategy: initialize x with any value 'v' of an appropriate
[...]

> (2) Java Strategy: let us say we have the same scenario as before
> but 'x' is not initialized. If I read from x before assigning a value
[...]

> Can you still say that the ML strategy is better than the Java
> strategy?

Yes, I can.

> I thus argue that it is better using dynamic checking
> to detect reading from uninitialized reference than simply
> assigning a value to every reference upon its creation.
> 
> To summarize, my bottom line question is: what is really achieved
> by assigning a reference a (wrong) initial value? Isn't this just
> like an ostrich solving its problem by burying its head in sand?
> 
> Of course, another problem with the ML strategy is efficiency loss
> (which, though, is often negligible as discussed here before)

The ML style is better, since the default regime is to initialize
references and in most cases, you perfectly know the correct
initialization value at creation time.

For the few remaining cases, where you cannot guess the initial value,
then you must use another scheme that indeed involves dynamic testing;
I will not consider initialization with ``any value 'v' of an
appropriate type'' as a receivable solution, since this ``solution''
is far too error prone (as you had already mentioned).

Another well-known trick to initialize references is to use
options. At creation time you define the reference as being ``ref
None'', and later assign it to ``Some v'', when v can be computed.

Then in your program you have to pattern match the contents of the
reference to get its value, and raise an exception if necessary,
getting the Java semantics.

To elegantly handle this new scheme, you may even write a new
dereferencing prefix operator:

let ( !! ) r =
 match !r with
 | None -> invalid_arg "not yet initialized"
 | Some v -> v;;

Then you just substitute !!r to !r into your program.

One step further is to aly define a new assignment operator to hide the
``Some'' manipulations:

let ( =: ) r v = r := Some v;; 

Now, for instance:

let r = ref None;;

r =: 1;;

r =: 2 + !!r;;

This way, the ``cannot initialize my reference at creation time''
problem, is somewhat solved, but still evident in your code (and this
is a good property, since there is a real difficulty in your source
code, that can raise an exception when accessing the ``r'' reference).

Conclusion: I prefer the ML style, which elegantly solves the common
case and let you encode fairly simply the hairy cases. The efficiency
loss problem deceives the same remark and the same solution: there is
no loss in the most common case (in that case you know what is the
initial value and have to compute it anyway), and in the hairy cases
you can use the None/Some trick, an this hairy case is evident in the
source code.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: reference initialization

[John Prevost]

>>>>> "hx" == Hongwei Xi <hwxi@ececs.uc.edu> writes:

    hx> I have given some thoughts on this one.

    hx> I find that it is really not a good design choice to
    hx> initialize every reference in all ML-like languages (yes, I
    hx> well realize the difficulty in not doing so). Here is my
    hx> argument.

The contrary argument is twofold.

First--if you want a reference which you may assign no initial value
to, you can use an option.  Certainly, this is yet another bit of
overhead.  (But the good thing is that unlike in Java, you have the
choice to always receive a not-null value, and therefore you don't
have to check all the time!)

Second--as for uninitialized values and loops and the like: try to
find a better way to do it.  I don't remember the last time I had to
use a reference in a loop to get what I wanted.  I hardly remember the
last time I used a reference.

Another reason to prefer this second approach (especially in a loop)
is that O'Caml's GC mechanism implies that destructive updates of heap
values are slower than variable changes, so the tail-recursive loop:

let test l =
  let rec loop n = function 
    | [] -> n
    | _ :: t -> loop (n + 1) t
  in loop 0 l

is more efficient than:

let test l =
  let l' = ref l in
  let n = ref 0 in

 let n = ref 0 in
  while !l' <> [] do
    incr n;
    l' := List.tl l'
  done;
  !n

even if you ignore the cost of repeatedly dereferencing--just because
of the cost of updating.  IMO, it's easier to read, too, though you
need to be used to the idiom.

Note that a loop like "for i = 1 to n" is as efficient (or more so,
possibly, I don't remember) as the equivalent tail recursive loop.
Why?  Because like the tail recursive call, all updates are temporary
storage in the stack, not values in the heap.


I have not seen the message you are replying to, so I don't know if it
addresses your specific concerns--but it might, I hope, clarify
something about ML style type systems that I find very important: the
ability to *choose* what features a variable has.  (Optional value,
mutable value) rather than always having to deal with optional mutable
values.

John.

Re: reference initialization

[Hongwei Xi]

Okay, I withdraw my argument that the Java strategy is better then
the ML strategy However, I'd like to use the following example
to make my point clear.

I want to combine two arrays into one. Here is the code in OCaml.

let combine_arrays a b =
  let alen = Array.length a in
  let blen = Array.length b in
  let c = Array.make (alen + blen) ?
  in begin
    for i = 0 to alen - 1 do
      c.(i) <- a.(i)
    done;
    for i = 0 to blen -1 do
      c.(alen + i) <- b.(i)
    done
  end

Of course, you need to provide ? to make the above code work.
Here is my argument:

(1) If you try to provide ?, the code becomes repulsive.
(2) If you really want to make sure that 'c' is well-initialized,
you should probably check this after those two loops. The question
is how to incorporate the checking result into the type system.
(3) If you initialize 'c' with a (wrong) value, it seems to me
that nothing is achieved.
(4) Also, the problem cannot be solved using option type.

This is a precise senario that I had in mind, where the kind of
mandatory array initialization in ML-like langugages is simply
inappropriate, isn't it?

Cheers,

--Hongwei

\~~~~/ \\   //  \\    //    @       Mail: hwxi@ececs.uc.edu
C-o^o,  ))__||   \\__//_  // \\     Url: http://www.ececs.uc.edu/~hwxi
(  ^ )  ))__||    \--/-\\     \\    
/ \V\   ))  ||     //   \\     \\   Tel: +1 513 556 4762 (office)
------ //   || o  //     \\     \\//Fax: +1 513 556 7326 (department)
 

Re: reference initialization

[Pierre Weis]

> Okay, I withdraw my argument that the Java strategy is better then
> the ML strategy However, I'd like to use the following example
> to make my point clear.
> 
> I want to combine two arrays into one. Here is the code in OCaml.
> 
> let combine_arrays a b =
>   let alen = Array.length a in
>   let blen = Array.length b in
>   let c = Array.make (alen + blen) ?
>   in begin
>     for i = 0 to alen - 1 do
>       c.(i) <- a.(i)
>     done;
>     for i = 0 to blen -1 do
>       c.(alen + i) <- b.(i)
>     done
>   end
> 
> Of course, you need to provide ? to make the above code work.
> Here is my argument:
> 
> (1) If you try to provide ?, the code becomes repulsive.

Not exactly, you just have to find one element into a. For instance:
 let alen = Array.length a in
 if alen = 0 then b (or Array.copy b if you need a fresh array) else
 let ? = a.(0) in
 let c = ...

  for i = 1 to alen - 1 do
   ...

> (2) If you really want to make sure that 'c' is well-initialized,
> you should probably check this after those two loops. The question
> is how to incorporate the checking result into the type system.
> (3) If you initialize 'c' with a (wrong) value, it seems to me
> that nothing is achieved.
> (4) Also, the problem cannot be solved using option type.
> 
> This is a precise senario that I had in mind, where the kind of
> mandatory array initialization in ML-like langugages is simply
> inappropriate, isn't it?

You should consider that there is a general initialisation function in
the Array module, named Array.init, that allocates for you a fresh
array then fill it with values obtained by calling an arbitrary
supplied function:

# Array.init;;
- : int -> f:(int -> 'a) -> 'a array = <fun>

Using it, you don't need to bother with any dummy initialization value:

let combine_arrays a b =
  let alen = Array.length a in
  let blen = Array.length b in
  let init i = if i < alen then a.(i) else b.(i) in
  Array.init (alen + blen) init

This code ensures the ``always initialized strategy'' of ML, and seems
to me elegant and clear (but note that it uses higher-order
functionality). Have I missed something ?

Best regards,

PS: An even shorter version of combine_arrays should be
    let combine_arrays = Array.append

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: reference initialization

[Hongwei Xi]

> Not exactly, you just have to find one element into a. For instance:
>  let alen = Array.length a in
>  if alen = 0 then b (or Array.copy b if you need a fresh array) else
>  let ? = a.(0) in
>  let c = ...
> 
>   for i = 1 to alen - 1 do
>    ...

But, why? Why should we first initialize c with such a value.
I don't think you have made a program safer by doing so.

> # Array.init;;
> - : int -> f:(int -> 'a) -> 'a array = <fun>
> 
> Using it, you don't need to bother with any dummy initialization value:
> 
> let combine_arrays a b =
>   let alen = Array.length a in
>   let blen = Array.length b in
>   let init i = if i < alen then a.(i) else b.(i-alen) in
>   Array.init (alen + blen) init

This is great in this case. But suppose that I want to compute
the combinatorial numbers 'n chooses k' for k= 0,..,n.

let chooses (n) =
  let result = Array.array (n+1) ? in begin
    result.(0) <- 1; result.(n) <- 1;
    for i = 1 to n/2 do
      result.(i) <- result.(i-1) * (n-i+1) / i;
      result.(n-i) <- result.(i);
    done;
    result
  end
(* code is not tested *)

Certainly, we can replace ? with 0. But what is really achieved?
I would say it is simply an illusion that a program is made safer
by initializing each array upon its allocation. Actually, a program
is likely made faster but unsafer by doing so (since no nullity
checking is needed but a wrong value may be supplied to continue
a computation that should be aborted)

Best,

--Hongwei

\~~~~/ \\   //  \\    //    @       Mail: hwxi@ececs.uc.edu
C-o^o,  ))__||   \\__//_  // \\     Url: http://www.ececs.uc.edu/~hwxi
(  ^ )  ))__||    \--/-\\     \\    Tel: +1 513 871 4947 (home)
/ \V\   ))  ||     //   \\     \\   Tel: +1 513 556 4762 (office)
------ //   || o  //     \\     \\//Fax: +1 513 556 7326 (department)
Rhodes Hall 811-D
Department of ECE & CS  
University of Cincinnati
P. O. Box 210030
Cincinnati, OH 45221-0030

On Fri, 12 May 2000, Pierre Weis wrote:

> 
> > (2) If you really want to make sure that 'c' is well-initialized,
> > you should probably check this after those two loops. The question
> > is how to incorporate the checking result into the type system.
> > (3) If you initialize 'c' with a (wrong) value, it seems to me
> > that nothing is achieved.
> > (4) Also, the problem cannot be solved using option type.
> > 
> > This is a precise senario that I had in mind, where the kind of
> > mandatory array initialization in ML-like langugages is simply
> > inappropriate, isn't it?
> 
> You should consider that there is a general initialisation function in
> the Array module, named Array.init, that allocates for you a fresh
> array then fill it with values obtained by calling an arbitrary
> supplied function:
> 
> 
> This code ensures the ``always initialized strategy'' of ML, and seems
> to me elegant and clear (but note that it uses higher-order
> functionality). Have I missed something ?
> 
> Best regards,
> 
> PS: An even shorter version of combine_arrays should be
>     let combine_arrays = Array.append
> 
> Pierre Weis
> 
> INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/
> 
> 

Re: reference initialization

[Daniel de Rauglaudre]

On Thu, May 11, 2000 at 02:59:16PM -0400, Hongwei Xi wrote:

> I want to combine two arrays into one. Here is the code in OCaml.
>  ...

Simple (library) solution:
=======================
let combine_arrays a b =
  let alen = Array.length a in
  let blen = Array.length b in
  Array.init (alen + blen)
    (fun i -> if i < alen then a.(i) else b.(i - alen))
=======================

Simple (custom) solution:
=======================
let combine_arrays a b =
  let alen = Array.length a in
  let blen = Array.length b in
  if alen = 0 && blen = 0 then [| |]
  else
    let c = Array.make (alen + blen) (if alen = 0 then b.(0) else a.(0)) in
    in begin
      for i = 0 to alen - 1 do
	c.(i) <- a.(i)
      done;
      for i = 0 to blen -1 do
	c.(alen + i) <- b.(i)
      done
    end
=======================

Dirty solution (don't tell them I told you):
=======================
let combine_arrays a b =
  let alen = Array.length a in
  let blen = Array.length b in
  let c = Array.make (alen + blen) (Obj.magic 0)
  in begin
    for i = 0 to alen - 1 do
      c.(i) <- a.(i)
    done;
    for i = 0 to blen -1 do
      c.(alen + i) <- b.(i)
    done
  end
=======================

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/

Re: reference initialization

[Daniel de Rauglaudre]

On Thu, May 11, 2000 at 02:59:16PM -0400, Hongwei Xi wrote:

> I want to combine two arrays into one. Here is the code in OCaml.
>...

Woops, I forgot another solution:

==========================
let combine_arrays = Array.append
==========================

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/

Re: reference initialization

[John Max Skaller]

Pierre Weis wrote:
 
> You should consider that there is a general initialisation function in
> the Array module, named Array.init, that allocates for you a fresh
> array then fill it with values obtained by calling an arbitrary
> supplied function:
> 
> # Array.init;;
> - : int -> f:(int -> 'a) -> 'a array = <fun>
> 
> Using it, you don't need to bother with any dummy initialization value:
> 
> let combine_arrays a b =
>   let alen = Array.length a in
>   let blen = Array.length b in
>   let init i = if i < alen then a.(i) else b.(i) in
>   Array.init (alen + blen) init
> 
> This code ensures the ``always initialized strategy'' of ML, and seems
> to me elegant and clear (but note that it uses higher-order
> functionality). Have I missed something ?

I think so: the init function is a callback; code which
'naturally' initialises an array by storing into it needs
to be 'control inverted': in general this is very hard,
if not impossible, to do by hand. The general case requires
the client to write an 'interpreter' for the initialisation
algorithm, maintaining state in the callback's closure.

If we consider a simple initialisation like:

	for i=0 to n-1 do x.(i) <- i done

the control inverse is

	fun i -> i

which is simple. However, for more complex algorithms,
such as a sort, this seems non-trivial. For example,
the naive functional solution to fibonacci:

	let rec fib i = match i with 
		| 0 | 1 -> 1 
		| _ -> fib (i-1) + fib (i-2)

works, but is unacceptably inefficient. The actual control
inverse of the usual procedural array initialisation algorithm,
which keeps track of the last two fibonacci numbers, requires
a wrapper function to create the storage in a closure:

	let fib_creator () =
		let a = ref 1 and b = ref 1 in
		let fib i = (* ignore the i *)
			let result = !a + !b in
			b := !a; a := result;
			result
		in fib

Here, fib_creator is a lazy data structure, and fib an iterator
over it. A 'purer' solution could be constructed
using streams I think.

I have written a tool which performs control inversion mechanically,
although in a different context (procedural code 'reading' messages
is control inverted to be event driven). There is some sort of
deep duality theorem here.

But I think the effect is: code which is easy to write procedurally
must be converted to use continuation passing, and that isn't
a trivial task.

[On the other hand, it is usually easy to write a dispatcher for
callback driven code, provided it is the control inverse of
a single thread of control]

So I think you are missing something: iter provides a reasonable
solution for only 'half' of those problems where the callback
driven style is 'natural'. In ocaml, the only way I'm aware of
to encode continuations 'naturally' requires using (hardware
or bytecode) threads.

[BTW: if we had this duality theorem, we would know how to
mix functional and stateful code in the same language seamlessly:
it would seem Charity offers some hints here]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: reference initialization

[Max Skaller]

Hongwei Xi wrote:

> Certainly, we can replace ? with 0. But what is really achieved?
> I would say it is simply an illusion that a program is made safer
> by initializing each array upon its allocation. 

What's happening here is this: ocaml is basically a _functional_
programming language. In such a language there is no such thing
as a variable, _everything_ is a constant. In this view,
the notion that there can be an uninitialised variable
is absurd, since there are no variables!

This is not the case for procedural programming, IHMO.
But the framework of ocaml is functional first, with
adaptions for procedural programming. In particular,
because of the way the underlying run-time system works,
uninitialised pointers would cause the garbage collector to core dump.
(and almost all ocaml values are represented by pointers).


-- 
John (Max) Skaller at OTT [Open Telecommications Ltd]
mailto:maxs@in.ot.com.au      -- at work
mailto:skaller@maxtal.com.au  -- at home

Re: reference initialization

[Hongwei Xi]

On Mon, 15 May 2000, Max Skaller wrote:

> Hongwei Xi wrote:
> 
> > Certainly, we can replace ? with 0. But what is really achieved?
> > I would say it is simply an illusion that a program is made safer
> > by initializing each array upon its allocation. 
> 
> What's happening here is this: ocaml is basically a _functional_
> programming language. In such a language there is no such thing
> as a variable, _everything_ is a constant. In this view,
> the notion that there can be an uninitialised variable
> is absurd, since there are no variables!

It is not absurd. You may think an uninitialized value having
type (exists alpha.alpha), or type 'top' by making every type a
subtype of 'top'.

--Hongwei

Re: reference initialization

[Max Skaller]

Pierre Weis wrote:
 
> So, adding a test to detect this case we can initialize the vector
> properly, without using Obj.magic.
> 
> exception Not_yet_initialized of int;;
> exception Already_initialized of int;;
> exception Never_initialized of int;;
> 
> let initialize n f =
>  if n = 0 then [||] else
>  let init_v = Array.make n false in
>  let v = ref [||] in
>  let get i = if init_v.(i) then !v.(i) else raise (Not_yet_initialized i) in
>  let set i ei =
>    if !v = [||] then v := Array.make n ei;

Hmmm. This should work, even if 'ei' has a finaliser or mutable
field: 'ei' isn't a 'dummy' value, but a real value that the client
wanted in the array. On the other hand, a dummy value the client
is forced to supply may have dire consequences where the type
is either a class instance , or finalised: here
either construction or destruction may have arbitrary
semantics.

So this (the code you gave) is much better than having to supply a dummy
value.

The same problem occurs with 'forced' variable initialisation:
dummy values may have unwanted side-effects.
There is a tension here, since ocaml is not a purely
functional language.

-- 
John (Max) Skaller at OTT [Open Telecommications Ltd]
mailto:maxs@in.ot.com.au      -- at work
mailto:skaller@maxtal.com.au  -- at home

Re: reference initialization

[Pierre Weis]

> So array takes an uppper and lower bound, and a list of (index,value) pairs;
> it returns an array with each element filled in.  The list should mention
> each element just once, but that is not statically checked.
> 
> In conjunction with list comprehensions, this gives rise to quite nice code.
> For example, to tabulate a function we might write
> 
> 	array (1,n) [(i, f i) | i <- [1..n]]
> 
> Referring to existing elements is easy via recursion:
> 
> 	fibs = arrray (1,n) ([(1,1),(2,1)] ++
> 			       [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])
> 
> Notice how easily the boundary cases are specified.
> 
> Laziness means that the compiler does not need to figure out which
> order to do the initialisation. In a strict language it would be a little
> harder -- or perhaps one could say "it's done in the order the index,value
> pairs are given".

This would be perfectly reasonable.

> You may wonder about the efficiency issue.  After all, it doesn't seem
> great to build an intermediate list just before constructing an array.
> But a bit of short-cut deforestation does the trick, and eliminates the
> intermediate list.  I have to admit that a lot of things have to Work Right
> in the compiler to really get the for-loop you intended, but that's what
> compilers are for.

Wao! You've got a really impressive compiler.

> None of this is specific to Haskell or to a lazy language.  Caml could
> well use it.  I mention it on this list becuase it's an aspect of the
> Haskell design that I think has worked particularly well, and which 
> might be of use to Camlers.

Oups. I frankly doubt that we can define in Caml something like your fibs:

fibs =
 arrray (1,n) ([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])

Don't forget our evaluation regime that will try to completely
evaluate the list

([(1,1),(2,1)] ++ [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])

before calling the array creation function. What's the meaning of
fibs! then, since fibs has no existance yet ?

I think that in these examples, lazy evaluation is important: the list
is lazyly evaluated, and the fibs array elements are assigned one at a
time, as soon as the corresponding pair of the list has been computed.

As far as I can imagine the way vectors are handled in a lazy
language, the compiler must ``initialize'' vectors elements with a
dummy ``undefined value'', and updates this dummy value as usual as
soon as a value is provided for the dummy.

This way you always have the ``not yet initialized'' test for free,
since attempts to access such an element will raise some ``bottom'' or
``undefined'' exception. However, for the ``completely initialized
test'' you also need to access all the elements of the new vector
(once more accessing an undefined element will automatically raise an
exception). And I suspect also that the ``initialized only once'' check
will be tricky... (or similar to an ML solution).

So, I don't know how to implement your elegant solution in a strict
language (unless by adding some lazy evaluation regime for some
functions, such as ... array!)

> A lot of the benefit comes from the re-use (for arrays) of the 
> list comprehension notation.  I forget whether Caml has such notation,
> but again, it's nothing to do with laziness and it's a notation which
> is really useful.

Yes this is really a interesting notation. However, I studied it once,
and as far as I remember I had the feeling that lazy evaluation was
also mandatory to handle ``real'' cases other than the trivial ones (such
as. [(i, f i) | i <- [1..n]] that can be easily done in Caml): complex
mutually recursive lists, where f and the bounds where functions of
other lists given in comprehension.

Also, I remember my strange feeling at reading pieces of code like:

 [i | i <- [1..2**32]]

which is not completely reasonable in a strict language.

Anyway, you're right that we could may give it a try ...

Thank you for your interesting remarks.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: reference initialization

[Pierre Weis]

> Pierre Weis wrote:
> > 
> > Finally I think I've done the ``Further work part'' I mentioned for
> > vector initialization!
> 
> > let initialize n x0 f =
> 
> x0 is both a problem and unnecesary: it is hard to pick
> a sensible x0 sometimes, and it is not necessary, since
> Obj.magic can be used internally: there is no loss of
> safety, since the code checks all usage, and such a magic
> value cannot be accessed.
>
> John (Max) Skaller at OTT [Open Telecommications Ltd]
> mailto:maxs@in.ot.com.au      -- at work
> mailto:skaller@maxtal.com.au  -- at home

You're right, getting rid of this x0 would be better. Still, I don't
understand how you can manage to write the f function if you cannot
figure out at least one random value of the type of the elements of
the vector you want f to initialize. Also, I don't like to use Obj.magic
to create an heterogeneous vector, even if I can prove that no Caml
program can observe it: it breaks some invariants that the runtime
system, the memory manager, or the debugger could observe.

However, since we know that the function f gives plenty of suitable initial
values: in particular at the first call to the set function.

So, adding a test to detect this case we can initialize the vector
properly, without using Obj.magic.

exception Not_yet_initialized of int;;
exception Already_initialized of int;;
exception Never_initialized of int;;

let initialize n f =
 if n = 0 then [||] else
 let init_v = Array.make n false in
 let v = ref [||] in
 let get i = if init_v.(i) then !v.(i) else raise (Not_yet_initialized i) in
 let set i ei =
   if !v = [||] then v := Array.make n ei;
   if not init_v.(i) then (!v.(i) <- ei; init_v.(i) <- true) else
   raise (Already_initialized i) in
 (f get set : unit);
 for i = 0 to n - 1 do if not init_v.(i) then raise (Never_initialized i) done;
 !v;;

(*
val initialize :
 int -> ((int -> 'a) -> (int -> 'a -> unit) -> unit) -> 'a array
 [initialize n f] returns a fresh array of length [n],
 with elements initialized by function [f].
 All the elements of the new array must be assigned once and only
 once by the function [f]. [f] received two functions as arguments,
 one to access elements of the new array, and the other to set the
 elements of the new array. [f] can access to element [i] of the new
 array provided [f] has already properly initialized element [i].
 Raise [Not_yet_initialized i] if element [i] is accessed before being
 assigned.
 Raise [Already_initialized i] if element [i] is assigned twice.
 Raise [Never_initialized i] if element [i] has never been assigned at
 the end of initialization.
 [Array.initialize n f] uses [2 n] words of heap space.
*)

Thanks for your simulating remark.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

RE: reference initialization

[Simon Peyton-Jones]

| val initialize :
|  int -> 'a -> ((int -> 'a) -> (int -> 'a -> unit) -> unit) -> 'a array
|  [initialize n x f] returns a fresh array of length [n],
|  with elements initialized by function [f].
|  All the elements of the new array must be assigned once and only
|  once by the function [f]. [f] received two functions as arguments,
|  one to access elements of the new array, and the other to set the
|  elements of the new array. [f] can access to element [i] of the new
|  array provided [f] has already properly initialized element [i].

This is all good stuff.  It might be worth mentioning Haskell's approach
in this context.  The main array former is

	array :: Ix ix => (ix,ix) -> [(ix,elt)] -> Array ix elt

'array' takes an upper and lower bound, both of type 'ix'.  ix is a type
variable that must be bound to a type in class Ix, which supports indexing
operations.  So that I can avoid discussion of type classes, let's
specialise
array much as 'initialize' is above, to vectors indexed by Ints:

	array :: (Int,Int) -> [(Int,elt)] -> Array Int elt

So array takes an uppper and lower bound, and a list of (index,value) pairs;
it returns an array with each element filled in.  The list should mention
each element just once, but that is not statically checked.

In conjunction with list comprehensions, this gives rise to quite nice code.
For example, to tabulate a function we might write

	array (1,n) [(i, f i) | i <- [1..n]]

Referring to existing elements is easy via recursion:

	fibs = arrray (1,n) ([(1,1),(2,1)] ++
			       [(i, fibs!(i-1) + fibs!(i-2)) | i <- [3..n]])

Notice how easily the boundary cases are specified.

Laziness means that the compiler does not need to figure out which
order to do the initialisation. In a strict language it would be a little
harder -- or perhaps one could say "it's done in the order the index,value
pairs are given".


You may wonder about the efficiency issue.  After all, it doesn't seem
great to build an intermediate list just before constructing an array.
But a bit of short-cut deforestation does the trick, and eliminates the
intermediate list.  I have to admit that a lot of things have to Work Right
in the compiler to really get the for-loop you intended, but that's what
compilers are for.


None of this is specific to Haskell or to a lazy language.  Caml could
well use it.  I mention it on this list becuase it's an aspect of the
Haskell design that I think has worked particularly well, and which 
might be of use to Camlers.

A lot of the benefit comes from the re-use (for arrays) of the 
list comprehension notation.  I forget whether Caml has such notation,
but again, it's nothing to do with laziness and it's a notation which
is really useful.

Simon

Re: reference initialization

[Max Skaller]

Pierre Weis wrote:
> 
> Finally I think I've done the ``Further work part'' I mentioned for
> vector initialization!

> let initialize n x0 f =

x0 is both a problem and unnecesary: it is hard to pick
a sensible x0 sometimes, and it is not necessary, since
Obj.magic can be used internally: there is no loss of
safety, since the code checks all usage, and such a magic
value cannot be accessed.


-- 
John (Max) Skaller at OTT [Open Telecommications Ltd]
mailto:maxs@in.ot.com.au      -- at work
mailto:skaller@maxtal.com.au  -- at home

Re: reference initialization

[Pierre Weis]

Finally I think I've done the ``Further work part'' I mentioned for
vector initialization!

We end up with a new initialization function for arrays that ensures
the proper and unique initialisation of each element of the array, but
is simpler to use and understand:

(*
val initialize :
 int -> 'a -> ((int -> 'a) -> (int -> 'a -> unit) -> unit) -> 'a array
 [initialize n x f] returns a fresh array of length [n],
 with elements initialized by function [f].
 All the elements of the new array must be assigned once and only
 once by the function [f]. [f] received two functions as arguments,
 one to access elements of the new array, and the other to set the
 elements of the new array. [f] can access to element [i] of the new
 array provided [f] has already properly initialized element [i].
 Raise [Not_yet_initialized i] if element [i] is accessed before being
 assigned.
 Raise [Already_initialized i] if element [i] is assigned twice.
 Raise [Never_initialized i] if element [i] has never been assigned at
 the end of initialization.
 [Array.initialize n x f] uses [2 n] words of heap space.
*)
exception Not_yet_initialized of int;;
exception Already_initialized of int;;
exception Never_initialized of int;;

let initialize n x0 f =
 if n = 0 then [||] else
 let init_v = Array.make n false in
 let v = Array.make n x0 in
 let get i = if init_v.(i) then v.(i) else raise (Not_yet_initialized i) in
 let set i ei =
   if not init_v.(i) then (v.(i) <- ei; init_v.(i) <- true) else
   raise (Already_initialized i) in
 (f get set : unit);
 for i = 0 to n - 1 do if not init_v.(i) then raise (Never_initialized i) done;
 v;;

The examples can now be written more naturally, with a minimum of
modification (beside correction of original bugs in chooses) :

let fibs n =
 let init_fibs get set =
   set 0 1; set 1 1;
   for i = 2 to n - 1 do
    set i (get (i - 1) + get (i - 2))
   done in
 initialize n 0 init_fibs;;

let chooses n =
 let init_chooses get set =
  let set_ei i ei =
    set i ei;
    if n - i <> i then set (n - i) ei in
  set_ei 0 1;
  for i = 1 to n / 2 do
   set_ei i (get (i - 1) * (n - i + 1) / i)
  done in
 initialize (n + 1) 0 init_chooses;;

let invs f n =
 let init_inv get set =
  for i = 0 to n - 1 do set (f i) i done in
 initialize n 0 init_inv;;

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: reference initialization

[Hongwei Xi]

> When you need more complex initializations, then you need a smarter
> version of Array.init (still you want to keep the same good properties
> as the simple version).
> 
> For instance, a simple generalization of Array.init, that allows
> access to the locations that are already initialized into the array,
> could be written as:
> 
>   exception Uninitialized_access of int;;
> 
>   let initialize f n =
>    if n = 0 then [||] else
>    let get v i j =
>     if j < i && j >= 0 then v.(j) else raise (Uninitialized_access j) in
>    let v = Array.make n (f (get [||] 0) 0) in
>    for i = 1 to n - 1 do
>     v.(i) <- f (get v i) i
>    done;
>    v;;
> 
> Using initialize, we can easily define a vector containing the
> fibonacci numbers:
> 
>   let init_fib g = function
>     | 0 | 1 -> 1
>     | n -> g (n - 1) + g (n - 2);;
> 
>   let fib10 = initialize init_fib 10;;
>   val fib10 : int array = [|1; 1; 2; 3; 5; 8; 13; 21; 34; 55|]

This looks pretty neat to me. Probably 'initialize' can be implemented
in C so that we can squeeze out some extra efficiency.

> Initialize provides the following properties:
> 
> If v is defined as ``let v = Array.initialize f n'' then
> 
>   1) v is completely initialized:
>      for all i, v.(i) has been assigned exactly once during the
>      initialization of v
>   2) not yet initialized locations in v are never accessed during the
>      initialization process:
>      for all i, for all j, if j > i then the location j is not accessed during
>      the initialization of v.(i)
>   3) elements of v are values computed by f:
>      for all i, v.(i) = f (fun i -> (Array.sub v 0 (i - 1)).(i)) (i)
> 
>   Once more there is no need to dynamically check accesses to a vector
>   initialized unsing the function initialize.

Yes, I thought along very much the same line.

> 3) New random_initialize function for ``random'' initialization
> ----------------------------------------------------------------
> 
> Now, you can still argue that you have even more complex
> initialisation schemes: then you need to define a more complex
> initialization function. For instance:
> 
> [random_initialize f i0 n] returns a vector [v] of length [n],
> initialized using the function [f], starting from index [i0]. The
> function [f] takes two arguments, an access function [g : int -> 'a]
> that gives access to already initialized elements of the vector [v],
> and an index [i]; given those arguments [f] returns a pair [next, a],
> where [a] is the value to be stored at index [i] of vector [v], and
> [next] the index of the next element of [v] to initialize. [f] should
> raise the predefined exception [Exit] to mean that index [i] is out of
> range, presumably at the end of initialization.
> 
> The following properties hold:
> 
> If v is defined as ``let v = random_initialize f i0 n'' then
> 
>   1) v is completely initialized:
>      for all i, v.(i) has been assigned exactly once during the
>      initialization of v
>   2) not yet initialized locations in v are never accessed during the
>      initialization process:
>      for all i, for all j, if v.(j) has not yet been assigned then the
>      location j is not accessed during the initialization of v.(i)
>   3) all elements of v are values computed by calls to f.
> 
> Implementation
> 
>   (* Already_initialized is raised when there is an attempt to
>      initialize an array location more than once. *)
>   exception Already_initialized of int;;
> 
>   (* Partial_initialization is raised when there is a location that is
>      not initialized at the end of initilization. *)
>   exception Partial_initialization of int;;
> 
>   let random_initialize f i0 n =
>    if n = 0 then [||] else
>    let initialized = Array.make n 0 in
>    let set v i a =
>     if initialized.(i) = 0 then (initialized.(i) <- 1; v.(i) <- a)
>     else raise (Already_initialized i) in
>    let get v j =
>     if j >= 0 && j < n && initialized.(j) = 1 then v.(j)
>     else raise (Uninitialized_access j) in
>    let nexti0, a0 = f (get [||]) i0 in
>    let v = Array.make n a0 in
>    set v 0 a0;
>    let rec init i =
>     let nexti, ai = f (get v) i in
>     set v i ai;
>     init nexti in
>    try init nexti0 with
>    | Exit ->
>       for i = 0 to n - 1 do
>        if initialized.(i) = 0 then raise (Partial_initialization i)
>       done;
>       Array.init n (fun i -> v.(i));;
>
> Example: we can define a suitable initialization function for your
> example of combinatorial numbers,
> 
>   let init_chooses n get i =
>    let next i j = if j <> i then j else n + 1 in
>    let ai i = get (i - 1) * (n - i + 1) / i in
>    if i = 0 then (next 0 n, 1) else
>    if i = n then (next n 1, 1) else
>    if i > n then raise Exit else 
>    if i <= n / 2 then (next i (n - i), ai i)
>    else (next i (n - i + 1), get (n - i));;
> 
>   let chooses n = random_initialize (init_chooses n) 0 (n + 1);;
> 
>   let v4 = chooses 4;;
>   val v4 : int array = [|1; 4; 6; 4; 1|]

I don't know about this. It seems a bit too involved to me
(at this moment)

> 4) Further work
> ---------------
> 
> The general vector initialization function should probably take as
> argument f a function that uses 2 functions get and set to handle the
> initialized vector. In any case, the properties 1, 2, and 3 should
> still hold.
> 
> 5) Conclusion
> -------------
> 
> I'm not sure we need a complex additional machinery to solve a problem
> that can be elegantly solved with some library functions (admittedly
> at the price of some linear additional cost at initialization time);

Me neither (at this moment).

> however, following Xavier, I would also be glad to read articles on
> dependant type systems and their applications to vector initialisation
> (if any);

Sorry. I don't have any paper on this subject :-)

> also, I would be delighted to try such an experimental type
> system, if it is tractable in practice (I mean, we don't want a type
> system that obliges the programmer to rewrite his pattern matchings in
> a strange and awful maneer, nor a type system that emits error
> messages that are incredibly more difficult to understand than those
> of usual ML typecheckers, nor a type system that is so slow that
> modern machines are turned into good old Apple IIs, don't we ?).

These are very legitimate points. The design of DML actually
addresses all these points in certain ways as our goal is also
towards having a practical programming system.

> I mean, we don't want a type system that obliges the programmer to
> rewrite his pattern matchings in a strange and awful maneer

The problem here is that unlike ML, sequentiality of pattern
matching must be taken into consideration in DML, but this can
be done automatically using Laville's approach (with some
modification).

> type system that emits error messages that are incredibly more
> difficult to understand than those of usual ML typecheckers

I find that in practice, the location of a type error in a DML
program is reported very accurately (mainly because that the user
has to provide dependent type annotations). Unless one uses the
type system to encode sophisticated information, the error messages
are not so hard to understand. Of course, one needs to gain some
exprience first but this is the same thing with ML.

> nor a type system that is so slow that modern machines are turned
> into good old Apple IIs, don't we ?).

Yes, type-checking can be slow, but this is also the case in ML.
I recently used Okasaki's parsing combinators to implement
parsers; I noticed that ML type-checking in this case is
indeed much slower (because larger higher-order types are involved)
than average cases.

A strong point of DML is its compatibility with ML. If you don't
use dependent types, you won't pay the price (no type-checking
slowdown). One can essentially just build a front-end. For OCaml,
one may simply first try whether it is effective to eliminate run-
time array bound checks; if it is good, further work can be done to
support dependent refinement types; if it is not, then it is nothing
more than a front-end. We need to make *no* changes to OCaml's backend!

> also, I would be delighted to try such an experimental type system

I would be happy to write such a front-end for OCaml, but I have
some serious difficulties:

(1) I am no expert of the OCaml front-end and often have
serious difficulty figuring out the code, which is neat but
has almost none comments.

(2) The syntax for OCaml is evolving so fast recently; this makes
it too difficult for me to support such a front-end even if it is
written.

If these problems can be addressed, such a front-end can be
quickly constructed (my estimate: no more than 3 person * months
work).

Best Regards,

--Hongwei

Re: reference initialization

[Dave Mason]

>>>>> On Mon, 15 May 2000 13:47:15 -0400 (EDT), Hongwei  Xi <hwxi@ECECS.UC.EDU> said:


> What I had in mind is actually something pretty simple (since it
> won't be very useful if it is not simple :-))

> Is it possible to have something like the following in the library:

I propose something more like:

    Array.init_with_array: int -> (int -> (int -> 'a) -> 'a) -> 'a Array

let Array.init_with_array n f =
  let a = Array.create n in
    for i = 0 to n - 1 do
      a.(i) <- f i (fun j -> if j<i then
                                a.(i)
                             else raise ``initialization error'')
    done

The second parameter could instead be a version of the array but with
the bound limited to 0..i, but this would allow the function f to save
that version somewhere which might not be good.

This would solve an additional subset of the cases... but is NOT a
complete solution (personally, I'm fine with the initial value).

../Dave

Re: reference initialization

[Pierre Weis]

I think you're right to consider proper initialization of vectors as a
desirable property.

I also agree with you that initializing a vector with a dummy value is
not a good practice and not an acceptable solution. However, the
Java's way of testing further accesses to elements of vectors does not
seem to be more appealing, since it does not ensure proper
initialization of vectors, and thus spurious exceptions, due to access
into improperly initialized vectors, can occur at anytime after the
creation of the faulty vector.

The Caml way to handle this kind of problems is to provide automatic
means to ensure maximum safety, in this case we must warranty proper
initialization of vectors. I introduced Array.init to address this
issue; however, as we already know, Array.init has some limitations;
in the following, I propose other initialization functions to overcome these
limitations, while still providing safety of vector initializations.

1) Array.init
-------------

Array.init is simple to use and convenient for simple initializations
(when the value to assign to location i can be expressed as a function
of i). Safety is provided by properties automatically ensured by
Array.init, such as:

If v is defined as ``let v = Array.init f n'' then

  1) v is completely initialized:
     for all i, v.(i) has been assigned exactly once during the
     initialization of v 
  2) elements of v are values computed by f:
     for all i, v.(i) = f (i)

  In addition, if v is defined with Array.init there is no need to
  perform runtime tests when accessing items inside vector v: v is
  properly initialized.

2) New initialize function
--------------------------

When you need more complex initializations, then you need a smarter
version of Array.init (still you want to keep the same good properties
as the simple version).

For instance, a simple generalization of Array.init, that allows
access to the locations that are already initialized into the array,
could be written as:

  exception Uninitialized_access of int;;

  let initialize f n =
   if n = 0 then [||] else
   let get v i j =
    if j < i && j >= 0 then v.(j) else raise (Uninitialized_access j) in
   let v = Array.make n (f (get [||] 0) 0) in
   for i = 1 to n - 1 do
    v.(i) <- f (get v i) i
   done;
   v;;

Using initialize, we can easily define a vector containing the
fibonacci numbers:

  let init_fib g = function
    | 0 | 1 -> 1
    | n -> g (n - 1) + g (n - 2);;

  let fib10 = initialize init_fib 10;;
  val fib10 : int array = [|1; 1; 2; 3; 5; 8; 13; 21; 34; 55|]

Initialize provides the following properties:

If v is defined as ``let v = Array.initialize f n'' then

  1) v is completely initialized:
     for all i, v.(i) has been assigned exactly once during the
     initialization of v
  2) not yet initialized locations in v are never accessed during the
     initialization process:
     for all i, for all j, if j > i then the location j is not accessed during
     the initialization of v.(i)
  3) elements of v are values computed by f:
     for all i, v.(i) = f (fun i -> (Array.sub v 0 (i - 1)).(i)) (i)

  Once more there is no need to dynamically check accesses to a vector
  initialized unsing the function initialize.

Evidently, if you want to initialize the other way round, you may
define the corresponding function, say initialize_down:

  let initialize_down f n =
   if n = 0 then [||] else
   let get v i j =
    if j > i && j < n then v.(j) else raise (Uninitialized_access j) in
   let v = Array.make n (f (get [||] 0) 0) in
   for i = n - 1 to 1 do
    v.(i) <- f (get v i) i
   done;
   v;;

3) New random_initialize function for ``random'' initialization
----------------------------------------------------------------

Now, you can still argue that you have even more complex
initialisation schemes: then you need to define a more complex
initialization function. For instance:

[random_initialize f i0 n] returns a vector [v] of length [n],
initialized using the function [f], starting from index [i0]. The
function [f] takes two arguments, an access function [g : int -> 'a]
that gives access to already initialized elements of the vector [v],
and an index [i]; given those arguments [f] returns a pair [next, a],
where [a] is the value to be stored at index [i] of vector [v], and
[next] the index of the next element of [v] to initialize. [f] should
raise the predefined exception [Exit] to mean that index [i] is out of
range, presumably at the end of initialization.

The following properties hold:

If v is defined as ``let v = random_initialize f i0 n'' then

  1) v is completely initialized:
     for all i, v.(i) has been assigned exactly once during the
     initialization of v
  2) not yet initialized locations in v are never accessed during the
     initialization process:
     for all i, for all j, if v.(j) has not yet been assigned then the
     location j is not accessed during the initialization of v.(i)
  3) all elements of v are values computed by calls to f.

Implementation

  (* Already_initialized is raised when there is an attempt to
     initialize an array location more than once. *)
  exception Already_initialized of int;;

  (* Partial_initialization is raised when there is a location that is
     not initialized at the end of initilization. *)
  exception Partial_initialization of int;;

  let random_initialize f i0 n =
   if n = 0 then [||] else
   let initialized = Array.make n 0 in
   let set v i a =
    if initialized.(i) = 0 then (initialized.(i) <- 1; v.(i) <- a)
    else raise (Already_initialized i) in
   let get v j =
    if j >= 0 && j < n && initialized.(j) = 1 then v.(j)
    else raise (Uninitialized_access j) in
   let nexti0, a0 = f (get [||]) i0 in
   let v = Array.make n a0 in
   set v 0 a0;
   let rec init i =
    let nexti, ai = f (get v) i in
    set v i ai;
    init nexti in
   try init nexti0 with
   | Exit ->
      for i = 0 to n - 1 do
       if initialized.(i) = 0 then raise (Partial_initialization i)
      done;
      Array.init n (fun i -> v.(i));;

Example: we can define a suitable initialization function for your
example of combinatorial numbers,

  let init_chooses n get i =
   let next i j = if j <> i then j else n + 1 in
   let ai i = get (i - 1) * (n - i + 1) / i in
   if i = 0 then (next 0 n, 1) else
   if i = n then (next n 1, 1) else
   if i > n then raise Exit else 
   if i <= n / 2 then (next i (n - i), ai i)
   else (next i (n - i + 1), get (n - i));;

  let chooses n = random_initialize (init_chooses n) 0 (n + 1);;

  let v4 = chooses 4;;
  val v4 : int array = [|1; 4; 6; 4; 1|]

4) Further work
---------------

The general vector initialization function should probably take as
argument f a function that uses 2 functions get and set to handle the
initialized vector. In any case, the properties 1, 2, and 3 should
still hold.

5) Conclusion
-------------

I'm not sure we need a complex additional machinery to solve a problem
that can be elegantly solved with some library functions (admittedly
at the price of some linear additional cost at initialization time);
however, following Xavier, I would also be glad to read articles on
dependant type systems and their applications to vector initialisation
(if any); also, I would be delighted to try such an experimental type
system, if it is tractable in practice (I mean, we don't want a type
system that obliges the programmer to rewrite his pattern matchings in
a strange and awful maneer, nor a type system that emits error
messages that are incredibly more difficult to understand than those
of usual ML typecheckers, nor a type system that is so slow that
modern machines are turned into good old Apple IIs, don't we ?).

Best regards,

-- 
Pierre Weis

Re: reference initialization

[Hongwei Xi]

What I had in mind is actually something pretty simple (since it won't
be very useful if it is not simple :-))

> My gut feeling about this approach is that the type system could
> probably work well for arrays that are initialized linearly, e.g.
> 
>         let a = Array.create n in
>         for i = 0 to n - 1 do
>           a.(i) <- ...
>           (* at this point, the type system knows that 
>              a.(0)...a.(i-1) are initialized and
>              a.(i)...a.(n-1) are not *)
>         done
>         (* at this point, the type system knowns that all elements of a
>            are initialized *)
> 
> But notice that most of these cases are easily expressed using Array.init!

But one common case is not covered: when you initialize A[i], you may
need values stored in A[j] for some 0 <= j < i. Is it possible to make
'init' handle this case as well. I must say that I have problems writing
such a function. This is certainly a problem that people who are
interested in generic programming should study (if it has not be
studied yet).

> However, the type system is going to break horribly on more complex
> initialization patterns, e.g. the following code for tabulating the
> inverse of a permutation f over [0...n-1] :
> 
>         let a = Array.create n in
>         for i = 0 to n - 1 do a.(f(i)) <- i done
> 
> So, I don't think the (Caml) programmer will gain much from a type
> system/static analysis for array initialization.  (For a lower-level
> language such as TAL, the story may be different, though.)

In this case, I could imagine that there are programmers who 
would like to verify that this code indeed initialize every
array cell; this is clearly a case where initialization upon
allocation doesn't make much sense.

Is it possible to have something like the following in the library:

Array.init': int -> (int -> (int * 'a)) -> 'a Array

let Array.init' n f =
  let a = Array.create n in
  for i = 0 to n - 1 do
    let (j, v) = f i
    in a.(j) <- v
  done
  (* then check that all cells are initilized *)

RE: reference initialization

[Eijiro Sumii]

> Yes, in theory, it requires null check at every use. However,
> I assume that a marjority of such null checks can be readily
> eliminated using flow analysis,

I'm afraid that this is not so easy, especially under separate
compilation.  For example, if we want to separately-compile a function
like "fun ref x -> !x + 1" (in the ocaml syntax), and if x could be
null, then the null check elimination would be hard.  Such situations
seem ubiquitous in practice.

On the other hand, ML types work as an interface to specify whether x
is always initialized ("int ref") or not ("int option ref").  And
static typing enforces such a protocol between modules.

> Note that Java is imperative, which makes flow analysis easier
> (compared to ML).

I wonder how flow analysis can be easier in Java than in ML.  While ML
has higher-order functions, Java has inner classes.

> A common saying is that a program is made safer if references
> are always initialized. I find this is contrary to the truth.
> In this case, a program is made safer if you insert run-time
> checks (and rely on a compiler to remove redundant checks)
> 
> If I use 'get' and 'set', is there a compiler to eliminate such
> checks (i.e., after 'set', 'get' should do no tag checking)?
> 
> Yes, ML allows the programmer to tag values (using option
> types) and thus shifts the burden to the programmer. In Java,
> this is done automatically (and we can rely on a compiler to
> remove redundant null checks).

ML could also do it automatically, by analyzing whether a value of an
"option" type always has the "Some" tag.  The analysis would be
similar to standard flow analyses or type-based analyses.

// Eijiro Sumii <sumii@saul.cis.upenn.edu>
//
// currently visiting: Department of Computer and Information Science,
// School of Engineering and Applied Science, University of Pennsylvania

Re: reference initialization

[Xavier Leroy]

> [The Java solution with null pointers]
> Yes, in theory, it requires null check at every use. However,
> I assume that a marjority of such null checks can be readily
> eliminated using flow analysis, though things can become difficult
> when arrays are involved. Note that Java is imperative, which
> makes flow analysis easier (compared to ML).

Don't count too much on the Java compiler being able to eliminate null
checks.  I don't think today's Java compiler technology is good enough
to do that.  Also:

- To eliminate null checks efficiently requires global (whole program)
analysis, which is nearly unapplicable to Java due to dynamic class
loading.
- To eliminate null checks for pointers fetched from an array requires
very subtle analyses, e.g. you need to keep track of which array
elements were initialized with non-null references and which elements
still hold the default null value.  (See below.)
- Those null checks work for arrays of objects, but not for arrays of
numerical quantities, which are initialized with default values just
like in ML.

This whole discussion seems to be going in circles.  If you want the
additional safety of run-time checking for uninitialized array
entries, you can get it in Caml by using option types, at a
performance cost.  If you'd rather avoid the performance cost, you
have to be a little more careful in your coding.  Finally, in many
cases you can have your cake and it eat too by avoiding low-level
operations such as "allocate array then fill it" and using
higher-level operations such as "tabulate this function in an array"
(a la Array.init).

Knowing the background of Hongwei Xi, I think I've guessed where he is
getting at: one could envision a refined type system for arrays that
keep track of (a conservative estimate of) the indices of elements
that have been initialized.  TAL does it for heap-allocated tuples,
and it would be interesting to see whether DML-style dependent types
allow such a type-checking for the more general case of arrays.
So, Hongwei, we'll read your next paper on this topic with interest :-)

My gut feeling about this approach is that the type system could
probably work well for arrays that are initialized linearly, e.g.

        let a = Array.create n in
        for i = 0 to n - 1 do
          a.(i) <- ...
          (* at this point, the type system knows that 
             a.(0)...a.(i-1) are initialized and
             a.(i)...a.(n-1) are not *)
        done
        (* at this point, the type system knowns that all elements of a
           are initialized *)

But notice that most of these cases are easily expressed using Array.init!

However, the type system is going to break horribly on more complex
initialization patterns, e.g. the following code for tabulating the
inverse of a permutation f over [0...n-1] :

        let a = Array.create n in
        for i = 0 to n - 1 do a.(f(i)) <- i done

So, I don't think the (Caml) programmer will gain much from a type
system/static analysis for array initialization.  (For a lower-level
language such as TAL, the story may be different, though.)

- Xavier Leroy

RE: reference initialization

[Hongwei Xi]

> The real difference between ML references and Java pointers is that ML
> separates "reference" from "possibly unitialized", while Java combines the
> two into one construct. It's not to difficult to implement Java-style
> pointers in ML, just use an option ref. For example:
> 
> type 'a ptr = a' option ref
> exception NullPointer
> let new () = ref None
> let get x = match !x with Some y -> y | None -> raise NullPointer
> let set x y = x := Some y 
> 
> ML, of course, lacks the syntactic support to use these pointers as
> gracefully as Java can. On the other hand, the problem with _Java_ is
> efficiency loss, as the programmer cannot syntactically enforce that the
> reference is initialized -- requiring a null check at every use.
> 
> -Stephanie

Yes, in theory, it requires null check at every use. However,
I assume that a marjority of such null checks can be readily
eliminated using flow analysis, though things can become difficult
when arrays are involved. Note that Java is imperative, which
makes flow analysis easier (compared to ML).

A common saying is that a program is made safer if references
are always initialized. I find this is contrary to the truth.
In this case, a program is made safer if you insert run-time
checks (and rely on a compiler to remove redundant checks)

If I use 'get' and 'set', is there a compiler to eliminate such
checks (i.e., after 'set', 'get' should do no tag checking)?

Yes, ML allows the programmer to tag values (using option
types) and thus shifts the burden to the programmer. In Java,
this is done automatically (and we can rely on a compiler to
remove redundant null checks). Which is better?

--Hongwei

RE: reference initialization

[Stephanie Weirich]

> -----Original Message-----
> From: Hongwei Xi [mailto:hwxi@ececs.uc.edu]
> Sent: Wednesday, May 10, 2000 12:50 AM
> To: caml-list@inria.fr
> Subject: reference initialization
> 
> 
> > Wrong. You have references, which are quite better than pointers
> > (they are typed, and necessarily initialized)
> 
> I have given some thoughts on this one.
> 
[... parts elided ...]
> 
> Can you still say that the ML strategy is better than the Java
> strategy? I thus argue that it is better using dynamic checking
> to detect reading from uninitialized reference than simply
> assigning a value to every reference upon its creation.
> 
> To summarize, my bottom line question is: what is really achieved
> by assigning a reference a (wrong) initial value? Isn't this just
> like an ostrich solving its problem by burying its head in sand?
> 
> Of course, another problem with the ML strategy is efficiency loss
> (which, though, is often negligible as discussed here before)

The real difference between ML references and Java pointers is that ML
separates "reference" from "possibly unitialized", while Java combines the
two into one construct. It's not to difficult to implement Java-style
pointers in ML, just use an option ref. For example:

type 'a ptr = a' option ref
exception NullPointer
let new () = ref None
let get x = match !x with Some y -> y | None -> raise NullPointer
let set x y = x := Some y 

ML, of course, lacks the syntactic support to use these pointers as
gracefully as Java can. On the other hand, the problem with _Java_ is
efficiency loss, as the programmer cannot syntactically enforce that the
reference is initialized -- requiring a null check at every use.

-Stephanie

RE: reference initialization

[Dave Berry]

IMO, the "ML strategy" is to use an option type.  SML has 
	datatype 'a option = NONE | SOME of 'a
although I prefer 
	datatype 'a option = NULL | VALUE of 'a.
I don't know if Caml provides such a type as standard, although
it's easy to define your own.

Then your code checks whether the value has been assigned (dynamically,
as you require), and can take whatever action is appropriate.  If you want
to throw an exception, you can.

With this approach, the ML type system tells you which values may be null.
This has an advantage over the Java approach, where any value may be
null or uninitialised.

Dave.

-----Original Message-----
From: Hongwei Xi [mailto:hwxi@ececs.uc.edu]
Sent: Wednesday, May 10, 2000 5:50 AM
To: caml-list@inria.fr
Subject: reference initialization


> Wrong. You have references, which are quite better than pointers
> (they are typed, and necessarily initialized)

Suppose I use a reference 'x'. If I know what the initial value
of 'x' should be, I'll of course prefer to initialize it with that
value. Now suppose I don't, that is, I intend to assign a value
to 'v' later (maybe in a loop or in a conditional branch)

(1) ML strategy: initialize x with any value 'v' of an appropriate
type (sometimes, such a 'v' is difficult to find or takes time to
construct (consider 'x' to be a large array)).