From: gorilla@elaine.furryape.com (Alan Barclay) Newsgroups: alt.folklore.computers Subject: diff's history Date: 16 Jan 2002 23:51:33 GMT Organization: Ye 'Ol Disorganized NNTPCache groupie Lines: 2 Message-ID: <1011225093.897928@elaine.furryape.com> NNTP-Posting-Host: p-036.newsdawg.com X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Originator: gorilla@elaine.furryape.com (Alan Barclay) Cache-Post-Path: elaine.furryape.com!unknown@elaine.furryape.com X-Cache: nntpcache 2.4.0b5 (see http://www.nntpcache.org/) Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!news-fra1.dfn.de!news-lei1.dfn.de!news-was.dfn.de!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!logbridge.uoregon.edu!pln-e!spln!dex!extra.newsguy.com!newsp.newsguy.com!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:99058 When was diff introduced to Unix? I know it was in v7, but I'm guessing that it was in earlier versions too. ###### From: jmfbahciv@aol.com Newsgroups: alt.folklore.computers Subject: Re: diff's history Date: Fri, 18 Jan 02 10:44:34 GMT Organization: UltraNet Communications, Inc. Lines: 42 Message-ID: References: <1011225093.897928@elaine.furryape.com> <3C4663C5.CAF9B28D@bell-labs.com> <3C479177.7080500@multicians.org> X-Trace: UmFuZG9tSVaNwObR7OFAgrVrfyn3YNIP+/8kF07AdLzapuxulYgy48Yk6C8EUo5U X-Complaints-To: abuse@rcn.com NNTP-Posting-Date: 18 Jan 2002 12:54:07 GMT X-Newsreader: News Xpress Version 1.0 Beta #4 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!newsfeeds.belnet.be!news.belnet.be!news.tele.dk!small.news.tele.dk!4.1.16.34!cpk-news-hub1.bbnplanet.com!news.gtei.net!feed2.news.rcn.net!feed1.news.rcn.net!rcn!207-172-255-123 Xref: chonsp.franklin.ch alt.folklore.computers:99032 In article <3C479177.7080500@multicians.org>, Tom Van Vleck wrote: >Dennis Ritchie wrote: > >> Alan Barclay asked: >> >>>When was diff introduced to Unix? I know it was in v7, but I'm guessing >>>that it was in earlier versions too. >>> >> >> Fifth edition (June 1975). It wasn't in Fourth (1973). >> >> The 5th ed. manual says "diff does an unfailing job of detecting >> the file differences, and also reports the differences side-by-side. >> However, diff uses a quadratic algorithm that usually slows to a >> crawl on 2000-line files." -- to which (in my copy of the manual) >> I have added a note: "better now." > > >The Multics compare_ascii (cpa) command may >have been an ancestor to Unix diff. It was present in 645 >Multics in the late 1960s. I think it too used >a quadratic algorithm and could become very slow on >files that were completely different. Multics later added >merge_ascii (ma), similar to Unix merge3, as described in > http://www.multicians.org/mullen-paper.html TOPS-10 and TOPS-20 shipped a program called FILCOM which was a combination of SRCCOM and BINCOM (I think that's how they were spelled). I was last maintainer of FILCOM but I couldn't tell you its algorithms. I looked at the code once and decided that it was a piece that was better left untouched. When it was touched to "fix" an anomoly, the anomoly didn't happen anymore, but the normal use of the program became very broke. I don't remember it being "slow" when the whole compare was one difference. It could be the way it did the I/O. /BAH Subtract a hundred and four for e-mail. ###### From: Dennis Ritchie Newsgroups: alt.folklore.computers Subject: Re: diff's history Date: Thu, 17 Jan 2002 05:40:21 +0000 Organization: Bell Labs / Lucent Technologies Lines: 19 Message-ID: <3C4663C5.CAF9B28D@bell-labs.com> References: <1011225093.897928@elaine.furryape.com> NNTP-Posting-Host: 135.104.65.78 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.61 [en] (WinNT; U) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newscore.univie.ac.at!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newspeer.radix.net!uunet!ash.uu.net!nntphub.cb.lucent.com!news Xref: chonsp.franklin.ch alt.folklore.computers:99018 Alan Barclay asked: > > When was diff introduced to Unix? I know it was in v7, but I'm guessing > that it was in earlier versions too. Fifth edition (June 1975). It wasn't in Fourth (1973). The 5th ed. manual says "diff does an unfailing job of detecting the file differences, and also reports the differences side-by-side. However, diff uses a quadratic algorithm that usually slows to a crawl on 2000-line files." -- to which (in my copy of the manual) I have added a note: "better now." McIlroy has a postscript rendition of a paper (Bell Labs CSTR #41) describing the improved version under his home page at http://www.cs.dartmouth.edu/~doug Dennis ###### From: Tom Van Vleck Newsgroups: alt.folklore.computers Subject: Re: diff's history Date: Thu, 17 Jan 2002 22:07:35 -0500 Organization: Multicians Lines: 27 Message-ID: <3C479177.7080500@multicians.org> References: <1011225093.897928@elaine.furryape.com> <3C4663C5.CAF9B28D@bell-labs.com> NNTP-Posting-Host: 3f.d0.b8.ce Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Server-Date: 18 Jan 2002 03:06:51 GMT User-Agent: Mozilla/5.0 (Windows; U; Win98; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 X-Accept-Language: en,pdf Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newscore.univie.ac.at!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.earthlink.net!newsfeed2.earthlink.net!newsfeed.earthlink.net!news.mindspring.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:99023 Dennis Ritchie wrote: > Alan Barclay asked: > >>When was diff introduced to Unix? I know it was in v7, but I'm guessing >>that it was in earlier versions too. >> > > Fifth edition (June 1975). It wasn't in Fourth (1973). > > The 5th ed. manual says "diff does an unfailing job of detecting > the file differences, and also reports the differences side-by-side. > However, diff uses a quadratic algorithm that usually slows to a > crawl on 2000-line files." -- to which (in my copy of the manual) > I have added a note: "better now." The Multics compare_ascii (cpa) command may have been an ancestor to Unix diff. It was present in 645 Multics in the late 1960s. I think it too used a quadratic algorithm and could become very slow on files that were completely different. Multics later added merge_ascii (ma), similar to Unix merge3, as described in http://www.multicians.org/mullen-paper.html ###### From: jmfbahciv@aol.com Newsgroups: alt.folklore.computers Subject: Re: diff's history Date: Sat, 19 Jan 02 10:23:58 GMT Organization: UltraNet Communications, Inc. Lines: 78 Message-ID: References: <1011225093.897928@elaine.furryape.com> <3C4663C5.CAF9B28D@bell-labs.com> <3C479177.7080500@multicians.org> <3C48B04E.CE20581E@ev1.net> X-Trace: UmFuZG9tSVZ8CN7UZwOKRffsYrZhYeXMcH6vVNBHnxuYPAfVwE99FLc1qrVW5qHp X-Complaints-To: abuse@rcn.com NNTP-Posting-Date: 19 Jan 2002 12:33:40 GMT X-Newsreader: News Xpress Version 1.0 Beta #4 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!14423!news.imp.ch!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feed2.news.rcn.net!feed1.news.rcn.net!rcn!207-172-245-81 Xref: chonsp.franklin.ch alt.folklore.computers:99148 In article <3C48B04E.CE20581E@ev1.net>, Charles Richmond wrote: >jmfbahciv@aol.com wrote: >> >> In article <3C479177.7080500@multicians.org>, >> Tom Van Vleck wrote: >> >Dennis Ritchie wrote: >> > >> >> Alan Barclay asked: >> >> >> >>>When was diff introduced to Unix? I know it was in v7, but I'm guessing >> >>>that it was in earlier versions too. >> >>> >> >> >> >> Fifth edition (June 1975). It wasn't in Fourth (1973). >> >> >> >> The 5th ed. manual says "diff does an unfailing job of detecting >> >> the file differences, and also reports the differences side-by-side. >> >> However, diff uses a quadratic algorithm that usually slows to a >> >> crawl on 2000-line files." -- to which (in my copy of the manual) >> >> I have added a note: "better now." >> > >> > >> >The Multics compare_ascii (cpa) command may >> >have been an ancestor to Unix diff. It was present in 645 >> >Multics in the late 1960s. I think it too used >> >a quadratic algorithm and could become very slow on >> >files that were completely different. Multics later added >> >merge_ascii (ma), similar to Unix merge3, as described in >> > http://www.multicians.org/mullen-paper.html >> >> TOPS-10 and TOPS-20 shipped a program called FILCOM which >> was a combination of SRCCOM and BINCOM (I think that's how >> they were spelled). I was last maintainer of FILCOM but >> I couldn't tell you its algorithms. I looked at the code >> once and decided that it was a piece that was better left >> untouched. When it was touched to "fix" an anomoly, the >> anomoly didn't happen anymore, but the normal use of the >> program became very broke. >> >> I don't remember it being "slow" when the whole compare was >> one difference. It could be the way it did the I/O. >> >Looking on page 200 of the book _The UNIX Programming >Environment_, by Kernighan and Pike, McIlroy based the >algorithm used in "diff" on an algorithm "invented >independently by Harold Stone and by Wayne Hunt and >Tom Szymanski." The reference given is "A fast algorithm >for computering longest common subsequences", by J.W. Hunt >and T.G. Szymanski, CACM, May 1977. > >The algorithm used in diff is described in Bell Labs Tech >Report 41 in 1976, written by McIlroy and J.W. Hunt titled: >"An algorithm for differential file comparison." I think >this is the paper available on McIlroy's WEB sit. So if >Multics or either of TOPS-10 or TOPS-20 used it, it must >be *after* 1976. Then it can't have used it. I don't think FILCOM was changed very much after [best guess] 1973. I can't remember if we ever put SFD support into it. > >The book quotes McIlroy as saying: "I had tried at least >three completely different algorithms before the final one. >diff is a quintessential case of not settling for mere >compentency in a program but revising it until it was right." > That was apparently the modus operedi for that kind of application. FILCOM's code looked exactly like that. Whenever I encountered code looking like that, I did not touch it. I knew I wasn't smart enough. /BAH Subtract a hundred and four for e-mail. ###### Message-ID: <3C48B04E.CE20581E@ev1.net> From: Charles Richmond Reply-To: richmond@ev1.net Organization: Cannine Computer Center X-Mailer: Mozilla 4.7C-CCK-MCD {C-UDP; EBM-APPLE} (Macintosh; I; PPC) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: alt.folklore.computers Subject: Re: diff's history References: <1011225093.897928@elaine.furryape.com> <3C4663C5.CAF9B28D@bell-labs.com> <3C479177.7080500@multicians.org> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 65 NNTP-Posting-Host: 12.237.69.87 X-Complaints-To: abuse@attbi.com X-Trace: rwcrnsc54 1011389451 12.237.69.87 (Fri, 18 Jan 2002 21:30:51 GMT) NNTP-Posting-Date: Fri, 18 Jan 2002 21:30:51 GMT Date: Fri, 18 Jan 2002 21:30:51 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!news.maxwell.syr.edu!newsfeed.cwix.com!wn2feed!wn3feed!worldnet.att.net!204.127.198.204!attbi_feed4!attbi.com!rwcrnsc54.POSTED!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:99209 jmfbahciv@aol.com wrote: > > In article <3C479177.7080500@multicians.org>, > Tom Van Vleck wrote: > >Dennis Ritchie wrote: > > > >> Alan Barclay asked: > >> > >>>When was diff introduced to Unix? I know it was in v7, but I'm guessing > >>>that it was in earlier versions too. > >>> > >> > >> Fifth edition (June 1975). It wasn't in Fourth (1973). > >> > >> The 5th ed. manual says "diff does an unfailing job of detecting > >> the file differences, and also reports the differences side-by-side. > >> However, diff uses a quadratic algorithm that usually slows to a > >> crawl on 2000-line files." -- to which (in my copy of the manual) > >> I have added a note: "better now." > > > > > >The Multics compare_ascii (cpa) command may > >have been an ancestor to Unix diff. It was present in 645 > >Multics in the late 1960s. I think it too used > >a quadratic algorithm and could become very slow on > >files that were completely different. Multics later added > >merge_ascii (ma), similar to Unix merge3, as described in > > http://www.multicians.org/mullen-paper.html > > TOPS-10 and TOPS-20 shipped a program called FILCOM which > was a combination of SRCCOM and BINCOM (I think that's how > they were spelled). I was last maintainer of FILCOM but > I couldn't tell you its algorithms. I looked at the code > once and decided that it was a piece that was better left > untouched. When it was touched to "fix" an anomoly, the > anomoly didn't happen anymore, but the normal use of the > program became very broke. > > I don't remember it being "slow" when the whole compare was > one difference. It could be the way it did the I/O. > Looking on page 200 of the book _The UNIX Programming Environment_, by Kernighan and Pike, McIlroy based the algorithm used in "diff" on an algorithm "invented independently by Harold Stone and by Wayne Hunt and Tom Szymanski." The reference given is "A fast algorithm for computering longest common subsequences", by J.W. Hunt and T.G. Szymanski, CACM, May 1977. The algorithm used in diff is described in Bell Labs Tech Report 41 in 1976, written by McIlroy and J.W. Hunt titled: "An algorithm for differential file comparison." I think this is the paper available on McIlroy's WEB sit. So if Multics or either of TOPS-10 or TOPS-20 used it, it must be *after* 1976. The book quotes McIlroy as saying: "I had tried at least three completely different algorithms before the final one. diff is a quintessential case of not settling for mere compentency in a program but revising it until it was right." -- +-------------------------------------------------------------+ | Charles and Francis Richmond | +-------------------------------------------------------------+ ###### Message-ID: <3C494499.4A206EF5@trailing-edge.com> Date: Sat, 19 Jan 2002 10:04:09 -0400 From: Tim Shoppa Organization: Trailing Edge Technology X-Mailer: Mozilla 3.03Gold (X11; I; OpenVMS V7.2 AlphaServer 1200 5/533 4MB) MIME-Version: 1.0 Newsgroups: alt.folklore.computers Subject: Re: diff's history References: <1011225093.897928@elaine.furryape.com> <3C4663C5.CAF9B28D@bell-labs.com> <3C479177.7080500@multicians.org> <3C48B04E.CE20581E@ev1.net> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 20 NNTP-Posting-Host: 63.73.218.130 X-Trace: 1011452647 reader0.ash.ops.us.uu.net 712 63.73.218.130 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!newsfeed00.sul.t-online.de!t-online.de!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!cpk-news-hub1.bbnplanet.com!news.gtei.net!newsfeed1.cidera.com!Cidera!portc01.blue.aol.com!uunet!dca.uu.net!ash.uu.net!spool0900.news.uu.net!reader0900.news.uu.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:99173 jmfbahciv@aol.com wrote: > TOPS-10 and TOPS-20 shipped a program called FILCOM which > was a combination of SRCCOM and BINCOM (I think that's how > they were spelled). I was last maintainer of FILCOM but > I couldn't tell you its algorithms. I looked at the code > once and decided that it was a piece that was better left > untouched. When it was touched to "fix" an anomoly, the > anomoly didn't happen anymore, but the normal use of the > program became very broke. The earliest PDP-10 mention of SRCCOM I've found is datestamped October 1971 and is in http://new-pdp-10.trailing-edge.com/cuspmar86binsrc_2of2_bb-fp63a-sb/10,7/soup/compar.mac It claims to be Version 3 and is attributed to CWRU/CAM, but even this cannot be the first because it talks about producing output that is compatible with SRCCOM. Tim.