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 the entire backend to use ExecutableAST #105

Closed
magnus-madsen opened this Issue Feb 2, 2016 · 10 comments

Comments

Projects
None yet
2 participants
@magnus-madsen
Member

magnus-madsen commented Feb 2, 2016

Requires changes to (at least) the following components:

  • Solver
  • Interpreter

and all their dependencies. You should not change Verifier.

Semantics differences:

  • Pattern matching is no longer required in the interpreter (but it must be extended with CheckTag, etc.)
  • Literal are eliminated.
@mhyee

This comment has been minimized.

Member

mhyee commented Feb 5, 2016

I think there's a bug when pattern matches are simplified. In my current branch, TestExamples fails for Constant and ConstantSign.

The stack trace seems to point to the following case in the interpreter ("key not found: n1"):

case Expression.Var(ident, _, _, loc) => Value.cast2int32(env(ident.name))

And also the leq definition in the Flix program:

    fn leq(e1: Constant, e2: Constant): Bool = match (e1, e2) with {
        case (Constant.Bot, _)                      => true
        case (Constant.Cst(n1), Constant.Cst(n2))   => n1 == n2
        case (_, Constant.Top)                      => true
        case _                                      => false
    }

I'm guessing that the tag destruction isn't binding variables n1 and n2. I will investigate on Monday.

Here is the stack trace:

key not found: n1
java.util.NoSuchElementException: key not found: n1
    at scala.collection.MapLike$class.default(MapLike.scala:228)
    at scala.collection.AbstractMap.default(Map.scala:59)
    at scala.collection.mutable.HashMap.apply(HashMap.scala:65)
    ...
    at ca.uwaterloo.flix.runtime.Interpreter$.eval(Interpreter.scala:29)
    at ca.uwaterloo.flix.runtime.Interpreter$.eval2(Interpreter.scala:363)
    at ca.uwaterloo.flix.runtime.datastore.IndexedLattice.leq(IndexedLattice.scala:263)
    ...
@magnus-madsen

This comment has been minimized.

Member

magnus-madsen commented Feb 6, 2016

I changed something. Not sure if it fixes it.

@mhyee

This comment has been minimized.

Member

mhyee commented Feb 8, 2016

I updated my branch, and the bug I mentioned above seems to be fixed. However, a new (old?) bug is revealed: the fall-through for a match expression isn't working properly.

In TestExamples, right now Belnap.flix is the only test that fails. Consider the following function in Belnap.flix:

     fn not(e: Belnap): Belnap = match e with {
         case Belnap.Bot     => Belnap.Bot
         case Belnap.True    => Belnap.False
         case Belnap.Top     => Belnap.Bot // TODO: Deliberately incorrect.
     }

Other than the comment, the other bug in this function is that Belnap.False is not matched, so it should throw a match error. However, if this bug is intentional, then the test is incorrect, as it contains the line

A(5, not(Belnap.False)).

but then the test expects the fact A(5, Belnap.True).

But, ignoring all of this, the match should throw an error. Instead, the interpreter crashes:

key not found: tmp736602445
java.util.NoSuchElementException: key not found: tmp736602445
    at scala.collection.MapLike$class.default(MapLike.scala:228)
    at scala.collection.AbstractMap.default(Map.scala:59)
    at scala.collection.mutable.HashMap.apply(HashMap.scala:65)
    at ca.uwaterloo.flix.runtime.Interpreter$.evalGeneral(Interpreter.scala:225)
    at ca.uwaterloo.flix.runtime.Interpreter$.evalCall(Interpreter.scala:338)
    ...

(The stacktrace has a whole bunch of calls within the interpreter.)

@magnus-madsen

This comment has been minimized.

Member

magnus-madsen commented Feb 9, 2016

Yes, the generated code (by the pattern matcher) is somehow incorrect.

@mhyee

This comment has been minimized.

Member

mhyee commented Feb 18, 2016

As I mentioned today, I wasn't able to find a bug in pattern matching (other than not throwing a match error).

Anyway, most of this work is done -- you can start looking at the diff here. The majority of the changes were to rewrite TestInterpreter, and it's better to look at the individual commits for that file.

I'm not opening a PR, because it's not quite ready. There's still some miscellaneous cleanup, and a number of questions/TODOs to discuss, which we can do here.

  1. What's the plan with Expression.Apply and Expression.Closure and lambda lifting? I've implemented Expression.Apply3 (function is an expression) in the Interpreter, but not Expression.Apply (function is a Name.Resolved). [EDIT: No action required.]

  2. Expression.CheckNil and Expression.CheckCons aren't implemented yet. [EDIT: No action required yet.]

  3. We still haven't decided what to do with Term.Body.Wildcard. Issue #65 (formerly #22) was about this. [EDIT: No action required yet.]

  4. The tests constantly spit out "Successfully solved in 0 msec" because of Flix's default options. To silence this, we could change the default settings, or change the tests. [EDIT: I changed the tests to silence Flix.]

  5. If there's a match or a switch error, the interpreter throws a RuntimeException. This is too general -- one of our tests throws a "key not found" (because of the pattern matching bug), but the test passes because it expects a RuntimeException, and not a MatchException (which doesn't actually exist). We should figure out what exceptions to throw and where to define them, otherwise our tests aren't actually useful. [EDIT: See #118. I'll update the interpreter, codegen, and tests once the exception hierarchy is implemented.]

  6. The LoadExpression and StoreExpression implementation is untested, because nothing actually generates these AST nodes. [EDIT: No action required yet.]

  7. A question about syntax. Consider the program:

    fn x: Int = 5
    fn y: Int = x()
    

    It seems it's necessary to call the function x() with parentheses -- simply writing x is invalid. What are the rules for defining and accessing/calling "values," i.e. zero-arg functions? Are the parentheses optional only in the definition, but required in the function call? [EDIT: No action required yet.]

  8. Just to confirm, but we don't actually allow lambdas, i.e. all functions must be named? So I can write something like

    fn f(x: (Int) -> Int, y: Int): Int = x(y)
    fn g(x: Int): Int = x + 1
    fn h: Int = f(g, 5)
    

    but not

    fn f(x: (Int) -> Int, y: Int): Int = x(y)
    fn h: Int = f(x => x + 1, 5)
    

    But I guess this is what #93 addresses. [EDIT: Wrote a test. No further action required.]

  9. There is a bug when comparing Type.Tag, which breaks some of my tests. The problem is that comparing two Type.Tags involves comparing a Name.Ident, which ends up comparing source locations. The problem arises when writing native functions that deal with tag types - mkTagType constructs a Type.Tag with an unknown source location. [EDIT: See #119. Will leave the tests as ignore for now and fix them later.]

  10. Related to that, mkTagType exposes the Flix implementation, because it takes a Type and not an IType. [EDIT: See #120.]

  11. What are the rules for what appears in a head term? Due to the (partial) refactor, we now have Term.Head.Exp instead of Term.Head.Lit, but right now we only allow "literal-like" expressions. So the following program is actually invalid:

    rel A(x: Int);
    rel B(x: Int);
    rel C(t: (Int, Int));
    fn f(x: Int, y: Int): (Int, Int) = (x, y)
    
    A(1).
    A(2).
    B(3).
    
    C((x, y)) :- A(x), B(y).  // invalid
    C(f(x, y)) :- A(x), B(y). // OK
    

    [EDIT: No action required yet.]

  12. The backend supports Int8/Int16/Int32/Int64 (codegen, interpreter, and tests). But it's still missing from the frontend (see #107). [EDIT: I wrote a bunch of tests using the i8 suffixes.]

@mhyee

This comment has been minimized.

Member

mhyee commented Feb 18, 2016

Another question/comment. TypedAst currently has a freeVars set for Predicate.Body. As part of this work, I've moved it to ExecutableAst. But this really shouldn't be in the AST -- in a not-yet-pushed commit, I've moved it to CreateExecutableAst.

Now the question: what is the implementation of freeVars for Predicate.Body.Loop? I can't put ???, so for now, I'm making it an empty set with a TODO.

def freeVars: Set[String] = this match {
  case TypedAst.Predicate.Body.Collection(_, terms, _, _) => // omitted
  case TypedAst.Predicate.Body.ApplyFilter(_, terms, _, _) => // omitted
  case TypedAst.Predicate.Body.ApplyHookFilter(_, terms, _, _) => // omitted
  case TypedAst.Predicate.Body.NotEqual(x, y, _, _) => Set(x.name, y.name)
  case TypedAst.Predicate.Body.Loop(_, _, _, _) => ??? // What should go here?
}

[EDIT: Comment and TODO updated.]

@magnus-madsen

This comment has been minimized.

Member

magnus-madsen commented Feb 19, 2016

What's the plan with Expression.Apply and Expression.Closure and lambda lifting? I've implemented Expression.Apply3 (function is an expression) in the Interpreter, but not Expression.Apply (function is a Name.Resolved).

Expression.Apply and Expression.Closure will be removed. Expression.Apply3 is the only apply.

Expression.CheckNil and Expression.CheckCons aren't implemented yet.

Neither are they anywhere else.

We still haven't decided what to do with Term.Body.Wildcard. Issue #65 (formerly #22) was about this.

Yes, you will probably have to wait some time, before we get around to fixing issue #65 properly.

The tests constantly spit out "Successfully solved in 0 msec" because of Flix's default options. To silence this, we could change the default settings, or change the tests. [EDIT: I changed the tests to silence Flix.]

Good. I think this is the appropriate solution.

If there's a match or a switch error, the interpreter throws a RuntimeException. This is too general -- one of our tests throws a "key not found" (because of the pattern matching bug), but the test passes because it expects a RuntimeException, and not a MatchException (which doesn't actually exist). We should figure out what exceptions to throw and where to define them, otherwise our tests aren't actually useful.

Please introduce UserException, SwitchException and MatchException and have them extend FlixRuntimeException (also new) and have that extend FlixError. Then come see me, and we can discuss the full exception hierarchy. Maybe we should prefix these names with Flix to distinguish them from Scala's.

The LoadExpression and StoreExpression implementation is untested, because nothing actually generates these AST nodes.

Yes, it is on the list. It will probably have to wait until Luqman joins us.

What are the rules for defining and accessing/calling "values," i.e. zero-arg functions?

Unclear. This is pending on the rewrite of the type checker. Currently, you must call a zero argument function as f(). In the future that will likely change. However, you can define a zero argument function without arguments (and that is already the preferred style).

Just to confirm, but we don't actually allow lambdas.

We do. It just that we don't have any code to test it, so we have no idea if it works, or what pieces are missing.

There is a bug when comparing Type.Tag, which breaks some of my tests. The problem is that comparing two Type.Tags involves comparing a Name.Ident, which ends up comparing source locations.

Bug where? Name.Ident should have be compared directly.

Related to that, mkTagType exposes the Flix implementation, because it takes a Type and not an IType.

Well spotted. Can you fix it?

What are the rules for what appears in a head term?

Very much up in the air. We have yet to decide what we want in the final version. Right now some literals should be allowed.

The backend supports Int8/Int16/Int32/Int64 (codegen, interpreter, and tests).

Yes. On the list. Feel free to write tests using the i8, i16, etc. suffixes like rust.

@magnus-madsen

This comment has been minimized.

Member

magnus-madsen commented Feb 19, 2016

Now the question: what is the implementation of freeVars for Predicate.Body.Loop?

Not sure, who uses freeVars?

@mhyee

This comment has been minimized.

Member

mhyee commented Feb 19, 2016

Expression.Apply and Expression.Closure will be removed. Expression.Apply3 is the only apply.

So when we have lambda lifting, the expression in Apply3 (which will be renamed to Apply) will be rewritten to a Ref (and not a Lambda)? [EDIT: Answer: yes.]

Please introduce UserException, SwitchException and MatchException and have them extend FlixRuntimeException (also new) and have that extend FlixError. Then come see me, and we can discuss the full exception hierarchy. Maybe we should prefix these names with Flix to distinguish them from Scala's.

Let's do this together, in a separate PR. (We also need to incorporate InternalRuntimeError and InternalCompilerError into the exception hierarchy.) [EDIT: See #118.]

We do. It just that we don't have any code to test [lambdas], so we have no idea if it works, or what pieces are missing.

I will write some tests in the interpreter and see what happens. [EDIT: Seems to work, even though the syntax is ugly.]

Bug where? Name.Ident should have be compared directly.

Here's a partial and simplified snippet from my test:

val input =
  """enum Val { case C(Int) }
    |fn g: Val = f(111)
  """.stripMargin
val tagTpe = flix.mkTagType("Val", "C", Type.Int32)
val tpe = flix.mkFunctionType(Array(...), flix.mkEnumType("C", Array(tagTpe)))

Here, f is a native function I implement with addHook (not shown in the snippet). The Flix program defines an enum type Val, with tag type Val.C. I build that type with the Flix API (mkTagType and mkEnumType).

However, typechecking fails because Val.C (defined in the Flix program) is not equal to tagTpe (constructed with the API).

case class Tag(enum: Name.Resolved, tag: Name.Ident, tpe: Type) extends Type

Specifically, tag, a Name.Ident, is different in Val.C and tagTpe. This is because source positions are compared.

case class Ident(sp1: SourcePosition, name: String, sp2: SourcePosition) extends SmartHash

We need to override equals() and hashCode() to compare only name. We can do this in the implementation of Tag or Ident. [EDIT: See #119.]

[mkTagType exposing Type and not IType]

I will fix this in a separate PR. [EDIT: See #120.]

Yes. On the list. Feel free to write tests using the i8, i16, etc. suffixes like rust.

Will update my tests. [EDIT: Done.]

freeVars

Looks like the Indexer. [EDIT: Comment updated.]

@mhyee

This comment has been minimized.

Member

mhyee commented Feb 23, 2016

(Commenting here so we have this recorded somewhere.)

This refactor has caused a slowdown. The overall time (solver + interpreter) has basically doubled, but this is because the interpreter is now six times slower. Another way of looking at the numbers: previously 20% of the time was spent in the interpreter, now it's 60% of the time (and the overall time has doubled). The solver (excluding the interpreter) is about the same (some runs it's faster, other runs it's slower).

Here's some concrete numbers, taken from the 401.bzip2 SU benchmark (I modified Flix to collect the interpreter times):

Before

Successfully solved in 20,577 msec.
    Solver time (exclusive): 16,112 msec.
    Interpreter time: 4,465 msec.
Initial Facts: 11,844. Total Facts: 639,197.
Throughput: 31,062 facts per second.

After

Successfully solved in 39,138 msec.
    Solver time (exclusive): 14,718 msec.
    Interpreter time: 24,420 msec.
Initial Facts: 11,844. Total Facts: 639,197.
Throughput: 16,331 facts per second.

Magnus and I suspect that it's because we now compile pattern matching to let-bindings and if-then-else expressions. The nesting requires more recursive calls to the interpreter, and the let-bindings increase the size of the environment map, so lookups and copying become much more expensive. (I had also previously spent time optimizing the interpreter's implementation of pattern matching, but that's now gone.)

We don't think IFDS will be significantly affected, since it doesn't really call the interpreter (no lattice operations and mainly native functions).

I guess what this means is we really want code generation for performance (but we already knew that).

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