LanguageGame Final Report

YAMAMIYA Takashi

Qript One Soft, INC.

For giving instruction to a computer, now we have many ways as selecting menu, push button, drag icon or so. Recent researches of computer user interface have developed various methods of interact with computer. Above all, with using WYSIWYG (What You See Is What You Get) way, user interface becomes very rich and useful for non-engineer. But yet, the most fundamental way of to dialog with computer is to input a sequence of command kind of programming language.

Using WYSIWIG style has advantages when a user uses a computer instead of a real paper. But to deal with more abstract or involved matter, using a programming language has more benefit because symbols are more stable and we can use powerful idea as a recursion or a reference with such language. Then I think the importance of programming language could be never change however GUI will be more improved.

There are various languages in the world, and there are many interesting aspect and taste in each language. I thought that a grammar of the programming language is very interesting but developing a language must be more fun. Of course making a language seemed to be difficult. Then I have taken another way to develop a parser generator that people can make their own script easily.

A parser generator is one of the most basic software in computer. Historically, various programming languages have been developed. And to make developing their parser easily, the technique of automatic parser generation was found. Now the parser generator becomes established technology.

The motivation of LanguageGame project was very simple. If a parser generator has pretty GUI for non-professional user, what’s going to happening? Programming language is indispensability for computer. To learn programming language is to see computer deeply and to use more effectively. It’s also an important aspect to remember that a programming language parser is a program written in a programming language.

If a user just uses a computer as alternative to a real paper, a pencil or so, this aspect has no point yet. But if you want to handle symbols freely with a computer, The recursive aspect that a programming language is a program is very important. Though this aspect is assumed as an axiom for computer engineers when editing or debugging, if non-programmer like students, artist or businessperson can use it, I think that new application of computer should spread from here.

As first phase of developing LanguageGame, I surveyed GUI this project needed. Because I wanted to be focused on GUI, I chose Squeak as developing environment that has useful library and has informative code like “eToys”. And I used T-Gen as a table driven parser generator engine.

As development progressed, it become clear about the character that LanguageGame should be equipped. The following are especially mentioned as an important point.

To make user operation reflect as immediately as possible, improvement in user-friendliness can be expected. I designed about the data structure required for this real-time nature.

Usually, we write a computer program using a series of texts. But not only texts, we can write a program using any symbols like graphical icons if their analysis is possible. In LanguageGame, programming with pictorial symbol was supported in order to give a sociable impression to user.

To describe a grammar, BNF (Backus-Naur Form) notation was established. But to describe a meaning, there are many way for definition. In LanguageGame, notation of BlockContext is used as representation of meaning.

Not only for programmer, but also for general user, it is important to understand how to process in any program. Watching internal process and changing its behavior dynamically, user can get insight into the system intuitively. I developed the simplest debugger simple, which realizes this purpose.

To operate external objects freely, a user can create pleasant application. Then LanguageGame need adjustable external interface. It is very difficult work to design such interface. In the present implementation, reference of an external object was statically stored in the class variable. It is hard to say that is has succeeded now. This portion is a future big subject.

A main window has two panes. The upper part is called grammar pane that a user describes a grammar using BNF notation here. And the lower part is input pane that a user can input the sentence to be analyzed now. As each interface, text mode and tile mode exists. A grammar or a sentence can be build intuitively with drag and drop in tile mode.

With right click, the control menu appears. The meaning of command is as follows.

Table 1 menu

In LanguageGame, BNF notation that is subset of T-Gen is used. But compare to T-Gen, user cannot make own scanner but can use preset scanner in LanguageGame. How to describe grammar is follows.

A user can input with tile mode either a grammar pane or an input pane. In tile mode, to add the symbol is possible with drag and drop.

To use a tile in the input pane, first, you should call a palette pane from right click menu. Terminal symbols that can be used in the present grammar will be in the palette. When you drag the terminal tile from the palette to a nonterminal tile in an input pane, the nonterminal changes green if the nonterminal can acceptable the terminal.

If a nonterminal can determine which rule does match for the terminal uniquely, the remaining terminals of the rule are complemented automatically.

In a grammar pane, a user can also do tile operation. Additionary, in the block element where is rightmost of a rule, a user can drop a phase tile from eToys’ viewer. In this case, the phase tile is automatically changed to expression of a block context in Smalltalk.

As a tile, not only a string but also any morph can be used. LanguageGame treats externalName of the morph as a terminal symbol of the tile. Specifically, if a morph is named and is dragged into a tile, the morph treated as a symbol string of the tile. The morph and the symbol is bind in the system, and the registered symbol string is always able to change into morph.

Using this function, programming by the pictorial symbol is realizable. It may be useful for user who cannot speak English and also to collaboration among people who have another language.

To look and delete these registered morphs, an image tool from menu is used.

Action block is used to add a meaning to syntax tree. An example is shown

This grammar counts the number of words “egg” in the input sequence, and returns the number. In example, to input a sequence “egg egg egg”, a following tree is generated.

It is easier to actually be shown rather than to explain by sentence about operation of a computer. LanguageGame is prepared easy debugger called Mole to debug grammar happily. Mole is shown with a right click menu on the nonterminal of a parse tree.

When Mole is clicked, it will move onto the symbol that should me executed, and display the answer returned from the action.

Mole is also controllable with the mechanism of eToys in Squeak, it has ‘fire’ command in eToys’ viewer.

There are some advantages in using tile style like eToys to input from a user. One is that the users have familiarity. Another is being able to restrict operation of user appropriately. Restriction of operation can reduce incorrect operation and can stay focus a user on the essence of the problem. To restrict suitable operation, the complex interaction between tiles is required. To realize these, the following structures ware required.

The GTile object for displaying a tile on a screen: The GTile itself does not know the meaning of a sentence but know a GNode. If other morph dragged on the GTile, it will ask its GNode the processing. GNode decides whether accept the morph as a symbol or ignore.

The internal structure GNode of a tree: Contrary to other parser generator that process input sequences collectively, In LanguageGame, a tree is dynamically changed by operation of user. To realize this function, the node itself has the reference to its parser. The following operations are performed when the terminal B is dragged to the nonterminal A.

First, A compares whether an own parser and the parser of B are the same. When it differs, B "is made to pollute with A's parser", and B is scanned again. When the grammar class of B is acceptable, A chooses the rule that suits from own parser, and make B a child node according to the rule. When other child nodes become settled uniquely by the rule, the child node, which suits automatically, is generated and it connects (it works as an input complement).

When “fire” is selected in the menu on an input pane or a tree, LanguageGame executes its sequence.

If it is where simple four-arithmetical-operations computer is created, this is realizable just to evaluate the given block according to input. However, using execution control of a loop etc. and a debugger, the simple wrapper for supporting delay execution is needed.

To hide the complexity of delay execution from a user, the delay execution object GMonad in LanguageGame has adopted the model “performed after asking.”

When a GMonad evaluates self, the exception occurs each time for debugging. Although this exception is usually ignored, but when Mole runs for debugging, Mole receives this exception, interrupts its process and tells a user about the context that have variables under execution.

As interesting usage, combining this debug function and eToys’ step execution, such as a musical automatic performance can be carried out.

LanguageGame hold the reference to external objects as a GGame class variable. There are the two following kinds.

The dictionary showing the variable used within a block. When any morph is dragged into text mode pane, morph will be registered into VariableTable. Thereby any morph can be operated in a block.

It is the dictionary, which connects a morph to a terminal. A morph registered at once can be used in all LanguageGame windows.

Because this project had an investigation-purpose, the comprehensive combined test was omitted. To help the implementation, simple unit test was suitably created with SUnit.

The evaluation of LanguageGame is very difficult because there is no parser generator product that was characterized with GUI to compare in others. To focus attention on the educational purpose as first goal of LanguageGame, it is specializing in the meta-level concept of program compare to other programming tools for education. That is to say, this is a tool for understanding the program that makes a program rather than the teaching material for doing/use of a program.

This is a powerful feature but has a risk of the purpose becoming ambiguous. Then for LanguageGame, how to use with many samples is required.

The present implementation has many redundant and unstable elements. I want to narrow down the goal from now and to aim implementation that is easy to use. Anyway, concrete applications currently I assumed and a technical improving point is described

About the real-time parsing which is feature of LanguageGame, it is still incomplete. Especially, it has many portions with unstable operation in order to have to hold an incomplete syntax tree while usual parser generator treat only complete syntax tree. I have to complete this portion. Moreover, although now only LL grammar is supported, larger grammar class is necessary for practical.

To be dependent on BNF grammar with recursion, now it does not understand easily for non-programmer especially to describe a grammar as list structure. The notation is friendlier and more intuitively to adopting regular right-part grammar.

When dealing with recursive or tree structure in field, such as mathematics and chemistry, LanguageGame offers an intuitive model. There are many cases that the notation of an idea is difficult but the idea itself. In such a case, unnecessary confusion is avoidable to design simpler notation with LanguageGame.

As a precedence example in this direction, there are functional language groups like as Lisp and Haskell. Those languages are suitable for symbol processing to be nearly mathematical notation. LanguageGame also has the character like a functional language because it does not depend in order of processing and it does not have a state. Then LanguageGame can be said that it is the environment that united with descriptiveness of a functional language and friendliness Squeak has. Moreover, the environment of Lisp or Haskell itself can be implemented in Smalltalk using the framework of LanguageGame, and the multimedia nature of Squeak can also be united with the logical feature such languages have.

A lot of interesting application can be considered from the dynamic syntax tree generation function LanguageGame has. For example, recently in integrated development environment, it needs the function to detect dynamically the code that a user inputs and to provide an input complement and help. If the parser generation system of LanguageGame is more developed, the comprehensive framework for such input support function is generable. Moreover there may be applicable to the input support not only in development environment but also general purpose.

It is a very effective idea that complex object is made from a text in a viewpoint of the application productivity. For example, in web application, now using HTML language makes building interface easily and more portable than RAD system. Although XML with abstract semantic data will more popular, using a language for more abstraction that specialized in each application, it is able to generate a user interface automatically from a business rule.

In system development, cost occurs with the objective description of a business rule as well as programming. As another possibility of LanguageGame, there are development and implement of notation that support description of such a rule.

The present accomplishment can be downloaded from here.

株式会社クリプトワンソフト

世界には数多くのさまざまな言語があり、それぞれ興味深い性質と特徴を備えている。これらプログラミング言語の文法には非常に興味を惹かれるが、言語自身の開発はより興味深いに違いない。もちろん、言語の開発は非常に困難である。そこで、人々が彼ら自身のプログラミング言語を簡単に作れるような方法を考える事にした。

パーサジェネレータは最も基本的なコンピュータソフトウェアの一つである。歴史的にさまざまなプログラミング言語が開発されてきたが、これらの言語のパーサを簡単に開発するために、自動パーサ生成系の技術が開発されてきた。いまやパーサジェネレータは確立された技術になっている。

開発が進むにつれて、言語ゲームが備えるべき性質についても明らかになった。特に重要な点として以下の物が挙げられる。

ユーザの操作を出来るだけすぐに反映させる事により効率の良い開発が期待できる。このリアルタイム性のために必要なデータ構造について設計を行った。

通常プログラミング言語では一連のテキストを記述する事によって意味を記述する。しかし、解析可能な情報であれば特にテキストにこだわる必要は無い。言語ゲームでは、ユーザにより親しみやすい印象を与えるため、絵文字によるプログラミングをサポートした。

プログラマだけでなく一般ユーザにとってもコンピュータがどのようなプロセスで動作しているのかを把握することは重要である。コンピュータの動作を追跡し、可能であれば動的に振る舞いを変更する事によってユーザはシステムの動作を直感的に把握する事が出来る。この目的を実現する最低限シンプルなデバッガについて開発した。

自由に外部のオブジェクトを操作する事によって、ユーザは楽しいアプリケーションを作成する事が出来る。しかし整合性のある外部インタフェースを設計する事は非常に難しい仕事である。言語ゲームの場合、この点において成功しているとは言い難い。現在の実装では多少強引だがクラス変数に静的にオブジェクトの参照を格納して外部との通信を実現している。この部分は今後の大きな課題である。

文法ペイン、入力ペインのどちらでもタイルモードによる入力が出来る。タイルモードでは、ドラッグアンドドロップによるシンボルの追加が可能である。

入力ペインでタイルを使うには、まずパレットを右クリックメニューからパレットを呼び出す。パレットには、現在の文法で使用可能な終端記号が現れる。これをドラッグして、入力ペインの非終端記号の上に重ねる。もしも該当する非終端記号がドラッグしたタイルを解釈できる場合、非終端記号は緑色に変化する。

非終端記号が、ドラッグされた終端記号に対してルールを一意に決定する事が出来る場合、そのルールの残りの終端記号は自動的に補完される。

この機能により、絵文字によるプログラミングが実現出来る。英語を話せないユーザの助けになる他、将来的には別の言語を持つ人々が共同作業を行う際に役立つ可能性がある。

解析された文に意味を付加させるため、アクションブロックと呼ぶ仕組みを導入している。例を示す。

終端記号とモルフを結びつける辞書。一度登録されたモルフは、すべての言語ゲームウインドウから同じように使う事が出来る。

これは強力な特徴である反面、何に使えるのかあいまいになってしまう危険が伴うため、数多くのサンプルを用意しどのように使うと効果的なのかを強く打ち出す必要がある。

現在の実装には冗長、不安定な要素も多い。今後はさらに目的を絞り、使いやすい実装を目指したいと思う。現時点での技術的な改善点および想定している具体的な応用について述べる。

数学や化学などの分野で再帰的な構造を扱う場合に、言語ゲームは直感的なモデルを提供する。ある概念の難しさが、概念そのものから来るものでは無く、その表記法による場合が多い。そのような場合に、言語ゲームによってより単純な表記法を設計することで無用な混乱を避ける事が出来る。

言語ゲームの持つ動的な構文ツリー生成機能はそれだけでいくつもの興味深い応用が考えられる。例えば、近年の統合開発環境においてはユーザの入力するコードを検知し、適切な入力補完やヘルプの提供が必須となっている。言語ゲームのツリー生成系を発展させるとそういった入力支援機能の包括的なフレームワークを生成することが出来る。また、これらは開発環境のみならず、一般的なアプリケーションにおける入力支援に応用する事が出来るだろう。

システム開発の中で、実はコーディングそれ自体よりもルールの客観的な記述と言った点により多くのコストが発生する。言語ゲームのもうひとつの可能性として、このようなルールの記述を支援するような表記法の開発と実装があるだろう。

現在の成果物はこちらからダウンロード出来る。