Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Я сейчас тривиальную вещь скажу

...но ведь всем (кто этим занимается), наверное, понятно, что определение системы типов в стиле двунаправленной типизации это индуктивно-индуктивно-рекурсивное определение, где совместно индуктивно определяются типы
– типов теории Ty
– канонических термов каждого типа El[t : Ty]
– выражений Expr, вместе с функцией synth-type : Expr -> Ty и
– рекурсивной зависимой функцией type driven редукции reduce : (e : Expr) -> Tn[synth-type e]?

Причём, если задаваемая алгебраическая теория имеет только операторы нулевого порядка, например это теория категорий-с-конечными произведениями, то тут есть раздилимые индуктивно-индуктивное определение Ty и El, и индуктивно-рекурсивное определение Expr и Reduce. А если в теории появляются операторы первого порядка, (кванторы и/или лямбды), то этот узел уже не рассечь, вся четвёрка задаётся взаимно индуктивно-индуктивно-рекурсивно.
Tags: #fp
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments