Copy Link
Add to Bookmark
Report
AIList Digest Volume 5 Issue 135
AIList Digest Tuesday, 2 Jun 1987 Volume 5 : Issue 135
Today's Topics:
Bindings - NL-KR the List,
Theory - Philosophy and Computational Complexity,
Applications - Computer Grading and the Law & Solid Geometry &
The Synthesizer Generator
----------------------------------------------------------------------
Date: Fri, 29 May 87 17:11 EDT
From: Brad Miller <miller@ACORN.CS.ROCHESTER.EDU>
Subject: NL-KR the list...
Is now available on USENET in group comp.ai.nlang-know-rep as part of the
massive USENET project to have all arpa lists forwarded to their own groups.
If you can receive this group and would prefer to read the digests there,
please send a message to nl-kr-request@cs.rochester.edu so I can remove you
from the separate mailing list.
Brad Miller
nl-kr moderator
nl-kr-request@cs.rochester.edu
[I have been forwarding the recent comp.ai linguistics discussion
to the NL-KR list (instead of to the Arpanet AIList digest). Now
that NL-KR is available via Usenet, I would suggest that the discussion
move there. In that way the Usenet participants will not be missing
out on the cogent repies of the NL-KR linguists. I assume that your
submissions should go to nl-kr@cs.rochester.edu and that you can then
read all of the replies on comp.ai.nlang-know-rep. -- KIL]
------------------------------
Date: Mon, 1 Jun 87 09:18:28 EDT
From: "William J. Rapaport" <rapaport%buffalo.csnet@RELAY.CS.NET>
Subject: philosophy and computational complexity
A good _philosophical_ reference is:
Christopher Cherniak, "Computational Complexity and the Universal Acceptance
of Logic," _Journal of Philosophy_ 81 (1984) 739-758.
William J. Rapaport
Assistant Professor
Dept. of Computer Science, SUNY Buffalo, Buffalo, NY 14260
(716) 636-3193, 3180
uucp: ..!{allegra,decvax,watmath,rocksanne}!sunybcs!rapaport
csnet: rapaport@buffalo.csnet
bitnet: rapaport@sunybcs.bitnet
------------------------------
Date: Mon 1 Jun 87 13:31:58-PDT
From: PAT <HAYES@SPAR-20.ARPA>
Subject: Re: Philosophy, AI, and Complexity Theory
In reply to Ray Lister: the best overview is probably Hector Levesques
Computers and Thought lecture delivered at the last IJCAI.
Pat Hayes
------------------------------
Date: Sun, 29 Mar 87 03:15:44 cst
From: Laurence Leff <leff%smu.csnet@RELAY.CS.NET>
Subject: Computer Grading and the Law
I propose the attached comment to Mr. Craig's Volume 5 #87 submission
to ailist. In order to allow Mr. Craig an opportunity to either
ammend his statement peacefully or to rebut my criticism, I request
that Dr. Laws hold this until Mr. Craig has had an opportunity to
respond.
[He has apparently chosen not to, and Laurence has now asked
me to forward this to the list. -- KIL]
tektronix!videovax!dmc, Donald Craig, wrote in Volume 5, number 87
about his concern of student's essays being graded by machine.
He also states "In law I have the right to be judged by a jury
of my peers." drawing an analogy between a jury trial and a court case.
The first concern is unfounded and the second statement is an
overgeneralizaton.
In a criminal case involving over six months of imprisonment you have
the right to a jury trial. However, in criminal cases involving small
penalties, the states may pass laws allowing convictions without
a jury. (Source: the Criminal Procedure issue of Georgetown Law Review.)
In a suit in equity, i. e. someone wants an injunction against you or
a declaratory action, you do not have the right to a jury trial.
In administrative cases, you do not have the right to a jury trial.
(Source: "Administrative Law" by Davis, another law book)
However, there must be
"notice" and "hearing" if "life, liberty or property" is to be denied.
"Property" has been interpreted by the courts to include such things
as food stamp benefits (722 F 2d 933), driver licenses and high school
diplomas (Debra P. v. Turlington 644 F 2d 397).
After addressing the overbroad statement, we now address the substantive
concern: can computers grade essays without some human in the loop.
We find that legally, they cannot and furthermore we see the importance
of an "explanation facility", a subject that has come up recently in
AILIST.
The issue of computers making judgements came up in Foggs versus
Block, 722 F2d 933 (1983). In this case, the Commissioner
reduced people's Food Stamp allottment due to a change
in Statute. A computer program reduced the benefits and the card
so announcing gave information regarding the required hearing.
However, this notice was considered inadequate because insufficient
information was provided to determine if an error was made.
Thus any expert system making decisions impinging upon what the courts
view as "property" must provide adequate explanation and must also
provide some form of hearing procedure. Furthermore, some explanation
of the hearing procedure must be provided so that people could take
advantage of it.
Although, there would be no legal problem with a first pass determination
of the grade on a student's essay by computer program, it is clear that
some human must be available to hear a student's objections and furthermore,
that computer program must in some way indicate how the grade was determined.
In the case you mentioned, a first pass grading could be done by
computer as long as there was some procedure for complaints to be made
to a human being with an appropriate hearing.
(Due to the concepts
of ripeness, it may be necessary that the grade for the course/quarter
etc. was recorded since the error made by the computer on one essay
may not be sufficient to change the final recorded grade. However, if the
erroneous grading occurred often enough or was serious enough,
the student would eventually have a complaint that could be heard.)
------------------------------
Date: Sun, 31 May 1987 14:56 CST
From: Leff (Southern Methodist University)
<E1AR0002%SMUVM1.BITNET@wiscvm.wisc.edu>
Subject: Re: Solid Geometry
[...]
Here are some references on converting from 2-D views to constructive
solid geometry references.
The difficulty is that
simply going from three views along orthogonal axis to a 3-D
physical description
of the problem is ambiguous. That is true, even in the presence of
the "hidden line" information that would not be available from a camera.
In fact, for a given wire-frame (set of edges of the object), there are
many possible corresponding solid objects.
%A H. Yoshiura
%A Kikuo Fujimura
%A T. L. Kunii
%T Top-Down Construction of 3-D Mechanical Object Shapes from
Engineering Drawings
%J COMPUTER
%D December 1984
%P 32-40
%K AIME
%W 14D
%A M. Idesawa
%T A System to Generate a Solid Figure from Three View
%J BJSME
%V 16
%P 216-225
%N 92
%D FEB 1973
%K CADCAM
%W 05J
%A M. A. Wesley
%A G. Markowsky
%T Fleshing OUt Projections
%J IBM J. Research and Development
%V 25
%N 6
%D NOV 1981
As mentioned in AILIST, there are two main methods of modeling objects
in CAD/CAM: boundary representations and constructive solid geometry
systems. CSG based systems provide some mechanism for converting
to boundary representation as this is needed for such functions as
display. This can be done in worst case O(N ** 3) time for the two-D case
where N is the number of two dimensional objects and O(N ** 4)
for three-D. However, the average case is linear!
For an extremely clear discussion of these issues, see Tilove's
thesis which is TM-38 from the PADL group.
Going back from boundary representation to CSG is fairly straightforward.
Looking at the problems of conversion from a canonical form perspective
or cases where the object is represented parametrically is discussed in my
papers.
The argument that CSG systems cannot be put on micros is bogus.
First of all Cubicomp has been selling a commercial CSG based system
for micros for years. Second of all the original research versions of
CSG done by the PADL group was done on an 11/40 containing 28K 16 bit words
which is much more limited than an IBM-PC.
------------------------------
Date: Fri, 22 May 87 08:35:19 PDT
From: Tim Teitelbaum
<synrels%gvax.cs.cornell.edu@Forsythe.Stanford.EDU>
Subject: The Synthesizer Generator
[Forwarded from the Stanford bboard by Laws@STRIPE.SRI.COM.]
Introducing the Synthesizer Generator:
a tool for creating editors
Thomas Reps Tim Teitelbaum
Computer Science Department Computer Science Department
University of Wisconsin Cornell University
Madison, WI 53706 Ithaca, NY 14853
1. What is the Synthesizer Generator
The Synthesizer Generator is a tool for creating editing
environments for complex objects. The editor designer
prepares a specification that includes rules defining a
language's abstract syntax, context-sensitive relationships,
display format, and concrete input syntax. From this
specification, the Generator creates a full-screen editor
for manipulating objects according to these rules.
2. Who might want to use the Synthesizer Generator?
The Synthesizer Generator can be used by researchers who
need to construct an editing environment for objects that
can be described by a grammar. The Generator has been suc-
cessfully used to create a Pascal editor with full static
semantic checking, editors for C and Fortran 77, and many
editors for program verification and proof editing. It has
also been used to construct WYSIWYG editors for right-
justified text and mathematical formulae.
Using the Synthesizer Generator is much faster than
producing a hand-crafted editor, just as using a compiler
compiler is faster than writing a compiler. The Generator
maintains abstract representations for objects and incor-
porates algorithms for propagating context-sensitive infor-
mation through the objects being manipulated. It also pro-
vides the many mundane features that any editor must have,
such as binding of key sequences to generic commands, creat-
ing and manipulating buffers for edited objects, multiple
windows, etc., that would otherwise distract the editor
designer from his primary interest. The relative ease of
generating editors makes the Generator ideal for prototype
development and experimental use.
3. Are there serious applications beyond program editors?
Applications of the Synthesizer Generator are not limited to
editors for programming languages. At Cornell the Generator
is being used to implement environments for formal reasoning
that allow users to interactively construct proofs. Proofs
are represented as trees whose nodes correspond to inference
rules, while proof correctness is represented by context-
sensitive constraints between the nodes of the tree. Two
approaches to building such environments have been investi-
gated: in one the environment designer hand-tailors a Syn-
thesizer specification for a particular formal system [Reps
and Alpern]; in the other, the Synthesizer Generator is used
to implement an environment for defining formal systems that
allows a user to interactively define a particular logic and
to conduct formal reasoning in that logic.
[Reps and Alpern] Reps. T. and Alpern, B. "Interactive Proof
Checking," Eleventh POPL, 1984, 36-45.
4. How does it work?
The Synthesizer Generator is particularly well suited for
creating editors that enforce the syntax and static seman-
tics of objects that can be described in a particular
language. Each object to be edited is represented as a con-
sistently attributed derivation tree. When these objects
are modified, some of the attributes may no longer have con-
sistent values; incremental analysis is performed by updat-
ing attribute values throughout the tree in response to
modifications. If an editing operation modifies an object
in such a way that context-dependent constraints are
violated, the attributes that indicate satisfaction of con-
straints will receive new values; thus, these attributes can
be used to annotate the display in order to provide the user
with feedback about the existence of errors.
Editor specifications are written in the Synthesizer
Specification Language (SSL), which is based on the concepts
of a term algebra and an attribute grammar, although certain
features are tailored to the application domain of
language-based editors.
The Synthesizer Generator has two components:
a) a translator that takes an SSL specification as input,
and produces grammar tables as output, and
b) an editor kernel that consists of an attributed-tree
data-type and a driver for interactively manipulating
attributed trees; the kernel takes input from the key-
board and executes appropriate operations on the
current tree.
A shell program handles the details of invoking the transla-
tor and producing a language-based editor from the resulting
tables.
5. How to get a copy of the Generator
The Generator is written in C and runs under Berkeley UNIX
on VAX computers, Sun workstations (using SunWindows), and
the IBM PC/RT. Porting to other versions of UNIX is
straightforward. We are in the process of porting the Gen-
erator to XWindows. Editors generated with the Synthesizer
Generator will work on any crt terminal described in the
UNIX termcap database. A keyboard description file speci-
fies the layout of special function keys used by the gen-
erated editors. The distribution, which is available for
$200.00, consists of:
a) Source and object code for the SSL translator and edi-
tor kernel.
b) A collection of demonstration editors and their specif-
ications, including a Pascal editor with full static-
semantic checking and several proof editors.
c) A copy of The Synthesizer Generator Reference Manual.
6. References
The Synthesizer Specification Language is described in:
Reps, T. and Teitelbaum, T. The Synthesizer Genera-
tor. In Proceedings of the ACM SIGSOFT/SIGPLAN
Software Engineering Symposium on Practical Software
Development Environments, Pittsburgh, Penn., Apr.
23-25, 1984. (Appeared as joint issue: SIGPLAN No-
tices (ACM) 19, 5 (May 1984), and Soft. Eng. Notes
(ACM) 9, 3 (May 1984), 42-48).
A complete manual is available:
Reps, T. and Teitelbaum, T. The Synthesizer Genera-
tor Reference Manual. Department of Computer Sci-
ence, Cornell University, Ithaca, NY, 14853, August,
1985.
A description of the theory underlying the Generator may be
found in:
Reps, Thomas W. Generating Language-Based Environ-
ments, The MIT Press, 1984.
To request further information about acquiring a copy of the
system, please respond with the name of your organization and
your postal address to
ARPA: synrels@gvax.cs.cornell.edu
UUCP: {rochester, allegra}!cornell!synrels
Bitnet: synrels@crnlcs.Bitnet
USMail: Prof. Tim Teitelbaum
Synthesizer Generator Distribution
Dep't of Computer Science, Upson Hall
Cornell University
Ithaca, NY 14853
USA
We will send you the terms of the distribution and copies
of the distribution agreement.
------------------------------
End of AIList Digest
********************
