Fun with opcodes

"If I were to implement a language now, I'd write a very minimal core suitable for bootstrapping. ... Think of a handful of ops. Think very low level. (Think something a little higher than the universal Turing machine and the lambda calculus and maybe a little bit more VMmy than a good Forth implementation, and you have it.) If you've come up with something that can replace XS, stop. You're there. Do not continue. That's what you need." (Chromatic, January 2013) 

In September or October I started thinking about that, and began to play with a tiny interpreter written in Perl that processed a rather loose version of Lua opcodes.

Lua includes a register-based virtual machine (VM) and has a uniquely light-and-performant driven view of interpreters.  Using Perl to implement a sort-of Lua VM opcode interpreter let me play with the concepts without having to really write very much, because Perl is nothing if not excellent at tokenizing strings and tearing apart text.

Here's the core loop.


my %R   = (); # registers
my %K   = (); # constants
my %U   = (); # "upvars"
my $PC  = 0;  # program counter
my $FPF = 0; # ???

my @prg = <DATA>;

while( $PC < @prg )
{
   my $line = $prg[ $PC ];
   my ($opcode, $a, $b, $c, $d) = split ' ', $line;

   $PC++;
  
   next unless $opcode;
  
   given( lc $opcode )
   {
      when (/ffd2/)         { print $R{$a}; print " " if $b eq '\s';  print "\n" if $b eq '\n' }
      when (/nl/)            { print "\n" }
     
      when (/clr/)          { $R{$_} = '' for $a .. $b }
      when (/move/)          { $R{$a} = $R{$b} }
      when (/loadk/)         { $R{$a} = $b     }
      when (/loadbool/)        { $R{$a} = $b? 1 : 0; $PC++ if $c }
      when (/loadnil/)        { $R{$_} = 0 for $a..$b }
      when (/getupval/)     { $R{$a} = $U{$b} }
     
      when (/gettabup/)     { $R{$a} = $U{$b}->{ $c } }
      when (/gettable/)     { $R{$a} = $R{$b}->{ $c } }
     
      when (/settabup/)     { $U{$a}->{ $b } = $R{$c} }
      when (/setupval/)     { $U{$b} = $R{$a} }
      when (/settable/)     { $R{$a}->{$b} = $c }
     
      when (/newtable/)     { $R{$a} = {} } # size = B,C
     
      when (/self/)         { $R{$a+1} = $R{$b};
                              $R{$a} = $R{$b}->{$c} }
                       
      when (/inc/)            { $R{$a}++ }
      when (/dec/)            { $R{$a}-- }
      when (/bz/)           { $PC += $b unless $R{$a} }
      when (/bnz/)          { $PC += $b if     $R{$a} }

      when (/add/)          { $R{$a} = $b + $c }
      when (/sub/)          { $R{$a} = $b - $c }
      when (/mul/)          { $R{$a} = $b * $c }
      when (/div/)             { $R{$a} = $b / $c }
      when (/mod/)          { $R{$a} = $b % $c }
      when (/pow/)            { $R{$a} = $b ** $c }
      when (/unm/)          { $R{$a} = -$R{$b} }
      when (/not/)          { $R{$a} = ~$R{$b} }         # ?
      when (/len/)          { $R{$a} = length $R{$b} }  # ...if scalar
                                     # $#R{$b}          # ...if hash
                                   
      when (/concat|cat|join/)    { my $sp = $R{$d}? ' ' : ''; $R{$a} = join( $sp, @R{$b..$c} ) }
           
      when (/ju?mp/)        { $PC += $a; closeAllUpvalues($R{$a}+1) if $a }
      when (/j?eq/)            { $PC++ if ( $b == $c ) != $a }
      when (/j?lt/)            { $PC++ if ( $b < $c ) != $a }
      when (/j?le/)             { $PC++ if ( $b <= $c ) != $a }
     
      when (/test/)         { $PC++ unless $R{$b} <=> $c }
      when (/testset/)        { ( $R{$b} <=> $c )? $R{$a} = $R{$b} : $PC++ }
 
      when (/call/)         { @R{$a..$a+$c-2} = call( @R{$a..$a+$b-1} ) }
     
      when (/tailcall/)     { call(@R{$a..$a+$b-1}) }
     
      when (/return/)       { @R{$a..$a+$b-2} }
     
      when (/forloop/)        { $R{$a} += $R{$a+2};
                              $PC += $b if $R{$a} <= $R{$a+1} }
     
      when (/forprep/)        { $R{$a} -= $R{$a+2}; $PC += $b }
     
      when (/tforcall/)        { @R{$a+3..$a+2+$c} = call( $R{$a..$a+2} ) }
     
      when (/tforloop/)        { if ( $R{$a+1} ) {
                                $R{$a} = $R{$a+1};
                                $PC += $b
                            }}
     
      when (/setlist/)        { $R{$a}->{ ($c-1) * $FPF + $_ } = $R{$a+1}
                                    for 1..$b;
                            }
     
      when (/closure/)        { $R{$a} = closure(proto($b)) }
      when (/vararg/)        { $R{$_} = 'vararg' for $R{$a} .. $R{$a+$b-2} }                   
     
   }; 
}

Subversive Metadata for Existing Commodore Images

SYNOPSIS

Jim Brain has suggested a way to encode optional metadata into Commodore images.  Though there are problems with his suggestion, it has merit.

METHOD

Jim's suggestion is to put optional metadata into the final sector of the directory.  The reason given is that this sector is seldom used, since the directory is seldom filled up or exceeded, although this does happen from time to time.

The reason for making this metadata optional is because this sector can be used for other nonstandard purposes, as well as for directory entries.

METADATA

What sort of metadata could go into this block?  There is a lot of useful, but not critical, information that could go there.

1. Magic Strings.  A "magic string" is a short, constant data string that indicates the overall structure of the image.  This string could be scanned for, regardless of the file size, to verify how the file should be parsed.  For example, a D64 might have a magic string of "1541 Digital Image, 2014 January"-- a string that is highly unlikely to show up in any D64 file.  But if present, the parser can be certain that it's a D64 file.

2. Nonstandard Sizes.  Nonstandard image size data could go here.   For example, a byte that indicates the number of tracks present for this image could allow a D64 with 255 tracks, or as few as 18 tracks (stopping at the Directory track).

3. Nonstandard Formats.  Metadata may indicate that the image's format has been altered in specific ways.  For example, the BAM might be nonexistent, or error data is stored in data blocks as a file starting at a particular T/S link.  For that matter, the entire image may be rearranged, with the header at Block 0, the Directory pointed to with a T/S link, error data at another T/S link, and a disk structure having a variable number of tracks with 256 sectors each.  This sort of radical departure would require easy detection of a Magic String of course.

Absurd Commodore Disk Image Format, version 3

Whereas previously I tried to parameterize every possible physical image format, this time I'm just focusing on a more abstract but Commodore-friendly structure.  My purpose is to define a simpler format that is quite flexible, which carries data that can be transferred onto a true physical image with a minimum of fuss.

OVERVIEW

This meta-disk uses a virtual disk format with 256 sectors per track and a variable number of tracks (64k per track).  The image begins with Track 0, and has a maximum possible track number of 255. 
   
The number of tracks present in an image is always computable as:

    Number of Tracks = [Image Size in Bytes] / 65536;
Similarly, the total number of sectors present in an image is known:

    Sectors Per Track = 256;
    Number of Sectors = [Image Size in Bytes] / 256;
NO BAM

This format has no need for a Block Allocation Map (BAM). Being an image designed for virtual use rather than physical media, such a map would be presumably constructed and maintained in memory as the image is used.  If its contents are written to a physical format (e.g. a D64), the BAM would
be calculated as the target image is built, or the new image would be validated by some other means at hand.

I. Header block, 256 bytes.

   This is addressed as sector 0 of track 0, which is always a "null"
   pointer reference for data blocks.
  
   This block contains information about the disk image,
   plus meta-data found in every header block of a Commodore disk.
  
   IMAGE HEADER
  
   $00-$0c Magic Header ASCII = 'ABSURD FORMAT'
   $0d     $00    
   $0e     Header version
   $0f     $00
   $10-$1f Image Label, $a0 terminated
   $20-$21 First directory block (0/0 = none)
   $22-$23 First error block (0/0 = none)  
   (remaining bytes thru $3f Reserved)
  
   DISK HEADER
  
   $40-$4f Disk label, $a0 terminated
   $50     $a0
   $51-$52 Disk ID
   $53     $00
   $54-$55 DOS Type and Version
   $56     $00
   (remaining bytes thru $ff Reserved)

II. Directory Block, 256 bytes.
    Standard Commodore format.  Contains up to eight directory entries.
   
III. File Block, 256 bytes.
     Standard Commodore format.
   
IV. Error Block, 256 bytes.
    Similar in structure to a file block, but contains up to 254 error bytes
    per Error Block, corresponding to sector read errors (usually for 1541 error
    protection schemes).  A full 1541 image requires three Error Blocks.

A C64 in hindsight (or: if they knew then...)

If they knew then what they know now, I think the C64 could have had some better-thought-out components.  For example:

* The power supply could have had a universal power cord, so that peripherals and the CPU could use the same unit.  It might even have had two outlets so a single supply could power (for example) the C64 and a disk drive.  This would have decreased the price and complexity of the disk drive a bit, and increased its life span, as well.

* The 1541 could have had a logical track and sector layout, regardless of the physical layout, to simplify I/O.

* The 1541 layout would have put the image metadata in the header at location $10-$27, instead of $90-$A7, and started the BAM at $28, allowing contiguous BAM entries thru Track 40 (and theoretically thru Track 53).

* They could have spent just a little more time to fix the IEEE chip, to bring its speed back up to normal.

CargoCult in a Nutshell

Here's my working syntax for CargoCult.

assumptions

numerical expressions are per C standards.


variable declarations:

my [<type>] <id> [= <initialization expression>];

Array variables start with the sigil '@'.  They're indexed with square brackets, as in C.


function declarations:

fn <returntype> <name> parm1, parm2, ...

<body>
endfn


function calls:

[<return value> =] <function name([<parameters>])>;


function parameters are comma-separated, and typed or untyped.  If typed, the type precedes the identifier, e.g. callMyFunction( String foo, int bar );


for loops (currently only increment, by 1):

for |<indexname>| <start>..<end>

<body>
endfor


if statements:

if ( <expression> )
<body>
endif


return statements:

return <expression>;

CargoCult as an Intermediate Language

I face the onerous task of converting my commodore image reading code from AS3 into Perl and Objective-C.

Rather than port code twice to two platforms, I'd rather use CargoCult as the specification, and use real languages as targets.

I don't have to get 100% code conversion: I just need to get 80% of the way there to make this worthwhile.

That means CargoCult is a high-level Intermediate Language of sorts.  It's C-like, but uses syntactic sugar in a way that makes it relatively easy to write generators to transform it to other languages.  My goal is to be able to make line-by-line translators without having to do any real analysis of the code.

Here's a sample of CargoCult 1.0.

fn int buildZones totalSectors, startTrack, @zones

   for |index| 0..@zones.length
  
      my track = 1 + GLOBAL.totalTracks + startTrack;
      my sectorCount = @zones[index][1];
      my endTrack = 1 + GLOBAL.totalTracks + @zones[index][0];
     
      GLOBAL.totalTracks += @zones[index][0];
     
      for |jdex| track..endTrack
     
         GLOBAL.@trackOffset[ jdex ] = totalSectors * 0x100;
         GLOBAL.@sectorOffset[ jdex ] = totalSectors;
         GLOBAL.@sectorsInTrack[ jdex ] = sectorCount;
        
         totalSectors += sectorCount;
     
      endfor
     
   endfor
  
   return totalSectors;
  
endfn


I've successfully translated this into fully functional Perl, ActionScript3, and Objective-C.  It took 80 lines of code for each, but after that the translator was able to translate another CargoCult function, as well.

What I want to do next is build up a set of translations for each target language, for each transformation needed (line preprocessing, library call handing, subroutine handling, loop handling, and line postprocessing).

CN - "C Data Notation"

Just for fun, here's an idea for a data notation that's sort of C-like in structure.  Does it have enough representational power to be useful?

CN  "C Data Notation"

A CN document is a list of items, separated by one or more newlines, like so:

list item one
list item two

list item three

---

CN documents are delimited by the triple-dash made popular by YAML:

---

Multi-line items use the C-style backslash \
at the end of the line.

---

Pairs are specified using the colon, like so:

key1: value1
key2: value2
key3: value3

Terminating colons do not represent a pair.

A group can be created using curly braces.

{
   key1: value1
   key2: value2
   key3: value3
   key4: value4\
         line2\
         line3\
         last line
        
}

It's not a hash, it's a key-value list, where the pairs are stored in order.

myLevel1:
{
   myLevel2:
   {
      subkey: 123
   }
}


A value from a pair can be referenced with an asterisk and the key's qualified namespace:

*myLevel1.myLevel2.subkey