Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 8/7/84; site ucbvax.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!zehntel!dual!ucbvax!wildbill
From: wildbill@ucbvax.ARPA (William J. Laubenheimer)
Newsgroups: net.lang
Subject: Re: levelheight
Message-ID: <4295@ucbvax.ARPA>
Date: Mon, 21-Jan-85 19:37:51 EST
Article-I.D.: ucbvax.4295
Posted: Mon Jan 21 19:37:51 1985
Date-Received: Wed, 23-Jan-85 04:56:24 EST
References: <2673@dartvax.UUCP> <4890@utzoo.UUCP> <247@gumby.UUCP> <369@hercules.UUCP> <463@kcl-cs.UUCP>
Reply-To: wildbill@ucbvax.UUCP (William J. Laubenheimer)
Organization: University of California at Berkeley
Lines: 54

It seems that a lot of the proposed definitions for determining how "high-level"
a language is are focusing on things like "how many keystrokes do I need to
do thus-and-so". Not only does this lead to the silliness about "APL only
needs epsilon keystrokes to do this operation while C needs omega", but it
doesn't take into account languages which don't use keystrokes at all. How
would you apply this metric to a "language" which you might find on a Mac,
where you define variables by pointing to an area on the screen, which then
becomes a "bin" from which you can get a value or leave one for later; a
"function" is some sort of machine icon with connectors which you can
attach to bins (parameters) or other machines (expressions) or whatevers,
and a procedure or control structure looks like an assembly line, which
you can reduce to a building icon with the same kind of connectors as
the appropriate machine icons? How many characters is a mouse-click worth?
What's the value of wheeling the mouse around the display area? Is pointing
to a building-icon worth the same as pointing to a machine-icon?

These definitions seem to be pointing at an information-theoretic measurement
of the level of a language. Although I haven't studied information theory
to more than a passing familiarity with some of the concepts, these squabbles
seem to be precisely why the discipline was put together in the first place.
So let's condense all the stuff which tries to figure out how bulky the
source code is down to the following:

INFORMATION-THEORETIC MEASURE OF LANGUAGE COMPLEXITY: Language "X" is
"higher-level" than language "Y" iff, given any problem, there exists
a coding of a solution to the problem in "X" which, \\when represented as the
sequence of symbols in "X" implementing that solution//, requires fewer
bits than a coding of any solution to the problem in "Y" when represented
as the sequence of symbols in "Y" implementing that solution.

I have tried to construct a definition that will allow such tricks as
representing a keyword as a single token and an identifier as "just a name"
regardless of length, while still allowing for the fact that if a large
number of keywords are present, there is more information contained in
each keyword, and if many identifiers are declared, more information is
necessary to distinguish between them. This also allows other neat things
like the hieroglyphic language I briefly described above, or using various
compression techniques on the output. However, I hope I have prohibited
little tricks like the famous "smallest integer not sayable in fewer than
twenty syllables" paradox (translated to this environment, it comes out
as defining "matrix inversion" and all the terms relevant thereto, specifying
that you are interested in the shortest program written in that language
which solves "matrix inversion", and encoding that into some representation
which might require fewer bits than the solution to the problem).

Stated in less precise terms, what I have tried to construct is a metric
which will compare information content of the source representations of
the best solution in the two languages under discussion. This would
seem to be what all the "count-the-source-bits" people want. Am I a
"count-the-source-bits" person myself? I don't think so...

                                        Bill Laubenheimer
----------------------------------------UC-Berkeley Computer Science
     ...Killjoy went that-a-way--->     ucbvax!wildbill