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.

Improve this question
$\endgroup$
5
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 12:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.