What's the ICFP Programming contest?

What's the ICFP Programming contest?

[tmoran]

What's the ICFP programming contest to be held this weekend?
http://www.icfpcontest.org

Re: What's the ICFP Programming contest?

[Preben Randhol]

tmoran@acm.org wrote:
> What's the ICFP programming contest to be held this weekend?
> http://www.icfpcontest.org

According to the FAQ they will announce it when it starts as I can
understand it.

-- 
Ada95 is good for you.
http://www.crystalcode.com/codemage/MainMenu/Coding/Ada/IntroducingAda.php

Re: What's the ICFP Programming contest?

[Michael Erdmann]

Preben Randhol wrote:
> tmoran@acm.org wrote:
> 
>>What's the ICFP programming contest to be held this weekend?
>>http://www.icfpcontest.org
> 
> 
> According to the FAQ they will announce it when it starts as I can
> understand it.
> 

Every thing ready?

- send your wife on a trip for the weekend
- coffee maschine checked
- Your favourite algorithm handbook handy
- Enough free disk space
- .....


Upps, i forgot to send my wife on a trip!

Any way, is some one or a team from the Ada community
attenending the contents?
I would be interested, but next time, when i got position one
on my check list fixed before the contentest starts!


Michael

Re: What's the ICFP Programming contest?

[tmoran]

>>>http://www.icfpcontest.org
>Any way, is some one or a team from the Ada community
>attenending the contents?
  I see it's a race car around a track simulation.  At any step you
(your program) can accelerate, brake, turn, and they supply equations
for where you'll be next.  The object is to get around the arbitrarily
shaped) track to the goal fastest, without going into the fence enroute.
Sounds like an Ada type of problem.

Re: What's the ICFP Programming contest?

[Michael Erdmann]

tmoran@acm.org wrote:
>>>>http://www.icfpcontest.org
>>
>>Any way, is some one or a team from the Ada community
>>attenending the contents?
> 
>   I see it's a race car around a track simulation.  At any step you
> (your program) can accelerate, brake, turn, and they supply equations
> for where you'll be next.  The object is to get around the arbitrarily
> shaped) track to the goal fastest, without going into the fence enroute.
> Sounds like an Ada type of problem.

I guess this is a nice optimazation problem. Theoretically it
could be solved by brutal force to find the best route.

Re: What's the ICFP Programming contest?

[Hyman Rosen]

Michael Erdmann wrote:
> I guess this is a nice optimazation problem. Theoretically it
> could be solved by brutal force to find the best route.

The ICFP contests are always like that. I doubt that pure brute
force is the way to go, since the answers have to be submitted
by Monday! The model uses fixed point arithmetic, and the rules
give an exact description of the representation format and how
arithmetic works. I don't know enough about Ada to know whether
this maps directly onto an Ada fixd point type.

The contest is unique this year in that you run your program
yourself, on your own computer, and just produce a sequence of
driving instructions. Then the contest organizers race the cars,
and the fastest performer wins.

Re: What's the ICFP Programming contest?

[tmoran]

> The model uses fixed point arithmetic, and the rules
> give an exact description of the representation format and how
> arithmetic works. I don't know enough about Ada to know whether
> this maps directly onto an Ada fixd point type.
 They use truncating long integer arithmetic instead of rounding.
As I understand it, Ada allows either.  The two compilers I've tried
both round.

overriding "*", was Re: What's the ICFP Programming contest?

[tmoran]

For the contest I needed to override normal fixed point multiply and
divide, so I declared
  type Root_Numbers is delta ...
  type Numbers is new Root_Numbers;
  function "*"(Left, Right : Numbers) return Numbers;
  A, B, C : Numbers;
and tried to use it in formulas like
  C := Numbers(A * B);
But a compiler said the "*" was ambiguous between my function and Standard.
It seems to me I overrode, and thus hid, Standard."*", no?
  p.s. I did manage to write a program that successfully drove the first 5
out of 9 race tracks.  It gets really lost though in the maze-like ones.
The "programming" contest really becomes an "algorithm" contest there.

Re: overriding "*", was Re: What's the ICFP Programming contest?

[Randy Brukardt]

tmoran@acm.org wrote in message ...
>For the contest I needed to override normal fixed point multiply and
>divide, so I declared
>  type Root_Numbers is delta ...
>  type Numbers is new Root_Numbers;
>  function "*"(Left, Right : Numbers) return Numbers;
>  A, B, C : Numbers;
>and tried to use it in formulas like
>  C := Numbers(A * B);
>But a compiler said the "*" was ambiguous between my function and
Standard.
>It seems to me I overrode, and thus hid, Standard."*", no?
>  p.s. I did manage to write a program that successfully drove the
first 5
>out of 9 race tracks.  It gets really lost though in the maze-like
ones.
>The "programming" contest really becomes an "algorithm" contest there.

That's a well-known feature of Ada 95 (and it is incompatible with Ada
83). The problem is that you can't hide the mixed fixed point multiply
(any fixed * any fixed -> universal fixed), so it is ambiguous anywhere
other than in the children of your fixed point package.

The ARG has looked at this problem several times, and so far it has
defied solution. Tucker announced that he had solved it when I was
talking to him after the Toulouse meeting, but whether that is really
true (and whether we can live with the incompatibility) is yet to be
seen.

                 Randy.

Re: overriding "*", was Re: What's the ICFP Programming contest?

[tmoran]

>That's a well-known feature of Ada 95 (and it is incompatible with Ada
>83). The problem is that you can't hide the mixed fixed point multiply
>(any fixed * any fixed -> universal fixed), so it is ambiguous anywhere
>other than in the children of your fixed point package.
  Why did it work in Ada 83, and why was it changed?

Re: overriding "*", was Re: What's the ICFP Programming contest?

[Randy Brukardt]

tmoran@acm.org wrote in message <9mEMa.19277$926.1303@sccrnsc03>...
>>That's a well-known feature of Ada 95 (and it is incompatible with Ada
>>83). The problem is that you can't hide the mixed fixed point multiply
>>(any fixed * any fixed -> universal fixed), so it is ambiguous
anywhere
>>other than in the children of your fixed point package.
>  Why did it work in Ada 83, and why was it changed?

Ada 83 required that the mixed fixed point operators be used in a type
conversion:

     A := My_Fixed(B*C);

But this didn't allow literals, and was clumsy. So, it was changed to
take the type from context:

    A := B*C;

But that makes the operators always visible, so they get priority over
use-visible ones. The incompatibility that that causes was thought to
not be too important; but we know better now.

              Randy.

Re: overriding "*", was Re: What's the ICFP Programming contest?

[Robert I. Eachus]

tmoran@acm.org wrote:
> For the contest I needed to override normal fixed point multiply and
> divide, so I declared
>   type Root_Numbers is delta ...
>   type Numbers is new Root_Numbers;
>   function "*"(Left, Right : Numbers) return Numbers;
>   A, B, C : Numbers;
> and tried to use it in formulas like
>   C := Numbers(A * B);
> But a compiler said the "*" was ambiguous between my function and Standard.
> It seems to me I overrode, and thus hid, Standard."*", no?
>   p.s. I did manage to write a program that successfully drove the first 5
> out of 9 race tracks.  It gets really lost though in the maze-like ones.
> The "programming" contest really becomes an "algorithm" contest there.

There are fixed-point multiplying operators that return universal-fixed. 
  You can't override or hide them.  What you can do is write:

    C := Numbers'(A * B);

This requires the result to be of type Numbers.  The magic is that in 
Ada 95, there can be an implict conversion on the assignment, but the 
qualified expression comes first.
-- 

                                                        Robert I. Eachus

�In an ally, considerations of house, clan, planet, race are 
insignificant beside two prime questions, which are: 1. Can he shoot? 2. 
Will he aim at your enemy?� -- from the Laiden novels by Sharon Lee and 
Steve Miller.

Re: overriding "*", was Re: What's the ICFP Programming contest?

[Robert I. Eachus]

Robert I. Eachus wrote:

I said:

> There are fixed-point multiplying operators that return universal-fixed. 
>  You can't override or hide them.  What you can do is write:
> 
>    C := Numbers'(A * B);
> 
> This requires the result to be of type Numbers.  The magic is that in 
> Ada 95, there can be an implict conversion on the assignment, but the 
> qualified expression comes first.

But I just tried this example on GNAT:

procedure Fixed_Example is
   type Root_Numbers is delta 0.0625 range -1000.0..1000.0;
   type Numbers is new Root_Numbers;
   function "*"(Left, Right : Numbers) return Numbers is
   begin return Numbers(Integer(Left/Numbers'Small)*
                Integer(Right/Numbers'Small)*Numbers'Small);
   end "*";

   A, B, C : Numbers := 42.0;
begin
   C := Numbers'(A * B);
end Fixed_Example;

And got a nasty message.  This is definitely a bug, but I don't think it 
  is a compiler bug, it is a language bug.  As I remember it, Tuck, Ben 
Brosgol, Dave Emery?, myself and one or two others discussed this at a 
meeting at Wellesley College.  (Robert Dewar was there, but I think he 
was in another meeting when this was discussed.)  In any case, the 
intention was that the implicit conversions should only occur in certain 
contexts, including parameters and assignment statements but not type 
conversions and qualified expressions to deal with just this issue.
There is/was an AI on the issue, AI-193.  The result, approved by WG9 
was to take no action.  That probably should be reconsidered for Ada 
2005, but that doesn't mean it will change.  However, writing in 1996, I 
had a solution, I just didn't remember it correctly:

========================================================================
!section 4.5.5(18)
!subject User-defined fixed,fixed multiplying op
!reference RM95-4.5.5(18-20)
!reference RM95-3.1.4(6-8)
!reference RM95-3.2.3(1)
!reference RM95-A.1(34-35)
!reference 1996-5700.a Tucker Taft 1996-9-17
!reference 1996-5707.a Robert Dewar 1996-9-26
!reference AI95-00163/00
!from Robert Eachus 1996-10-14
!keywords incompatibility, fixed point, user-defined operator
!reference 96-5727.a Robert I. Eachus 96-10-14>>
!discussion

...

     Finally, the trick that started me writing this.  If you want to
write expressions using user defined multiplying operations for fixed
point types, it is possible.  You can even do it in the C := A*B
format.  But literals require explicit user-defined conversions.
(Which do nothing in the object code, but can look messy in the
source, and you get wierd error messages if you leave out a "+".)

    package My_Fixed is

       type Real_Fixed is delta ...;

       type Fixed is private;

       function "+" (L,R: Fixed) return Fixed;
       ...
       function "/" (L,R: Fixed) return Fixed;

    private

       type Fixed is new Real_Fixed;

    end My_Fixed;

    If you add in the "standard" conversion operations:

    function "+"(L: in Real_Fixed) return Fixed;
      and
    function "-"(L: in Real_Fixed) return Fixed;

    Then the only "penalties" incurred outside the package are that
literals have to have signs, and that you can't instantiate generics
that require fixed point types on Fixed.  But you don't want to do
that (other than for Text_IO.Fixed_IO).  You want generics which have
generic formal subprograms to match the operators, or you want generic
formal derived types.  So make My_Fixed itself a generic package (with
a Fixed_IO child), and use generic formal package types.  The final
result looks like:

    generic
      type Real_Type is delta <>;
    package Special_Fixed is

       type Fixed is private;

       function "+"(L: in Real_Type) return Fixed;
       function "-"(L: in Real_Type) return Fixed;

       function "+" (L: Fixed) return Fixed;
       function "-" (L: Fixed) return Fixed;
       function "+" (L,R: Fixed) return Fixed;
       ...
       function "/" (L,R: Fixed) return Fixed;

    private
       type Fixed is new Real_Type;
       pragma Inline(...);
    end Special_Fixed;

    with Text_IO;
    generic
    package Special_Fixed.Fixed_IO is
    ...
    end Special_Fixed.Fixed_IO;

    If NASA, or whoever, isn't happy with this, they can contact their
vendor.

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

So there is the workaround, but I think for Ada 2005 we need a better 
solution.  I personally think that implicit conversions in a qualified 
expression are evil in general, and fixing that would certainly help in 
this case.

-- 

                                                        Robert I. Eachus

�In an ally, considerations of house, clan, planet, race are 
insignificant beside two prime questions, which are: 1. Can he shoot? 2. 
Will he aim at your enemy?� -- from the Laiden novels by Sharon Lee and 
Steve Miller.