RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Don Syme]

Hi Pierre,

> On the language design side, we worked hard to bypass the limitations
> of letrefs in order to design first class citizens references, and to
> get rid of left values in the language. On the compiler construction
> side, Xavier worked hard to optimise spurious allocations of
> references that can be treated as vars. I think we now have the power
> and conceptual simplicity of references along with the runtime
> efficiency of letrefs, I don't see the point to introduce a new
> arguably useless construct.

I agree with most of what you say, but only in the sense that I would
agree that "mutable" is not really needed for record fields either, and
that programmers could be forced to live with Standard ML's "ref" just
to keep the language slightly simpler.  

But then why is "mutable" on record fields better for the working
imperative programmer?  Firstly because it's just closer to C.  But I
think it might also be the case that using "mutable" is just lighter on
the programmer's mind than using "ref".  My feeling is that the same
holds true for let-bound variables.  

[ To expand on why "mutable" fields are, IMHO, so much better...  In
Standard ML "refs" get used in data structures for four main purposes: 
  - to get values that can be compared by pointer equality; 
  - to ensure sharing of an allocation cell; 
  - to allow "regular" mutation; 
  - to cope with initializing recursive data structures using "ref
option".  

Because of these multiple uses I honestly used to get "ref" type
constructors nested two or three deep (when designing some
pointer-chasing graph structures)!!  

I was never able to get this code right until I switched to Caml,
precisely because my structures became simpler.  In Caml the combination
of inbuilt pointer equality and "mutable" made things sufficiently
simple, and the ability to allocate at least some recursively linked
objects without using "ref option" also helped.  
]

Mutable let-bound variables aren't as important as mutable fields, but I
don't see any great harm in having them.  OCaml is almost a truly great
imperative programming language, and I reckon if you added these then
you'd be a bit closer to this goal.  But at the moment C programs still
look like a bit of a mess when translated over to OCaml: too many "refs"
and "!"s...  These are fine if you're writing the stuff, but look pretty
crazy when you show the code to a C programmer (for starters ! gets
confused with C's "not"...)

(As an aside I will mention that I would like to see some remaining
problems solved: specifying enforced sharing by some other means than
using refs; and being able to "tie the knot" on recursive structures
that extend beyond a finite number of simultaneously allocated
cons-cells, without using "ref option". I guess both of these are pretty
hard to solve.  More realistically, I also don't see any harm at all in
having an extended "for" loop construct much as I proposed a year or so
ago.)

Don

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

I once advocated a "const" datatype for SML.  The const constructor
would create unique immutable values that could be compared for pointer
equality, satisfying Don's first use of refs.  (It's possible I included
these in the Edinburgh SML Library -- I don't recall after all these
years).  But this idea never caught on.

A similar idea is to define:
  type 'a pointer = 'a option ref
  fun null (ref NONE) = true | null _ = false
  fun ::= (p, v) = p := SOME v

Dave.


-----Original Message-----
From: Don Syme [mailto:dsyme@microsoft.com]
Sent: 15 June 2001 04:20

[ To expand on why "mutable" fields are, IMHO, so much better...  In
Standard ML "refs" get used in data structures for four main purposes: 
  - to get values that can be compared by pointer equality; 
  - to ensure sharing of an allocation cell; 
  - to allow "regular" mutation; 
  - to cope with initializing recursive data structures using "ref
option".  

Because of these multiple uses I honestly used to get "ref" type
constructors nested two or three deep (when designing some
pointer-chasing graph structures)!!  

I was never able to get this code right until I switched to Caml,
precisely because my structures became simpler.  In Caml the combination
of inbuilt pointer equality and "mutable" made things sufficiently
simple, and the ability to allocate at least some recursively linked
objects without using "ref option" also helped.  
]

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

Let me refute my own suggestion.  If people do want the ability to
specify stack allocation, they will want it for immutable values as well
as mutable values.  So it should be a separate, orthogonal construct.


-----Original Message-----
From: Dave Berry 
Sent: 08 June 2001 10:00
To: Jacques Garrigue; tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: RE: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


One possible reason for adding "let mutable" would be to specify that
escapes (such as the one Jacques gave) are explicitly disallowed.  In
other words, programmers could use "let mutable" to enforce the
requirement that the data is stack-allocated.  The compiler would report
an error if it is not possible to stack-allocate, instead of silently
defaulting to heap allocation.  Programmers might want to do this to
guarantee efficiency, or to guarantee that the memory is deallocated and
does not become a potential memory leak.

It might even be possible to attach finalisers to the data, which would
be guaranteed to be called when the function exits, analogous to C++
destructors.  However, this would complicate exception handling and
possibly tail-recursion optimisations.


-----Original Message-----
From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp]
Sent: 08 June 2001 00:50
To: tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Dave Berry]

One possible reason for adding "let mutable" would be to specify that
escapes (such as the one Jacques gave) are explicitly disallowed.  In
other words, programmers could use "let mutable" to enforce the
requirement that the data is stack-allocated.  The compiler would report
an error if it is not possible to stack-allocate, instead of silently
defaulting to heap allocation.  Programmers might want to do this to
guarantee efficiency, or to guarantee that the memory is deallocated and
does not become a potential memory leak.

It might even be possible to attach finalisers to the data, which would
be guaranteed to be called when the function exits, analogous to C++
destructors.  However, this would complicate exception handling and
possibly tail-recursion optimisations.


-----Original Message-----
From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp]
Sent: 08 June 2001 00:50
To: tom7ca@yahoo.com
Cc: williamc@paneris.org; caml-list@inria.fr
Subject: [Caml-list] let mutable (was OCaml Speed for Block
Convolutions)


About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[William Chesters]

Hugo Herbelin writes:
 > Assume more generally that you can modify any local variable as in the
 > (standard) following example:
 > 
 > let fact (mutable n) =
 >   let mutable r = 1 in
 >   while n > 0 do
 >      r <- r * n;
 >      n <- n - 1
 >   done;
 >   r

This doesn't actually make life much easier for the compiler.  On
32-bit machines [see other thread!], `r' must be a reference (in the
C++ sense) to a heap object---64-bit float, plus header.  In general
it is not safe to overwrite the float value in the heap, if it's
possible that other variables have been assigned to it (unless floats
are assigned by value not by reference, but in that case you get heap
allocation at the time of assignment ...).  The analysis necessary for
determining that no such aliasing references can exist, and indeed
that the value can simply be kept in a float register/on the FPU
stack, is already there in the compiler and applies perfectly well to
mutable references.

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] OCaml Speed for Block Convolutions

[Tom _]

--- William Chesters <williamc@paneris.org> wrote:
> Hugo Herbelin writes:
>  > Assume more generally that you can modify any
> local variable as in the
>  > (standard) following example:
>  > 
>  > let fact (mutable n) =
>  >   let mutable r = 1 in
>  >   while n > 0 do
>  >      r <- r * n;
>  >      n <- n - 1
>  >   done;
>  >   r
> 
> This doesn't actually make life much easier for the
> compiler.  On 32-bit machines [see other thread!], 
> `r' must be a reference (in the 
> C++ sense) to a heap object---64-bit float, plus
> header.

I don't see why. The compiler has full type 
information.  All it may have to do is box up
a return value.

In any case, whether or not the compiler in the
current implementation can or cannot do good type
inference and may or may not be forced to box
a floating point number, the two constructs mean
something different to the programmer, and they
behave differently.  In particular "mutable x"
can never be passed around as a reference, while
"x = ref ..." can.  If not anything else, that
prevents the programmer from inadvertently inhibiting
a compiler optimization by passing around a reference.

Besides, the syntax is probably quite a bit more 
natural to imperative programmers anyway.

Tom.


__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

About the introduction of a let mutable construct,
Tom _ <tom7ca@yahoo.com> wrote

> In any case, whether or not the compiler in the
> current implementation can or cannot do good type
> inference and may or may not be forced to box
> a floating point number, the two constructs mean
> something different to the programmer, and they
> behave differently.  In particular "mutable x"
> can never be passed around as a reference, while
> "x = ref ..." can.  If not anything else, that
> prevents the programmer from inadvertently inhibiting
> a compiler optimization by passing around a reference.

Not exactly, the compiler may still need to build a reference.

    let mutable x = 0 in
    List.iter (fun y -> x <- x+y) l;
    x

Since x has to be modified in a function called by iter, it must be
wrapped into an actual reference cell.

As the compiler already does a good job at unboxing only locally used
references, let mutable would only be some syntactic sugar (with
exactly the same typing as a reference).

> Besides, the syntax is probably quite a bit more 
> natural to imperative programmers anyway.

This is actually the only argument for let mutable.
I would also like such a construct, but I don't know whether its worth
it. The real question is whether let mutable should be allowed at
toplevel, with problems for both answers.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Ohad Rodeh]

I don't mean to barge into an open door here, but
the discussion here is about escape analysis. This certainly
does not require the new "mutable" syntax. My personal opinion
is that Caml has enough syntax as it is (try using/modifying the
OCaml mly files as an exercise ...). 

In any case, escape analysis a clever optimization allowing some heap
allocated objects to be allocated on the run-time stack.
The MLkit takes escape analysis into the extrem, using regions. Java
compilers also use escape analysis to reduce heap allocation. 

Since we are already on the "with list" thread, I'd like to add my 
own wish. I'm going to teach the "Purely Functional Data Structures" book
(Chris Okasaki) as a course next semester. To do the real nifty stuff, you
need to have polymorphic recursion supported by the compiler. Can this be
added to the next release? 

	Ohad.

On Fri, 8 Jun 2001, Jacques Garrigue wrote:

> About the introduction of a let mutable construct,
> Tom _ <tom7ca@yahoo.com> wrote
> 
> > In any case, whether or not the compiler in the
> > current implementation can or cannot do good type
> > inference and may or may not be forced to box
> > a floating point number, the two constructs mean
> > something different to the programmer, and they
> > behave differently.In particular "mutable x"
> > can never be passed around as a reference, while
> > "x = ref ..." can.If not anything else, that
> > prevents the programmer from inadvertently inhibiting
> > a compiler optimization by passing around a reference.
> 
> Not exactly, the compiler may still need to build a reference.
> 
>   let mutable x = 0 in
>   List.iter (fun y -> x <- x+y) l;
>   x
> 
> Since x has tobe modified in a function called by iter, it must be
> wrapped into an actual reference cell.
> 
> As the compiler already does a good job at unboxing only locally used
> references, let mutable would only be some syntactic sugar (with
> exactly the same typing as a reference).
> 
> > Besides, the syntax is probably quite a bit more
> > natural to imperative programmers anyway.
> 
> This is actually the only argument for let mutable.
> I would also like such a construct, but I don't know whether its worth
> it. Thereal question is whether let mutable should be allowed at
> toplevel, with problems for both answers.
> 
> Cheers,
> 
> Jacques Garrigue
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugsFAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.frArchives: http://caml.inria.fr
> 

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Brian Rogoff]

> Since we are already on the "with list" thread, I'd like to add my 
> own wish. I'm going to teach the "Purely Functional Data Structures" book
> (Chris Okasaki) as a course next semester. To do the real nifty stuff, you
> need to have polymorphic recursion supported by the compiler. Can this be
> added to the next release? 

This has been discussed many times here, and Pierre Weis has given a 
few good summaries of past work which you can access from the archives. 
In particular, the forward declaration he proposed also fixed the 
module spanning recursive function definition issue, and so kills 
at least two birds with one stone. Here's the ref 

http://caml.inria.fr/archives/199902/msg00020.html

Supporting polymorphic recursion is really high on my wish list too even
though I'm not in school or teaching. In essence, I want more
recursion: polymorphic recursion, module spanning recursive types, etc. I
personally hadn't bumped into the case where module spanning recursive
function definitions were a pain, but I found Fergus Henderson's argument
from the Mercury compiler sources pretty convincing so I want that too. 

Anyways, that's the problem with that damned Okasaki book; once you read
it you start wanting all of these fancy features. I guess ignorance
really is bliss. :-)

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> About the introduction of a let mutable construct,
> Tom _ <tom7ca@yahoo.com> wrote
> 
> > In any case, whether or not the compiler in the
> > current implementation can or cannot do good type
> > inference and may or may not be forced to box
> > a floating point number, the two constructs mean
> > something different to the programmer, and they
> > behave differently.  In particular "mutable x"
> > can never be passed around as a reference, while
> > "x = ref ..." can.  If not anything else, that
> > prevents the programmer from inadvertently inhibiting
> > a compiler optimization by passing around a reference.
> 
> Not exactly, the compiler may still need to build a reference.
> 
>     let mutable x = 0 in
>     List.iter (fun y -> x <- x+y) l;
>     x
> 
> Since x has to be modified in a function called by iter, it must be
> wrapped into an actual reference cell.
> 
> As the compiler already does a good job at unboxing only locally used
> references, let mutable would only be some syntactic sugar (with
> exactly the same typing as a reference).
> 
> > Besides, the syntax is probably quite a bit more 
> > natural to imperative programmers anyway.
> 
> This is actually the only argument for let mutable.
> I would also like such a construct, but I don't know whether its worth
> it. The real question is whether let mutable should be allowed at
> toplevel, with problems for both answers.
> 
> Cheers,
> 
> Jacques Garrigue
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

The introduction of a ``let mutable'', more concisely noted with the
var keyword, is not new: it has been discussed in the Caml groups 3 or
4 years ago. We chose to abandon it for sake of semantics simplicity
of the language. This construction would have introduced the notion of
Lvalue in Caml, thus introducing some additional semantics complexity,
and a new notion to explain to beginners. Furthermore, the efficiency
gain was not clear, since Xavier had succeeded at optimizing reference
allocations for all typical uses of references that are relevant to
the proposed (less powerful) ``let mutable'' bound variables.

Let me explain the semantics arguments (semantics is more important
that many of us think, although all of us are syntax lovers and syntax
alternate features advocates) for pure references and against the
introduction of ``let mutable'' bound variables.

Dynamic semantics (or evaluation mechanism)
-------------------------------------------

You may not have noticed that Caml mutable values (references or
arrays) have a first class citizen status, being treated as regular
values with respect to data structures manipulation and function calls
and returns. For example, the assignment operators are regular
functions with no magic (such as special annotations of arguments at
definition time, or special operation at call sites). Hence you can
define your own assigment functions using regular Caml programming:

let ( += ) r v = r := !r + v;;
val ( += ) : int ref -> int -> unit = <fun>

Now, if you write x += 2 you apply the (infix) operator += to the two
expressions x and 2. This is just regular Caml computation, hence you
can write arbitrary programs instead of x and 2. For instance, f y +=
g 0 means that function call f y returns a reference whose contents is
incremented by (the value of) g 0.

Note that the mechanism is also that simple for the ! operator: ! has
no special evaluation rule, it is applied to the value of its argument
(which must be a reference) and returns it contents. Hence you may
write !(f y), provided that f y returns a reference.

In the same vein you can redefine the usual := operator (for instance
to count the number of assigments in your program):

let assignment_count = ref 0;;

let ( := ) r v =
  incr assignment_count;
  r := v;;
val ( := ) : 'a ref -> 'a -> unit = <fun>

If you prefer the C way, you can even use:

let ( = ) r v = r := v;;
val ( = ) : 'a ref -> 'a -> unit = <fun>

Now you loose = as a short hand for the polymorphic comparison, but as
desired, r = 1 will gladly assign 1 to r ...

Another interesting point: there is no scope limitation or odity for
references; references obey the usual scope and life time rules.

Static semantics (or typechecking mechanism)
--------------------------------------------

On this (hard) side, nothing to gain with the new construct: the
restriction on typechecking of polymorphic refs should be maintained
for vars, or we must revert to the original complicated (and probably
not proved sound) rule of original ML (see below).

Historical (and personal) note:
-------------------------------

The proposed construct is not new: it has been introduced in original
ML (from LCF) by Robin Milner in 1978. Mutable variables were
introduced by letref (reminiscent of the letrec keyword that
introduced recursive definitions at that time). You would declare a
(so-called) reference identifier by the definition

letref x = 0;;

and assign it using:

x := x + 1;;

(Note that on the left of := you needed a left value, hence an
identifier previously defined via letref.)

During the year 1984, the ML team discovered that allocating a cell
for letref identifiers will enhance the power of ``letref''
definitions since references could be treated as first class citizen
values. My first compilation programming exercise was to implement the
new feature into the V6.1 version of the ML compiler during falls 1984
(or may be at beginning of 1985 ?). We simultaneously maintained both
constructs in the language; we also used the same := operator to
assign references (desambiguated via a compiler annotation of letref
bound identifiers), and an explicit deref function to get the contents
of the new references. After the introduction of the shorter !
dereferencing operator, everybody in the ML community (read community
as ``the people logged on our vax or on the Cambridge University's
vax''!) agreed that the old letref construct was subsumed by the new
references stuff. Thus, I suppressed the old letref construct from the
language. The special typing rule for letref was reinforced for the
new references (but getting rid of the strange lambda-bound
restriction of the letref construct) in a trivial way: at the end of
typechecking all references defined in the program should have
monomorphic types. As you may know this was the beginning of a long
and difficult quest of the right typing restriction for safe
manipulation of polymorphic mutable values in ML-like
languages. Although the currently used value restriction rule was
discovered by Greg Morrisset in 1995, the Caml team actively
participated to this quest with a POPL article by Xavier Leroy and I
in 1991, and culminated with Xavier's PHD thesis in 1992.

Conclusion:
-----------

On the language design side, we worked hard to bypass the limitations
of letrefs in order to design first class citizens references, and to
get rid of left values in the language. On the compiler construction
side, Xavier worked hard to optimise spurious allocations of
references that can be treated as vars. I think we now have the power
and conceptual simplicity of references along with the runtime
efficiency of letrefs, I don't see the point to introduce a new
arguably useless construct.

Best regards,

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Stefan Monnier]

>>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:
> languages. Although the currently used value restriction rule was
> discovered by Greg Morrisset in 1995, the Caml team actively

I though it was Andrew K. Wright "Simple Imperative Polymorphism" in
Lisp and Symbolic Computation, Déc 95 (the corresponding tech-report
dates back to 93).  Does anybody remember ?


	Stefan
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> >>>>> "Pierre" == Pierre Weis <Pierre.Weis@inria.fr> writes:
> > languages. Although the currently used value restriction rule was
> > discovered by Greg Morrisset in 1995, the Caml team actively
> 
> I though it was Andrew K. Wright "Simple Imperative Polymorphism" in
> Lisp and Symbolic Computation, Déc 95 (the corresponding tech-report
> dates back to 93).  Does anybody remember ?
> 
> 
> 	Stefan
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Oups: the value restriction was indeed studied by Andrew Wright and
first published as a tech report in 1993, then published in 1995 in
Lisp and Symbolic Computation. Sorry for the mistake.

Here are the references to the relevant publications:

A.K. Wright. Polymorphism for imperative languages without imperative
types. Technical report TR93-200, Rice University, 1993.

@article{ wright95simple,
    author = "Andrew K. Wright",
    title = "Simple Imperative Polymorphism",
    journal = "Lisp and Symbolic Computation",
    volume = "8",
    number = "4",
    pages = "343--355",
    year = "1995",
    url = "citeseer.nj.nec.com/wright95simple.html"
}

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Michel Quercia]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="US-ASCII", Size: 1469 bytes --]

Le Vendredi  8 Juin 2001 19:30,  Pierre Weis a écrit :

> The introduction of a ``let mutable'', more concisely noted with the
> var keyword, is not new: it has been discussed in the Caml groups 3 or
> 4 years ago. We chose to abandon it for sake of semantics simplicity
> of the language.

For beginners (f.e. students) things look a bit complicated :

(* summing up all elements of an integer array *)
let adda a =
  let res = ref 0 in
  let i = ref 0 in
  while !i < Array.length(a) do res := !res+a.(!i); i := !i+1 done;
  !res
;;

A lot of boring exclam, but that's the price to pay for having 
mutable values, and that's logical. Okay ...

(* same, but with a for loop *)
let add_1 a =
  let res = ref 0 in
  for i=0 to Array.length(a)-1 do res := !res + a.(i) done;
  !res
;;

No exclam and no ref for i ?  And its value is changing though ? Where is 
gone the logic ?

> This construction would have introduced the notion of
> Lvalue in Caml, thus introducing some additional semantics complexity,
> and a new notion to explain to beginners.

Lvalues already exist in Ocaml (and have to be explained to beginners), for 
example : "a.(i) <- a.(i)+1".

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://pauillac.inria.fr/~quercia
mailto:michel.quercia@prepas.org
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> Le Vendredi  8 Juin 2001 19:30,  Pierre Weis a écrit :
> 
> > The introduction of a ``let mutable'', more concisely noted with the
> > var keyword, is not new: it has been discussed in the Caml groups 3 or
> > 4 years ago. We chose to abandon it for sake of semantics simplicity
> > of the language.
> 
> For beginners (f.e. students) things look a bit complicated :
> 
> (* summing up all elements of an integer array *)
> let adda a =
>   let res = ref 0 in
>   let i = ref 0 in
>   while !i < Array.length(a) do res := !res+a.(!i); i := !i+1 done;
>   !res
> ;;
> 
> A lot of boring exclam, but that's the price to pay for having 
> mutable values, and that's logical. Okay ...
> 
> (* same, but with a for loop *)
> let add_1 a =
>   let res = ref 0 in
>   for i=0 to Array.length(a)-1 do res := !res + a.(i) done;
>   !res
> ;;
> 
> No exclam and no ref for i ?  And its value is changing though ? Where is 
> gone the logic ?

The for loop is a short hand for a call to a local recursive function:
no reference and no problem here, unless you consider that you cannot
change the arguments of a recursive call to a function.

(For readers not familiar with the subject, let's recall that

for i = e1 to e2 do e3 done

 is equivalent to

let rec _loop i _lim = if i <= _lim then begin e3; _loop (i + 1) _lim end in
_loop e1 e2

(where _loop and _lim stand for new fresh identifiers, not free in e1, e2,
or e3)
)

> > This construction would have introduced the notion of
> > Lvalue in Caml, thus introducing some additional semantics complexity,
> > and a new notion to explain to beginners.
> 
> Lvalues already exist in Ocaml (and have to be explained to beginners), for 
> example : "a.(i) <- a.(i)+1".

I'm afraid this is wrong.

The syntactic construction e1.(e2) <- e3 is a short hand for a
function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
just a regular function call (hence you can write arbitrary complex
expressions in place of e1, provided it returns an array value).

I'm a bit surprised that you feel it necessary to explain the notion
of Lvalue to beginners when there is no such notion in the language !

Best regards.

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

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

> > > This construction would have introduced the notion of
> > > Lvalue in Caml, thus introducing some additional semantics complexity,
> > > and a new notion to explain to beginners.
> > 
> > Lvalues already exist in Ocaml (and have to be explained to
> > beginners), for example : "a.(i) <- a.(i)+1".
> 
> I'm afraid this is wrong.
> 
> The syntactic construction e1.(e2) <- e3 is a short hand for a
> function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
> just a regular function call (hence you can write arbitrary complex
> expressions in place of e1, provided it returns an array value).
> 
> I'm a bit surprised that you feel it necessary to explain the notion
> of Lvalue to beginners when there is no such notion in the language !

You can of course explain the semantics this way, but most people
apparently consider that there are lvalues in ocaml, just that they
are very restricted. It is certainly much simpler to explain than
lvalues in C!

Also, there is one unique case currently which can only be explained
by the distinction lvalue/rvalue: instance variables in objects.

  class counter = object
    val mutable x = 0
    method get = x
    method bump = x <- x + 1
  end

How can you explain the method bump without the notion of lvalue?

Perfectly coherent answers would be, let's remove mutable instance
variables, or force the notation self.x to access variables.
Another answer is that people so fond of objects have already heared
of lvalues anyway.

the problem is not only with lvalues either. With for loops, you have
a case of rvalue, where something which is not syntactically a
function have a changing variable, which is accessed directly. The
fact you cannot change it yourself is not relevant.

Best regards,

     Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Pierre Weis]

> From: Pierre Weis <Pierre.Weis@inria.fr>
> 
> > > > This construction would have introduced the notion of
> > > > Lvalue in Caml, thus introducing some additional semantics complexity,
> > > > and a new notion to explain to beginners.
> > > 
> > > Lvalues already exist in Ocaml (and have to be explained to
> > > beginners), for example : "a.(i) <- a.(i)+1".
> > 
> > I'm afraid this is wrong.
> > 
> > The syntactic construction e1.(e2) <- e3 is a short hand for a
> > function call: Array.set e1 e2 e3. Once more there is no Lvalue here,
> > just a regular function call (hence you can write arbitrary complex
> > expressions in place of e1, provided it returns an array value).
> > 
> > I'm a bit surprised that you feel it necessary to explain the notion
> > of Lvalue to beginners when there is no such notion in the language !
> 
> You can of course explain the semantics this way, but most people
> apparently consider that there are lvalues in ocaml, just that they
> are very restricted. It is certainly much simpler to explain than
> lvalues in C!

Most people consider Caml as a toy language, since it is not a
mainstream language. As a computer science researcher fond of riguour,
I certainly will not organize a vote to find out if ``most people
apparently consider'' something, to decide that this something is
true.

A more interesting contribution would be to give evidences that
references and arrays and other imperative features are indeed built
with lvalues in Caml.

> Also, there is one unique case currently which can only be explained
> by the distinction lvalue/rvalue: instance variables in objects.
> 
>   class counter = object
>     val mutable x = 0
>     method get = x
>     method bump = x <- x + 1
>   end
> 
> How can you explain the method bump without the notion of lvalue?

I can't and I just consider the introduction of lvalues to model
states in objects as a flaw in the design of this feature (and I
certainly never have promoted it). Reintroduction of lvalues just for
this questionable facility is an error.

> Perfectly coherent answers would be, let's remove mutable instance
> variables, or force the notation self.x to access variables.

Yes. That's what we should have done, since we love perfectly coherent
answers for Caml.

> Another answer is that people so fond of objects have already heared
> of lvalues anyway.

So what ?

I cannot consider such a vague argument as a satisfactory answer to an
important language design decision, since this ``answer'' is not a
language design consideration. If we were using this kind of general
public oriented reasons as guidelines to develop the semantics of the
language, you could imagine I could state that ``people so fond of
objects have already heared of bus error anyway'', which is also true
I'm afraid, to justify the introduction of a feature that would cause
some bus errors from time to time!

> the problem is not only with lvalues either. With for loops, you have
> a case of rvalue, where something which is not syntactically a
> function have a changing variable, which is accessed directly. The
> fact you cannot change it yourself is not relevant.

What do you mean here ? A for loop being just a shorthand for the
definition of a function, I don't see the problem...

Best regards,

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Jacques Garrigue]

Bonjour Pierre,

> > You can of course explain the semantics this way, but most people
> > apparently consider that there are lvalues in ocaml, just that they
> > are very restricted. It is certainly much simpler to explain than
> > lvalues in C!
> 
> Most people consider Caml as a toy language, since it is not a
> mainstream language. As a computer science researcher fond of riguour,
> I certainly will not organize a vote to find out if ``most people
> apparently consider'' something, to decide that this something is
> true.

I didn't ask for one. I'm basically agreeing with you that once we
have a good property, we shall stick to it.
My remark was just that it was not a completely unreasonable way to
explain the behaviour of assignment, and that thanks to good
properties, this was kept simple.

> A more interesting contribution would be to give evidences that
> references and arrays and other imperative features are indeed built
> with lvalues in Caml.

Indeed the type checker has an individual case for each of the
assignment constructs, so the parallel with lvalues is only on
surface. (More precisely, only records are handled by the type
checker, other ones are just syntactic sugar.)

> > Also, there is one unique case currently which can only be explained
> > by the distinction lvalue/rvalue: instance variables in objects.
> 
> > Perfectly coherent answers would be, let's remove mutable instance
> > variables, or force the notation self.x to access variables.
> 
> Yes. That's what we should have done, since we love perfectly coherent
> answers for Caml.

Indeed.

> > Another answer is that people so fond of objects have already heared
> > of lvalues anyway.
> 
> So what ?

I was just wondering why it is the way it is, nothing more.
I suppose we're not going to change it anyway, considering the
quantity of code involved. The best would be not to have it in the
first place.

> > the problem is not only with lvalues either. With for loops, you have
> > a case of rvalue, where something which is not syntactically a
> > function have a changing variable, which is accessed directly. The
> > fact you cannot change it yourself is not relevant.
> 
> What do you mean here ? A for loop being just a shorthand for the
> definition of a function, I don't see the problem...

If we take your previous argument of evidences in the compiler, the
loop variable is indeed compiled as a lvalue. There is no function
involved, and the for loop goes down to the backend.
But I agree that you can handle this as syntactic sugar, and provide a
semantics without rvalues for it.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Georges Brun-Cottan]

Bonjour Jacques,

>  > > the problem is not only with lvalues either. With for loops, you have
>  > > a case of rvalue, where something which is not syntactically a
>  > > function have a changing variable, which is accessed directly. The
>  > > fact you cannot change it yourself is not relevant.

I think it is relevant: it is not uncommon in C to mistakenly
transform a simple finite loop in an infinite one through side-effect
to the loop control variable... The 'for' loop makes the point very
clear that you are protected against this case.

[...]  and later on 

> If we take your previous argument of evidences in the compiler, the
> loop variable is indeed compiled as a lvalue. There is no function
> involved, and the for loop goes down to the backend.

But it can not be assigned explicitely by the programmer, right?

-- Georges
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[John Max Skaller]

Pierre Weis wrote:

> A more interesting contribution would be to give evidences that
> references and arrays and other imperative features are indeed built
> with lvalues in Caml.

	To do that, one must understand what an lvalue is.
In C, it is an expression term obeying certain syntactic
constraints.  That is, it is not a matter of semantics,
or typing: an lvalue is a particular piece of syntax.

	To say that another way, some constraints on the
language _syntax_ are not imposed by the grammar, but by 
additional rules such as 'the argument of the unary & operator
must be an lvalue'.

	This is NOT the case in C++, where the typing
is related to lvalueness. Note that in BOTH cases,
lvalueness is related to addressability, NOT necessarily
mutability. In C++, non-lvalues are definitely mutable!

	[The rules in C++ are a shambles]

-- 
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
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] let mutable (was OCaml Speed for Block Convolutions)

[Michael Sperber [Mr. Preprocessor]]

Here's a shameless plug for a paper which also examines some related
issues and briefly talks about mutable let as well:

@InProceedings{SperberThiemann1998,
  author = 	 {Michael Sperber and Peter Thiemann},
  title = 	 {{ML} and the Address Operator},
  booktitle = 	 {1998 {ACM-SIGPLAN} Workshop on {ML}},
  crossref =	 {ML1998},
  pages =	 {4--13},
  year =	 1998
}

@Proceedings{ML1998,
      title =        "1998 {ACM-SIGPLAN} Workshop on {ML}",
      booktitle =    "1998 {ACM-SIGPLAN} Workshop on {ML}",
      year =         "1998",
      month =     sep,
      address = "Baltimore, Maryland"
}

I'll be glad to send PostScript to anyone who asks.

-- 
Cheers =8-} Mike
Friede, Völkerverständigung und überhaupt blabla
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr