cicada-lang / cicada-plct Goto Github PK

let id = (T: Type, x: T) => x

compute id(Type)

the result is (x) => x: (x: T) -> T (tested in bb68336)

the expected result is (x) => x: (x: Type) -> Type, T should be replaced by Type

Problem:

We need a module system.

Solution 1:

Importing with full file name including extension.

Be able to import from relative path.

• Relative to current URL or file system path.

Be able to importing from URL.

• Like Deno: https://deno.land

fix test "solve Car -- deepWalk"
fix test "solve Cdr -- deepWalk"
fix test "solve Dot -- deepWalk"

Problem:

We need to support writing recursive function directly, beside using recursive combinators.

Solution 1:

Implement Coq like fixpoint, readback should handle fixpoint to avoid infinite loop.

Implement ReplCommand

• DefaultCommand -- repl

Problem:

Suppose we have the following definition of my_car and my_cdr:

function my_car(
  implicit A: Type,
  implicit B: (x: A) -> Type,
  pair: exists (x: A) B(x)
): A {
  return car(pair)
}

function my_cdr(
  implicit A: Type,
  implicit B: (x: A) -> Type,
  pair: exists (x: A) B(x),
): B(car(pair)) {
  return cdr(pair)
}

Given my_car(cons("a", "b")),
we can infer cons("a", "b") to be exists (_: String) String.

Then we must be able to solve the following equation:

solve (A: Type, B: (x: A) -> Type) {
  unify exists (x: A) B(x) = exists (_: String) String
}

The same problem occurs for unification between two Pis.

• We want to use { x, y, z } for object literal sugar for { x: x, y: y, z: z }

• Thus { x } is an object literal

• We also want to use { ... } for a sequence of code -- for example let

  {
    let x = ...
    f(x)
  }
  

• If we do not use return statement in sequence,
  we can not distinguish { x } from { return x }.

• If we use return in sequence, we can write something like:

  let y = { return x }
  

  which reads bad, because return sounds like an early return from function.

• What should we do?

class Isomorphism {
  cat: Category
  dom: cat.Object
  cod: cat.Object
  morphism: cat.Morphism(dom, cod)
  inverse: cat.Morphism(cod, dom)

  inverse_left: Equal(
    cat.Morphism(dom, dom),
    cat.compose(morphism, inverse),
    cat.id(dom),
  )

  inverse_right: Equal(
    cat.Morphism(cod, cod),
    cat.compose(inverse, morphism),
    cat.id(cod),
  )
}

Problem：

• cat.compose is a PiImplicit.
• take the cat.compose(morphism, inverse) in inverse_left as example.
• elaboration will insert ApImplicit based on the type of morphism,
  get cat.compose(implicit x1, implicit x2, morphism, implicit x3, inverse).
• solve it, get cat.compose(implicit dom, implicit dom, morphism, implicit dom, inverse),
  we write it like this, but actually solved value will not be substituted in place,
  but be saved in the env of the closure as x1 => dom.
• now dom is in scope, but only have type dom: cat.Object, no value, thus it is a neutral variable.
• in the following code block, fulfilling class type Isomorphism(cat, x.object, y.object)
  will provide the value of dom -- x.object.
• during fulfilling class type, when evaluating inverse_left's type,
  we have dom => x.object and x1 => dom in scope,
  evaluate variable x1 will only get the neutral variable dom,
  but not going further to get the value of dom -- x.object,
  this is the problem.

import { Isomorphism } from "../category/index.cic"
import { equal_swap, equal_compose } from "../equality/index.cic"

function terminal_object_isomorphism(
  cat: Category,
  x: Terminal(cat),
  y: Terminal(cat),
): Isomorphism(cat, x.object, y.object) {
  let f = x.morphism(y.object)
  let g = y.morphism(x.object)

  return {
    cat,
    dom: x.object,
    cod: y.object,
    morphism: y.morphism(x.object),
    inverse: x.morphism(y.object),

    inverse_left: equal_compose(
      x.morphism_unique(cat.compose(g, f)),
      equal_swap(x.morphism_unique(cat.id(x.object))),
    ),

    inverse_right: equal_compose(
      y.morphism_unique(cat.compose(f, g)),
      equal_swap(y.morphism_unique(cat.id(y.object))),
    ),
  }
}

Solution 1:

Use substInEnv.

It might be not enough for substInEnv to only handle variable,
maybe we also need to handle all Values
-- like deep walk
-- maybe called advanceByEnv (v.s. advanceBySolution).

Problem:

We need a built-in type for equivalence.

Solution 1:

Implement "the little typer"-like Equal:

• Equal
• Replace
• Refl
• Same

Problem:

During check of an Exp of type ImplicitPi,
use the information from the given type
to solve (typed) pattern variables in the ImplicitPi,
and use the Solution to insert ImplicitAp to the original Exp.

During infer of an Ap expression,
if the target of the Ap is of ImplicitAp,
we might infer some of its arguments' type,
use the information from these argTypes
to solve (typed) pattern variables in the ImplicitPi,
and use the Solution to insert ImplicitAp to the original Ap.

Constraints:

We should first be clear about the constraints (maybe the following).

• During infer, an application f(x, y, z) of an expression f
  of ImplicitPi type (implicit A: Type, x: String, y: Pair(A, A), z: String) -> A,
  must resolve all of its pattern variables in this infer.

  • Application can curry, as long as it resolve all pattern variables.

  • f(x, y) -- ok

  • f(x) -- not ok

• During check, an application check f(x, y, z): String
  can use return type to resolve pattern variables.

• During check, a variable expression check id: (String) -> String
  of ImplicitPi type id: (implicit A: Type) -> (A) -> A
  must resolve all of its pattern variables using the given type.

• The above constraints require a new constraint:

  • All pattern variables must occur at the start of the FoldedPi.

  If we break this constraint, we may say
  "must resolve all of its pattern variables until next ImplicitPi"
  instead of "must resolve all of its pattern variables".

• function expression can have return type.

• function stmt can drop return type and let it infer.

just like Pi and Ap.

tests required.

This question occurs during ImplicitAP insertion,
because the inserted are Cores.

Where the inferred argType are inferred in current ctx,
but Values are not evaluated in current ctx.

We need to prove it is safe to not use freshen,
maybe in a simplified project
with only untyped lambda calculus and NbE.

• pass test "check Cons -- my_cons -- constraint-based unification"
• globals.cons
• add test compute just cons

Problem:

In js/ts there are new User() and new User.

How should we handle nullary applications?

Problem:

We need a standard formatter.

To help users avoid arguing about code formating.

Solution 1:

Implement formatExp and formatStmt(s).

These functions should take formatting context as argument,
and recurse down the Exp and Stmt.

Solution 2:

Learn from prettier API, and write prettier plugin.

https://prettier.io/docs/en/plugins.html

[maybe] checkByInfer -- when inferred type is ImplicitPi, handle it specially

• infer-cons.test.ts

• infer-objekt.test.ts

Problem:

We need a playground website, to share code examples and report bugs.

Solution 1:

Copy the design of existing playground and add features.

Designs to copy:

• typescript playground: https://www.typescriptlang.org/play
• rust playground: https://play.rust-lang.org
• tailwindcss playground: https://play.tailwindcss.com
• vue playground: https://sfc.vuejs.org

maybe, maybe not.

After adding the return type support, the function experssion will be written like:

function(x: String): String x 

It's strange to put return type and the body of function on an equal footing.

As we have (x: String) => x for the simple function, we can use function-style only for the complex function with Sequence on the body:

function(x: String): String {
  return x
}

Problem:

We need a way to distinguish consistency levels.

For examples:

• side effect
• type in type

Solution 1:

One module, one consistency level.

Use file extension to distinguish consistency levels.

• .c0, .c1, .c2, ...

Higher level can not import lower level module.

Problem:

We need to support inductive datatype to let user define new types.

Solution 1:

Maybe add the following new values:

• Datatype
• TypeConstructor
• DataConstructor

Write test for each case.

• try to write failing test that can be fixed by using deepWalk here.

The semantics of pi_binding and fn_binding are different.

To support recursive function, beside termination-check we also need coverage-check.

The coverage-check of function clauses, can be implemented separately from the termination-check.

Solution 1:

• Compute the max depth of all patterns in all clauses of a function.
• Generate data up to the given depth.
• Assert all generated data are covered by the clauses.

[maybe] insertImplicitFn -- after foldFn

See fu peng's paper: https://homepage.divms.uiowa.edu/~astump/papers/fu-stump-rta-tlca-14.pdf

We should setup an error report framework (and test it) as soon as possible.

• ElaborationError might have span