HDTenEightyP/NetNews huggingface dataset:
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Programming by Description of Output...
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Thu, 31 Dec 1992 15:57:36 GMT

In article <BEVAN.92Dec31001940@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
>Getting back to the sorting example: if the arrays are changed to
>lists, then a spec is :-
>
>  sort(List, Sorted_List) :-
>    permutation(List, Sorted_List),
>    ordered(Sorted_List).
>
>Suitable definitions of `permutation' and `ordered' are left as an
>excercise for the reader.

My impression is that most of the work of writing this specification
is in the spec of "permutation", a smaller amount is in "ordered", and
the part shown above is trivial in comparison.  So the above example
doesn't make much of an impression on me.

>[...]  Someone here did some
>work on automatically transforming Prolog programs (the thesis
>specifically covers generation of various sort routines from the above
>spec).

Good, I figured someone would be working on this.  I could be surprised
by the results.

-- David Karr (karr@cs.cornell.edu)
From: vnoble@dhvx20.csudh.edu
Newsgroups: comp.programming
Subject: Software development in Russia?
Date: 23 Dec 92 01:38:38 GMT
Organization: CSU, DOMINGUEZ HILLS


Hi out there in NETland!

I am contemplating investing some money in software development in Russia and
selling it here in US.  It seems to be a good idea since software is a heavily
labor-consuming product with little hardware investment required to start it
out.  As you know, Russia now has a lot of skillful mathematicians, physisists
and programmers who are actively seeking an opportunity to earn any hard
currency.  With exchange rate at rediculously low level and the cost of labor
which is THE cheapest in the world, Russia looks like a heaven for software
development.  Besides, I was born there and lived there until about 5 years
ago, so it is reletively easy for me to establish right contacts.

I would like to solicit your opinion on the following matter.  Short time ago I
encountered an ad of a Russian software company offering different products such
as computer graphics, PC games, learning packages for children with game
elements, and so on.  My question is: Can I try to become a distributor of
their products in US and what kind of agreements are generally required? If I 
had a distribution or licencing agreement with those guys, how would I go
about selling this stuff here? Is there a market for, say, PC games or 
learning packages?  How can I interest big software resellers like CompUSA
or Egghead to carry them? Unfortunately, I do not have any experience in
selling software, so any info on this will be highly appreciated.

You can E-mail me at Vnoble@dhvx20.csudh.edu.

Thank you for taking time to read this.

Vladimir Noble
Newsgroups: comp.programming
From: boutell@isis.cshl.org (Tom Boutell)
Subject: Programming by Description of Output...
Organization: Cold Spring Harbor Labs
Date: Wed, 30 Dec 1992 03:27:27 GMT

In learning about methods of proving algorithms correct (and the
various difficulties of doing same), I have come to wonder
to what degree it is possible to create a language in which
the programmer specifies not the steps to be accomplished
but rather the goal to be achieved-in other words, whether it
is possible, working from a specification of the initial state
and a specification of the final state, to derive an algorithm
automatically which permutes the one into the other. I suppose
this is similar to other generalized AI problem-solving tasks,
but a notable advantage is that the goal state is well-defined
(none of the AI problems of needing to operate in non-abstract
universes come into play, at least not for a decently interesting
set of cases). 

Are there languages/programming systems that attempt this sort
of thing? I'm sure it's impossible to guarantee a solution
to every request that has a possible solution, since this would
imply the ability to prove that fact, and the statement of the
problem is likely to be equivalent to second-order predicate
calculus, in which a proof (by resolution) cannot be guaranteed 
in finite time. But if the system can recognize solved problems
as subsets of the problem at hand, it can move more quickly toward
assembling a solution, or deciding it's overwhelmed. 

An example of what I have in mind:

Initial state:
Array A[] contains n whole numbers. 
Final state:
Array B[] contains n whole numbers such that each element of
A[] appears in B[] and for all i such that 1<=i<n, B[i]<B[i+1].

How might the problem of calculating B[] (a sorted version of
A[]) be solved in a general fashion, absent a known
method of sorting?

-T

-- 
Tom Boutell, boutell@cshl.org

Clausthaler is the best non - alcoholic beer in the known universe.
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Programming by Description of Output...
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Wed, 30 Dec 1992 17:40:04 GMT

In article <C01yxr.BGF@phage.cshl.org> boutell@isis.cshl.org (Tom Boutell) writes:
>Initial state:
>Array A[] contains n whole numbers. 
>Final state:
>Array B[] contains n whole numbers such that each element of
>A[] appears in B[] and for all i such that 1<=i<n, B[i]<B[i+1].
>
>How might the problem of calculating B[] (a sorted version of
>A[]) be solved in a general fashion, absent a known
>method of sorting?

This sounds like automatic programming, which is an old idea.
Frederick P. Brooks mentioned it in an article a couple of years ago,
entitled (I think) "No Silver Bullet."

How much easier is it to specify a program by predicates on its input
and output rather than by an algorithm?  I contend it's not as easy
as one might hope.  For example, is the following legal I/O for your
specification:

A[] (input):   3 2 1 3 2 1 3 2 1
B[] (output):  1 2 3 3 3 3 3 3 3

Each element of A[] appears in B[], but not with the same count of 
repetitions.  Is this what you intended?

-- David Karr (karr@cs.cornell.edu)
From: lpeters@postmaster@hq.af.mil (Leslie D Peters)
Newsgroups: comp.programming
Subject: Re: Programming contest
Date: 21 Dec 92 14:22:23 GMT
Reply-To: lpeters@marge.hq.af.mil
Organization: 7th Communications Group

In article <1992Dec16.044710.8207@galileo.cc.rochester.edu>, wa2cs252@troi.cc.rochester.edu (Guardian) writes:
|> In <1992Dec15.213125.28056@athena.mit.edu> acgoldis@athena.mit.edu (Andrew C Goldish) writes:
|> 
|> >  I am a relatively new subscriber to this newsgroup and did not get most of the
|> >information about the programming contest.  Can you send over the complete file
|> >with the details?
|> 
|> >							A. Goldish
|> 						acgoldis@athena.mit.edu
|> 
|> Me Too!
|> 
|> 						D. Flores
|> 					df004b@uhura.cc.rochester.edu
I also!
					L. Peters
				lpeters@marge.hq.af.mil
-- 
/============================================================================\
|                                            |                               |
|                    ___                     |                               |
|       ___....-----'---`-----....___        |   I haven't lost my mind --   |
| =========================================  |                               |
|        ___`---..._______...---'___         |    it's backed up on          |
|       (___)      _|_|_|_      (___)        |           tape somewhere.     |
|         \\____.-'_.---._`-.____//          |                               |
|           ~~~~`.__`---'__.'~~~~            |   lpeters@marge.hq.af.mil     |
|                   `~~~'                    |                               |
|                                            |     Les Peters                |
\============================================================================/
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: How to copyright?
Keywords: copyright
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Distribution: usa
Date: Mon, 4 Jan 1993 04:43:20 GMT

In article <tim.30.726110910@tim.src.utah.edu> tim@tim.src.utah.edu (Tim Ma) writes:
>[...] could anyone tell me 
>what the procedure is to officially copyright a program or portions of its 
>code?

There is a relevant article on copyrights in the latest IEEE Spectrum.
In particular read the end of the article.

-- David Karr (karr@cs.cornell.edu)
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: Knapsack problem??
Date: 21 Dec 92 19:12:34 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <1992Dec17.210241.8948@julian.uwo.ca>, john@phobos (John Tucker) writes:
>	I have N items with an associated cost of Cn. I want to select
>the best subset of these items where TotalCost-Tolerance < Sum(Cn) <
>TotalCost.
>
>	I know it is a form of a knapsack problem

Yup.

>but I can't recollect the
>elegant way of coding this. I'm using a brute force algorithm based on
>2^n possible combinations of n objects taken 0..n at a time. This limits
>me to a max of 32 items and is slow (micro) to acceptable (DECstation 5000).

I hate to break this to you, but the Knapsack problem is NP-complete.
That means if someone does find a polynomial-time algorithm to solve it,
they'll gain fame (well, at least within CS circles) as well as the
satisfaction of having solved a long-standing open question in CS theory.

On the other hand, there could very well be a polynomial time algorithm
for a special case which is useful for your purposes.

-- 
Dave Schaumann			dave@cs.arizona.edu
Xref: sparky comp.programming:3380 comp.unix.programmer:5805
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.programming,comp.unix.programmer
Subject: Re: Network Chat Messaging Algorithm
Followup-To: comp.unix.programmer
Date: 31 Dec 1992 19:08:17 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

markh@csd4.csd.uwm.edu (Mark) writes:
>Net lag is not causing those problems, select() is.  Always check for blocking
>even if set in non-blocking mode, because select() sometimes blocks regardless.
>Or, better, don't use select().  Use fork().

In article <1992Dec31.023104.13944@netcom.com> pdh@netcom.com (Phil Howard ) writes:
>Of course select() blocks.  It's supposed to if none of the fd's have anything
>and the time is non-zero.

You misunderstood.  My fault.  I meant to say: always check for blocking by
setting all devices to non-blocking mode, because select() sometimes indicates
devices ready for I/O that are still in a blocking state, regardless of
whether you set them for non-blocking or not.

All devices have to be set for non-blocking mode even if you use select(), and
you have to check for EWOULDBLOCK on the device select()'ed on each I/O access.

It's a moot point.  The problem referred to in the original article has already
been demonstrably proven to be solved with fork().
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Newsgroups: comp.programming
Subject: Re: Programming by Description of Output...
Date: 31 Dec 92 15:46:23 GMT
Organization: Cornell Univ. CS Dept, Ithaca NY 14853

In article <1992Dec30.233659.7290@black.ox.ac.uk> ke94002@black.ox.ac.uk (Daniel J Mitchell) writes:
>
> This method of programming is usually called 'deriving programs'
>-- the original work is Edsger Dijkstra's _A Discipline of
>Programming_ (Prentice-Hall, 1976), [...]
>
> It also can wind up deriving /very/ elegant algorithms (qv the
>longest upsequence problem, covered in Gries and Morgan) for
>difficult problems.

I've derived programs and the methods can indeed yield very elegant
solutions.  But I think Dijkstra intended the process to at least be
guided by human intelligence.  He once gave as an example the
following problem:

	Two diagonally opposite corner squares have been removed
	from an 8x8 chessboard.  Determine whether it is possible
	to "tile" the remaining squares with 31 1x2 dominoes.

The problem can be solved by exhaustive search, but it is much
better to observe that there are 32 squares of one color to be
covered, while each domino can only cover one square of each color.

> As to doing it automatically, the only thing I know of is a
>language called ML which reputedly is a great deal higher level
>than most languages, and comes close to being able to take
>specifications of the above form as code. (I think. I'm probably
>wrong about that, on reflection..)

ML is a functional rather than an imperative language, but it
still encodes "algorithms" in some sense.  That is, you can define
a function "sort" that returns the sort of a list, or you can define a
function "sorted" that tells you if a list is sorted, but you cannot
just give the system the definition of "sorted" and the instructions
"make this be true."

-- David Karr (karr@cs.cornell.edu)
Xref: sparky comp.programming:3390 comp.unix.programmer:5810 comp.unix.misc:4798 rec.games.corewar:1550 rec.games.programmer:5235 comp.org.ieee:605 comp.org.usenix:1173 comp.lang.c:19130 comp.lang.c++:18630 comp.software-eng:5185
From: ahmedh@ccwf.cc.utexas.edu (ahmed h al-mehdi)
Newsgroups: comp.programming,comp.unix.programmer,comp.unix.misc,rec.games.corewar,rec.games.programmer,comp.org.ieee,comp.org.usenix,comp.lang.c,comp.lang.c++,comp.software-eng
Subject: 1993 IEEE CS National Programming Contest Notice
Date: 2 Jan 93 04:07:47 GMT
Reply-To: ahmedh@ccwf.cc.utexas.edu (ahmed h al-mehdi)
Followup-To: comp.programming
Organization: The University of Texas at Austin, Austin TX
Originator: ahmedh@happy.cc.utexas.edu


:--------------------------------------------------------------------------:
 
        Important Notice : 1993 IEEE CS National Programming Contest
 
:--------------------------------------------------------------------------:

The npc.ece.utexas.edu has been down from 19 Dec to 27 Dec 1992.  Mails and
applications sent to npc may have bounced.

We apologize for the inconvenience that this might have created.  The machine
is working right now.  Please send your mails and applications to the following
address:

                      npc@npc.ece.utexas.edu, or
                      ahmedh@ccwf.cc.utexas.edu


Thank you....



Newsgroups: comp.programming
From: pdh@netcom.com (Phil Howard )
Subject: Re: Network Chat Messaging Algorithm
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Thu, 31 Dec 1992 02:31:04 GMT

markh@csd4.csd.uwm.edu (Mark) writes:

>Net lag is not causing those problems, select() is.  Always check for blocking
>even if set in non-blocking mode, because select() sometimes blocks regardless.
>Or, better, don't use select().  Use fork().

Of course select() blocks.  It's supposed to if none of the fd's have anything
and the time is non-zero.

And fork() won't necessarily solve anything.  You STILL have the situation
where ONE process has to wait for things from at least 2 different sources,
even if those sources are children processes.

While these function names tend to be UNIX specific, the same situation
exists regardless of system type and interface.  Simply having more processes
does not solve the problems that have to be dealt with by a program that is
going to be merging and multiplexing data that has random arrival order.

I have some specific solution possibilities, but I'll be sending them by
e-mail since they are not relevant to comp.programming.
-- 
/************************************************************************\
| Phil Howard,  pdh@netcom.com,  KA9WGN    Spell protection?  "1(911)A1" |
| "It's not broken... it's just functionally challenged" --Phil and Pete |
\************************************************************************/
From: lomasm@p4.cs.man.ac.uk (Martin Lomas)
Newsgroups: comp.programming
Subject: Re: Fillet mode?
Date: 23 Dec 92 23:37:04 GMT

In <BzKv0M.1I3@geovision.gvc.com> pt@geovision.gvc.com (Paul Tomblin) writes:

>I'm trying to figure out the algorithm for this, but I thought I'd ask
>first:

>Given: Corner points of a polyline, and a fillet radius
>Generate: the parameters for the arcs at each corner point (ie. radius,
>start point, end point, or 3 points that define the arc)


Use PostScript! It already has such a function built in.
I don't know what algorithm it uses.

But from simple maths -- consider:

Two lines A-B, B-C, with vertex B. You want to replace vertex B with
an arc of radius r.
Draw a circle of radius r tangental to A-B B-C, tangent points AB and
BC respectively.

You know angle ABC, length r: Hence you can calculate the points AB and
BC and any of the other lengths/angles/points you may wish. 

Sorry, non-too good with diagrams on ttys!

Regards,
Martin.
From: dodson@convex.COM (Dave Dodson)
Newsgroups: comp.programming
Subject: Re: Fast array rotation
Date: 22 Dec 92 15:43:38 GMT
Reply-To: dodson@convex.COM (Dave Dodson)
Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
Originator: dodson@bach.convex.com
X-Disclaimer: This message was written by a user at CONVEX Computer
              Corp. The opinions expressed are those of the user and
              not necessarily those of CONVEX.

In article <u895027.724990251@tasman> u895027@tasman.cc.utas.edu.au (Mark Mackey) writes:
>
>	I am currently writing a terrain display routine which utilises
>a fast surface display algorithm based on scan-line processing. As
>part of the algorith I need to rotate the raw data array. I have an
>algorithm to do this using two 1d transforms, but in between these
>transforms the data array needs to be transposed.
>	Does anyone out there have any code for fast array transposition
>on disk, minimising disk access time? Alternatively, if anyone out there
>has ideas on how to rotate a large array (512*512 reals) efficiently
>I would be most grateful.

I assume you have the array stored on disk in row- or column-major order.
There is a way to transpose the array by reading and writing the matrix
twice.  For simplicity, assume you have row-major order, 4 byte reals,
and a scratch array of length 64K bytes.  Read 65536/4/512 = 16 rows into
the scratch array.  Write 16 x 16 square blocks onto a scratch file.  There
will be 512/16 = 32 of them for every 16 rows.  Repeat for all rows of the
matrix.  Now randomly read blocks 1, 33, 65, ... .  Transpose each 16 x 16
block in memory, and write out the first 16 rows of the transposed matrix.
Repeat with blocks 2, 34, 66, ... , 3, 35, 67, ... .

Alternatively, you might consider storing your 512 x 512 matrix in those
16 x 16 blocks as your standard storage format.  Then you can easily read
or write it in either normal or transposed form using that 64K scratch array.

----------------------------------------------------------------------

Dave Dodson		                             dodson@convex.COM
Convex Computer Corporation      Richardson, Texas      (214) 497-4234
Newsgroups: comp.programming
From: ppc1@cec2.wustl.edu (Peter Pui Tak Chiu)
Subject: MAZE
Organization: Washington University, St. Louis MO
Date: Thu, 24 Dec 1992 07:04:17 GMT

hi everyone,

is there a maze generating algorithm out there?  i don't mean a C program
that generates maze... i mean the algorithm...

please send email to ppc1@cec1.wustl.edu

thanks a lot

peter


Newsgroups: comp.programming
From: nagle@netcom.com (John Nagle)
Subject: Re: Programming by Description of Output...
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Fri, 1 Jan 1993 04:33:29 GMT

     It's a beguiling idea, but it doesn't scale up well.  We went through
this back when formal specifications were being touted as the next big
thing.  It works well for a few simple cases:

      1) The inverse of a function is much simpler to implement than 
         the function.
	 Example: square root.

      2) The function has a simple but inefficient implementation that
	 can be used as its description.
	 Example: lookup-type operations, including relational databases.

      3) The function can be well-expressed by a few constraints.
	 Example: sorting.
 
Unfortunately, not many applications seem to fall into these categories.
Our experience in building an operating system this way was that the formal
spec was about 1/3 to 1/2 the size of the code, and much harder to debug.

However, if I were doing a database management system, or anything that
basically stores and retrieves data, I'd consider specifying it formally
in terms of its inputs and outputs.  But it might be easier to write a
"dumb" implementation, with everything in arrays and all lookups by 
brute-force search, and use that as a specification.  Formal specs
that you can't run are tough to work with.

					John Nagle

					John Nagle
Newsgroups: comp.programming
From: reagle@umbc8.umbc.edu (Mr. Joseph Reagle; MEYERHOFF (U))
Subject: Re: Semaphores, Swap, or Test_And_Set
Organization: University of Maryland, Baltimore County Campus
Date: Mon, 21 Dec 1992 19:59:48 GMT

In article <1h53bpINNabh@usenet.INS.CWRU.Edu> trier@slc6.ins.cwru.edu (Stephen C. Trier) writes:
>
>I'd eventually like to rewrite this in inline assembly in C, and perhaps
>to switch to the shorter and simpler xchg sequence.  This works, though,
>and right now, that's what I need in order to get this software out the door.

	Thanks for all the great info.  I'm not up on my assembly, so
I'm gonna digest this over winter break and see if I can't get it
working.  I'll post here if I have any comments or thoughts on it.
	Again thanks alot.

					Joe
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.programming
Subject: Re: Programming by Description of Output...
Date: 31 Dec 92 20:20:01 GMT
	<BEVAN.92Dec31001940@panda.cs.man.ac.uk>
	<1992Dec31.155736.29068@cs.cornell.edu>
Organization: Department of Computer Science, University of Manchester
In-reply-to: karr@cs.cornell.edu's message of 31 Dec 92 15:57:36 GMT

In article <1992Dec31.155736.29068@cs.cornell.edu> karr@cs.cornell.edu (David Karr) writes:
   >  sort(List, Sorted_List) :-
   >    permutation(List, Sorted_List),
   >    ordered(Sorted_List).

   My impression is that most of the work of writing this specification
   is in the spec of "permutation", a smaller amount is in "ordered", and
   the part shown above is trivial in comparison.  So the above example
   doesn't make much of an impression on me.

I don't think the whole spec. makes much of an impression either, what
does is an example of the transformation from the spec. to a program.
Since I don't have any of the work I mentioned to hand I can't give an
example of that.  As a consolation, here are some spur of the moment
(i.e. not guaranteed to be correct) definitions of "permutation" and
"ordered" :- 

 permutation(A,B) :- length(A,L), length(B,L), range(A,X), range(B,Y), eq(X,Y).
 ordered([]).
 ordered([H|T]) :- item_ordered(H,T), ordered(T).
 item_ordered(_,[]).
 item_ordered(A,[H|T]) :- less_than_or_equal_to(A,H), item_ordered(A,T).

"range" returns the elements of a list as a set and "eq" compares sets
for equality.  Note Prolog doesn't have "set" as a native type, so
there is a level of detail hidden there.

bevan
Newsgroups: comp.programming
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Programming by Description of Output...
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Mon, 4 Jan 1993 04:50:09 GMT

In article <BEVAN.93Jan1134444@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
>In article <1993Jan1.043329.27160@netcom.com> nagle@netcom.com (John Nagle) writes:
>
>   Formal specs that you can't run are tough to work with.
>
>I heartily agree, though there are those who feel that if a spec. is
>executable it probably isn't a good spec.

A denotational semantics of a programming language is a formal spec of
the language itself; strangely (or perhaps not so strangely), such specs
*are* executable in Standard ML.

Admittedly, this is somewhat of a special case.

-- David Karr (karr@cs.cornell.edu)



Newsgroups: comp.programming