Форум TeamX
   Home   Members  
Pages: [1] |   Go Down
 
Author Topic: MSGL  (Read 453 times)
KLIMaka
Пользователь
Posts: 72


MSGL
« on: 13 December 2010, 01:20:38 »

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

Нумсь, приступим. Для начала нужно определить необходимый функционал. Сперва я попытался реализовать интерпретатор, используя лишь tokenize(). Даже успешно реализовал приличную часть функциональности ядра, но в какой-то момент я понял, что код стал абсолютно нечитаемым. Посему пришлось прибегать к небольшим расширениям SSL.
Для реализации лексического анализатора крайне необходима возможность манипуляции со строками. Присутствующего функционала явно недостаточно, и дополнительно необходимо:
  • получение первого символа строки
  • получение всей строки, кроме первого символа.

С помощью этих функций можно посимвольно проанализировать всю строку, чего нам и нужно. Немного обобщив требования, я изменил поведение функции sfall string_split. Оригинальное ее поведение можно посмотреть в документации. Я сохранил существующее поведение, но дополнительно ввел три режима:

string_split(str, key)
  • если key == 0, то возвращает длину строки
  • если key > 0, то возвращает первые key символов строки
  • если key < 0, то возвращает строку за исключением первых key символов
   

Теперь вся необходимая функциональность у нас есть и можно приступать к написанию интерпретатора.
Сначала нужно выбрать, какой же мы будем реализовывать язык? Я выбрал LISP. Почему? Ну, есть две основные причины:
  • В LISP’e отсутствует синтаксис. Точнее он есть, но такой минимальный, что часто LISP называют языком без синтаксиса. Что это нам дает? Это дает значительное упрощение лексического и синтаксического анализатора.
  • Мне всегда хотелось написать функциональный язык. Извините мне мою прихоть Улыбка
   
Я понимаю, что этот выбор сомнителен в том смысле, что LISP – это не тот язык, в котором свободно ориентируются большинство моддеров. К слову сказать, и я к этому большинству отношусь. Но выбор сделан, и отступать некуда, к тому же все не так уж и сложно, если потратить несколько минут и вникнуть в основные понятия языка.

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

Ядро. Внутреннее представление.

Эту часть языка я вовсе не документировал, так что разобраться в ней может оказаться достаточно непростой задачей. На документирование пока нет времени, увы. Хотя там все вполне прозрачно окромя некоторых скользких моментов, связанных с вычислениями форм. Если будет кому интересно, то могу описать поподробнее.

Работа ядра построена на выполнении следующих фаз:
1)   Из входного потока извлекается очередная лексема. Этой лексемой может быть список либо атом. Список – это последовательность лексем, заключенных в круглые скобки и разделенных пробельными символами (пробел, табуляция, перевод строки). Список – структура рекурсивная, что обозначает, что список, в качестве элементов может содержать другие списки. Атом – элементарная единица данных. Это может быть число (1100, -100, 0), строка (“foo”, “bar”) или символ (любая последовательность печатных символов, кроме скобок, символа ‘&’ и пробельных символов)
2)   Если входная лексема - список, то считается что первый элемент списка – это имя функции, а все остальные элементы – ее аргументы. В таком виде происходит выполнение функции, имя и аргументы которой последовательно извлекаются с помощью фазы (1)
Это очень укрупненная схема работы ядра, там еще происходит и разыменование ссылок, и обработка специальных функциональных форм, и поддержка времени исполнения и еще несколько штуковин.

Ядро. Внешнее представление.

За описанием функций, используемых в данном разделе идти в файл lib.ssi.

Внешне язык представлен как интерпретатор, который получает входной поток, выполняет его и возвращает результат выполнения. Программа на MSGL (ну, как-то так решил назвать язык) представляет собой одно S-выражение. S-выражение – это… Это одно из тех понятий, которые проще понять, чем объяснить. Кратко – это список атомов и списков. Это обозначает то, что каждой открывающей скобке должна соответствовать своя закрывающая скобка. Например:

–   ((foo bar) 1 2 3 ( 7 5)) – правильное S-выражение.
–   ((foo bar( 1 2 3 ( 7 5)) – неправильное S-выражение.

Итак, программа – это S-выражение. MSGL – язык функциональный, и нет ничего странного в том, что основным действием в нем является вызов функции. Как уже отмечалось выше для того чтобы вызвать функцию ее необходимо разместить в начале списка, остальные элементы которого представляют из себя фактические аргументы этой функции. Такая запись называется функциональной формой.

(foo 1  2 3)  - это вызов функции foo с тремя аргументами 1, 2 и 3

Да, я не вводил обработку комментариев, так что комментировать код пока никак нельзя.

В MSGL’е как и в LISP’е действует правило, гласящее: «Вычисляется все, кроме того, что запрещено». Это обозначает то, что каждая лексема, встреченная во входном потоке исполнения, будет вычислена. Под «вычислением» понимается процесс получения истинного значения лексемы. Если лексема является списком, то он считается функциональной формой, и заменяется на значение, получаемое при выполнении этой функциональной формы. Если же лексема является символом, то в случае, если этот символ является ссылкой, символ заменяется на результат своего разыменования. Если же символ не является ссылкой, то результатом его вычисления является он сам. Во всех остальных случаях результатом вычисления лексемы является сама лексема. Давайте посмотрим пример: допустим foo является ссылкой на функцию div, тогда запись формы:

(foo (add 10 (add 10 10)) 10)

фактически будет последовательно свернута в:

(div (add 10 (add 10 10)) 10) – разыменовываем foo
(div (add 10 20) 10) – заменяем (add 10 10) на результат 20
(div 30 10) – заменяем (add 10 20) на результат 30
3 - заменяем (div 30 10) на результат 3

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

Запретить же вычисление можно с помощью записи символа «’» перед лексемой. Например, в предыдущем примере можно написать так:

(‘foo (add 10 (add 10 10)) 10)

В этом виде он свернется в:

(foo (add 10 (add 10 10)) 10) – не разыменовываем foo
(foo (add 10 20) 10) – заменяем (add 10 10) на результат 20
(foo 30 10) – заменяем (add 10 20) на результат 30
выполняем нашу foo с аргументами 30 и 10

Т.е. вычисление лексемы, предваряемой «’» сводится к удалению этого самого «’». Важно заметить, что списки, предваряемые одинарной кавычкой, выводятся из потока исполнения, и как следствие не будут вычисляться. Например:

(displayx (add 1 2)) -> выведет 3
(displayx ‘(add 1 2)) -> выведет (add 1 2)

Также важно заметить, что лексемы вычисляются единожды. Это значит, что в случае, если A ссылается на B, которая в свою очередь ссылается на C, и записав:

(displayx A) -> получим B, но не C.

Вслед за возможностью вызывать функции следует рассмотреть возможность определять собственные функции. Функции в MSGL представляют из себя лямбда-тела, т.е. безымянные функции. Вот так можно связать лямбда-тело с именем:

(set sqr ‘(lambda (x) (mul x x))) – это функция возведения в квадрат

Синтаксис очень прост и состоит из списка, который содержит:
  • ключевое слово lambda
  • список формальных аргументов
  • последовательность лексем, которые будут вычислены
   
Результатом вычисления функции является результат вычисления последней лексемы в ее теле. Так можно использовать объявленную ранее функцию:

(displayx (sqr 10)) – выведет 100

Лямбда-тела можно использовать везде, где предполагается наличие функции. Например, чтобы прибавить к каждому элементу списка 10, можно записать:

(displayx (map ‘(lambda (x) (add 10 x)) ‘(1 2 3 4)) -> (11 12 13 14)

Каждая функция образовывает замыкание. Это значит, что ссылки, видимые во внешнем замыкании, перекрываются ссылками, определенными в данном замыкании. Т.е. по существу это аналог области видимости в таких языках как С или Pascal. Поясню на примере:

(seq
   (set a 10)
   (displayx a)               выведет 10
   (displayx ((lambda (a) a) 5))         выведет 5
)

Также возможна рекурсия, куда ж без нее. Но есть одна проблема –уровень вложенности не должен превышать 12. С чем это связанно? Наверняка пока сказать не могу, но возможно с переполнением стека скрипта.

Библиотека функций.

В файле lib.ssi представлена реализация некоторых полезных функций. Каждая снабжена небольшим пояснением с примерами применения. Думаю, не составит труда с ними разобраться. Пока практически полностью отсутствует определение функций, связывающих MSGL c SSL. Написание их является тривиальной задачей, но пока руки не дошли.

Поддержка времени выполнения.

Этим занимается модуль stack.ssi. Здесь тоже нет никаких комментариев, но по-моему там все предельно просто. Этот модуль занимается только хранением значений ссылок и обслуживанием стека замыканий.
Что происходит при выполнении функции set? Вычисляется символ и значение, которое ставится в соответствие это символу. Важно не забыть, что оба аргумента вычисляются! Например:

(seq
   (set a 10)               присваиваем а 10. а еще не ссылка
   (set a 5)               присваиваем десяти пять. Смысла в этом ноль.
   (set ‘a 5)               присваиваем а 5
)

С помощью set можно создавать ссылки:

(seq
   (set a 10)
   (set b ‘a)
   (displayx (deref b))         выведет 10
)

Здесь применение b в последней строке сначала разыменуется в а, а затем еще разыменуется с помощью функции deref в 10.
На сегодня пока все, на днях напишу продолжение.

Здесь брать правленный ddraw.dll, исходники, и мини-модик, который дает Клинту интерпретатор, который при наведении на него курсора исполняет нулевое сообщение в его msg-файле.
« Last Edit: 13 December 2010, 01:40:48 by KLIMaka »
Rainman
Пользователь
Posts: 69

301104000
Re: MSGL
« Reply #1 on: 13 December 2010, 11:46:10 »

Очень интересно. Просто для моего кругозора: какие дополнительные возможности (теоретически, конечно) MSGL может дать по сравнению с оригинальным языком fallout2 и sfall? Или, может быть, MSGL может вырасти в инструментарий для написания движковых расширений или нового движка? Каков потенциал у нового языка?

Наш большой пост апокалиптический проект "Олимп 2207"
http://olympus2207.com
Jordan
Пользователь
Posts: 416

476228895
Re: MSGL
« Reply #2 on: 13 December 2010, 13:49:35 »

Очень познавательная статья.

Возможно ли сделать другой синтаксис?(технически это осуществимо?) К примеру синтаксис oberon 2.


Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
Jordan
Пользователь
Posts: 416

476228895
Re: MSGL
« Reply #3 on: 13 December 2010, 14:55:58 »

Есть идея. Может сделать диалоги как в аркануме. Через текстовые файлы.

Пример.

{0}{}{Text|IF|Result|STR}

Text - сообщение
IF - условие
Result - результат
STR - переход к строке или вызов процедуры

Пример

#Начало диалога
{0}{}{Привет|||}
  {1}{}{Есть работа|IQ >= 5|Global[5]:=7|10}
{10}{}{Да, мой огород навещают грызуны. Убей их всех.|||}
  {11}{}{Я это сделаю.||Global[5]:=8|Exit}
  {12}{}{Нет, я из грин писа.|IQ >= 5|Reaction:=-7|Exit}

Скрипты фола на 95% это диалоги. Подскажи как это реализовать. Если это возможно.

Воспрянет Россия, из праха отцов
Расправятся крылья, миллионов сердец
Поднимут все головы и грудью вздохнут
И громка скажут, что пришли
Мы пришли, со столетней войны
KLIMaka
Пользователь
Posts: 72


Re: MSGL
« Reply #4 on: 14 December 2010, 03:07:42 »

Quote
Очень интересно. Просто для моего кругозора: какие дополнительные возможности (теоретически, конечно) MSGL может дать по сравнению с оригинальным языком fallout2 и sfall? Или, может быть, MSGL может вырасти в инструментарий для написания движковых расширений или нового движка? Каков потенциал у нового языка?
Никаких. То есть вообще никаких возможностей. Функциональных конечно. MSGL интерпретируемый, выполняется в контексте скрипта, и по сути интерпретатор делегирует возможности SSL. Это обозначает, что вещи, которые невозможно воспроизвести на SSL также невозможно воспроизвести и на MSGL. Возможности, которые может дать MSGL чисто выразительные. Т.е. используя MSGL мы пишем то же что и в SSL, но немного в другом виде и другими словами. Да, в SSL конечно нет, допустим, функционалов, списков как таковых и т.п., а в MSGL они есть. Но это совсем не значит, что SSL менее функционален нежели MSGL, это неправда. Неправда потому, что как я сказал выше - MSGL пользуется функциональностью SSL, и ни в коем случае не может выйти за ее границы. Так что MSGL  дает только дополнительные возможности выразительного характера. Пример таких возможностей приведен ниже.

Но возможности - это одна сторона медали. А есть другая - темная сторона. И аспекты этой стороны не очень приятны:
1) MSGL медленный. Нет, он ОЧЕНЬ МЕДЛЕННЫЙ! Причины очевидны - он вводит дополнительный уровень косвенности. Если SSL, даже скомпилированный в байт-код медленнее машинного кода раз в 100 (когда то дядька Шилдт приводил подобную цифру, ЕМНИП), то MSGL минимум в 100 раз медленней SSL, что в результате дает 10000 кратное замедление по сравнению с машинным кодом. Но и это еще очень оптимистичная оценка, т.к. MSGL интерпретируется, и методы интерпретации не всегда самые оптимальные (это связанно с ограничениями SSL).
2) В текущей реализации отсутствует контроль ошибок синтаксиса/семантики. Т.е. при возникновении сомнительных ситуаций вы ,в лучшем случае, получите сомнительные результаты. Обычно же просто вылетит скрипт интерпретатора. В первую очередь этот недостаток связан с отсутствием каких-либо средств информирования об ошибках. Нет, есть конечно отладочная консоль, но это не выход, 4-6 строк отладочной информации - этого часто слишком мало. Во-вторых это связано с тем, что я не хотел усугублять и так очень проблемный пункт (1).
3) Отсутствует статический контроль синтаксиса. Это приводит к тому, что вы, забыв поставить или перепутав одну скобку, можете получить вполне работоспособный код, который на самом деле исполняется совсем не так, как вы ожидаете.

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

Quote
Возможно ли сделать другой синтаксис?(технически это осуществимо?) К примеру синтаксис oberon 2.
Да, безусловно. Конечно есть множество ограничений, но почти все из них так или иначе можно обойти. Вот только чего это будет стоить. Синтаксический анализатор выйдет очень громоздким, и производительность его будет стремится к нулю. уж лучше реализовывать синтаксис Форта, например. Его синтаксис как раз  очень хорошо подходит для исполнения на виртуальной машине SSL. Но он тоже больше похож на тарабарщину чем на язык, увы.

Quote
Есть идея. Может сделать диалоги как в аркануме. Через текстовые файлы. ...
Скрипты фола на 95% это диалоги. Подскажи как это реализовать. Если это возможно.
Возможно, конечно.

Здесь реализация. Опять же все скомпилировано и готово к работе.
В acklint.msg приведены несколько вспомогательных функций и сам диалог.
При начале диалога с Клинтом исполняется 0й блок, в котором происходит необходимая инициализация и вызывается режим диалога:

(talk 10)

Здесь мы инициализируем диалог, начиная с 10 сообщения:

{10}{}
{("Привет"
(11 12)
)}

Сообщение должно являться списком, первым элементом которого есть реплика NPC, а вторым - список возможных ответов:

{11}{}
{("Работка для меня есть, а?"
 (gte (stat (dude) 4) 5)   
 (dialog 14)   
 )}
 
{12}{}
{("Покедава" 
 1
 0
)}

Ответы - это тоже списки, которые состоят из:
1) текст ответа
2) условие появления на MSGL. условие является истинным, если возвращает 1, так что можно просто писать 1, если ответ присутствует всегда.
3) код, который выполнится при выборе этого ответа. Для перехода к следующей реплике нужно записать (dialog N), где N - номер сообщения, описывающего реплику (как в сообщении 10).

Вот так вот несложно можно реализовать твою идею. Но сам посмотришь как это подтармаживает. Хотя если реализовать функцию dialog прямиком на SSL, то будет намного шустрее.
За сим откланяюсь...
« Last Edit: 14 December 2010, 03:19:14 by KLIMaka »
Pages: [1] |   Go Up