Lambda the Ultimate

inactiveTopic Fold and Unfold for Program Semantics
started 10/5/2002; 3:53:03 AM - last post 10/5/2002; 4:07:11 AM
jon fernquest - Fold and Unfold for Program Semantics  blueArrow
10/5/2002; 3:53:03 AM (reads: 2346, responses: 1)
Fold and Unfold for Program Semantics
"The paper is based upon categorical work on semantics, but explaining the ideas using Haskell makes them simpler, accessible to a wider audience, and executable."

This paper explains how to use fold and unfold to build executable semantic models. The equivalence between denotational semantics and folding over syntax trees is demonstrated with a simple example. A denotational semantics for addition is defined with fold and then redefined to compile "expressions into a list of instructions for execution using a stack." Next, the relation between unfold and operational semantics is illustrated:

"In operational semantics, the meaning of terms is defined using a transition relation that captures execution steps in an appropriate abstract machine... we explain how an operational semantics can be characterised as a semantics defined by unfolding to transition trees."

The last part of the paper deals with a more involved example: Milner's Calculus of Concurrent Systems (CCS) which is "defined in an abstract manner as least fixpoints of functors" again using Haskell. (Fold and Unfold for Program Semantics, Graham Hutton)

Posted to functional by jon fernquest on 10/5/02; 3:54:21 AM

jon fernquest - Re: Fold and Unfold for Program Semantics  blueArrow
10/5/2002; 4:07:11 AM (reads: 656, responses: 0)
Does anyone know of any good online reading material that explains Milner's Calculus of Concurrent Systems (CCS) ?

The references section of this course has some Milner papers:

There are also some lecture notes: