🚀 go-pugleaf

In article <1990Sep3.0...@cbnewsh.att.com> w...@cbnewsh.att.com (Bill Stewart 201-949-0705 erebus.att.com!wcs) writes:
>Does anyone know if HAKMEM is available on-line?
Not a chance.  An attempt was made about 10-12 years ago to create an
online version but it got abandoned.

>(unfortunately) a lot of what purported to be
>interesting algorithms written in highly legible PDP-10 assembler.

Yes, indeed, the assembler was highly legible.  It was, without a
doubt, the easiest assembly language to read and understand; a true
delight to program in.  This was one of the reasons migration from the
PDP-10 was so painful; there was *much* more programmed in assembly
language for that machine than for just about any other platform.

Now, what the algorithms *did* was rather obscure, and no programming
language could clarify it further.  At least the assembly language was
precise and unambiguous, unlike certain programming languages.

>ARRRGH - as with Knuth, why can't people use ALGOL instead of
>preferring low-level languages?

Such as which bogus dialect of ALGOL was in vogue at the time?  I can
show you lots of "ALGOL" which is totally unintelligible today, as it
depends upon long-forgotten side-effects or even (shudder!) obsolete
evaluation-order rules...

If written in anything other than PDP-10 assembly language, it would
have been in Lisp.  HAKMEM was an internal document for the MIT AI
Lab.  At the time, they used two programming languages; assembly (for
the systems hackers) and Lisp (for the AI work).

>Admittedly, some of the algorithms
>were really concerned with "how to make a 36-bit machine do
>something useful?"

36-bit machines did quite a bit useful without obscure algorithms.
True, most of the assembly algorithms had to do with exploiting subtle
mathematical relations with surprising results, or would be irrelevant
on other architectures, but in almost all cases the bizarre hack was
more of an intellectual exercise rather than anything useful.

For example, on the PDP-10 a common vector pointer had a negative
length count in the left 18-bit halfword and a positive index in the
right halfword (indexing only used the right halfword in the
traditional address space); this was incremented, tested, and iterated
by the AOBJN (Add One to Both halfwords and Jump if Negative)
instruction.  One HAKMEM hack to load an AOBJN pointer was:

	HRLOI AC,-1(COUNT)	; Halfword Right to Left Immediate, fill Ones
	EQVI AC,ADDR		; EQuiValence Immediate

where AC is a register to receive the pointer, COUNT is a register
containing the positive size of the vector, and ADDR is a constant
address of the origin of the vector.

The calculation of the indexed immediate value results in 9 (I'm
keeping this decimal).  The "right half" of an immediate value is that
value; this goes into the left half of AC.  Ones go into the right
half of AC (the "O" of "HRLOI"), resulting in 9,,-1.  The EQV is a
logical equivalence test, returning bitwise 1's for equivality and 0's
for inequality.  The left half of an immediate value is always zero,
so the equivalence complements the 9.  On a twos complement machine,
the complement of 9 is -10; this goes into the left half.  Since the
right half of AC is -1, equivalence is an identity operation; so the
immediate value goes into the left half.  Result: -10,,ADDR.

This can, of course, be done in a much more straightforward manner
with the series:
	MOVN AC,COUNT		; MOVe Negative
	HRL AC,AC		; Halfword Right to Left
	HRRI AC,ADDR		; Halfword Right to Right Immediate
but of course this lacks the wonderful obscurity (and is one machine
instruction longer!) of the HAKMEM example.  A single machine
instruction was rarely important, even in the (by today's standards)
limited address space on a PDP-10.

Thus is the way of all good hacks.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ M...@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.