David, having done a number of things like this over the years, I would suggest that instead of Forth you consider Tiny BASIC as a starting point. It's not very efficient but it's very, very small. The interpreter probably wouldn't fit in a Cog but the runtime kernal would, and the interpreter could be written in (somewhat extended) Tiny BASIC.
Original TB stores line numbers in binary and the rest of the program in ASCII. There are 26 permanent variables named A-Z, and whatever memory is left over is devoted to a "vector" array addressible from !(0) to !(whatever). Strings are not supported. The math expression evaluator uses recursion to implement true precedence of operators and containing function calls with full expressions as arguments within expressions.
Once you get it running, you have a number of mostly very easy optimization paths.
* Add a tokenizer so you can use a tables instead of parsing keywords at runtime.
* Tokenize numeric constants
* Create a separate line number table and use binary search instead of linear scan to find jump targets
* or better, create jump tokens with space for an address to be pre-compiled in pre-runtime
* Add a string vector growing from the opposite end of space, with fixed length storage
* Add DIM and fixed variable storage eating away at the vector
* Add procedure names (still needing line numbers for the simple editor though)
* Static local variables of the internal form procname_varname if DIM is in a PROC
Most of this is trivially easy once you've understood and ported the original simple Tiny Basic interpreter, and can add up to a surprisingly capable development environment. Here is a version that adds strings very similar to the one I reverse engineered when I was a teenager:
Thanks for the suggestion but I have many languages I've written over the years that I will probably draw from if I end up doing this project. The most likely starting point is a language I called ebasic that already runs on the Propeller but isn't very fast. Changing its VM to PASM will probably fix that.
When you say "performance" do you mean execution speed of the finished program or the expressive power of the syntax/semantics and the much lauded interactivity.?
Or perhaps all of that?
Because...I have always assumed, perhaps wrongly, that the reason Forth manages to pack all that performance, in all the above ways, into such a small space is precisely because of it's stack based RPN syntax.
That is to say there is no other language that can do that, unless it looks and behaves much as Forth does.
It will be interesting to see what you come up with.
Actually, many languages are stack-based at runtime. It's just the parser that translates infix notation to stack operators. This was true of Pascal pcode as well as Java and Smalltalk bytecodes. I think some JavaScript interpreters actually compile to bytecodes on the fly as well. So I should be able to achieve the runtime efficiency of Forth from an infix language at the expense of a more complicated parser.
Yes many language are stack based at run time. Something like C can be compiled to run on a purely stack based machine. See zpu-gcc. The parser/compiler is the thing that gets you from code you can read to something that runs. The further the source code is away from a stack based machine the the bigger and more complex the compiler becomes.
Now, Forth is designed to be a minimally sized dev system, which is why it's source language is stack based. It makes for a minimal parser/compiler.
Hence my speculation that any language more readable than Forth will have a bigger parser/compiler. As you say "...infix language at the expense of a more complicated parser", i.e. bigger. The Forth syntax is not just a matter of taste in language style, it is required to achieve that minimalism.
Unless I have missed a point.
The question then is, how big a parser/compiler can we tolerate as we move toward a less headache inducing language.
Yes many language are stack based at run time. Something like C can be compiled to run on a purely stack based machine. See zpu-gcc. The parser/compiler is the thing that gets you from code you can read to something that runs. The further the source code is away from a stack based machine the the bigger and more complex the compiler becomes.
Now, Forth is designed to be a minimally sized dev system, which is why it's source language is stack based. It makes for a minimal parser/compiler.
Hence my speculation that any language more readable than Forth will have a bigger parser/compiler. As you say "...infix language at the expense of a more complicated parser", i.e. bigger. The Forth syntax is not just a matter of taste in language style, it is required to achieve that minimalism.
Unless I have missed a point.
The question then is, how big a parser/compiler can we tolerate as we move toward a less headache inducing language.
Yes, that is the question. I'm perfectly willing to add a SPI flash chip and use PropGCC XMMC mode. That would give me up to a megabyte for the compiler code. I'd still like to run the target code in hub memory though so it runs fast. I suspect others (maybe most others) will object to having to add a flash chip and sacrifice the pins it takes to talk to it. That may be the sticking point.
Heater, even with a PC hosting your development environment there's value in Forth for trial and error scripting. My hello world program on the Drawbot was done using a wireless link and entering commands to see how well they matched what I was looking for. To do the same thing for my card dealing robot I needed to write a gcode interpreter in C++ and solve some flow control issues. I used Forth for the scara arm's kinematic and it offers a similar level of interactive noodling without having to write a gcode interpreter.
So you have on the one hand a pile of data in gcode and a parser for that written in C++. On the other hand a pile of data in Forth commands and let Forth parse itself.
Sounds like a reasonable idea (interactive or otherwise).
Heater, even with a PC hosting your development environment there's value in Forth for trial and error scripting. My hello world program on the Drawbot was done using a wireless link and entering commands to see how well they matched what I was looking for. To do the same thing for my card dealing robot I needed to write a gcode interpreter in C++ and solve some flow control issues. I used Forth for the scara arm's kinematic and it offers a similar level of interactive noodling without having to write a gcode interpreter.
I think you described this before somewhere else but what is gcode?
As Heater says it is intended for CNC machines, but the motion of a robot arm is pretty similar so it seemed like a natural fit. As a language gcode consists of a g or m, followed by a numeric code, and followed by an argument. Usually the argument is an axis of motion (i. e. X, Y, Z, A, B, or C). For example G1 x0 y150 z20 means move the tool smoothly to that location. A G92 means move as quickly as possible. A g92 c90 would rotate about the Z axis.
It's really terse stuff, but more likely to be better thought out than anything I would come up with on my own. Plus I can use programs that generate CNC tool paths to control my robot arm.
(This is some 2D Gcode typical for a punching machine)
G90 G92 X20.000 Y20.000 'establish origin parameters, no transform
T301 'put tool number 301 into service
X4.500 'do something with tool 301 at this coordinate
X5.600 Y3.123 'do it again at this one
Y4.100
M04 'machine specific macro start or parameter input
T302 'put tool 302 into service
X 5.500
Y 2.541
etc...
There are commands for macros, patterns, tools, and coordinates and coordinate transforms along with machine parameters, wattage, tonnage, tools, speeds, feeds and so on.
Early on, controllers were expensive and they would operate on a block at most. A block is simply a command, such as a coordinate, or one of the T, G, M codes. Those controllers would literally read from paper tape, fetch it, do it, fetch it, do it, fetch it, do it, etc...
A "program loop" was a paper tape program actually taped with adhesive tape, to form a loop! That loop would run non-stop making parts over and over. I was kind of amazed to see it working so well when I did it in the 80's. (Many small manufacturers were using antiquated tech in the 80's for cost reasons.)
Over time, the increase in computer power led to controllers that could hold large programs in memory and offer more sophisticated macros, patterns and offer advanced features like interpolation, which can cut down on the number of G code expressions needed to describe curves for example.
Today, machine controls run advanced software and offer "on machine" development tools sufficient to program reasonably complex parts right at the machine, which is used for fixtures, one off type things regularly. These things are very powerful embedded designs.
So that's the machine control side.
On the computer side of things, the minimum was typing things into a controller that had enough capacity to offer that kind of thing. Most of the parts I made early on were done exactly that way. Work it all out, walk up to the machine, type it in and go! Programming systems would offer a text editor of some kind, paper tape read / write machine, and a plotter to verify a tool path before actually running it on the machine. Primitive stuff, and something a P1 could offer right now.
Then software advanced as did computers overall and we got visual programming that worked off CAD geometry, which really improved things, making very complex parts viable. In tandem with that we started to get CNC simulation too where a model of the CNC machine is manipulated to show potential collisions as well as verify the model of the part is representative and that the tool path makes sense in that context.
Today VM technology is being used to simulate the entire machine! The VM runs the machine controller code and the physics of the machine tool itself are modeled so that the simulation can not only verify, but answer "what if?" types of questions mostly related to advanced high speed machining or robotic control that approaches the safe, accurate limits of the devices in question.
I just got to see one of these systems deployed and it's impressive! So is the computer at the engineers desk.
David, I should have included this link earlier. The Wikipedia article on threaded code actually looks decent. It may not be of use or interest to you, or perhaps you've already seen it, but I thought I should mention it in this context at any rate.
tell me how Forth manages memory.
...
What happens if I redefine a word?
...
Is the old definition removed and the memory that it occupied reclaimed or does the new definition just shadow the old definition?
typically, FORTH uses a variable called 'here' that hold the address of the next free (unallocated) location in memory. Beyond that, you arre free to do what ever you need to do.
Making a new definition means all subsequent call to that name will get the newest version. All words defined before the new definition will of course continue to reach the previous definition, as that is already compiled. This is a primative type of "operator overloading" except it came about before the term operator overloading was coined (if I recall correctly) and can be used with any definition.
In propforth, there is a word "saveforth" which save the current state of RAM to EPROM. Next time you reboot, the current state of the dictionary is restored, complete with any redefinitions, and you can 'forget' the most recent definition to reach the previous one. Forget releases memory by taking the start address of the word you are forgetting, and puts that in 'here'. Anything after the forgotten word is also forgotten.
Propforth has a routine "spinmaker" which is used in rebuilding the dictionary. It takes all the currently visible definitions, and creates spin code for them. The affect is that the only the most recent (i.e. visibile) definition for each word is kept. If you went through several iterations of a word and like to keep the last one, this is one way to do it. But this is usually done with Application level words, if you go redintining primatives like + or @ you might get wacky results.
Okay, now I'm going to run into trouble with the Forth enthusiasts. The reason I've been asking how Forth handles memory is that I'm investigating the idea of building a more traditional infix language that has some of the efficiency advantages of Forth but with a more familiar syntax. One big problem I have with other languages I've written is that they mostly use heap-based memory managers that tend to take up more memory and also involve complicated code to maintain. If I could use a simpler symbol table and object storage scheme then I could reduce significantly the code and data space requirements. I feel as though one of the biggest advantages of Forth is it's interactivity. I want that but with a more traditional syntax.
You won't necessarily get into trouble with forth enthusiasts, you are free to do what ever works and it cool. (And we will borrow it if it is cooler than the existing stuff, this is tradition). Problem is may come when you do infix, you hanve to do a whole bunch of extra stuff (like heap based memory management etc) the eats all the memory space. Most (or many) early words in teh forth dictionary take 8 to 14 bytes, application words take a few more. The challenge is keeping the definitions small and therefore simple, can you do infix and keep it simple? So far, the answer has been, sure, but it takes so much space to continue with RPN, and we usually need the extra space for applications. If you have a honkin big system with exessive memory, like an 8086 PC, you can easily use FORTH to implement an interactive C environment. But there are not many examples (that I know of) of forth implemntation of interactive C on microcontrolers with limited memory. It seems that "small enough" and "RPN" go together, at least so far. Which is not to say it can't be done, you are very knowledgeable and may figure out and elegant solution.
David, I should have included this link earlier. The Wikipedia article on threaded code actually looks decent. It may not be of use or interest to you, or perhaps you've already seen it, but I thought I should mention it in this context at any rate.
Thanks for the reference. I used to have a bunch of books about Forth and threaded languages but I sent them all to Dave Hein. :-)
You won't necessarily get into trouble with forth enthusiasts, you are free to do what ever works and it cool. (And we will borrow it if it is cooler than the existing stuff, this is tradition). Problem is may come when you do infix, you hanve to do a whole bunch of extra stuff (like heap based memory management etc) the eats all the memory space. Most (or many) early words in teh forth dictionary take 8 to 14 bytes, application words take a few more. The challenge is keeping the definitions small and therefore simple, can you do infix and keep it simple? So far, the answer has been, sure, but it takes so much space to continue with RPN, and we usually need the extra space for applications. If you have a honkin big system with exessive memory, like an 8086 PC, you can easily use FORTH to implement an interactive C environment. But there are not many examples (that I know of) of forth implemntation of interactive C on microcontrolers with limited memory. It seems that "small enough" and "RPN" go together, at least so far. Which is not to say it can't be done, you are very knowledgeable and may figure out and elegant solution.
I don't intend to implement an infix language in Forth. Rather, I hope to take a few good ideas from Forth and use them to make an infix language. It will, of course, be bigger than Forth. The question is, will it be small enough to fit on the Propeller without having to resort to external memory. It seems people (including Parallax) are reluctant to use external memory in Propeller projects.
I don't intend to implement an infix language in Forth. Rather, I hope to take a few good ideas from Forth and use them to make an infix language. It will, of course, be bigger than Forth. The question is, will it be small enough to fit on the Propeller without having to resort to external memory. It seems people (including Parallax) are reluctant to use external memory in Propeller projects.
At least in the case of propforth, it was determined that once we go to external memory, size and speed advantages are forfeit. Also, the resources consumed for parallel I/O leave little for applications. The trade off was SD memory, its cheap, big, faster than the prop's i/o channel, and easy to implement and use. When we allocate the SD transfer to the "inbetween times" and load appropriate sized scripts or precompiled assembly routines, we can get max execution speed as long as we remain below the prop internal memory size for any give function. And we can have the utilmate application as big as the current SD. Turns out its not been difficult to work within these constraints. We try the do things that will fit on a uC in the first place, so we might be imposing artificial limits
You might want to check out the PF6 built automation when its ready, it makes it fairly transparent to rebuild and test the kernel. That might be a good way to figure out what you want to borrow and how it works.
You can add a SPI flash chip using the same number of pins that you use for an SD card. In fact, you can share the DI/DO/CLK pins with the SD card if you want. You don't have to use a lot of pins for a parallel interface to external memory.
Comments
By the way, "Stack Computers" by Philip Koopman is freely available online. It might give you some insights/ideas to help with your project.
Now, Forth is designed to be a minimally sized dev system, which is why it's source language is stack based. It makes for a minimal parser/compiler.
Hence my speculation that any language more readable than Forth will have a bigger parser/compiler. As you say "...infix language at the expense of a more complicated parser", i.e. bigger. The Forth syntax is not just a matter of taste in language style, it is required to achieve that minimalism.
Unless I have missed a point.
The question then is, how big a parser/compiler can we tolerate as we move toward a less headache inducing language.
So you have on the one hand a pile of data in gcode and a parser for that written in C++. On the other hand a pile of data in Forth commands and let Forth parse itself.
Sounds like a reasonable idea (interactive or otherwise).
It's really terse stuff, but more likely to be better thought out than anything I would come up with on my own. Plus I can use programs that generate CNC tool paths to control my robot arm.
To add to the other answers, G-Code (Gerber) is a subset of EIA RS-274D:
http://en.wikipedia.org/wiki/Gerber_format
A page describing some popular codes:
http://www.timgoldstein.com/cad_cam/rs274.htm
c (Joe Gerber used to be my boss
Jim
(This is some 2D Gcode typical for a punching machine)
G90 G92 X20.000 Y20.000 'establish origin parameters, no transform
T301 'put tool number 301 into service
X4.500 'do something with tool 301 at this coordinate
X5.600 Y3.123 'do it again at this one
Y4.100
M04 'machine specific macro start or parameter input
T302 'put tool 302 into service
X 5.500
Y 2.541
etc...
There are commands for macros, patterns, tools, and coordinates and coordinate transforms along with machine parameters, wattage, tonnage, tools, speeds, feeds and so on.
Early on, controllers were expensive and they would operate on a block at most. A block is simply a command, such as a coordinate, or one of the T, G, M codes. Those controllers would literally read from paper tape, fetch it, do it, fetch it, do it, fetch it, do it, etc...
A "program loop" was a paper tape program actually taped with adhesive tape, to form a loop! That loop would run non-stop making parts over and over. I was kind of amazed to see it working so well when I did it in the 80's. (Many small manufacturers were using antiquated tech in the 80's for cost reasons.)
Over time, the increase in computer power led to controllers that could hold large programs in memory and offer more sophisticated macros, patterns and offer advanced features like interpolation, which can cut down on the number of G code expressions needed to describe curves for example.
Today, machine controls run advanced software and offer "on machine" development tools sufficient to program reasonably complex parts right at the machine, which is used for fixtures, one off type things regularly. These things are very powerful embedded designs.
So that's the machine control side.
On the computer side of things, the minimum was typing things into a controller that had enough capacity to offer that kind of thing. Most of the parts I made early on were done exactly that way. Work it all out, walk up to the machine, type it in and go! Programming systems would offer a text editor of some kind, paper tape read / write machine, and a plotter to verify a tool path before actually running it on the machine. Primitive stuff, and something a P1 could offer right now.
Then software advanced as did computers overall and we got visual programming that worked off CAD geometry, which really improved things, making very complex parts viable. In tandem with that we started to get CNC simulation too where a model of the CNC machine is manipulated to show potential collisions as well as verify the model of the part is representative and that the tool path makes sense in that context.
Today VM technology is being used to simulate the entire machine! The VM runs the machine controller code and the physics of the machine tool itself are modeled so that the simulation can not only verify, but answer "what if?" types of questions mostly related to advanced high speed machining or robotic control that approaches the safe, accurate limits of the devices in question.
I just got to see one of these systems deployed and it's impressive! So is the computer at the engineers desk.
typically, FORTH uses a variable called 'here' that hold the address of the next free (unallocated) location in memory. Beyond that, you arre free to do what ever you need to do.
Making a new definition means all subsequent call to that name will get the newest version. All words defined before the new definition will of course continue to reach the previous definition, as that is already compiled. This is a primative type of "operator overloading" except it came about before the term operator overloading was coined (if I recall correctly) and can be used with any definition.
In propforth, there is a word "saveforth" which save the current state of RAM to EPROM. Next time you reboot, the current state of the dictionary is restored, complete with any redefinitions, and you can 'forget' the most recent definition to reach the previous one. Forget releases memory by taking the start address of the word you are forgetting, and puts that in 'here'. Anything after the forgotten word is also forgotten.
Propforth has a routine "spinmaker" which is used in rebuilding the dictionary. It takes all the currently visible definitions, and creates spin code for them. The affect is that the only the most recent (i.e. visibile) definition for each word is kept. If you went through several iterations of a word and like to keep the last one, this is one way to do it. But this is usually done with Application level words, if you go redintining primatives like + or @ you might get wacky results.
You won't necessarily get into trouble with forth enthusiasts, you are free to do what ever works and it cool. (And we will borrow it if it is cooler than the existing stuff, this is tradition). Problem is may come when you do infix, you hanve to do a whole bunch of extra stuff (like heap based memory management etc) the eats all the memory space. Most (or many) early words in teh forth dictionary take 8 to 14 bytes, application words take a few more. The challenge is keeping the definitions small and therefore simple, can you do infix and keep it simple? So far, the answer has been, sure, but it takes so much space to continue with RPN, and we usually need the extra space for applications. If you have a honkin big system with exessive memory, like an 8086 PC, you can easily use FORTH to implement an interactive C environment. But there are not many examples (that I know of) of forth implemntation of interactive C on microcontrolers with limited memory. It seems that "small enough" and "RPN" go together, at least so far. Which is not to say it can't be done, you are very knowledgeable and may figure out and elegant solution.
At least in the case of propforth, it was determined that once we go to external memory, size and speed advantages are forfeit. Also, the resources consumed for parallel I/O leave little for applications. The trade off was SD memory, its cheap, big, faster than the prop's i/o channel, and easy to implement and use. When we allocate the SD transfer to the "inbetween times" and load appropriate sized scripts or precompiled assembly routines, we can get max execution speed as long as we remain below the prop internal memory size for any give function. And we can have the utilmate application as big as the current SD. Turns out its not been difficult to work within these constraints. We try the do things that will fit on a uC in the first place, so we might be imposing artificial limits
You might want to check out the PF6 built automation when its ready, it makes it fairly transparent to rebuild and test the kernel. That might be a good way to figure out what you want to borrow and how it works.