Църковните числа се преобразуват в int без езиков примитив

Възможно ли е да се преобразува църковно число в цяло число, без да се използва езиков примитив като add1?

Всички примери, на които съм попадал, използват примитив за dechurch към int

Пример:

 plus1 = lambda x: x + 1
 church2int = lambda n: n(plus1)(0)

Пример 2:

 (define (church-numeral->int cn)
    ((cn add1) 0))

Експериментирам с интерпретатор на micro lisp (използвайки само 10-те правила на Джон Маккарти) и бих искал да разбера дали това може да се направи без добавяне на примитивен елемент.


lisp scheme lambda-calculus
person Joe    schedule 03.04.2013    source източник
comment
Имам предвид примитиви в смисъла на stackoverflow.com/questions/3482389/. Не съм виждал как да конвертирам обратно в четливо представяне на църковно число, използвайки общите 7,10,x примитиви като atom, quote, eq, car, cdr, cons, cond, lambda, label, apply. Сега ще е необходим и изходен примитив, за да бъде полезен. Може ли да се направи нещо с ycombinator и изход?   -  person Joe    schedule 03.04.2013

Отговори (2)


arrow_upward
2
arrow_downward

Целочисленият числов тип не е част от списъка на Маккарти с елементарни примитивни процедури на Lisp - имате само функции на това ниво, не съществуват други типове данни. Ето защо целите числа ще трябва да бъдат представени като функции (например, използвайки числа на Чърч), ако трябва да се придържаме стриктно към такава минималистична дефиниция на Lisp. Така че отговорът е не. Не можете да конвертирате към тип данни, който все още не съществува.

Да предположим сега, че добавяме цели числа като атоми в езика (забележете, че добавянето на нов тип данни към езика надхвърля споменатите 7-10 примитивни процедури). За да опростим още повече, да предположим, че просто добавяме едно число, числото нула - тогава пак ще се нуждаем от операцията add1, за да изградим останалите цели числа, съгласно Аксиоми на Пеано, които изискват съществуването на операцията наследник, за да съществуват естествените числа. Отново, не можем да преобразуваме от числа на Чърч в цели числа без поне да имаме числото нула като атом и функцията add1.

person Óscar López    schedule 03.04.2013

arrow_upward
1
arrow_downward

№ int, както го описвате, е примитивен тип стойност, а не функция. Не можете изобщо да манипулирате такива ints без примитиви (без add1, как изобщо ще стигнете до 1 от 0?).

Със сигурност обаче можете да конвертирате между две различни Чърч-кодирания на естествени числа, без да използвате примитиви, стига вашият език да е пълен по Тюринг без тези примитиви.

person Paul Stansifer    schedule 03.04.2013