Skip to content
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

Specifying problem.yaml, small changes suggested #372

Open
thorehusfeldt opened this issue Mar 4, 2025 · 14 comments
Open

Specifying problem.yaml, small changes suggested #372

thorehusfeldt opened this issue Mar 4, 2025 · 14 comments

Comments

@thorehusfeldt
Copy link
Contributor

thorehusfeldt commented Mar 4, 2025

Here’s a CUE schema for problem.yaml:

package problemformat

import "list"
import "time"

#ProgrammingLanguage: "ada" | "algol68" | "apl" | "bash" | "c" | "cgmp" | "cobol" | "cpp" | "cppgmp" | "crystal" | "csharp" | "d" | "dart" | "elixir" | "erlang" | "forth" | "fortran" | "fsharp" | "gerbil" | "go" | "haskell" | "java" | "javaalgs4" | "javascript" | "julia" | "kotlin" | "lisp" | "lua" | "modula2" | "nim" | "objectivec" | "ocaml" | "octave" | "odin" | "pascal" | "perl" | "php" | "prolog" | "python2" | "python3" | "python3numpy" | "racket" | "ruby" | "rust" | "scala" | "simula" | "smalltalk" | "snobol" | "swift" | "typescript" | "visualbasic" | "zig"
#LanguageCode: =~ "^[a-z]{2,3}(-[A-Z]{2})?$"
#Type: "pass-fail" | "scoring" | "multi-pass" | "interactive" | "submit-answer"

#Source: string | {
	name!: string
	url?:  string
}

#Person: string
#Persons: #Person | [#Person, ...#Person]

#Problem: {
	problem_format_version!: =~"^[0-9]{4}-[0-9]{2}(-draft)?$" | "draft" | "legacy" | "legacy-icpc"

	type?: *"pass-fail" | #Type | [#Type, ...#Type]
	if (type & [...]) != _|_ {
		_policy: true &
			!(list.Contains(type, "scoring") && list.Contains(type, "pass-fail")) &&
			!(list.Contains(type, "multi-pass") && list.Contains(type, "submit-answer")) &&
			!(list.Contains(type, "interactive") && list.Contains(type, "submit-answer"))
	}

	name!: string | {[#LanguageCode]: string}

	uuid!:    string

	version?: string

	credits?: #Person | {
		authors!:                                                        #Persons // TODO: Made authors mandatory
		["contributors" | "testers" | "packagers" | "acknowledgements"]: #Persons
		translators?: [#LanguageCode]: #Persons
	}

	source?: #Source | [#Source, ...#Source]
	license: *"unknown" | "public domain" | "cc0" | "cc by" | "cc by-sa" | "educational" | "permission"
	rights_owner?: _
	if license != "unknown" && license != "public domain" && credits.authors == _|_ && source == _|_ {rights_owner!: #Person}
	if license == "unknown" || license == "public domain" {rights_owner: null}

	embargo_until?: time.Format("2006-01-02") | time.Format("2006-01-02T15:04:05Z")

	limits?:        #Limits

	keywords?: [string, ...string] 

	languages?: *"all" | [#ProgrammingLanguage, ...#ProgrammingLanguage]

	allow_file_writing?: *false | true

	constants?: [=~"^[a-zA-Z_][a-zA-Z0-9_]*$"]: int | float | string
}

#TimeLimit: "time_limit" | "compilation_time" | "validation_time"
#SizeLimit: "memory" | "output" | "code" | "compilation_memory" | "validation_memory" | "validation_output"
#Limits: {
	time_multipliers?: {
		ac_to_time_limit?:  float | *2.0
		time_limit_to_tle?: float | *1.5
	}
	time_resolution?:   float & >0 | *1.0
	[#TimeLimit]:       float & >0
	[#SizeLimit]:       int & >0
	validation_passes?: int & >0 | *1
}

You can play around with it live at https://cuelang.org/play/?id=w85MrRg1lkY#w=function&i=cue&f=eval&o=cue . In particular, play around with the YAML snippets at the bottom, which contain many examples of validated problem.yaml. Please try to break the schema by inventing YAML that you think should validate (but doesn’t) and vice versa.

Changes from Current Draft

The schema solidifies several unclear details in the prose specification, but I also introduced some changes. Here goes.

C1. Keywords

The spec says

keywords?: [...!~" "] // no spaces

I say

keywords?: [string, ...string] // nonempty sequence of string

C2. Single Translators

The spec says

Map of strings to sequences of persons

which disallows the spec's own example of

translators:
    da: Mads Jensen <[email protected]>
    eo: Ludoviko Lazaro Zamenhofo

I say

credits: translators?: [#LanguageCode]: #Persons

where

#Person: string
#Persons: #Person | [#Person, ...#Person]

C3. Limit time types

The spec is not clear about what numerical values are allowed for most of the limits. I have

#TimeLimit: "time_limit" | "compilation_time" | "validation_time"
#SizeLimit: "memory" | "output" | "code" | "compilation_memory" | "validation_memory" | "validation_output"
#Limits: {
	[#TimeLimit]:       float & >0
	[#SizeLimit]:       int & >0
       // other fields
}

C4. Default validation_passes

The spec has validation_passes defaulting to 2. I think it should be

validation_passes?: int & >0 | *1

C5. Empty type sequence

The spec allows

type: []

which I find meaningless. I suggest

	type?: *"pass-fail" | #Type | [#Type, ...#Type]

where #Type: "pass-fail" | "scoring" | "multi-pass" | "interactive" | "submit-answer"

C6. Mandatory credits.authors

I have

credits?: #Person | {
		authors!:  #Persons
   ...
    } 

so that authors must be present in a credits struct. This is more stringent than the draft spec.

Q1. Question: #Person format

The draft spec has

A person is specified as a string with the full name, optionally followed by an email wrapped in <>, (e.g.: Full Name or Full Name <[email protected]>).

I just have

#Person: string

This allows somebody called "@Lice" or "Shifty << McShiftyson". Should we forbid such names? How?

For instance, in the schema for submissions.yaml I now maintain at https://github.com/thorehusfeldt/problem-package-schemas/blob/master/cue/submissions.cue I have

#person: =~"^[^<]+(<[^>]+>)?$" // "Alice" or "Bob <bob@com>"

which is slightly more restrictive with respect to < and >; it would disallow "Shifty << McShiftyson".

Q2. Question: Lenient Natural Language Codes

I have

#LanguageCode: =~ "^[a-z]{2,3}(-[A-Z]{2})?$"

rather than a large regex of the ISO-specified language codes that actually exist. I think this is fine; I don’t want us to have an opinion on whether fil exists compared to xyx or po-BR.

@Tagl
Copy link
Contributor

Tagl commented Mar 5, 2025

This allows somebody called "@Lice" or "Shifty << McShiftyson". Should we forbid such names? How?

I'll get to the rest of your comments later, but I think it is a bad idea to make assumptions about what is or isn't a name.

@thorehusfeldt
Copy link
Contributor Author

thorehusfeldt commented Mar 5, 2025

(I clarified under Q1 above why this is a question at all.)

@mpsijm
Copy link
Contributor

mpsijm commented Mar 7, 2025

  • C1: Looks like the requirement to not have spaces appeared in Simplify the metadata table #270, but it's not clear to me where this comes from. The discussion in Are keywords: and languages: in problem.yaml lists or strings #88 is just about changing from a space-separated string to a YAML list, but I don't see why the keywords themselves can't have spaces, so I'm fine with "just" a list of strings 🙂
  • C2: Simple clarification, agreed. BAPCtools already allows this.
  • C3: Agreed with making these fields & >0. Note that there are only two fields in limits that allow float according to the spec, namely time_limit and time_resolution. The timeouts are generally int, because the resolution with which we can tell a system to abort a program with, is in seconds, due to kernel reasons.
  • C3a: I think that the two keys in time_multipliers should be float & >=1.
  • C4: The default is 2, but it's only used when "multi-pass" in type. This key is ignored when the problem is not multi-pass, but it looks like the spec doesn't say this yet. (am I correct in saying this @mzuenni? Since you implemented multi-pass in BAPCtools)
  • C5: So you're saying that the spec should read "String or non-empty sequence of strings" instead? Sounds good, but then we should probably write "non-empty" in a couple of other places as well 😂 E.g. name should be a string or a non-empty map of strings. But other sequences/maps could potentially be empty (e.g. credits and its sub-keys, source, or constants).
  • C6: Not sure about this one. credits is not required in problem.yaml, so I don't see why we should force authors to be provided when credits is specified as a map.
  • Q1: I agree with how you would like to restrict a name, since that would help parsing an email address from a Person. But I also agree with Are keywords: and languages: in problem.yaml lists or strings #88 (comment), where the argument was made that we should not be "manually" parsing things that could be specified in YAML directly. We could decide for a Person to be specified as {name: string, email: string} (perhaps with a regex on the email field, but IMO that's optional).
  • Q2: Note that your regex rejects (at least) zh-Hans and zh-Hant for Chinese (simplified and traditional, respectively). Regarding "don't want us to have an opinion on whether [a language code] exists", perhaps we don't need a regex at all 😛

@mzuenni
Copy link
Contributor

mzuenni commented Mar 7, 2025

  • C4: The default is 2, but it's only used when "multi-pass" in type. This key is ignored when the problem is not multi-pass, but it looks like the spec doesn't say this yet.

yes that key is meaningless for non multi-pass problems

@thorehusfeldt
Copy link
Contributor Author

thorehusfeldt commented Mar 7, 2025

Q1: Yes, the correct way would be

#Person = string |  { name:  string, email: string }

I’ve tried to make that point some time ago. (It’s how we handle #Source.) Even better,

#Person = string |  { name!:  string, email?: string, orcid?: string }

C4: Another issue I’ve flagged before. The number of passes should not be given in two different places in problem.yaml. Certainly the defaults should not be not multi_pass and that simultaneously validation_passes: 2. (We would need a whole new concept of “YAML default” to make sense of this.)

A more readable, useful, parseable and maintainable schema would like something like this:

scoring?: *false | true
interactive?: *false | true
limits?:
  validation_passes?: *1 | int &>1
*{ submit_answer?: false } | { 
   submit_answer: true, 
   interactive: false, 
   limit.validation_passes : 1
}

@thorehusfeldt
Copy link
Contributor Author

C3: Interesting. So I think you’re saying

time_multipliers?: {
	ac_to_time_limit?:  float & >=1 | *2.0
	time_limit_to_tle?: float & >=1 | *1.5
}
time_resolution?:   float & >0 | *1.0
time_limit:       float & >0
["compilation_time" | "validation_time" ] : int & >0
[#SizeLimit]: int & >0

This sounds good to me.

@mpsijm
Copy link
Contributor

mpsijm commented Mar 7, 2025

  • Q1: I think adding orcid only makes sense if we can list our problems on our OrcID profile (which would be awesome, btw) 😛
  • C4: Hmm... The schema you suggest kind of makes every problem implicitly multi-pass, but with validation_passes: 1, it behaves as a "regular" problem? I do think that specifying type: multi-pass for this explicitly, would better signal intention.
    If it does not make sense to have validation_passes default to 2 when type includes multi-pass, can we then say that limits.validation_passes is required if (and only if) type includes multi-pass?

@mzuenni
Copy link
Contributor

mzuenni commented Mar 7, 2025

I do think that specifying type: multi-pass for this explicitly, would better signal intention.

I agree and prefer this (we also don't use something like output limit to decide interactive). But I don't understand the issue in the first place ^^' What is the problem with validation_passes defaulting to two and only being allowed if multi-pass is set?

(btw. I would say that validation passes must be at least 2, its multi-pass not single pass...)

@thorehusfeldt
Copy link
Contributor Author

thorehusfeldt commented Mar 8, 2025

What is the problem with validation_passes defaulting to two and only being allowed if multi-pass is set?

We can do that, and I quite like the idea. That’s a different schema again. (This is exactly why we’re here.) Let me see if I can write that:

   if (type & [...]) != _|_ {                   // is type a list?
       if list.Contains(type, "multi-pass") {   // does the list contain "multi-pass"?
             validation: passes: *2 | int & >1  // allow this field (else it's forbidden) with default 2
       }
   }

Do we like this? (I do.)

@mpsijm
Copy link
Contributor

mpsijm commented Mar 8, 2025

Yes, looking good 😄 Can two nested ifs be combined into one using && ("and") in Cue?

Also note that, in BAPCtools, we currently allow type: multi-pass as single string (so no list), leaving the "pass-fail" implied. But maybe that's also because we don't support scoring at all, so then it makes sense to omit the obvious pass-fail for compactness? On the other hand, pass-fail is the default when compared to scoring, so IMO it's fine to leave it implied. Or we should split off scoring: bool from type?: "submit-answer" | list["interactive" | "multi-pass"] anyway, to simplify the mutually-exclusive constraints 😛

@thorehusfeldt
Copy link
Contributor Author

thorehusfeldt commented Mar 8, 2025

(No, CUE very deliberately does not allow that kind of combination. Evaluation order must be independent. There’s a deep reason for this, going back to compositionality, which I will not elucidate here.)

Yes, the fact that type does too many things continues to hurt us. It’s simply a bad idea. Here’s what we need:

if (type & [...]) != _|_ {
    if list.Contains(type, "multi-pass") { validation_passes: *2 | int & >=2 }
}
if (type & string) != _|_ {
    if type == "multi-pass" { validation_passes: *2 | int & >=2 }
}

I observe again that type is an unnecessary mess (note also the terrible set of rules for ensuring various mutually excluding values). Note how easy it would be to just have one place, such as limits.validation_passes, and actually use YAML in the intended fashion:

scoring: *false | true
validation_passes: *1 | int & >= 1
# and so on.

Readable, easy-to parse, accessible, easy to communicate, etc. No rules need ever be explained or checked or parsed or validated. A schema-aware editor would give useful feedback, etc. etc.

@thorehusfeldt
Copy link
Contributor Author

With the above schema, we validate all of:

---
# Specify validation passes for multi-pass problem
limits:
  validation_passes: 2 # this is the default
type: "multi-pass"
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02
---
# limits.validation_passes would default to 2
type: "multi-pass"
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02
---
# Type can be list
type: ["multi-pass"]
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02
---
type: ["multi-pass"]
limits:
  validation_passes: 2 # this is the default
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02

and reject both of the following:

# Don't specify validation passes for problems that aren't multi-pass
limits:
  validation_passes: 1
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02
---
# Multi-pass problems need at least two passes
type: "multi-pass"
limits:
  validation_passes: 1
name: Hello
uuid: 550e8400-e29b-41d4-a716-446655440000
problem_format_version: 2023-02

@mpsijm
Copy link
Contributor

mpsijm commented Mar 8, 2025

(By the way, we're now continuing the discussion from #131 and #167, linking them for good measure)

Your schema with two nested ifs is looking good to me. For the further simplification, I see two arguments against your suggestion:

  • When we say that something is "a multi-pass problem", having only validation_passes to signal this is slightly unclear, whereas mentioning multi-pass in type signals that the problem "is multi-pass", as was also discussed in Move more information into type #131. The fact that limits.validation_passes then only makes sense when "multi-pass" in type (note that this Python syntax would support both str and list 😂), is fine by me (I agree with Specifying problem.yaml, small changes suggested #372 (comment)).
  • The mutual-exclusiveness of submit-answer and interactive | multi-pass will become messy anyway, whether we put them into type or into separate fields. And then I prefer having them in a single type field, because it feels natural to talk about "an interactive multi-pass problem".

Whether we split off scoring from type is a different discussion that I don't have a strong opinion about, because I only work with pass-fail problems. I agree that it would be nice, to simplify some constraints in the schema and the specification, but I have no clue what impact this has on concrete problems with scoring.

@thorehusfeldt
Copy link
Contributor Author

I’ve summarised my thoughts on type at #378

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants