r5 - 20 Sep 2004 - 09:48:00 - Andrei MishchenkoYou are here: TWiki >  XSG Web > XsgForum > WhatSyntaxIs

Ну и какой же синтаксис?

Итак, сейчас я расскажу некий внешний синтаксис, который мы с Юрой придумали в Голицино. Сразу скажу, что он поддерживает только конструкции позитивного варианта языка. Далее будут мысли о том, что, как мне кажется, нужно подправить во внутреннем синтаксисе для большей стройности. От читателя требуется искать логические нестыковки во всех этих построениях smile

Внешний синтаксис

fun_name := id
ctor_name := id
var_name := id
exp := empty | var_name | exp exp | ctor_name exp | fun_name exp | ( exp )
fun_def := fun_name branch_list
branch := action_list
action := -> exp | = exp
ctor_def := ctor_name arity

Наверное, надо объяснить, да?... wink Итак, программа -- это совокупность определений функций и конструкторов. Чтобы определить конструктор, достаточно указать его имя и арность. Наиболее интересной идеей является вид тела функции. В теле функции указывается некоторое количество ветвей (branch). Семантика этого заключается в недетерминизме, то есть порядок ветвей не играет никакой роли. Ветвь представляет собой список действий (action). Чтобы понять их семантику рассмотрим следующую модель вычислений. Представим себе, что во время вычисления функции меется некоторое место, называемое рабочей областью. В ней изначально находятся аргументы функции, в по завершению работы там должны остаться возвращаемые значения. Действия из списка совершаются по очереди слева направо. Действие -> exp заменяет содержимое рабочей области на exp, а действие = exp проверяет, что содержимое рабочей области совпадает с exp. Знающие Рефал уловят аналогию с конструкциями ,(=) и : этого языка, но принципиальное отличие от Рефала состоит в том, что новые переменные могут появляться где угодно, и после =, и после ->.

Строить выражения можно с помощью переменных, вызывая функции, применяя конструкторы, а также приставляя выражения друг к другу через пробел. В отличие от Рефала предполагается, что арность выражений будет контролироваться в статике. Как уже несколько раз упоминалось, по арности конструкторов и функций однозначно востанавливается скобочная структура выражения, поэтому скобки нужны лишь для удобочитаемости.

В случае когда первым действием является = exp (а как правило это так, иначе функция не будет зависеть от своих аргументов), то этот знак "=" можно опустить. Пожалуй, несколько примеров. Здесь "O" - нульместный конструктор (это 0, а заодно и пустой список), "I" - одноместный (он обозначает +1), а "C" - двуместный (для конструирования списков).

swap x y -> y x

add O     x -> x
    (I y) x -> I (add y x)

sub x     O     -> x
    (I x) (I y) -> sub x y 

sub' x y -> y = O -> x
     x y -> x = (I x') -> y = (I y') -> sub' x' y' 
    
mul O     x -> O
    (I y) x -> add (mul y x) x

fact O       -> I O
     x = I y -> mul x (fact y)

append O        ys -> ys
       (C x xs) ys -> C x (append xs ys)

length O       -> O
       (C x xs)-> I (length xs)

take O     xs       -> O
     (I n) (C x xs) -> C x (take n xs)

take' n xs -> n = O -> O
      n xs -> n = I n' -> xs = C x xs' -> C x (take' n' xs')

split xs     ->                     O        xs
      C x xs -> ys zs = split xs -> (C x ys) zs    

split' xs     -> O xs
       C x xs -> C x split' xs

Комментарии. Функции sub/sub', take/take', split/split' отличаются исключительно синтаксически. Это разные способы записать одно и то же. Вычисление sub x y в случае x < y, а также take n xs при length xs < n не приводит к какой-нибудь ошибке, просто эти функции в этих случаях неопределены, так же как, если, например, применить add не к числам, а к спискам. Функция split существенно недетерминирована, результатом ее работы является какое-то (точнее каждое) разбиение списка на две части. В функции split' имеется выражение C x split' xs, которое не совсем подходит под грамматику exp, в нем никак нельзя расставить скобки. Но хотелось бы, чтобы так можно было писать, потому что у этой записи имеется вполне разумное и естественное прочтение, а именно, C x split' xs ~ ys zs = split' xs -> C x ys zs.

Обсудим теперь как такие программы транслируются во внутреннее представление и каково оно.

  • Компиляция функции: генерируются уникальные имена для аргументов; компилируются ветви финкции.
  • Компиляция ветви: формально исполняются все действия ветви, формируется система уравнений и выражение-результат; далее каждый вызов каждой функции, встречающийся в уравнениях или результате помечается уникальным идентификатором (l-переменная); система уравнений разделяется на две части
    • определения l-переменных (в каждом определении в точности один вызов функции)
    • уравнения, не содержащие вызовов; в выражении-результате вызовы функций также исчезают.

То есть в отличие от внутреннего представления, имеющегося на данный момент, кажется естественным перенести систему клешей за let-терм, то есть позволить употреблять в клешах l-переменные, введенные в let-терме.

Особо хочется обсудить следующий вопрос. На первый взгляд кажется естественным потребовать, чтобы новые переменные выражались только через уже определенные. Собственно, по этой причине в текущей реализации система клешей стоит перед let-термом. Но с другой стороны, имеющийся драйвинг совершенно невосприимчив к тому, к каком месте возникают новые переменные (x-переменные). Почему бы не позволить писать

any -> x //функция может вернуть все что угодно.

split'' 
  append ys zs -> ys zs //третий вариант функции split

h 
  x = f y = g z -> x y z //решение другой странной ura-подобной задачи

И последние, что я хочу рассказать, это то, как писать пользовательские предикаты. Зачастую в программе нужны разрешимые предикаты, с которыми нужно уметь выполнять любые логические действия

not True -> False
    False -> True

and True True -> True
    False _   -> False
    _ False   -> False 

or  True _      -> True
    _ True      -> True
    False False -> False

if True  x y -> x
   False x y -> y

isOdd O   -> False
      I O -> True
      I I n -> isOdd n

isEven n -> not (isOdd n)

Но зачастую в операции not нет необходимости, и тогда достаточно программировать перечислимые предикаты. То есть функции, которые просто неопределены если предикат неверен. Например,

isOdd I O -> True
      I I n -> isOdd n

isEven O -> True
       I n -> isOdd n

div2 O -> O
     I I n -> I (div2 n)

div2WhenPossible n -> isEven n = True -> div 2 n
                 n -> isOdd n = True  -> n

В этом случае символ True несколько теряет свой смысл, он может быть заменен на любой другой. Предлагается ввести понятие нулькоарной функции, то есть функции, имеющей коарность равную нулю. На уровне внутреннего представления компилятор мог бы завести специальную константу, скажем, defined, и вернуть ее во всех случаях, когда функця завершает работу, а при каждом вызове добавлять условие = defined. А на уровне внешнего синтаксиса это выглядело бы так

isOdd I O -> 
      I I n -> isOdd n

isEven O -> 
       I n -> isOdd n

div2 O -> O
     I I n -> I (div2 n)

div2WhenPossible n -> isEven n -> div 2 n
                 n -> isOdd n -> n

То есть, результат работы нулькоарной функции можно положить в рабочую область, только если он определен.

Всем спасибо за внимание!

-- Andrei Mishchenko - 17 Sep 2004

С одной стороны нулевая коарность у вас в чём-то похожа на Си-шный void, с другой стороны вы получаете класические хорновские дизъюнкты (читай прологовские правила), да ещё и учитывая вашу позитивность smile Если будете продолжать идти этим путём, то введёте в XSG отрицание-как-отказ (если уже не ввели) и... пошли-поехали вопросы с интерпретациями результатов функций, использующих эту конструкцию несколько раз вложенно. К сожалению, все наработки, типа такого defined (у себя я его называл success), оказываютя совершенно непригодными для модели открытого мира (где конструктивно можно выразить отрицание чего-либо). Но там приходится ковыряться вообще с четырёхзначной логикой (типа как у Белнапа), и вы судя по всему, уже отведали всех её прелестей, раз решили пока не трогать. Вобстчем - зер гут. Следим за успехами smile

-- AnatolyARessin - 20 Sep 2004

Сложно говорить про С-ный void в контексте ленивого языка. Если функция ничего не возвращает (возвращает void) то она не будет вызвана. Скорее эти предикаты больше похожи на Haskell-ное (), то есть тип с единственным значением. Похожий стиль написания предикатов популярен в Рефале, они там называются фильтрами. Пишется функция, которая возвращает свой же агрумент, если он "подходит", а если он "не подходит", то она "ломается". В Рефале в этом случае просходит откат на другой вариант означивания открытых переменных.

XSG, как и любой язык в котором хоть как-то затрагивается понятие унификации, разумеется имеет некоторые аналогии с Прологом. Лично для меня, основное отличие от Пролога в справедливости. Я посмотрел (не очень внимательно smile про Андору, мне показалось, что это не про то. Будет время, постараюсь написать программу, которая "виснет" в Андоре, но работает в XSG.

До сих пор в планах по добавлению отрицания предполагалось, что оно будет только конструктивным... Правда, есть еще одна интересная идея: добавить возможность запускать интерпретатор из самого языка. Пока, если функция f имеет два значения, то они как пара из самого языка недостижимы. Можно что-то сделать с каждым из них (скажем, каждое умножить на 2), но нельзя ничего сделать с ними вместе (например, сложить). Если же в языке будет не только возможность вызвать функцию (и получить какое-то ее значение), а также вызвать интерпретацию функции (и получить все ее значения, в виде списка или еще как-то) то их потом можно будет сложить, взять максимум и т.п. Одновременно, это сделает выразимым неконструктивный вариант отрицания (можно будет проверить, что у функции вообще нет значений).

Вообще усложнять язык надо аккуратно. Нашей целью все-таки является не создание языка на котором удобно программировать, а создание модельного языка и метавычисления над ним. Все усложнения, который были введены в язык, делались ради его замкнутости относительно суперкомпиляции.

-- Andrei Mishchenko - 20 Sep 2004

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r5 < 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