Meta-Language

The "language" proposed here is a type of real time state machine or token interpreter which is targeted at pattern matching and translation using a variation of the BNF grammer. Other examples are CUMP Byte Code, and Minimal Controller Idea.

Examples

| "when you see this" ? "output this" .

| "or change this" ? "into this" .

| @Timer "12:00:00" ? "Good Morning!" @Day = Day + 1 .

| @Comment "This is a comment, it will be copied to the bit bucket" .

to get the current exchange rate with Italy:
@http://www.x-rates.com/htmlgraphs/ITL30.htm 'current rate: ' number ? 'Our exchange rate with Italy is ' number .

to translate written text to numbers. "one-two" becomes "1-2" The ":" word causes the OutBuffer to become a local buffer so that the digits that are matched are placed in a local holding area. When digit is referenced after the "?" word, the InBuffer is redirected to that local buffer. Each call to digit adds or removed one entry from the local buffer so that more than one digit can be matched in a single pattern.

| digit '-' digit ? digit '-' digit

Word Description

The idea of very small, punctuation type words rather than english keywords is not commonly seen in programming languages. Years ago, I wondered why the punctuation marks in standard english text were of no use. The Bitscope Command Set is a brilliant example of the application of punctuation to small programming languages. Compair this to the Oricom ICTC command set, NPCI or the PICos commands. CUMP Byte Code, and Minimal Controller Idea are other attempts. Meta-L tries to use the same meaning of punctuation symboles from human text in program code. "(" and ")" denote a comment rather than a memory reference.

Each word address is expected to point to a machine language command (i.e. the "interpreter" just jumps to the code at that address) and that command can be a call (or more likely a software interrupt or "restart") that invokes the interpreter with the address of the word on the stack which will  point to the addresses that make up the word.

Rather than using word addresses, we can use a single byte "token" or index to a memory address in a table. To increase the number of available subroutines past 255, some of the routines can implement their own jump table and fetch the value of a second byte following their own token in the code to use as an index in their own table. This process can be repeated as often as needed.

To improve performance, the current thread IP can be held in a register (vice on the stack) and can be pushed to the stack when a new thread is started by the interpreter.

Instead of a conditional word like MATCH popping its thread to fail to the next entry, Just set the CY flag and return to FailTo which will then Jump to the next entry (if CY=1) or return (popping the FailToPtr) to the Parent (if CY=0) when a simple TRet is encountered indicating success at the end of a series of trials.

The following example assumes that the inbuffer contains "good"

TRet ;FailtoRun drops <addr> and returns

Memory Allocation for Buffers

By default, Buffers are initialized as small memory areas (16 bytes) just after their name entries in the dictionary. The pointer compiled into new code that references this buffer will point to the length byte following a pointer to the method used to refill or empty the buffer (see figure 2) If the length is zero, or insufficient for the required operation, the method requesting access to the buffer should call the pointer to the buffers method with a "fill with x bytes" message sent, this will return a pointer to the filled buffer (not necessarily at the original address) with a new length indicating the actual number of bytes now in the new buffer. The method is responsible for interpreting the rest of the data in the buffer. For example: A dynamic method will take the next byte in the buffer as a chunk pointer (and see zero,zero as meaning that there is no data and no chunks) but a virtual pointer will look for a cache len byte or zero followed by a cache chunk pointer. This system allows binary data to be stored without escapes via the length byte, but switches to a zero terminated string of pointer or other data when the length byte is zero. Also, the original pointer to the buffers length byte should not be confused with a buffer pointer (which would point not to a length byte but rather to a position in the data of the buffer).

Memory image of various buffer types

[(match)<len)(buffername)](bufdef)(token)(startthread)(method	static)(buffer len:byte=[1...255])(buffer data:15 bytes)
	dynamic)(byte=0)(chunk pointer)[(chunk pointer)](byte=0)
	virtual)(byte=0)(cache len)(cache:14bytes max) or (byte=0)(byte=0)(cache chunk pointer)(byte=0)
	file)(byte=0)(handle len)(handle/zero if not open)(url len)(url)(offset len)(file offset)(cache chunk pointer)

After a static buffer is filled with 15 bytes of data, its method can be called to "make room" at which time, the static method will be replaced with a dynamic method and a chunk allocated, the original data moved to it, a chunk pointer inserted in the buffer, and the length changed to zero. If the dynamic buffer is not often accessed and free chunks are no longer available, the chunk allocator may replace the dynamic method with a virtual method and move the data to a disk file.

It should be kept in mind that all the program code, data, dictionary etc.. that make up the system must also be contained in buffers. Match, fail, Outbuf must all take into account the number of bytes left in the current In and Out buffers and break up output / repeat input operations accordingly. All programs will basically be paragraph aligned to simplify memory management.

Buffers Length

 Buffers have no maximum length but are processed in 255 byte chunks. The first byte in a buffer contains its length. As the buffer exceeds 255 bytes an additional index chunk is added that tracks the number of 255 byte chunks that are contained in the buffer, An invalid byte length value (255, or zero for easier testing with zero,zero reserved to flag buffers that need to be refilled) at the start of this new chunk acts as a flag that this index chunk is present. All the bytes in the index chunk point to other chunks. When the buffer exceeds 255 chunks of 255 bytes of 64k of data, the next "meta" index chunk is added indicating one full chunk chunk of data. There are 256 chunks in a segment.
 Note that with this system, it is entirely legal to delete part of a chunk without having to move the entire file. I.e. we do not have to fill each chunk completely.
 With 14 bytes of data for chunk references, a single small (16 byte) buffer entry in the dictionary would allow access to 255*14=3570 bytes of data without calling a method and using only two buffer pointers; one to the small buffer data to select the chunk pointer and one to select the byte in the chunk pointed to. By increasing the number of levels of index chunks, any amount of data can be stored.
 To optimize for buffers that are normally accessed sequentially (and remove the need to store the index chunk in ram which may be critical in embedded implementations) could buffer data be combined with pointers in one chunk? e.g. (byte=0)(chunk pointer)(byte=0)(length byte)(data)

in	of memory there are:	each containing:	which can be selected by a pointer of:
4GB	4G bytes	1 byte	32 bits
4GB	16M chunks	256 bytes
4GB	64k segments	65536 bytes	16 bits
1MB	1M bytes	1 byte	20 bits
1MB	4096 chunks	256 bytes
1MB	16 segments	65536 bytes	4 bits
640KB	2560 chunks	256 bytes
640KB	10 segments	65536 bytes	4 bits
64KB	64k bytes	1 byte	16 bits
64KB	256 chunks	256 bytes	8 bits
64KB	2048 buffer entries	about 32 bytes

Chunk Pointers

 To access an unlimited amount of memory without allocating an unlimited sized address pointer, we can use very small relative pointers that are combined by having the first pointer point to a second pointer that points etc.... when needed to reference more distant memory.
 One problem with this approach is that when an area of memory becomes completely used, no second pointer may be available within range of the first. To reduce the risk of this occurring, the meaning of the pointers can be changed to allow some values to point to distant memory while others point to local memory with greater granularity. For example, rather than interpret successive values of a pointer as successive local chunks, cause every other value to point to a chunk in another segment. Ideally, most values would still point to local chunks distributed evenly (every other or every 4th etc..), a smaller number of values would point to chunks less local and still a smaller number of values would point to chunks still farther away until finally only a very few values would point to chunks very far away.
 The system of value interpretation selected is as follows: shift the chunk pointer left by the number of bits indicated by the lower 2 bits of the chunk pointer themselves shifted left one and add to the result the original lower two bits. This should be easily implemented in most processors with a register A to register B copy, bit mask register B (and with 0FCh), shift register A left by register B value, shift register A left by register B value (again), and an add register B to register A. An A86 macro has been developed. The following is an illustration of the chunks that can be referenced from a chunk pointer relative to any given chuck that contains the pointer via this interpretation:

Each line of pixels represents one segment (256 chunks of 256 bytes or 64k bytes) and each column represents one chunk with in that segment.
 The illustration was generated with a simple QBASIC program which also prints a list of address offsets in order generated from chunk pointer value and sorted by offset value with distance between offsets. A few chunks almost 16k chunks or 4M bytes away and about every 4th chunk in the local segment can be referenced. This is comparable to the x386 index*scale addressing mode.
 A second problem with this approach is that each time a new level of pointers is added, space to store the current value of the pointer must be allocated. Since all pointers are being mapped to the physical addresses in the machine (e.g. an index register), we are certainly aware that some actual upper limit on the address will be reached, however we do not wish to impose this limit in the structure of the language but only in the actual implementation on a specific machine.

Chunk Allocation

We can specify that some number of chunks be used to hold free/allocated information in each byte rather than a chunk pointer. One chunk per segment suffices if each chunks free / allocated values are limited to 255. Each method that allocates a chunk must select the related byte in the index and increase its value if it is not already 255. For simplicity, it would seem to be best to combine this system with a system for tracking frequency of  chunk access for virtual memory management. If we take the value 0 to indicate availability, allocating a new chunk would consist of:

1. point to the index chunk of the local segment
2. scan for a zero value in a byte related to a chunk that can be pointed to from the chunk we are adding to, if not found, repeat with each segment that can be referenced by the chunk we are adding to until no segments are available, then call the virtual memory manager to dump to secondary memory the least used chunk from the set to which we can point.
3. change the value of the index byte related to the chunk to be allocated from zero to one
4. compute and add a chunk pointer to the new chunk
   

Virtual Buffers

 As buffers grow to large sizes, it may be necessary to move less frequently used parts (chunks) of the buffer to secondary memory (hard disk). This implies the following.

1. We must track which chunks are used less frequently
2. We must allocate a file on the disk and track which chunks are stored in it and where they are in the file
3. When a chunk that is not in memory is needed, some mechanism must retrieve it from the file.

 One solution may be to convert the memory buffer to a file buffer and then keep track of the chunks that are in cache. We can specify that some number of chunks be used to hold access count information in each byte rather than a chunk pointer. One chunk per segment suffices if each chunks access count is limited to 255. Each method that accesses a chunk must select the related byte in the index and increase its value if it is not already 255. It should be noted that we wish to remove first groups of chunks pointed to by index chunks (because the overhead required to track the position of the removed chunk is probably greater than the space that would be released by the removal of one chunk) that A) do not contain data often needed and B) are not index chunks themselves that are used to get to data that is often needed. Also, while the relationship between index chunks that point to infrequently used data is related to the structure of buffers, it is entirely possible that one part of a buffer will be constantly in use while another part of the same buffer is never used after its initial allocation.
 For simplicity, it would seem to be best to combine this system with a system for tracking unused chunks. See Chunk Allocation elsewhere.
 When the virtual memory manager is called to free space:

1. scan through the segment index chunks for each available segment to find the lowest access count value greater than zero of a chunk index.
2. verify that the chunks pointed to in the selected chunk index are not frequently used
3. copy all the chunks pointed to by the index chunk to secondary memory, change their segment index chunk byte value to zero (marking them as free), and place a reference to the location in the index chunk after a zero length value and a method token for virtual memory reloading. This assumes that the code reading the chunks will know to call the method after the zero byte (rather than before the zero length byte as in a buffer) when it encounters an index chunk (first byte 255) with no chunk pointers or a chunk with a zero length.
   

 In the case that only one chunk referenced in a chunk index is repeatedly called when all the other chunks are never used; if we only increment the chunk usage count for the index chunk when we shift from one chunk to the next - since the count will remain low for the index there is a better chance that it will be selected to page out (good) and if the high usage count for the high usage chunk is noted when the indexed chunks are being processed, perhaps the index chunks can be reorganized so that the high usage chunk is moved to a different index. For example a buffer with only one commonly used chunk could end up with chunk pointers to index chunks that are all paged out followed by one chunk pointer directly to the we want to keep handy followed by more chunk pointer to paged out index chunks. Actually all the paged out chunks should be combined into one paged out index chunk before the commonly used chunk and one other after it. This results in only 3 chunks and the buffer area as the worst case minimum memory usage for any size buffer where only one chunk is really needed.

Buffer list

Normally the buffer list would be spread out through memory as new buffers are created in the dictionary and old buffers are destroyed with matches and fail-to's used to search the list. But if the buffers list was rearranged in order by swapping around fail-to pointers so that the last buffer used was always moved to the first position in the list and if the last position in the list was quickly accessible (maybe the XOR linked list pointer could be adapted, this would provide two benefits as the buffer list would sort itself in the most often used to least often used order over time

1. the chance of finding the buffer you need closer to the top of the list increases and
2. the buffer at the end of the list is probably the best candidate for swapping out to virtual memory.

Persistent Buffers

Buffers with a persistent method will be saved to NVM when the system receives a power off interrupt or constantly in a background process.

Stack

In order to continue the theme of unlimited size, the stack must be implemented as a buffer which can be upgraded to a virtual method handler. The chunk allocator should know that chunks buried on the bottom of the stack are less likely to be needed that chunks near the top.

Records / Tables

If the name of the buffer contains a '.' dot, the name before the dot is taken to be a table name and the name after the dot will refer to a field in that table. Operators to select records by key value, relative or absolute record number and to add new or delete old records.

Arrays / Indexed Tables

If the name of a buffer (field or table) ends in a [key], the buffer is taken to be an indexed array. The key value is used to find an individual element or record in the buffer and can be any text (Refer to JavaScript arrays)

Sequential File System

In order to simplify the sequential reading of data that is normally accessed serially, we can modify the normal index chunk system to also include a "streaming" linked list where each chunk pointer to the next chunk of data is stored at the end of the current chunk and is logically XOR'd with the address of the previous chunk so that the sequence can be traversed backwards or forwards.

Directory Chunk (each memory device must have one at a known starting place)

File: array of FileHeader

FileHeader

file number
starting chunk
ending chunk
length (chunk count and bytes used in last chunk)

DataChunk

method/file number (for redundancy)?
data
chunk link

OpenFile (in ram, like a fcb)

file number
chunk pointer
previous chunk pointer
cache

See also:

• Randy Hyde's UCR Standard Library
  • Pattern Matching
• Randall Hyde's Pattern Matching Routines for Delphi
• Alien's Define
• http://www.rebol.com/rebolsteps.html

See:

• /techref/language/asp/ix/ixfildll.htm

  .