FVM.h

Go to the documentation of this file.

#ifndef ARDUINO_FVM_H
#define ARDUINO_FVM_H

#include <Arduino.h>

typedef const PROGMEM char* str_P;

class FVM {
 public:
  enum {
    /*
     * Control structure and literals
     */
    OP_EXIT = 0,                
    OP_ZERO_EXIT = 1,           
    OP_LIT = 2,                 
    OP_CLIT = 3,                
    OP_SLIT = 4,                
    OP_VAR = 5,                 
    OP_CONST = 6,               
    OP_FUNC = 7,                
    OP_DOES = 8,                
    OP_PARAM = 9,               
    OP_BRANCH = 10,             
    OP_ZERO_BRANCH = 11,        
    OP_DO = 12,                 
    OP_I = 13,                  
    OP_J = 14,                  
    OP_LEAVE = 15,              
    OP_LOOP = 16,               
    OP_PLUS_LOOP = 17,          
    OP_NOOP = 18,               
    OP_EXECUTE = 19,            
    OP_HALT = 20,               
    OP_YIELD = 21,              
    OP_SYSCALL = 22,            
    OP_CALL = 23,               
    OP_TRACE = 24,              
    OP_ROOM = 25,               

    /*
     * Memory access
     */
    OP_C_FETCH = 26,            
    OP_C_STORE = 27,            
    OP_FETCH = 28,              
    OP_STORE = 29,              
    OP_PLUS_STORE = 30,         
    OP_DP = 31,                 
    OP_HERE = 32,               
    OP_ALLOT = 33,              
    OP_COMMA = 34,              
    OP_C_COMMA = 35,            
    OP_COMPILE = 36,            

    /*
     * Return stack
     */
    OP_TO_R = 37,               
    OP_R_FROM = 38,             
    OP_R_FETCH = 39,            

    /*
     * Parameter stack
     */
    OP_SP = 40,                 
    OP_DEPTH = 41,              
    OP_DROP = 42,               
    OP_NIP = 43,                
    OP_EMPTY = 44,              
    OP_DUP = 45,                
    OP_QUESTION_DUP = 46,       
    OP_OVER = 47,               
    OP_TUCK = 48,               
    OP_PICK = 49,               
    OP_SWAP = 50,               
    OP_ROT = 51,                
    OP_MINUS_ROT = 52,          
    OP_ROLL = 53,               
    OP_TWO_SWAP = 54,           
    OP_TWO_DUP = 55,            
    OP_TWO_OVER = 56,           
    OP_TWO_DROP = 57,           

    /*
     * Constants
     */
    OP_MINUS_TWO = 58,          
    OP_MINUS_ONE = 59,          
    OP_ZERO = 60,               
    OP_ONE = 61,                
    OP_TWO = 62,                
    OP_CELL = 63,               
    OP_CELLS = 64,              

    /*
     * Bitwise logical operations
     */
    OP_BOOL = 65,               
    OP_NOT = 66,                
    OP_TRUE = 67,               
    OP_FALSE = 68,              
    OP_INVERT = 69,             
    OP_AND = 70,                
    OP_OR = 71,                 
    OP_XOR = 72,                

    /*
     * Arithmetic operations
     */
    OP_NEGATE = 73,             
    OP_ONE_PLUS = 74,           
    OP_ONE_MINUS = 75,          
    OP_TWO_PLUS = 76,           
    OP_TWO_MINUS = 77,          
    OP_TWO_STAR = 78,           
    OP_TWO_SLASH = 79,          
    OP_PLUS = 80,               
    OP_MINUS = 81,              
    OP_STAR = 82,               
    OP_STAR_SLASH = 83,         
    OP_SLASH = 84,              
    OP_MOD = 85,                
    OP_SLASH_MOD = 86,          
    OP_LSHIFT = 87,             
    OP_RSHIFT = 88,             

    /*
     * Math operations
     */
    OP_WITHIN = 89,             
    OP_ABS = 90,                
    OP_MIN = 91,                
    OP_MAX = 92,                

    /*
     * Relational operations
     */
    OP_ZERO_NOT_EQUALS = 93,    
    OP_ZERO_LESS = 94,          
    OP_ZERO_EQUALS = 95,        
    OP_ZERO_GREATER = 96,       
    OP_NOT_EQUALS = 97,         
    OP_LESS = 98,               
    OP_EQUALS = 99,             
    OP_GREATER = 100,           
    OP_U_LESS = 101,            

    /*
     * Dictionary functions
     */
    OP_LOOKUP = 102,            
    OP_TO_BODY = 103,           
    OP_WORDS = 104,             

    /*
     * Basic I/O
     */
    OP_BASE = 105,              
    OP_HEX = 106,               
    OP_DECIMAL = 107,           
    OP_QUESTION_KEY = 108,      
    OP_KEY = 109,               
    OP_EMIT = 110,              
    OP_CR = 111,                
    OP_SPACE = 112,             
    OP_SPACES = 113,            
    OP_U_DOT = 114,             
    OP_DOT = 115,               
    OP_DOT_S = 116,             
    OP_DOT_QUOTE = 117,         
    OP_TYPE = 118,              
    OP_DOT_NAME = 119,          
    OP_QUESTION = 120,          

    /*
     * Arduino extensions
     */
    OP_MICROS = 121,            
    OP_MILLIS = 122,            
    OP_DELAY = 123,             
    OP_PINMODE = 124,           
    OP_DIGITALREAD = 125,       
    OP_DIGITALWRITE = 126,      
    OP_DIGITALTOGGLE = 127,     
    OP_ANALOGREAD = 128,        
    OP_ANALOGWRITE = 129,       

    CORE_MAX = 128,

    KERNEL_MAX = 256,

    APPLICATION_MAX = 384,

    TOKEN_MAX = 511
  };

#if defined(ARDUINO_ARCH_AVR)
  typedef int16_t cell_t;
  typedef uint16_t ucell_t;
  typedef int32_t cell2_t;
  typedef uint32_t ucell2_t;
#else
  typedef int32_t cell_t;
  typedef uint32_t ucell_t;
  typedef int64_t cell2_t;
  typedef uint64_t ucell2_t;
#endif

  typedef int8_t code_t;
  typedef const PROGMEM code_t* code_P;

  struct task_t {
    Stream& m_ios;              
    cell_t m_base;              
    bool m_trace;               
    code_P* m_rp;               
    code_P* m_rp0;              
    cell_t* m_sp;               
    cell_t* m_sp0;              

    task_t(Stream&ios, cell_t* sp0, code_P* rp0, code_P fn) :
      m_ios(ios),
      m_base(10),
      m_trace(false),
      m_rp(rp0),
      m_rp0(rp0),
      m_sp(sp0 + 1),
      m_sp0(sp0)
    {
      *++m_rp = fn;
    }

    void push(cell_t value)
    {
      *++m_sp = value;
    }

    cell_t pop()
    {
      return (*m_sp--);
    }

    int depth()
    {
      return (m_sp - m_sp0 - 1);
    }

    bool trace()
    {
      return (m_trace);
    }

    void trace(bool flag)
    {
      m_trace = flag;
    }

    task_t& call(code_P fn)
    {
      *++m_rp = fn;
      return (*this);
    }
  };

  template<int PARAMETER_STACK_MAX, int RETURN_STACK_MAX>
  struct Task : task_t {
    cell_t m_params[PARAMETER_STACK_MAX];
    code_P m_returns[RETURN_STACK_MAX];

    Task(Stream& ios, code_P fn = 0) :
    task_t(ios, m_params, m_returns, fn)
    {}
  };

  struct obj_t {
    code_t op;                  
    code_t noop;                
    cell_t* value;              
  } __attribute__((packed));

  struct var_t {
    code_t op;                  
    cell_t* value;              
  } __attribute__((packed));

  struct const_t {
    code_t op;                  
    cell_t value;               
  } __attribute__((packed));

  typedef void (*fn_t)(task_t &task, void* env);
  struct func_t {
    code_t op;                  
    fn_t fn;                    
    void* env;                  
  } __attribute__((packed));

   FVM(uint8_t* dp0 = 0, size_t bytes = 0, uint8_t words = 0) :
    DICT_MAX(bytes),
    WORD_MAX(words),
    m_next(0),
    m_dp(dp0),
    m_dp0(dp0)
  {
    m_body = (code_t**) dp0;
    m_name = 0;
    if (words == 0) return;
    dp0 += sizeof(code_t**) * words;
    m_name = (char**) dp0;
    dp0 += sizeof(char**) * words;
    m_dp = dp0;
    m_dp0 = dp0;
  }

  uint8_t* dp()
  {
    return (m_dp);
  }

  void dp(uint8_t* dp)
  {
    m_dp = dp;
  }

  bool compile(int op)
  {
    if (op < 0 || op > TOKEN_MAX) return (false);
    if (op < KERNEL_MAX) {
      if (op >= CORE_MAX) *m_dp++ = OP_SYSCALL;
      *m_dp++ = op;
    }
    else if (op < APPLICATION_MAX) {
      *m_dp++ = APPLICATION_MAX - op - 1;
    }
    else {
      *m_dp++ = OP_CALL;
      *m_dp++ = op - APPLICATION_MAX;
    }
    return (true);
  }

  void literal(int val)
  {
    if (val < INT8_MIN || val > INT8_MAX) {
      *m_dp++ = OP_LIT;
      *m_dp++ = val;
      *m_dp++ = val >> 8;
    }
    else {
      *m_dp++ = OP_CLIT;
      *m_dp++ = val;
    }
  }

  bool create(const char* name)
  {
    if (m_next == WORD_MAX) return (false);
    m_name[m_next] = (char*) m_dp;
    strcpy((char*) m_dp, name);
    m_dp += strlen(name) + 1;
#if defined(ARDUINO_ARCH_AVR)
    m_body[m_next] = (code_t*) (m_dp + CODE_P_MAX);
#else
    m_body[m_next] = (code_t*) m_dp;
#endif
    m_next += 1;
    return (true);
  }

  bool variable(const char* name)
  {
    if (!create(name)) return (false);
    *m_dp++ = OP_VAR;
    *m_dp++ = 0;
    *m_dp++ = 0;
#if !defined(ARDUINO_ARCH_AVR)
    *m_dp++ = 0;
    *m_dp++ = 0;
#endif
    return (true);
  }

  bool constant(const char* name, int val)
  {
    if (!create(name)) return (false);
    *m_dp++ = OP_CONST;
    *m_dp++ = val;
    *m_dp++ = val >> 8;
#if !defined(ARDUINO_ARCH_AVR)
    *m_dp++ = val >> 16;
    *m_dp++ = val >> 24;
#endif
    return (true);
  }

  const char* name(int op)
  {
    return (op < m_next ? m_name[op] : 0);
  }

  code_t* body(int op)
  {
#if defined(ARDUINO_ARCH_AVR)
    return (op < m_next ? m_body[op] - CODE_P_MAX : 0);
#else
    return (op < m_next ? m_body[op] : 0);
#endif
  }

  bool forget(int op)
  {
    op = op - APPLICATION_MAX;
    if (op < 0 || op > m_next) return (false);
    m_dp = (uint8_t*) m_name[op];
    m_next = op;
    return (true);
  }

  int scan(char* bp, task_t& task);

  int lookup(const char* name);

  int resume(task_t& task);

  int execute(int op, task_t& task);

  int execute(code_P fn, task_t& task)
  {
    return (resume(task.call(fn)));
  }

  int execute(const char* name, task_t& task)
  {
    return (execute(lookup(name), task));
  }

  int interpret(task_t& task);

  // Threaded code and dictionary to be provided by sketch (program memory)
  static const code_P fntab[] PROGMEM;
  static const str_P fnstr[] PROGMEM;

  // Address mapping; max program memory code pointer
  static const uint16_t CODE_P_MAX = 0x8000;

 protected:
  // Kernel dictionary (optional)
  static const str_P opstr[] PROGMEM;

  // Data allocation pointer and dynamic dictionary
  const size_t DICT_MAX;
  const uint8_t WORD_MAX;
  uint8_t m_next;
  uint8_t* m_dp;
  uint8_t* m_dp0;
  code_t** m_body;
  char** m_name;
};

#define FVM_OP(code) FVM::OP_ ## code

#define FVM_LIT(n)                                                      \
  FVM::OP_LIT,                                                          \
  FVM::code_t(n),                                                       \
  FVM::code_t((n) >> 8)

#define FVM_CLIT(n)                                                     \
  FVM::OP_CLIT,                                                         \
  FVM::code_t(n)

#define FVM_CALL(fn) FVM::code_t(-fn-1)

#define FVM_CREATE(id,var,does,data)                                    \
  const int var = id;                                                   \
  const char var ## _PSTR[] PROGMEM = #data;                            \
  const FVM::obj_t var ## _VAR PROGMEM = {                              \
    FVM_CALL(does),                                                     \
    FVM_OP(NOOP),                                                       \
    (FVM::cell_t*) &data                                                \
  }

#define FVM_VARIABLE(id,var,data)                                       \
  const int var = id;                                                   \
  const char var ## _PSTR[] PROGMEM = #data;                            \
  const FVM::var_t var ## _VAR PROGMEM = {                              \
    FVM_OP(CONST),                                                      \
    (FVM::cell_t*) &data                                                \
  }

#define FVM_CONSTANT(id,var,name,val)                                   \
  const int var = id;                                                   \
  const char var ## _PSTR[] PROGMEM = name;                             \
  const FVM::const_t var ## _CONST PROGMEM = {                          \
    FVM_OP(CONST),                                                      \
    val                                                                 \
  }

#define FVM_COLON(id,var,name)                                          \
  const int var = id;                                                   \
  const char var ## _PSTR[] PROGMEM = name;                             \
  const FVM::code_t var ## _CODE[] PROGMEM = {

#define FVM_FUNCTION(id,var,fn,env)                                     \
  const int var = id;                                                   \
  const char var ## _PSTR[] PROGMEM = #fn;                              \
  const FVM::func_t var ## _FUNC PROGMEM = {                            \
    FVM_OP(FUNC),                                                       \
    fn,                                                                 \
    (FVM::cell_t*) &env                                                 \
  }

#define FVM_SYMBOL(id,var,name)                                         \
  const int var = id + FVM::KERNEL_MAX;                                 \
  const char var ## _PSTR[] PROGMEM = name

#endif