runtimeverification / k

K Framework Tools 7.0
BSD 3-Clause "New" or "Revised" License
445 stars 147 forks source link

[K-Bug] Uncaught MatchingException in kompile #4351

Open sliedes opened 4 months ago

sliedes commented 4 months ago

What component is the issue in?

None

Which command

What K Version?

v7.0.61

Operating System

Linux

K Definitions (If Possible)

module VM
    imports STRING
    imports LIST

    syntax AnyConst ::= Int | String

    syntax Op ::= "load_const" AnyConst
                | "store_name" String

    syntax OpsList ::= List{Op, ","}
    syntax Eval ::= "eval" "(" OpsList ")"

    configuration <k> $PGM:Eval </k>
                  <stack> .List </stack>
                  <locals> .Map </locals>

    rule <k> eval(store_name N:String, I:OpsList) => eval(I) ...</k>
            <stack> V => .List </stack>
            <locals> L => L[N <- V] ...</locals>
endmodule

Steps to Reproduce

$ kompile --debug vm.k
org.kframework.backend.llvm.matching.MatchingException: Could not find binding for variable while compiling pattern matching.
    at org.kframework.backend.llvm.matching.Matrix.liftedTree1$1(Matrix.scala:754)
    at org.kframework.backend.llvm.matching.Matrix.getLeaf(Matrix.scala:746)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:912)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:902)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:902)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.MapS.tree(SortCategory.scala:290)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:902)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:902)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matrix.$anonfun$compiledCases$2(Matrix.scala:616)
    at scala.collection.immutable.List.map(List.scala:247)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases$lzycompute(Matrix.scala:612)
    at org.kframework.backend.llvm.matching.Matrix.compiledCases(Matrix.scala:606)
    at org.kframework.backend.llvm.matching.pattern.SymbolS.tree(SortCategory.scala:85)
    at org.kframework.backend.llvm.matching.Matrix.compileInternal(Matrix.scala:907)
    at org.kframework.backend.llvm.matching.Matrix.compile(Matrix.scala:868)
    at org.kframework.backend.llvm.matching.Matching$.writeDecisionTreeToFile(Matching.scala:47)
    at org.kframework.backend.llvm.matching.Matching.writeDecisionTreeToFile(Matching.scala)
    at org.kframework.backend.llvm.LLVMBackend.accept(LLVMBackend.java:68)
    at org.kframework.kompile.KompileFrontEnd.run(KompileFrontEnd.java:114)
    at org.kframework.main.FrontEnd.main(FrontEnd.java:60)
    at org.kframework.main.Main.runApplication(Main.java:127)
    at org.kframework.main.Main.runApplication(Main.java:117)
    at org.kframework.main.Main.main(Main.java:58)
[Error] Internal: Uncaught exception thrown of type MatchingException
(MatchingException: Could not find binding for variable while compiling pattern
matching.)
[Warning] Compiler: Could not find main syntax module with name VM-SYNTAX in
definition.  Use --syntax-module to specify one. Using VM as default.

Expected Results

I would expect kompile to either successfully compile or give a more-or-less human readable error message (not sure which since I don't yet understand much about what I'm doing). I'm trying to implement something like Python VM, which is a stack machine.

Baltoli commented 4 months ago

The problem here is this rule:

            <locals> L => L[N <- V] ...</locals>

What you actually want to write is:

            <locals> L => L[N <- V] </locals>

because the rule is updating the entire map L (rather than a single element using the structural framing dots).

An alternative formulation for the rule would be (under the assumption that the key N already exists in the map, which might not hold in general):

            <locals> N |-> (_ => V) ...</locals>

Note here that the pattern in the cell isn't binding the entire map to a variable L, just the single element N |-> _.

If you're interested, the reason this happens is that the dots on the RHS are equivalent here to an anonymous variable of sort Map. As originally written, your rule is equivalent to:

            <locals> (L => L[N <- V]) _Rest:Map </locals>

The pattern matching compiler here greedily binds the contents of the cell to the variable L, meaning that there's nothing left to bind to _Rest.

We should absolutely provide a better error here, though, you're correct. Thanks for pointing this out!