Newsgroups: net.mail.headers From: Dan Hoey Date: Mon, 11-Feb-85 19:29:55 EST Subject: Re: RFC 934 - Message Encapsulation Marshall, I am surprised that you say ... we need to bit (well, byte) stuff. This is the ONLY way to unambiguously separate messages in a digest (or a forwarding of messages, in general). I have previously indicated to you that there is a way to entirely avoid modification of the text of messages. Header People, The method I proposed was for the Forwarding Agent to choose an encapsulation boundary that does not occur in the messages to be encapsulated. Barry Margolin's proposal of indicating the chosen EB in the header is an appropriate way of communicating the choice to the Bursting Agent. However, the use of this boundary followed by a space for stuffing is not necessary. An algorithm for choosing the EB: 1. Form a list of trial EB's. I suggest the trial EB's be - twenty hyphens, - twenty hyphens followed by the current date and time, and - twenty hyphens followed by twenty randomly-chosen alphanumeric characters. 2. Scan the messages to be encapsulated for occurrences of the trial EB's. 3. If all of the trial EB's were found, fail. (If messages are being encapsulated at a rate of a megabyte per second, this step should be taken fewer than once every quintillion centuries, barring hardware failure.) 4. Return the first of the trial EB's not found in any message. Dan --- Newsgroups: net.unix-wizards From: hoey@nrl-aic.ARPA (Dan Hoey) Date: Wed, 20-Mar-85 18:48:50 EST Subject: Multi-step implicit rules for make(1) e...@osiris.UUCP (Eric Bergan) has a problem with make's use of implicit rules. An example of the problem can be seen with a makefile like .SUFFIXES: .D .C .B .A CONVERT_A_TO_B=cp CONVERT_B_TO_C=cp CONVERT_C_TO_D=cp .A.B: $(CONVERT_A_TO_B) $< $@ .B.C: $(CONVERT_B_TO_C) $< $@ .C.D: $(CONVERT_C_TO_D) $< $@ all: foo.D Executed in a directory with only makefile and foo.A, this make will complain that it doesn't know how to make foo.D. As both how...@cyb-eng.UUCP (Howard Johnson) and g...@ncr-tp.UUCP (Greg Noel) have pointed out, the problem is that for an implicit make rule ".A.B" to be invoked foo.A must either exist or be mentioned as a target or dependent in some rule. Thus the problem can be circumvented by the addition of the dependency foo.D: foo.B foo.C or even foo.C: foo.B in the makefile. One problem with adding lines like this is that they must be added for bar.D, baz.D, ad infinitum. Another problem is that the methods fool make's error handling. If we instead add the line foo.D: foo.B make will create only foo.B, with no complaints. The problem is that it treats "foo.D" as a target like "all" in this case, not as a file that must be created. We now turn to methods for getting make to use implicit rules to create foo.D. Both Howard and Greg propose adding a rule like .A.D: $(CONVERT_A_TO_B) $< $*.B $(CONVERT_B_TO_C) $*.B $*.C $(CONVERT_C_TO_D) $*.C $@ (their solutions are identical except for Greg's cleanup line rm -f $*.B $*.C ) to the makefile. In this case, with four suffixes involved, we might want to also add rules for .A.C: and .B.D:. I find these methods unsatisfactory because of the proliferation of the information about the commands used for converting one object into another. For instance, if the procedure for $(CONVERT_B_TO_C) took the arguments in the opposite order, we would have to change the information in two or three rules. I would suggest that the rules to be added should tell make to use the previously defined implicit rules, for example .A.D .B.D: @make $(MFLAGS) $*.C $@ rm -f $*.C .A.C: @make $(MFLAGS) $*.B $@ rm -f $*.B There are a few things to watch out for here. For one thing, the inclusion of $(MFLAGS) does not pass all of make's invocation to the subsidiary make. If you expect to invoke this script as, for instance ``make CONVERT_B_TO_C=mv'', you must set up the recursive invocations to say ``@make CONVERT_B_TO_C=$(CONVERT_B_TO_C) $(MFLAGS) ...''. It is clear this could get out of hand. And if you like to try things out with ``make -f fakefile'' you had better forget this approach entirely. Another thing to watch out for is the ordering of ".SUFFIXES:". The dependents of .SUFFIXES must be in reverse temporal order for this to work. Since lines like ".SUFFIXES: .A" append to the list of suffixes, this is sufficient if you want to add preprocessors to your source files. If you want to add postprocessors to targets already known to make, be sure to start with a ``.SUFFIXES:'' line with no dependents. It would of course be nicer if we could get make to know how to recursively apply its own implicit rules as it does for explicit rules, but I suppose there are problems with that. Dan Hoey Navy Center for Applied Research in Artificial Intelligence --- Newsgroups: net.mail.headers From: hoey@NRL-AIC.ARPA (Dan Hoey) Date: Thu, 11-Jul-85 11:13:59 EDT Subject: Re: reordering header lines Date: 03 Jul 85 01:03:59 PDT (Wed) From: Einar Stefferud Please correct me if I am wrong, but I understand that there is a problem with finding a place in the X.400 "header" part for fields named "Received" and that they need to be carried in the "envelope" part, or tossed out during a transformation from 822 to X.400. They can always be stuffed into the body if you're concerned about them. Thus, I believe it will be proper to collect all "received" headers, in the order of appearance in the 822 headers, whether all nicely grouped at the beginning or not. Why do you object to collecting them all together? I don't understand the problem. You were saying that reordering the ``Received:'' lines was not a good idea, because it loses information that might be useful in tracking down bugs. I just pointed out that collecting them together loses information, too. The whole point, I guess, is whether you want to be able to debug 822 through the gateway. If so, you probably have to preserve the entire header somewhere. If not, I don't really see why you want to preserve the ``Received:'' lines at all. Dan --- Newsgroups: net.unix From: hoey@nrl-aic.ARPA (Dan Hoey) Date: Fri, 16-Aug-85 11:50:29 EDT Subject: Re: unix file system >From: cu...@daisy.warwick.UUCP (Rob McMahon) >Date: 7 Aug 85 10:25:12 GMT >>> basic problem with the UNIX file system for FORTRAN. >>You must also rewrite "cat," because I can copy a file by saying cat a >b . >It's worse than that - the shell creates `b', and it's got no idea what >sort of file to create, It's even worse than that. ``cat'' can take more than one argument, hence its name. What do *you* want to happen when you concatenate files with different record sizes, character sets, etc. >maybe the shell should be changed to include a syntax >like `>[ASCII,RECORDSIZE=80,ANSICC]b' ! Ulch! Maybe we should begin each command with "//" and use space for a comment character. Dan --- Date: 16 Aug 1985 12:16:43 EDT (Fri) From: Dan Hoey To: SF-LOVERS Subject: Star Trek stamp FYI, from Bob Levey's Washington, in The Washington Post, 15 August 85. Let me level with you. ``Star Trek'' does not make my blood race. But for others, it's more than a TV show. It's a vision of the future. And now it may become a commemorative postage stamp. Carolee C. Davis of Derwood, Md., is spearheading a drive to get the Postal Service to issue a stamp in 1986 marking the 20th anniversary of S.T. If you'd like to hop aboard Carolee's bandwagon, write to: U.S. Postal Service, Philatelic Sales Division, Washington, D.C., 20625-6300. Dan Hoey --- Date: 7 Nov 1985 12:17:29 EST (Thu) From: Dan Hoey To: SF-LOVERS Subject: Re: Space Is Clean >From: mtgzz!leeper@caip.rutgers.edu (m.r.leeper) >...thinking about how likely it was that if we found life in the >universe it would likely be something that would turn our >collective stomachs. > >...So most life-forms we find disgusting, but the converse is even >more true. Only a small part of the matter on Earth is connected >with life-forms, yet everything disgusting is. This is an awesome thesis. I like it, it's a pretty idea, but... I'm not convinced. True, giant insects, organic slimes, or humanoids with tentacles might incite disgust (remember the diplomat in Heinlein's *Star Beast*). But why do we expect aliens to look like something we avoid on Earth? Real aliens should be so different from anything we would recognize as organic that aversion wouldn't be aroused. Could a monolith, a hurkle, a berserker, or a beach ball make you queasy? And if aliens have anywhere near as stringent environmental requirements as humans do, our environments will probably be disjoint, so we won't see, smell, or touch anything but the inside of our life support system. Certainly, really alien aliens that we can't meet face to face are a minority in SF, but I attribute this to a lack of author imagination, effects budgets, and audience empathy. But it sure is a nice idea. ``There's only one thing wrong with the Great Red Spot... It's alive!'' Dan Hoey --- Date: 6 Dec 1985 16:21:28 EST (Fri) From: Dan Hoey Subject: Re: Obnoxious messages To: "Keith F. Lynch" Date: Thu, 5 Dec 85 23:02:09 EST From: "Keith F. Lynch" Subject: Obnoxious messages To: ihnp4!mgnetp!wnuxb!laj@UCBVAX.BERKELEY.EDU Cc: KFL@MIT-MC.ARPA, Info-Ada@USC-ISIF.ARPA, Info-Ada-Request@USC-ISIF.ARPA How about a Bronx cheer for Larry Johnson (ihnp4!mgnetp!wnuxb!laj).... Sure, but please leave "INFO-ADA" out of it. The mailing list is for discussing ADA, not obnoxious cretins. Dan --- Date: 9 Dec 1985 09:08:12 EST (Mon) From: Dan Hoey To: ALAN at MIT-MC.ARPA Subject: Re: Attractive nuisances appear regularly in Scientific American. I should have known you couldn't resist finding yet more efficient rulers, and lo, there is an ALAN;. RULER here. Well, you can probably guess I couldn't resist either. So far I've pushed the lower bound for 14-mark rulers up to 122. But eliminating 121 took a little over 3 cpu-days (68010, C), and it seems to double each time, so I'm probably not going to get much farther. I took a somewhat different approach from the strategy given the article. I add marks from both the left and from the right. This lets me quickly eliminate some large distances as being unavailable. Then I have a neat cutoff for detecting that too many of the small distances have been used up, which I'll bore you with on request. I have some ideas that might yield fruit, that I haven't implemented. For instance, suppose mark x has been selected, and marks x+d and x+2d are open. Well, marks x+d and x+2d can't be both selected. If x+3d is unavailable for some reason, then distance d is not available from mark x+2d. If this elimination can be done enough times, we be able to eliminate mark x+2d from consideration. This might speed things up if the bookkeeping isn't too slow. Just wanted to know you're not alone. Let me know what you find. Dan --- Date: 10 Dec 1985 10:48:32 EST (Tue) From: Dan Hoey To: Alan Bawden Subject: Re: Attractive nuisances From ALAN@MIT-MC.ARPA Tue Dec 10 00:24:36 1985 Date: Tue, 10 Dec 85 00:28:30 EST I was rather struck by the fact that the solutions for 7, 8, and 9 spaces are unique. I haven't seen the solutions for 11 and 12 spaces yet, I presume you have them? The shortest 11-space ruler is unique: (2 4 18 5 11 3 12 13 7 1 9). Took about an hour. I haven't got any 12-space rulers, but I will run it and get you the answer Friday, Grid willing. If you have any other particularly fruitful places where answers will help, I can get them. But finding the 12-space rulers of length 107 might take a week. Then I have a neat cutoff for detecting that too many of the small distances have been used up, which I'll bore you with on request. This sounds very similar to an idea I was playing with for a while. Not that similar, but yours is interesting. I should have known I was in for a wild new approach when I sent the note. I view the problem as one of placing the integers from 1 to N into (K^2+K)/2 bins arranged in a triangle .... Neat! If you put zeroes along the bottom of the triangle, then ruler-nature is expressed by requiring that the sum of opposite corners of each aligned parallelogram equal the sum of the other pair of corners, like A+B=C+D and D=B+E below. . . A . . . . . . D . C . . E . . . . . . . . . B . . . 0 0 0 0 0 0 You continue, For example: 17 . . 13 A . . . . . . 4 . . . . X What values can A assume? ... A can be no greater than 15 because we have to fit two -larger- numbers in the two spaces above it. Here I think you mean A can be no greater than 14, since the two larger numbers can't include 17. The rest of the argument is right. Now perhaps a program that takes advantage of a whole batch of such trivial constraints before it takes any recursive search steps would be a winner. You could even decide which cases to explore on the basis of what decision seems the most constrained in the current configuration. I have some ideas that might yield fruit, that I haven't implemented. For instance, suppose mark x has been selected, and marks x+d and x+2d are open. Well, marks x+d and x+2d can't be both selected. If x+3d is unavailable for some reason, then distance d is not available from mark x+2d. If this elimination can be done enough times, we be able to eliminate mark x+2d from consideration. This might speed things up if the bookkeeping isn't too slow. Just wanted to know you're not alone. Let me know what you find. Just when I thought I had abandoned this thing you remind me of it and here I am getting inspired to think about it some more... --- Date: 10 Dec 1985 13:02:15 EST (Tue) From: Dan Hoey To: Alan Bawden Subject: Re: Attractive nuisances To continue (oops), I just wanted to mention the cutoffs I had found. I'll deal with them assuming that distances are chosen in order from the ends, because I've thought that way so far, but there may be a generalization worth working on here. What we have at some point is triangles filled in at the bottom and a parallelogram at the top, say after choosing 0, 55, 1, 53, 6, 10, and 41, we have 55 53 54 41 52 49 . 40 47 45 . . 35 43 . . . . 31 . . 10 J K L M N O 6 9 E F G H I 14 1 5 4 A B C D 12 2 Now all the remaining distances are bounded above by 45 (or 41), so we can put 46, 48, 50, and 51 off to the side. There are a fair amount of cutoffs from noticing that there aren't enough distances left to fill the triangle. There are also a fair amount of cutoffs from noticing there aren't enough possible marks to fill the left side. In the space from 11 to 40, we have eliminated all but 21, 23, 25, 26, 28, 30, 32, 33, 34, and 38 because of their distance to existing marks. Also, 21 is the midpoint of 1-41 and 28 is the midpoint of 1-55, so they are eliminated. Each new mark removes a large number of possibilities. The intense cutoff I found, though, is related from the proof that there are no perfect rulers. Fact one is that A+B+C+D=31, just dividing up the space from 10 to 41 in four jumps. If the four smallest remaining distances add up to more than 31, continuation is impossible. Fact two is that E+G+I=47, dividing the space from 6 to 53 in three double-jumps. So if the seven smallest remaining distances add up to more than 78, continuation is impossible. I also use F+H=31, J+M=40, K+N=47, and L+O=45. There might be some mileage gained from ordering the use of these, or trying them in different orders, but I didn't do it. Interesting corrolary to the ruler-nature criterion of my last message: given any path through the triangle, with alternate edges aligned with the left and right triangle edges, say B M H C L F, the sum of the odd vertices equals the sum of the even vertices. Also, the triangle is reflected in the row of zeroes at the base. Do you know if this kind of tableau has been studied before? News flash: There are no ten-space rulers exactly 73 units long, though there are two at 72 units and at least nine at 74. Oh, and my code took half an hour to find the two rulers at 72 units, and 45 minutes to check 73. So it's somewhat faster than yours, but not incredibly. The big win is its ability to run on these 68K boxes we have. Now you've got me interested. Amazing how contagious these time-sinks are. Dan --- Newsgroups: net.announce.arpa-internet Date: 11 Dec 1985 09:55:47 EST (Wed) From: Dan Hoey Subject: Software alert: DATE-86 To: ARPANET-BBOARDS@MIT-MC.ARPA Early this year a message appeared on ARPANET-BBOARDS commemorating the ten-year anniversary of DATE-75. A somewhat more ominous anniversary will occur in four weeks, on 9 January 1986. Users of the TOPS-10 operating system should beware of software failures beginning on that date. DATE-75 is the name of a set of program modifications applied to the TOPS-10 operating system, running on DEC PDP-10 computers. Before the modifications, the TOPS-10 system could only represent dates between 1 January 1964 and 4 January 1975. The DATE-75 modifications added three more bits to the representation of dates, so that dates up to 1 February 2052 could be represented. To maximize compatibility with existing software, the three extra bits were taken from several unused positions in existing data structures. The change was announced in mid-1974, and several tens of person-years went into updating software to recognize the new dates. Unfortunately, reassembling these bits into an integer representing the date was somewhat tricky. Also, some programs had already used the spare bits for other purposes. There were a large number of bugs that surfaced on 5 January 1975, the first day whose representation required the DATE-75 modification. Many programs ignored or cleared the new bits, and thought that the date was 1 January 1964. Other programs interpreted the new bits incorrectly, and reported dates in 1986 or later. Date-related program bugs were frequent well into the Spring of 1975. On 9 January 1986, the second bit of the DATE-75 extension will come into use. Users of software developed in the 60's and early 70's on the TOPS-10 operating system should beware of problems with testing and manipulation of dates. Beware especially of programs that were patched after manifesting bugs in 1975, for in the rush to fix the bugs it is possible that some programs were modified to assume that the date was between 1975 and 1986. Any date that is off by a multiple of eleven years and four days is probably caused by this type of bug. Dan Hoey --- Date: 11 Dec 1985 15:48:04 EST (Wed) From: Dan Hoey To: SF-LOVERS Subject: Re: JOB - Mini Review from a UK viewpoint To: stc!pete@ru-caip.ARPA >From: stc!pete@caip.rutgers.edu > ... Heaven/Hell sequence is good fun. Heinlein's treatment of Heaven and Hell, and possibly the entire book, imitates James Branch Cabell's *Jurgen*, which you might guess since both are subtitled *A Comedy of Justice*. If you want to know who Koshchei really is, read it. (Read it anyway, it's a great fantasy.) But good luck finding a copy. I don't know if it's in print now; mine is from a used-book stall. Dan Hoey --- Date: 13 Dec 1985 16:09:04 EST (Fri) From: Dan Hoey To: Alan Bawden Subject: Re: Attractive nuisances Date: Thu, 12 Dec 85 03:08:51 EST From: Alan Bawden I would have guessed that a unique solution could not fail to start with a 1... (I don't know -why-, just a feeling.) I don't know if this is a corroborative counterintuitivity, but among the 12-space length 106 ruler(s), the only one found so far is (2 3 20 12 6 16 11 15 4 9 1 7) No solution starts with 1, and this is the only one starting with 2. Unfortunately, the machine crashed, and I haven't got checkpoint restart on this yet, so there won't be anything more definite this week. ...I always wind up speculating if there is something to be gained by looking for solutions mod P. I can't make that idea go anywhere unfortunately. By looking at solutions mod 2 I was able to devise an alternate way of proving that there are no perfect solutions for -some- of the larger numbers of marks, but big deal. Using this hint, I was able to prove that the number of spaces on a perfect ruler is either one less or one greater than a perfect square. Is this your result? I think this even-odd hack has strong possibilities of cutoffs for my program. Once when debugging I saw a situation where the program was investigating a situation where a lot of even marks had been put down. There were a lot of available marks, most all of them odd. And there were a lot of available distances, most all of them odd. The result was a fairly lengthy search through a doomed space. I will look at trying to turn this into a workable heuristic. I am also a little skeptical about being able to make use of larger P. When you mentioned this, I remembered a related problem that ocurred to me when I first read about rulers. What if the ruler is a circle? It seems solutions for a circular ruler would be more regular, with the elimination of edge effects, and might give insight into the straight ruler case. Dan --- Date: 16 Dec 1985 16:21:43 EST (Mon) From: Dan Hoey To: Alan Bawden Subject: Re: Attractive nuisances The program finished without finding any more rulers with 12 spaces and length 106. The only one is (2 3 20 12 6 16 11 15 4 9 1 7). Still thinking about mod-2 cutoffs. Dan --- Date: 20 Dec 1985 18:42:24 EST (Fri) From: Dan Hoey To: Alan Bawden Subject: Re: [rdz: Lonely Supercomputer Seeks Cycle-Sucker] Date: Fri, 20 Dec 85 18:04:15 EST From: Alan Bawden ...[PASTEL is] sort of a combination of PACSAL and PL/1 as I understand it. It's a good thing Ramin is interested. He suggested he would recode it. Though I might move it to PASCAL first. BTW, I sent you a message a few days ago about parity constraints in rulers.... Hmm.. I think perhaps I never got your message. I didn't say much, so you may just not have noticed, but I enclose that message and its followup at the end of this one. I engaged in a little counting for some -specific- numbers of marks/spaces and was able to show that there could be no perfect rulers with 4, 6, 7, 9, 11, and 12 spaces. Instead of being of length 10, 21, 28, 45, 66, and 78 respectively, they had to be at least of length 11, 22, 29, 47, 69, and 79. I managed the same results except that I find the 11-space ruler must be at least 68, not 69. Indeed your result explains my numbers, although I never discovered the "perfect square plus or minus one" rule. If the proof has any elegance I would be interested. Elegance is subjective, but at least this is fairly short. For M marks, let Me be the number of even marks, Mo the number of odd marks, and M'=Mo-Me. So Mo=(M+M')/2 and Me=(M-M')/2. The ruler achieves D=(M^2-M)/2 distances, Do=Mo Me=(M^2-M'^2)/4 of them odd. So D'=Do-De=2Do-D=(M-M'^2)/2. So M'^2=M-2D' must be a perfect square. For perfect rulers, D' must be either 0 or 1 according as D is even or odd, so either M or M-2 must be a perfect square. In fact, the ruler length is at least max(2De,2Do-1)=max(D-D',D+D'-1) =D+max(-D',D'-1) from which I managed to get the results you reported above, as modified. In the table below, we find the closest perfect squares M-2D'. The one that minimizes the third column is starred. That third column is just the amount of slop we have to add to D to get the ruler size. M min D'>0 max D'<=0 min(max(-D',D'-1)) 5 2 * -2 1 6 1 * -5 0 7 3 -1 * 1 8 2 * -4 1 9 4 0 * 0 10 3 * -3 2 11 1 * -7 0 12 4 -2 * 2 (we disagree here) 13 2 * -6 1 14 5 -1 * 1 15 3 * -5 2 16 6 0 * 0 17 4 * -4 3 In the place where we disagree, I think the 11-space ruler could have Mo=8, Me=4, Do=32, De=34, and length 68. ---