<p>Imperative programs are typically interpreted in domains, which are a special kind of topological space. The axioms of domains are not usually given in algebraic form, since the operations on domains include taking limits of chains, which is a non-finitary operation. But most applications of domains only need limits of $\omega$-chains, so it may be possible to describe them categorically with a generalization of the concept of algebraic theory, in terms of "locally presentable categories". However, this is a bit of category theory which is really a step beyond my knowledge, and I can't really tell you for sure either way. </p>

<p>Specifications about imperative programs are typically given via Hoare logic. Michael B. Smyth wrote an (IMO) very readable article on the topological semantics of specifications in 1983. </p>

<p>Michael B. Smyth: Power Domains and Predicate Transformers: A Topological View. ICALP 1983: 662-675</p>

<p>He also wrote the chapter "Topology", for the Handbook of Logic in Computer Science, Vol I. I have not read this chapter myself, but it is very widely cited.</p>

CC BY-SA 3.0
2011-07-28T15:06:18.300Z
I do not know much about semantics yet. If I understand correctly, a domain is where states are in.
Though programs and states are closely related, I think the structure of a program space is different 
from that of a domain.  However, the references are also interesting. Thanks!
Yuning
CC BY-SA 3.0
2011-07-25T10:24:14.487Z
2011-07-25T10:24:14.487Z
Neel Krishnaswami
<p><a href="http://www.cs.ox.ac.uk/files/3223/PRG03.pdf" rel="nofollow"><em>The Lattice of Flow Diagrams</em></a>, Dana Scott, Programming Research Group report 03, Oxford University, 1969.</p>

<p>Flow diagram = Control flow graph. Another viewpoint is of  imperative programs as generators of possibly infinite transition systems. The transition systems will form a coalgebra.</p>

<p><em><a href="http://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf" rel="nofollow">Introduction to Coalgebra. Towards Mathematics of States and Observation</a>,</em> Bart Jacobs. </p>

<p>Artem's comment and Neel's answer provide further possibilities. There are many answers to this question depending on what you mean by imperative program and what properties are of interest. Do you care only about syntactic objects or some underlying semantic notion? Even if you only care about, say, control flow graphs, there is a difference between arbitrary flow graphs and those generated by standard structured programming constructs (the latter are reducible). These properties in turn affect the mathematical structure of the space involved.</p>

CC BY-SA 3.0
2011-08-03T05:31:48.277Z
The lattice of flow diagrams is about relation of approximations of programs, so there seems to be more objects involved than necessary. Nevertheless, the idea is inspiring to me.
Yuning
CC BY-SA 3.0
2011-08-04T01:21:35.370Z
Maybe when you see a few different models, you will know what it is you want in your lattice. If I recall, Dana Scott says something like: There are many elements in the lattice. If you ignore them, it is your loss, not theirs.
Vijay D
CC BY-SA 3.0
2013-10-19T21:33:32.393Z
I like it. It appears following the mentioning of _transcendental_ elements: "They are there, in any case. If you do not care to look at them, you need not do so. It will be your loss not theirs."
Yuning
CC BY-SA 3.0
2011-07-25T11:08:06.730Z
2011-07-25T11:08:06.730Z
Vijay D
<p>Consider the space of all imperative programs.</p>

<ol>
<li>From the view of mathematical analysis, what kind of space is it?</li>
<li>Is it an algebraic structure?</li>
</ol>

<p>Please also give references.</p>

<p>Editing of the question is welcome.</p>

CC BY-SA 3.0
2011-07-25T09:51:52.797Z
how is the space of imperative programs different from the space of programs? or the space of Turing Machines? What special feature of imperative programs do you want the answer to be mindful of. Also, a google search produces: http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7251
Artem Kaznatcheev
CC BY-SA 3.0
2011-07-26T04:13:14.487Z
I am more familiar with imperative programs, and I want to be specific when asking.

I have got an (incorrect?) impression that declarative programs(functional, logic) show better properties.

Of course, it would be even better if there is a generic answer to this question.

Thank you for the book recommendation.
Yuning
<reference-request>
Space of Imperative Programs
Yuning
# Space of Imperative Programs

(Asked by: username_0 on 2011-07-25)

Consider the space of all imperative programs.

1. From the view of mathematical analysis, what kind of space is it?
2. Is it an algebraic structure?

Please also give references.

Editing of the question is welcome.

**Tags:** reference-request
> **Comments:**
> **username_1**: how is the space of imperative programs different from the space of programs? or the space of Turing Machines? What special feature of imperative programs do you want the answer to be mindful of. Also, a google search produces: http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7251  
> **username_0**: I am more familiar with imperative programs, and I want to be specific when asking.  I have got an (incorrect?) impression that declarative programs(functional, logic) show better properties.  Of course, it would be even better if there is a generic answer to this question.  Thank you for the book recommendation.  

---

## 2 answers

### Answer by username_3 on 2011-07-25. Score: 7 | Accepted answer

[*The Lattice of Flow Diagrams*](http://www.cs.ox.ac.uk/files/3223/PRG03.pdf), Dana Scott, Programming Research Group report 03, Oxford University, 1969.

Flow diagram = Control flow graph. Another viewpoint is of imperative programs as generators of possibly infinite transition systems. The transition systems will form a coalgebra.

*[Introduction to Coalgebra. Towards Mathematics of States and Observation](http://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf),* Bart Jacobs.

Artem's comment and Neel's answer provide further possibilities. There are many answers to this question depending on what you mean by imperative program and what properties are of interest. Do you care only about syntactic objects or some underlying semantic notion? Even if you only care about, say, control flow graphs, there is a difference between arbitrary flow graphs and those generated by standard structured programming constructs (the latter are reducible). These properties in turn affect the mathematical structure of the space involved.

> **Comments:**
> **username_0**: The lattice of flow diagrams is about relation of approximations of programs, so there seems to be more objects involved than necessary. Nevertheless, the idea is inspiring to me.  
> **username_3**: Maybe when you see a few different models, you will know what it is you want in your lattice. If I recall, Dana Scott says something like: There are many elements in the lattice. If you ignore them, it is your loss, not theirs.  
> **username_0**: I like it. It appears following the mentioning of _transcendental_ elements: "They are there, in any case. If you do not care to look at them, you need not do so. It will be your loss not theirs."  

---

### Answer by username_2 on 2011-07-25. Score: 6

Imperative programs are typically interpreted in domains, which are a special kind of topological space. The axioms of domains are not usually given in algebraic form, since the operations on domains include taking limits of chains, which is a non-finitary operation. But most applications of domains only need limits of $\omega$-chains, so it may be possible to describe them categorically with a generalization of the concept of algebraic theory, in terms of "locally presentable categories". However, this is a bit of category theory which is really a step beyond my knowledge, and I can't really tell you for sure either way.

Specifications about imperative programs are typically given via Hoare logic. Michael B. Smyth wrote an (IMO) very readable article on the topological semantics of specifications in 1983.

Michael B. Smyth: Power Domains and Predicate Transformers: A Topological View. ICALP 1983: 662-675

He also wrote the chapter "Topology", for the Handbook of Logic in Computer Science, Vol I. I have not read this chapter myself, but it is very widely cited.

> **Comments:**
> **username_0**: I do not know much about semantics yet. If I understand correctly, a domain is where states are in. Though programs and states are closely related, I think the structure of a program space is different  from that of a domain.  However, the references are also interesting. Thanks!  

---

