Clean function declaration
Author Message
Clean function declaration

Recently I downloaded the Clean compiler, and the Clean book PDFs, from
< http://www.*-*-*.com/ ~clean/>. I triedd doing the exercises, and of
course, everything breaks down at the second one...

Exercise 2 (chapter l.9) asks you to define a function to raise a number
to a power, then to define a function to square a number, and to use
that function to square 128. Fine. Of course, there's a ^ function built
in, but I decide to go all exercistic and define this:

module ex_1`9`2

import StdEnv

Start = square 128

square x  = power x 2

power x n
| n==1      = x
| otherwise = x * power x (n-1)

Still fine, right? Ok, but here's where it started to fall to pieces:

I considered that chapter 1 had also dealt with function declarations,
and decided that it would be nice to add declarations to this module,
for completeness' sake. So I write this:

module ex_1`9`2

import StdEnv

power :: a Int -> a | * a

Start = square 128

square x  = power x 2

power x n
| n==1      = x
| otherwise = x * power x (n-1)

After all, power is a function; it takes one number and an Int, and for
the first number, all we care about is that it can be multiplied with
itself. Right? Right. Except that the Clean compiler tells me:

Syntax error [ex_1`9`2.icl,8,<non-type-def>]:
"power" function name doesn't match function type def

Yeck. And it won't tell me why not. To add insult to injury, when I ask
it to list the types it infers itself, it comes up with both

power (Int) :: Int Int -> Int;

and

power :: a Int -> a | * a;

Ok, so I can understand why it would have both of these. The first
declaration is the tightest one that can be inferred (since I use it
only on Ints, after all); and the second one is the minimum required.

But why, if the compiler can infer this type itself, won't it accept it
when I type it in? It can't be that I, as a mere mortal, must use the
stricter declaration. I tried that; it won't accept that one, either,
giving the same error message.

So what gives? How do I get the Clean compiler to accept my own function
declarations, do I have to wait until chapter 42 before these things are
explained (and if so, why does chapter 1 mention them), or should I give
up on declarations altogether?

Richard

Sat, 24 Dec 2005 23:11:27 GMT
Clean function declaration

Quote:

> Recently I downloaded the Clean compiler, and the Clean book PDFs, from
> <http://www.cs.kun.nl/~clean/>. I triedd doing the exercises, and of
> course, everything breaks down at the second one...

Comin' over from the dark side, are ya? ;-)

Quote:

> Exercise 2 (chapter l.9) asks you to define a function to raise a number
> to a power, then to define a function to square a number, and to use
> that function to square 128. Fine. Of course, there's a ^ function built
> in, but I decide to go all exercistic and define this:

>   module ex_1`9`2

>   import StdEnv

>   Start = square 128

>   square x  = power x 2

>   power x n
>     | n==1      = x
>     | otherwise = x * power x (n-1)

OK. You should deal with the case where the power is 0 or < 0 (but I
know you know that).

Quote:
> Still fine, right? Ok, but here's where it started to fall to pieces:

> I considered that chapter 1 had also dealt with function declarations,
> and decided that it would be nice to add declarations to this module,
> for completeness' sake. So I write this:

>   module ex_1`9`2

>   import StdEnv

>   power :: a Int -> a | * a

Ah. Trying to prototype, eh?
Alas, that's not how it's done in Clean. In Clean, if you're creating a
module, you put function declarations in a separate .dcl file (see
chapter 2 of the language report).

In any event, you do not separate function declaration and function
definition in an implementation module.

Quote:

>   Start = square 128

>   square x  = power x 2

In other words, put this *here* and all will be well.

power :: a Int -> a | * a

- Show quoted text -

Quote:
>   power x n
>     | n==1      = x
>     | otherwise = x * power x (n-1)

> After all, power is a function; it takes one number and an Int, and for
> the first number, all we care about is that it can be multiplied with
> itself. Right? Right. Except that the Clean compiler tells me:

>   Syntax error [ex_1`9`2.icl,8,<non-type-def>]:
>      "power" function name doesn't match function type def

> Yeck. And it won't tell me why not. To add insult to injury, when I ask
> it to list the types it infers itself, it comes up with both

>   power (Int) :: Int Int -> Int;

> and

>   power :: a Int -> a | * a;

> Ok, so I can understand why it would have both of these. The first
> declaration is the tightest one that can be inferred (since I use it
> only on Ints, after all); and the second one is the minimum required.

> But why, if the compiler can infer this type itself, won't it accept it
> when I type it in? It can't be that I, as a mere mortal, must use the
> stricter declaration. I tried that; it won't accept that one, either,
> giving the same error message.

> So what gives? How do I get the Clean compiler to accept my own function
> declarations, do I have to wait until chapter 42 before these things are
> explained (and if so, why does chapter 1 mention them), or should I give
> up on declarations altogether?

> Richard

And there ya go! (This ain't C, after all.)

HTH,
--ag

Sun, 25 Dec 2005 01:02:25 GMT
Clean function declaration

Quote:

> > Recently I downloaded the Clean compiler, and the Clean book PDFs, from
> > <http://www.cs.kun.nl/~clean/>. I triedd doing the exercises, and of
> > course, everything breaks down at the second one...

> Comin' over from the dark side, are ya? ;-)

Nah, merely trying to paint in yellow as well as in blue :-)

Quote:
> > Exercise 2 (chapter l.9) asks you to define a function to raise a number
> > to a power, then to define a function to square a number, and to use
> > that function to square 128. Fine. Of course, there's a ^ function built
> > in, but I decide to go all exercistic and define this:

> >   module ex_1`9`2

> >   import StdEnv

> >   Start = square 128

> >   square x  = power x 2

> >   power x n
> >     | n==1      = x
> >     | otherwise = x * power x (n-1)

> OK. You should deal with the case where the power is 0 or < 0 (but I
> know you know that).

Yup. Easy enough, but it complicates the declaration even more.

Quote:
> >   module ex_1`9`2

> >   import StdEnv

> >   power :: a Int -> a | * a

> Ah. Trying to prototype, eh?
> Alas, that's not how it's done in Clean. In Clean, if you're creating a
> module, you put function declarations in a separate .dcl file (see
> chapter 2 of the language report).

Yes, if you're defining a module for use in a larger program. It seemed
somewhat overkill to do so for one example...

Quote:
> In any event, you do not separate function declaration and function
> definition in an implementation module.

Pity - I like the way that provides you with a nice precis of the file,
the way it's done in C.

Quote:
> >   Start = square 128

> >   square x  = power x 2

> In other words, put this *here* and all will be well.

Right. Done. And thank you, that works. I've now got

module ex_1`9`2

import StdEnv

Start = square 128

square :: a -> a | *,/ a
square x  = power x 2

power :: a Int -> a | *,/ a
power x n
| n==1      = x
| n <1      = power x (n+1) / x
| otherwise = power x (n-1) * x

(Does this break tail recursion elimination, btw?)

I tried both

square :: a -> a | power a

and

square :: a -> a

but neither of them works - but at least in these cases it comes up with
a clear, plausible reason of why it doesn't accept them. Now all I have
to do is make power a class symbol so I can use it in the declaration of
square, but AFAICT that's only explained in chapter 2...

Quote:
> And there ya go! (This ain't C, after all.)

Aw shucks. All languages should be C ;->

Richard

Sun, 25 Dec 2005 21:22:17 GMT
Clean function declaration

Quote:

>>In any event, you do not separate function declaration and function
>>definition in an implementation module.

> Pity - I like the way that provides you with a nice precis of the file,
> the way it's done in C.

It's a good thing to have a separation of interface and implementation.
BUT it's very bad to have the programmer write both. The compiler should
automatically generate interface from the implementation (where the
implementation may have annotations about what to export into the public
interface and what to keep "under the hood").

I've seen this done, and it works marvellously. No more header file
inconsistencies...

Regards,
Jo

Sun, 25 Dec 2005 22:55:00 GMT
Clean function declaration

Quote:

>   power x n
>     | n==1      = x
>     | n <1      = power x (n+1) / x
>     | otherwise = power x (n-1) * x

> (Does this break tail recursion elimination, btw?)

Yes.
There's a division resp. multiplication *after* the recursive call.

You can always eliminate this kind of problem by using a helper function
with an accumulator:

power x n = exp x n 1

exp x n acc
| n == 1 = acc
| n < 1  = exp x (n + 1) (acc / x)
| n > 1  = exp x (n - 1) (acc * x)

Regards,
Jo

Sun, 25 Dec 2005 22:56:09 GMT
Clean function declaration
[snip]

Quote:

> Yes, if you're defining a module for use in a larger program. It seemed
> somewhat overkill to do so for one example...

Granted.

Quote:
>>In any event, you do not separate function declaration and function
>>definition in an implementation module.

> Pity - I like the way that provides you with a nice precis of the file,
> the way it's done in C.

>>>  Start = square 128

>>>  square x  = power x 2

>>In other words, put this *here* and all will be well.

> Right. Done. And thank you, that works. I've now got

>   module ex_1`9`2

>   import StdEnv

>   Start = square 128

>   square :: a -> a | *,/ a
>   square x  = power x 2

>   power :: a Int -> a | *,/ a
>   power x n
>     | n==1      = x
>     | n <1      = power x (n+1) / x
>     | otherwise = power x (n-1) * x

> (Does this break tail recursion elimination, btw?)

> I tried both

>   square :: a -> a | power a

> and

>   square :: a -> a

> but neither of them works - but at least in these cases it comes up with
> a clear, plausible reason of why it doesn't accept them. Now all I have
> to do is make power a class symbol so I can use it in the declaration of
> square, but AFAICT that's only explained in chapter 2...

Which you'll get to soon (if not already...)

Quote:

>>And there ya go! (This ain't C, after all.)

> Aw shucks. All languages should be C ;->

B-o-r-i-n-g.... :-(

Seriously though, when at the learning stage, it is often useful to
_not_ explicitly give your functions types -- and see what type the
compiler infers (and, naturally, how that compares to your expectation).

Cheers,
--ag

--
Artie Gold -- Austin, Texas

Mon, 26 Dec 2005 00:20:47 GMT
Clean function declaration

Quote:

> >   power x n
> >     | n==1      = x
> >     | n <1      = power x (n+1) / x
> >     | otherwise = power x (n-1) * x

> > (Does this break tail recursion elimination, btw?)

> Yes.
> There's a division resp. multiplication *after* the recursive call.

Odd, though, that the compiler isn't capable of optimising that away.
It's easily provable that a*b==b*a, and that a/b==(the proper kind of
1)/b*a, except for overflow, so perhaps a decent optimiser _could_
change things around like that. Or isn't it allowed to?

Quote:
> You can always eliminate this kind of problem by using a helper function
> with an accumulator:

> power x n = exp x n 1

> exp x n acc
>    | n == 1 = acc
>    | n < 1  = exp x (n + 1) (acc / x)
>    | n > 1  = exp x (n - 1) (acc * x)

Yech.

I really want to rewrite it

power x n
| n==1      = x
| n <1      = 1/x * power x (n+1)
| otherwise =  x  * power x (n-1)

but that would restrain x to Int unnecessarily. I'm sure this could be
overcome by creating a polymorphic function of some sort, but I think
I'll leave that for when I'm a bit further along in the book.

Richard

Mon, 26 Dec 2005 19:39:52 GMT
Clean function declaration
Richard Bos wrote (snipped):

Quote:
> Odd, though, that the compiler isn't capable of optimising that away.
> It's easily provable that a*b==b*a, and that a/b==(the proper kind of
> 1)/b*a, except for overflow, so perhaps a decent optimiser _could_
> change things around like that. Or isn't it allowed to?

It's certainly not true for floats.  Optimisers which silently reorder
numeric operations to produce slightly different results are a pain in
the neck.

I think the TeX program has some functions for simulating various
multiprecision arithmetic operations in Pascal, and at one point the
code has to be deliberately obfuscated to prevent over-enthusiastic
optimisers mucking it up.

Mon, 26 Dec 2005 19:45:06 GMT
Clean function declaration

...

Quote:
>>>    | n <1      = power x (n+1) / x
>>>    | otherwise = power x (n-1) * x

>>>(Does this break tail recursion elimination, btw?)

>>Yes.
>>There's a division resp. multiplication *after* the recursive call.

> Odd, though, that the compiler isn't capable of optimising that away.
> It's easily provable that a*b==b*a, and that a/b==(the proper kind of
> 1)/b*a, except for overflow, so perhaps a decent optimiser _could_
> change things around like that. Or isn't it allowed to?

Of course it is not allowed, decent or not. Nobody can *prove* that your
multiplication is commutative in this context since you can define your
own class * .

Besides, the commutativity is not enough, you need associativity as well
in order to apply some optimizations in the style of Burstall&Darlington
with accumulating parameters, unless I am mistaken...

I am afraid that Joachim Durchholz proposal has a little bug, though, look
what happens if n==1.

Quote:
>>You can always eliminate this kind of problem by using a helper function
>>with an accumulator:

>>power x n = exp x n 1

>>exp x n acc
>>   | n == 1 = acc
>>   | n < 1  = exp x (n + 1) (acc / x)
>>   | n > 1  = exp x (n - 1) (acc * x)

=======

Quote:
> I really want to rewrite it

>   power x n
>     | n==1      = x
>     | n <1      = 1/x * power x (n+1)
>     | otherwise =  x  * power x (n-1)

> but that would restrain x to Int unnecessarily. I'm sure this could be
> overcome by creating a polymorphic function of some sort, but I think
> I'll leave that for when I'm a bit further along in the book.

Actually what do you really want?  You want to have a generic power for any
x and integral n? Je vous en prie. Overload your "1". Actually you don't even
have to do it. StdInt, StdReal, etc., libraries, which use StdOverloaded,
do it for you. Please, read them, you will find  "class zero", "class one" etc.
with appropriate instances in Int and Real.

The rest can be easily polymorphi...hmhm...sized. Here you are the linear
iterator, similar to yours, optimized by JD, but also a dichotomic one,
with logarithmic complexity. The stuff below will work with complex numbers etc.

On the other hand, it does not contain the case with n negative, since then
you get out of the Ring category, you need Field, and *just* iterations are
not sufficient. You may easily add by hand x^(-n) = 1/x^n.

// Linear Iterator
iterOp :: (!a !a -> a) !Int !a !a -> a
iterOp _  0 _ buf = buf
iterOp op n x buf = iterOp op (n-1) x (op x buf)

// Dichotomic iterator for associative operators.
itOp :: (!a !a -> a) !Int !a !a -> a
itOp _  0 _ buf = buf
itOp op n x buf | isOdd n = itOp op (n-1) x (op x buf)
= itOp op (n / 2) (op x x) buf

// (Int) Power by linear iteration
pow :: !a !Int -> a | *,one a
pow x n = iterOp (*) n x one

// (Int) Power by binary iteration
fpow :: !a !Int -> a | *,one a
fpow x n = itOp (*) n x one

Jerzy Karczmarczuk

Mon, 26 Dec 2005 20:19:09 GMT
Clean function declaration

Quote:
Joachim Durchholz writes:
> It's a good thing to have a separation of interface and
> implementation. BUT it's very bad to have the programmer write
> both. The compiler should automatically generate interface from
> the implementation (where the implementation may have annotations
> about what to export into the public interface and what to keep
> "under the hood").

That's a matter of taste. I like having the definition of a
module's external interface in a separate file that's written
by the programmer. It makes you better aware when you're
changing the interface. It makes it easier to track changes
to the interface and allows different implementations for
one interface.

Then there's the technicality of cyclic imports, but that's
just for compiler writers to worry about.

As for inconsistencies between interface and implementation:
in Clean < 2 this was a big problem, because you had to repeat
all definitions from the declaration module in your
implementation module. In current versions you only have this
obligation for function types.

Cheers,

Ronny Wichers Schreur

Mon, 26 Dec 2005 21:24:53 GMT
Clean function declaration

Quote:

> ...

> >>>    | n <1      = power x (n+1) / x
> >>>    | otherwise = power x (n-1) * x

> >>>(Does this break tail recursion elimination, btw?)

> >>Yes.
> >>There's a division resp. multiplication *after* the recursive call.

> > Odd, though, that the compiler isn't capable of optimising that away.
> > It's easily provable that a*b==b*a, and that a/b==(the proper kind of
> > 1)/b*a, except for overflow, so perhaps a decent optimiser _could_
> > change things around like that. Or isn't it allowed to?

> Of course it is not allowed, decent or not. Nobody can *prove* that your
> multiplication is commutative in this context since you can define your
> own class * .

Ah, yes, I'd overlooked that.

Quote:
> > I really want to rewrite it

> >   power x n
> >     | n==1      = x
> >     | n <1      = 1/x * power x (n+1)
> >     | otherwise =  x  * power x (n-1)

> > but that would restrain x to Int unnecessarily. I'm sure this could be
> > overcome by creating a polymorphic function of some sort, but I think
> > I'll leave that for when I'm a bit further along in the book.

> Actually what do you really want?  You want to have a generic power for any
> x and integral n? Je vous en prie. Overload your "1".

fortran... and anyway, the first chapter specifically said that you can
only use 1 for Int and 1.0 for Real.

Quote:
> Actually you don't even
> have to do it. StdInt, StdReal, etc., libraries, which use StdOverloaded,
> do it for you. Please, read them, you will find  "class zero", "class one"
> etc. with appropriate instances in Int and Real.

Oh... so you're not actually overloading 1, you're creating a new kind
of object and overloading _that_ to the various kinds of 1. That makes
more sense.

Quote:
> // Linear Iterator
> iterOp :: (!a !a -> a) !Int !a !a -> a
> iterOp _  0 _ buf = buf
> iterOp op n x buf = iterOp op (n-1) x (op x buf)

I think this is slightly out of my league, as yet... not far out, but
just beyond my grasp. I think I can see what its intention is, and I
think I'll be able to figure out exactly what it does after I've
finished the next chapter or so.

Richard

Tue, 27 Dec 2005 19:09:57 GMT

 Page 1 of 1 [ 11 post ]

Relevant Pages