Йота и Джот

В формальном языке теории и информатики , Йота и Jot (от грека йота ι, Hebrew yodh י, самые маленькие буквы в этих двух алфавитов) языки, крайне минималистичные формальные системы , разработанные , чтобы быть еще проще , чем в других популярных альтернатив, таких как лямбда - исчисление и SKI комбинатор исчисление . Таким образом, их также можно считать минималистскими языками компьютерного программирования или тьюринговыми тарпитами , эзотерическими языками программирования, призванными быть как можно меньшими , но все жеПолный по Тьюрингу . Обе системы используют только два символа и включают только две операции. Оба были созданы профессором лингвистики Крисом Баркером в 2001 году. Zot (2002) является преемником Iota, который поддерживает ввод и вывод. ^[1]

Универсальная йота [ править ]

Универсальный комбинатор йоты ι Криса Баркера имеет очень простую структуру λf.fSK, определенную здесь с использованием денотационной семантики в терминах лямбда-исчисления ,

${\ Displaystyle \ iota: = \ лямбда f. ((fS) K)}$

( 1 )

Отсюда можно восстановить обычные выражения SKI , таким образом:

${\ Displaystyle I \, = \, (\ йота \ йота), \; К \, = \, (\ йота (\ йота (\ йота \ йота))), \; S \, = \, (\ йота (\ йота (\ йота (\ йота \ йота))))}$

( 2 )

Из-за своего минимализма он повлиял на исследования постоянной Чайтина . ^[2]

Йота [ править ]

Йота является LL (1) языка, префиксы упорядочивают дерева вышеупомянутого Юниверсала йота ι комбинатор Лифс, consed по функции приложения е ,

iota =  "1"  |  "0"  йота йота

так что например 0011011 обозначает , тогда как${\ Displaystyle ((\ йота \ йота) (\ йота \ йота))}$0101011 обозначает .${\ Displaystyle (\ йота (\ йота (\ йота \ йота)))}$

Jot [ править ]

Jot - это обычный язык, состоящий из всех последовательностей 0 и 1,

jot =  ""  |  jot "0"  |  jot "1"

Семантика задается переводом в выражения SKI. Пустая строка обозначает , обозначает , где перевод , и обозначает .${\ displaystyle I}$${\ displaystyle w0}$${\ Displaystyle (([ш] S) К)}$${\ Displaystyle [ш]}$${\ displaystyle w}$${\ displaystyle w1}$${\ Displaystyle (S (К [ш]))}$

Дело в том, что перевод удовлетворяет произвольным условиям SKI и . Например,${\ displaystyle w1}$${\displaystyle (([w1]A)B)=([w](AB))}$${\displaystyle A}$${\displaystyle B}$

$${\displaystyle [w11100]=(([w1110]S)K)=(((([w111]S)K)S)K)=((([w11](SK))S)K)=(([w1]((SK)S))K)=([w](((SK)S)K))=([w]K)}$$

${\displaystyle w}$

$${\displaystyle [w11111000]=(((((([w11111]S)K)S)K)S)K)=([w](((((SK)S)K)S)K))=([w]S)}$$

Jot связан с Iota тем, что и с помощью одних и тех же идентификаторов на условиях SKI для получения базовых комбинаторов и .${\displaystyle [w0]=(\iota [w])}$${\displaystyle K}$${\displaystyle S}$

Zot [ править ]

Языки Zot и Positive Zot управляют вычислениями Iota , от входов до выходов с использованием стиля передачи продолжения , в синтаксисе, напоминающем Jot ,

zot =  горшок |  "" pot =  iot |  pot iot iot =  "0"  |  «1»

где 1 производит продолжение , а${\displaystyle \lambda cL.L(\lambda lR.R(\lambda r.c(lr)))}$0 производит продолжение , а wi потребляет последнюю входную цифру i , продолжая до конца w .${\displaystyle \lambda c.c\iota }$

См. Также [ править ]

• Лямбда-исчисление
• Комбинаторная логика
• Бинарная комбинаторная логика
• Расчет комбинатора SKI

Ссылки [ править ]

Внешние ссылки [ править ]

• Официальный веб-сайт
• Баркер, Крис. «Йота и Джот: самые простые языки?» . Веб-кольцо эзотерических языков программирования . Архивировано из оригинального 7 -го мая 2016 года . Проверено 13 августа 2004 года .
• https://esolangs.org/wiki/Iota
• https://esolangs.org/wiki/Jot
• https://esolangs.org/wiki/Zot