turing_tarpit.html

   1 <html>
   2 <title>Turing Tarpit Simulator</title>
   3 <script>
   4
   5 /* internal values for simulated computer */
   6 var ins_pointer = 0;                    /* instruction pointer */
   7 var dat_pointer = 0;                    /* data pointer */
   8 var dat_pointer_changed = 0;            /* bool set to 1 if data pointer has changed in the last step */
   9 var dat_pointer_last_address = 0;       /* address of data pointer in last step */
  10 var ram_last_address = 0;               /* address of RAM updated in last step */
  11 var breakpoints = 1;                    /* bool set to 0 to ignore breakpoints */
  12 var ram = new Array();                  /* memory of virtual machine */
  13 var jmp = new Array();                  /* used as a stack to jump from one command to another */
  14 var ins = null;                         /* current instruction from code */
  15 var halt = false;                       /* halts program ASAP */
  16
  17 /* objects that display data to the user */
  18 var disp_code;
  19 var disp_ram;
  20 var disp_ins_pointer;
  21 var disp_dat_pointer;
  22 var disp_pointer = "<div id=disp_pointer>&#8658;</div>"; /* data pointer displayed in memory block */
  23
  24 /* highlight current instruction running on machine */
  25 function code_highlight(inputEl, selStart, selEnd) {
  26         if (inputEl.setSelectionRange) {
  27                 inputEl.focus();
  28                 inputEl.setSelectionRange(selStart, selEnd);
  29         } else if (inputEl.createTextRange) {
  30                 var range = inputEl.createTextRange();
  31                 range.collapse(true);
  32                 range.moveEnd('character', selEnd);
  33                 range.moveStart('character', selStart);
  34                 range.select();
  35         }
  36 }
  37
  38 /* turns breakpoints on and off */
  39 function debug_toggle_breakpoints()
  40 {
  41         var button = document.getElementById("dbg_status");
  42         if(breakpoints) {
  43                 breakpoints=0;
  44                 button.innerHTML='<img src="http://opentextbook.info/icons/32x32/bug_delete.png">';
  45         }else {
  46                 breakpoints=1;
  47                 button.innerHTML='<img src="http://opentextbook.info/icons/32x32/bug_add.png">';
  48         }
  49 }
  50
  51 /* removes all breakpoints in source code */
  52 function debug_remove_breakpoints()
  53 {
  54         /* ask user for permission first */
  55         var ans = confirm("Permanently remove all breakpoints from code?");
  56         var code = document.getElementById("code");
  57         if(ans) { code.value = code.value.replace( /\*/g , '' ); }
  58 }
  59
  60 /* test current code character - return true if it is an instruction */
  61 /* tried to use regex on this and could not get it to work :( */
  62 function tst_inst()
  63 {
  64         if(ins == '+' ||  ins == '-' ||  ins == '>' ||  ins == '<' ||
  65           ins == '*' ||  ins == '.' ||  ins == '[' ||  ins == ']' ||  ins == ',') {
  66                 return true;
  67         }
  68         return false;
  69 }
  70
  71 /* find next instruction in code and move instruction pointer to it */
  72 function fnd_nxt_inst()
  73 {
  74         do {
  75                 if(ins_pointer > disp_code.value.length) { break; } /* must stop at end of code */
  76                 update_ins_pointer(1);
  77                 ins = disp_code.value.substring(ins_pointer-1,ins_pointer); /* get data at ins_pointer location */
  78         }while(!tst_inst());
  79         if(ins_pointer > disp_code.value.length) {
  80                 alert("HALT: Program is Complete");
  81                 halt = true;
  82                 reset();
  83         }
  84
  85         /* highlight code currently executing on screen */
  86         code_highlight(disp_code, ins_pointer-1, ins_pointer);
  87 }
  88
  89 /* find previous instruction in code and move instruction pointer to it */
  90 function fnd_prv_inst()
  91 {
  92         ins_pointer--;
  93         while(ins_pointer >= 0)
  94         {
  95                 ins = disp_code.value.substring(ins_pointer-1, ins_pointer); /* get data at ins_pointer location */
  96                 if(tst_inst()) { return; }
  97                 ins_pointer--;
  98         }
  99         if(ins_pointer == 0) {
 100                 alert("SEGFAULT: Program could not find corresponding jump instruction");
 101                 halt = true;
 102                 reset();
 103         }
 104 }
 105
 106 /* execute next instruction from input */
 107 function exe_nxt_inst()
 108 {
 109         var temp_count = 0;
 110         fnd_nxt_inst();
 111         switch(ins)
 112         {
 113                 case '+':
 114                         ram_modify(dat_pointer, 1);
 115                         break;
 116                 case '-':
 117                         ram_modify(dat_pointer, -1);
 118                         break;
 119                 case '>':
 120                         dat_point_modify(1);
 121                         break;
 122                 case '<':
 123                         dat_point_modify(-1);
 124                         break;
 125                 case '*': /* these are comments - a break from the standard language */
 126                         if(breakpoints) { stop(); }
 127                         break;
 128                 case '.':
 129                         print_mem();
 130                         break;
 131                 case '[':
 132                         jump_fwd();
 133                         break;
 134                 case ']':
 135                         jump_bak();
 136                         break;
 137                 case ',':
 138                         break;
 139                 default:
 140                         /* must be a comment :) */
 141         }
 142 }
 143
 144 /* if byte at data pointer is = 0, jump forward to instruction after matching ']' command */
 145 function jump_fwd()
 146 {
 147         if(ram[dat_pointer] != 0) { return; }
 148         /* add this jump to stack */
 149         jmp.push('[');
 150         /* loop through code, pushing and popping stack until stack is empty */
 151         while(jmp.length > 0) {
 152                 fnd_nxt_inst();
 153                 if(ins == ']') { jmp.pop();
 154                 } else if (ins == '[') { jmp.push(']'); }
 155         }
 156 }
 157
 158 /* if byte at data pointer is != 0, jump back to instruction after matching '[' command */
 159 function jump_bak()
 160 {
 161         if(ram[dat_pointer] == 0) { return; }
 162         /* add this jump to stack */
 163         jmp.push(']');
 164         /* loop through code, pushing and popping stack until stack is empty */
 165         while(jmp.length > 0 && ins_pointer > 0) {
 166                 fnd_prv_inst();
 167                 if(ins == '[') { jmp.pop();
 168                 } else if (ins == ']') { jmp.push(']'); }
 169         }
 170 }
 171
 172 /*
 173         rewind code to beginning reset all memory locations
 174         this simulates rebooting the computer
 175 */
 176 function reset()
 177 {
 178         update_ins_pointer(0);
 179         dat_point_modify(0);
 180         ram_reset();
 181         ram_highlight_clear();
 182         dat_point_highlight();
 183         document.getElementById("output_disp").innerHTML = '';
 184         document.getElementById("addr_0").innerHTML = "0" + disp_pointer;
 185         dat_point_highlight_clear();
 186 }
 187
 188 /* stop stepping through code on timer if breakpoints enabled */
 189 function stop()
 190 {
 191         halt = true;
 192 }
 193
 194 /* run through program on timer, stopping at breakpoints if enabled */
 195 function run()
 196 {
 197         var total_steps = document.getElementById("code").value.length;
 198         while(ins_pointer <= total_steps && halt == false) { step_next(); }
 199 }
 200
 201 /* step forward one instruction */
 202 function step_next()
 203 {
 204         //update_ins_pointer(1);
 205         exe_nxt_inst();
 206         dat_point_highlight();
 207 }
 208
 209 /* more back one instruction - undoes work of previous instruction */
 210 function step_back()
 211 {
 212         update_ins_pointer(-1);
 213         dat_point_highlight();
 214 }
 215
 216 /* update instruction pointer
 217         direction:
 218
 219         1 increment pointer by one
 220         0 set pointer to 0
 221         -1 decrement pointer by one
 222 */
 223 function update_ins_pointer(direction)
 224 {
 225         if(direction < 0 && ins_pointer != 0 ) { ins_pointer--; }
 226         else if (direction == 0 ) { ins_pointer = 0; }
 227         else { ins_pointer++; }
 228         disp_ins_pointer.value =  ins_pointer;
 229 }
 230
 231 /* update instruction pointer and set to new value */
 232 function ins_point_modify_by_address(val)
 233 {
 234         /* instruction pointer can never be less than 0 */
 235         if(val < 0) {
 236                 alert("Instruction Pointer cannot be set less than Zero.");
 237                 disp_ins_pointer.value =  ins_pointer; /* reset val to previous */
 238                 return;
 239         }
 240         if(val > disp_code.value.length) {
 241                 alert("Instruction Pointer cannot be set beyond end of code.\n Current length of code: " + disp_code.value.length);
 242                 disp_ins_pointer.value =  ins_pointer; /* reset val to previous */
 243                 return;
 244         }
 245         ins_pointer = disp_ins_pointer.value;
 246 }
 247
 248 /* setup virtual machine - must be called on page load */
 249 function init_form()
 250 {
 251         disp_code  = document.getElementById("code");
 252         disp_ins_pointer = document.getElementById("ins_pointer_disp");
 253         disp_dat_pointer = document.getElementById("dat_pointer_disp");
 254         disp_ram = document.getElementById("ram_disp");
 255         ram_reset();
 256         ram_init();
 257         document.getElementById("addr_0").innerHTML = "0" + disp_pointer;
 258         /* reset_output(); */
 259 }
 260
 261 /* reset all RAM to 0 */
 262 function ram_reset()
 263 {
 264         var i;
 265         for(i=0; i < 64; i++) { ram[i] = 0; }
 266 }
 267
 268 /* update highlight of one memory address and release other highlight if needed */
 269 function ram_highlight(address)
 270 {
 271         var disp_last_address = document.getElementById("ram_"+ram_last_address);
 272         /* highlight background of current address */
 273         document.getElementById("ram_"+address).style.backgroundColor = "#ff0";
 274
 275         /* remove highlight from last address modified */
 276         if(ram_last_address != address){
 277                 if(ram_last_address%2==0) {
 278                         disp_last_address.style.backgroundColor = "#fff";
 279                 } else {
 280                         disp_last_address.style.backgroundColor = "#def";
 281                 }
 282         }
 283 }
 284
 285 /* remove highlight from all memory cells regardless of current status */
 286 function ram_highlight_clear()
 287 {
 288         var i;
 289         for(i=0; i < 64; i++)
 290         {
 291                 if(i%2==0) {
 292                         document.getElementById("ram_"+i).style.backgroundColor = "#fff";
 293                 } else {
 294                         document.getElementById("ram_"+i).style.backgroundColor = "#def";
 295                 }
 296                 document.getElementById("ram_"+i).innerHTML = ram[i];
 297         }
 298 }
 299
 300 /* define RAM on screen */
 301 function ram_init()
 302 {
 303         var i;
 304         var table = "<table id=memory_table>\n";
 305         for(i=0; i < 16; i++){
 306                 if(i%2==0) {
 307                         table += "\t<tr>";
 308                 } else {
 309                         table += "\t<tr class=odd>";
 310                 }
 311                 table += "<td width='35' class=addr id=addr_"+i+">"+i+"</td><td width='35' class=ram id=ram_"+i+">";
 312                 table += ram[i]+"</td><td width='35' class=addr id=addr_"+(i+16)+">";
 313                 table += (i+16)+"</td><td class=ram id=ram_"+(i+16)+">"+ram[i+16]+"</td>\n";
 314                 table += "<td class=addr id=addr_"+(i+32)+">"+(i+32)+"</td><td width='35' class=ram id=ram_";
 315                 table += (i+32)+">"+ram[i+32]+"</td><td class=addr id=addr_";
 316                 table += (i+48)+">"+(i+48)+"</td><td width='35' class=ram id=ram_"+(i+48)+">"+ram[i+48]+"</td></tr>\n";
 317         }
 318         table +=  "</table>\n";
 319         disp_ram.innerHTML = table;
 320 }
 321
 322 /*
 323         modify the value at this address - reset RAM highlights for all addresses
 324         1 increment RAM by one
 325         0 set RAM to 0
 326         -1 decrement RAM by one
 327 */
 328 function ram_modify(address, change)
 329 {
 330         if(address < 0 || address > 63) {
 331                 alert("SEGFAULT: Cannot Modify Data Outside of Memory Range");
 332                 halt = true;
 333                 reset();
 334                 return;
 335         }
 336
 337         if (change > 0 ) {
 338                 ram[address]++;
 339         } else if(change < 0 ) {
 340                 ram[address]--;
 341         } else {
 342                 ram[address] = 0;
 343         }
 344         ram_highlight(address);
 345         document.getElementById("ram_"+address).innerHTML = ram[address];
 346         ram_last_address = address;
 347 }
 348
 349 /*
 350         modify state of data pointer
 351         1 increment data pointer by one
 352         0 set data pointer to 0
 353         -1 decrement data pointer by one
 354
 355 */
 356 function dat_point_modify(change)
 357 {
 358         dat_pointer_last_address = dat_pointer;
 359         if (change > 0 ) {
 360                 dat_pointer++;
 361         } else if(change < 0 ) {
 362                 /* could put SEGFAULT here, but C does not have a check for this, so neither will I ;) */
 363                 dat_pointer--;
 364         } else {
 365                 dat_pointer = 0;
 366         }
 367
 368         /* place '>' char next to memory address in table */
 369         if(dat_pointer >= 0 && dat_pointer < 64) {
 370                 document.getElementById("addr_"+dat_pointer).innerHTML = dat_pointer + disp_pointer;
 371         }
 372
 373         /* remove '>' char next to memory address in table */
 374         if(dat_pointer_last_address >= 0 && dat_pointer_last_address < 64) {
 375                 document.getElementById("addr_"+dat_pointer_last_address).innerHTML = dat_pointer_last_address;
 376         }
 377
 378         disp_dat_pointer.value = dat_pointer;
 379         dat_pointer_changed = 1;
 380 }
 381
 382 function dat_point_modify_by_address(val)
 383 {
 384         dat_pointer_last_address = dat_pointer;
 385         dat_pointer = disp_dat_pointer.value;
 386         /* place '>' char next to memory address in table */
 387         if(dat_pointer >= 0 && dat_pointer < 64) {
 388                 document.getElementById("addr_"+dat_pointer).innerHTML = dat_pointer + disp_pointer;
 389         }
 390
 391         /* remove '>' char next to memory address in table */
 392         if(dat_pointer_last_address >= 0 && dat_pointer_last_address < 64) {
 393                 document.getElementById("addr_"+dat_pointer_last_address).innerHTML = dat_pointer_last_address;
 394         }
 395         dat_pointer_changed = 1;
 396         dat_point_highlight();
 397 }
 398
 399 /* turns on and off data pointer highlight if it has changed this step */
 400 function dat_point_highlight()
 401 {
 402         if(dat_pointer_changed) {
 403                 disp_dat_pointer.style.backgroundColor = "#ff0";
 404                 dat_pointer_changed = 0;
 405         } else {
 406                 disp_dat_pointer.style.backgroundColor = "#fff";
 407         }
 408
 409         /* as a convenience to the user, set to red if pointer is out of memory range */
 410         if(dat_pointer < 0 || dat_pointer > 63) {
 411                 disp_dat_pointer.style.backgroundColor = "#f00";
 412         }
 413 }
 414
 415 /* remove highlight from data pointer */
 416 function dat_point_highlight_clear()
 417 {
 418         disp_dat_pointer.style.backgroundColor = "#fff";
 419 }
 420
 421 /* print ASCII representation of memory at data pointer */
 422 function print_mem()
 423 {
 424         var x = String.fromCharCode(63+ram[dat_pointer]);
 425         document.getElementById("output_disp").innerHTML += x;
 426 }
 427
 428 </script>
 429
 430 <style type="text/css">
 431
 432 body {
 433         font-family: Tahoma, Arial, Helvetica, sans-serif;
 434 }
 435
 436 #disp_pointer {
 437         float:right;
 438         color: #f00;
 439 }
 440
 441 #code_buttons {
 442         position: absolute;
 443         top: 570px;
 444         left: 10px;
 445 }
 446
 447 #input_banner {
 448         position: absolute;
 449         top: 120px;
 450         left: 10px;
 451 }
 452
 453 #da_banner {
 454         position: absolute;
 455         top: 450px;
 456         left: 625px;
 457 }
 458
 459 #ip_banner {
 460         position: absolute;
 461         top: 400px;
 462         left: 625px;
 463 }
 464
 465 #output_banner {
 466         position: absolute;
 467         top: 120px;
 468         left: 625px;
 469 }
 470
 471 #memory_banner {
 472         position: absolute;
 473         top: 120px;
 474         left: 315px;
 475 }
 476
 477 #input {
 478         position: absolute;
 479         top: 140px;
 480         left: 10px;
 481 }
 482
 483 #ram_disp {
 484         position: absolute;
 485         top: 140px;
 486         left: 315px;
 487 }
 488
 489 #memory_table {
 490         border:1px solid #000;
 491         border-collapse: collapse;
 492 }
 493
 494 td {
 495         padding: 5px;
 496         border-bottom:1px solid #000;
 497 }
 498
 499 .odd {
 500         background-color: #def;
 501 }
 502 .odd td {
 503         border-bottom: 1px solid #000;
 504 }
 505
 506 .addr {
 507         color: #00f;
 508 }
 509
 510 .ram {
 511         border-right:1px solid #000;
 512 }
 513
 514 #output {
 515         position: absolute;
 516         top: 140px;
 517         left: 625px;
 518 }
 519
 520 #instruction {
 521         position: absolute;
 522         top: 425px;
 523         left: 625px;
 524 }
 525
 526 #data {
 527         position: absolute;
 528         top: 475px;
 529         left: 625px;
 530
 531 }
 532
 533 </style>
 534 <body onLoad="init_form();">
 535
 536 <center><h2>Turing Tarpit Simulator</h2></center>
 537
 538 <center>
 539 <button onClick='reset();'><img src="http://opentextbook.info/icons/32x32/resultset_first.png"></button>
 540 &nbsp;&nbsp;
 541 <button onClick='step_back();'><img src="http://opentextbook.info/icons/32x32/resultset_previous.png"></button>
 542 &nbsp;&nbsp;
 543 <button onClick='step_next();'><img src="http://opentextbook.info/icons/32x32/resultset_next.png"></button>
 544 &nbsp;&nbsp;
 545 <button onClick='run();'><img src="http://opentextbook.info/icons/32x32/resultset_last.png"></button>
 546 &nbsp;&nbsp;
 547 <button onClick='halt();'><img src="http://opentextbook.info/icons/32x32/cancel.png"></button>
 548 &nbsp;&nbsp;
 549 <button disabled><img src="http://opentextbook.info/icons/32x32/disk.png"></button>
 550 </center>
 551
 552 <div id="code_buttons">
 553 <button id="dbg_status" onClick='debug_toggle_breakpoints();'>
 554         <img src="http://opentextbook.info/icons/32x32/bug_add.png">
 555 </button>
 556 &nbsp;&nbsp;
 557 <button id="dbg_status" onClick='debug_remove_breakpoints();'>
 558         <img src="http://opentextbook.info/icons/32x32/bin.png">
 559 </button>
 560 </div>
 561
 562 <div id="input_banner">INPUT</div>
 563 <div id="input"><textarea id="code" rows="27" cols="38"></textarea></div>
 564
 565 <div id="ip_banner">INSTRUCTION POINTER</div>
 566 <div id="instruction"><input  onBlur="ins_point_modify_by_address(disp_ins_pointer.value);" id="ins_pointer_disp" type="text" diabled value=0></div>
 567
 568 <div id="da_banner">DATA POINTER</div>
 569 <div id="data"><input onBlur="dat_point_modify_by_address(disp_dat_pointer.value);" id="dat_pointer_disp" type="text" diabled value=0></div>
 570
 571 <div id="memory_banner">MEMORY</div>
 572 <div id="ram_disp"></div>
 573 <div id="output_banner">OUTPUT</div>
 574 <div id="output">
 575 <textarea name=code id=output_disp rows="15" cols="38" disabled ></textarea>
 576 </div>
 577
 578 </body>
 579 </html>
 580