Gabriella439 / Gabriella439/Haskell-Morte-Library

Should we add Self types?

Open
#30 31 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
384
Forks
25
PR merge metrics
No merged PRs in 30d

Description

The Scott encoding is an important tool that is ultimately necessary for many efficient algorithms on the untyped lambda calculus. It is impossible to encode Scott encoded values on Morte. Things such as `zipWith` and `min` are quadratic. [Self Types](http://homepage.cs.uiowa.edu/~astump/papers/fu-stump-rta-tlca-14.pdf) enable the Scott Encoding, and linear zipWith/min/similar functions without compromising strongly normalization or soundness. The extension is so simple it could be added in Morte as it is as a few lines of code.

I could submit a pull request if Gabriel wishes. Should Self types be added?

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with issue #30 and the linked Self Types paper to understand the proposed extension to Morte's calculus of constructions. Confirm the intended semantics, soundness and normalization implications with the issue discussion; done means reaching a project decision and defining the implementation scope for enabling Scott encodings.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.