Concrete Data Structure

Concrete Data Structure

(CDS) A model of programming language terms developed in thecontext of constructing fully abstract semantics forsequential languages. A CDS is a 4-tuple (C,V,E,|-) where Cis a cell, V is a value, E is an event and |- is an "enablingrelation". An event is a cell and a value. A cell C is"enabled" by a set of events S if S |- C. A state is a set ofevents which are consistent in that the values they give forany cell are all equal. Every cell in a state is enabled.

[G. Berry, P.-L. Curien, "Theory and practice of sequentialalgorithms: the kernel of applicative language CDS", Algebraicmethods in semantics, CUP 1985].