Expectations 0.7.2

[thorehusfeldt]

Here is my best shot at Expectations 0.7.2, much of it in CUE:

Changed in 0.7.1: Removed false from the values for with_margin

Changed in 0.7.2: Restricted expectation keys based on problem.type

// The registry maps submission name patterns to expectations.
// A submission whose name matches a pattern must satisfy its expectations.
// (In particular, a submission can match several patterns, and thus
// needs to satisfy several expectations.)
// The semantics of "matching a pattern" are not defined here
// (possibilities: regexen, prefix, globbing).

#registry: close({[string]: #root_expectations})

// Problem-wide constants
// ======================
// Set by the judging environment
time_limit: >0
// Set in problem.yaml; these are problem.timing.tle_margin and problem.timing.ac_margin
tle_margin: >1
ac_margin:  >1

// Testcase Result
// ===============
// The result of running a submission on a testcase

#result: {
	testcase_name!: #name
	time!:         >=0
	if time <= time_limit {
		// When the submission terminates within the time limit
		// its exit status is either a success or a failure:
		terminated_successfully!: bool
		if terminated_successfully {
			// The output of successfully terminated submissions is
			// validated by the output validator, the resulting values are:
			output_validated!: bool
			message?:          string
			score?:            >=0
		}
	}
}

// The verdicts that can occur in the expectations framework are:

#verdict: "AC" | "WA" | "RTE" | "TLE"

// Testcase Verdict
// ================
//
// The verdict of (a submission's execution on) a single testcase is
// defined in terms of the testcase result in terms of time, termination
// status, and output validation as follows.

#verdict_for_result: {
	// The verdict for the _result
	_result: #result
	let t = _result.time
	if t >= time_limit {"TLE"}
	if t < time_limit {
		if !_result.terminated_successfully {"RTE"}
		if _result.terminated_successfully {
			if !_result.output_validated {"WA"}
			if _result.output_validated {"AC"}
		}
	}
}

// Aggregate verdict
// =================

// For a linearly ordered sequence of verdicts, the aggregate verdict is
// * the first occurrence of "WA", "TLE", or "RTE" if it exist
// * "AC" if the list is empty or only contains "AC"


// Expectations
// ============

#root_expectations: {
	// Set expectations for all testcases
	#expectation | #range | #abbreviation

	// And/or set them for testcases matching a pattern (such as testgroups)
	[=~"^(sample|secret)"]: #expectation | #range | #abbreviation
}

// Often-used expectations are specified in terms of abbreviations

#abbreviation: "accepted" | "wrong answer" | "runtime exception" | "time limit exceeded" | "does not terminate" | "not accepted"

// Scoring problems can set the range

#range: number | ordered_tuple

ordered_tuple: tuple=[number, number & >=tuple[0]]

// In general, we can set fine-grained expectations in terms of which verdicts, timing, // messages, scores are allowed and disallowed for a set of results R

#expectation: {
	permitted_testgroup_verdicts?: [...#verdict] // only these testcase verdicts may appear
	required_testgroup_verdicts?: [...#verdict]  // at least one of these testcase verdicts must appear
	message?:                   string // this judgemessage must appear
	with_margin?: true // Set m = max(r.time) over all r in R. Then t < timelimit / ac_margin or t >= timelimit * tle_margin

      // pass-fail problems only: 
	permitted_aggregate_verdict?: [...#verdict]  // the aggregate verdict must be in this list 
        // scoring problems only:	
	permitted_testcase_scores?: #range // all testcase scores be in range
	permitted_aggregate_score?: #range // the aggregate score must be in range
}

// Useful abbreviations
// ====================
//
// Each  abbreviation is a shorthand for common #expectations struct, as follows:

_expectation_for_abbreviation: {
	_abbreviation: #abbreviation
	if _abbreviation == "accepted" {
		permitted_testcase_verdicts: ["AC"]
		with_margin: true
	}
	if _abbreviation == "wrong answer" {
		permitted_testcase_verdicts: ["AC", "WA"]
		required_testcase_verdicts: ["WA"]
	}
	if _abbreviation == "runtime exception" {
		permitted_testcase_verdicts: ["AC", "RTE"]
		required_testcase_verdicts: ["RTE"]
	}
	if _abbreviation == "time limit exceeded" {
		permitted_testcase_verdicts: ["AC", "TLE"]
		required_testcase_verdicts: ["TLE"]
		with_margin: true
	}
	if _abbreviation == "does not terminate" {
		permitted_testcase_verdicts: ["AC", "RTE", "TLE"]
		required_testcase_verdicts: ["RTE", "TLE"]
	}
	if _abbreviation == "not accepted" {
		required_testcase_verdicts: ["RTE", "TLE", "WA"]
	}} & #expectation

What changed?

The most visible change is that the #expectations struct is now a lot larger. Here it is again:

#expectation: {
	permitted_testgroup_verdicts?: [...#verdict] // only these testcase verdicts may appear
	required_testgroup_verdicts?: [...#verdict]  // at least one of these testcase verdicts must appear
	permitted_aggregate_verdict?: [...#verdict]  // the aggregate verdict must be in this list 
	message?:                   string // this judgemessage must appear
	permitted_testcase_scores?: #range // all testcase scores be in range
	permitted_aggregate_score?: #range // the aggregate score must be in range
	with_margin?: true // Set m = max(r.time) over all r in R. Then t < timelimit / ac_margin or t >= timelimit * tle_margin
}

1. The key names distinguish between testcase_verdicts and aggregate_verdict. Symmetrically, the score field has split into two (and this will do a lot of good!).

2. The new boolean with_margin has also been added. In ototal, 3 new fields, and several renamings. Have a look.

3. Also, #result got a new field

#result: {
   testcase_name!: #name
   ... 
}

We need this for sorting verdicts (so we can compute aggregate verdicts), and for applying the scoring aggregation rules (which depends on testdata.yaml file contents and their full path names).

I added the ! to make it explicitly mandatory.

4. I didn’t bother to specify the aggregate verdict in CUE, it’s not clearer than the prose expression I wrote down.

5. Note that none of the abbreviations use aggregated verdicts or scores. (But they do use with_margin)

[niemela]

My first take on this:

I'm assuming that a lot of the naming is still placeholder? I'm not commenting on naming here.

// Set by the judging environment
time_limit: >0
// Set in problem.yaml; these are problem.timing.tle_margin and problem.timing.ac_margin
tle_margin: >1
ac_margin:  >1

I'm confused by this? These three can all be set in problem.yaml, the last two will always have a value (since there is a default for when they are not explicitly set).

#result: {
	testcase_name: #name

Why does the name have to be part of the result? Wouldn't it feel more natural to have a testcase (which has a name) map to a result?

Also, give that the name is here, why is it optional? A testcase always has a name.

	if time <= time_limit {
		// When the submission terminates within the time limit
		// its exit status is either a success or a failure:
		terminated_successfully!: bool

It would feel more natural to me if terminated_successfully is always defined, same with output_validated. Why should these be conditional?

// For a linearly ordered sequence of verdicts, the aggregate verdict is
// * the first occurrence of "WA", "TLE", or "RTE" if it exist
// * "AC" if the list is empty or only contains "AC"

This is not how aggregate verdicts are currently defined for scoring problems.

	// And/or set them for testcases matching a pattern (such as testgroups)
	[=~"^(sample|secret)"]: #expectation | #range | #abbreviation

A testcase or group could also start with *.

// Often-used expectations are specified in terms of abbreviations

#abbreviation: "accepted" | "wrong answer" | "runtime exception" | "time limit exceeded" | "does not terminate" | "not accepted"

I don't think we need these. Well... we obviously don't need them since it's "just" syntactic sugar, but I don't think we should have them.

// Scoring problems can set the range

...or value (which is what the code actually says)

	permitted_testcase_scores?: #range // all testcase scores be in range

This feels very strange. When and why would you use this?

1. The key names distinguish between testcase_verdicts and aggregate_verdict. Symmetrically, the score field has split into two (and this will do a lot of good!).

Please elaborate on the lot of good it will do. This seems to be a point I'm not getting above.

5. Note that none of the abbreviations use aggregated verdicts or scores. (But they do use with_margin)

Shouldn't they though?

[RagnarGrootKoerkamp]

// Set by the judging environment
time_limit: >0
// Set in problem.yaml; these are problem.timing.tle_margin and problem.timing.ac_margin
tle_margin: >1
ac_margin:  >1

I'm confused by this? These three can all be set in problem.yaml, the last two will always have a value (since there is a default for when they are not explicitly set).

In my understanding these are not something you can write in expectations.yaml since they're not part of the #registry. They're only here to specify #result.

#result: {
	testcase_name: #name

Why does the name have to be part of the result? Wouldn't it feel more natural to have a testcase (which has a name) map to a result?

Also, give that the name is here, why is it optional? A testcase always has a name.

	if time <= time_limit {
		// When the submission terminates within the time limit
		// its exit status is either a success or a failure:
		terminated_successfully!: bool

It would feel more natural to me if terminated_successfully is always defined, same with output_validated. Why should these be conditional?

All of this is only for the purposes of precisely specifying how to go from the #result (its running time, exit code, and correctness of output) on a single testcase to a #verdict for that testcase. But I agree it's a bit confusing. It may be better to write this down in a different way.

// For a linearly ordered sequence of verdicts, the aggregate verdict is
// * the first occurrence of "WA", "TLE", or "RTE" if it exist
// * "AC" if the list is empty or only contains "AC"

This is not how aggregate verdicts are currently defined for scoring problems.

Can you explain how they are defined? I'm not quite sure.

A testcase or group could also start with *.

// Often-used expectations are specified in terms of abbreviations

#abbreviation: "accepted" | "wrong answer" | "runtime exception" | "time limit exceeded" | "does not terminate" | "not accepted"

I don't think we need these. Well... we obviously don't need them since it's "just" syntactic sugar, but I don't think we should have them.

I definitely want them. It's super useful to specify wrong_answer/*: sample: accepted without having to fully write out what accepted means.

5. Note that none of the abbreviations use aggregated verdicts or scores. (But they do use with_margin)

Shouldn't they though?

No, I don't think so. permitted and required already pin things down very precisely

Generally, permitted_testcase_verdicts and required_testcase_verdicts give me all I need. I don't really see what an additional permitted_aggregate_verdict gives me on top of that. @niemela Could you give an example of where exactly this would be useful?

[thorehusfeldt]

I don't think we need [abbreviations]. Well... we obviously don't need them since it's "just" syntactic sugar, but I don't think we should have them.

Strongly disagreed. (Again, it feels as we are rehashing conversations from three months ago.)

I very much want to be able to do this. (A quadratic time submission that passes the n=16 testgroup, the n=1000 testgroup, times out on the n=100000 testgroup, and gets wrong answer on the testgroup with disconnected graphs.

partially_accepted/thore.py:
    sample: accepted
    group1: accepted
    group2: accepted
    group3: time limit exceeded
    group4: wrong answer

For an IOI-style problem, I have 20 of these submissions. I need the abbreviations.

[niemela]

[...]
This is not how aggregate verdicts are currently defined for scoring problems.

Can you explain how they are defined? I'm not quite sure.

No, I would say that it's quite unclear. We need to improve that:
https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#grading

It's clearly not simply "first error" though.

I definitely want them. It's super useful to specify wrong_answer/*: sample: accepted without having to fully write out what accepted means.

Ok, yeah, we probably (i.e. definitely) need some kind of shorthand. Do you feel the same about all of them?

I don't really see what an additional permitted_aggregate_verdict gives me on top of that. @niemela Could you give an example of where exactly this would be useful?

It allows you to say things about the submissions (rather than the testcases). I.e. this submission will be judge as X. It can also allow for short circuiting. Seems to me to be the most basic thing we would want to express.

[niemela]

For an IOI-style problem, I have 20 of these submissions. I need the abbreviations.

Yes, I agree that we need some kind of shorthand.

[Tagl]

I agree that shorthand and verifying aggregate verdict/score are both very nice to have.

[thorehusfeldt]

Why does the name have to be part of the result? Wouldn't it feel more natural to have a testcase (which has a name) map to a result?

It does not have to (the same effect would indeed be achieved with a higher-order datatype such as a map), it’s merely the conceptually most minimal way to give sense to “the first one” for a set of #results (and we need this in order to humour your wish to express aggregate_verdict.) If you like adding more complexity, we can introduce yet another concept, namely

#result_for_testcase: [#name]: #result

and then define aggregate verdict in terms of a #result_for_testcase object instead of (like now) defining it for [...#result] (which means “list of #result”.) This would be more verbose (you’d have to write something like “the verdict of the value of the lexicographically first key of the #result_for_testcase map what maps to a result whose verdict is not "AC")

In short (x,y) is at a lower order of abstraction than lambda x: y. Remember that I’m specifying meaning not implementation, so I use the least complicated structures that suffice to express the semantics.

testcase or group could also start with *.

No, I want fine-grained targeting of testdata to always start with sample or secret. This is to avoid matching against data/invalid_inputs/foo.in, which should never be targeted by an expectation. This is a deliberate constraint to the syntax that aims to increase clarity of intent.

Please elaborate on the lot of good it will do

Assume you have a two-testcase scoring problem (with secret/a and secret/b). The max scores are 100. The scoring abbreviation rule is sum.

Consider now:

thore.py:
  secret:
    permitted_testcase_scores: [0, 50]

This means that thore.py scores at most 50 points on secret/a and at most 50 points on secret/b. (It’s a claim about a set of numbers.)

One the other hand, consider:

ragnar.cpp:
  secret:
    permitted_aggregate_score: [0, 75]

This means that Ragnar’s submission gets at most 75 points in total over both secret/a and secret/b. For instance by scoring 66 points on secret/a and 5 points on secret/b. (It’s a claim about a single number.)

In principle, it makes sense to write:

my_heuristic.cpp:
  permitted_aggregate_score: [0,90] // total score is max 90
  permitted_testcase_scores: [0,10]  // individual score on each testcase is max 10

Since there are many different ways of defining scoring problems (in particular, in the Swedish Olympics, using both subtasks and a bespoke scoring output validator for the last subtask), it is useful to support both concepts.

So: testcase score (for a set of testcases) and aggregate score (of a set of testcases) are not the same. It is extremely unfortunate that the terminology in the specification is what it is (but my valiant attempt in August at clarifying this failed, just like my attempt at terminologically separating (testcase) verdict and (aggregate) verdict.)

[thorehusfeldt]

The definition of how verdicts are aggregated in the specification is this:

For pass-fail problems, the verdict of a submission is the first non-accepted verdict, where test cases are run in lexicographical order of their full file paths (note that sample comes before secret in this order).

I think this is close, except for

1. what is the verdict of the empty set of results?, and
2. it should’t specify the order in which test cases are run
3. I see no reason to restrict this to pass-fail problems.

Is there anything else wrong with it?

My suggestion to clarify both issues in 0.7.1 above is

// Aggregate verdict
// =================

// For a linearly ordered sequence of verdicts, the aggregate verdict is
// * the first occurrence of "WA", "TLE", or "RTE" if it exist
// * "AC" if the list is empty or only contains "AC"

The linear ordering would be given by lexicographic ordering of result.name.

[niemela]

No, I want fine-grained targeting of testdata to always start with sample or secret. This is to avoid matching against data/invalid_inputs/foo.in, which should never be targeted by an expectation. This is a deliberate constraint to the syntax that aims to increase clarity of intent.

I definitely agree that invalid_inputs should not be targeted. That said, invalid_inputs does not contain test cases test groups. How about allowing *, but only using the glob (or regexp?) to target test cases and groups. This is indeed what I thought we we're already doing.

[niemela]

The definition of how verdicts are aggregated in the specification is this:

For pass-fail problems, the verdict of a submission is the first non-accepted verdict, where test cases are run in lexicographical order of their full file paths (note that sample comes before secret in this order).

@thorehusfeldt
I think you are replying to my statement that "This is not how aggregate verdicts are currently defined for scoring problems"? I was only referring to scoring problems, the aggregation of pass-fail problem is pretty well specified and agrees with what you had said in this proposal.

1. what is the verdict of the empty set of results?, and

I would say that it should be AC. It seems you agree.

2. it should’t specify the order in which test cases are run

It should say that the result must be as if you ran the test cases in lexicographic order and and take the first non-accepted verdict. Rather than rewording the spec to carefully avoid saying which order things should run, I would suggest adding something explicitly allowing "optimizations" (or whatever it should be called?) as long as the externally observable behavior is as specified.

3. I see no reason to restrict this to pass-fail problems.

What do you mean? The definition quoted clearly is restricted to pass-fail problems, and just removing "For pass-fail problems" gives us an incorrect description of how the verdict of scoring problems are determined. I agree that the description should not be limited to pass-fail problems.

My suggestion to clarify both issues in 0.7.1 above is

// Aggregate verdict
// =================

// For a linearly ordered sequence of verdicts, the aggregate verdict is
// * the first occurrence of "WA", "TLE", or "RTE" if it exist
// * "AC" if the list is empty or only contains "AC"

The linear ordering would be given by lexicographic ordering of result.name.

I still don't understand the purpose of this text? The canonical description of how verdict are aggregated should be in the spec, and we shouldn't have a separate copy (or much worse, a different definition) in the spec of the expectations. If this text is just for completeness while discussing the proposal, I guess it's fine. I would rather just refer to the correct section of the spec though. (Currently https://www.kattis.com/problem-package-format/spec/2023-07-draft.html#grading).

As pointed out above, the description is in fact not correct for scoring problems.

Why is the ordering mentioned outside of the comment, and not in it?

[thorehusfeldt]

I guess then it is an error to specify permitted_aggregate_verdict for scoring problems, and an error to specify any kind of score-related expectation for pass-fail problems.

[niemela]

I guess then it is an error to specify permitted_aggregate_verdict for scoring problems

What is your guess based on? I don't think it should be.

and an error to specify any kind of score-related expectation for pass-fail problems.

Yes, that sounds reasonable. pass-fail problems don't have a score.