Programs=data=first-class citizens in a computational world
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Programs=data=first-class citizens in a computational world. / Jones, Neil; Simonsen, Jakob Grue.
In: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Vol. 370, No. 1971, 2012, p. 3305-3318.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Programs=data=first-class citizens in a computational world
AU - Jones, Neil
AU - Simonsen, Jakob Grue
PY - 2012
Y1 - 2012
N2 - From a programming perspective, Alan Turing's epochal 1936 paper on computable functions introduced several new concepts, including what is today known as self-interpreters and programs as data, and invented a great many now-common programming techniques. We begin by reviewing Turing's contribution from a programming perspective; and then systematize and mention some of the many ways that later developments in models of computation (MOCs) have interacted with computability theory and programming language research. Next, we describe the ‘blob’ MOC: a recent stored-program computational model without pointers. In the blob model, programs are truly first-class citizens, capable of being automatically compiled, or interpreted, or executed directly. Further, the blob model appears closer to being physically realizable than earlier computation models. In part, this is due to strong finiteness owing to early binding in the program; and a strong adjacency property: the active instruction is always adjacent to the piece of data on which it operates. The model is Turing complete in a strong sense: a universal interpretation algorithm exists that is able to run any program in a natural way and without arcane data encodings. Next, some of the best known among the numerous existing MOCs are described, and we develop a list of traits an ‘ideal’ MOC should possess from our perspective. We make no attempt to consider all models put forth since Turing's 1936 paper, and the selection of models covered concerns only models with discrete, atomic computation steps. The next step is to classify the selected models by qualitative rather than quantitative features. Finally, we describe how the blob model differs from an ‘ideal’ MOC, and identify some natural next steps to achieve such a model.
AB - From a programming perspective, Alan Turing's epochal 1936 paper on computable functions introduced several new concepts, including what is today known as self-interpreters and programs as data, and invented a great many now-common programming techniques. We begin by reviewing Turing's contribution from a programming perspective; and then systematize and mention some of the many ways that later developments in models of computation (MOCs) have interacted with computability theory and programming language research. Next, we describe the ‘blob’ MOC: a recent stored-program computational model without pointers. In the blob model, programs are truly first-class citizens, capable of being automatically compiled, or interpreted, or executed directly. Further, the blob model appears closer to being physically realizable than earlier computation models. In part, this is due to strong finiteness owing to early binding in the program; and a strong adjacency property: the active instruction is always adjacent to the piece of data on which it operates. The model is Turing complete in a strong sense: a universal interpretation algorithm exists that is able to run any program in a natural way and without arcane data encodings. Next, some of the best known among the numerous existing MOCs are described, and we develop a list of traits an ‘ideal’ MOC should possess from our perspective. We make no attempt to consider all models put forth since Turing's 1936 paper, and the selection of models covered concerns only models with discrete, atomic computation steps. The next step is to classify the selected models by qualitative rather than quantitative features. Finally, we describe how the blob model differs from an ‘ideal’ MOC, and identify some natural next steps to achieve such a model.
U2 - 10.1098/rsta.2011.0328
DO - 10.1098/rsta.2011.0328
M3 - Journal article
C2 - 22711860
VL - 370
SP - 3305
EP - 3318
JO - Philosophical transactions. Series A, Mathematical, physical, and engineering sciences
JF - Philosophical transactions. Series A, Mathematical, physical, and engineering sciences
SN - 1364-503X
IS - 1971
ER -
ID: 45487997