How to represent a nested self contained data type? (lisp SExps)

[Víctor R. Escobar]

Hello,

I am trying to build a little lisp in order to teach myself better haxe; the beginning was a lot of fun (especially the parsing) until I took the decision of go typed.

Since some days I am hanging myself with the type system; I think I can't get a proper self-nested data type for the S-Expressions.

I though on do them with Enums instead of classes, just for the sake of "staticness".

An S-Expression can be either an Atom or a List 0 or more S-Expressions. A couple of examples using Haxe's syntax:

Symbol(a)
[]
[Symbol(a), Symbol(b), Symbol(c)]
[Symbol(a), [Symbol(b), Symbol(c)], Symbol(d), []]

As dynamic it works:

var a:Array<Dynamic> = [[Atom.Symbol("a")], []];

But how would you represent it without go the dynamic way? 

var a:Expression = [[Atom.Symbol("a")], []];

I tried lots of ways to represent those types, and I though the one that suits more the problem can be represented in the net way:

enum Atom {

    Number(n:Float);

    Symbol(s:String);

}

enum Pair<A, B> { Pair(a:A, b:B); }

typedef Expression = Pair<Atom,Array<Expression>>;

But the truth is that  doesn't matter what and how I try to initialize this type; nothing seems to compile, and this datatype seems to be un-initializable:

src/HxLisp.hx:16: characters 8-52 : Array<Array<hxlisp.Atom>> should be hxlisp.Expression

src/HxLisp.hx:16: characters 8-52 : Array<Array<hxlisp.Atom>> should be hxlisp.Pair<hxlisp.Atom, Array<hxlisp.Expression>>

Does anyone have an idea about how to solve that statically? Should I abandon the ADT way and go for more flexible classes or quit and go dynamic?

[Matthew Spencer]

Here, give this a try:  http://try.haxe.org/#7cB5c

--Matthew

[Víctor R. Escobar]

Thank you so much for the answer!

I will try it as soon as possible and probably I will upload the whole lisp interpreter as soon as it is ready :D