VerySimpleAbstractMachine.js

/* -*- coding: utf-8 -*- 
 *
 * VerySimpleAbstractMachines.js
 * (c) M.Hiyama 2015
 */

/*
 * トレース
 * ========
 */

// トレースを行うかどうかのフラグ
var TRACE = false;

// 状態を、ステップ番号と共に表示する
function showState(step, stat) {
  if (TRACE) {
    console.info(step + ":(" + stat + ")")
  }
}

// プログラム（基本命令の配列）を表示する
function showProg(prog) {
  if (TRACE) {
    console.info(prog)
  }
}

/*
 * 2つのプロセッサ
 * ===============
 */

/* 
 * プロセッサ その1 （P1）
 */

// P1 の基本命令
const N = "N"; // No operation
const U = "U"; // Up

// Stat = {0, 1, 2}
// Inst = {N, U}

// P1 : Stat×Inst → Stat
function P1(stat, inst) {
  // stat : 0, 1, 2 のいずれか
  // inst : N, U のどちらか

  switch (inst) {
  case N:
    switch (stat) {
    case 0: return 0;
    case 1: return 1;
    case 2: return 2;
    default: throw "Invalid state: " + stat
    }
  case U:
    switch (stat) {
    case 0: return 1;
    case 1: return 2;
    case 2: throw "Not defined"
    default: throw "Invalid state: " + stat
    }
  default: throw "Invalid instraction: " + inst
  }
}

/* 
 * プロセッサ その2 （P2）
 */

// P2 の基本命令
const N_N = [N, N];
const N_U = [N, U];
const U_N = [U, N];
const U_U = [U, U];

// P2 : (Stat×Stat)×(Inst×Inst) → Stat×Stat
function P2(stat, inst) {
  // stat : 0, 1, 2 を要素とするペア
  // inst : N, U を要素とするペア
  
  var stat1 = stat[0];
  var stat2 = stat[1];
  var inst1 = inst[0];
  var inst2 = inst[1];
  return [P1(stat1, inst1), P1(stat2, inst2)];
}

/*
 * 5つのマシン
 * ===========
 */

/*
 * マシン その1 （M1）
 * P1を使用
 */

// M1 : Inst^* → Stat
function M1(prog) {
  // prog : N, U を要素とする配列
  
  var stat = 0; // 初期状態
  var n = prog.length;
  for (var pc = 0; pc < n; pc++) {
    showState(pc, stat);
    stat = P1(stat, prog[pc]) // 命令の実行
  }
  showState(pc, stat);
  return stat; // プログラム実行の結果
}

/*
 * マシン その2 （M2）
 * P2を使用
 */

// M2 : (Inst×Inst)^* → Stat×Stat
function M2(prog) {
  // prog : 「N, U を要素とするペア」を要素とする配列
  
  var stat1 = 0, stat2 = 0; // 初期状態
  var n = prog.length;
  var tmp; 
  for (var pc = 0; pc < n; pc++) {
    showState(pc, stat1 + ", " + stat2);
    tmp = P2([stat1, stat2], prog[pc]) // 命令の実行
    stat1 = tmp[0]; stat2 = tmp[1];
  }
  showState(pc, stat1 + ", " + stat2);
  return [stat1, stat2]; // プログラム実行の結果
}

/*
 * マシン その3 （M3）
 * P1を使用
 * 時分割方式
 */

// 2つのプログラムを互い違いに混ぜる
// 第1引数から来た要素には1、第2引数から来た要素には2の目印を付ける。
// Inst^*×Inst^* → ({1, 2}×Inst)^*
function shuffle(prog1, prog2) {
  // prog1 : N, U を要素とする配列（を想定）
  // prog2 : N, U を要素とする配列（を想定）

  var n1 = prog1.length;
  var n2 = prog2.length;
  var result = [];
  for (var i = 0; i < n1 && i < n2; i++) {
    result.push([1, prog1[i]]);
    result.push([2, prog2[i]]);
  }
  if (i < n1) {
    for (; i < n1; i++) {
      result.push([1, prog1[i]]);
    }
  }
  if (i < n2) {
    for (; i < n2; i++) {
      result.push([2, prog2[i]]);
    }
  }
  showProg(result);
  return result;
}  

// M3 : Inst^*×Ins^* → Stat×Stat
function M3(prog1, prog2) {
  // prog1 : N, U を要素とする配列
  // prog2 : N, U を要素とする配列

  var prog = shuffle(prog1, prog2);
  
  var stat1 = 0, stat2 = 0; // 初期状態
  var n = prog.length;
  var which;
  for (var pc = 0; pc < n; pc++) {
    showState(pc, stat1 + ", " + stat2);
    which = prog[pc][0];
    switch (which) {
    case 1: // stat1 を使う
      stat1 = P1(stat1, prog[pc][1]); // 命令の実行
      break;
    case 2: // stat2 を使う
      stat2 = P1(stat2, prog[pc][1]); // 命令の実行
      break;
    default:
      throw "Invalid tag"
    }
  }
  showState(pc, stat1 + ", " + stat2);
  return [stat1, stat2]; // プログラム実行の結果
}

/*
 * マシン その4 （M4）
 * P2を使用
 * 2コア機能の利用
 */

// 2つのプログラムをジップする（圧縮じゃないよ！）
// Inst^*×Inst^* → (Inst×Inst)^*
function zip(prog1, prog2) {
  // prog1 : N, U を要素とする配列（を想定）
  // prog2 : N, U を要素とする配列（を想定）

  var n = Math.max(prog1.length, prog2.length);
  var result = []
  for (var i = 0; i < n; i++) {
    result.push(
      [
	prog1[i] || N,
	prog2[i] || N
      ])
  }
  showProg(result);
  return result;
}

// M4 : Inst^*×Inst^* → Stat×Stat
function M4(prog1, prog2) {
  // prog1 : N, U を要素とする配列
  // prog2 : N, U を要素とする配列

  var prog = zip(prog1, prog2);
  var stat1 = 0, stat2 = 0; // 初期状態
  var n = prog.length;
  var tmp; 
  for (var pc = 0; pc < n; pc++) {
    showState(pc, stat1 + ", " + stat2);
    tmp = P2([stat1, stat2], prog[pc]) // 命令の実行
    stat1 = tmp[0]; stat2 = tmp[1];
  }
  showState(pc, stat1 + ", " + stat2);
  return [stat1, stat2]; // プログラム実行の結果
}

/*
 * マシン その5 （M5）
 * P2を使用
 * プログラムをマルチコア用に変換
 */

// 1つのプログラムを先頭からカップリングする
// Inst^* → (Inst×Inst)^*
function couple(prog) {
  // prog : N, U を要素とする配列（を想定）

  var n = Math.ceil(prog.length / 2);
  var result = []
  for (var i = 0; i < n; i++) {
    result.push([prog[i*2], prog[i*2 + 1] || N])
  }
  showProg(result);
  return result;
}

// 2つの結果（状態）を1つにする
// Stat×Stat → Stat
function merge(stat1, stat2) {
  // stat1 : 0, 1, 2 のいずれか（を想定）
  // stat2 : 0, 1, 2 のいずれか（を想定）

  var stat = stat1 + stat2;
  if (stat > 2) throw "Can not merge";
  return stat;
}

// M5 : Inst^* → Stat
function M5(prog) {
  // prog : N, U を要素とする配列

  var prog = couple(prog);
  var stat1 = 0, stat2 = 0; // 初期状態
  var n = prog.length;
  var tmp; 
  for (var pc = 0; pc < n; pc++) {
    showState(pc, stat1 + ", " + stat2);
    tmp = P2([stat1, stat2], prog[pc]) // 命令の実行
    stat1 = tmp[0]; stat2 = tmp[1];

  }
  showState(pc, stat1 + ", " + stat2);  
  return merge(stat1, stat2); // プログラム実行の結果
}