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}
}