> I wonder if the Symbolics microcode was horizontal? If they used
> vertical microcode while the Dorado was horizontal, maybe that might
> explain the difference between their perception of Moore's Law and
> Alan Kay's --- Kay consistently complains that modern CPU
> architectures run Smalltalk and other late-bound things slowly, which
> is sort of the opposite of the apocryphal Symbolics comment I cited
> earlier.
I don't know Kay's argument well enough to address it directly, but I
believe a modern CPU architect would say the critical factor is to run
fast stuff fast, so early-bound things go as quickly as possible, and
late-bound things wind up going as slowly as necessary -- if the only way
to make late-bound things appear to run in the same number of clocks as
early-bound is to slow down the machine, that's a tradeoff they've thus
far been unlikely to make.
(this implies there ought to be a hierarchy of binding: late-binding for
code whose data lives on the net or on disk, early-binding for code whose
data lives in L1 or in registers, and a suitable mix for everything in
between)
But I don't think this is the opposite of the Symbolics comment:
> I have a vague memory that some of the Symbolics folks said that when
> they reimplemented their 36-bit CPU as an Alpha AXP program
> ("OpenGenera"), it fit in the L1 cache of the Alpha, and it ran Lisp
> programs about as fast as you'd expect microcode to run on a machine
> with that kind of clock speed.
The two closest references I was able to track down were:
http://www.unlambda.com/lispm/memo528.html
http://pt.withy.org/publications/VLM.html
My understanding is the first, AI Memo 528, was roughly the architecture
for all the lisp machines with the possible exception of LMI's K-machine.
(After reading Stallman's inspiration for GNU in the demise of the AI lab,
I have to wonder to what extent the "AI winter" came about because lisp
machines were sold largely to projects flush with Star Wars money?
Afterwards, with no raygun, they appeared more exotic than practical -- I
am personally glad to have picked the web over Lucid in the mid-90's.
This hypothesis implies there should now be an "AI spring" with the modern
DOD, which, at least in robotics and speech tagging (consider automated
wiretaps), seems to be true)
The second was an abstract for a paper that was never written. They
appear to have coded in a style similar to microcode, making use of
multiple dispatch, paying attention to cache conflicts, and requiring 64
bit data paths. Given that simulating hardware is an early-bound problem
(and that they had a wider and faster machine than the one being
emulated), it doesn't sound surprising they got decent performance from a
modern architecture.
Squint at emulation just right, and it looks like programming in general.
One has an abstract problem, for which one wants to compute an abstract
solution:
A ---> A'
which (if one is not EWD, who saw no need to suffer from the diseases
which he studied :-) tends to involve using a concrete machine to
calculate a concrete solution:
C ---> C'
then coding the abstract into the concrete (A->C), and decoding the result
(C->A)
A ...> A'
| ^
v |
C ---> C'
That is, we want to emulate the abstract computation with our concrete
calculation.
I think I now understand why Dijkstra was interested in adjunctions: when
F:A->C and G:C->A form an adjunction, then GF is a nice endofunctor, and
GFGF => G(FG)F => GF reduces to another nice endofunctor, (and GFGFGF is
indeed associative) so when we string a bunch of these together we get a
monad.
> Maybe [debugging] accounts, in part, for the great interest in static
> correctness proofs in the functional programming community? OCaml has
> a reportedly very nice debugger that works only with its bytecode, not
> with its native code, and they simply try very hard to ensure that
> they have the same behavior so you never have to debug the native
> code. Having a static type system that permits type erasure without
> loss of safety helps with this.
Yes, exactly. The way to debug easily is to behave exactly as above, and
map between the concrete and abstract at each step (GF...GF). An
interpreter does this "for free", that is, ignoring execution time. The
way to run quickly is to erase the intermediate (normally identity)
C->A->C steps, and run the problem strictly in the concrete domain
(Gccc...ccccF). Compilers do this "for free", but then if we want to look
at "the middle of" the computation, we must then have a debugger to
reconstruct the equivalent A' from any given C' (and possibly synthesize a
new C'', should we alter A' to A'').
Horowitz and Hill point out that similar games are played in hardware with
sequential PLDs -- if one has the gates, it's easier to make a strictly
synchronous design which keeps its (abstract) outputs in the registers.
If one doesn't have the gates, it's more efficient to make a design which
keeps the bare minimum of (concrete) state in the registers.
-Dave
:: :: ::
> It's too bad gdb hasn't acquired a decent scripting language, all
> these years after the Plan9 paper (was it "Acid: a debugger built from
> a language"?)
Sounds like the right paper. I wonder to what extent Forthers,
Smalltalkers, and Lispers use the multilevel nature of their languages to
script debugging?
> If I remember correctly, bass started out using ColorForth as a basis?
> I'm afraid it's been a number of years since I looked at it. Is there
> a place to see it these days?
It was on a laptop that didn't survive the move, so now it's on a bare
2.5" disk and a few backup CDs packed somewhere in the "cave". (a
basement area that supposedly contains supplies in case of nuke attack,
but in the case of swiss tends to be used for wine, prosecco, and skis;
and in the case of at least some americans is stuffed full of things
which, had we had half a mind when moving, would never have been shipped
across the atlantic in the first place. What's the news on you two? Is
it BA?)
I should dig it out sometime and GPL it, but it never progressed much
beyond what you've seen. The register allocation wasn't for general use,
but was to allow full bandwidth when doing sequences of loads and stores
-- somewhat like how the concatenative people are experimenting with
interspersing linear code with stack-shuffling. I was happy fairly with
the code, but never came up with an equivalently structured approach to
data literals. (or rather, never came up with an approach that didn't
seem to eventually lead to a traditional language) I was interested in
YAML for this purpose before it grew; now it'd be tempting to just put in
something JSON-like (which would require changing the code syntax to
preserve duality) and call it done.
The fellow who provides my alpine elevation data uses a homebrew language
(which he actually ported from moto to intel at some point) that wound up
in a similar place, but as his interests are array processing and
raytracing, he's never bothered implementing much in the way of data types
either.
Someday, I'd like to look at the initialization stuff in Virgil to see if
it'd solve one of the big problems: literals, like code, live in readonly
("text") and are expressed abstractly; we'd like for the intermediate
variable values which live in data to be expressed concretely. I had a
decorator kludge in bass for literals that was a half-assed approach,
something more elegant would not only handle specializing data
representations but would also be able to specialize code fragments so the
same source might have several machine-code translations to run in
different monads -- and at this point the problem is to avoid simply
reinventing macros.
The effort to stay 1-1 (and to prioritize sequences over graphs) may just
be too restrictive; the approach I would try now would involve an algebra
whose top level values would still be hardware-oriented bytestrings, but
whose intermediates could be more symbolic. It still wouldn't be powerful
enough to turn a declarative text into an FSM, but at least it'd be able
to transpose a COND form into a decision table or do peephole tail call
optimization.
> There's the apocryphal story of Leonard Zubkoff implementing a
> debugger in a weekend for a new platform, rather than waiting weeks
> for someone else to do the job; I wonder how much more or less his
> debugger contained than DEBUG.COM.
Probably much more -- RPG's story is that it was a "symbolic UNIX
debugger": when one controls the compiler symbols are simple, and
ptrace(2) breaks things up into a debugging process and a debugged
process, which also simplifies things. So I'd imagine it at least had
symbols and breakpoints {go, stop, step into}, and probably had expression
evaluation and possibly step over. (step out requires parsing opcodes,
but the RT was a RISC, which would have helped)
> What do you mean, "loops with tails"? You mean that you don't tend to
> factor the code into a lot of small functions?
Calling a function involves a label, so lots of small functions would mean
lots of labels, which is what we're trying to avoid. The head of a loop
requires a label, but any straight-line code we can tack onto the end
doesn't. So we tend to wind up with chunks that consist of reducing
something to a canonical form (the loop), followed by addition of more
data which will be reduced in another chunk (the tail). I guess it's
effectively an apply(Y, eval(X)) -- somewhat reminiscent of writing in sed
and fairly reminiscent of the algebraists' habit of canonically splitting
maps into projection followed by injection.
> I wonder why DEBUG couldn't rememember labels or breakpoints.
> FIG-Forth ran on the same hardware and remembered the names of every
> routine in the system. Maybe DEBUG had to fit into a tiny static
> corner of a 64K memory segment, to avoid limiting its applicability to
> small programs? But it isn't restricted to disassembling or debugging
> tiny-model programs.
Of course if I was going to write more than 512 bytes of code that way,
and wanted an interactive environment, I'd probably wind up with something
like a forth. The history seems to be that DEBUG.COM, like EDIT.COM, was
part of the "quick and dirty OS" that Microsoft bought, and had been
written figuring that someone else would soon replace them.
> Have you been following Ian Piumarta's Pepsi/Coke/Jolt/Albert work?
> He's very much focused on questions like how to allow you to modify
> Array>>#at: at runtime without breaking everything. (Of course, if
> your modification is broken, you will still have problems...)
No, thanks for the links! I think the reason for the ST-80 spec in ST at
the back of the blue book was not only because metacirculars are cool, but
also because they did cross development/upgrades from time to time by
building up a foreign image and a foreign VM inside the usual image, and
then bootstrapping them to standalone.
> I also think that's the first 8-page conference paper I've ever seen
> that includes a complete and working (?) synthesizable CPU design (in
> noweb and Verilog) in the text of the paper. (It is synthesizable,
> isn't it? My Verilog is not up to snuff. The actual Verilog seems to
> be about 240 lines.)
>
> It's too bad that he doesn't report on how much FPGA space it needed
> or how fast it ran.
True. I think FPGA boards are pretty big and cheap these days (so it
should be possible to "try it and see"), but haven't had the excuse to
play with one. Any recommendations from kragen-discuss?
