Finite State Machines in Forth (1995)
galileo.phys.virginia.eduWith 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...
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...
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.
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!
I hope this book puts you on the right path, Brothers and Sisters.
https://en.wikipedia.org/wiki/The_Gospel_of_the_Flying_Spagh...
Ramen!
Hopcroft Ullman's Introduction to Automata Theory, Languages and Computation has good section on state machines and their connection to Regular Expressions
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.
That book is amazing. I donated mine to my hometown library maybe 20 years ago, or more, but should have kept it.
Thank you!!! Its relationship to regex is actually precisely the part that piqued my interest.
With automata theory it’s useful to be pedantic. What people ordinarily mean by “regex” are in different classes of automata from regular expressions as equivalent to finite state machines. For example Perl capture groups, look ahead, and backtracking are beyond what a finite state machine or its equivalent regular expression is capable of. Though for me the simplicity of the FSM is a big part its intellectual appeal.
This book is great. It opened my mind how powerful regular expressions could be.
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.
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.
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.
I made a visual cheat-sheet here: https://excalidraw.com/#json=5149387806212096,XD-zzKj7vlSIgw...
I always thought Go Corporation should have made a mathematically focused FORTH dialect called "GoFORTH&*”, to bring FORTH abundantly in the earth.
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`?
This is great! (but maybe put a (1995) on the title?)
Forth is mentioned in the title, do you really need to add that it's before the 2000's if that's the case? ;)
Forth is still alive and kicking!
Of course! Have friends who work with it on a daily basis. My comment was mostly tongue in cheek, didn't mean that Forth is completely dead. Usually when seeing Forth though, it's bit older stuff than say PHP. My friends for example, are stuck trying to refactor very old code, written in Forth.
Didn't mean no harm :)
What do your friends do with it? It’s very high on my priority list for new languages to learn, and finding a job with it someday would be very interesting.
Be sure to read "Thinking Forth". Even if you don't wind up doing a lot with Forth it will still improve your abilities as a programmer.
It's in my pile o' papers. I've broken it out a couple of times but haven't gotten far yet.
One set work with maintaining old software for a national bank and the other set work with software for a huge international company that are not IT focused but ended up with software and firmware that just been ticking along since forever.
I'm not jealous and don't think I would bear working like that every day for months. Take a hard look and try to build software with Forth before you try to use it professionally.
There's a reasonable number of people out there who would be very interested in a disambiguation of scale, architecture, implementational wins/shortcomings, etc, about these two cases.
Codebase size? Entropic/organizational complexity? Word style? Environment (custom/standard)? Standard(s) used? Ease of debugging? Testing methodology used?
I most definitely am not literally asking for answers to this set of questions (considering the cases of a bank and an industry that presumably doesn't want to be known for its software) - I guess I'm just being exact in the gist of my curiosity :)
The only interesting illustrative example I can provide is that Mattel once used Forth for its toys (quoting previous times I mentioned this: https://news.ycombinator.com/item?id=21823216, https://news.ycombinator.com/item?id=17755287)
I don't know of any recent case studies.
You might want to actually use it first before thinking you want to use it more. Forth is simple because it is primitive and passes the cognitive load on to you.
None taken - agree Forth's slightly older language.
FORTH ?KNOW IF HONK ELSE FORTH LEARN THEN
Added.