Maker Pro
Maker Pro

Finites State Machine (OT?)

J

Jeffrey C. Dege

Jan 1, 1970
0
Jeffrey C. Dege wrote:

In his sig:

^^^^^^^^^^^^^

allegly from Marcus Tulius Cicero.

Could you please produce the original Latin - this doesn't parse (as an
English sentence).

THE SPEECH OF M. T. CICERO IN DEFENCE OF TITUS ANNIUS MILO.
M. Tulli Ciceronis pro T. Annio Milone oratio

This, therefore, is a law, O judges, not written, but born with
us,--which we have not learnt or received by tradition, or read, but
which we have taken and sucked in and imbibed from nature herself;
a law which we were not taught but to which we were made,--which we
were not trained in, but which is ingrained in us,--namely, that if
our life be in danger from plots, or from open violence, or from the
weapons of robbers or enemies, every means of securing our safety is
honourable. [11] For laws are silent when arms are raised, and do
not expect themselves to be waited for, when he who waits will have to
suffer an undeserved penalty before he can exact a merited punishment.

Est igitur haec, iudices, non scripta, sed nata lex, quam non
didicimus, accepimus, legimus, verum CX natura ipsa adripuimus,
hausimus, expressimus, ad quam non docti sed facti, non instituti sed
imbuti sumus, ut, si vita nostra in aliquas insidias, si in vim et
in tela aut latronum aut inimicorum incidisset, omnis honesta ratio
esset expediendae salutis. [11] Silent enim leges inter arma nec se
exspectari iubent, cum ei, qui exspectare velit ante iniusta poena
luenda sit quam iusta repetenda.

--
All the great governments of the world---those now existing, as well
as those that have passed away---have been of this character. They have
been mere bands of robbers, who have associated for purposes of plunder,
conquest, and the enslavement of their fellow men. And their laws, as
they have called them, have been only such agreements as they have found
it necessary to enter into, in order to maintain their organizations,
and act together in plundering and enslaving others, and in securing to
each his agreed share of the spoils.

All these laws have had no more real obligation than have the agreements
which brigands, bandits, and pirates find it necessary to enter into
with each other, for the more successful accomplishment of their crimes,
and the more peaceable division of their spoils.

- Lysander Spooner, "Natural Law"
 
J

Jeffrey C. Dege

Jan 1, 1970
0
On a good CPU, with lots of registers, you can generally write a
fairly complex embedded program without using stack for anything but
interrupt context saves and subroutine return addresses. I've written
actually-useful programs that use no stack at all. I wrote one PDP-11
program - a boot loader - that used no stack and no memory, just
registers.

The CDC6600 had no hardware stack. The calling convention was to begin
every subroutine with a jump to zero and to end every subroutine with
a jump to that jump-to-zero. The calling routine would replace the
jump-to-zero with a jump to the instruction following the call, then
jump to the instruction following the what is no longer a jump-to-zero.

Worked fine, if you could get over your willies about self-modifying code.
For languages in which reentrent function calls were forbidden, anyway.

Like FORTRAN.

It'd be a royal bitch to implement a C compiler on that hardware.

The lack of byte-addressing and the 6-bit character set would see to that.
 
J

John Larkin

Jan 1, 1970
0
The CDC6600 had no hardware stack. The calling convention was to begin
every subroutine with a jump to zero and to end every subroutine with
a jump to that jump-to-zero. The calling routine would replace the
jump-to-zero with a jump to the instruction following the call, then
jump to the instruction following the what is no longer a jump-to-zero.

Worked fine, if you could get over your willies about self-modifying code.
For languages in which reentrent function calls were forbidden, anyway.

Like FORTRAN.

It'd be a royal bitch to implement a C compiler on that hardware.

The lack of byte-addressing and the 6-bit character set would see to that.


The PDP-8 JMS call saved the return address in the first location of
the called routine.


JMS SUBBIE calls the sub,



SUBBIE, 0

..... subroutine code...

JMP I SUBBIE

is the return, an indirect jump through the start of your own
subroutine! It was a paged machine, of course. No stack. Rick Merrill
managed to jam FOCAL-8, a reentrant, stack-oriented, floating-point
language, with editor and all, into 4k x 12 bits of core. I used to do
steamship propulsion system simulations on it.

I think the PDP-8 architecture became the low-end PIC stuff.

The PDP-11 taught me how to think; its architecture was/is beautiful.


John
 
S

Stephen Fuld

Jan 1, 1970
0
John Larkin said:
that.


The PDP-8 JMS call saved the return address in the first location of
the called routine.


JMS SUBBIE calls the sub,



SUBBIE, 0

.... subroutine code...

JMP I SUBBIE

is the return, an indirect jump through the start of your own
subroutine!

The 1108 etc. had that feature long before Ken Olsen founded DEC. It also
had, what most mainframe systems had, an instruction that branched to a
subroutine and stroed the address of the next instruction in a register (IBM
S/360 had the same thing). This was advantagous as it wasn't self modifying
and a subroutine could simply save the contents of that register in a memory
location if necessary. If it was a leaf routine, it didn't even have to do
that if it didn't need to use that register. If a stack was desired (there
was no hardware stack - again along with most mainframes except of course
the Burroughs large scale systems) you simply by convention used a register
as a stack pointer, so such machines support recursive languages today.
 
H

hack

Jan 1, 1970
0
John Larkin said:
On a good CPU, with lots of registers, you can generally write a
fairly complex embedded program without using stack for anything but
interrupt context saves and subroutine return addresses. I've written
actually-useful programs that use no stack at all. I wrote one PDP-11
program - a boot loader - that used no stack and no memory, just
registers.

Indeed, for many programs I use a stack only when there is recursion, and
I make sure there is a stack check at one point in the recursive chain.
For statically nested subroutines I pick registers such that arguments
are likely already in the right register, and return registers are where
the caller wants the result. With proper design, and some conventions
for commonly-used idioms, this can be made to work rather well; spill code
is rarely needed. The whole concept of named variables falls largely by
the wayside -- except in the comments, of course, to help the reader keep
track of what is in the registers at relevant points. Most small leaf
subroutines end up using no storage whatsoever -- and that includes most
of the common run-time functions such as string parsing, number conversion
etc. -- it makes it trivial to write re-entrant code.

Michel.
 
J

John Larkin

Jan 1, 1970
0
Indeed, for many programs I use a stack only when there is recursion, and
I make sure there is a stack check at one point in the recursive chain.
For statically nested subroutines I pick registers such that arguments
are likely already in the right register, and return registers are where
the caller wants the result. With proper design, and some conventions
for commonly-used idioms, this can be made to work rather well; spill code
is rarely needed. The whole concept of named variables falls largely by
the wayside -- except in the comments, of course, to help the reader keep
track of what is in the registers at relevant points. Most small leaf
subroutines end up using no storage whatsoever -- and that includes most
of the common run-time functions such as string parsing, number conversion
etc. -- it makes it trivial to write re-entrant code.

Michel.

What's a leaf?

John
 
J

Jeffrey C. Dege

Jan 1, 1970
0
What's a leaf?

The end of a branch on a tree.

If you think of subroutines calling other subroutines as a tree, the
leafs are the subroutines that don't call any other subroutines.

Of course, subroutine calls diagrams aren't really trees, their directed
graphs - a single subroutine can be called from several other places in
the graph - but a certain sloppiness of idiom isn't uncommon.
 
T

Terry Given

Jan 1, 1970
0
Tom Gardner said:
I've owned one made using hydraulic logic: my automatic gearbox.
And I know of others that are based on gas at 2000-4000 psi,
on unmanned offshore oil rigs.

There are *many* technologies that are used for implementing
FSMs :)

--
Tom Gardner
Mobile Payments,
LogicaCMG Wireless Networks
_____________________________
LogicaCMG
2420 The Quadrant
Aztec West
Bristol BS32 4LD
United Kingdom

T: +44 (0) 117 901 7896 (direct)

A new Zealander built one of the first analogue computers in the UK for
modelling financial markets - it was hydraulic. cute.

I used to have a front-loading washing machine/dryer. These are all FSMs,
but with N m-pole rotary switches, it has m^n states, ie many, of which only
a very few are decoded. it was left in storage for 3 years while i was in
the states, when I came back the switches had all gone dodgy. alas the door
interlock was state-driven rather than, say, water level sensor driven. In
addition to opening the door and getting inundated with hot water, the
stupid thing also turned the dryer on whilst full of water - i found that
from the power bill! cheaper to replace than repair......and the moral of
the story is, always use all states, even if only to point to the zeroth
state (lots of people get bit by this in electronics with turn-on states of
FFs etc causing the FSM to start in the wrong state....)

Cheers
Terry
 
T

Terry Given

Jan 1, 1970
0
Peter Dickerson said:
Surely most GUIs are FSMs, where the state transitions are usually called
messages.

Peter

If so, they are badly implemented ones. just because you make an FSM doesnt
mean you designed it well. s/w is very rarely designed - programmers far
prefer typing to thinking IMO. I read a few articles on the team that writes
software for the space shuttle. typical debugged code has a 5% error rate.
Space Shuttle code has 1 error per 420,000 lines of code (the $4billion cost
of a fuckup may have a lot to do with this. Apparently killing astronauts is
frowned upon), and they do 99% of their debugging before writing a single
line of code. Who hasnt seen a programmer "fix" a minor bug, and in so doing
introduce much worse bugs.

Terry
 
R

R. Steve Walz

Jan 1, 1970
0
Jeffrey said:
Jeffrey C. Dege wrote:

In his sig:

^^^^^^^^^^^^^

allegly from Marcus Tulius Cicero.

Could you please produce the original Latin - this doesn't parse (as an
English sentence).

THE SPEECH OF M. T. CICERO IN DEFENCE OF TITUS ANNIUS MILO.
M. Tulli Ciceronis pro T. Annio Milone oratio

This, therefore, is a law, O judges, not written, but born with
us,--which we have not learnt or received by tradition, or read, but
which we have taken and sucked in and imbibed from nature herself;
a law which we were not taught but to which we were made,--which we
were not trained in, but which is ingrained in us,--namely, that if
our life be in danger from plots, or from open violence, or from the
weapons of robbers or enemies, every means of securing our safety is
honourable. [11] For laws are silent when arms are raised, and do
not expect themselves to be waited for, when he who waits will have to
suffer an undeserved penalty before he can exact a merited punishment.

Est igitur haec, iudices, non scripta, sed nata lex, quam non
didicimus, accepimus, legimus, verum CX natura ipsa adripuimus,
hausimus, expressimus, ad quam non docti sed facti, non instituti sed
imbuti sumus, ut, si vita nostra in aliquas insidias, si in vim et
in tela aut latronum aut inimicorum incidisset, omnis honesta ratio
esset expediendae salutis. [11] Silent enim leges inter arma nec se
exspectari iubent, cum ei, qui exspectare velit ante iniusta poena
luenda sit quam iusta repetenda.

--
All the great governments of the world---those now existing, as well
as those that have passed away---have been of this character. They have
been mere bands of robbers, who have associated for purposes of plunder,
conquest, and the enslavement of their fellow men. And their laws, as
they have called them, have been only such agreements as they have found
it necessary to enter into, in order to maintain their organizations,
and act together in plundering and enslaving others, and in securing to
each his agreed share of the spoils.

All these laws have had no more real obligation than have the agreements
which brigands, bandits, and pirates find it necessary to enter into
with each other, for the more successful accomplishment of their crimes,
and the more peaceable division of their spoils.

- Lysander Spooner, "Natural Law"
-------------------
Absolutely, but the only govt which is finally not evil, is that
one where all have equal voice, and none are plundered by gangs.

Capitalism is a system that breeds bandit gangs that speculate
and connive to enslave the less lucky. It must be done away with!

-Steve
 
K

KR Williams

Jan 1, 1970
0
Oh, that brings up another rule: if, at any point in your code, you
can't pretty-closely estimate your stack usage, find another line of
work.

Having done designs with 8051s, one quickly learned to keep track
of the stack usage *exactly*.
 
A

Andy Glew

Jan 1, 1970
0
They could not grasp why we were wasting time writing functions that
had nothing in them.

Or, classes that do not extend their base class.
Or...

Zero is a very important number.
There are many flavors of 0.
 
K

Keith Wootten

Jan 1, 1970
0
In message <[email protected]>, John Larkin

On a good CPU, with lots of registers,
you can generally write a
fairly complex embedded program without using stack for anything but
interrupt context saves and subroutine return addresses. I've written
actually-useful programs that use no stack at all. I wrote one PDP-11
program - a boot loader - that used no stack and no memory, just
registers.


On an even better CPU, one with two stacks, you can write a very complex
embedded program without any registers other than status and
initialisation.

I like stacks.

Cheers
 
R

Rob Warnock

Jan 1, 1970
0
+---------------
| > JMS SUBBIE calls the sub,
| > SUBBIE, 0
| > .... subroutine code...
| > JMP I SUBBIE
| > is the return, an indirect jump through the start of your own
| > subroutine!
|
| The 1108 etc. had that feature long before Ken Olsen founded DEC. It also
| had, what most mainframe systems had, an instruction that branched to a
| subroutine and stroed the address of the next instruction in a register
| (IBM S/360 had the same thing).
+---------------

The DEC PDP-10 had both of those *and* a stack-oriented call/return!
The "JSR addr" instruction was just like a PDP-8 JMS, except that it
also stored the flags with the saved PC. The "JSP reg, addr" was like
the 1108 instruction you mention, also like the S/360 BAL. ["JSP r1,(r2)"
was "BALR r1, r2".] "PUSHJ reg, addr" was like most modern stack-based
calls, except that you could use *any* register as the stack pointer
[though normally r0 wasn't used, since you couldn't index off of r0].


-Rob
 
H

hack

Jan 1, 1970
0
John Larkin said:
What's a leaf?

A subroutine that doesn't call any other subroutines. I thought this
was standard terminology; if it's IBMese, I apologise.

Michel.
 
J

John Larkin

Jan 1, 1970
0
+---------------
| > JMS SUBBIE calls the sub,
| > SUBBIE, 0
| > .... subroutine code...
| > JMP I SUBBIE
| > is the return, an indirect jump through the start of your own
| > subroutine!
|
| The 1108 etc. had that feature long before Ken Olsen founded DEC. It also
| had, what most mainframe systems had, an instruction that branched to a
| subroutine and stroed the address of the next instruction in a register
| (IBM S/360 had the same thing).
+---------------

The DEC PDP-10 had both of those *and* a stack-oriented call/return!
The "JSR addr" instruction was just like a PDP-8 JMS, except that it
also stored the flags with the saved PC. The "JSP reg, addr" was like
the 1108 instruction you mention, also like the S/360 BAL. ["JSP r1,(r2)"
was "BALR r1, r2".] "PUSHJ reg, addr" was like most modern stack-based
calls, except that you could use *any* register as the stack pointer
[though normally r0 wasn't used, since you couldn't index off of r0].


-Rob

The PDP-11 did

JSR Rn, dest

whence Rn was pushed on the stack (R6 was always the SP) and the
return address was stashed in Rn. The idea was...


code
code
JSR R5, SUBBIE
arg1
arg2
arg3
code ...


so that the sub would use R5 in autoincrement mode to nab the args.
Bad idea! But you could also do JSR PC, dest which just pushed the
return address on the stack. R7 was the PC, incidentally, and was a
general register. You could, for instance

CLR PC
ADD R3, PC
NEG PC

or the famous Land Mine instruction,

MOV -(PC), -(PC)

which copied itself into all of memory, backwards.

The 68K, like most contemporary gadgets, just pushes the return
address.

John
 
J

John Larkin

Jan 1, 1970
0
Having done designs with 8051s, one quickly learned to keep track
of the stack usage *exactly*.

I'd just as soon cut off my mouse finger as program an 8051!

Someone recently editoralized that semiconductor design and fab is
getting so expensive, only one big-CPU architecture can ultimately
survive. And it will be, basicly, the 8008.

John
 
K

KR Williams

Jan 1, 1970
0
I'd just as soon cut off my mouse finger as program an 8051!

I found it "interesting". We did about 25K lines of code for the
last generation and it worked quite well (FIPS 140 class 4 stuff
too). After getting into the "Harvard" architecture it wasn't
all that bad. The only thing put on the stack was a few
registers and return addresses. Other widgets in the chip made
it rather nice. Of course the last time I touched one was more
than ten years ago. ...though I wouldn't be afraid to use
another variant again today.

Processors are tools. ...nothing more. ...though chain saws
scare me, 8051s... Please!
Someone recently editoralized that semiconductor design and fab is
getting so expensive, only one big-CPU architecture can ultimately
survive. And it will be, basicly, the 8008.

That "someone" is simply stupid. ...likely a journalism major
writing fir EET, or some such.
 
J

John Larkin

Jan 1, 1970
0
That "someone" is simply stupid. ...likely a journalism major
writing fir EET, or some such.

Maybe so. But at a couple of billion dollars a pop, CPUs can get
expensive. Add another bunch of billions for applications support,
maybe.

The argument was that PA-risc and Alpha have already fallen, and Sparc
is in trouble. Itanic isn't looking too good, either.

John
 
G

Greg Lindahl

Jan 1, 1970
0
John Larkin said:
Maybe so. But at a couple of billion dollars a pop, CPUs can get
expensive. Add another bunch of billions for applications support,
maybe.

You might want to check your numbers -- while fabs are that expensive,
CPU designs are not necessarily so expensive. In particular, AMD
(currently) and DEC (used to) spend a lot less than that on their
designs. And that's just a piece of the market -- there are other
places where from-scratch designs are done, and I assure you that if
they cost a billion a pop, no one (other than Intel) would do them.

We've always known that stupidly expensive engineering is hard to
fund. Fortunately, not all engineers are stupid.

-- greg
 
Top