Does there exist a DSL for describing data structures and their manipulation? I realize that a "normal" programming language describes data structures, but they also do a lot more (e.g. IO).

I'm curious what the smallest language is required to describe classic data structures like List, Tree, Set, Stack, Queue, Map, Graph, etc. and their operations like append, remove, get, add, remove, poll, offer, etc.


I ask this question because I was trying to think of a way to specify a data structure at runtime.

For example, imagine there exists some service which allows its clients to allocate space for a data structure. This is done by enumerating the possible valid types that the data structure may be as well as the data structure's starting state. For the list case, it's possible states are the empty and non-empty lists, and the starting state would be the empty list.

Then, clients would specify valid operations, that would modify the state of the data structure. For example, define append, define remove, etc. My question appears here: how would a client communicate to the service a valid operation to be performed on the data structure? It would have to be written in some agreed upon formal language, the simplest DSL used for describing data structures and their operations.

  • $\begingroup$ The lambda calculus is a plausible candidate for "smallest", or an imperative version of it with updateable memory cells. I suspect that isn't the kind of answer you're looking for, but right now it meets all of the requirements you listed. Can I suggest fleshing out the question with some specific requirements that narrow down what you're looking for, in a way that will rule out uninteresting answers (like "the lambda calculus")? $\endgroup$ – D.W. Aug 18 '16 at 20:36
  • $\begingroup$ @D.W. I've added the motivation for the question as an edit. Let me know if it's unclear. $\endgroup$ – geofflittle Aug 18 '16 at 21:42
  • $\begingroup$ Have you encountered abstract or order-sorted data types? $\endgroup$ – Raphael Aug 18 '16 at 21:59
  • $\begingroup$ Note that since finite automata with two stacks are already Turing-complete, there probably is no really "small" language for specifying all these things. $\endgroup$ – Raphael Aug 18 '16 at 22:00
  • $\begingroup$ I don't understand how the use case listed in the motivation leads to the question you asked. There's nothing there that requires the data structure to be specified in the "simplest"/"smallest" DSL. Anyway, I still think the lambda calculus plus imperative update to memory cells qualifies, or some nice Scheme subset, or a small subset of Standard ML (that includes ref), or SafeHaskell, or any of a gazillion other possibilities. I still don't understand why "smallest"/"simplest" is important. Is this an XY problem? $\endgroup$ – D.W. Aug 18 '16 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.