Subject: AIList Digest V5 #135

From: [email-masked]@vtcs1
Date: Tue, 2 Jun 87 03:26:36 edt

Date: Mon  1 Jun 1987 17:33-PDT
From: AIList Moderator Kenneth Laws <[email-masked]>
Subject: AIList Digest   V5 #135
To: [email-masked]
Reply-to: [email-masked]
US-Mail: SRI Int., 333 Ravenswood Ave., Menlo Park, CA  94025
Phone: (415) 859-6467

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 <[email-masked]>
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 [email-masked] so I can remove you
from the separate mailing list.

Brad Miller
nl-kr moderator
[email-masked]

  [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 [email-masked] 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" <[email-masked]>
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:  [email-masked]
bitnet: [email-masked]

------------------------------

Date: Mon 1 Jun 87 13:31:58-PDT
From: PAT <[email-masked]>
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 <[email-masked]>
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)
      <[email-masked]>
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
      <[email-masked]>
Subject: The Synthesizer Generator

     [Forwarded from the Stanford bboard by [email-masked].]

           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: [email-masked]
        UUCP: {rochester, allegra}!cornell!synrels
        Bitnet: [email-masked]
        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
********************