r4 - 31 May 2004 - 16:37:37 - Yuri KlimovYou are here: TWiki >  XSG Web > Positive

Позитивный XSG

Как Вы уже знаете из писем, появилась новая версия XSG - позитивный XSG. Основное отличие от "основного" XSG - это отсутствие отрицаний. От них временно решено отказаться с целью упрощения программирования.

Хотя нет отрицания, зато есть следующие:

  • Сравнение, основанное на MGU. Это одно из основных отличий XSG от других функциональных, логических и функционально-логических языков.
  • Cправедливость. Это требование можно переформулировать так: если есть путь вычислений, приводящий к результату, то и интерпретатор языка должен находить этот ответ. В языках без сравнения, основанного на MGU, таких как лябда-вычисления, Haskell, ленивость и справедливость одно и то же. Но в XSG это не так.
  • Ленивость. Хотя многие языки имеют ленивость, но у них нет сравнения, основанного на MGU, поэтому в них в каждый момент времени нужно считать только одну функцию. В XSG это не так, так что ленивость немного преображается. Пока для XSG нет отдельного интерпретатора (может быть и не будет...), его роль выполняет драйвинг с выдачей ответов из всех листовых вершин. Каждый путь по дереву от вершины до листка обладает ленивостью - считается только то, что необходимо. Но есть тупиковые пути... Так что драйвингу приходится считать и то, что не нужно для ответов, но нужно для того, чтобы доказать, что других ответов нет. И он считает справедливо в том смысле, что если есть порядок вычислений, доказывающий что так к результату дойти нельзя (встретится противоречие), то драйвинг это поймет за конечное время.
  • Недетерминированность. Если все предыдущие особенности языка были заложены в него изначально (точнее были заложены сравнение и "стандартная" ленивость, и в процессе программирование первого интерпретатора из них вытекли справедливость и "новая" ленивость), то эта особенность появилась из-за требования о корректности и замкнутости языка относительно суперкомпиляции. Оно означает, что при полностью заданных аргументах разные пути вычисления (или пути по дереву, построенному драйвингом) могут приводить к разным ответам. С одной стороны это недостаток, с другой - преимущество, ибо теперь можно оперировать с множествами, а не с последовательностями. Простой пример: numbers n = 0; numbers n = 1+(numbers (n-1)). Эта функция возвращает какое-то число от 0 до n. Каждое число, т.е. интерпретатор выдаст все числа от 0 до n.

-- Yuri Klimov - 31 May 2004


У меня три замечания

  • А зачем зря складывать?
numbers n = n
numbers n = numbers (n-1)
  • Я все таки против Haskell-ного синтаксиса в этом месте. Имеется же в виду совсем не то, что в Haskell-е, по-моему лучше так:
numbers n = 
  -> n  
  -> numbers (n-1)
  • Недетерминизм автоматически приводит к тому, что в языке поддержано Maybe. Раз интерпретатор осмысленно работает с функцией, у которой несколько значений, то он адекватен и тогда, когда значений нет вообще. В частности, в предыдущем примере (n-1) просто неопределено при n==0.
data Number = O | I Number
minus x y =
  x :=: I x', y :=: I y' -> minus x' y'
  y :=: O                -> x 
numbers n = 
  -> n
  -> numbers (minus n (I O))
Можно начинать суперкомпилировать - специализировать minus по (y == 1) smile

PS. Юра, а чего не запостил перестановки? Это ж произведение искусства! wink

-- Andrei Mishchenko - 31 May 2004


По просьбам трудящихся выставляю перестановки:

split xs     = []     xs
split (x:xs) = (x:ys) zs
                where ys zs = split xs

perm 0 = [0]
perm n = xs++(n:ys)
          where xs ys = split (perm (n-1))

Здесь пробел обозначает и применение функции ко всем аргументам, и арность, и коарность. Все числа в XSG выражаются в унарной системе, так что отрицательных чисел нет (что написал Андрей). Поэтому последняя строчка в perm работает только тогда, когда есть n-1. Также списки в XSG выражены через конструктор CONS, но для удобства пишу как в Haskell'е.

Вопрос с внешним синтаксисом остается открытым - так что смотрите, выбирайте...

-- Yuri Klimov - 31 May 2004

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r4 < r3 < r2 < r1 | More topic actions
 
Powered by TWiki

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback