UCS/UPS tracking issue

[LPTK]

Issue to track the parts of the UCS implementation that are still incomplete or wrong – please update with more cases as you find them.

Translation

• Support virtual constructors for pattern matching against tuples. Note as of Jan 2024: We implemented simple tuple pattern in New UCS desugarer and rudimentary PreTyper #194 and we will support advanced tuple patterns, for example, splice tuple patterns, in the near future.
• Do not duplicate default cases and insert local function definitions instead.
  • Note as of Jan 2024: We paved the road for this in New UCS desugarer and rudimentary PreTyper #194 and we will implement this feature in the near future.
  • Note as of Nov 2025: This has been solved in Unify patterns in UCS and UPS #336. Instead of using local functions, we use Block and Break.

Locations

• Track scrutinee locations with Scrutinee.Source. (Note: it was removed in new desugarer.)

• No location reported in:

  fun testF(x) = if x is
    Foo(a) then a
    Foo(a) then a
  //│ ╔══[WARNING] duplicated branch
  //│ ╙──

Reporting

• Warn when an is test has a single pattern
  Though maybe we shouldn't warn when it's conjuncted with other things, as then the is may be used to bind expressions, as in if xs is x :: xs and mapPartition(f, xs) is (as, bs) and ...

String patterns overhaul

• Make a PR that overhauls string patterns; currently, they misbehave in some cases; eg

  Example

  pattern Digits = ("0"..="9") ~ (Digits | "")
  pattern DigitsCommas = Digits | Digits ~ "," ~ DigitsCommas
  pattern Integer = "0" | ("1"..="9") ~ (DigitsCommas | "")
  pattern FractionalPart = "." ~ Digits
  pattern ExponentPart = ("e" | "E") ~ ("+" | "-" | "") ~ Integer
  
  // FIXME: does not work!
  // pattern NumberStr = Integer ~ (FractionalPart | "") ~ (ExponentPart | "")
  
  // Works
  pattern NumberStr = Integer | Integer ~ FractionalPart ~ (ExponentPart | "")
  
  // FIXME: `Number` doesn't recognize commas
  pattern AsNumber = (NumberStr & n) => Number(n)

Fix pattern extraction semantics

• Patterns like Pair(0 => 1, 0 => 1) should rebuild the outer ctors
• Patterns like C(_, 0 => 1) should fail when the first param of C is private, as the thing can't be rebuilt
• Patterns like P(Transf) should warn about a discarded transformation when P is a HOP – users should write P(Transf as _) instead

Fixed point patterns

• Avoid retraversing rec pattern prefixes when no change happened (see: EvaluationContexts2, StackParse)

[LPTK]

• hygiene

  :NewParser
  :NewDefs
  :NoJS
  
  class Union<Region>(a: Region, b: Region)
  //│ class Union[Region](a: Region, b: Region)
  
  // * [FIXME:UCS] unhygienically desugars to:
  // | | | | Desugared term: case x of { Union => let x = (x).a in let y = (x).b in x }
  fun hmm(x) =
    if x is Union(x, y) then x
  //│ fun hmm: Union[{b: anything} & 'a] -> 'a
  
  fun hmm(x) =
    if x is Union(z, y) then x
  //│ fun hmm: Union['Region] -> Union['Region]

[LPTK]

• There's a problem witth he builtin true/false in the current UCS impl

:NewParser
:NewDefs

module Nil
class Cons[A](head: A, tail: Cons[A] | Nil)
//│ module Nil()
//│ class Cons[A](head: A, tail: Cons[A] | Nil)

// FIXME
fun filtermap(f, xs) = if xs is
  Nil then Nil
  Cons(y, ys) and f(ys) is
    false then filtermap(f, ys)
    true then Cons(y, filtermap(f, ys))
    [true, z] then Cons(y, filtermap(f, ys))
//│ ╔══[ERROR] identifier not found: ys
//│ ║  l.26: 	  Cons(y, ys) and f(ys) is
//│ ╙──      	                    ^^
//│ ╔══[ERROR] Type mismatch in application:
//│ ║  l.26: 	  Cons(y, ys) and f(ys) is
//│ ║        	                  ^^^^^^^^
//│ ║  l.27: 	    false then filtermap(f, ys)
//│ ║        	^^^^^^^^^
//│ ╟── reference of type `false` is not an instance of type `number`
//│ ║  l.27: 	    false then filtermap(f, ys)
//│ ╙──      	    ^^^^^
//│ ╔══[ERROR] Type mismatch in application:
//│ ║  l.26: 	  Cons(y, ys) and f(ys) is
//│ ║        	                  ^^^^^^^^
//│ ║  l.27: 	    false then filtermap(f, ys)
//│ ║        	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//│ ║  l.28: 	    true then Cons(y, filtermap(f, ys))
//│ ║        	^^^^^^^^
//│ ╟── reference of type `true` is not an instance of type `number`
//│ ║  l.28: 	    true then Cons(y, filtermap(f, ys))
//│ ╙──      	    ^^^^
//│ ╔══[ERROR] type identifier not found: Tuple#2
//│ ╙──
//│ fun filtermap: ((error | Cons['A] | Nil) -> number & (Cons['A] | Nil) -> error, Cons['A0] | Nil,) -> (Cons['A1] | Nil | error)
//│   where
//│     'A := 'A0
//│     'A0 <: nothing
//│ Code generation encountered an error:
//│   unknown match case: Tuple#2

module True
module False
//│ module True()
//│ module False()

class Pair[A, B](lhs: A, rhs: B)
//│ class Pair[A, B](lhs: A, rhs: B)

fun filtermap(f, xs) = if xs is
  Nil then Nil
  Cons(y, ys) then if f(y) is
    True then filtermap(f, ys)
    False then Cons(y, filtermap(f, ys))
    Pair(True, z) then Cons(z, filtermap(f, ys))
//│ fun filtermap: ('head -> (False | Pair[anything, 'A] | True), Cons['head] | Nil,) -> (Cons['A] | Nil)
//│   where
//│     'head <: 'A

[chengluyu]

• Fix unhygienic bindings in HygienicBindings.mls and shared/src/test/diff/ucs/Hygiene.mls
• Should report warnings in shared/src/test/diff/ucs/Wildcard.mls
• Proper errors in shared/src/test/diff/ucs/PlainConditionals.mls
• Some parser failures in shared/src/test/diff/ucs/ParseFailures.mls
• Support or in shared/src/test/diff/ucs/Or.mls
• Leading and in shared/src/test/diff/ucs/LeadingAnd.mls
• Incomplete example in shared/src/test/diff/ucs/JSON.mls

[chengluyu]

• Warning message regression. It should report the first duplicated branch.
  https://github.com/chengluyu/mlscript/blob/ee1ab193234e9d59ad0ce3fa82e2c922efd8d56e/shared/src/test/diff/ucs/DirectLines.mls#L50-L63
• Show terms properly, not using the internal debug string. https://github.com/chengluyu/mlscript/blob/ee1ab193234e9d59ad0ce3fa82e2c922efd8d56e/shared/src/test/diff/ucs/Exhaustiveness.mls#L51

[chengluyu]

• Give warnings for non-conditional UCS. See

  mlscript/shared/src/test/diff/nu/BadUCS.mls

  Line 75 in ee1ab19

  fun foo0(x, y) = if x is y then 0

  Update as of the introduction of new desugarer in Jan 2024: This case is interesting, it means that we bind x to y which shadows parameter y, but someone may think it means if x == y then 0.

• Precise scrutinee tracking and merge explicit let bindings:

  mlscript/shared/src/test/diff/ucs/HygienicBindings.mls

  Line 31 in 66d41f2

  // FIXME: Precise scrutinee identification (easy)

[LPTK]

• One more hygienic bindings thing to make sure and address

  mlscript/shared/src/test/diff/ucs/CrossBranchCapture.mls

  Lines 8 to 12 in 687f39d

  	// * FIXME should be rejected
  	fun process(e) =
  	if e is
  	Numb(n) and n > 0 then n
  	Numb(m) then n

• Warn against shadowing pattern variables

  mlscript/shared/src/test/diff/ucs/CrossBranchCapture.mls

  Lines 49 to 52 in 687f39d

  	// * FIXME should warn, be rejected, or compare both values for equality
  	fun process(e) =
  	if e is
  	Pair(Numb(n), Numb(n)) then n

[LPTK]

• It seems that this should work, but is currently warned about due to an overly restrictive implementation:

  fun fold(opt, k, d) = if opt is
    None then d
    refined(Some) then k(opt)
    else k(opt)
  //│ ╔══[WARNING] inconsistent refined pattern
  //│ ║  l.67:     None then d
  //│ ║            ^^^^
  //│ ╟── pattern `Some` is refined
  //│ ║  l.68:     refined(Some) then k(opt)
  //│ ║                    ^^^^
  //│ ╟── but pattern `None` is not refined
  //│ ║  l.67:     None then d
  //│ ╙──          ^^^^

[LPTK]

• Currently, or is not supported – see:

  mlscript/hkmc2/shared/src/test/mlscript/ucs/general/LogicalConnectives.mls

  Lines 39 to 43 in ac5ce9c

  	:fixme
  	true or test(42)
  	//│ ╔══[ERROR] Logical `or` is not yet supported.
  	//│ ║ l.40: true or test(42)
  	//│ ╙── ^^^^^^^^

[chengluyu]

Refactorings

• Rewrite the Desugarer. Currently, semantics.Pattern is not used by Desugarer, which makes it unable to support many useful patterns.
• Some refactoring of FlatPattern and Pattern can be postponed until the Desugarer is rewritten.
• A lot of the work for checking arguments and pattern arguments is done in Normalization. This should be handled in the NaiveCompiler instead.

Missing Features in UPS

Besides that, there are still some unimplemented features:

• Support tuple patterns in pattern definitions.
• Support locally recursive patterns using as. (Needs clarification)
• Implement compilation of string patterns. Although there are many examples, some string patterns still don't work correctly.

  mlscript/hkmc2/shared/src/test/mlscript/rp/regex/Simplification.mls

  Lines 18 to 28 in 513b1ea

  	pattern XsX = Xs ~ "x"
  	// In the following tests, the left-hand side of concatenation should not
  	// eagerly consume all letters. We should compile these string patterns even in
  	// naive compilation, rather than just transliterate them.
  	:expect true
  	:fixme
  	"xxxxxxxxxxxxxx" is XsX
  	//│ ═══[RUNTIME ERROR] Expected: 'true', got: 'false'
  	//│ = false