Finite State Machines in Forth (1995) (opens in new tab)

(galileo.phys.virginia.edu)

110 pointsnprescott5y ago31 comments

31 comments

With the veritable flurry of state machine posts today[0,1] I thought I'd (re)submit[2] one of my favorite posts on finite state machines in Forth.

The specific example is of number input routine allows signed decimal numbers without power-of-10 exponents (fixed-point, in FORTRAN parlance) and comes from the author's book Scientific Forth, where a fuller example is used ... to determine whether a piece of text is a proper identifier (that is, the name of a variable, subroutine or function) according to the rules of FORTRAN.

I originally heard of Scientific Forth from Programming in the Twenty First Century where it made a list of "Five Memorable Books about Programming"[3] with the following description:

Dr. Noble demonstrates how he uses Forth for hardcore matrix work and, when he realizes that RPN notation isn't ideal in all circumstances, develops a translator from infix expressions to Forth.

[0]: https://news.ycombinator.com/item?id=22746708

[1]: https://news.ycombinator.com/item?id=22748785

[2]: previously 3, 6 and 8 years ago, never any comments: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

[3]: https://prog21.dadgum.com/19.html

nyankosensei5y ago

A project to create a Creative Commons version of Dr. Noble’s book was started, but doesn’t seem very active lately [0]. The lead even received permission from Dr. Noble’s widow [1].

[0] https://github.com/Josefg/Scientific_FORTH [1] https://github.com/Josefg/Scientific_FORTH/blob/master/Conse...

nprescottOP5y ago

I've helped out with a few chapters! I'm actually very excited about it due to the relative scarcity of physical copies of the book.

While it isn't too active, the most recent activity was in the last week or so, I think all that remains are some figures and tables for a couple chapters, the index and proof-reading[0]. It's very nearly there due to a lot of work on Josef's part.

[0]: https://github.com/Josefg/Scientific_FORTH/wiki

hangonhn5y ago

FSM is something I've always been curious about but I can't seem to find any good intro on. Does anyone have a good recommendations? I sort of don't want one tied to a specific language but rather one that helps me understand it from a conceptual level.

Thanks!

DonHopkins5y ago

I hope this book puts you on the right path, Brothers and Sisters.

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

pstuart5y ago

Ramen!

bear86425y ago

Hopcroft Ullman's Introduction to Automata Theory, Languages and Computation has good section on state machines and their connection to Regular Expressions

WhyNott5y ago

So I searched and I found that my library has a book with this exact title, but by a guy named Shyamalendu Kandar. I've read the introduction and the preface, and nothing suggests it has any direct influence or relation to the book you are describing. Maybe its just a coincidence, though it does seem slightly fishy.

jjtheblunt5y ago

That book is amazing. I donated mine to my hometown library maybe 20 years ago, or more, but should have kept it.

hangonhn5y ago

Thank you!!! Its relationship to regex is actually precisely the part that piqued my interest.

1 more reply

qtplatypus5y ago

This book is great. It opened my mind how powerful regular expressions could be.

coupdejarnac5y ago

Any intro level logic design textbook should have a discussion of state machines. My copy of Bebop to the Boolean Boogie has a few pages about them. That's a good freshman level EE book.

bp00175y ago

If you're looking for a more theoretical overview, the first chapter of Sipster's Introduction to the Theory of Computation is a really solid into to FSA and automata in general.

basementcat5y ago

The first example is a machine with two states.

https://en.wikipedia.org/wiki/Finite-state_machine

From there you can deep dive into subjects like digital logic and automata theory.

davidkpiano5y ago

I made a visual cheat-sheet here: https://excalidraw.com/#json=5149387806212096,XD-zzKj7vlSIgw...

DonHopkins5y ago

I always thought Go Corporation should have made a mathematically focused FORTH dialect called "GoFORTH&*”, to bring FORTH abundantly in the earth.

NieDzejkob5y ago

I'm trying to follow the code in "The Best FSM so far", and I can't see the moment where offset-to-action is added to the base address of the FSM like in the previous examples. Shouldn't there be a `R@ +` after `CELLS`?

carapace5y ago

This is great! (but maybe put a (1995) on the title?)

capableweb5y ago

Forth is mentioned in the title, do you really need to add that it's before the 2000's if that's the case? ;)

bear86425y ago

Forth is still alive and kicking!

2 more replies

dang5y ago

Added.

j / k navigate · click thread line to collapse

31 comments

nprescottOP5y ago

With the veritable flurry of state machine posts today[0,1] I thought I'd (re)submit[2] one of my favorite posts on finite state machines in Forth.

I originally heard of Scientific Forth from Programming in the Twenty First Century where it made a list of "Five Memorable Books about Programming"[3] with the following description:

Dr. Noble demonstrates how he uses Forth for hardcore matrix work and, when he realizes that RPN notation isn't ideal in all circumstances, develops a translator from infix expressions to Forth.

[0]: https://news.ycombinator.com/item?id=22746708

[1]: https://news.ycombinator.com/item?id=22748785

[2]: previously 3, 6 and 8 years ago, never any comments: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

[3]: https://prog21.dadgum.com/19.html

nyankosensei5y ago

A project to create a Creative Commons version of Dr. Noble’s book was started, but doesn’t seem very active lately [0]. The lead even received permission from Dr. Noble’s widow [1].

[0] https://github.com/Josefg/Scientific_FORTH [1] https://github.com/Josefg/Scientific_FORTH/blob/master/Conse...

nprescottOP5y ago

I've helped out with a few chapters! I'm actually very excited about it due to the relative scarcity of physical copies of the book.

[0]: https://github.com/Josefg/Scientific_FORTH/wiki

hangonhn5y ago

Thanks!

DonHopkins5y ago

I hope this book puts you on the right path, Brothers and Sisters.

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

pstuart5y ago

Ramen!

bear86425y ago

Hopcroft Ullman's Introduction to Automata Theory, Languages and Computation has good section on state machines and their connection to Regular Expressions

WhyNott5y ago

jjtheblunt5y ago

That book is amazing. I donated mine to my hometown library maybe 20 years ago, or more, but should have kept it.

hangonhn5y ago

Thank you!!! Its relationship to regex is actually precisely the part that piqued my interest.

1 more reply

qtplatypus5y ago

This book is great. It opened my mind how powerful regular expressions could be.

coupdejarnac5y ago

Any intro level logic design textbook should have a discussion of state machines. My copy of Bebop to the Boolean Boogie has a few pages about them. That's a good freshman level EE book.

bp00175y ago

If you're looking for a more theoretical overview, the first chapter of Sipster's Introduction to the Theory of Computation is a really solid into to FSA and automata in general.

basementcat5y ago

The first example is a machine with two states.

https://en.wikipedia.org/wiki/Finite-state_machine

From there you can deep dive into subjects like digital logic and automata theory.

davidkpiano5y ago

I made a visual cheat-sheet here: https://excalidraw.com/#json=5149387806212096,XD-zzKj7vlSIgw...

DonHopkins5y ago

I always thought Go Corporation should have made a mathematically focused FORTH dialect called "GoFORTH&*”, to bring FORTH abundantly in the earth.

NieDzejkob5y ago

carapace5y ago

This is great! (but maybe put a (1995) on the title?)

capableweb5y ago