Комментарии 28
Мне непонятно, чем отличается подход Маркова от Черча, если представленный в примере алгоритм по сути и есть лямбра выражение: (λC. (λB. (λA. ABC) B) CC) ø
Различие в идее, лежащей в основе обсуждаемых подходов. Лямбда-исчисление построено вокруг функции, как некоторой сущности которая преобразует A в B (можно сказать, что соответствии). Нормальные алгоритмы на идее переписывания и подстановок. Даже в самой семантике алгоритмов есть разница: Чёрч говорит о вычислениях, а НАМ — это не вычисления, а лишь поиск и замена. При это да, и лямбда-исчисление и НАМ равномощны, и одно можно представить в виде другого.
Лямбда-исчисление построено вокруг функции, как некоторой сущности которая преобразует A в B (можно сказать, что соответствии)
Нет, нельзя так сказать. Лямбда ф-я тем и отличается от обычной функции, что это не отображение и не соответствие, а замена определенного символа в строке* на другой символ или последовательность символов, в том числе и на такую последовательность символов, которая может содержать в себе некую произвольную лямбда функцию. И как я вижу, подстановки Маркова это лямбда функция и есть, только записаны они в менее компактной форме. Либо я реально чего-то не понимаю.
*Строка это упорядоченная последовательность символов, т.е. связанный список.
Могу ошибаться, но подход Чёрча – мы работаем не со списком, а с единственной функцией, у неё единственный аргумент (ну, на выходе снова может быть функция, которая сожрёт следующий аргумент). Нет поиска матча в "строке", всегда идём с начала (или рекурсивно вычисляя аргумент для жадного вычисления, или хватая его, как есть).
Т.е. Чёрч проще.
Но понятно, что изоморфизм есть (как и с машиной Тьюринга, только, кажется, ещё прозрачнее).
Всегда найдется кто-то, к кому хорошая мысль пришла раньше((
https://github.com/mxgmn/MarkovJunior
В статье об этом есть упоминание.
Я на самом деле, когда узнал о существовании MJ и Thue, был очень обрадован, подумал: замечательно! я не один в своих исканиях, кто-то уже начал протоптывать дорожку.
Однако, одного взгляда на эти ЯП хватило, чтобы понять: моя работа отличается от перечисленных. Тот же MJ, насколько я понял, не язык общего назначения.
А зачем марковским машинам быть общего назначения?
А почему бы и нет? Целью моей работы как раз и было выяснить: что получится, если НАМ приспособить для общего назначения. Может быть я изначально занимаюсь вещами бесполезными, но мне просто было интересно посмотреть что будет и поделиться этим с общественностью.
Ну если начать перечислять то, что включается в общее назначение, то выйдет, что всякого рода подстановки имеют довольно ограниченное применение и обычно встраиваются в виде какого-нибудь DSL внутри конкретных языков. Из прямых использований только вычисляющие шаблонизаторы и макроподстановки. Когда появляется состояние и соотвественно некоторые машины состояний следить за такими подстановками становится сложнее и соответственно с большей вероятностью в проде использоваться с такой целью не будет. Поэтому пытаться приладить НАМ к общему назначению это как раз та самая история с совой и глобусом - провернуть конечно можно, возможно даже это весело, но в требования всё равно не попадает.
По фану пилить что-то такое естественно это никак не мешает.
А чем оно от полуизотерического Prolog'а отличается?
Мне этот подход к созданию языков программирования очень сильно напомнил TeX.
Тогда уж и m4 (макропроцессор) - тоже НАМ?
Помнится читал статью, что Рефал базируется на арифметике, те согласно черчу противоречив и сл не годится в языки программирования Деталей не помню
| Задача. Воде, массой 5 кг и теплоёмкостью 4200 Дж/кг×°C, сообщили теплоту. В результате её |температура изменилась на 20°C. Чему равно изменение температуры воды? Теплообменом с |сосудом и окружающей средой пренебречь.
^^ Ответ очевиден: 20°C, это задача-шутка ?
Внезано, в качестве имплементации подходит Noq (почти что live разработка тут). Собсна язык и занимается по факту подстановками по правилам, правда написан он был маленько с другого конца - идея была взять у всяких Coq/Lean/прочих решателей теорем систему подстановки выражений. Ровно то же, что описал автор.
Правда не очень понятно чем вводные НАМ машины отличаются от той же общей машины тьюринга. Разве что компактностью.
Первое впечатление при взгляде на код: «ого, автор выдумал свой lisp! Респект!»
</irony>
Я не понял, может кто пояснить?
atom simple-while rule
[ simple-while 1 .seq ]
[ simple-while
cond [ some data ]
print "Hello, world" ]
Мы научились создавать конструкции ветвления через "if 1", "if 2", т.е. здесь мы аналогично с помощью simple-while 1 вызываем цикл (скорее рекурсию) конструкции. Вместо 1 у нас cond. Ok, но зачем мы в конце самого выражения для вычисления вызываем print? Зачем действие производимое внутри цикла необходимо после его окончания? Или конструкция странная или я вообще не понял синтаксиса
[ simple-while
cond
print "Hello, world!" ]
Нормальные алгоритмы Маркова как основание языка программирования