Thoughts on the recent ICFP contest

Thoughts on the recent ICFP contest

[Ted Dennison]

I was reading over the results of this year's ICFP programming contest 
(http://icfpcontest.cse.ogi.edu/ ) last week.

For those allergic to following links, this year's project was to build 
a simple virtual robot that moves crates around and interacts with other 
robots in a way that maximizes its own score. Entrants had the recent 
long weekend (long in the US anyway) to complete their entries, at which 
time they'd compete against each other's entries to see how they score. 
This is *very* similar to an AI class project I did as an undergrad (in 
Lisp), so I'm somewhat familiar with the issues involved with doing this.

One thing I started wondering is what libraries would have been needed 
to have been available for someone to complete this project 
competitively in Ada. After reading over the web pages of some of the 
contestants (http://icfpcontest.cse.ogi.edu/links.html ) and a bit of 
thought, I came up with the following things that would have helped an 
Ada implementation get into the lightning round (submitted <24 hours 
after the requirements were posted):

   (1) An inference engine.
   (2) High-level socket bindings.
   (3) A generic implementation of Dijkstra's Algorithm

(1) would be useful for the actual robot decision-making process.
We already have it in a preliminary form, with my CLIPS bindings 
(http://www.telepath.com/~dennison/Ted/AdaClips/AdaClips.html )

(3) (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html ) 
would have saved someone lots of time here, but is probably not 
something that would be general-use enough to find laying around in a 
reusable package library somewhere. I could be wrong though...

That leaves me with (2), which is both generally useful, and not 
available right now (at least not outside of Claw). I'm thinking the 
best way to do this in the context of Ada would be to implement it as a 
stream, with the various sockopt function codes implemented as 
primitives on it.  I'm curious if anyone else thinks something like this 
ought to be available.

Another thought I had was that for a general-purpose socket stream to be 
really useful in many applications, you'd also need some way to tell it 
to transmit an entire buffer at once, rather than one component at a 
time (although you might want that in a lot of situations too). The best 
idea I came up with is a new type that users can convert their objects 
to (via some kind of pointer magic-perhaps), which has its 'Write and 
'Read implemented to write the whole defined length of the buffer at 
once. This would be quite useful with *any* stream too, not just with 
socket streams. Since this is a speed optimization, copying the buffer 
would be missing the point. Therefore, it would probably be implemented 
as a simple addres and length (or pointer if the type is generic).

Anyway, I'm curious what other Ada folks think about all this.

Re: Thoughts on the recent ICFP contest

[tmoran]

>  (3) A generic implementation of Dijkstra's Algorithm
In the sense of an Ada "generic", or what?  I would think a library
version of the algorithm would be a single call, taking a graph
representation as input and giving a shortest path as output,
so the only novelty would be in devising convenient ways to build
the input data structure or use the output.  Or is this not what
you're think of at all?

> stream, with the various sockopt function codes implemented as
> primitives on it.  I'm curious if anyone else thinks something like this
  Can you give an example of a piece of code written using what you
have in mind?

> to transmit an entire buffer at once, rather than one component at a
  Like marshalling all those 'Writes to a buffer, then making one
socket'write(buffer) call?

> Since this is a speed optimization, copying the buffer would be missing
> the point.
  That sounds more like creating a "channel program" to do "gather
writes" when the IO is actually started.  Is that what you mean?

Re: Thoughts on the recent ICFP contest

[Wes Groleau]

> > to transmit an entire buffer at once, rather than one component at a
>   Like marshalling all those 'Writes to a buffer, then making one
> socket'write(buffer) call?

Have I missed the point all this time?
I thought that 'Write recursively used
all the component 'Writes to pack the
object into a stream, and then the
possibly dispatching operations of the
stream would determine the method of
transmission.


-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

tmoran@acm.org wrote:
>> (3) A generic implementation of Dijkstra's Algorithm
> 
> In the sense of an Ada "generic", or what?  I would think a library

Not in the Ada sense, no. But it could be made an Ada generic I suppose, 
to allow user-defined data in the graph nodes.

> version of the algorithm would be a single call, taking a graph
> representation as input and giving a shortest path as output,
> so the only novelty would be in devising convenient ways to build
> the input data structure or use the output.  Or is this not what
> you're think of at all?

Well, I believe that algorithm finds *all* shortest paths from a given 
node as a side effect. Given that, one might want to have one call to 
find all the paths, then another to return the shortest one between two 
given nodes. As long as the start node is on the original path, you 
wouldn't need to recalculate.

Then again, if one wanted to make some kind of general path search 
interface, keeping it simple enough to be supported by any algorithm 
might be better.

But again, I'm not sure how generally useful this would be. I've never 
needed such a thing at work. But then again there are many industries 
I've never worked in...

>>stream, with the various sockopt function codes implemented as
>>primitives on it.  I'm curious if anyone else thinks something like this
> 
>   Can you give an example of a piece of code written using what you
> have in mind?

The idea is that network code would look just like file streaming code. 
Something along the lines of:

    Ada.Streams.Sockets.Connect
       (New_Socket => Server,
        Address    => (127,0,0,1),
        Port       => 5517,
        Protocol   => Ada.Streams.Sockets.TCP);
    Server_Request'Write (Server, Request);
    Server_Response'Read (Server, Response);


> 
>>to transmit an entire buffer at once, rather than one component at a
> 
>   Like marshalling all those 'Writes to a buffer, then making one
> socket'write(buffer) call?
> 
> 
>>Since this is a speed optimization, copying the buffer would be missing
>>the point.
> 
>   That sounds more like creating a "channel program" to do "gather
> writes" when the IO is actually started.  Is that what you mean?

No, nothing that complicated (unless I'm misunderstanding you). Its just 
that 'Write on a 1000-byte array will, by default, perform one 'Write on 
  each component of that array, amounting to 1000 'Writes. That means 
any time someone is interested in efficency, they end up having to make 
their own 'Write that calls Ada.Streams.Write once for each object that 
they want transferred efficiently. This is an issue for *any* stream, 
not just the one I'm proposing above.

It would be nice if instead there were a generic object that already has 
this overload for its 'Write and 'Read, and to which any object can be 
converted. No actual data would have to be copied to do this.

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

Wes Groleau wrote:
> 
>>>to transmit an entire buffer at once, rather than one component at a
>>
>>  Like marshalling all those 'Writes to a buffer, then making one
>>socket'write(buffer) call?
> 
> 
> Have I missed the point all this time?
> I thought that 'Write recursively used
> all the component 'Writes to pack the
> object into a stream, and then the
> possibly dispatching operations of the
> stream would determine the method of
> transmission.

As a point of reference, perhaps you should see this post: 
http://groups.google.com/groups?q=streams+stream_io+group:comp.lang.ada+author:dennison%40telepath.com&hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=94hjbp%24ks6%241%40nnrp1.deja.com&rnum=4
from a couple of years ago.

The issue is that each 'Write on a "leaf object" (a non-compound object) 
will result in its own call to the stream's Write routine. That means if 
I do a 'Write on a 1K string, the stream's Write routine gets called 
1024 times. That's a lot of overhead, not to mention that many stream 
objects might be way more efficient with one Write of 1K than they are 
with 1024 one-byte writes. That is certianly the case with Gnat's 
Ada.Streams.Stream_IO

This issue has come up here many times before. The answer is always that 
the user should either call the stream's Write routine themselves 
directly with the entire buffer, or overload their object's 'Write 
attribute with their own routine that does that.

I'm thinking it would be nice to have an object that does this for you, 
rather than everyone always having to go out and write this same code.

Re: Thoughts on the recent ICFP contest

[David C. Hoos]

Yes, you _have_ missed the point.  Each of the component 'Writes
dispatches to the appropriate "method of transmission." 
----- Original Message ----- 
From: "Wes Groleau" <wesgroleau@despammed.com>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: Thursday, September 12, 2002 9:23 AM
Subject: Re: Thoughts on the recent ICFP contest


> 
> 
> > > to transmit an entire buffer at once, rather than one component at a
> >   Like marshalling all those 'Writes to a buffer, then making one
> > socket'write(buffer) call?
> 
> Have I missed the point all this time?
> I thought that 'Write recursively used
> all the component 'Writes to pack the
> object into a stream, and then the
> possibly dispatching operations of the
> stream would determine the method of
> transmission.
> 
> 
> -- 
> Wes Groleau
> http://freepages.rootsweb.com/~wgroleau
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada.eu.org
> http://ada.eu.org/mailman/listinfo/comp.lang.ada
> 

Re: Thoughts on the recent ICFP contest

[tmoran]

> I thought that 'Write recursively used
> all the component 'Writes to pack the
> object into a stream, and then the
> possibly dispatching operations of the
> stream would determine the method of
> transmission.
  Yes 'Write is called recursively, but all it does is make a bunch of
calls to routines taking an access to stream and the particular item.
Commonly those routines write the value to successive positions in
a stream_element_array or to an IO device, but they don't have to.
Ultimately you get a bunch of calls to
Write(your_child_of_Root_Stream_Type, Stream_Element_Array).
If that routine merely adds one to a global counter, and quite ignores
the Stream_Element_Array, then you have a "component counter", not
an IO operation.
Claw has a Marshalling thing
  type Buffer_Type(Initial_Length : Ada.Streams.Stream_Element_Count)
    is new Ada.Streams.Root_Stream_Type with private;
and Claw.Sockets has, for instance,
  procedure Output(Socket  : in out Datagram_Type;
                   Item    : in out Claw.Marshalling.Buffer_Type;
                   Address : in     Network_Address_Type := System_Supplied_Address;
                   Port    : in     Port_Type := 0);
specifically to let you do a bunch of short writes into a marshalling
buffer, then do one socket write of that buffer.

Re: Thoughts on the recent ICFP contest

[tmoran]

>   Ada.Streams.Sockets.Connect
>      (New_Socket => Server,
>       Address    => (127,0,0,1),
>       Port       => 5517,
>       Protocol   => Ada.Streams.Sockets.TCP);
  Claw, even the GMGPL version on adapower, has
  procedure Open(Socket     : in out Socket_Type;
                 Domain_Name: in     String;
                 Port       : in     Port_Type;
                 Timeout    : in     Duration := 30.0);
  procedure Open(Socket  : in out Socket_Type;
                 Address : in     Network_Address_Type;
                 Port    : in     Port_Type;
                 Timeout : in     Duration := 30.0);
>   Server_Request'Write (Server, Request);
>   Server_Response'Read (Server, Response);
  I'm not quite sure how high level this is supposed to be.  Claw has
  type Socket_Stream_Type(Socket : access Socket_Type'class)
    is new Ada.Streams.Root_Stream_Type with ...
so you can write
  userid'write(stream_access, "tmoran");
and I'm currently working on
  f : ftp.stream_io.remote_file_type;
  stream : ftp.stream_io.stream_access;
  ...
  ftp.stream_io.connect(f,"upload.attbi.com",userid=>"joe",password=>"secret");
  ftp.stream_io.create(f, ftp.stream_io.out_file, "test");
  claw.bitmaps.root_dibitmap_type'class'output(stream,pic);

> that 'Write on a 1000-byte array will, by default, perform one 'Write on
> each component of that array, amounting to 1000 'Writes. That means
> any time someone is interested in efficency, they end up having to make
> their own 'Write that calls Ada.Streams.Write once for each object that
> they want transferred efficiently. This is an issue for *any* stream,
> not just the one I'm proposing above.
  Agreed.  Anytime you make a data structure that needs to be read/written,
part of the job is to write the Data_Structure'Write etc. routines.  So
it would be nice to have an efficient String'Write, but I'm not sure how
much real work it would let you avoid.

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

tmoran@acm.org wrote:
>>  Ada.Streams.Sockets.Connect
>>     (New_Socket => Server,
>>      Address    => (127,0,0,1),
>>      Port       => 5517,
>>      Protocol   => Ada.Streams.Sockets.TCP);
> 
>   Claw, even the GMGPL version on adapower, has


I did occur to me that Claw probably had something like that. However, 
for the ICFP contest, the code has to run on a Linux box, so that 
wouldn't have helped.

Re: Thoughts on the recent ICFP contest

[Warren W. Gay VE3WWG]

tmoran@acm.org wrote:
...
>>that 'Write on a 1000-byte array will, by default, perform one 'Write on
>>each component of that array, amounting to 1000 'Writes. That means
>>any time someone is interested in efficency, they end up having to make
>>their own 'Write that calls Ada.Streams.Write once for each object that
>>they want transferred efficiently. This is an issue for *any* stream,
>>not just the one I'm proposing above.
> 
>   Agreed.  Anytime you make a data structure that needs to be read/written,
> part of the job is to write the Data_Structure'Write etc. routines.  So
> it would be nice to have an efficient String'Write, but I'm not sure how
> much real work it would let you avoid.

I encountered this type of performance problem with my APQ Ada95 interface
to PostgreSQL. I provide a streams interface to blobs. However, when I tried
to write strings to the blob, the performance was abysmal because each byte
was being sent to the database server and acknowledged back up the food chain.

I solved the problem (mostly) by providing buffered reads and writes to
the blob, much the same way the fread(2) and fwrite(2) calls in C work. It
turned out to be simpler than expected, because you can do all of the
buffering work at the bottom stream layer. See the following link if
you have the patience to sift through the code:

    http://home.cogeco.ca/~ve3wwg/apq-1.9.tar.gz

I have been tempted to look at that very same issue for sockets myself.
I have also pondered whether there is a universal way (non-GNAT specific)
using XDR routines to make the I/O endian neutral.  I know that GNAT uses
some vector of routines technique to do this, though I've not fully explored
this yet.  Do a google search -- it was discussed this year I think.

-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Thoughts on the recent ICFP contest

[Wes Groleau]

> Yes, you _have_ missed the point.  Each of the component 'Writes
> dispatches to the appropriate "method of transmission."

What I meant was, I _thought_ that 'Write would put more
stuff in the stream, and that _another_ call would send
the assembled stuff to where-ever.

Obviously, I haven't actually coded any stream stuff.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

Wes Groleau wrote:
> What I meant was, I _thought_ that 'Write would put more
> stuff in the stream, and that _another_ call would send
> the assembled stuff to where-ever.

Nope. However, some folk have mentioned making an intermediate stream 
that performs this function (presumably triggered by some kind of 
"flush" call). I have to say, I didn't think of that. I should be 
ashamed of myself, an educated computer scientist, not thinking of 
applying Wheeler's Maxim ("Any problem in computer science can be solved 
with another layer of indirection.")  :-)

However, if you are doing something byte-oriented on a big buffer, the 
'Write calls on each byte alone may chew up a huge amount of time. This 
was touched on in the thread I linked to about disk I/O using 
Ada.Streams.Stream_IO. The underlying transmission mechanisim does 
buffering (as per Robert Dewar), so each 'Write does not actually 
perform an I/O. But still, 'Writing each and every byte took 10 times 
longer than Ada.Streams.Writing the whole buffer when I measured it. 
You'd expect I/O times to dominate over procedure call overhead, even 
for a single I/O, but it doesn't appear to be doing so. (I'm still a 
little doubtful about this, but one has to trust Robert Dewar's word 
about the Gnat internals. :-) )

So what I was talking about doing was creating an object that has a 
'Write and 'Read that are defined to make only one call to 
Ada.Streams.Write and .Read respectively, and that any object can be 
converted into without processing the source object. Any transformation 
done by a 'Write of a lower-level object in an aggregate would not 
happen, but it would be fast for very large aggregates (eg: arrays). You 
can think of it sort of as the System.Address type for streams.

> Obviously, I haven't actually coded any stream stuff.

I found quite a few suprising (to me) things when I first began serious 
stream use. I think its one of those things you really have to do 
yourself once to fully grok.

Re: Thoughts on the recent ICFP contest

[Jacob Sparre Andersen]

Ted Dennison wrote:

> I was reading over the results of this year's ICFP programming contest 
> (http://icfpcontest.cse.ogi.edu/ ) last week.

> One thing I started wondering is what libraries would have been needed 
> to have been available for someone to complete this project 
> competitively in Ada.

You claim our submission isn't competitive? :-)

(I am afraid it isn't)

 > I came up with the following things that would have 
helped an
> Ada implementation get into the lightning round (submitted <24 hours 
> after the requirements were posted):
> 
>   (1) An inference engine.

Maybe.

>   (2) High-level socket bindings.

I think the AdaSockets package is sufficient.

>   (3) A generic implementation of Dijkstra's Algorithm

More important: Knowledge of Dijkstra's Algorithm.

Neither I or my team mate knew Dijkstra's Algorithm (but we 
learned about it after submitting our entry). I implemented 
a simplified version of Dijkstra's Algorithm in only a few 
hours the night after the deadline. :-(

> Anyway, I'm curious what other Ada folks think about all this.

I wish somebody had told me of Dijkstra's Algorithm a few 
weeks ago.

Jacob
-- 
No trees were killed in the sending of this message.
However a large number of electrons were terribly 
inconvenienced.

Re: Thoughts on the recent ICFP contest

[Preben Randhol]

On Thu, 12 Sep 2002 02:35:10 GMT, Ted Dennison wrote:
> 
> That leaves me with (2), which is both generally useful, and not 
> available right now (at least not outside of Claw). I'm thinking the 
> best way to do this in the context of Ada would be to implement it as a 
> stream, with the various sockopt function codes implemented as 
> primitives on it.  I'm curious if anyone else thinks something like this 
> ought to be available.

What is missing in Adasocket?

Preben

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

Preben Randhol wrote:
> On Thu, 12 Sep 2002 02:35:10 GMT, Ted Dennison wrote:
> 
>>That leaves me with (2), which is both generally useful, and not 
>>available right now (at least not outside of Claw). I'm thinking the 
>>best way to do this in the context of Ada would be to implement it as a 
>>stream, with the various sockopt function codes implemented as 
>>primitives on it.  I'm curious if anyone else thinks something like this 
>>ought to be available.
> 
> 
> What is missing in Adasocket?

There are 2 problems with Adasocket:

The main one is that I didn't know about it. :-)   My bad...


The other issue is that its not quite the high-level interface I was 
considering. However, it would have actually been perfect for the task 
in question (better than the solution I was considering), as its 
"Get_Line" function is precisely what one would have needed to retrieve 
data from the host.

Re: Thoughts on the recent ICFP contest

[Ted Dennison]

Jacob Sparre Andersen wrote:
> Ted Dennison wrote:
> 
>> I was reading over the results of this year's ICFP programming contest 
>> (http://icfpcontest.cse.ogi.edu/ ) last week.
> 
> 
>> One thing I started wondering is what libraries would have been needed 
>> to have been available for someone to complete this project 
>> competitively in Ada.
> 
> You claim our submission isn't competitive? :-)
> 
> (I am afraid it isn't)

Sorry, I didn't know there was an Ada entry. Do you have a web page for 
it somewhere?


>>   (1) An inference engine.
> 
> 
> Maybe.

You could do without one without too much trouble. But doing decision 
logic in procedural programming is a bit slower, and much harder to 
tune. So I think to get things going quickly, in the "short-long run", 
an inference engine like CLIPS would save you time. :-)


>>   (2) High-level socket bindings.
> I think the AdaSockets package is sufficient.

Hmmm...for this task better than what I was thinking of. You got one up 
on me there!


>>   (3) A generic implementation of Dijkstra's Algorithm
> I wish somebody had told me of Dijkstra's Algorithm a few weeks ago.

When we did something very similar for an AI class 14 years ago, I used 
it (as did everyone else; it was covered in class). However, I had 
completely forgotten about it since, and was only reminded by reading 
over the submission websites. So I won't make the claim that I would 
have come up with it in your place.

What would have been really nifty would have been to have my old 
project's sources available. The only change needed would have been to 
the communications code and the AI, so I could have hit the lightning 
round. But that was back when the only offline media was paper printouts 
or 9-inch reel taps (which they would never have let me have). I may 
still have a printout somewhere though...

Re: Thoughts on the recent ICFP contest

[Jacob Sparre Andersen]

Ted Dennison wrote:

> Sorry, I didn't know there was an Ada entry. Do you have a web page for 
> it somewhere?

No, but I could put a copy of the source code on a web site.

> You could do without one without too much trouble. But doing decision 
> logic in procedural programming is a bit slower, and much harder to 
> tune. So I think to get things going quickly, in the "short-long run", 
> an inference engine like CLIPS would save you time. :-)

Sounds like I should take a look at CLIPS.
Jacob
-- 
Warning: Dates in calendars are closer than they appear.

Re: Thoughts on the recent ICFP contest

[tmoran]

> "Get_Line" function is precisely what one would have needed to retrieve
> data from the host.
  There's a "type Socket_Type(Max_Line_Length:Positive) is new [socket]
with associated Get_Line that does
    -- Return Line(Line'first .. Last)
    -- Input up through LF if LF occurs,
    -- Line(Line'range) if no LF seen,
    -- or Input up through last received char if timeout or hangup
in the spider program Finder at www.adapower.com/os/finder.html
Is that the same functionality?  (Finder also has package Te_Text_Line_Sockets,
which also handles "chunked" http encoding.)

Re: Thoughts on the recent ICFP contest

[Samuel Tardieu]

>>>>> "Ted" == Ted Dennison <dennison@telepath.com> writes:

Ted> [...] as its "Get_Line" function is precisely what one would have
Ted> needed to retrieve data from the host.

A lot of TCP popular protocols are text-based; this function is useful
for most of them. It was there in the very first version :)

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam