<p><strong>Joy</strong> comes to mind. It's a simple concatenative language that involves manipulations on a stack. It's essentially a reverse Polish notation for combinatory logic with quoting, developed by a professor of logic and programming so presumably it was taught in class. :)</p>

<p>I'm not 100% sure what qualifies as as denotational semantics, but, there is an algebra for it:</p>

<p><a href="http://www.kevinalbrecht.com/code/joy-mirror/j04alg.html" rel="nofollow">http://www.kevinalbrecht.com/code/joy-mirror/j04alg.html</a></p>

CC BY-SA 3.0
2013-05-03T21:39:58.467Z
2013-05-03T21:39:58.467Z
tangentstorm
<p>David Schmidt's tutorial on <a href="http://people.cis.ksu.edu/~schmidt/papers/CRC.chapter.ps.gz" rel="nofollow">Programming language semantics</a> survey semantics methods then provides a fully detailed denotational semantics for a toy imperative language. 
You may have additional fun playing with a <a href="http://liris.cnrs.fr/romuald.thion/files/Ressources/Prog/Haskell/Schmidt/" rel="nofollow">naive Naskell interpreter</a> for the language.</p>

CC BY-SA 3.0
2013-05-04T11:03:05.370Z
2013-05-04T11:03:05.370Z
Romuald
<p>I would not know what toy language is often used. I can point to a language that was used. A very early example : <em>A Complete Machine-checked Definition of a Simple Programming Language Using Denotational Semantics</em> -
Véronique Donzeau-Gouge, Gilles Kahn, Bernard Lang
RR-330 IRIA-Laboria, 1978, 31 pages.
<a href="ftp://ftp.inria.fr/INRIA/Projects/Atoll/croap/ASPLE-semantics.pdf" rel="nofollow">ftp://ftp.inria.fr/INRIA/Projects/Atoll/croap/ASPLE-semantics.pdf</a><br>
It may be too old for your taste, particularly in style.</p>

<p>It was done at the time in preparation for the formal semantics of the Ada programming language. But I guess the denotational semantics of Ada would be too large for your purpose
(I think it was published too).</p>

CC BY-SA 3.0
2013-05-23T21:23:01.263Z
2013-05-23T21:23:01.263Z
babou
<p>Please forgive my arrogance, as I post so insubstantial answer. However, it may be helpful - if the case is teaching the idea of programming languages - and comments are to narrow.</p>

<p>I deeply believe, the tactic of teaching is more important, then choosing the simplest language. My classes (being a student) of programming languages involved the <em>while language</em>, which, I purpose, is more complex then <em>PFC</em>. However, in the end, the students was able to do some simple inductive proofs about while-programs, and build interpreters for a small statically-typed objective-functional-imperative cross language. Even though, they were of the first year. - I think the organization of the material and incremental going from formal grammars, through ASTs, static analyses, fixed points to semantics, Hoare logic and little lambda calculus, together with implementation of own interpreter have done the job pretty well.</p>

<p><strong>Edit:</strong><br>
The $while$ languages are generally - at least in my villagy surroundings -  minimalistic derivations of IMP, containing the $while$ instruction. - Maybe this is local. If so, I should probably ask for forgiveness for my arrogance and ignorance, either. $:-)$</p>

<p>A good reference, for this case, can be <em>CS522 - Programming Language Semantics (Spring 2011)</em> lecture notes. - Especially this, if we are into the denotational semantics  <a href="http://fsl.cs.uiuc.edu/images/4/45/CS522-Spring-2011-PL-book-denotational.pdf" rel="nofollow">http://fsl.cs.uiuc.edu/images/4/45/CS522-Spring-2011-PL-book-denotational.pdf</a></p>

CC BY-SA 3.0
2013-05-18T08:54:44.053Z
You might want to include in your answer a well-chosen reference for the While language: I did not know it and had to google it (found http://www.program-analysis.com/while.html interesting but it might not be the best reference).
J.y B.y
CC BY-SA 3.0
2013-05-17T13:56:51.047Z
2013-05-18T11:22:10.027Z
2013-05-18T11:22:10.027Z
Number47
<p>What is a simple toy research programming language that has simple denotational semantics (including numbers or reals) that is used often to demonstrate certain properties of programming languages, or other things?</p>

<p>I am looking to demonstrate an idea on a programming language, and I don't want it to be complex in syntax, and I also want it to have easy to understand denotational semantics.</p>

<p>I don't need a working implementation of the language. Just the syntax and denotational semantics for the syntax.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2013-05-03T18:49:36.997Z
PCF springs to mind. http://en.wikipedia.org/wiki/Programming_Computable_Functions. However, bear in mind that there are hundreds of such languages, which may be more or less suited to your needs.
cody
CC BY-SA 3.0
2013-05-03T18:59:56.717Z
As Cody points out, PCF, especially its call-by-value version, is often used, although if by denotational semantics you mean order-theoretic semantics, you'd be out of luck. Alternatively, you can use a traditional `while` language, e.g. that of Hoare's famous paper [An axiomatic basis for computer programming](http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf). If you don't need non-termination, you can use a typed $\lambda$-calculus. The (asynchronous) $\pi$-calculus is an especially beautiful and widely used toy language. Finally, why don't you invent a language that suits your purpose?
Martin Berger
CC BY-SA 3.0
2013-05-04T17:59:45.487Z
Perhaps if you state briefly what you want this for, then we can provide better answers.
Dave Clarke
<pl.programming-languages>
A simple programming language?
poolk
# A simple programming language?

(Asked by: username_0 on 2013-05-03)

What is a simple toy research programming language that has simple denotational semantics (including numbers or reals) that is used often to demonstrate certain properties of programming languages, or other things?

I am looking to demonstrate an idea on a programming language, and I don't want it to be complex in syntax, and I also want it to have easy to understand denotational semantics.

I don't need a working implementation of the language. Just the syntax and denotational semantics for the syntax.

Thanks.

**Tags:** pl.programming-languages
> **Comments:**
> **username_1**: PCF springs to mind. http://en.wikipedia.org/wiki/Programming_Computable_Functions. However, bear in mind that there are hundreds of such languages, which may be more or less suited to your needs.  
> **username_2**: As Cody points out, PCF, especially its call-by-value version, is often used, although if by denotational semantics you mean order-theoretic semantics, you'd be out of luck. Alternatively, you can use a traditional `while` language, e.g. that of Hoare's famous paper [An axiomatic basis for computer programming](http://sunnyday.mit.edu/16.355/Hoare-CACM-69.pdf). If you don't need non-termination, you can use a typed $\lambda$-calculus. The (asynchronous) $\pi$-calculus is an especially beautiful and widely used toy language. Finally, why don't you invent a language that suits your purpose?  
> **username_3**: Perhaps if you state briefly what you want this for, then we can provide better answers.  

---

## 4 answers

### Answer by username_4 on 2013-05-03. Score: 1

**Joy** comes to mind. It's a simple concatenative language that involves manipulations on a stack. It's essentially a reverse Polish notation for combinatory logic with quoting, developed by a professor of logic and programming so presumably it was taught in class. :)

I'm not 100% sure what qualifies as as denotational semantics, but, there is an algebra for it:

<http://www.kevinalbrecht.com/code/joy-mirror/j04alg.html>


---

### Answer by username_5 on 2013-05-04. Score: 1

David Schmidt's tutorial on [Programming language semantics](http://people.cis.ksu.edu/~schmidt/papers/CRC.chapter.ps.gz) survey semantics methods then provides a fully detailed denotational semantics for a toy imperative language.
You may have additional fun playing with a [naive Naskell interpreter](http://liris.cnrs.fr/romuald.thion/files/Ressources/Prog/Haskell/Schmidt/) for the language.


---

### Answer by username_6 on 2013-05-23. Score: 0

I would not know what toy language is often used. I can point to a language that was used. A very early example : *A Complete Machine-checked Definition of a Simple Programming Language Using Denotational Semantics* -
Véronique Donzeau-Gouge, Gilles Kahn, Bernard Lang
RR-330 IRIA-Laboria, 1978, 31 pages.
<ftp://ftp.inria.fr/INRIA/Projects/Atoll/croap/ASPLE-semantics.pdf>  
It may be too old for your taste, particularly in style.

It was done at the time in preparation for the formal semantics of the Ada programming language. But I guess the denotational semantics of Ada would be too large for your purpose
(I think it was published too).


---

### Answer by username_7 on 2013-05-17. Score: 0

Please forgive my arrogance, as I post so insubstantial answer. However, it may be helpful - if the case is teaching the idea of programming languages - and comments are to narrow.

I deeply believe, the tactic of teaching is more important, then choosing the simplest language. My classes (being a student) of programming languages involved the *while language*, which, I purpose, is more complex then *PFC*. However, in the end, the students was able to do some simple inductive proofs about while-programs, and build interpreters for a small statically-typed objective-functional-imperative cross language. Even though, they were of the first year. - I think the organization of the material and incremental going from formal grammars, through ASTs, static analyses, fixed points to semantics, Hoare logic and little lambda calculus, together with implementation of own interpreter have done the job pretty well.

**Edit:**  
The $while$ languages are generally - at least in my villagy surroundings - minimalistic derivations of IMP, containing the $while$ instruction. - Maybe this is local. If so, I should probably ask for forgiveness for my arrogance and ignorance, either. $:-)$

A good reference, for this case, can be *CS522 - Programming Language Semantics (Spring 2011)* lecture notes. - Especially this, if we are into the denotational semantics <http://fsl.cs.uiuc.edu/images/4/45/CS522-Spring-2011-PL-book-denotational.pdf>

> **Comments:**
> **username_8**: You might want to include in your answer a well-chosen reference for the While language: I did not know it and had to google it (found http://www.program-analysis.com/while.html interesting but it might not be the best reference).  

---

