Model and API to manage variables in scripting languages

[sporniket]

Abstract

Studying some scripting languages like Espruino, Micropython,..., design my own model and API for my own scripting language.

In a javascript-like toy scripting language, it would gives something like :

a = 10
console.log(a) // Output: 10

a = "Hello"
console.log(a) // Output: Hello

a = true
console.log(a) // Output: true

a = { 
  order_id: 1, 
  amount: 10.35, 
  currency: "EUR", 
  shipping_address: {
    lines:[
      "1 baker street","for M. Bar"
    ], 
    zipcode:"92340", 
    city:"New York"
  } 
}
console.log(a) // Output: { order_id: 1, amount: 10.35, currency: "EUR", shipping_address: {lines:["1 baker street","for M. Bar"], zipcode:"92340", city:"New York"} }

[sporniket]

Variable representation

Inspired by Espruino variable storage principles, one variable will occupy one or more blocks of 16 bytes.

The set of features : a wish-list

The blocks

• A block has an ID that is a 16-bits unsigned value, hence up to around 65k blocks (1 MiB). The actual number of blocks depends on actual available memory. The actual address of a block is base address + 16*ID.
• the block with ID 0 is reserved, it is the root of all free blocks.
• a block may be free or unused
• Memory is provisionned for raw memory areas, a storage for a continuous blob of data (pictures, long string of characters,...)
• A block is part of a linked list : it has a pointer to next and previous, as well as a parent ; those are the ID of the designated blocks
• A free cell has 0 for parent.

The variables

• A flag area (16 bits value) encode the type of the block and some status flags.
• the native number type IS fixed point, signed Q31.32 (TI convention : sign bit + 31 bits (integral part) + 32 bits (fractionnal part)) see Q
• the native number MAY be forced to be integral with a flag
• A variable is named. The name is stored in at least one block, it MAY require supplemental blocks when the name is too long.
• A native number variable may store the name and the value if the name is short enough. A flag MUST tell about this compactedness. The name IS the main data of the bloc, the value is stored after the name slot, at an offset convenient for the machine language (aligned over a 4-bytes alignment boundary). A native number is 8 bytes, 6 bytes for the navigation and 2 bytes for the flags/types, this system of compression WILL NOT be implemented
• A native string of characters is a linked list of blocks to store the string of characters (single, unsigned byte). If there is a need to use multiple blocks, those are children blocks, with a pointer to the first and the last

Logic model :

const {
  data, // 8 bytes
  navigation : {
    parent, previous, next // ids of blocks of same level = 6 bytes
  },
  children : { 
    first, last // ids of children blocks = 4 bytes
  },
  flags : {
    integral, // boolean, meaningfull only when the type is number
    type, // unsigned integer (predefined types : 0 = number, 1 = names, 2 = strings, ...)
    //...
  } // MUST hold into 2 bytes
} = jsvar  // MUST hold into 16 bytes

Samples

An integer named item_count

[ //...
//current index for the variable : i
{
  data: {
    name: {
      length:10, // uint16_t
      first:i+1, 
      last:i+2 
    }, // 6 bytes
    value: {
      type : 0, // uint16_t
      first : i+3,
      last: i+3
    }
  },
  navigation : {
    parent : p //whatever, 
    previous : i-3 // if the previous variable is a short named, integer value too, 
    next : 0 // this is the latest variable declared
  },
  flags : {
    type : TYPE__VARIABLE_DEFINITION
  } // MUST hold into 2 bytes
}, 
// current index for the name, first block : i+1
{
  data: {
    name: "item_cou", //8 bytes at most
  },
  navigation : {
    parent : i //the variable definition block, 
    previous : 0 // first block in the list
    next : i+2 // next block to complete the name
  },
  flags : {
    type : TYPE__NAME_PART
  } // MUST hold into 2 bytes
}, 
// current index for the name, second block : i+2
{
  data: {
    name: "nt\u0000\u0000\u0000\u0000\u0000\u0000", //8 bytes at most, padded with 0
  },
  navigation : {
    parent : i //the variable definition block, 
    previous : i+1 // previous block in the list
    next : 0 // no more blocks for the name
  },
  flags : {
    type : TYPE__KEY_NAME_PART
  } // MUST hold into 2 bytes
}, 
// current index for the value : i+3
{
  data : {
    integral, decimal // 2×uint32_t
  }, 
  navigation : {
    parent : i, //the block that "owns" the value
    previous:0, next:0 // single child bloc
  },
  flags : {
    integral : true, //by default, false
    type : TYPE__NUMBER_VALUE, 
    //...
  } // MUST hold into 2 bytes
}
]