Return type of procedures?

Return type of procedures?

[John Max Skaller]

I am designing a programming language (the compiler is written
in ocaml) which is a procedural language with 'purely functional'
expressions (using eager evaluation). Function closures can
access their context, which procedural statements my change between
building the closure and evaulating it. Procedural closures may
mutate their environment.

Procedures and functions are defined with distinct keywords
'procedure' and 'function'. I have given a procedure the 
functional type

	'a -> unit (where 'a may sensibly be 'unit')

whereas functions have signature

	'a -> 'b

where either 'a or 'b may be unit. Note that if 'a is unit, the
function is not necessarily constant, since it may depend on
the environment. OTOH, a function with 'b as unit is farily
useless.

However, as it stands, the type system fails to achieve
separation of functions and procedures:

	procedure p: unit -> unit
	function f: unit -> unit
	f (p ())  // woops! 

Here is an expression (functional code) which has taken the result
of calling a procedure (unit) as an argument.

Proposal: just as unit is the trivial product (tuple, terminal object),
so
we say 'void' is the trivial sum (initial object), and make procedures
have the signature

	procedure f: unit -> void

Now, procedures cannot be used 'in' expressions anywhere,
provided we do not allow the argument of a function or procedure
to have 'void' type. We can also treat procedures uniformly
from a typing view point.

Comments?


-- 
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: Return type of procedures?

[David McClain]

Is it just me? I am quite troubled by the concepts you propose in a new
language. You chose to use Caml for very good reasons. Why would you do away
with things like immutable global environments for your users? Procedures
altering the environment in such a way as to cause a function to behave
differently on separate invocations seems like it is going against the basic
tenets of FP. The FP approach makes it so easy to reason about the behavior
of programs. Partial evaluation allows customization of functions when
needed. Am I missing something here?

- David McClain, Sr. Scientist, Raytheon Systems Co., Tucson, AZ

-----Original Message-----
From: John Max Skaller <skaller@maxtal.com.au>
To: caml-list@inria.fr <caml-list@inria.fr>
Date: Monday, August 21, 2000 2:33 PM
Subject: Return type of procedures?


>I am designing a programming language (the compiler is written
>in ocaml) which is a procedural language with 'purely functional'
>expressions (using eager evaluation). Function closures can
>access their context, which procedural statements my change between
>building the closure and evaulating it. Procedural closures may
>mutate their environment.
>
>Procedures and functions are defined with distinct keywords
>'procedure' and 'function'. I have given a procedure the
>functional type
>
> 'a -> unit (where 'a may sensibly be 'unit')
>
>whereas functions have signature
>
> 'a -> 'b
>
>where either 'a or 'b may be unit. Note that if 'a is unit, the
>function is not necessarily constant, since it may depend on
>the environment. OTOH, a function with 'b as unit is farily
>useless.
>
>However, as it stands, the type system fails to achieve
>separation of functions and procedures:
>
> procedure p: unit -> unit
> function f: unit -> unit
> f (p ())  // woops!
>
>Here is an expression (functional code) which has taken the result
>of calling a procedure (unit) as an argument.
>
>Proposal: just as unit is the trivial product (tuple, terminal object),
>so
>we say 'void' is the trivial sum (initial object), and make procedures
>have the signature
>
> procedure f: unit -> void
>
>Now, procedures cannot be used 'in' expressions anywhere,
>provided we do not allow the argument of a function or procedure
>to have 'void' type. We can also treat procedures uniformly
>from a typing view point.
>
>Comments?
>
>
>--
>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: Return type of procedures?

[John Max Skaller]

David McClain wrote:
> 
> Is it just me? I am quite troubled by the concepts you propose in a new
> language. You chose to use Caml for very good reasons. Why would you do away
> with things like immutable global environments for your users? Procedures
> altering the environment in such a way as to cause a function to behave
> differently on separate invocations seems like it is going against the basic
> tenets of FP. The FP approach makes it so easy to reason about the behavior
> of programs. Partial evaluation allows customization of functions when
> needed. Am I missing something here?

Yes: I am required to interface to an existing object oriented
event driven system. There is an intrinsic requirement to be able
to modify 'state'. In addition, I have to provide a language that
other people (familiar with C/C++) can use.

But the other thing you miss is that even in ocaml, environments
are NOT immutable: there are mutable fields, and thus mutable
data structures like Hashtbl. The fact is, some things are easier
to express in a stateful manner than a functional one.


-- 
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: Return type of procedures?

[Pierre Weis]

> But the other thing you miss is that even in ocaml, environments
> are NOT immutable: there are mutable fields, and thus mutable
> data structures like Hashtbl. The fact is, some things are easier
> to express in a stateful manner than a functional one.

Strictly speaking, environments in Caml ARE immutable: there is no way
to change the binding of an identifier. What can be mutated are
designated sub-parts of values bound to identifiers.

Pierre Weis

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

RE: Return type of procedures?

[Manuel Fahndrich]

We are having a related problem with unit and void in a language we design
at MSR called Vault. The problem we ran into was with polymorphism. If you
have a polymorphic function in your language (such as the identity id : 'a
-> 'a), you could still end up in the situation you are trying to avoid,
namely by saying:

	id (p ()),

where p : unit -> void

In this example, one could check the instance type, but in general, one can
hide these instances inside other polymorphic functions and procedures and
that approach is impractical.

-Manuel


-----Original Message-----
From: John Max Skaller [mailto:skaller@maxtal.com.au]
Sent: Monday, August 21, 2000 10:17 AM
To: caml-list@inria.fr
Subject: Return type of procedures?


I am designing a programming language (the compiler is written
in ocaml) which is a procedural language with 'purely functional'
expressions (using eager evaluation). Function closures can
access their context, which procedural statements my change between
building the closure and evaulating it. Procedural closures may
mutate their environment.

Procedures and functions are defined with distinct keywords
'procedure' and 'function'. I have given a procedure the 
functional type

	'a -> unit (where 'a may sensibly be 'unit')

whereas functions have signature

	'a -> 'b

where either 'a or 'b may be unit. Note that if 'a is unit, the
function is not necessarily constant, since it may depend on
the environment. OTOH, a function with 'b as unit is farily
useless.

However, as it stands, the type system fails to achieve
separation of functions and procedures:

	procedure p: unit -> unit
	function f: unit -> unit
	f (p ())  // woops! 

Here is an expression (functional code) which has taken the result
of calling a procedure (unit) as an argument.

Proposal: just as unit is the trivial product (tuple, terminal object),
so
we say 'void' is the trivial sum (initial object), and make procedures
have the signature

	procedure f: unit -> void

Now, procedures cannot be used 'in' expressions anywhere,
provided we do not allow the argument of a function or procedure
to have 'void' type. We can also treat procedures uniformly
from a typing view point.

Comments?


-- 
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: Return type of procedures?

[John Max Skaller]

Manuel Fahndrich wrote:
> 
> We are having a related problem with unit and void in a language we design
> at MSR called Vault. The problem we ran into was with polymorphism. If you
> have a polymorphic function in your language (such as the identity id : 'a
> -> 'a), you could still end up in the situation you are trying to avoid,
> namely by saying:
> 
>         id (p ()),
> 
> where p : unit -> void
> 
> In this example, one could check the instance type, but in general, one can
> hide these instances inside other polymorphic functions and procedures and
> that approach is impractical.

My language supports polymorhpism, but only at the  module level:
if you want parametric polymorphism, you must put the function
in a module, currently the slightly hacked:

	module ident[<T>] { id: T-> T; }

This means that when the function is used, the module must
be instantiated:

	x = ident[<void>].id (y);

and the error is detected at instantiation time.
The instantiation is not done yet, because it is currently
a 'hack' in that it takes a listr of C++ style types as
arguments, instead of a module: this is because I haven't
defined any concept of 'interface=signature' yet.
Partly, that is because I'm unhappy with the fact that
functions are called with 'positional' arguments,
whereas modules would be called with 'named' arguments:

	functor ident[<type T;>] { id: T-> T; }
	x = ident[<T=void>].id(y);

Here, the contents of the [<>] brackets are a 'module expression',
which could be an anonymous module (as shown) or a named one
(not shown), and I have yet to figure out the syntax to use
so these are handled regularly. I note that functor application 
should be transparent, given:

	module Int { type t = int; }

we should be able to write

	(ident Int) . id y

as for any 'other' function application (where . binds
tighter than application).

-- 
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: Return type of procedures?

[Manuel Fahndrich]

John Max Skaller wrote:

> My language supports polymorhpism, but only at the  module level:
> if you want parametric polymorphism, you must put the function
> in a module, currently the slightly hacked:
>
>	module ident[<T>] { id: T-> T; }
>
>This means that when the function is used, the module must
>be instantiated:
>
>	x = ident[<void>].id (y);
>
>and the error is detected at instantiation time.

Again, in this example, it is easy to detect, but in general it might not
be. I'm assuming I can write something like the following in your language:

module Foo[<T>] { bar: (unit -> T) -> void; } =
  struct

    func localid(x : T) { return(x); }

    proc bar(f : unit -> T) {

      let x:T = local_id(f())
      in
      return();
    }

  end


Now suppose you have a procedure p : unit -> void and I do

  Foo[<void>].bar(p);

The fact that you are instantiating 'localid' with void is no longer
obvious. In the worst case you have to fully instantiate the entire module,
including every single local definition, nested module instantiations etc...
essentially C++ template application, in order to detect the violation.

To me it looks like you want to have two distinct arrow constructors, one
for functions  -f> and one for procedures -p>. Then you can't go wrong.

-Manuel