New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Refactor imperative core AST #711

Open
garyb opened this Issue Nov 16, 2014 · 15 comments

Comments

Projects
None yet
5 participants
@garyb
Member

garyb commented Nov 16, 2014

No description provided.

@garyb garyb added this to the 0.7.0 milestone Nov 16, 2014

@garyb garyb added the enhancement label Nov 16, 2014

@paf31

This comment has been minimized.

Member

paf31 commented Nov 16, 2014

For common optimizations like TCO and rewrites.

@jdegoes

This comment has been minimized.

jdegoes commented Nov 16, 2014

I'd suggest imperative core be minimal and expression-oriented, also typed or typed targets like JVM would have to go from functional core (a bigger jump).

Sent from my iPhone

On Nov 16, 2014, at 4:26 PM, Phil Freeman notifications@github.com wrote:

For common optimizations like TCO and rewrites.


Reply to this email directly or view it on GitHub.

@garyb garyb self-assigned this Feb 8, 2015

@garyb

This comment has been minimized.

Member

garyb commented Feb 17, 2015

I know you mentioned we could just rename the JS AST @paf31, but I couldn't resist having a look to see if we could do something a bit more "core"/reusable for other targets. At the moment I have this:

data Expr a
  -- |
  -- A literal value (`Literal` is reused from `CoreFn` here).
  --
  = Literal a (Literal (Expr a))
  -- |
  -- An object property or array accessor expression (prop/index, obj/array)
  --
  | Accessor a (Expr a) (Expr a)
  -- |
  -- An anonymous function value (arguments, body)
  --
  | AnonFunction a [Ident] [Statement a]
  -- |
  -- Function application
  --
  | App a (Expr a) [Expr a]
  -- |
  -- Variable reference
  --
  | Var a Ident

type Label = String

data Statement a
  -- |
  -- An expression whose value is discarded (probably causes a side effect)
  --
  = Expr (Expr a)
  -- |
  -- A function introduction (name, arguments, body)
  --
  | Function Ident [Ident] [Statement a]
  -- |
  -- A variable introduction and optional initialization
  --
  | VarIntroduction Ident (Maybe (Expr a))
  -- |
  -- A variable assignment (assignee, value)
  --
  | Assignment (Expr a) (Expr a)
  -- |
  -- While-style loop (condition, body)
  --
  | Loop (Expr a) [LoopStatement a]
  -- |
  -- A loop over an object's keys (key variable, object value, body)
  --
  | ObjectIterator Ident (Expr a) [LoopStatement a]
  -- |
  -- If-then-else statement
  --
  | IfElse (Expr a) [Statement a] (Maybe [Statement a])
  -- |
  -- Return statement
  --
  | Return (Expr a)
  -- |
  -- Throw statement
  --
  | Throw (Expr a)
  -- |
  -- InstanceOf test
  --
  | InstanceOf (Expr a) (Expr a)
  -- |
  -- Labelled statement
  --
  | Label Label (Statement a)
  -- |
  -- Commented statement
  --
  | Comment [Comment] (Statement a)

data LoopStatement a
  -- |
  -- Break statement
  --
  = Break (Maybe Label)
  -- |
  -- Continue statement
  --
  | Continue (Maybe Label)
  -- |
  -- Standard statement
  --
  | Statement (Statement a)

I don't know if this is the kind of route we do want to go down, but figured I'd throw it out there. It's not really expression orientated as @jdegoes suggested, but it feels like a middle ground between being too JS specific and something completely different.

The only thing in here I'm definitely unhappy with is InstanceOf, as we don't have a representation of classes at all in this, but if we want to desugar cases into IfElses then we need something like InstanceOf, but perhaps it just needs to be more PureScript specific, like IsDataConstructor Ident (Expr a) or something?

Also would we want annotations on Statement as well as Expr?

Anyway, thoughts please.

@ikarienator

This comment has been minimized.

ikarienator commented Feb 17, 2015

Sorry, what is the purpose of the imperative AST? I thought it was used for optimization? Isn't this design a little bit too "high level"? I thought it would be some sort of SSA or similar, or even simply llvm.

@paf31

This comment has been minimized.

Member

paf31 commented Feb 17, 2015

I like this, but agree that the instanceof part is a bit unfortunate. It comes down to what to do about "tagged" values. I think we have two options:

  • Tagged things don't exist in the imperative core AST. In this case, we desugar to records or something else, but perhaps pay a performance tax in JS.
  • Tagged things do exist in the imperative core AST. In this case, maybe we should separate tag constructors from Vars as a new data constructor, to make it really clear that tagged things are special. Then we leave it up to the backend to pick a representation (prototypes, records, whatever). Ideally, we'd use a phantom type or GADT to encode this sort of info in the AST, but this makes codegen much more difficult or even impossible.

I personally prefer the latter option.

@paf31

This comment has been minimized.

Member

paf31 commented Feb 17, 2015

Oh, also, I think annotations on statements would be nice unless there is some obstacle to adding them.

@jdegoes

This comment has been minimized.

jdegoes commented Feb 17, 2015

Non-extensible records can be easily compiled to high-performance struct-like constructs in many backends. Extensible records (i.e. adding fields to a record) will require a slower map-like construct. So maybe some notion of "class" or tagged "struct" / "record" could be useful.

@paf31

This comment has been minimized.

Member

paf31 commented Feb 17, 2015

Good point.

@garyb

This comment has been minimized.

Member

garyb commented Feb 17, 2015

@ikarienator this is intended for optimization, but only for things like TCO, a little inlining, etc. We're trying to keep the JS output as human readable and somewhat close to the input where practical. That's one of the selling points of the language over using something like GHCJS actually.

The other purpose it has is to act as an intermediary step between other potential backends apart from JS, as @osa1 did some work to make a version of psc that produced Lua a while back, and there's been a little interest in a JVM target also, so having a proper non-JS-specific imperative AST will help with that.

@paf31, @jdegoes I'll address your points in a bit, but basically, 👍. And adding annotations to statements is no problem at all.

@paf31

This comment has been minimized.

Member

paf31 commented Feb 17, 2015

I'm seriously considering making a case for removing the busted TCO implementation and promoting purescript-tailrec actually.

@joneshf

This comment has been minimized.

Member

joneshf commented Feb 17, 2015

The other purpose it has is to act as an intermediary step between other potential backends apart from JS, as @osa1 did some work to make a version of psc that produced Lua a while back, and there's been a little interest in a JVM target also, so having a proper non-JS-specific imperative AST will help with that.

I think this would spur multiple backends quite a bit. I looked into writing a backend the other weekend, and It's just a bit too much work for a weekend project, for me at least.

@garyb

This comment has been minimized.

Member

garyb commented Feb 17, 2015

@paf31: Ah yeah, I caught up with your video from the last session the other day and saw you mention that. What's wrong with it at the moment, I thought most of the kinks had been ironed out now?

We can definitely retain a notion of tagged things as per your second suggestion, we do that in CoreFn currently with an IsConstructor metadata annotation, and then there's a Constructor value which is a representation of a data constructor - essentially a function which produces a tagged thing.

From the above then, I'll add a Constructor case to Expr, and IsInstanceOf becomes IsTagOf Ident (Expr a), and we can defer the actual implementation of those things to the JS/whatever codegen.

@paf31

This comment has been minimized.

Member

paf31 commented Feb 17, 2015

I think a --dump-imp-core option would be nice to have too. Then people could implement backends in different languages by parsing the core representation. I created an issue for that separately.

@garyb

This comment has been minimized.

Member

garyb commented Feb 17, 2015

Yeah, definitely :)

@garyb

This comment has been minimized.

Member

garyb commented Feb 17, 2015

@joneshf I hope it does! There will be a bunch more issues to solve yet, like the FFI, but at least this should help.

@garyb garyb referenced this issue Mar 17, 2015

Closed

Core imperative representation #971

3 of 7 tasks complete

@paf31 paf31 modified the milestones: 0.7.0, 0.8.0 Apr 18, 2015

@paf31 paf31 modified the milestones: 0.9.0, 0.8.0 Aug 8, 2015

@paf31 paf31 modified the milestones: 0.9.0, 0.10.0 Apr 10, 2016

@paf31 paf31 removed this from the 0.10.0 milestone Sep 17, 2016

@paf31 paf31 modified the milestones: 1.0.0, 0.10.0 Sep 17, 2016

@paf31 paf31 modified the milestones: 1.0, Approved Oct 2, 2016

@paf31 paf31 changed the title from Introduce core imperative AST to Refactor imperative core AST Mar 19, 2017

@paf31 paf31 modified the milestones: 1.0, Approved Mar 25, 2017

@paf31 paf31 removed the defer? label Mar 25, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment