Published in Volume XXII, Issue 2, 2012, pages 253-265, doi: 10.7561/SACS.2012.2.253

Authors: J.A. Bergstra, C.A. Middelburg

Abstract

Instruction sequences with direct and indirect jump instructions are as expressive as instruction sequences with direct jump instructions only. We show that, in the case where the number of instructions is not bounded, we are faced with increases of the maximal internal delays of instruction sequences on execution that are not bounded by a linear function if we strive for acceptable increases of the lengths of instruction sequences on elimination of indirect jump instructions.

Full Text (PDF)

References

[1] J. A. Bergstra and M. E. Loots. Program algebra for sequential code. Journal of Logic and Algebraic Programming, 51(2):125-156, 2002. http://dx.doi.org/10.1016/S1567-8326(02)00018-8 .

[2] J. A. Bergstra and C. A. Middelburg. Instruction sequences with indirect jumps. Scienti c Annals of Computer Science, 17:19-46, 2007.

[3] J. A. Bergstra and C. A. Middelburg. Instruction sequence notations with probabilistic instructions. arXiv:0906.3083v1 [cs.PL], June 2009.

[4] J. A. Bergstra and C. A. Middelburg. On the expressiveness of single-pass instruction sequences. Theory of Computing Systems, 50(2):313-328, 2012. http://dx.doi.org/10.1007/s00224-010-9301-8 .

[5] J. A. Bergstra and A. Ponse. Combining programs and state machines. Journal of Logic and Algebraic Programming, 51(2):175-192, 2002. http://dx.doi.org/10.1016/S1567-8326(02)00020-6 .

[6] J. A. Bergstra and M. B. van der Zwaag. Mechanistic behavior of single- pass instruction sequences. arXiv:0809.4635v1 [cs.PL], September 2008.

[7] J. Gosling, B. Joy, G. Steele, and G. Bracha. The Java Language Speci cation. Addison-Wesley, Reading, MA, second edition, 2000.

[8] A. Hejlsberg, S. Wiltamuth, and P. Golde. C# Language Speci cation. Addison-Wesley, Reading, MA, 2003.

[9] S. H. P. Schroevers. Expressiveness and extensions of an instruction sequence semigroup. arXiv:1003.1572v1 [cs.PL], March 2010.

Bibtex

@article{sacscuza:bergstra2012ijiisp,
  title={Indirect Jumps Improve Instruction Sequence Performance},
  author={J.A. Bergstra and C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={22},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2012},
  pages={253--265},
  doi={10.7561/SACS.2012.2.253},
  publisher={``A.I. Cuza'' University Press}
}