Skip to content

Instantly share code, notes, and snippets.

@luqui
Created November 7, 2012 06:19
Show Gist options
  • Save luqui/4029824 to your computer and use it in GitHub Desktop.
Save luqui/4029824 to your computer and use it in GitHub Desktop.

All this lisp programming has fired up my language design interested again -- mostly seeing how bad common lisp is, and how great it could be in my idealized details-not-figured-out-and-possibly-don't-exist world.

What I'm working with right now is seeing a language implementation entirely as a structural catamorphism -- or perhaps more alluringly, a semantic map. This is an extensible, Lisp-style language, and we see language extensions as extending the semantic domain. What I hope will result is a language that has very nice denotational reasoning properties, despite being very customizable and extensible (the latter being what usually destroys the former).

The semantic domain is often made up of mathematical objects which are complex to specify, and in the spirit of Lisp we would like this to be a small language base upon which more can be built. So I believe it is too much to ask of the language to specify semantic domains in full detail. However, perhaps we may keep the domains themselves abstract from the compiler's perspective, but specify embeddings between the different domains completely.

Fundamentally, let us consider the term f * x in two semantic domains A and B, where * is the application operator (and would be unwritten in the langauge's concrete syntax, presumably). A's semantics for f * x is A[f * x] = A[f] A[*] A[x], and B's semantics is B[f * x] = B[f] B[*] B[x]. But let's suppose these languages are related by an embedding µ.

µ :: A -> B

For this to be a semantic embedding and not just any old function, we expect the natural commutativity property

µ[A[f * x]] = µ[A[f]] µ[A[*]] µ[A[x]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment