Re[9]: Преобразование Java -> Tcl с помощью TXL
От: Victor Repetsky Украина  
Дата: 22.12.08 08:59
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>Промежуточное представление может быть сохранено на диск, так как на этапе компиляции диалект целевого языка может быть неизвестен.

А в каком сохранялось промежуточное AST? (У меня использовался XML с той же целью. Кроме того для тестов разных частей преобразования использовал пары XML-вход, XML-выход.)

AVK>3) Генератор. Формирует из промежуточного кода код на целевом языке. При этом синтез конструкций целевого языка происходит именно на этом этапе. Отдельного претти принтера как такового просто нет, так как особая нужда в нем просто отсутствует.

AVK>Соответственно, по объему работ для каждой части и получается 20-30-50.
Ясно. А какой язык и/или инструменты использовались?
SCJP, SCEA
Re[10]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 22.12.08 11:21
Оценка:
Здравствуйте, Victor Repetsky, Вы писали:

VR>А в каком сохранялось промежуточное AST?


Просто сериализуется в бинарник стандартным BinaryFormatter.

AVK>>Соответственно, по объему работ для каждой части и получается 20-30-50.

VR>Ясно. А какой язык и/или инструменты использовались?

Antlr для парсера, остальное C#.
... << RSDN@Home 1.2.0 alpha 4 rev. 1132 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[4]: Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 22.12.08 11:48
Оценка:
Здравствуйте, Victor Repetsky, Вы писали:


VR>Не совсем понятно, по виду этого правила кажется что мы оперируем на уровне текста а не AST?

replace [catch_statement]

Задает тип вершины в дереве.
'catch '( _ [repeat modifier] _ [type_specifier] _ [variable_name] ') '{ '}

Определяет шаблон для вершины дерева, представляющего выражение catch, в котором block пустой {}.
Затем данное правило применяется к вершине, группе вершин, ветви дерева и если находится вершина, удовлетворяющая шаблону, то срабатывает правило.

Кстати, в TXL можно вывести результаты парсинга в xml, если запустить с флагом -xml. Правда я не знаю можно ли это где-то потом использовать как входные данные.
Re[3]: Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 22.12.08 12:26
Оценка:
Уточнение. TXL работает с parse tree.
Re[6]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 23.12.08 11:47
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Грамматика расширений, которую я дописал, уже превосходит в размерах оригинальную грамматику луа. К 240 строкам оригинальной грамматики я дописал 350 строк расширений. Богатый паттерн-матчинг, функции задаваемые паттерн матчингом, списки в стиле ML: x::y::[], инфиксные и префиксные операторы, '$' оператор как в Haskell, короткая запись лямбд, имена бинарных функций как инфиксные операторы и еще что-то по мелочи (например опциональная совместимость вывода с Lua 5.0.x).


Z>Я постоянно дописываю всякую фигню и переписываю старую. Просветления все нет


Потому, что ты дописываешь синтаксис.
Вот есть у тебя язык, и в нём несколько типов для Expression.
Как их обрабатывает компилятор? Если через pattern matching, то надо в каждом из них прописывать все варианты Expression.
Ты добавил новый, скажем, lazy list.
Распарсить его — не проблема.
Проблема — что он может возникнуть в любом месте, где может быть expression, и по всему коду работающему с expression тебе надо повставлять case для этого нового LazyListExpression.
Если ты только меняешь парсер (добавляешь сахар), если у тебя интерпретатор, если динамическая типизация — этой проблемы не возникает. Она уходит в runtime.
Но я о компиляторе, а не интерпретаторе.
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[7]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 23.12.08 12:22
Оценка:
Здравствуйте, mkizub, Вы писали:

M>Здравствуйте, z00n, Вы писали:


Z>>Грамматика расширений, которую я дописал, уже превосходит в размерах оригинальную грамматику луа. К 240 строкам оригинальной грамматики я дописал 350 строк расширений. Богатый паттерн-матчинг, функции задаваемые паттерн матчингом, списки в стиле ML: x::y::[], инфиксные и префиксные операторы, '$' оператор как в Haskell, короткая запись лямбд, имена бинарных функций как инфиксные операторы и еще что-то по мелочи (например опциональная совместимость вывода с Lua 5.0.x).


Z>>Я постоянно дописываю всякую фигню и переписываю старую. Просветления все нет


M>Потому, что ты дописываешь синтаксис.

Я не синтаксис дописываю. Паттерн матчинг компилятор — это весьма нетривильная вещь.
См ML pattern match compilation by Peter Sestoft
Вот реализация того же самого алгоритма в компиляторе Nemerle:
http://nemerle.org/svn/nemerle/trunk/ncc/typing/DecisionTreeBuilder.n
У меня все еще сложнее из-за динамической типизации.
M>Вот есть у тебя язык, и в нём несколько типов для Expression.
M>Как их обрабатывает компилятор? Если через pattern matching, то надо в каждом из них прописывать все варианты Expression.
Правильно. Знаете сколько таких паттерн матчингов в компиляторе? Ровно 1 Там вызываются тысячи строк кода, чтобы преобразовать одно дерево в другое, но сам паттерн матчер 1, и занимает 20 строк. Все остальные прогоны(типа алфа-ренейминга и кой каких оптимизаций) я делаю по дереву оригинального языка, который не меняется. Компилятор паттерн матчинга вообще работает со своим представлением дерева(даже не одним) и сразу выдает дерево оригинального языка. Все остальные расширения знать о нем не знают, просто вызывают по необходимости.

// Hyper Expressions:
  implicit def Compile(o:ExprHyper):Expr = o match {
    case ShortLambda(formals_list, body) =>  {
      def loop(formals:Formals):Lambda = formals match {
        case Nil             => Lambda(Nil, false, body)
        case (ids,dots)::Nil => Lambda(ids, dots, body)
        case (ids,dots)::xs  =>
          Lambda(ids, dots, Block(Nil,Some(Return(loop(xs)::Nil))))
      }
      loop(formals_list)
    }
    case Infix(lhs, id, rhs) => Call(id, lhs::rhs::Nil)
    case Dollar(rator,rand)  => Call(rator,rand::Nil)
    case Prefix(id,rhs)      => Call(id,rhs::Nil)
    case ConsList(exps)      => {
      val arr = Table(for(exp <- exps)yield(RecArray(exp)))
      Call(Id(zoon.lua.Const.K_array2list),arr::Nil)
    }
    case LambdaPM(clauses,dots,src) => {
      val(arity,root_obj,block) = PMCompile.make(None,dots,clauses,src)
      Lambda(root_obj,dots,block)
    }
  }
Re[8]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 23.12.08 13:14
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Правильно. Знаете сколько таких паттерн матчингов в компиляторе? Ровно 1 Там вызываются тысячи строк кода, чтобы преобразовать одно дерево в другое, но сам паттерн матчер 1, и занимает 20 строк. Все остальные прогоны(типа алфа-ренейминга и кой каких оптимизаций) я делаю по дереву оригинального языка, который не меняется. Компилятор паттерн матчинга вообще работает со своим представлением дерева(даже не одним) и сразу выдает дерево оригинального языка. Все остальные расширения знать о нем не знают, просто вызывают по необходимости.


То есть ты теряешь высокоуровневую информацию компилируя непосредственно в дерево оригинального языка.
Наверное, для lua это не заметно вообще.
А представь себе, что ты сделал lazy list для Java. И написал

for (int i : [0..10]) {}


которое твоим способом компилируется в

LazyList lst = new LazyList(0,10);
while (lst.hasMore()) {
  int i = ((Integer)lst.next()).intValue();
  {}
}


вместо

for (int i=0; i <= 10; i++) {}


Угадай, куда пошлют твоё расширение разработчики, которые на ровном месте получат уменьшение производительности при такой компиляции?
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[9]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 23.12.08 14:33
Оценка:
Здравствуйте, mkizub, Вы писали:

M>Здравствуйте, z00n, Вы писали:


M>То есть ты теряешь высокоуровневую информацию компилируя непосредственно в дерево оригинального языка.

M>Наверное, для lua это не заметно вообще.
Это, извините, ерунда. Я компилирую в дерево, не в парсере, а после того, как использовал всю интересную информацию.

M>А представь себе, что ты сделал lazy list для Java. И написал


M>
M>for (int i : [0..10]) {}
M>


M>которое твоим способом компилируется в ...

Это опять ерунда. Если я могу cкомпилировать это в цикл — компилирую в цикл — в чем проблема?

val ii = fresh("u$")
val for_ = VanillaFor(Id(ii),Int(0),BinOp(Le,Id(ii),Num(10),PostOp(Id(ii),PlusPlus)))
val block = Block(for_::body::Nil)
      ||| pretty printing
      VVV
for(int u$0123 = 0, u$0123 <= 10, u$0123++) {
    /* body */
}


Если не знаю, могу или нет — жду пока узнаю и компилирую.
Или вы серьезно пытаетесь оптимизировать программу как есть ходя по своему "обогащенному" дереву, без SSA etc?

Я вам могу показать что получается, например с паттерн матчингом(оч.простой пример). Поинт в том, что "обогащенного" AST здесь нет — оно выполняет тривиальную задачу предоставления необходимых аргументов компилятору PM.
-- Hyperlua
fun foo
  | 1,2,_ -> 111
  | 2,_,_ -> 222
end


-- Parse Tree
(block
  [(FunPM
     (FunctionName
       (Id "foo") RNone)
     (PatMatch
       [(PatClause
          [(GuardedPattern
             [(Number "1"),(Number "2"),(WILDpat)] RNone)]
          (ExpressionList
            [(Number "111")]))
       ,(PatClause
          [(GuardedPattern
             [(Number "2"),(WILDpat),(WILDpat)] RNone)]
          (ExpressionList
            [(Number "222")]))]))]


-- Pattern Tree
! arity: 3
! (ConPat(LTop(3)[ConPat(LNum("1")[])
              ,ConPat(LNum("2")[])
              ,WildPat]),(Vars: []
,Guard: None
,RHS: return 111))
! (ConPat(LTop(3)[ConPat(LNum("2")[]),WildPat,WildPat]),(Vars: []
,Guard: None
,RHS: return 222))


-- Decision Tree
IfEq (Obj[1] == LNum("1"))
    IfEq (Obj[2] == LNum("2"))
        Success((Vars: []
                ,Guard: None
                ,RHS: return 111))
        Failure
    IfEq (Obj[1] == LNum("2"))
        Success((Vars: []
                ,Guard: None
                ,RHS: return 222))
        Failure


И собственно Lua(поскольку AST изоморфно коду — отдельного претти-принтера нет)
-- lua
function foo(_u0,_u1,_u2)
  if _u0 == 1 then
    if _u1 == 2 then return 111
    else error'pattern-match error';
    end;
  else
    if _u0 == 2 then return 222
    else error'pattern-match error';
    end;
  end;
end;
-- + warning
foo.hlua:1:1: warning: this pattern-matching is not exhaustive:
fun foo
  | 1,2,_ -> 111
  | 2,_,_ -> 222
end
Re[10]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 23.12.08 15:01
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Это опять ерунда. Если я могу cкомпилировать это в цикл — компилирую в цикл — в чем проблема?

Z>Если не знаю, могу или нет — жду пока узнаю и компилирую.

Проблема в том, что ты уже потерял эту информацию, когда скомпилировал в стандартное дерево.
Или ты компилируешь сразу и теряешь возможность оптимизации, или ты компилируешь когда знаешь всю необходимую информацию, и тогда ты работаешь с нестандартным ("обогащённым" как ты его назвал) деревом. И тогда тебе надо эту компиляцию размазывать по коду и компилировать в несколько проходов, потому как в один момент времены ты это ещё не знаешь, а потом уже знаешь.

Z>Или вы серьезно пытаетесь оптимизировать программу как есть ходя по своему "обогащенному" дереву, без SSA etc?


SSA это только один из проходов оптимизатора. И ему дополнительные узлы в дереве не мешают, если содержат необходимую информацию о side-effect-ах.
И если ты думаешь, что SSA это такое волшебное место, куда скормил неоптимизированную программу, и на выходе получил оптимизацию по самые гланды — ты ошибаешься.
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[11]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 24.12.08 03:04
Оценка:
Здравствуйте, mkizub, Вы писали:

Вы вообще не читаете того, что я пишу — хватит уже в третий раз банальности повторять.
M>Проблема в том, что ты уже потерял эту информацию, когда скомпилировал в стандартное дерево.
Скомпилировал в стандартное дерево === закончил работу. Вам не нужна никакая информация после этого.
M>Или ты компилируешь сразу и теряешь возможность оптимизации, или ты компилируешь когда знаешь всю необходимую информацию, и тогда ты работаешь с нестандартным ("обогащённым" как ты его назвал) деревом. И тогда тебе надо эту компиляцию размазывать по коду и компилировать в несколько проходов, потому как в один момент времены ты это ещё не знаешь, а потом уже знаешь.
Я, знаете ли, в предудущем посте показал вам 4 прохода по 4 разным деревьям. Дальше что?


Z>>Или вы серьезно пытаетесь оптимизировать программу как есть ходя по своему "обогащенному" дереву, без SSA etc?

M>SSA это только один из проходов оптимизатора. И ему дополнительные узлы в дереве не мешают, если содержат необходимую информацию о side-effect-ах.
M>И если ты думаешь, что SSA это такое волшебное место, куда скормил неоптимизированную программу, и на выходе получил оптимизацию по самые гланды — ты ошибаешься.

Я знаю что такое SSA. Если у вас с этим проблемы — Мучника почитайте.
Re[12]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 24.12.08 09:22
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Вы вообще не читаете того, что я пишу — хватит уже в третий раз банальности повторять.


Читаем вместе —

засосал parsing-tree в Scala, преобразовал там в типизированное AST, по которому ходил паттерн-матчингом. Преимущества терм-рерайтинга (как в TXL или Stratego) перед паттерн-матчингом мне до сих пор непонятны.


Знаете сколько таких паттерн матчингов в компиляторе? Ровно 1 Там вызываются тысячи строк кода, чтобы преобразовать одно дерево в другое, но сам паттерн матчер 1, и занимает 20 строк. Все остальные прогоны(типа алфа-ренейминга и кой каких оптимизаций) я делаю по дереву оригинального языка, который не меняется.


Эти цитаты между собой не согласуются.
Это не использование pattern-matching. Вот в Nemerle его используют, а ты — нет. 1 паттерн-мэтчинг на 20 строк легко переписывается на if-else тоже на несколько десятков строк, и вообще никаких преимуществ перед ним не имеет, так как главное их отличие — читабельность. Сотня pattern-matching-ов по всему коду — не переписывается так легко.
Возможно из-за этого начались проблемы с непониманием с самого начала.

Далее

Компилятор паттерн матчинга вообще работает со своим представлением дерева(даже не одним) и сразу выдает дерево оригинального языка


Я компилирую в дерево, не в парсере, а после того, как использовал всю интересную информацию.


Эти слова опять между собой не согласуются.
Есть два варианта:
а) преобразовать твоё расширенное AST в стандартное AST, и с ним уже работать (верифицировать, резолвить, оптимизировать и пр.), при этом ты можешь свободно использовать pattern-matching в работе со стандартным деревом (так как набор его элементов фиксирован).
б) ты работаешь с расширенным AST (верифицируешь, резолвишь, оптимизируешь и пр.), постепенно переводя его в стандартное AST (которое опять нужно верифицировать, оптимизировать и т.п.), и при этом тебе тяжело использовать pattern-matching, так как в любом месте дерева могут обнаружится неизвестные узлы (принадлежащие некоему расширению, о котором остальная часть программы не знает).
Первая твоя цитата говорит о том, что ты используешь вариант (а), а во второй ты утверждаешь, что используешь вариант (б).

Хотя теперь мне уже кажется, что ты вообще pattern-matching не используешь, и потому просветления насчёт проблем его использования до сих пор не получил
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[13]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 24.12.08 15:30
Оценка:
Здравствуйте, mkizub, Вы писали:

M>Читаем вместе -


M>

засосал parsing-tree в Scala, преобразовал там в типизированное AST, по которому ходил паттерн-матчингом. Преимущества терм-рерайтинга (как в TXL или Stratego) перед паттерн-матчингом мне до сих пор непонятны.


Дальше я для ясности вставлю ваш вопрос:
M>Вот есть у тебя язык, и в нём несколько типов для Expression.
M>Как их обрабатывает компилятор? Если через pattern matching, то надо в каждом из них прописывать все варианты Expression.

M>

Знаете сколько таких паттерн матчингов в компиляторе? Ровно 1 Там вызываются тысячи строк кода, чтобы преобразовать одно дерево в другое, но сам паттерн матчер 1, и занимает 20 строк. Все остальные прогоны(типа алфа-ренейминга и кой каких оптимизаций) я делаю по дереву оригинального языка, который не меняется.


Нужно читать "таких" — как "таких в которых несколько [новых] типов для Expression"

M>Эти цитаты между собой не согласуются.

См. выше.


M> 1 паттерн-мэтчинг на 20 строк легко переписывается на if-else тоже на несколько десятков строк, и вообще никаких преимуществ перед ним не имеет, так как главное их отличие — читабельность. Сотня pattern-matching-ов по всему коду — не переписывается так легко.

В целом согласен.


M>Возможно из-за этого начались проблемы с непониманием с самого начала.

Наверное.

M>Далее


M>

Компилятор паттерн матчинга вообще работает со своим представлением дерева(даже не одним) и сразу выдает дерево оригинального языка


M>

Я компилирую в дерево, не в парсере, а после того, как использовал всю интересную информацию.



M>Эти слова опять между собой не согласуются.

M>Есть два варианта:
M>а) преобразовать твоё расширенное AST в стандартное AST, и с ним уже работать (верифицировать, резолвить, оптимизировать и пр.), при этом ты можешь свободно использовать pattern-matching в работе со стандартным деревом (так как набор его элементов фиксирован).
M>б) ты работаешь с расширенным AST ....
M>Первая твоя цитата говорит о том, что ты используешь вариант (а), а во второй ты утверждаешь, что используешь вариант (б).

Вообще то из моей первой цитаты не следует вариант а). Все расширения независимы друг от друга. Каждое обрабатывается своим маленьким (или немаленьким) компилятором. Если одно внутри другого — рекурсивно. Вы же все время настаиваите, что у меня в каждый момент времени должно быть только одно дерево:"расширенное AST" или "стандартное AST".
Взять к примеру паттерн-матчинг. Слева там некие конструкции которых заведомо нет в языке (хотя они могут быть похожи на остальной язык), справа некие statements и expressions, которые вообще не как не могут повлиять на компиляцию собственно паттернов (см. статью или компилятор Nemerle). И самому компилятору паттернов по большому счету все равно с каким языком работать — он работает с таким простым представлением :
A pattern is either a variable, or a constructor applied to a possibly 
empty sequence of patterns. Patterns must be linear : no variable may occur 
more than once in a pattern. 
A (proper) term is a pattern not containing variables. Constructors 
and patterns can be modelled as follows:
 
    type con = { name : string, arity : int, span : int } 
    datatype pat = PVar of string | PCon of con * pat list
 
Example 1. For instance, the three constructors Null, Leaf, and Node declared 
by the Standard ML declaration 

   datatype 'a tree = 
         Null | Leaf of 'a | Node of 'a tree * 'a * 'a tree

can be represented as follows: 
   val Nullc = {name = "Null", arity = 0, span = 3} 
   val Leafc = {name = "Leaf", arity = 1, span = 3} 
   val Nodec = {name = "Node", arity = 3, span = 3}


Результатом является такая конструкция (тоже практически независимая от языка):
datatype access = Obj | Sel of int * access 

datatype 'rhs decision =  
     Failure  
   | Success of 'rhs  
   | IfEq of access * con * 'rhs decision * 'rhs decision


Так вот все эти типы не часть никакого из AST, но 'decision tree' достаточно тривиально преобразуется в "стандартное AST".
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.