[Epic] String Implementation

[Protryon]

• Write RFC.
• [Feature] Extend ABNF for strings feature  #941 - Extend ABNF grammar with char type, character literals, and string literals.
• Extend abstract syntax withchar type, character literals, and string literals.
  • [Feature] Char Abstract Syntax #939 - char Portion.
  • [Feature] String Abstract Syntax #943 - string Portion.
• Extend lexer and parser to handle char type, character literals, and string literals.
  • [Feature] Char Parsing #940 - char Portion.
  • [Feature] String Parsing #944 - string Portion.
• [Feature] String Reducers + Canonicalization #945 - Extend canonicalization to turn string literals into array inline expressions.
• [Feature] Char Type Inference #942 - Extend type inference to handle characters.
• Extend flattening transformations (e.g. constant folding) to handle characters.
  • Should already be handled by the constant folding code that exists. We should test to make sure though.
• [Feature] Field Compiler R1CS Synthesis  #950 - Extend synthesis of R1CS to handle characters with == and !=.
• [Feature] Console Functions Refactor #949 - Refactor console functions to use string literals -- affects grammar, abstract syntax, etc.
• Add support for operations on characters and strings.
  • [Feature] Char Operations #946 - char Portion.
  • [Feature] String Operations #947 - string Portion.
• Extend zero-knowledge proof generation to handle characters.
• [Feature] UTF-8 Input/Output Conversion #951 - Add UTF-8 conversion for input/output.
• Add tests for all the character and string features spread throughout features:
  • [Feature] Char Parsing #940
  • [Feature] Char Type Inference #942
  • [Feature] String Parsing #944
  • [Feature] String Reducers + Canonicalization #945
  • [Feature] Char Operations #946
  • [Feature] String Operations #947
  • [Feature] Field Compiler R1CS Synthesis  #950
  • [Feature] UTF-8 Input/Output Conversion #951
• Extend developer documentation to describe all the character and string features. Will be a PR on leo-welcome to add documentation for the features. Could be done for each feature as they are done, or we could do them all at once.

[acoglio]

In regard to 'char type as alias for field', I'd like to make sure we are all on the same page. According to the RFC, and I believe previous discussions, char is a separate type from field, at the Leo language level. Concretely:

let c:char = 3field; // type error
let c:char = 3field as char; // legal when we have type casts

We implement char as field values (in the range 0 to 10FFFF) in R1CS, similarly to how we implement bool as field values (in the range 0 to 1), but char, bool, and field are all separate types. In particular, the type inference will need a small extension to handle the new type char. (Having a separate char type also leaves the door open to a different R1CS representation in the future, should that prove useful.)

[acoglio]

I expanded and reordered @Protryon's initial list. Feedback/amendments welcome as usual.

[damirka]

Updated task description, added links to sub issues for easier access.

[damirka]

@acoglio I've marked resolved issues. Only two we got left are:

• [Feature] Extend ABNF for strings feature  #941 (close issue when it's done)
• Update developer documentation

[acoglio]

@damirka Thanks, I've merged the ABNF PR and checked off the item.

[damirka]

Sent documentation update to welcome branch. So this epic can be considered complete once we have new Leo release.

[acoglio]

This is now complete.