<p>What do you mean by the ‘computational model’ of a programming language?</p>
<p>Are ‘abstract machines’ such as Stack, RAM, and <em>Warren Abstract Machine (WAM)</em> examples of computational models?</p>
<p>Is the <em>computational model</em> related to the <em>operational semantics</em> of a programming language?</p>
<p>I’ve seen answers here link the ‘computational model’ and ‘operational semantics’.</p>
<p>PS I have one PL textbook that is pretty recent(PLAI) but it doesn’t mention computational model at all - so any text recommendations would be appreciated.</p>

<language-design><language-comparison>
What do you mean by the ‘computational model’ of a programming language?
CC BY-SA 4.0
2024-01-07T20:42:15.050Z
Can you give an example of where you see the phrase "computational model" being used? I don't find anything searching that exact phrase here.
David Young
CC BY-SA 4.0
2024-01-07T20:51:25.303Z
“Simultaneously to the notion of FRP, Hughes [1991] developed the notion of Arrows, a restricted computational model consisting of reified functions joined together by combinators.” - https://felleisen.org/matthias/7480-s21/lectures.html - sorry this is the first use I could find
Stephen
CC BY-SA 4.0
2024-01-07T21:15:36.220Z
I doubt that there's a single, specific meaning for that phrase. But someone who is more familiar with this should answer. To me, it means something like "the fundamental abstractions that the language/DSL is built upon." That is close to "abstract machine" but maybe a bit more, well, abstract and high-level. Another similar instance of that phrase being used is in [The Art of the Propagator](https://dspace.mit.edu/handle/1721.1/44215), describing how you can build programs out of "propagators" (a sort of cell that gains information over time which can be combined into highly concurrent nets)
David Young
CC BY-SA 4.0
2024-01-08T00:05:25.903Z
I’ve found https://www.tutorialspoint.com/what-are-the-basic-computational-models and https://www.tutorialspoint.com/what-is-computational-model - but these resources sadly lack any references.
Stephen
CC BY-SA 4.0
2024-01-08T01:59:59.340Z
Is it helpful to rephrase the term as "model of computation", which means no more or less than what those words all mean on their own? Or are you looking for something more specific somehow, and if so, what? Who is "you" in the question?
Michael Homer
CC BY-SA 4.0
2024-01-13T00:25:44.780Z
I don't think either had a clear definition, but are you asking about computational model (or [model of computation](https://en.wikipedia.org/wiki/Model_of_computation)), or you already know that, but only asking about how it is used for a programming language?
user23013
CC BY-SA 4.0
2024-01-18T00:07:09.800Z
I'm surprised this question still has no answer. I'm tempted to write up a bad answer in hopes someone will correct it.
kouta-kun
CC BY-SA 4.0
2024-01-26T16:42:11.990Z
I think this definition is probably about as good as it gets (from Andrej Bauer's [currently unfinished monograph on realizability](https://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf)): "A *model of computation* describes what computation is and how it is done." This is from the start of Chapter 2 which is titled "Models of Computation".
David Young
<p>The term Computational Model (hereafter, CM) in general (outside the specific context you specified, that is &quot;the CM of the programming language&quot;):</p>
<p>In <strong>Introduction of theory of comptutation</strong>, by Michael Sipser it is said:</p>
<blockquote>
<p>The theory of computation begins with a question: What is a computer? It is
perhaps a silly question, as everyone knows that this thing I type on is a computer. But these real computers are quite complicated-too much so to allow usto set up a manageable mathematical theory of them directly.
Instead we use an idealized computer called a computational model.</p>
</blockquote>
<p>In this book Automata and Pushdown Automata are two examples of that conceptual tool he calls CM.
He says later:</p>
<blockquote>
<p>All reasonable deterministic computational models are polynomially equivalent. That is, any one of them can simulate another with only a polynomial increase in running time.</p>
</blockquote>
<p>Which is a well known argument that comes from Church and Touring in person.</p>
<p>In <strong>Semistructured Computation</strong>, by the brillant Luca Cardelli (in the conclusions of his discourse) it is said:</p>
<blockquote>
<p>From our point of view, we have discovered that the Ambient Calculus can be seen as a computational model over semistructured data.</p>
</blockquote>
<p>If I'm not wrong he affirms that &quot;a calculus can be a CM&quot;.</p>
<p>In <strong>Algorithms and Theory of Computation handbook</strong>, by Mikhail J, Atallah:</p>
<blockquote>
<p>The seed of computational complexity is the formalization of the concept of an algorithm. Algorithms in turn must be planted in some computational model, ideally one that abstracts important features of real computing machines and processes.</p>
</blockquote>
<p>In <strong>Computational Modeling and Complexity Science</strong>, by Allen Downey:</p>
<blockquote>
<p>Computational modeling: A model is a simplified description of a system that is useful for simulation or analysis. Computational models are designed to take advantage of cheap, fast computation.</p>
</blockquote>
<p>Maybe this is is the most clean, linear and simple explanation of CM.</p>
<p>But you was talking of CM <strong>in the programming language</strong>.
Well, the mention Sipser made about the equivalence of all CM is what we developers usually say about the idem-potence of programming languages.</p>
<p>I mean that there is a substantial equivalence between CM (in its own) and CM in the context of programming language. They are the same thing (at least IMHO).</p>
<p><strong>EDIT</strong></p>
<p>Sorry: forgot to mention Peter Wegner!</p>
<p>An interesting point of view about computational models paradigms is the one elaborated by him, who worked (among many other things) in the field of <strong>interactive vs. algorithmic computing</strong>.</p>
<p><strong>Why Interaction is More Powerful Than Algorithms</strong> by Peter Wegner:</p>
<blockquote>
<p>Interactive models of computation provide a unifying conceptual framework that captures changes in computer architecture, software engineering, and AI in the last quarter of the 20th century.</p>
</blockquote>

CC BY-SA 4.0
2024-06-20T13:40:22.713Z
2024-06-22T10:06:45.037Z
2024-06-22T10:06:45.037Z
pber
# What do you mean by the ‘computational model’ of a programming language?
Posted by: username_0 on 2024-01-07
What do you mean by the ‘computational model’ of a programming language?

Are ‘abstract machines’ such as Stack, RAM, and *Warren Abstract Machine (WAM)* examples of computational models?

Is the *computational model* related to the *operational semantics* of a programming language?

I’ve seen answers here link the ‘computational model’ and ‘operational semantics’.

PS I have one PL textbook that is pretty recent(PLAI) but it doesn’t mention computational model at all - so any text recommendations would be appreciated.
**Tags:** language-design language-comparison
> **Comments:**
> **username_1**: Can you give an example of where you see the phrase "computational model" being used? I don't find anything searching that exact phrase here.  
> **username_0**: “Simultaneously to the notion of FRP, Hughes [1991] developed the notion of Arrows, a restricted computational model consisting of reified functions joined together by combinators.” - https://felleisen.org/matthias/7480-s21/lectures.html - sorry this is the first use I could find  
> **username_1**: I doubt that there's a single, specific meaning for that phrase. But someone who is more familiar with this should answer. To me, it means something like "the fundamental abstractions that the language/DSL is built upon." That is close to "abstract machine" but maybe a bit more, well, abstract and high-level. Another similar instance of that phrase being used is in [The Art of the Propagator](https://dspace.mit.edu/handle/1721.1/44215), describing how you can build programs out of "propagators" (a sort of cell that gains information over time which can be combined into highly concurrent nets)  
> **username_0**: I’ve found https://www.tutorialspoint.com/what-are-the-basic-computational-models and https://www.tutorialspoint.com/what-is-computational-model - but these resources sadly lack any references.  
> **username_2**: Is it helpful to rephrase the term as "model of computation", which means no more or less than what those words all mean on their own? Or are you looking for something more specific somehow, and if so, what? Who is "you" in the question?  
> **username_3**: I don't think either had a clear definition, but are you asking about computational model (or [model of computation](https://en.wikipedia.org/wiki/Model_of_computation)), or you already know that, but only asking about how it is used for a programming language?  
> **username_4**: I'm surprised this question still has no answer. I'm tempted to write up a bad answer in hopes someone will correct it.  
> **username_1**: I think this definition is probably about as good as it gets (from Andrej Bauer's [currently unfinished monograph on realizability](https://www.andrej.com/zapiski/MGS-2022/notes-on-realizability.pdf)): "A *model of computation* describes what computation is and how it is done." This is from the start of Chapter 2 which is titled "Models of Computation".  
---
## 1 answers
### Answer by username_5 on 2024-06-20. Score: 4
The term Computational Model (hereafter, CM) in general (outside the specific context you specified, that is "the CM of the programming language"):

In **Introduction of theory of comptutation**, by Michael Sipser it is said:

> The theory of computation begins with a question: What is a computer? It is
> perhaps a silly question, as everyone knows that this thing I type on is a computer. But these real computers are quite complicated-too much so to allow usto set up a manageable mathematical theory of them directly.
> Instead we use an idealized computer called a computational model.

In this book Automata and Pushdown Automata are two examples of that conceptual tool he calls CM.
He says later:

> All reasonable deterministic computational models are polynomially equivalent. That is, any one of them can simulate another with only a polynomial increase in running time.

Which is a well known argument that comes from Church and Touring in person.

In **Semistructured Computation**, by the brillant Luca Cardelli (in the conclusions of his discourse) it is said:

> From our point of view, we have discovered that the Ambient Calculus can be seen as a computational model over semistructured data.

If I'm not wrong he affirms that "a calculus can be a CM".

In **Algorithms and Theory of Computation handbook**, by Mikhail J, Atallah:

> The seed of computational complexity is the formalization of the concept of an algorithm. Algorithms in turn must be planted in some computational model, ideally one that abstracts important features of real computing machines and processes.

In **Computational Modeling and Complexity Science**, by Allen Downey:

> Computational modeling: A model is a simplified description of a system that is useful for simulation or analysis. Computational models are designed to take advantage of cheap, fast computation.

Maybe this is is the most clean, linear and simple explanation of CM.

But you was talking of CM **in the programming language**.
Well, the mention Sipser made about the equivalence of all CM is what we developers usually say about the idem-potence of programming languages.

I mean that there is a substantial equivalence between CM (in its own) and CM in the context of programming language. They are the same thing (at least IMHO).

**EDIT**

Sorry: forgot to mention Peter Wegner!

An interesting point of view about computational models paradigms is the one elaborated by him, who worked (among many other things) in the field of **interactive vs. algorithmic computing**.

**Why Interaction is More Powerful Than Algorithms** by Peter Wegner:

> Interactive models of computation provide a unifying conceptual framework that captures changes in computer architecture, software engineering, and AI in the last quarter of the 20th century.
---
