2
$\begingroup$

I am writing a compiler for a simple subset of standard ML (just for fun) and I am stuck on how to represent the core language (I should mention that I write it in Haskell probably).

Basically what I have already is an expression type that looks like the following:

data Expr' e
  = Let Name e e
  | Fn Name e
  | Val Value
  | Var Name
  | App e e
  | If e e e
  deriving (Show, Eq, Functor)

newtype Mu f = In { out :: f (Mu f) }

deriving instance Eq (f (Mu f)) => Eq (Mu f)
deriving instance Show (f (Mu f)) => Show (Mu f)

type Expr = Mu Expr'
type LocExpr = Cofree Expr' SourcePos

(I use Cofree to conveniently annotate the terms with source code position and other information). With this core language I can already transpile simple programs to Scheme (or other langauges), it kind of is like a dynamic programming language at the moment (probably not treating recursion properly at the moment, but it seems to work).

Now I want to support tuples as well, because I want to catch up with Kennedy's compiling with continuations, continued (https://www.microsoft.com/en-us/research/publication/compiling-with-continuations-continued/). If I understand the paper right, for his example of the untyped ML subset that he implements, he just uses pairs.

I guess however, that I could just add a term Tuple [e] and indexing terms/case terms (where if I read Kennedy 2007 right, he just implements Tuple e e) to the core language to represent a tuple. Unfortunately, I don't find much about what would be a good way to represent tuples there. I am just a hobbyist, so I might just not look in the right places for that information.

Another resource where I stumbled over a core language was Turon's thesis https://www.mpi-sws.org/~turon/turon-thesis.pdf which is obviously not exactly about SML, but there he also only implements pairs (which makes me think whether tuples might be implemented as (a, (b, unit)) or something.

$\endgroup$
  • 4
    $\begingroup$ Are you asking how to represent them in the AST or are you asking how to represent them in the target language? If the later what is the target language? If the former then why do you think there's a problem with the Tuple [e] representation? $\endgroup$ – Jake Oct 14 '16 at 16:37
  • $\begingroup$ in the AST. I just wondered because writing Tuple [e] doesn't seem much overhead over Pair e e, so I thought there could be something to it. $\endgroup$ – wirrbel Oct 14 '16 at 16:48
  • 1
    $\begingroup$ In my experience it doesn't matter. I think it depends (but is in no way a major issue) on how your language uses tuples. For instance in haskell tuples are not defined inductively or constitutionally. They're just defined to be collections of values. This jives well with the list representation. In SML a pair operator is used to represent the type. This jives better with the 'Pair' representation. Both work however and don't impose significant coding overhead or mental strain. Also keep in mind church/scott encodings if you just want to avoid tuples in your core language. $\endgroup$ – Jake Oct 14 '16 at 16:53
  • 2
    $\begingroup$ I have trouble finding your question in this long post. Can you please tighten things up a bit? $\endgroup$ – Raphael Oct 14 '16 at 17:41
  • 1
    $\begingroup$ Amazingly PL Zoo does not have tuples anywhere, but I am mentioning it anyway in case you want to have a look at it. It sounds like you might like it. $\endgroup$ – Andrej Bauer Oct 15 '16 at 12:36

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.