Эта разложение в паттерне лямбда-исчисления

12

У Клопа, ван Оострома и де Врийера есть статья о лямбда-исчислении с узорами.

http://www.sciencedirect.com/science/article/pii/S0304397508000571

В некотором смысле шаблон - это дерево переменных - хотя я просто думаю о нем как о вложенном кортеже переменных, например, ((x, y), z), (t, s)).

В статье они показали, что если шаблоны являются линейными в том смысле, что ни одна переменная в шаблоне не повторяется, то правило

(\p . m) n = m [n/p]

где p - переменная структура, а n - набор терминов с точно такой же формой, что и p, является слитым.

Мне любопытно, есть ли в литературе подобные разработки для лямбда-исчисления с шаблонами и дополнительным правилом eta (расширение, уменьшение или просто равенство).

В частности, под eta я имею в виду 

m = \lambda p . m p

Точнее, мне любопытно, какими свойствами будет обладать такое лямбда-исчисление. Например, это ли слив?

Это заставляет классифицирующую категорию быть закрытой, потому что это заставляет свойство, которое

m p = n p implies m = n

Используя \ xi-правило между ними. Но, возможно, что-то могло пойти не так?

type-theory lambda-calculus typed-lambda-calculus extensionality Джонатан Галлахер
источник
Можете ли вы написать поставить, что это правило вы имеете в виду? Если это не очень странно, вы должны быть в состоянии закодировать его с помощью сумм и создать аргумент моделирования.
Макс Новый
2
@MaxNew: похоже, он спрашивает о нетипизированном исчислении. Все, что касается шаблонов, прекрасно работает с типами (о-о, так скромно предлагаю мой собственный Фокус на сопоставление с образцом ), но нетипизированное лямбда-исчисление достаточно отличается от типизированного LC (особенно в отношении eta), на которое я не смею отвечать, не выполняя доказательства ,
Нил Кришнасвами
@MaxNew: Что влечет за собой кодирование суммами?
Джонатан Галлахер
@NeelKrishnaswami: Я на самом деле интересуюсь обоими. Я думаю, что я нервничаю из-за наличия переменных типа продукта вместе с правилом eta. Я думаю, что это сделано, например, dicosmo.org/Articles/JFP96.pdf . Но если я ошибаюсь, поправьте меня. Тогда у вас есть равенства как \ lambda x .mx = m = \ lambda (p, q). m (p, q), например. Спасибо за ссылку на вашу статью!
Джонатан Галлахер

Ответы:

7

Это не полный ответ; это комментарий, который стал слишком большим.

Если вы расширили типизированное лямбда-исчисление продуктами с проективными элиминаторами (то есть элиминаторами продуктов fst(e)и т. Д. snd(e)), В принципе никаких проблем не возникнет. Причина, по которой это потребовалось так много времени, состоит в том, что оказывается, что более естественно делать этапы расширения, а не сокращения . См. Барри Джея « Добродетели расширения Эта» .

Если вы хотите, чтобы в продуктах использовался шаблонный шаблон 

let (a,b) = e in t

Тогда дело обстоит сложнее. Основная сложность сопоставления с образцом - это коммутирующие преобразования . То есть эти исчисления имеют уравнение

C[let (a,b) = e in t] === let (a,b) = e in C[t]

и выяснить (а) какой контекст C[-]использовать и (б) как ориентировать это уравнение становится сложно. ИМО, современное состояние подходов в стиле переписывания - это перезапись экстремума Сэма Линдли с суммами и решающая эквивалентность Габриэля Шерера с суммами и пустой тип , оба из которых рассматривают типизированное лямбда-исчисление как с продуктами, так и с суммами.

Нил Кришнасвами
источник