yzyzsun / cp-next

The Next Generation of Compositional Programming

CP - The Next Generation

CP is a compositional programming language, founded on a core calculus named Fi+. The next-gen CP is shipped with more features and implemented in PureScript (a Haskell-like language that compiles to JavaScript).

Language Features

• A typed lambda calculus with five base types (Int Double String Bool ()), built-in arrays ([1; 2; 3] : [Int]), and some built-in operations over them;
• The merge operator¹, disjoint intersection types² and disjoint polymorphism³;
• Generalized record operations with type difference⁴;
• Iso-recursive types with nominal unfoldings⁵;
• Nested composition and distributive subtyping⁶;
• Compositional programming⁷ with first-class traits⁸;
• Type-directed operational semantics for Fi+⁹ with {HOAS,substitution,closure}-based {big,small}-step variants;
• A compositionally embedded DSL for document authoring called ExT¹⁰.

Online Demo

PLGround provides an online CP interpreter and a wiki-like document repository. Documents are written in ExT and rendered in your web browser.

Since the frontend code uses the Fetch API, PLGround is expected to work on Chrome 42+, Firefox 39+, Edge 14+, Safari 10.1+, or other modern browsers.

CLI Setup

If you want to run CP programs locally using a CLI, you can follow the procedure below:

• First of all, you need to install Node.js.
• Then execute npm install to get all of the dev dependencies.
• After installation, you can choose either of the following npm scripts:
  • npm start to run a REPL;
  • npm run compiler "*.cp" to compile CP files to JavaScript;
  • npm test to run a test suite checking examples/*.cp.

If you want to start a PLGround server locally, take the first two steps above and then:

• Install Ruby.
• Execute bundle install to get Ruby on Rails and other gems.
• Execute npm run build if you have modified PureScript code, grammar files, or app.js (i.e. every file that plground/app/assets/javascripts/bundle.js depends on).
• Execute npm run server to start a web server.

REPL Example

$ npm start
......
Next-Gen CP REPL, dev version (default mode: HOAS)

> :mode StepTrace
> 1+2*3

(1 + (2 * 3))
......
(1 + 6)
↓ Step-BinaryV
7

> :timing
> :mode HOAS
> :load examples/bench.cp

125000
Time: 1.024s

Grammar Maintenance

There are currently four different copies of the CP grammar. If you want to modify the grammar, please remember to change them all:

1. PureScript parser based on parser combinators, used in REPL (see the code here).
2. ANTLR-generated LL(*) parser, used in PLGround (see this directory).
3. Lezer-generated incremental parser for the CodeMirror 6 code editor (see the grammar file).
4. TextMate grammar specification for VS Code, mainly keyword highlighting (see the JSON file).

VS Code Extension

CP language support can be found on VS Code Marketplace.

If you want to build it from scratch, please execute npm run vscode. Then a .vsix file will be generated in vscode/.

Next-Gen CP versus Original CP

The original CP (hereinafter CP1) is introduced and formalized in our TOPLAS paper Compositional Programming. Its reference implementation is included in the artifact. The next-gen CP (hereinafter CP2) polishes the syntax of CP1 and extends it with new features, but their semantics are essentially the same. CP2 has a brand-new implementation that supersedes the original one.

Concerning implementation languages, CP1 is written in Haskell, while CP2 is written in PureScript. Thus, CP2 can easily run in a web browser without losing the ability to run traditionally in a terminal. Concerning the semantics of the core calculus Fi+, it is further elaborated to F-co in CP1 but has direct operational semantics in CP2. Furthermore, new features recently added and some syntactic differences can be found at CHANGELOG.md.

Footnotes

1. Jana Dunfield. Elaborating Intersection and Union Types. In JFP 2014. ↩

2. Bruno C. d. S. Oliveira, Zhiyuan Shi, and João Alpuim. Disjoint Intersection Types. In ICFP 2016. ↩

3. João Alpuim, Bruno C. d. S. Oliveira, and Zhiyuan Shi. Disjoint Polymorphism. In ESOP 2017. ↩

4. Han Xu, Xuejing Huang, and Bruno C. d. S. Oliveira. Making a Type Difference. In POPL 2023. ↩

5. Yaoda Zhou, Jinxu Zhao and Bruno C. d. S. Oliveira. Revisiting Iso-Recursive Subtyping. In TOPLAS 2022. ↩

6. Xuan Bi, Bruno C. d. S. Oliveira, and Tom Schrijvers. The Essence of Nested Composition. In ECOOP 2018. ↩

7. Weixin Zhang, Yaozhu Sun, and Bruno C. d. S. Oliveira. Compositional Programming. In TOPLAS 2021. ↩

8. Xuan Bi and Bruno C. d. S. Oliveira. Typed First-Class Traits. In ECOOP 2018. ↩

9. Andong Fan, Xuejing Huang, Han Xu, Yaozhu Sun, and Bruno C. d. S. Oliveira. Direct Foundations for Compositional Programming. In ECOOP 2022. ↩

10. Yaozhu Sun, Utkarsh Dhandhania, and Bruno C. d. S. Oliveira. Compositional Embeddings of Domain-Specific Languages. In OOPSLA 2022. ↩