On Thu, 13 Jan 2011, Byron Jeff wrote: > On Thu, Jan 13, 2011 at 11:12:03AM -0500, smplx wrote: >> >> >> On Thu, 13 Jan 2011, Byron Jeff wrote: >> >>> On Thu, Jan 13, 2011 at 08:36:15AM -0500, smplx wrote: >>>> >>>> Ok, just a couple of thoughts. >>>> >>>> Yes using a mixture of tokens and absolute addresses sounds good. Howe= ver >>>> I would forget about using a bit in the token to distinguish between t= he >>>> two as this means you lose half your tokens and half your address spac= e >>>> AND you increase the runtime overhead by having to decide which you ar= e >>>> decoding every time. >>> >>> Somewhat good points. Actually the half an address space isn't lost bec= ause >>> the architecture only has a 15 bit address space. So 7 bits from the to= ken >>> + 8 bits from the next fetch =3D 15 bits. >> >> Two points here though: >> >> (1) I assumed you wouldn't want a 15 bit address space limit hard coded >> throught your VM > > For this one, yes. The VM is tied to the architecture, which is limited t= o > 15 bits of program memory. If you move chips, you recode the VM and port > the source to the new VM. Being able to run encoded apps on different chi= ps > isn't in the design specification list. > >> (2) I assumed you'd have some way of encoding 16 bit integers directly >> into your forth programs. > > That's an issue that's orthogonal to the encoding of the subroutines. But > it is certainly worth discussing. > > Integers are put into the stream using a routine called LIT (for literal)= .. > The routine is followed in the stream by the literal to be pushed on the > stack. So something along the lines of: > > 3 4 + > > is encoded as > > LIT 3 LIT 4 + > > and one for a 16 bit one: > > LIT16BIT > > > Actually with the exception of integers, that is not the FORTH way of > doings things. What is done instead is the data (or addresses to the data= ) > is pushed on the stack where routines operate on them. FORTH thinking is = a > zero parameter subroutine system. So parameters are not encoded after the > routine. Take a simple example of printing a string. In a typical languag= e > there would be: > > print "the string to print" > > So in the VM the thought would be: > > PRINTTOKEN > > But FORTH is postfix all the way. So the implementation is: > > PRINTTOKEN Actually C does it the same way. It pushes all the actual parameters of a function onto the runtime stack and then calls the subroutine coressponding to the function. > > The "something about the string on the stack" are some combination of > integers such as the address of the string and its length. At the end of > the day it ends up being pushes of integers on the stack. That's already > implemented. So we're done without having the tack something after the > PRINTTOKEN. Exactly how a C compiler would do it. It allocates space for the string somewhere else and passes the address on the stack to the function. But actually embeding the string after the function call in the VM would be more efficient from a space viewpoint as you don't need to pass the address of the string, you already know where it is :-) > > The rationale for this comes in the simplicity of the compiling system fo= r > FORTH. It's so simple that even a 12F1822 with 2K of program memory and 1= 28 > bytes of RAM can implement it. Simply this: > > 1) Get a word (space separated string of characters) > 2) Look up the word in a dictionary converting it to an address > 3) Write the address in the next available space. > > Rinse and repeat. > > Now with infix with parameters, you need a parser to figure out what > follows something so that you can attach it properly. But in FORTH each > word stands alone and can be processed separately without regard for > anything that comes after. So both parsing and conversion are trivial. > > The "magic" that makes FORTH work is a set of words that will execute eve= n > when the system is in compiling mode. They are known as immediate words. > Strings are an example. When a word for a string (." or s") is encountere= d, > instead of just looking up the word and compiling it, like above, the wor= d > is executed instead. So it can do some special compiling stuff that the > normal process cannot handle such as reading the string, copying it anoth= er > location, then compiling the address and size of the string so that it is > pushed on the stack. So while the source may look like: > > s" my string to print" printme > > the VM code is: > > LIT16BIT LIT8BIT PRINTME > > because s" runs a subroutine instead of just being compiled. > > s" isn't special other than its immediate nature. So it can actually be > written in FORTH. > Yes I understand what you're saying: the parser is incredibly trivial. However it still needs to be able to tell the difference between numbers and words, to generate "LIT " inline for a number and to lookup the token coressponding to a word in the dictionary and generate inline for that word. So how much extra work is there in checking that is greater than 8 bits wide and instead generating "CALL " (where is the 16 bit address of the subroutine coressponding to ) Yes I understand that pushing everything is the way forth does it but you are not restricted to doing it this way. The parser overhead is tiny. It's still only working on one symbol at a time. It's not looking at combinations of symbols. >> >>> >>> Finally extending the token set does not seem to make much sense either >>> since it'll take 2 bytes for extended tokens and in 2 bytes you can hav= e >>> access to any absolute address. >> >> If you do decide to stick with pure 8 bit only tokens, consider the Z80'= s >> trick of having prefix instructions to modify the meaning of subsequent >> instructions. So you could have one token that changes the behaviour of >> the next token or tokens > > To what advantage? Tokens only advantage are space savings. I think that > it's a worth debate if any time is saved. I may have to code it up to see > the actual timings. > > Once a token is extended beyond 8 bits, it looses any advantage it may ha= ve > had. All routines can be accessed directly via their address, which take > two fetches. So if dealing with tokens takes two fetches, then there's no > reason to have them. Simply substitute the direct address instead of the > token. Well no actually there are other advantages to using tokens. If you have an interpreter executing the tokens rather than direct addresses of the subroutines, you can move the subroutines around, print out the program in meaningful form, execute it from non-program memory (well part of it anyway), edit individual subroutines without recompiling everything... I'm sure that there are other advantages, these are just off the top of my head. > > I look at tokens as a type of Huffman encoding scheme. Presume that > processing a token and a direct address takes about the same amount of ti= me > (I have to do this because I haven't yet done the actual timings). A toke= n > takes half the space of the direct address. So half the space and the sam= e > execution time is a win especially when heavily used routines are > tokenized. So if you're talking about Huffman encoding then stuff that occures most often or executes most often should be represented in the least number of bits and stuff that occures least often or executes least often is represented in far more bits. This is exactly what using prefix instructions would allow you to do. Say you had an 8 bit VM instruction to push a constant to the evaluation stack. Lets say the instruction looked like: 0x8n where is the 4 bit constant in the range 0 to 15 As you noted elsewhere programs tend to use small constants a lot. now lets say once in a while you actually wanted to push an 8 bit constant. You might "extend" your VM instruction with a prefix instruction like: 0x9m now when the VM sees 0x9m 0x8n it actually pushes the 8 bit constant onto the stack. This is how the old transputer actually works - it actually had a 3 level eveluation stack and 8 bit instructions. >>> BTW I have a design goal of running threads out of RAM so that temporar= y >>> words can be written and tested in RAM before being committed to flash. >> >> Yes I understood you wanted to be able to execute your VM code from RAM. > > But I need to think through if that is a worthy goal or am I simply > pressing my own expectations as this design goal. Well don't forget the possibility of executing code out of an external EEPROM. > > Forth is designed as an interactive "noodling" system with immediate > interactive debugging. Type a list at the prompt and it immediately > executes. This does cause some issues in terms of immediate words which a= re > designed to execute only in the compiling environment. > > I have it in my head, rightly or wrongly, that there should be an > opportunity to define and use temporary words and test them out before > final committment. That's what driving this design goal. > > But maybe it's the wrong approach. It would be possible to write, revise, > and erase words in program memory without affecting anything else as long > as each word started on a row boundary. Of course there would be wasted > program memory. But on the other hand, program memory is the most abundan= t > resource available. > > I'm wavering on MOVLB that would still be required for each call though. > Every call would require two memory locations, whereas a mix of tokens an= d > addresses would be the average between one and two words per call. But I > guess that with some optimization, the number of MOVLB's required could b= e > reduced. > > It's almost looking like there needs to be a development runtime that is > interactive and a compacted, compiled runtime that uses straight subrouti= ne calls and > takes the time to reorganize the list of routines to minimize the number = of > MOVLB calls that are required to implement all of the words. > > Wanting to execute from RAM actually complicates the system. I'm not sure > that is the best move. So are you saying you want to be able to have this thing self hosting? Do you intend to just attach a keyboard and display to it and enter code directly? If so, what happens when the programmer screws up and overwrites part of the OS? Regards Sergio Masci =3D=3D=3D Do NOT send emails to this email address directly. This email address is only valid for the PICLIST. Anything else gets dumpped without me ever seeing it. -- http://www.piclist.com PIC/SX FAQ & list archive View/change your membership options at http://mailman.mit.edu/mailman/listinfo/piclist .