1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ PCF springs to mind. 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. $\endgroup$
    – cody
    Commented May 3, 2013 at 18:49
  • 1
    $\begingroup$ 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. 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? $\endgroup$
    – Martin Berger
    Commented May 3, 2013 at 18:59
  • 4
    $\begingroup$ Perhaps if you state briefly what you want this for, then we can provide better answers. $\endgroup$
    – Dave Clarke
    Commented May 4, 2013 at 17:59

4 Answers 4

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

David Schmidt's tutorial on Programming language semantics 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 for the language.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 program-analysis.com/while.html interesting but it might not be the best reference). $\endgroup$
    – J..y B..y
    Commented May 18, 2013 at 8:54
0
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.