Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 089
AIList Digest Friday, 13 Jul 1984 Volume 2 : Issue 89
Today's Topics:
AI Languages - Syntax Semantics,
Seminars - Expressiveness of Languages
& Machine Translation
& Statistical Computing Environments
& Properties and Predication
----------------------------------------------------------------------
Date: Monday, 2-Jul-84 20:26:24-BST
From: O'Keefe HPS (on ERCC DEC-10)
Subject: Syntax Semantics
[Forwarded from the Prolog Digest by Laws@SRI-AI.
This is part of an ongoing discussion of a proposed
Prolog transport syntax.]
I agree that S-expressions are elegant, general, and so on.
{So for that matter are Goedel numbers.} But there is good
reason to believe that they are not well suited to human
reading and writing. That is that ***LISP*** doesn't use
S-expressions for everything. Consider
[A<-(FOR NODE IN NODELIST COLLECT CAR EVAL (NODE:NODEFORM]
which is perfectly good InterLisp. I might be persuaded
that this is readable, though not after the uglyprinter has
had its way with it, but it quite certainly is NOT an S-expression.
Now there is an isolationist section of the Lisp community which
ignores Interlisp (the Common Lisp designers did not, well done).
But as soon as you use ANY sort of read macro, you have left
S-expressions behind. `(cons ,(cadr form) ,(caddr form)) is not
an S-expression. And of course the MacLisp family has (loop ...).
As for the question about whether there are natural binary operations
which are not associative, mathematics is FULL of them. Any function
whose result type differs from its right argument type. Quite a lot
are relations, such as "=", "<", and so on. Note that the extension
of the relational operations to multiple arguments in some Lisps
loses you a lot of nice properties: (>= A B C) is not the same as
(NOT (< A B C)). Depending on implementation subtleties it might not
even be the same as (<= C B A). And the extension STILL doesn't let
you write 0 <= X < Y, you have to write -1 < X < Y which is often more
obscure than an explicit conjunction would have been. The principal
example of a non-associative binary operator is exponentiation.
As an instance of exponentiation, let's take the free monoid over
the ASCII characters, where "abc"^4 = "abcabcabcabc". Any
generalisation of this to take an arbitrary number of arguments will
not treat all the arguments equally. One natural extension to
multiple arguments would be to take an alternating list of strings
and integers (^ S1 N1 ... Sk Nk) = (concat (^ S1 N1) ... (^ Sk Nk))
with omitted integers taken to be 1. But this doesn't place all the
arguments on an equal footing (what should (^ "abc" 2 3) mean?) and
doesn't really generalise to other operators. There is even a
problem with operators which have coincident argument and result
types. For example, why should (CONS x y z) means (CONS x (CONS y z))
rather than (CONS (CONS x y) z)?
I'm afraid the Sigma notation is not an example of mathematicians
retreating in response to an indaequacy in infix notation. When
writing *informally*, mathematicians are as pleased as anyone else
to write a1 + ... + an. Sigma notation specifies three things:
a commutative associative binary operation (if the domain can be
empty the operation must have an identity), a domain, and a
FUNCTION. E.g. in
/\
/ \ f(i) = g(i)^2
i=1..n
the operation is "and", the domain is {1,2,...,n}, and the
function is lambda i. f(i) = g(i)^2. I fully agree that this is a
good thing to have, but it is NOT a thing you can get by allowing
the argument list of everything in sight to have an arbitrary number
of arguments. The number of arguments is still fixed at each CALL.
When the number of operands is unknown, the Lisper still has to write
(apply #'and (mapcar #'(lambda (i)
(eql (f i) (expt (g i) 2))) (num-list 1 n)))
and then finds that he can't, because "and" is a special form and
you can't apply special forms. Quite a few Lisps macro-expand
(plus a b c d) to (plus2 (plus2 (plus2 a b) c) d), and you can have
fun applying #'plus ! What you find yourself having to do all too
often is
(eval (cons #'and (mapcar #'(lambda (i)
(kwote (eql (f i) (expt (g i) 2)) )) (num-list 1 n)) ))
Now there IS a lisp-like language which has faced up to this problem
of some functions sensibly taking an arbitrary number of arguments.
It's called 3-Lisp. Yes, I mean the thing described in Brian Smith's
thesis. It has been implemented and runs quite nicely on Xerox 1108s.
3-lisp distinguishes between PAIRs, written (car . cdr) and SEQUENCES,
written [a1 ... an]. I shan't tell you about the distinction between
sequences and rails. There *is* a notational convention that if you
write (car a1 ... an) {note: no dot after the car} it means
(car . [a1 ... an]). So (+ a b c) means (+ [a b c]). The thing is
that if you employ the language's reflective capabilities to poke
around in the guts of your program while it's running, you'll find
that the rail or sequence really is there. The cdr of a pair can be
any form (as can the car), so if I want to write
(+ . (map f L))
I can.
Given that Prolog is based on relations rather than functions,
you don't find anywhere NEAR as much nesting as you do in a
language based on functions, so the operator priority issue doesn't
really arise, except when the data you are working on are expressions
in some language. MACSYMA, for example, exploits the CGOL parser
to handle its input. Prolog happens to use the analogous thing all
the time.
Prolog lets you use operators when you want to. You don't have
to use any operators at all if you don't want to:
:-(max_min(X,Y,X,Y), >=(X,Y)).
:-(max_min(X,Y,Y,X), <(Y,X)).
is quite acceptable to the Prolog parser, though not to me.
Similarly, Lisp lets you use operators if you want to (in InterLisp
it happens automagically with CLISP, use the CLISPTYPE, UNARYOP, and
LISPFN properties; in PSL you can use RLISP; in MacLisp there is
CGOL), but normally only uses a handful of strange syntactic forms.
Prolog and Lisp are similar internally as well. Modulo all the
exotic data structures like records and hash tables present in all
modern Lisps, which structures have no S-expression representation
{Common Lisp does let you use #(struct-name field-1 "val1" ...)
for defstructs, but there is nothing for hash tables or most forms
of array}, most Lisp data can be viewed as
atomic
or (CONS something something-else)
and functions to hack such structures are indeed easily written.
If you want to write programs that analyse programs, you rapidly
find yourself in very deep water sinking fast. It is a MAJOR
contribution of Common Lisp that they have spelled out exactly
what special forms a program-hacking tools must understand (there
are about 20 of them) and that they have specified ways of telling
whether a form is a macro call and of getting at the macro expansion
without too much pain. The hair in the MASTERSCOPE interface for
coping with InterLisp's "no specifications please, we're power-
assisted programmers!" view is amazing.
Prolog code that wants to hack arbitrary data structures can
similarly view the world as divided into two sorts of objects:
variables
and other terms
Other terms have a function symbol and 0 or more arguments.
For example, 77 is a non-variable whose function symbol is 77
and which has 0 arguments. This is admittedly a wee bit more
complex than basic Lisp, as cons cells are known to have exactly
two components. But I have faithfully described real Prolog;
there is nothing else that a Prolog program can get its hands
on and look inside. A Lisp |print| routine really does have
to worry about what to do with records (defstructs) and arrays
and compiled-code pointers and ...
The list of Prolog "special forms" is embarrassingly large:
?- /1 :- /1 :- /2 , /2
; /2 \+ /1 setof/3 bagof/3 call/1
once/1 forall/2 % some Prologs lack these two
But that's still a LOT less than Common Lisp has.
To summarise:
yes, S-expressions are general, clean, and hackable.
BUT, so are terms.
BUT, there is a LOT more to Lisp syntax and internal
structure both than S-expressions.
Ken Kahn is absolutely right that it is important to have an
internal structure which you can easily build tools for. He
is right that S-expressions are such an internal structure.
(Just don't assert any clauses mentioning arrays...) It is
also true that "Core Prolog" data structures are themselves
convenient to work with. (Some of the toy Prologs that you
can buy for peanuts get basic things like functor/3 wrong so
that it isn't true. But there are several toy implementations
of Lisp which represent a list as a string, so that
DEFINE('CAR(X)')
CAR.PAT = "(" BAL . CAR "." :ON
CAR X CAR.PAT :S(RETURN)F(FRETURN)
Does that mean Lisp data structures are bad?)
Look, we're NEVER going to agree about syntax. I've indulged myself
somewhat in this message, but I have been defending a kind of
syntax (infix operators) and to some extent even a choice of syntax,
rather than any specific form. [...]
[O'Keefe went on to discuss his previously-presented proposal for
a Prolog transport syntax. -- KIL]
------------------------------
Date: Thu 12 Jul 84 07:45:12-PDT
From: Dikran Karagueuzian <DIKRAN@SU-CSLI.ARPA>
Subject: Seminar - Expressiveness of Languages
[Forwarded from the CSLI Newsletter by Laws@SRI-AI.]
EXPRESSIVENESS OF LANGUAGES
Jock Mackinlay, Stanford, will give a talk on ``Expressiveness of Language''
on Friday, July 13, at noon in Braun Lecture Hall, Seeley Mudd Chemistry
Bldg., as part of SIGLunch series. The talk is expected to last no more than
45 minutes.
ABSTRACT: A key step in the design of user interface is
the choice of a language for presenting facts to the user.
The spectrum of possible choices ranges from general
languages, such as predicate calculus, to more specialized
languages, such as maps, diagrams, and ad hoc languages.
General languages can express a broader range of facts than
more specialized languages, but specialized languages are
more parsimonious. The basic motivation for the research
described in this talk is to construct a presentation
system that can automatically choose an appropriate graphic
language for presenting information to a user.
This talk addresses two issues that must be considered when
choosing a language to represent or present a set of facts.
First, a language must be sufficiently expressive to state
all the facts. Secondly, it may have the property that
when some collections of facts are stated explicitly,
additional facts are stated implicitly. Such a language
should not be chosen if these additional facts are not
correct. We first define when a fact is stated in a
message. Using this definition, we define when a set of
facts is expressible in a language. This definition can
be used to determine whether a language should be chosen
to represent or present a set of facts. We also consider
the problem of choosing between languages that are
sufficiently expressible for a set of facts. Two criteria
are considered: the cost of constructing a message and the
cost of interpreting a message.
------------------------------
Date: Thu 12 Jul 84 07:45:12-PDT
From: Dikran Karagueuzian <DIKRAN@SU-CSLI.ARPA>
Subject: Seminar - Machine Translation
[Forwarded from the CSLI Newsletter by Laws@SRI-AI.]
For the Record
MACHINE TRANSLATION AND SOFTWARE TOOLS
On Tuesday, July 10 Mike Rosner of ISSCO Geneva and Rod Johnson of the
University of Manchester gave a talk at SRI on their work on software
environment for the Eurotra machine translation project, a coordinated
international effort for the research and development of a multilingual
machine translation system.
ABSTRACT: A software environment which supports large-scale research
in machine translation must provide the facility for rapid implementation
and evaluation of a variety of experimental linguistic theories and/or
notations, including novel ones developed specifically for the task. We
have based our approach to the design of a suitable architecture upon the
principle of executable specifications, an important aspect of which is an
attempt to decouple the syntax of a given notation from the semantics. An
appropriate choice of definition languages is essential for the success of
such a venture, and in the talk we will present the current state of the
work and discuss some of the open issues.
------------------------------
Date: Thu 12 Jul 84 07:45:12-PDT
From: Dikran Karagueuzian <DIKRAN@SU-CSLI.ARPA>
Subject: Seminar - Statistical Computing Environments
[Forwarded from the CSLI Newsletter by Laws@SRI-AI.]
Computing Environments Seminar
FEATURES OF EXPERIMENTAL PROGRAMMING ENVIRONMENTS
Part 1
By John Alan McDonald (Stanford) at 11:00am Thursday, July 12, in Sequoia 114.
ABSTRACT: Interactive data analysis can be usefully thought
of as a particular kind of experimental programming. Our
work should build on the 10-15 years of research in
environments for experimental programming associated with
places like Xerox PARC and the MIT AI Lab. In this
session, we will discuss, in general terms, properties of
experimental programming environments that are relevant
to interactive data analysis. We will also describe and
compare the two basic alternatives in programming
environments that are open to us:
o Conventional operating systems (eg. Unix).
o Integrated programming environments
(eg. Lisp Machine Environment).
The conclusion will be that integrated programming
environments are far superior to conventional operating
systems for both the practice of data analysis and for
research in data analysis.
JULY-AUGUST SCHEDULE FOR COMPUTING ENVIRONMENTS SEMINAR SERIES
Tue., July 17: Flavors: Object-oriented Programming on the Symbolics
Lisp Machine. (Richard Dukes, Symbolics)
Thu., July 19: Features of Experimental Programming Environments, Part 2.
(John McDonald, Stanford)
Tue., July 24: Object-oriented Debugging Tools for S.
(Alan Wilks, AT\&T Bell Labs)
Thu., July 26: Data Analysis with Rule-based Languages and Expert Systems
(Steve Peters, MIT)
Tue., July 31: Current Research with S.
(Rick Becker, AT&T Bell Labs)
Thu., Aug. 2: Design Decisions in Object-oriented Programming.
(John McDonald, Stanford)
Tue., Aug. 7: Integrating Graphics into a Data Analysis Environment.
(Mathis Thoma, Harvard)
------------------------------
Date: Thu 12 Jul 84 07:45:12-PDT
From: Dikran Karagueuzian <DIKRAN@SU-CSLI.ARPA>
Subject: Seminar - Properties and Predication
[Forwarded from the CSLI Newsletter by Laws@SRI-AI.]
P R O P E R T I E S A N D P R E D I C A T I O N
By Gennaro Chierchia and Ray Turner, next Thursday's (July 19) CSLI Seminar
will take place at 2 p.m. in the Ventura Conference Room.
ABSTRACT: One of the most interesting recent developments
in logic is perhaps the formulation of theories of
properties where logically equivalent properties do not
have to be identical and properties in some sense can
be applied to themselves. We will consider two such
theories and argue for one which is inspired by Frege's
views . In particular, we will argue that such a theory
solves a number of outstanding problems in natural language
semantics. We shall consider some general consequences
of adopting such a property theoretic approach to formal
semantics. The presentation will be in two halves. The
first will provide some linguistic and semantic motivation
for the theory. The second will contain a formal
development.
------------------------------
End of AIList Digest
********************
