Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 156
AIList Digest Friday, 16 Nov 1984 Volume 2 : Issue 156
Today's Topics:
Programming Languages - Horror Stories,
Algorithms - Interlisp-D "Malgorithm",
AI Tools - DEC Software Agreements & Japanese Lisp Machines,
Seminars - Logo for Teaching Language &
Knowledge Representation and Temporal Representation
----------------------------------------------------------------------
Date: 14 Nov 84 20:45:32 EST
From: Edward.Smith@CMU-CS-SPICE
Subject: Programming Language Horror Stories
[Forwarded from the CMU bboard by Laws@SRI-AI.]
In a couple of weeks I'm going to give my last lecture in Comparative
Programming and as a way of motivating these undergraduates about the
importance of the consideration of language design in their future work I
was going to present some examples of particularly BAD (ugly or dangerous or
however you wish to define that) design. So, if you have any favorite horror
story about some programming language you'd like to contribute I would
appreciate it - I will put all the good ones up in a file somewhere. These
stories should be SHORT and to the point, and could be things like these
classics:
- the property of FORTRAN to compile and execute (generally without
complaining) a DO loop construct without a comma
- just about ANY one-line APL program (my favorite being the one-line game
of LIFE attributed to Marc Donner)
- the use of the space character in SNOBOL as (a) the separator between
labels and statements, (b) concatenation operator, (c) pattern matching
operator, or (d) separator for the pattern match assignment operator "."
- (FORTRAN's full of them) the property of early FORTRAN's to change the
value of "constants" like 5 to say 3 by an interesting parameter passing
mechanism
Please send to ets@cmu-cs-spice. Thanks in advance.
------------------------------
Date: 15 Nov 84 12:39 PST
From: JonL.pa@XEROX.ARPA
Subject: Interlisp-D "malgorithm"?
Regarding the "malgorithm" and "Logical method" proposed by
Todd.pasa@XEROX.ARPA: using the NTH function repeatedly on a list of
elements (as opposed to an array or "vector" of elements) has got to be
a classic "malgorithm". The access time for selecting the n'th element
of a list is proportional to n, whereas the similar time for arrays or
vectors should be essentially constant. The repeated selection evident
in Todd's example converts a linear algorithm into a quadratic one.
Just for the record, let me propose what I (and I suspect many other
long-time "Lisp lovers" would have considered to be the "logical"
algorithm):
(for ITEM in X as I to M collect ITEM)
A little analysis would show this to be asymptotically better than the
proposed "malgorithm" by a factor somewhere between 1 and 2 -- 2 because
the "malgorithm" traverses the M-prefix of the list X twice, and 1
because the the CONS time cost may be made arbitrarily high, thereby
occluding any other effect.
-- JonL White --
------------------------------
Date: 15 Nov 84 0524 EST
From: Dave.Touretzky@CMU-CS-A.ARPA
Subject: DEC news release
The following two paragraphs come from a medium-length article in DEC's
Large System News.
Digital Signs Marketing Agreements With Six AI Firms
Digital has signed agreements with a number of leading independent producers of
Artificial Intelligence (AI) software to market cooperatively their products
on VAX computers and personal computer systems.
Independent AI software producers include the Carnegie Group, Inc.; Digital
Research, Inc. (DIR); Gold Hill Computers; Inference Corp.; Prologia; and
USC Information Sciences Institute (ISI). AI software packages developed to
run on Digital's computers include Inference's ART, Gold Hill's GCLISP,
ISI's Interlisp, Prologia's PROLOG II, and the Carnegie Group's SRL+ and PLUME.
In two other articles in the same newsletter, Digital announced availability
of VAX Lisp 1.0 as a fully-supported Common Lisp product, and availability
of OPS5 as a supported product. Digital's OPS5 is written in Bliss-32 for
performance reasons; it includes both an interpreter and a compiler.
------------------------------
Date: 14 Nov 84 09:31:35 PST (Wed)
From: Jed Marti <marti@randgr>
Subject: Japanese Lisp Machines.
I just saw the request for information about the Fujitsu Alpha. I
recently spent a week in Japan as a guest of the RIKEN institute which
provided a tour of some of the local Tokyo efforts in this direction.
Perhaps it would be of interest to the AIList readers.
Jed Marti.
Japanese Lisp Machines
The RSYMSAC conference held at the Riken institute in Saitama, Japan on
August 21-22, provided an opportunity for a close view of Japanese
efforts to construct very fast machines for running large scale
symbolic algebra and AI programs. Four of us toured two computer
centers and three Lisp machine construction projects, talking to
implementors and trying our favorite test programs. This short report
describes the state of their systems and the Japanese symbolic algebra
environment.
FLATS at Riken
The Riken institute conducts research in the physical sciences and
operates a Fujitsu M380H (an IBM 370 look-alike) providing both time
sharing and batch services. During the day, computer algebra system
users access Cambridge Lisp running REDUCE 3.1. The symbolic
computation group operates a VAX 11/750 running VMS, a host of 16 bit
micro-computers, and the FLATS machine.
The symbolic computation group officially unveiled FLATS (Formula Lisp
Association Tuple Set) at the conference. The Mitsui Ship Building
Company constructed the hardware based on designs of the Riken group.
Built from SSI ECL components, the CPU executes a micro-instruction
every 50 nanoseconds and a Lisp instruction every 100 nanoseconds from
a 300 bit by 256 word micro store and 8 megabytes of 450 nanosecond
main memory. Over 70,000 wires connect the back plane making
conventional hardware debugging impossible. The engineers exercise
modules on a special test jig or through the attached support
processor.
The hash code generation hardware sets FLATS apart from conventional
Lisp machines. It computes a hash code in the basic machine cycle time
for extremely fast property list access and CONS cell generation.
Improvements in execution speed and program clarity more than offset
the loss of the RPLACA and RPLACD functions on hashed CONSes.
The designers increased speed with a number of special features:
3 separate cache memories for instructions, data, and stack
special micro-coded instructions for the garbage collector and
big numbers
CALL, JUMP and RETURN executed in parallel with other instructions
hardware type checking in parallel with data operations
3 address instruction codes
hardware support for paging
data path width of 64 bits
The FLATS machine, without hash CONS and property lists, runs REDUCE
3.0 at about IBM 3033 speeds. Several papers presented at RSYMSAC
described the status of FLATS and the design of the next FLATS machine
that the group hopes to construct from Josephson Junction circuits
[2-3].
University of Tokyo Computer Center
We visited the University of Tokyo Computer Center to find out more
about UTILISP (University of Tokyo Interactive LISP) implemented by the
Department of Mathematical Engineering and Instrumentation Physics
[1]). Probably one of the largest academic installations in the world,
the center operates two Hitachi M280 dual processors (roughly
equivalent to an IBM 3081) each with 32 megabytes of main storage and a
Hitachi M200H with 16 megabytes of main storage. A Hitachi S810/2
vector processor with 64 megabytes of main memory and a VAX 11/780 with
4 megabytes complement the general purpose machines. On-line storage
consists of 48 gigabytes on disk, and 37 gigabytes in data cells. The
center emphasizes user convenience. Users mount their own tapes, take
output off printers, read their own card decks (we didn't actually see
anyone do this, but the machine was there), tear off plots and so on.
The lightly loaded machines run an average of only 4,000 jobs per day.
Users need not wait for terminals and other equipment, an enviable
situation indeed.
UTILISP resembles MacLisp. An effort to transport MACSYMA to UTILISP
suffers only from the lack of built-in big number arithmetic.
Fujitsu ALPHA
A long train and subway ride brought us to the third tour stop, the
Fujitsu Laboratories in Kawasaki, home of the Lisp machine ALPHA [4-5].
The ALPHA offloads time sharing symbolic processing jobs from IBM style
mainframes. More than one ALPHA can be connected to a single mainframe,
which supplies I/O device, filing system, editing and operating system
support.
The ALPHA has 8 megabytes of real memory with a 16 megabyte virtual
address space. Memory and data buses are 32 bits wide with Lisp items
composed of an 8 bit tag and 24 bit value. The ALPHA processor has a
high speed hardware stack of 8k words with special hardware for
swapping segments to and from slower memory. The division of the stack
into blocks permits high speed switching between different processes.
To support tagged data items, a micro-instruction jump based on the 8
bit tag is implemented. The ALPHA machine performs data calculations by
masking off the tag bits in hardware, rather than software. The machine
has over 7700 STTL, 64k bit RAMs and 4k high speed RAMs.
Micro Instructions - 48 bits wide, 160 ns, 16k words.
Main Memory - Virtual 16 M words, Real 8 M words,
Page size 4 K bytes.
Stack - Logical stack 64 K words, Hardware stack 8 K words,
Swapping block size 2 K bytes.
The ALPHA runs UTILISP and has an interpreter, compiler, and copying
garbage collector. Fujitsu claims the ALPHA runs three times faster
than the Symbolics 3600 and 5 times faster than DEC 2060 MACLISP.
Fujitsu uses the ALPHA for CAD, machine translation, and natural
language understanding.
ELIS - Nippon Telegraph and Telephone Public Corporation
Nippon Telegraph and Telephone Public Corporation demonstrated the ELIS
machine and TAO language a "harmonic" mixture of Lisp, Smalltalk, and
Prolog, to quote the authors [6]. A PDP 11/60 provides file and
operating system support while the ELIS hardware performs the list
processing functions. The ELIS hardware features 32 bit items with 8
bit tags providing for 16 million items (128 megabytes). The basic
microcycle time is 180 ns in 32k of micro-instructions 64 bits wide.
Main memory is 4 megabytes with an access time of 420 ns and a special
system stack of 32k 32 bit items. Deep binding is used and multiple
processes are supported by stack groups, and the cpu switches between
contexts very fast (2 microseconds unless there is some stack
swapping). For identical tasks programmed in the three different
paradigms, the procedural version provides the most speed with the
object oriented version about 1.1 times as slow and the logic version
about twice as slow.
Acknowledgement: I would like to thank Dr. N. Inada of Riken for
organizing both RSYMSAC and the tour.
List of References
1. Chikayama, Takashi, `UTILISP Manual', Technical Report METR 81-6
(September 1981), Department of Mathematical Engineering and
Instrumentation Physics, University of Tokyo, Bunkyo-Ku, Tokyo,
Japan.
2. Goto, E., Shimizu, K., `Architecture of a Josephson Computer
(FLATS-2)', RSYMSAC, Wako-shi, Saitama, 351-01 Japan, 1984.
3. Goto, E., Soma, T., Inada, N., et al, 'FLATS: A Machine for
Symbolic and Algebraic Manipulation', RSYMSAC, Riken, Wako-shi,
Saitama, 351-01 Japan, 1984.
4. Hayashi, H., Hattori, A., Akimoto, H., `ALPHA: A High-Performance
LISP Machine with a New Stack Structure and Garbage Collection
System', Proceedings of the 10th Annual International Symposium
on Computer Architecture, pages 342-347.
5. Hayashi, H., Hattori, A., Akimoto, H., `LISP Machine "ALPHA"',
Fujitsu Scientific and Technical Journal, Vol. 20, No. 2,
pages 219-234.
6. Okuno, H. G., Takeuchi, I., Osato, N., Hibino, Y., Watanabe, K.,
`TAO: A Fast Interpreter-Centered System on Lisp Machine ELIS',
Proceedings of the 1984 Conference on LISP and Functional
Programming.
Jed Marti MARTI@RAND-UNIX
------------------------------
Date: 9 November 1984 1359-EST
From: Jeff Shrager@CMU-CS-A
Subject: Seminar - Logo for Teaching Language
[Forwarded from the CMU bboard by Laws@SRI-AI.]
Subject: Guest speaker on teaching language with LOGO
Source: charney (davida charney @ cmu-psy-a)
English Department -- Guest Speaker
NAME: Wallace Feurzeig (Bolt, Beranek and Newman)
DATE: Friday, November 16
TIME: 9 - 10:30 am (There will be coffee and doughnuts.)
PLACE: Adamson Wing in Baker Hall
TITLE: Exploring Language with Logo
The talk gives examples of materials from our forthcoming book "Exploring
Language with Logo" to be published by Harper and Row o/a first quarter,
1985, co-authored by Paul Goldenberg and Wallace Feurzeig. The book
attempts to develop a qualitatively different approach to the teaching of
language arts in schools. Our approach is based on two major intellectual
developments -- the theory of generative grammar in formal linguistics and
the invention of programming languages. The important new idea from
linguistics is that a grammar can be used as a constructive instrument to
generate sentences, in contrast to the conventional school experience of
grammar as an analytic device, a set of tools for parsing sentences to
determine whether or not they are instances of "good" English. This shift
has enormous psychological and pedagogical benefits: it switches the
learner's focus and viewpoint from rule learner to language creator. At the
same time, it provides a distinctly different, more accessible and
acceptable way of introducing the formal structures of language and the
regularities and rules describing these structures.
The other major intellectual development, programming languages, provides
the most distinctive and radical departure from the present language arts
course. Our approach depends fundamentally upon programming ideas and
activities. In our presentation, the key and central language concepts are
introduced and developed as Logo programs. Teachers and students are engaged
in programming projects throughout. The use of a programming language in the
English language classrooom makes the idea of generative grammars concrete
in tasks readily accessible to schoolchildren. Moreover, in the environment
of programming, grammar models are transformed from highly abstract
formalisms into runnable objects in semantic situations that are meaningful
and interesting to students. For example, students can create Logo programs
that simulate the grammar of gossip, puns, jokes, love letters, baby talk,
proverbs, quizzes, conversational discourse, poems of various forms and
expressive styles, and many other kinds of texts. Examples will illustrate
the approach and materials at three levels: the structure of sentences,
structures within a word, and larger structures.
------------------------------
Date: 13 November 1984 11:12-EST
From: Rosemary B. Hegg <ROSIE @ MIT-MC>
Subject: Seminar - Knowledge Representation and Temporal Representation
[Forwarded from the MIT bboard by Laws@SRI-AI.]
COOPERATIVE COMPUTATION, KNOWLEDGE ORGANIZATION AND TIME
John K. Tsotsos
Department of Computer Science
University of Toronto
Toronto, Ontario, Canada
DATE: Friday, November 16, 1984
TIME: 1.45 pm Refreshments
2.00 pm Lecture
PLACE: NE43-7th Floor Playroom
A cooperative processing scheme is presented that deals with
time-varying information. It operates over a network of temporal
concepts, organized along common representational axes:generali-
zation, aggregation, similarity and temporal precedence. Units
in this network are organized into computation layers, and these
layers are conceptualized as "recognizing" concepts that can be
organized along a generalization / specialization dimension.
Thus elements of both "localist" and "distributed" views of con-
cept representations are present. Static and dynamic data in the
same way - as samples over time, and thus, sampling issues are
directly addressed. This process is a time-varying non-linear
optimization task; it differs from past cooperative computation
schemes in three respects: a) our information is not uniform but
rather different concepts are represented at different levels of
the hierarchies; b) there are multiple interacting networks, each
organized according to different semantics; c) the data is time-
varying and more importantly, the structure over which relaxa-
tion is performed is time-varying. The cooperative process to be
described has the qualitative properties we believe are desirable
for temporal interpretation, and its performance will be
described empirically, and in a qualitative fashion through the
use of several examples.
HOST: Prof. Peter Szolovits
------------------------------
End of AIList Digest
********************
