Subject: Re: "untyped" (was: What's gone wrong with Scheme Macros? Why all the debate?)
From: rpw3@rpw3.org (Rob Warnock)
Date: Sun, 08 Sep 2002 00:14:54 -0000
Newsgroups: comp.lang.scheme
Message-ID: <unl5jum4i6ej6d@corp.supernews.com>
Jeffrey Siegal  <jbs@quiotix.com> wrote:
+---------------
| Brian Harvey wrote:
| > rpw3@rpw3.org (Rob Warnock) writes:
| >>(*Ahem!*) Scheme is *strongly*-typed, not untyped.
| >>Perhaps you meant to say "dynamically-typed"?
| > 
| > Is there such a thing as an untyped language?
| 
| Machine code/assembler.  I vaguely recall that BCPL (or was it BLISS or 
| something else from that era -- I'm not sure?) was untyped as well, and 
| possibly others.
+---------------

Data in BLISS[1], for sure, was completely untyped. Not certain
about BCPL, but I think there, too.

The BLISS data model was identical to that of assembler: All data
was fixed-width "words" whose width varied according to the target
architecture (DEC PDP-10, PDP-11, and VAX, maybe some others[2]).
The "value" of user identifiers (*and* numeric literals!!) in *all*
contexts was the *address* of some location, that is, what C calls
an "L-value". To get the *contents* (R-value) of a location, you
applied the "contents of" operator (a dot) to an address. That is,
to increment "foo" you said "foo := .foo + 1".[3] If you said
"foo := foo + 1" (no dot), you stored into "foo" a pointer to the
word following "foo" (roughly "foo = &foo[1]" in C). And, yes,
"37 := .(37) + 1" would increment memory location 37.

Or to say it another way, data wasn't typed; *operators* were!

	foo := .foo + 1
	foo := .foo fadr 1.0
	foo := .bar fdivr (.gorp fsubr 5.0)

The "+" operator was native full-word integer addition (whatever
that was on the target machine, usually 2's-complement), "fadr" was
"Floating-point ADd and Round" (same name as the PDP-10 assembler op),
"fdivr" was floating divide & round, etc. (The PDP-10 had non-rounding
versions, too, for implementing extended-precision ops.) Perverse
example:

	begin
	foo := 37.63;
	foo := .foo + 1.0
	end

Yes, it took the binary bit pattern that is the machine encoding
of the floating-point number "37.63", and used *integer* addition
to add the machine encoding of the floating-point number "1.0",
storing whatever the resulting bit pattern is into "foo".

Actually, identifiers were not just addresses; they also encoded
sub-word field information -- what the PDP-10 called "byte pointerss",
which could specify any bit alignment within a word and any width from
zero bits to the machine word size[4]. That is, this piece of BLISS:

	foo<3,7> := .bar<21,7> + 1

written in C would be:

	foo = (foo & ~0x3f8) | ((((bar >> 21) & 0x7f) + 1) << 3);

Or in Common Lisp:

	(setq foo (dpb (1+ (ldb (byte 7 21) bar))
		       (byte 7 3)
		       foo))

But in BLISS-10 at least, these "byte pointers" were first-class values.
You could pass them around or return them as values, e.g., the following
would do the same thing as the above:

	begin
	fp := foo<3,7>;
	bp := bar<21,7>;
	.fp := ..bp + 1
	end

[Aside: A user identifier without a byte specifier was taken as
having an implicit specifier of the full word, that is, when you
wrote "foo" by itself the compiler assumed you meant "foo<0,36>"
(for the PDP-10).]

Common Lisp reifies the byte-specifier part of PDP-10 byte pointers
(that is, the result of (byte 7 3) is a first-class object), but to
get the full effect of a PDP-10 byte pointer you have to pass around
both a byte-spec and some kind of locative. So if you want to pass
around "pointers" to inspectable/mutable fields, it's probably easier
just to pass a closure instead, which is probably how you'd want to
do it in Scheme anyway.


-Rob

[1] BLISS = Basic Language for the Implementation of System Software
    (see <URL:http://www.foldoc.org/foldoc/foldoc.cgi?BLISS>) was
    designed to be efficient enough to write operating systems and
    utilities in, yet high-level enough -- particularly its macros
    and structure definitions -- to increase productivity & reliability
    over assembler, which was, in those days, what operating systems
    were still almost all written in (except the Burroughs B5500, which
    used BALGOL; and Unix, which was still an internal Bell Labs project).

[2] CMU & DEC only did the PDP-10, -11, & VAX versions, but at DCA
    (not the .mil one) we invented a dialect we called "BLISS-8"
    (would have been named "BLISS-12" by the later BLISS-16/32/36
    naming scheme) for the PDP-8. However, the "compiler" in this
    case was a person. (But that's another story...)

[3] For clarity, I took the liberty of using the ":=" sequence for
    assignment here. BLISS actually used the ASCII code which printed
    as left-arrow on the {ASR,KSR}-{33,35,37} Teletypes, but the ASCII
    standard later changed that code to underscore, which caused BLISS
    code to look very weird on CRT displays, especially if optional
    spaces were omitted, e.g., "foo_.foo+1".

[4] Which is why we old-fart PDP-10 users get so rankled when people
    claim "a byte has always 8 bits, period". T'aint so, young'uns.

-----
Rob Warnock, PP-ASEL-IA		<rpw3@rpw3.org>
627 26th Avenue			<URL:http://www.rpw3.org/>
San Mateo, CA 94403		(650)572-2607