First Langosh language proof of concept implementation

langosh-plain.c

/*

Just a small weekend experiment...


First experimental implementation of the Langosh language ("plain", i.e. really minimal version).

Langosh is meant to be a language which:
 - can be easily machine-generated from Scratch-like visual programming tools (Blockly preferably)
 - interpreter is small enough to fit in a small MCU (ATMega328 preferably)
 - is powerful enough to express common "high-level" embedded devices programs
   (robot behaviour etc.) using underlying C primitives
 - bytecode is designed so that practical programs are as small as possible

By embedding Langosh into your AVR firmware, you can easily change your robot behaviour on the fly
even over low bandwidth connection.

This version ("plain") does not contain primitives for function definition and calling but
it contains Forth-like stack-based arguments passing, basic arithmetic and logic primitives
and one loop type ("while not zero").

Other control structures like e.g. if-then-else can be constructed using this "minimal practical"
primitives set (see test_if() function).

*/

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>

#define WITH_DEBUG
//#define WITH_STACK_PRINT
#define WITH_DEBUG_STACK

#ifdef WITH_DEBUG
#define DEBUG(x) {puts(x);}
#define DEBUGN(x) {printf("%s", x);}
#define DEBUGD(x) {printf("%d\n", x);}
#define DEBUG_STACK(s) stack_print(s)
#else
#define DEBUG(x)
#define DEBUGN(x)
#define DEBUGD(x)
#define DEBUG_STACK(s)
#endif

typedef uint8_t word_t;

const word_t SYM_TRUE = 1;
const word_t SYM_FALSE = 0;

enum {
  FATAL_BAD_OP = 1,
  FATAL_STACK_INVALID_POP,
  FATAL_STACK_INVALID_PEEP,
};

#define die(x) _die(x, __FILE__, __LINE__)

void _die(word_t reason, char* file, int line) {
  printf("\n\nKILLED: ");
  switch(reason) {
    case FATAL_BAD_OP:
      printf("bad op");
      break;
    case FATAL_STACK_INVALID_POP:
      printf("pop from an empty stack");
      break;
    case FATAL_STACK_INVALID_PEEP:
      printf("peep into an empty stack");
      break;
    default:
      printf("unknown reason (%d)", reason);
  }
  printf(" [%s:%d]\n\n", file, line);
  exit(1);
}

enum {
  OP_HALT = 32,
  OP_BYTE,
  OP_DROP,
  OP_DUP,
  OP_LT,
  OP_LTE,
  OP_EQ,
  OP_NEG,
  OP_LOOP,
  OP_END,
  OP_PLUS,
  OP_MINUS,
  OP_MULT,
  OP_PRINT = 253,
  OP_PRINT_STACK,
  OP_DSTACK_PUSH,
};

//
// STACK
//

typedef struct {
  word_t * top;
  word_t * sp;
} stack_t;

void stack_init(stack_t *s, word_t *stack_mem, size_t stack_size) {
  s->top = stack_mem + stack_size - 1;
  s->sp = s->top;
}

void stack_reset(stack_t *s) {
  s->sp = s->top;
}

bool stack_empty(stack_t *s) {
  return s->sp == s->top;
}

void stack_push(stack_t *s, word_t val) {
  // TODO: check bounds
  *(s->sp) = val;
  s->sp -= 1;
}

word_t stack_pop(stack_t *s) {
  s->sp += 1;
  if(s->sp > s->top) {
    die(FATAL_STACK_INVALID_POP);
  }
  return *(s->sp);
}

word_t stack_peep(stack_t *s) {
  if(s->sp == s->top) {
    die(FATAL_STACK_INVALID_PEEP);
  }
  return *(s->sp+1);
}

void stack_print(stack_t *s) {
  word_t *w = s->sp + 1;

  if(s->sp == s->top) {
    //puts("\n[stack is empty]");
    return;
  }
  printf("\n---------------------------------------------------------- STACK -----\n");
  while(w <= s->top) {
    printf("%ld: %d\n", s->top - w, *w);
    w++;
  }
  printf("----------------------------------------------------------------------\n");
}

//
// PROCESS
//

typedef struct {
  stack_t * stack;
  stack_t * rstack;
  #ifdef WITH_DEBUG_STACK
  stack_t * dstack;
  #endif
  const word_t * prog;
  size_t pc;
} process_t;

void proc_init(process_t *proc, stack_t *stack, stack_t *rstack, word_t *prog_mem) {
  proc->stack = stack;
  proc->rstack = rstack;
  proc->prog = prog_mem;
  proc->pc = 0;
}

void proc_reset(process_t *proc) {
  stack_reset(proc->stack);
  stack_reset(proc->rstack);
  #ifdef WITH_DEBUG_STACK
  stack_reset(proc->dstack);
  #endif
  proc->pc = 0;
}

void proc_skip_block(process_t *proc) {
  unsigned int counter = 1;
  DEBUG("skipping block");
  while(counter>0) {
    switch(proc->prog[proc->pc++]) {
    case OP_BYTE:
      proc->pc++;
      break;
    case OP_LOOP:
      counter++;
      break;
    case OP_END:
      counter--;
      break;
    }
  }
}

void proc_step(process_t *proc) {
  word_t arg1, arg2;

  #ifdef WITH_STACK_PRINT
  stack_print(proc->stack);
  #endif
  #ifdef WITH_DEBUG
  printf("%ld: ", proc->pc);
  #endif
  word_t opcode = proc->prog[proc->pc++];
  switch(opcode) {
    case OP_HALT:
      DEBUG("halt");
      DEBUG_STACK(proc->stack);
      proc->pc--;
      break;
    case OP_DROP:
      DEBUG("drop");
      stack_pop(proc->stack);
      break;
    case OP_DUP:
      DEBUG("dup");
      arg1 = stack_peep(proc->stack);
      stack_push(proc->stack, arg1);
      break;
    case OP_NEG:
      DEBUG("neg");
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 ? SYM_FALSE : SYM_TRUE);
      break;
    case OP_EQ:
      DEBUG("eq");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 == arg2 ? SYM_TRUE : SYM_FALSE);
      break;
    case OP_LT:
      DEBUG("lt");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 < arg2 ? SYM_TRUE : SYM_FALSE);
      break;
    case OP_LTE:
      DEBUG("lte");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 <= arg2 ? SYM_TRUE : SYM_FALSE);
      break;
    case OP_PLUS:
      DEBUG("+");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 + arg2);
      break;
    case OP_MINUS:
      DEBUG("-");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 - arg2);
      break;
    case OP_MULT:
      DEBUG("*");
      arg2 = stack_pop(proc->stack);
      arg1 = stack_pop(proc->stack);
      stack_push(proc->stack, arg1 * arg2);
      break;
    case OP_BYTE:
      arg1 = proc->prog[proc->pc];
      DEBUGD(arg1);
      stack_push(proc->stack, arg1);
      proc->pc++;
      break;
    case OP_LOOP:
      DEBUG("loop");
      stack_push(proc->rstack, proc->pc-1);
      arg1 = stack_pop(proc->stack);
      if(!arg1) {
        proc_skip_block(proc);
        stack_pop(proc->rstack);
      }
      break;
    case OP_END:
      DEBUG("end");
      proc->pc = stack_pop(proc->rstack);
      break;
    case OP_PRINT:
      DEBUG("print");
      printf("%d\n", stack_pop(proc->stack));
      break;
    case OP_PRINT_STACK:
      DEBUG("print-stack");
      stack_print(proc->stack);
      puts("");
      break;
    #ifdef WITH_DEBUG_STACK
    case OP_DSTACK_PUSH:
      arg1 = stack_pop(proc->stack);
      DEBUGN(">d "); DEBUGD(arg1);
      stack_push(proc->dstack, arg1);
      break;
    #endif
    default:
      if((opcode & 0b11100000) == 0) {
        word_t val = opcode & 0b11111;
        DEBUGD(val);
        stack_push(proc->stack, val);
      } else {
        DEBUGD(opcode);
        die(FATAL_BAD_OP);
      }
  }
}

void proc_run(process_t *proc) {
  while(proc->prog[proc->pc] != OP_HALT) {
    proc_step(proc);
  }
}

//
// TESTS
//

// test basic stack operations
void test_stack(process_t *proc) {
  DEBUG("\n5 dup drop 10 dup =");
  word_t prog[] = {
    5,
    OP_DUP,
    OP_DROP,
    10,
    OP_DUP,
    OP_HALT
  };

  proc_reset(proc);
  proc->prog = prog;
  proc_run(proc);
  assert(stack_pop(proc->stack) == 10);
  assert(stack_pop(proc->stack) == 10);
  assert(stack_pop(proc->stack) == 5);
  assert(stack_empty(proc->stack));

  puts("test_stack: OK\n");
}

// test arithmetic functions
void test_arithmetic(process_t *proc) {
  DEBUG("\n(4 - 2) * (5 + 3) =");
  word_t prog[] = {
    4, 2, OP_MINUS,
    5, 3, OP_PLUS,
    OP_MULT,
    OP_HALT
  };
  proc_reset(proc);
  proc->prog = prog;
  proc_run(proc);
  DEBUGN("= "); DEBUGD(stack_peep(proc->stack));
  assert(stack_pop(proc->stack) == 16);
  assert(stack_empty(proc->stack));

  puts("test_arithmetic: OK\n");
}

// test simple loop
void test_loop(process_t *proc) {
  DEBUG("\nfor i := 5 to 2 begin dstack.push(i) end");
  word_t prog[] = {
    5, // init: i=5
    OP_DUP, 2, OP_LTE, OP_NEG, // condition: i>2
    OP_LOOP,
      OP_DUP, OP_DSTACK_PUSH, // body
      1, OP_MINUS, // afterthought: i--
      OP_DUP, 2, OP_LTE, OP_NEG, // condition again: i>2
    OP_END,
    OP_DROP,
    OP_HALT
  };
  proc_reset(proc);
  proc->prog = prog;
  proc_run(proc);
  assert(stack_pop(proc->dstack) == 3);
  assert(stack_pop(proc->dstack) == 4);
  assert(stack_pop(proc->dstack) == 5);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  puts("test_loop: OK\n");
}

// test nested loops
void test_nested_loops(process_t *proc) {
  DEBUG("\nfor i := 5 to 2 do dstack.push(i); for j := 10 to 12 do dstack.push(j) end end");
  word_t prog[] = {
    5, // init: i=5
    OP_DUP, 2, OP_LTE, OP_NEG, // condition: i>2
    OP_LOOP,
      OP_DUP, OP_DSTACK_PUSH,
      10, // init: j=1
      OP_DUP, 12, OP_LT, // condition: j<12
      OP_LOOP,
        OP_DUP, OP_DSTACK_PUSH,
        1, OP_PLUS, // afterthought: j++
        OP_DUP, 12, OP_LT, // condition again: j<12
      OP_END,
      OP_DROP,
      1, OP_MINUS, // afterthought: i--
      OP_DUP, 2, OP_LTE, OP_NEG, // condition again: i>2
    OP_END,
    OP_DROP,
    OP_HALT
  };
  proc_reset(proc);
  proc->prog = prog;
  proc_run(proc);
  assert(stack_pop(proc->dstack) == 11);
  assert(stack_pop(proc->dstack) == 10);
  assert(stack_pop(proc->dstack) == 3);
  assert(stack_pop(proc->dstack) == 11);
  assert(stack_pop(proc->dstack) == 10);
  assert(stack_pop(proc->dstack) == 4);
  assert(stack_pop(proc->dstack) == 11);
  assert(stack_pop(proc->dstack) == 10);
  assert(stack_pop(proc->dstack) == 5);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  puts("test_nested_loop: OK\n");
}

// test if-then-else
void test_if(process_t *proc) {
  DEBUG("\nx:=1; if x<2 then dstack.push(2) end");
  word_t prog1[] = {
    1, // init: x=1
    2, OP_LT, // condition: x<2
    OP_LOOP,
      2, OP_DSTACK_PUSH, // "then" body
      0,
    OP_END,
    OP_HALT
  };
  proc_reset(proc);
  proc->prog = prog1;
  proc_run(proc);
  assert(stack_pop(proc->dstack) == 2);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  DEBUG("\nx:=2; if x<2 then dstack.push(2) end");
  prog1[0] = 2;
  proc_reset(proc);
  proc_run(proc);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  DEBUG("\nx:=1; if x<2 then dstack.push(2) else dstack.push(3) end");
  word_t prog2[] = {
    1, // init: x=1
    2, OP_LT, // condition: x<2
    OP_DUP,
    OP_LOOP,
      2, OP_DSTACK_PUSH, // "then" body
      0,
    OP_END,
    OP_NEG,
    OP_LOOP,
      3, OP_DSTACK_PUSH, // "else" body
      0,
    OP_END,
    OP_HALT
  };
  proc_reset(proc);
  proc->prog = prog2;
  proc_run(proc);
  assert(stack_pop(proc->dstack) == 2);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  DEBUG("\nx:=2; if x<2 then dstack.push(2) else dstack.push(3) end");
  prog2[0] = 2;
  proc_reset(proc);
  proc_run(proc);
  assert(stack_pop(proc->dstack) == 3);
  assert(stack_empty(proc->dstack));
  assert(stack_empty(proc->stack));

  puts("test_if: OK\n");
}

void tests() {
  word_t stack_mem[64];
  word_t rstack_mem[64];
  word_t dstack_mem[64];
  stack_t stack, rstack, dstack;
  process_t proc;

  stack_init(&stack, (word_t*)stack_mem, sizeof(stack_mem));
  stack_init(&rstack, (word_t*)rstack_mem, sizeof(rstack_mem));
  stack_init(&dstack, (word_t*)dstack_mem, sizeof(dstack_mem));

  proc_init(&proc, &stack, &rstack, NULL);
  proc.dstack = &dstack;

  test_stack(&proc);
  test_arithmetic(&proc);
  test_loop(&proc);
  test_nested_loops(&proc);
  test_if(&proc);
}

//
// MAIN
//

int main() {
  printf("Langosh-plain 0.1\n\n");
  tests();
  return 0;
}