[mod.ai] AIList Digest V3 #188

AIList-REQUEST@SRI-AI.ARPA (AIList Moderator Kenneth Laws) (12/16/85)

AIList Digest            Monday, 16 Dec 1985      Volume 3 : Issue 188

Today's Topics:
  Query - Superset of Common LISP on a Chip,
  Logic Programming - LIPS,
  Policy - ADS Discussion,
  Literature - Correction: Law and Technology Bibliography,
  Logic - Factual Counterfactuals

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

Date: Fri 13 Dec 85 11:52:12-PST
From: Ali Ozer <ALI@SU-SCORE.ARPA>
Subject: Superset of Common LISP...

         [Forwarded from the Stanford bboard by Laws@SRI-AI.]


...on a chip? I just read in this month's Byte (Dec 1985, p10):

"Texas Instruments is developing a 32-bit CMOS LISP processor chip...
 Roughly 10 times more complex than a 68000, the 40-MHz processor will
 directly execute a superset of Common LISP with extensions like
 object-oriented programming and message-passing..."

This sounds truly amazing to me. A superset of what is described in
Steele's Common Lisp manual? That would be a *powerful* chip. Has anyone
read more about this? (All Byte had was the above sentence...)

Ali

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

Date: Fri, 13 Dec 85 10:36 EST
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: LIPS


For a good discussion of the  systematic benchmarking and analysis of a
Prolog implementation, see "THE PRODUCTION AND EVALUATION OF A SET OF
PROLOG BENCHMARKS" by Paul F. Wilk, Dept. of Artificial Intelligence,
University of Edinburgh. I've cliped the following from this paper:

   The program "Nrev" is seen as a standard measurement for benchmarking  Pro-
   log  implementations.   This  is  a simple symbol-crunching program for the
   naive reversal of a list (see Appendix B).  It seems  fairer  to  use  this
   program as a standard measure rather than any program involving arithmetic;
   which favours the DEC-10 compiler.  The following table shows the estimated
   Logical  Inferences  Per  Second  (LIPS) for these Prolog system configura-
   tions. Nrev performs 496 logical inferences (procedure calls) each time  it
   is  executed.  Therefore, dividing the number of logical inferences for one
   execution by the execution time, in seconds, gives the number of LIPS.

   |===============|=======|=======|=======|=======|=======|=======|=======|
   |Implementation |PrologC|PrologI|Cprolog|Cprolog|PDP-11 |POPLOG |York   |
   |---------------|-------|-------|-------|-------|-------|-------|-------|
   |System range   |DEC-10 |DEC-10 |VAX-11 |ICLPerq|PDP-11 |VAX-11 |ICLPerq|
   |---------------|-------|-------|-------|-------|-------|-------|-------|
   |Processor      |KL-10  |KL-10  |11-750 |2910   |11-60  |11-780 |2910   |
   |---------------|-------|-------|-------|-------|-------|-------|-------|
   |Translator     |Compil.|Interp.|Interp.|Interp.|Interp.|Compil.|Interp.|
   |---------------|-------|-------|-------|-------|-------|-------|-------|
   |LIPS (Nrev)    |  45592|   2385|    800|    484|    888|   1858|     56|
   |---------------|-------|-------|-------|-------|-------|-------|-------|
   |Cputime ratio  |   1   |  19.12|  56.99|  94.20|  51.34|  24.54| 814.14|
   |===============|=======|=======|=======|=======|=======|=======|=======|
           Table 3. Nrev: LIPS comparison.

The paper discusses measuring other attributes (e.g. memory utilization) and
provides a variety of benchmarks to measure particular language features
(e.g. time to assert a unit clause).

I've checked several implementations/machines here.  For CProlog, I
recall measures like 2400 LIPS for a 785, 400 LIPS for a HP9836, and
140 LIPS for a MacIntosh.  Our Symbolics-prolog (compiled) tested out
at about 40K LIPS.Here is the program I've used to do the benchmarking.
I think it comes from Paul Wilk.

     % lips runs the nrev benchmark 10 times and writes the estimated lips.
     lips :- lips(10,L), nl,write(L),write(' lips').

     % Lips(N,L) runs the nrev benchmark N times and binds L to
     % an estimate of the LIPS.
     lips(N,L) :-
        init(X),
        T1 is cputime,
        tests(N,X),
        T2 is cputime,
        control(N,X),
        T3 is cputime,
        Testtime is T2-T1,
        Overhead is T3-T2,
        Nettime is Testtime-Overhead,
        write('     '),
        write(Testtime-Overhead=Nettime),
        nl,
        L is (496*N)/Nettime.

     tests(N,X) :- from(1,N,I), test(X), fail.
     tests(N,X).

     control(N,X) :- from(1,N,I), dummy(X), fail.
     control(N,X).

     from(I,I,I) :- !.
     from(L,N,I) :- N1 is (L+N)//2, from(L,N1,I).
     from(L,N,I) :- L1 is (L+N)//2+1, from(L1,N,I).

     %NREV: Naive Reverse of 30 element list

     init([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
     21,22,23,24,25,26,27,28,29,30]).

     dummy(L).

     test(L0) :- nreverse(L0,L1).

     nreverse([X|L0],L) :- nreverse(L0,L1), concatenate(L1,[X],L).
     nreverse([],[]).

     concatenate([X|L1],L2,[X|L3]) :- concatenate(L1,L2,L3).
     concatenate([],L,L).

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

Date: Fri 13 Dec 85 17:29:27-PST
From: LOUROBINSON@SRI-AI.ARPA
Subject: For AIList

Ken:

(For AIList:)

In response to AI.Duffy at UTexas and his message regarding the
AI&DS name change:

Why the cheap shot?  It's obvious why the name change was necessary.
Why exploit them for the sake of Duffy's unsigned, heavy-handed
cleverness?

Lou Robinson

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

Date: Sun, 15 Dec 1985 13:23 PLT
From: George Cross  <FACCROSS%WSUVM1.BITNET@WISCVM.WISC.EDU>
Subject: Correction: Law and Technology Bibliography


In my posting of the table of contents of the Proceedings of the First
Annual Law and Technology Conference (Ailist V3 #117, 12/13/85), I left
out Anne Gardner's paper and mispaged Zarri's:

%T Overview of an Artificial Intelligence Approach to Legal Reasoning
%A Anne v.d.L. Gardner
%B Computing Power and Legal Reasoning
%E Charles Walter
%I West Publishing Company
%P 247-274
%D 1985
%C St. Paul
%X ISBN 0-314-95570-4

%T Inference Techniques for Intelligent Information Retrieval
%A Gian Piero Zarri
%B Computing Power and Legal Reasoning
%E Charles Walter
%I West Publishing Company
%P 215-246
%D 1985
%C St. Paul
%X ISBN 0-314-95570-4

---- George

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
George R. Cross                                cross@wsu.CSNET
Computer Science Department         cross%wsu@csnet-relay.ARPA
Washington State University             faccross@wsuvm1.BITNET
Pullman, WA 99164-1210                     (509)-335-6319/6636
Acknowledge-To: George Cross <FACCROSS@WSUVM1>

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

Date: 13 Dec 85  1143 PST
From: Matthew Ginsberg <SJG@SU-AI.ARPA>
Subject: interesting counterfactual


> From: Mike Dante <DANTE@EDWARDS-2060.ARPA>
> . . .
> (0) Suppose a class consists of three people, a 6 ft boy (Tom), a 5 ft girl
>     (Jane), and a 4 ft boy (John).  Do you believe the following statements?
>
>         (1) If the tallest person in the class is a boy, then if the tallest
>             is not Tom, then the tallest will be John.
>         (2) A boy is the tallest person in the class.
>         (3) If the tallest person in the class is not Tom then the tallest
>             person in the class will be John.
>
>        How many readers believe (1) and (2) imply the truth of (3)?

It seems to me that this example gives insight as to what the status
is of a counterfactual whose premise is true.  The general view among
philosophers on this is that the truth or falsity of a counterfactual
with a true premise depends simply on the truth or falsity of its conclusion,
but this example seems to run against this view.

The reason seems to me to be that the conclusion should be investigated
as if the premise had read, "If the tallest person in the class is
*necessarily* a boy."  In other words, in constructing possible worlds
in which "the tallest is not Tom" (i.e., in investigating the truth of the
conclusion of (1)), possible worlds in which the tallest is not a boy are
disallowed.  Thus (1) and (2) can be true while (3) is false.

I don't know what to make of this generally.  It appears that the problem
can only arise with enbedded counterfactuals; perhaps it is reasonable
to treat them specially, rewriting (1) as:

If the tallest person in the class is a boy and the tallest is not Tom,
then the tallest will be John.

The two approaches are equivalent, but I fear there may be substantial
ramifications to messing around with the semantics in this fashion.

                                                Matt Ginsberg

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

End of AIList Digest
********************