discussion
discussion copied to clipboard
ForthHub
Minimal set of low level words to build forth
Hi folks,
I was curious how many low level words do you need to build forth. So I took sod32 by Lennart Benschop which uses 32 low level words and started to redefine low level words via other low level words. The whole process can be seen here. At the end of the day I managed to reduce low level words to 7 primitives: nop, nand, !, @, um+, special, lit. Inner interpreter has additional logic for 'exit' and 'call'. I was running tester.fr to ensure all words behave as expected and also used run time to track performance. My final implementation runs 708 times slower than original sod32. This whole effort hardly can be used in practice, but it was a fun little project. I wonder if we really need 3 primitives to access memory: @, ! and lit? Please let me know if there is any trick I can use to reduce this.
Thanks, Kirill.
On 12/27/2020 at 9:29 PM, "kt97679" [email protected] wrote:
Hi folks,
I was curious how many low level words do you need to build forth. So I took sod32 by Lennart Benschop which uses 32 low level words and started to redefine low level words via other low level words. The whole process can be seen [here](https://github.com/kt97679/forth- dev/commits/reduce_opcodes). At the end of the day I managed to reduce low level words to 7 primitives: nop, nand, !, @, um+, special, lit. Inner interpreter has additional logic for 'exit' and 'call'. I was running tester.fr to ensure all words behave as expected and also used run time to track performance. My final implementation runs 708 times slower than original sod32. This whole effort hardly can be used in practice, but it was a fun little project. I wonder if we really need 3 primitives to access memory: @, ! and lit? Please let me know if there is any trick I can use to reduce this.
While the three word Forth might be implemented with just teh ability to communicate with terminal device and the words XC@,m XC!, and @EXECUTE, the sensible minimum is something a little more wordy.
Peter Knaggs and myself put together this proooposal for the 2015 conference.
http://www.euroforth.org/ef15/papers/knaggs.pdf
I understand C. H. Ting has a similarly sparse set of primitives. While many Forth words can be implemented in terms of others, I expect that you would only do so as part of a bootstrapping a system onto a totally new architecture where there are no helpful resources. In the end, gaining reasonable performance will demand re-coding for efficiency.
Regards
Paul E. Bennett IEng MIET Systems Engineer Lunar Mission One Ambassador
Paul E. Bennett IEng MIET..... Forth based HIDECS Consultancy............. Mob: +44 (0)7811-639972 Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
Hi Paul,
do you know by chance how we can implement arithmetic and boolean operations just using XC@, XC!, and @EXECUTE? With all honesty I have no idea how this can be done.
Thanks, Kirill.
On 12/27/2020 at 11:05 PM, "kt97679" [email protected] wrote:
Hi Paul,
do you know by chance how we can implement arithmetic and boolean operations just using XC@, XC!, and @EXECUTE? With all honesty I have no idea how this can be done.
Thanks, Kirill.
As I understand it, those three words are used to insert and check the machine code instructions of the processor you are working with in order to construct the rest of the Forth VM primitives to a level where you can continue more easily. Think of them as the Peek and Poke and JUMP via Vector set.
Regards
Paul E. Bennett IEng MIET Systems Engineer Lunar Mission One Ambassador
Paul E. Bennett IEng MIET..... Forth based HIDECS Consultancy............. Mob: +44 (0)7811-639972 Going Forth Safely ..... EBA. www.electric-boat-association.org.uk..
I think I'd want to see the rest of for example Ting's set implemented in these 7 words ?
I started with Ting's set when building webForth, though there were a few more words that it made a HUGE difference to code - especially find or some part of it.
@Paul if XC! , XC@ etc are used to write machine code, then I don't see this as a minimum set because all its done is move "code" into forth.
@Kiril - what is "special" in your list.
@mitra42 special is used to call os functions like read and write files. It can be implemented via syscalls.
A lot of the exercises in this tend to just implement a virtual machine (for example with a huge switch statement), and then define a few primitives on top of that, and then define forth in those primitives - for example I could define forth in one word opcode then define "rot" as 5 opcode. But if I do that, then I haven't really made the port any easier since I've still got to define about 30 words in my switch statement. It doesn't look like you've done this, but I still can't see for example how to build rot from your 7 words: nop, nand, !, @, um+, special, lit. can you define rot in those words so e can see your approach.
Here is the new rot definition: https://github.com/kt97679/forth-dev/commit/2a3b456d1cf536a8ac2b901488b01261cc8e25f3#diff-6e5f6da6018a5fcb663d9b6fdbe51567e1bfb78e4cb8827663465886e0ac9547R120
You can check other commits to see how I replaced low level opcodes with high level definitions.
On Sun, Dec 27, 2020 at 3:44 PM Mitra Ardron [email protected] wrote:
A lot of the exercises in this tend to just implement a virtual machine (for example with a huge switch statement), and then define a few primitives on top of that, and then define forth in those primitives - for example I could define forth in one word opcode then define "rot" as 5 opcode. But if I do that, then I haven't really made the port any easier since I've still got to define about 30 words in my switch statement. It doesn't look like you've done this, but I still can't see for example how to build rot from your 7 words: nop, nand, !, @, um+, special, lit. can you define rot in those words so e can see your approach.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-751529935, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA2OI3UGSARUS3Y2NL2MN4LSW7BFDANCNFSM4VLGY4HA .
So if I read that commit correctly, you are using some working variables (at addresses 8, 12, 16) to allow things like ROT and SWAP to be defined.
(By the way, its coincidence that my example opcode two comments above uses the same word as SOD32 does)
Yes, location 0 holds stack pointer, location 4 holds return stack pointer, locations after that are "registers" to manipulate stack values.
On Sun, Dec 27, 2020 at 4:05 PM Mitra Ardron [email protected] wrote:
So if I read that commit correctly, you are using some working variables (at addresses 8, 12, 16) to allow things like ROT and SWAP to be defined.
(By the way, its coincidence that my example opcode two comments above uses the same word as SOD32 does)
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-751531975, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA2OI3UDXGEO2CNVTPWUK2LSW7DT3ANCNFSM4VLGY4HA .
"I still can't see for example how to build
rotfrom your 7 words:nop, nand, !, @, um+, special, lit. can you define rot in those words."
One can build flip flops and address decoders from NANDs, SRAM and registers from flip flops and decoders, and stacks from SRAM and register (if not implemented as cascaded shift register). From there, it needs moving stack tops between two stacks and from/to a temporary holding register (to avoid, at this point, swap), and voila, there's your ROT :)
IMHO 7 primitives is a bit too few - and this is confirmed in the 708 times slower performance.
Both C.H. Ting and C.H. Moore settled on "about" 32 primitives as the minimum sub-set to allow efficient synthesis and execution of Forth.
Needless to say, you can do a lot with fewer instructions.
The PDP-8 was a perfectly viable machine capable of running 4K FOCAL and BASIC with just TAD, AND, DCA, ISZ, JMP, JMS plus the modify accumulator instructions (Clear, Complement, Shift left, shift right, set and clear carry etc) that were made available through the OPR class of instruction. I think a minimum of 16 and a maximum of 32 primitives would be needed depending on the machine architecture.
@monsonite yes, I mentioned in the very beginning that there is not much practical use in the reducing of the number of primitives. This is more of the theoretical question what is most orthogonal set of words that can be used to build forth and can't be reduced.
If it's a theoretical question you might be interested in https://en.wikipedia.org/wiki/One-instruction_set_computer
@jacereda yes, I'm aware of the OISC, but I'm specifically interested in forth primitives that can be used to define the rest of the system. It is absolutely possible to implement forth in OISC, but in this case OISC single command will be used as an assembler, not as a forth primitive. And we will need to implement stack and everything else.
given that the logic of a NAND gate is enough to derive all other gates from it, and all kinds of gate logic in turn enough to model all primitives Forth would ever want to use, it seems that AND and 0= should all be needed, in addition to those words needed to glue them together such that new words can be written and executed - a NAND primitive alone shouldn't be enough to bootstrap a full system from it, as the NAND doesn't know about how to "connect" them, that is, how to build new words from it. It may also be a bit hefty to, say, having to implement a stack from NANDs alone. But as the question was about "needed", I suppose that required effort to implement a minimal system can be disregarded. Or is practicality also an aspect?
given that the logic of a NAND gate is enough to derive all other gates from it, and all kinds of gate logic in turn enough to model all primitives Forth would ever want to use, it seems that AND and 0= should all be needed...
Digital logic doesn't just require gates, but also something like flip-flops; some kind of memory.
Ah, but with (several) NAND gates you can make a flipflop...
On Wed, 19 Jan 2022, 13:44 Alex Dowad, @.***> wrote:
given that the logic of a NAND gate is enough to derive all other gates from it, and all kinds of gate logic in turn enough to model all primitives Forth would ever want to use, it seems that AND and 0= should all be needed...
Digital logic doesn't just require gates, but also something like flip-flops; some kind of memory.
— Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-1016104957, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACKCGHAO2FOXZNBB6YT4IATUWZFSZANCNFSM4VLGY4HA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
You are receiving this because you are subscribed to this thread.Message ID: @.***>
And the same with memory: have enough flip-flops (from NANDs) and decoders (from NANDs), and you can build any amount of RAM (from just NANDs)
When I try responding by email, it doesn't work; so I'm trying again in the github page:
True; but then you also need to be able to tri-state I/O bits. The only way you can do that with a NAND is if you add a separate output-enable input, or if the output is the wire-OR kind of thing which is a power hog and slows things down.
On 1/18/22 11:02 PM, Stuart wrote:
Ah, but with (several) NAND gates you can make a flipflop...
You don't need to tri-state outputs. You can also connect them as long as not both states are driven, as with open collector outputs. Those connect to a common usually high potential bar, pulled high by a pull-up, and any switched gate will pull it low. Or any number of active gates, doesn't matter. That's called a "wired or" and an alternative to tri-state when wanting to connect multiple outputs together.
Would a minimal set of primitives, build from NANDs, really care much about power? But there may arise another problem when trying to build them from NANDs only which I didn't consider in my first post: the problem of lack of concurrency when "connecting" them in software.
On 2020-12-27 16:29, kt97679 wrote:
Hi folks,
I was curious how many low level words do you need to build forth. So I took sod32 https://lennartb.home.xs4all.nl/sod32.tar.gz by Lennart Benschop which uses 32 low level words and started to redefine low level words via other low
One of the IOCCC 1992 winners wrote a tokenised indirect threaded Forth (like) with 13 primitives. I haven't looked at it in years, but it might be a fun snow day activity to study:
https://www.ioccc.org/years.html#1992_buzzard.2
-- Anthony C Howe @.*** BarricadeMX & Milters http://snert.com/ http://nanozen.snert.com/ http://snertsoft.com/
Ulrich Hoffman has also made considerable efforts to identify the useful minimum that will get you a practical Forth. See his presentation "Forth - The New Synthesis Growing Forth with preForth and seedForth" from FOSDEM 2020 here: https://archive.fosdem.org/2020/schedule/event/forth_new_synthesis/ . preForth has 13 primitives and seedForth has 31.
-- Ben Scherrey
On Sat, Jan 16, 2021 at 12:44 AM Ken Boak @.***> wrote:
IMHO 7 primitives is a bit too few - and this is confirmed in the 708 times slower performance.
Both C.H. Ting and C.H. Moore settled on "about" 32 primitives as the minimum sub-set to allow efficient synthesis and execution of Forth.
Needless to say, you can do a lot with fewer instructions.
The PDP-8 was a perfectly viable machine capable of running 4K FOCAL and BASIC with just TAD, AND, DCA, ISZ, JMP, JMS plus the modify accumulator instructions (Clear, Complement, Shift left, shift right, set and clear carry etc) that were made available through the OPR class of instruction. I think a minimum of 16 and a maximum of 32 primitives would be needed depending on the machine architecture.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-761084147, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAGWP76PJMC763CDL3MLZDDS2B5IVANCNFSM4VLGY4HA .
On 2022-01-19 10:18, Anthony Howe wrote:
On 2020-12-27 16:29, kt97679 wrote:
I was curious how many low level words do you need to build forth. So I took sod32 https://lennartb.home.xs4all.nl/sod32.tar.gz by Lennart Benschop which uses 32 low level words and started to redefine low level words via other low
One this subject, there are plenty of one and even zero instructions CPUs, and one of my favorite is the SUBLEQ computer;
Gary Explains; https://www.youtube.com/watch?v=jRZDnetjGuo (other resources available too, but this is fairly easy to understand by comparison)
So, with a SUBLEQ instruction, should be able to bootstrap the rest of a FORTH system. And it should be fairly easy to implement that in FPGA or with discrete ICs in hardware.
Enjoy Niclas
You could look at sectorForth, implemented in under 512 bytes, to fit in the boot sector, in x86 assembly language
https://github.com/cesarblum/sectorforth
It was inspired by Bernd Paysan's post from 1996, using 8 primitives plus KEY and EMIT.
Have a look at the "Hello World" example to see how the language is brought up from scratch.
https://github.com/cesarblum/sectorforth/blob/master/examples/01-helloworld.f
Hi folks,
I would like to clarify that my original research was about discovering an orthogonal minimal set of words sufficient for building the whole forth system. Alan Kay once described fundamental parts of lisp as "Maxwell equations of the software https://www.gnu.org/software/mes/manual/html_node/LISP-as-Maxwell_0027s-Equations-of-Software.html" and I was curious what a forth analog.
This was not about building the smallest forth in the world or using cpu with the smallest set of commands.
Thanks, Kirill.
On Wed, Jan 19, 2022 at 3:49 PM Ken Boak @.***> wrote:
You could look at sectorForth, implemented in under 512 bytes, to fit in the boot sector, in x86 assembly language
https://github.com/cesarblum/sectorforth
It was inspired by Bernd Paysan's post from 1996, using 8 primitives plus KEY and EMIT.
Have a look at the "Hello World" example to see how the language is brought up from scratch.
https://github.com/cesarblum/sectorforth/blob/master/examples/01-helloworld.f
— Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-1016539538, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA2OI3RGT7DYNHVHCGV4Q6DUW3FQJANCNFSM4VLGY4HA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
You are receiving this because you authored the thread.Message ID: @.***>
1 (one) word.
Probably Chuck would point out that all you need is an operator that can compile a byte into RWX memory.
On Wed, Jan 19, 2022 at 11:34 AM kt97679 @.***> wrote:
Hi folks,
I would like to clarify that my original research was about discovering an orthogonal minimal set of words sufficient for building the whole forth system.
-- Jack Woehr, IBM Champion 2021 https://www.youracclaim.com/badges/528d23d6-087f-4698-8d17-d59688106ac4/public_url Absolute Performance, Inc. 12303 Airport Way, Suite 100 Broomfield, CO 80021
NON-DISCLOSURE NOTICE: This communication including any and all attachments is for the intended recipient(s) only and may contain confidential and privileged information. If you are not the intended recipient of this communication, any disclosure, copying further distribution or use of this communication is prohibited. If you received this communication in error, please contact the sender and delete/destroy all copies of this communication immediately.
I'm afraid 1 word will not work. Memory modification can't be used to implement arithmetic operations.
On Wed, Jan 19, 2022 at 7:39 PM Jack J. Woehr @.***> wrote:
1 (one) word.
Probably Chuck would point out that all you need is an operator that can compile a byte into RWX memory.
On Wed, Jan 19, 2022 at 11:34 AM kt97679 @.***> wrote:
Hi folks,
I would like to clarify that my original research was about discovering an orthogonal minimal set of words sufficient for building the whole forth system.
-- Jack Woehr, IBM Champion 2021 < https://www.youracclaim.com/badges/528d23d6-087f-4698-8d17-d59688106ac4/public_url
Absolute Performance, Inc. 12303 Airport Way, Suite 100 Broomfield, CO 80021
NON-DISCLOSURE NOTICE: This communication including any and all attachments is for the intended recipient(s) only and may contain confidential and privileged information. If you are not the intended recipient of this communication, any disclosure, copying further distribution or use of this communication is prohibited. If you received this communication in error, please contact the sender and delete/destroy all copies of this communication immediately.
— Reply to this email directly, view it on GitHub https://github.com/ForthHub/discussion/issues/92#issuecomment-1016757830, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA2OI3SEMTEM63F6B7BQESDUW4APHANCNFSM4VLGY4HA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
You are receiving this because you authored the thread.Message ID: @.***>