VM for a state-machine machine

[Manuel Rodriguez]

I'm sure, the following question is completely ontopic, because it has to
do with compiler construction. Or to be more specific, of how to translate
one program into another program. The starting point is a turing-machine,
which is used in the Busy Beaver game. I'm linking to the German Wikipedia
https://de.wikipedia.org/wiki/Flei%C3%9Figer_Biber#Beispiele because
they have not only the busy-beaver itself in their article, but also
a visualization state-machine. The diagram shows, that the machine can
have different states, which are changed on demand. The interesting aspect
of a state-machine is, that it is not a computer, and not a Forth virtual
machine. It is something, which is one level deeper. It is called Microcode,
because it is so low level, that no stack or registers are existing.

In theory, it is possible to program a state-machine for every purpose,
for example to print out many One's or solving a factorial problem. But,
what we want is to construct on top something which is more useful. An
easy to program computer, a stackmachine. I believe, that everybody here
in the newsgroup knows, what a stackmachine is, it is more useful than
a statemachine, because it can be programmed in Forth.

And here is my question: How to transform a forth-like stackmachine into
a low-level-state-machine? So we have as input a Forth program and as
output a state-machine. Surely, I've researched the problem before I'm
asking. I found on some Homebrew CPUs websites the MARK I Forth computer
http://www.aholme.co.uk/Mk1/Architecture.htm in which additional to
a Forth interpreter also the Microcode is given. But, I'm not sure,
if this works in area of state-machines, and the busy-beaver-problem,
because it is very focused on real hardware.

[foxaudio...@gmail.com]

The late Dr. Julian Nobel created a set of extensions to Forth that lets one write an FSM as a table in Forth words.

The white paper is here:
http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html

Would this suit your requirements?

B

[foxaudio...@gmail.com]

NOTE:
The ANS Forth version which should compile on compliant systems is at the end of the document

[Manuel Rodriguez]

Am Dienstag, 16. Januar 2018 20:07:50 UTC+1 schrieb foxaudio...@gmail.com:
> http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html
> Would this suit your requirements?

The paper itself was not very helpful because it is very hard to understand.
But in the introduction were references given to other papers and also
google scholar give papers back, in which J.V. Noble was cited, so the
overall convolute satisfied my needs. Thank you.

[rickman]

I'm familiar with state machines and stack machines. But I'm not clear what
you are asking. You say you want to input a Forth program and output a
state machine, but I'm not clear on what it means to output a state machine.

The other responder seemed to think you simply want to implement a FSM
(Finite State Machine, the usual terminology) in Forth which is not hard at
all. The only question is how Forthy you wish to be.

I'm not at all clear on why you would be interested in the MARK I Forth
computer. It is just hardware which can run Forth programs. The
busy-beaver-problem can be adequately explored by any Forth compiler
regardless of the hardware. No?

--

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

[menti...@gmail.com]

On Tuesday, January 16, 2018 at 12:07:56 AM UTC-8, Manuel Rodriguez wrote:
> I'm sure, the following question is completely ontopic, because it has to
> do with compiler construction. Or to be more specific, of how to translate

> one program into another program. [...]

http://ai.neocities.org/MsIeAi.html
is where I am writing a program in
JavaScript for Microsoft Internet Explorer
to make it easier for people to work on
MindForth artificial intelligence in Forth
and ghost.pl AI in Strawberry Perl Five.

Mentifex (Arthur)

[Rod Pemberton]

On Tue, 16 Jan 2018 00:07:54 -0800 (PST)
Manuel Rodriguez <a...@gmx.net> wrote:

> I'm sure, the following question is completely ontopic, because it
> has to do with compiler construction.

(You'd be wrong, but whatever ...)

> Or to be more specific, of how
> to translate one program into another program.

Usenet groups comp.compilers or comp.lang.misc would be your best bet
after Google searches.

> The starting point is
> a turing-machine, which is used in the Busy Beaver game. I'm linking
> to the German Wikipedia

> [link]

I'm not looking at that.

> because
> they have not only the busy-beaver itself in their article, but also
> a visualization state-machine. The diagram shows, that the machine
> can have different states, which are changed on demand. The
> interesting aspect of a state-machine is, that it is not a computer,
> and not a Forth virtual machine. It is something, which is one level
> deeper.

I don't know what you mean by that, as FSMs are usually coded in a
high-level language, like Forth or C, so they cannot be "one-level
deeper".

> It is called Microcode, because it is so low level, that no
> stack or registers are existing.

Microcode
https://en.wikipedia.org/wiki/Microcode


As for FSMs, Julian V. Noble (RIP) coded a bunch of FSM in Forth.
Someone else (Jeff Fox?) posted a link to his paper. I also ported one
of his FSMs to C, years ago, posted to comp.lang.c, which may be easier
to understand:

https://groups.google.com/d/msg/comp.lang.c/WjqgM4p0LrU/XA-YJvYsqS8J

> In theory, it is possible to program a state-machine for every
> purpose, for example to print out many One's or solving a factorial
> problem.

Yes, but unless you have a tool (compiler-compiler, BNF parser, etc) to
construct the FSM from a grammar, FSMs difficult to program and
maintain, for anything more than simple tasks. Grammars are human
readable and editable. Of course, if you have a grammar as the
front-end and an FSM as the back-end, you don't need Forth.

> But, what we want is to construct on top something which is
> more useful. An easy to program computer, a stackmachine.

In my opinion, the easiest way to program a computer is using an
integer array, not a stack. The easiest way to program an array is by
using an array-based programming language, like Brainfuck. Compilers
for a few higher level languages (BASIC, assembly, etc) have been
produced for Brainfuck. However, Brainfuck is very primitive. You
might wish to select another language. Unfortunately, if you want your
code to be portable, you're restricted to C and Forth, as they're the
most widely implemented.

> I believe, that everybody here in the newsgroup knows, what a
> stackmachine is,

Ok.

> it is more useful than a statemachine,

Speculative.

> because it can be programmed in Forth.

A state machine can be programmed in Forth too, as you also stated. So,
I don't know what you intended to say here.

> And here is my question:

So, you do have one of those.

> How to transform a forth-like stackmachine into a
> low-level-state-machine? So we have as input a Forth program and as
> output a state-machine.

That's a good question. I've not done that. I'd direct you to post to
comp.compilers.


Rod Pemberton
--
"White Privilege - The privilege of being called 'racist' by people who
see nothing else about you except your race." - Internet meme

[Manuel Rodriguez]

Am Freitag, 19. Januar 2018 03:45:53 UTC+1 schrieb Rod Pemberton:
> > The starting point is
> > a turing-machine, which is used in the Busy Beaver game. I'm linking
> > to the German Wikipedia
> > [link]
>
> I'm not looking at that.

"This myth says that there are remnants of a space station called c-base underneath the city centre of Berlin." https://en.wikipedia.org/wiki/C-base#Mythological_self-image_of_the_c-base