non-functional syntax in a mostly functional language
Author Message
non-functional syntax in a mostly functional language

I'm designing a mostly functional language named DM.  (If you like,
http://www.*-*-*.com/ ~thomasc/dm_paper.ps).  Like ML, DM allows
boxed values so that you can write things like
i = box 5;  [# i is an integer box that starts off containing 5]
i := 6;     [# := is update, i now contains 6]
j = val i;  [# j is 6]

Now normally under such a setup, you have to write things like
k = 3 * (val i) + j + (val i) * (val i);
which can get tiresome if you are doing lots of computations with
boxed values.  Some would say that the solution is simply not to
used boxed values, but sometimes that's not possible.

On the other hand, DM does support overloaded operators, so what
only function on values to automatically val their arguments if
they're boxed.  [ _+ ( a : box Int, b : box Int) = {(val a) + (val b)};
for example.]  This allows you to then write the more compact
k = 3 * i + j + i * i;

I really doubt that this is an original idea, so my question is:
what other mostly functional languages allow this sort of syntax?

[Though I guess the other possibility is that it is original only
in the sense of filling a much needed gap in the literature; if
you know of some simple reason why this is all a horrible idea,
please let me know before I embarrass myself further.]

Many thanks,
-Thomas C

Sat, 09 Apr 2005 04:59:07 GMT
non-functional syntax in a mostly functional language

Quote:

> On the other hand, DM does support overloaded operators, so what
> I'm currently doing is overloading +, *, and other operators that
> only function on values to automatically val their arguments if
> they're boxed.  [ _+ ( a : box Int, b : box Int) = {(val a) + (val b)};
> for example.]  This allows you to then write the more compact
>     k = 3 * i + j + i * i;

> I really doubt that this is an original idea, so my question is:
> what other mostly functional languages allow this sort of syntax?

Algol 68 isn't what most people think of a as functional language but
what you've done has some similarities to the way a loc/ref is
de-referenced in a context-dependent matter to return the value it
contains.

Sun, 10 Apr 2005 08:45:23 GMT
non-functional syntax in a mostly functional language

Quote:
>I'm designing a mostly functional language named DM.  (If you like,
>http://www.hacksaw.org/~thomasc/dm_paper.ps).  Like ML, DM allows
>boxed values so that you can write things like
>     i = box 5;  [# i is an integer box that starts off containing 5]
>     i := 6;     [# := is update, i now contains 6]
>     j = val i;  [# j is 6]

>Now normally under such a setup, you have to write things like
>     k = 3 * (val i) + j + (val i) * (val i);
>which can get tiresome if you are doing lots of computations with
>boxed values.  Some would say that the solution is simply not to
>used boxed values, but sometimes that's not possible.

>On the other hand, DM does support overloaded operators, so what
>only function on values to automatically val their arguments if
>they're boxed.  [ _+ ( a : box Int, b : box Int) = {(val a) + (val b)};
>for example.]  This allows you to then write the more compact
>    k = 3 * i + j + i * i;

>I really doubt that this is an original idea, so my question is:
>what other mostly functional languages allow this sort of syntax?

What you've written means that "+" will work on values if they are
_both_ either boxed or unboxed.  For full generality, you would have
to define 4 different "+"s, for the various box/val combinations.  An
alternative way to express what you want is in terms of subtyping: a
boxed int is a subtype of a value int.  A typical notation is:

box int <: int

You can then go in one of (at least) two ways:

1) You have the subsumption rule:

E |- e: t   t <: t'
---------------------
E |- e: t'

Which means that any expression e of type t can be treated as an
expression of type t', if t is a subtype of t'.

Your "+" would have the type:

int * int -> int

2) You have polymorphism with subtyping constraints.  Your "+" would
then have the type:

forall 'a, 'b. 'a <: int, 'b <: int => 'a * 'b -> int

This means that "+" takes two arguments, each of which must be a
subtype of int (a type is always a subtype of itself), and returns an
int.

- Ed

Mon, 11 Apr 2005 02:51:47 GMT
non-functional syntax in a mostly functional language

Quote:
> Algol 68 isn't what most people think of a as functional language but
> what you've done has some similarities to the way a loc/ref is
> de-referenced in a context-dependent matter to return the value it
> contains.

It's slightly similar, but also very different.

In Algol type languages, all variable mentions get automatically
"dereferenced" (val-ed) except those to the left of an assignment
statement.  For example, C's
int a, b;
a = b;
would be the equivalent of DM's
a = box int 0;
b = box int 0;
a := val b;     [# a := b would be a type error, as would
val a := b ]

The functional language equivalent of this is the way that a name
is replaceable by the value that it names everywhere *except* in
the symbol name slot of a name binding construct:
let x = 5 in lambda x . (x + x)
is not that same as
lambda 5 . ( 5 + 5 )
for example.  From a LISP-ish perspective, name binding constructs
quote their symbol name slot, so that DM's
a = 3;
gets interpreted as something very much like
namebind( ["a], 3 );

What makes the functional language syntax a better choice in my
opinion is that it is much better for a language to occasionally
automatically apply an invertible operation like quoting
rather than almost always applying a non-invertible operation
like dereferencing.

[I would go on about how much effort people in non-functional
languages like C++ then have to go through with things like
const in order to re-express the semantic differences that
their language syntax erases, but this is comp.lang.functional
and I'd just be preaching to the converted.]

Anyway, I just wanted to make it clear that DM does not do any
sort of wholesale, Algol-type dereferencing of everything in
sight.  It merely does the limited dereferencing of arguments
to functions like + and * which wouldn't know what to do with
a boxed value, anyway.

-Thomas C

Mon, 11 Apr 2005 02:58:54 GMT
non-functional syntax in a mostly functional language

Quote:

> In Algol type languages, all variable mentions get automatically
> "dereferenced" (val-ed) except those to the left of an assignment
> statement.  For example, C's
>      int a, b;
>      a = b;
> would be the equivalent of DM's
>      a = box int 0;
>      b = box int 0;
>      a := val b;     [# a := b would be a type error, as would
>                         val a := b ]

I can't ascribe any useful meaning to "val a := b" so it being an
error is no problem, but assuming automatic de-referencing existed then
"a := b" has a reasonable meaning i.e. "a := val b;".  Since it only
has one reasonable meaning then forcing people to write "a := val b;"
when "a := b;" is unambiguous could be viewed as a tad annoying (the
Algol 68 designers clearly thought so :-)

If the syntax for "val" was more terse then perhaps the problem would
not look so bad e.g. borrowing SML's "!" we get "a := !b".
With this change, your motivating example goes from :-

k = 3 * (val i) + j + (val i) * (val i);

to :-

k = 3 * !i + !j + !i * !i;

Whether the "!" is still sufficiently annoying that +, *,
... etc. need to be overloaded to get rid of it is obviously a
judgement call.  I don't find the "!" too bad but then I'm used to SML
so I'm probably biased :-)

I'm *guessing* that if I used DM I would at least initially trip over
the fact that *, +, ... etc. are a special case and I don't need to
use "val" but for other functions I presumably would e.g. assuming x^y
is written as exp(x,y) then given that p, q and r are all boxed I'd
probably write :-

k = p * exp(q, r)

when I should write :-

k = p * exp(val q, val r)

One could get around this by overloading exp (along with all other
mathematical functions that don't have infix syntax) but that is a
slippery slope that you may not want to start down.  Another
alternative is to automatically de-reference but you've already noted
you don't want to go down that road :-)

Quote:
> [I would go on about how much effort people in non-functional
> languages like C++ then have to go through with things like
> const in order to re-express the semantic differences that
> their language syntax erases, but this is comp.lang.functional
> and I'd just be preaching to the converted.]

Algol 68 didn't have a "const" either :-

Algol 68              DM

int x = 10;          x = 10;
int y := 10;         y = box int 10;

The above declaration of y in Algol 68 being the short form of longer
one involving "loc" and even longer one involving "ref".

Mon, 11 Apr 2005 06:53:55 GMT
non-functional syntax in a mostly functional language

Quote:

>I can't ascribe any useful meaning to "val a := b"

What if a has type "box box int"?

Quote:
>so it being an error is no problem, but assuming automatic
>de-referencing existed then "a := b" has a reasonable meaning
>i.e. "a := val b;".  Since it only has one reasonable meaning
>then forcing people to write "a := val b;" when "a := b;" is
>unambiguous could be viewed as a tad annoying (the Algol 68
>designers clearly thought so :-)

Suppose you have

a = box int 0
b = box int 1
c = box a
d = box box int 2

then you say we get automatic dereferencing for

a := b;       (* means "a := val b" *)

c := a;       (* means "c := a" *)

which does *not* need the dereferencing (and in fact doesn't
typecheck if you have it)?  How about automatic dereferencing on
the first argument

c := 3;       (* means "val c := 3" *)

if there are too few levels of indirection instead of two many?
And for that matter, what about

c := b;       (* perhaps means "c := b" *)
c := b;       (* perhaps means "val c := val b" *)

where both are meaningful but different?

What I'm getting at is that special cases are apt to hurt
readability more than they help it.

--

http://www.people.cornell.edu/pages/jmv16/

Mon, 11 Apr 2005 07:13:21 GMT
non-functional syntax in a mostly functional language

Quote:

> >I can't ascribe any useful meaning to "val a := b"

> What if a has type "box box int"?

I meant in the context of the types of a and b being "box int".
In other contexts it could have a useful meaning.

Quote:
> >so it being an error is no problem, but assuming automatic
> >de-referencing existed then "a := b" has a reasonable meaning
> >i.e. "a := val b;".  Since it only has one reasonable meaning
> >then forcing people to write "a := val b;" when "a := b;" is
> >unambiguous could be viewed as a tad annoying (the Algol 68
> >designers clearly thought so :-)

> Suppose you have

>   a = box int 0
>   b = box int 1
>   c = box a
>   d = box box int 2

> then you say we get automatic dereferencing for

>   a := b;       (* means "a := val b" *)

>   c := a;       (* means "c := a" *)

> which does *not* need the dereferencing (and in fact doesn't
> typecheck if you have it)?

The Algol 68 rules for de-referencing are not that de-referencing is
always done on the RHS (as in C) but it is done when it is needed to
make the types match (actually it more complicated than that but I'll
skim over that for now).  So if the types match without any
de-referencing then no de-referencing is done.  Note Algol 68 is
manifestly typed, I'm not sure how this would work in a language which
relies on type inference.

Quote:
>  How about automatic dereferencing on the first argument

>   c := 3;       (* means "val c := 3" *)

Algol 68 would not do that.  The LHS of ":=" is considered a "soft
context" and automatic de-referencing is not done in that context,
unlike the weak, meek, firm and strong contexts.  Note I'm not
advocating this particular model, only noting what happens in it.

Quote:
> if there are too few levels of indirection instead of two many?
> And for that matter, what about

>   c := b;       (* perhaps means "c := b" *)
>   c := b;       (* perhaps means "val c := val b" *)

> where both are meaningful but different?

As noted above, in Algol 68 it would mean the former.

Quote:
> What I'm getting at is that special cases are apt to hurt
> readability more than they help it.

Two different people can look at the same code with one claiming it is
an example of clarity the other of opacity.  I find the explicit "!"
required in SML to be workable but I also know people (particularly
those used to Algol-style de-referencing) who find it clumsy.

Mon, 11 Apr 2005 07:50:39 GMT
non-functional syntax in a mostly functional language

Quote:

> An alternative way to express what you want is in terms of subtyping: a
> boxed int is a subtype of a value int.  A typical notation is:

>        box int <: int

But note that both of your suggestions generally require some form of
runtime dispatch, since the intrusive nature of subtyping precludes
proper specialization at the call site. Consider the innocent function

fun f x = x + 3

At the point of application of + it is statically unknown whether x is a
reference or not, because subtyping allows both, an int or a box int,
being passed to f.

Consequently, either the + operator has to look at the runtime type of
each of its arguments to dereference it if necessary, or the proper
specialised + implementation has to be passed in as a hidden argument
(in the style of Haskell's type class dictionaries).

- Andreas

--

"Computer games don't affect kids; I mean if Pac Man affected us
as kids, we would all be running around in darkened rooms, munching
magic pills, and listening to repetitive electronic music."
- Kristian Wilson, Nintendo Inc.

Mon, 11 Apr 2005 17:15:12 GMT
non-functional syntax in a mostly functional language

Quote:

>> An alternative way to express what you want is in terms of subtyping: a
>> boxed int is a subtype of a value int.  A typical notation is:

>>        box int <: int

>But note that both of your suggestions generally require some form of
>runtime dispatch, since the intrusive nature of subtyping precludes
>proper specialization at the call site. Consider the innocent function

>    fun f x = x + 3

>At the point of application of + it is statically unknown whether x is a
>reference or not, because subtyping allows both, an int or a box int,
>being passed to f.

>Consequently, either the + operator has to look at the runtime type of
>each of its arguments to dereference it if necessary, or the proper
>specialised + implementation has to be passed in as a hidden argument
>(in the style of Haskell's type class dictionaries).

of all possibilities is more verbose, and has a similar set of
problems.  How would you handle the example you gave w/o subtyping but

fun f x = x + 3

boxed or not in order to resolve the overloading, or you need to pass
a set of "+" operators implicitly and then resolve the overloading at
run time.  Equivalently, you can decide never to infer a boxed type
without the presence of an explicit type annotation.  This would allow
optimization to use a specialized "+" without any need for run-time
dispatching as well.

It just seems that putting subtyping into the language is less messy
all possible combinations of parameters.

- Ed

- Show quoted text -

Quote:
>    - Andreas

>--

>"Computer games don't affect kids; I mean if Pac Man affected us
> as kids, we would all be running around in darkened rooms, munching
> magic pills, and listening to repetitive electronic music."
> - Kristian Wilson, Nintendo Inc.

Mon, 11 Apr 2005 23:42:38 GMT
non-functional syntax in a mostly functional language

Quote:

> >> An alternative way to express what you want is in terms of subtyping: a
> >> boxed int is a subtype of a value int.  A typical notation is:

> >>        box int <: int

[ ... snip ... ]

Quote:

> It just seems that putting subtyping into the language is less messy
> all possible combinations of parameters.

Indeed, overloading is just as messy (if not more so) than subtyping
-- as far as implementing this particular facet of your language is
concerned.  (Subtyping comes with its own additional problems -- namely
the simple fact that a mutable ref cell type cannot really be
considered a subtype of the corresponding immutable value type.)

The least messy solution is to refrain from putting into the language
the kind of cuteness that you are after.  In a language where destructive
updates are the exception, I am more than happy to write explicit dereferencing
operators in those few situations where I need them.  After all, they alert
me (the program author) as well as you (the maintainer who has to read the
code in 2 years) that a side-effecting operation (fetch from a mutable variable)
is being performed.  Since semantically this is quite different from a reference
to an immutable value, it should also look different (IMNSHO).
For mutable state, timing of fetch operations is essential.  It is a Really Bad
Idea(tm) to let the compiler implicitly insert fetch operations because it will
quickly become totally non-obvious where and when the fetch operation will
take place.

--
-Matthias

Tue, 12 Apr 2005 00:39:33 GMT
non-functional syntax in a mostly functional language

Quote:

> How would you handle the example you gave w/o subtyping but

I wouldn't. ;-) You can take a simple form of overloading that simply
flags this as ambiguous. It's not so simple to rule out in a subtyping
framework.

But no criticism intended, I just wanted to point out the operational
implications of your suggestion, because I thought they might not be
obvious to everybody.

Quote:
> It just seems that putting subtyping into the language is less messy
> all possible combinations of parameters.

Not so sure about that. In any case, IMHO trying to automatize
dereferencing by type system magic is an ill-advised idea to start
with...

- Andreas

--

"Computer games don't affect kids; I mean if Pac Man affected us
as kids, we would all be running around in darkened rooms, munching
magic pills, and listening to repetitive electronic music."
- Kristian Wilson, Nintendo Inc.

Tue, 12 Apr 2005 00:57:20 GMT
non-functional syntax in a mostly functional language

Quote:

> (Subtyping comes with its own additional problems -- namely
> the simple fact that a mutable ref cell type cannot really be
> considered a subtype of the corresponding immutable value type.)

?? C++ does this with no pb.

(from http://merd.net/inoutness.html)

Simple examples in C++

In C++, you can give a "int *" where a "int * const" is
expected. This is easily understandable: you have an object you
are allowed to modify, and you give it to a function which is

On contrary, you can't give a "int * const" where a "int *" is expected.

Const subtyping rule

const A is a supertype of A

A is a subtype of const A

The real problem with reference and subtyping, is:

ref(A) < ref(B)  if  A < B

which is plain wrong (ref is invariant)

Tue, 12 Apr 2005 01:02:13 GMT
non-functional syntax in a mostly functional language

Quote:

> > It just seems that putting subtyping into the language is less
> > resolution for all possible combinations of parameters.

> Not so sure about that. In any case, IMHO trying to automatize
> dereferencing by type system magic is an ill-advised idea to start
> with...

In a language with mutable variables (like Scheme) you do exactly this
analysis to distinguish between mutable and immutable closed-over
variables when building closures. It's easy and fast to compute, too;
you can identify everywhere you need to box and unbox variables with a
single-pass algorithm.

Eg:

(define foo
(let ((x 1)  ;; immutable and unboxed
(y 2)) ;; mutable and boxed
(lambda ()
(begin (set! y (+ y 1))  ;; y gets deref'd automatically
(+ x y)))))       ;; x doesn't need to be deref'd

--
Neel Krishnaswami

Tue, 12 Apr 2005 01:31:06 GMT
non-functional syntax in a mostly functional language

Quote:

> > (Subtyping comes with its own additional problems -- namely
> > the simple fact that a mutable ref cell type cannot really be
> > considered a subtype of the corresponding immutable value type.)

> ?? C++ does this with no pb.

The whole language of C++ is one huge "pb.", IMNSHO.

--
-Matthias

Tue, 12 Apr 2005 03:46:36 GMT
non-functional syntax in a mostly functional language

Quote:

> > Not so sure about that. In any case, IMHO trying to automatize
> > dereferencing by type system magic is an ill-advised idea to start
> > with...

> In a language with mutable variables (like Scheme) you do exactly this
> analysis to distinguish between mutable and immutable closed-over
> variables when building closures.

No, you don't.  The Scheme situation is quite a bit simpler because there
are no first-class references in the surface language.

--
-Matthias

Tue, 12 Apr 2005 03:43:02 GMT

 Page 1 of 4 [ 57 post ] Go to page: [1] [2] [3] [4]

Relevant Pages