Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 8/7/84; site ucbvax.ARPA Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!LAWS@SRI-AI.ARPA From: LAWS@SRI-AI.ARPA Newsgroups: net.ai Subject: AIList Digest V2 #147 Message-ID: <3274@ucbvax.ARPA> Date: Wed, 14-Nov-84 12:23:57 EST Article-I.D.: ucbvax.3274 Posted: Wed Nov 14 12:23:57 1984 Date-Received: Thu, 15-Nov-84 03:29:02 EST Sender: daemon@ucbvax.ARPA Organization: University of California at Berkeley Lines: 384 From: AIList Moderator Kenneth Laws AIList Digest Wednesday, 31 Oct 1984 Volume 2 : Issue 147 Today's Topics: LISP - Function-itis & Comparison with C, Algorithms - Pessimal Algorithms & Real Programmers, Seminars - Robot Navigation & Accessibility of Analogies & Student Models ---------------------------------------------------------------------- Date: Sun 28 Oct 84 17:40:10-PST From: Shawn Amirsardary Subject: Lisp Function-itis [Forwarded from the Stanford bboard by Laws@SRI-AI.] Lisp with its very elegant syntax suffers from acute function-itis. When adhering to the traditional lispish style of using very few setq and god forbid even fewer progs, you end up with about a million and a half functions that get called from usually only one place. Of course LET and lambda help, but not that much. My question is does anybody know of a good method for ordering and perhaps even naming the little suckers? In pascal you have to define procedures before you use them, but the lack of such restrictions in lisp means that functions are all over the place. What is the cure? --Shawn ------------------------------ Date: Tue, 30 Oct 84 21:42:58 -0200 From: eyal@wisdom (Eyal mozes) Subject: Re: different language types > But seriously, one can adopt a very abstract (i.e. applicative/functional) > programming style or a very imperative (C-like) style when using Lisp. > On the other hand, adopting an applicative style in C is difficult (yes, > I've tried!). So Lisp is certainly more versatile. Really!! I've never yet seen an "imperative" non-trivial LISP program which is not impossible to read, full of bugs which nobody knows how to correct, and horribly time-consuming (most of UNIX's VAXIMA is a good example of what I mean). Writing "imperative" style in LISP is a programming equivalent of "badgorithms". You can be as abstract as you want to be in C or Pascal. I don't think there is anything for which you can't come up with a good program in C, if your writing style is good (and if it isn't, no language will help). Of course, there are some activities, especially in some areas of AI, which are made much easier by the functional style of LISP, and its representation of programs as data - but even this wouldn't be true for *all* AI systems. But in terms of versatility, I don't think there can be much question about the big advantage of C, Pascal, and languages of this type. ------------------------------ Date: 29 Oct 84 14:41 PST From: JonL.pa@XEROX.ARPA Subject: Pessimal Algorithms ("Badgorithms"?) The following "badgorithm" comes from a practical joke, perpretated many years ago; although it is not a naturally occuring "badgorithm", it does have a humorous side. In high school, I worked part-time for a university computing center ** programming on an IBM 650 (don't ask how many years ago!). [One really shouldn't pooh-pooh the 650 -- it was the world's first List processing computer! explication follows]. It's main memory consisted of 2000 10-digit decimal words, stored on a rotating magnetic drum; there were 40 rotational channels on the drum, with each channel holding 50 words (one complete revolution). Since the various instructions took a variable amount of time, it would be most unwise to sequence the instructions by merely incrementing each instruction address by 1, for an instruction which took more time than that which would elapse between two successive words in a "channel" would thus be blocked for one full drum rotation time. An instruction consisted of an operator, an operand address, and a "next instruction address" (i.e., a CDR link in Lisp parlance); thus one could assign the sequenceing of instructions to be "optimal" in that the successor of an instruction at word offset A (mod 50) would be A+n (mod 50) where n is the time in, fiftieths of a drum rotation, required for the instruction exection of the operator stored at A. The IBM 704/709 series had a machine language assembler called SAP, for "Symbolic Assembly Program"; the 650 had SOAP, for "Symbolic Optimal Assembly Program". One would speak of "Soaping" a program, meaning to assemble a symbolic deck of cards into a self-loading machine-language deck. My cohorts and I dubbed the obvious pessimizing version of SOAP as SUDS, for "Symbolic Un-optimal Disassembly System" (it would assign the "next instruction" to a word offset just 1 short of optimal, and thus would slow down the resultant object code by up to a factor of 50). As a gag, we SUDS'd the SOAP deck, and left it for others to use. Imagine the consternation when a program that normally took 10 minutes to assemble suddenly began taking over an hour! Of course, we were quickly found out, and SUDS was relagated to the circular hacks file. -- Jon L White -- ------------------------------ Date: 22 Oct 84 16:18:41 EDT From: Michael.Jones@CMU-CS-SPICE Subject: Real Programmers [Excerpted from the CMU bboard by Laws@SRI-AI.] [I regret having to truncate this, but the original was too long to distribute on AIList. I have decide to proceed with the following because it fits in with other recent AIList messages. -- KIL] A recent article devoted to the *macho* side of programming made the bald and unvarnished statement: Real Programmers write in Fortran. [...] I feel duty-bound to describe, as best I can through the generation gap, how a Real Programmer wrote code. I'll call him Mel, because that was his name. I first met Mel when I went to work for Royal McBee Computer Corp., a now-defunct subsidiary of the typewriter company. [...] Mel's job was to re-write the blackjack program for the RPC-4000. [...] The new computer had a one-plus-one addressing scheme, in which each machine instruction, in addition to the operation code and the address of the needed operand, had a second address that indicated where, on the revolving drum, the next instruction was located. In modern parlance, every single instruction was followed by a GO TO! [...] Since Mel knew the numerical value of every operation code, and assigned his own drum addresses, every instruction he wrote could also be considered a numerical constant. He could pick up an earlier "add" instruction, say, and multiply by it, if it had the right numeric value. His code was not easy for someone else to modify. I compared Mel's hand-optimized programs with the same code massaged by the optimizing assembler program, and Mel's always ran faster. That was because the "top-down" method of program design hadn't been invented yet, and Mel wouldn't have used it anyway. He wrote the innermost parts of his program loops first, so they would get first choice of the optimum address locations on the drum. The optimizing assembler wasn't smart enough to do it that way. Mel never wrote time-delay loops, either, even when the balky Flexowriter required a delay between output characters to work right. He just located instructions on the drum so each successive one was just *past* the read head when it was needed; the drum had to execute another complete revolution to find the next instruction. [...] Mel called the maximum time-delay locations the "most pessimum". [...] Perhaps my greatest shock came when I found an innocent loop that had no test in it. No test. *None*. Common sense said it had to be a closed loop, where the program would circle, forever, endlessly. Program control passed right through it, however, and safely out the other side. It took me two weeks to figure it out. The RPC-4000 computer had a really modern facility called an index register. It allowed the programmer to write a program loop that used an indexed instruction inside; each time through, the number in the index register was added to the address of that instruction, so it would refer to the next datum in a series. He had only to increment the index register each time through. Mel never used it. Instead, he would pull the instruction into a machine register, add one to its address, and store it back. He would then execute the modified instruction right from the register. The loop was written so this additional execution time was taken into account -- just as this instruction finished, the next one was right under the drum's read head, ready to go. But the loop had no test in it. The vital clue came when I noticed the index register bit, the bit that lay between the address and the operation code in the instruction word, was turned on-- yet Mel never used the index register, leaving it zero all the time. When the light went on it nearly blinded me. He had located the data he was working on near the top of memory -- the largest locations the instructions could address -- so, after the last datum was handled, incrementing the instruction address would make it overflow. The carry would add one to the operation code, changing it to the next one in the instruction set: a jump instruction. Sure enough, the next program instruction was in address location zero, and the program went happily on its way. I haven't kept in touch with Mel, so I don't know if he ever gave in to the flood of change that has washed over programming techniques since those long-gone days. I like to think he didn't. In any event, I was impressed enough that I quit looking for the offending test, telling the Big Boss I couldn't find it. [...] I didn't feel comfortable hacking up the code of a Real Programmer." -- Source: usenet: utastro!nather, May 21, 1983. [The Cray is so fast it can execute an infinite loop in three minutes? This machine might beat it! -- KIL] ------------------------------ Date: 28 Oct 1984 14:43 EST (Sun) From: "Daniel S. Weld" Subject: Seminar - Robot Navigation [Forwarded from the MIT bboard by SASW@MIT-MC.] Wednesday, October 31; 4:00pm; 8th Floor Playroom Navigation for Mobile Robots Rodney A. Brooks There are a large number of interesting questions in how to build a mobile robot capable of navigating through unknown surroundings in order to complete some desired task. Issues include obstacle avoidance using local observations, overall path planning, registration with a map and building a map from observations. There is a lot of ongoing and promising work on the first two of these problems. Less has been done on the last two. Registration work has been most succesful with detailed a priori maps in two domains: (1) indoors uncluttered areas with flat walls giving unambigous geometric clues, and (2) areas with reliably identifiable and accurately locatable landmarks visible over a large area. Re-registration with maps generated from a robot's own observations has mainly been successful in two modes: (1) incremental re-registration involving small motions from a known location, or (2) in an environment with active beacons providing reliably indentifiable and locatable landmarks. This talk focus on some of the issues in building a map from unreliable observations and in re-registering the robot to that map much later, again using unreliable observations. In particular we consider a new map represention, the requirements on the representations of the world produced by vision, the role of landmarks, and whether other sensors such as compasses or inertial navigation systems are needed. COMING SOON: Kent Pitman [Nov 7], Ryszard Michalski [Nov 14], Phil Agre [Nov 28] ------------------------------ Date: 29 Oct 1984 14:10-EST From: Brad Goodman Subject: Seminar - Accessibility of Analogies [Forwarded from the MIT bboard by SASW@MIT-MC.] "Mental Models of Electricity" Yvette Tenney, BBN Laboratories Hermann Hartel, University of Kiel, West Germany BBN Laboratories, 10 Moulton St, Cambridge. Third floor large conference room, 10:30 AM. Monday November 5th. The presentation will consist of two short talks that were part of a conference on Representations of Students' Knowledge in Electricity and the Improvement of Teaching, held in Ludwigsburg, Germany this fall. Talk 1: Yvette Tenney (in collaboration with Dedre Gentner) "What makes analogies accessible: Experiments on the water-flow analogy for electricity." In analogy, knowledge can be transferred from a known (base) domain to a target domain, provided the learner accesses the analogy. We used the water-electric current analogy to test the hypothesis that prior familiarity with the base domain (Experiment 1) and pre-training on the base domain (Experiment 2) increase the likelihood of noticing the analogy. Results showed that greater knowledge of the base domain did not increase accessibility, although it did increase the power of the analogy if detected. Talk 2: Hermann Hartel "The electric circuit as a system: A new approach." [...] ------------------------------ Date: Tue 30 Oct 84 09:28:59-PST From: Paula Edmisten Subject: Seminar - Student Models [Forwarded from the Stanford SIGLUNCH distribution by Laws@SRI-AI.] DATE: Friday, November 2, 1984 LOCATION: Chemistry Gazebo, between Physical and Organic Chemistry TIME: 12:05 SPEAKER: Derek Sleeman School of Education & HPP ABSTRACT: The PIXIE Project: The Inference and Use of Student (user) Models For a decade or more the importance of having accurate student models to guide Intelligent Tutoring Systems (ITSs) has been stressed. I will give an overview of the several types of models which have been inferred and will talk in some detail about a system which infers overlay models and Pixie which uses process-orientated models. Currently, all these techniques effectively determine whether the current user's behaviour falls within a previously defined model-space. The focus of some current work is to see whether these techniques can be extended to be more data-sensitive. (Analogous issues arise when an ITS or ES is attempting to reason with an incomplete database.) Issues which arise in the use of models to control (remedial) dialogues will be addressed. The seminar will conclude with an overview of the fieldwork shortly to be undertaken. PIXIE now runs on a PC (in LISP) and several of these machines will be used to "diagnose" the difficulties which high school students have with Algebra and maybe Arithmetic. It is envisaged that PIXIE will be used to screen several classes, and that the class teachers will remediate students on the basis of the diagnostic information provided by PIXIE. These sessions will then be analyzed to determine how "real" teachers remediate; remedial subsystem(s) for PIXIE will then be implemented. Paula ------------------------------ End of AIList Digest ********************