Gabriella439 / Gabriella439/Haskell-Morte-Library

unexpected slowness (non-recursive)

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

Description

There are files with terms in this directory (to be root) in the commit https://github.com/groupoid/om/tree/ac585365a69d8dcd6c43a31a424486d5718c2522/priv/barbers/Hurkens/lambda (also available as a gist here https://gist.github.com/zraffer/dc90b5d076eda6156277 ), a few of which take a very long time to typecheck and normalize. Especially `ShadowTrans` and `Shadow-MkOk`. The terms do not use recursion and need just a few reductions to normalize. Moreover, usage of this terms in simple expressions (call `id` for example --- file `test/Shadow-MkOk` as well as othes files in that directory) take much more time, so typechecking seems to have exponential time complexity in such cases. Therefore long typechecking time for simple terms makes `morte` unusable for development.

Older versions (since 1.1) from hackage were tested producing the same time results.
However fully normalized versions of the terms (from `morte` output, at https://github.com/groupoid/om/tree/ac585365a69d8dcd6c43a31a424486d5718c2522/priv/barbers/Hurkens/output ) have got typechecked immediately (no slowness).

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.