2018年5月3日木曜日

オレオレ言語、Expressoについて・・・そもそも言語とは?

こんにちは、1ヶ月ぐらいぶりでしょうか。はざまです。ここ最近、オレオレ言語のExpressoの記事を立て続けに上げてきましたが、そもそも言語とはなんなのでしょうか?

ここでいう言語とは、もちろん我々が日常生活で使用する自然言語ではなく、プログラミング言語を指していますが、では、プログラミング言語を作るとはどういうことでしょうか?
プログラミング言語を作るには、大きく分けて4つの工程を理解し、制作する必要があります。レキサー(lexer)、パーサ(parser)、アナライザ(analyzer)、ジェネレータ(code generator)です。アナライザは広く言われている呼称かは知りませんが。
Expressoにおいては、レキサー、パーサはパーサジェネレータを使用して自動生成、アナライザは手動生成、ジェネレータは、式木を活用しています。カタカナのままでは、それぞれの役目のイメージが浮かばないと思うので、和訳すると、順にトークン生成器、構文解析器、構文解釈器、コード生成器みたいな感じになります。順に噛み砕いていきましょう。

まず、トークンとは何かですが、その言語において、最低限の意味をなす文字列を表します。例えば日本語だったら、品詞がトークンに当たりますかね。この文章の頭から日本語のレキサーにかけると、こんにちは,1,ヶ月,ぐらい……などとトークン化された単語が表示されるでしょう。
このトークンを元に、その言語で特定の意味を表す文、式などを構成するのが次のパーサの役目です。同様にこのブログの文章をパースすると、こんにちは、1ヶ月、ぐらい……などとパースされて式(まあ日本語だと、微妙ですが、expressionなら意味が通るでしょう)になり、構文木を生成します。
そして、構成された文、式の意味を解析し、何を意図しているかを解釈するのが、次のアナライザの役目です。このブログの文章で行くと、こんにちは=挨拶、1ヶ月=期間、ぐらい=期間の範囲を指定する……などと解釈されて意味(semantics: 自然言語の分野ではこう呼ばれないと思いますが)が構成されます。
さらに、最後のコード生成のフェーズはその名の通り、解釈してできた動作を実際に行うコンピュータが解釈できるコード(まあ、究極的にはアセンブリですね)に置き換える作業です。日本語の例には例えられないので、例はありません。このようにして、ある言語のソースコードは解釈されて実行できるコードに翻訳されます。上記の工程のうち、Expressoの例でもわかるように、第2ステップまではパーサジェネレータにより、文法規則さえ与えれば、自動化できます。もちろん、手でパーサを書くこともできますが、一般にyaccなどのツールを使う方が、最適化が行われて無駄のない構文解析が行えるでしょう。文法の要素の1つにLL(1)というものがありますが、これは手動で書いたパーサでは担保するのが困難でしょう。もちろん、LL(1)は文法そのものに付随する要素なので、文法自体がLL(1)ならば、手で書こうが、機械で生成しようが、LL(1)になります。
一方、意味解析のフェーズは、自動化が難しい分野です。構文木を本にどう解釈、意味付けを行うかは、言語に依存する部分が大きいためです。同じ=記号でも、ある言語は代入と解釈し、ある言語は等号と解釈するかもしれないのです。同様に、コード生成のフェーズも自動化は困難でしょう。この程度なら自動化する手段はありそうですが、この意味をどのように実行できるコードに反映するかも、実装によって異なってきます。

このように、言語を作るとは、主に4つの工程を通して、ただのテキストを実行できる何かに翻訳するプログラムを構成することです。文法は自然言語のように、テキストおよび記号から合法な文字列を導き出すことであり、一般にLL(1)の文法は、いい文法とされます。LL(1)は、1個先のトークンを読むだけで意味の弁別が行えるという意味だからです。先読みが必要ないということは、それだけ動作も速くなります。

いかがでしたでしょうか?あなたもプログラミング言語を作ってみたくなりましたか?言語を作ることは、主にコマンドラインで動くプログラムを作ることになるので、WebなどGUIありきのプログラミングに慣れている方にはハードルが高いかもしれません。ですが、言語自体ができてきてコードコンプリーションなどのユーザ支援の機能を実装する段階に入ると、GUIのプログラミングも出てきます。もちろん、実用的な言語を作るならば、何かしらの目的がないと続かないでしょうが、お遊び程度にCのサブセットを実装してみるのも一興かもしれませんね^ - ^

2018年3月25日日曜日

My original programming language, Expresso -- The import statement and interoperability with other .NET languages

Hello, again. This is HAZAMA. And yet another blog post about Expresso.

In a previous blog post, I said that you can now use .NET as the standard library, and I expanded the specification further and it now supports interoperability with other .NET languages via assemblies. In addition, I also revised the specification of the import statement, so I'll cover it.
Let's say we have the following C# source code:

//In TestInterface.cs
using System;
using System.Collections.Generic;

namespace InteroperabilityTest
{
    public interface TestInterface
    {
        void DoSomething();
        int GetSomeInt();
        List<int> GetIntList();
    }
}

// In InteroperabilityTest.cs
using System;
using System.Collections.Generic;

namespace InteroperabilityTest
{
    public class InteroperabilityTest : TestInterface
    {
        public void DoSomething()
        {
            Console.WriteLine("Hello from 'DoSomething'");
        }

        public List<int> GetIntList()
        {
            Console.WriteLine("GetIntList called");
            return new List<int>{1, 2, 3, 4, 5};
        }

        public int GetSomeInt()
        {
            Console.WriteLine("GetSomeInt called");
            return 100;
        }
    }
}

// In StaticTest.cs
using System;
using Expresso.Runtime.Builtins;

namespace InteroperabilityTest
{
    public class StaticTest
    {
        public static void DoSomething()
        {
            Console.WriteLine("Hello from StaticTest.DoSomething");
        }

        public static bool GetSomeBool()
        {
            Console.WriteLine("GetSomeBool called");
            return true;
        }

        public static ExpressoIntegerSequence GetSomeIntSeq()
        {
            Console.WriteLine("GetSomeIntSeq called");
            return new ExpressoIntegerSequence(1, 10, 1, true);
        }
    }
}

Assume that the DLL containing the above code is named InteroperabilityTest.dll and we'll write this Expresso code:

module main;


import InteroperabilityTest.{InteroperabilityTest, StaticTest} from "./InteroperabilityTest.dll" as {InteroperabilityTest, StaticTest};

def main()
{
    let t = InteroperabilityTest{};
    t.DoSomething();
    let i = t.GetSomeInt();
    let list = t.GetIntList();

    StaticTest.DoSomething();
    let flag = StaticTest.GetSomeBool();
    let seq = StaticTest.GetSomeIntSeq();

    println(i, list, flag, seq);
}

Then we'll see the Console.WriteLine outputs, 100, [1, 2, 3, 4, 5, ...], true and [1..11:1] on the console. As you can see, although you generally call only functions using FFI(Function Foreign Interface), here you can create instances and even call instance methods. Of course, it's because we run on the same runtime environment, the CLR. With the compiled DLL, you can create instances and call methods from other .NET languages such as C#. We take full advantage of the .NET environment, huh?
Apr. 7 2018 added: Although you could have "gotten" properties, it now supports "setting" properties.
It's almost there where we achieve complete interoperability with foreign .NET languages. Apr. 8 2018 added: Now you can refer to enums defined on IL codes. That means that we have achieved complete interoperability with other .NET languages, I suppose.
C# can interoperate with C++, so we could interoperate with C++ from Expresso if we wrap it in C#.

So notice the import statement has changed? In the previous post, the import clause takes a string but now it looks more like the ones in Python or maybe Rust(Rust calls it use statements, though). When the import statement is written in EBNF, it looks something like the following:

"import" ident [ "::" ( ident | '{' ident { ',' ident } '}' ) ] { '.' ( ident | '{' ident { ',' ident } '}' ) [ "from" string_literal ] "as" ( ident | '{' ident { ',' ident } '}') ';'

This means that you can't omit the as clause unlike Python. In Expresso, you have to alias imported names. Otherwise you would have to refer to them with names containing "::" or "." but Expresso doesn't allow it. You use "::" when you refer to a type that belongs to a module. This is also true for other expressions.
On the other hand, you also specify the namespace when you're referring to a type in external assemblies that are written in C#. In addition, when doing so you can't import variables and functions directly. This is because IL code doesn't allow you to define variables or functions on assemblies.
The file names in the from clause is relative to the source file that the import statement resides in. That means that InteroperabilityTest.dll locates on the same directory as the source file. This rule applies as well when you refer to .exs source files.

Now that we can interoperate with C#, I'm expecting to write the Expresso compiler itself in Expresso.

オレオレ言語、Expressoについて・・・importと外部アセンブリ編

こんにちは、今月何回目かわかりませんが、はざまです。今回もExpressoについてです。

先日の記事で、.NETを標準ライブラリとして使用できるようにしたと書きましたが、今回その仕様をさらに改良して、任意の外部アセンブリを読み込んで相互運用できるようにしました。それに合わせて仕様が曖昧だったimport文も見直したので、簡単に解説しておこうかなと思います。
まず、以下のようなC#のコードがあったとします。

//In TestInterface.cs
using System;
using System.Collections.Generic;

namespace InteroperabilityTest
{
    public interface TestInterface
    {
        void DoSomething();
        int GetSomeInt();
        List<int> GetIntList();
    }
}

// In InteroperabilityTest.cs
using System;
using System.Collections.Generic;

namespace InteroperabilityTest
{
    public class InteroperabilityTest : TestInterface
    {
        public void DoSomething()
        {
            Console.WriteLine("Hello from 'DoSomething'");
        }

        public List<int> GetIntList()
        {
            Console.WriteLine("GetIntList called");
            return new List<int>{1, 2, 3, 4, 5};
        }

        public int GetSomeInt()
        {
            Console.WriteLine("GetSomeInt called");
            return 100;
        }
    }
}

// In StaticTest.cs
using System;
using Expresso.Runtime.Builtins;

namespace InteroperabilityTest
{
    public class StaticTest
    {
        public static void DoSomething()
        {
            Console.WriteLine("Hello from StaticTest.DoSomething");
        }

        public static bool GetSomeBool()
        {
            Console.WriteLine("GetSomeBool called");
            return true;
        }

        public static ExpressoIntegerSequence GetSomeIntSeq()
        {
            Console.WriteLine("GetSomeIntSeq called");
            return new ExpressoIntegerSequence(1, 10, 1, true);
        }
    }
}

このアセンブリ名がInteroperabilityTest.dllだとして、以下のようなExpressoのコードを記述します。

module main;


import InteroperabilityTest.{InteroperabilityTest, StaticTest} from "./InteroperabilityTest.dll" as {InteroperabilityTest, StaticTest};

def main()
{
    let t = InteroperabilityTest{};
    t.DoSomething();
    let i = t.GetSomeInt();
    let list = t.GetIntList();

    StaticTest.DoSomething();
    let flag = StaticTest.GetSomeBool();
    let seq = StaticTest.GetSomeIntSeq();

    println(i, list, flag, seq);
}

すると、Console.WriteLineの出力をしつつ、100、[1, 2, 3, 4, 5, ...]、true、[1..11:1]という出力がされます。ご覧の通り、普通FFI(Function Foreign Interface)を使用して呼べるのは関数だけですが、インスタンスの生成、インスタンスメソッドの呼び出しも行えます。ランタイム環境が共通になっている恩恵ですね。また、コンパイル後のILの状態ならば、リフレクションの機能を使用してC#などの他の言語から呼び出すこともできます。まさに「無敵」状態です。.NETを採用した強みが出ていますね。
2018/4/7 追記: 以前からプロパティのgetはできたものの、本日、setも実装し、完全にプロパティを扱えるようになりました。完全な互換性を保持するまであとenumを使えるようにするだけと、あと1歩になりました。2018/4/8 追記: ILのenumも参照できるようになりました。これで完全な互換性を持ったことになるはずです。
C#からC++のコードの呼び出しができたはずなので、C#でラップすることで、C++のライブラリもExpressoから呼べることでしょう。

さて、以前のコードと比べてだいぶ様相が変わっているのが、importの箇所でしょう。以前のコードでは、importの直後は文字列になっていましたが、仕様改訂を経てRustとPythonのimportの合いの子のような見た目になりました。import文をEBNFで記述すると、以下のようになっています。

"import" ident [ "::" ( ident | '{' ident { ',' ident } '}' ) ] { '.' ( ident | '{' ident { ',' ident } '}' ) [ "from" string_literal ] "as" ( ident | '{' ident { ',' ident } '}') ';'

つまり、Pythonと違ってas節は省略できません。これは、元の識別子そのままでインポートできないための措置です。インポートした識別子には、必ず別名をつけなければなりません。そうでなければ、"::"や"."を含む名前で識別せねばならず、これはExpressoの仕様上できないからです("::"や"."を含む識別子は定義できない)。import節は、.exsファイルからモジュール内の型を指定する場合に、"::"を使います。これはその他の式でも同様です。
一方、C#で生成したDLLを読む場合には、名前空間から型名を指定してください。また、C#などで生成したDLLを読む場合、変数名や関数名をインポートする識別子に指定することはできません。ILコードではアセンブリレベルにフィールドやメソッドを定義できない制約のためです。
from節のファイル名は、記述されているソースファイルに対して相対パスになります。つまり、上のコードでInteroperabilityTest.dllは、このソースファイルと同じディレクトリに存在します。この挙動は、他の.exsファイルを読み込む時も同じです。

こうして、Expressoから自由にC#のコードも呼べるようになったことですし、そろそろセルフホスティングだか、セルフブートストラップだかも視野に入れていきたい・・・

2018年3月17日土曜日

My original programming language, Expresso -- The intseq type

Hi, this is HAZAMA. And this is the 5th blog post about Expresso in this month.

Even though I wasn't planning to write blog posts about specific types, I have realized a funny fact about it, and I'm writing this post.
Namely, the intseq type is a builtin type to Expresso, and it is alike to the xrange type in Python or the Range type in Rust. Frankly, it is a generator that produces integers in sequence so the basic functionality is the same as that of the similar types in other programming languages. Although the range in Kotlin can be tested for inclusion with the in operator, Expresso can't. In is a keyword in Expresso as well, but it only is used as the right-hand-side in for loops.

module main;


def main()
{
    for let i in 0..10 {    // start..end:step is a ternary operator。When step is omitted, it will be 1.
        println(i);
    }

    for let j in 9...0:-1 { // If you set step to negative integers, the sequence go in the negative direction. Note that we don't check whether it is valid(On Apr. 5 2018 added: The compiler now checks whether it is correct when the expression consists only of literal expressions. In other words, the compiler issues a warning if you write it as 0...9:-1 instead).
        println(j);
    }

    for let k in 0..10:3 {  // Of course, you can set it to more than 1.
        println(k);
    }
    let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...]; // I wish that we can write it as (0..10).select(|x| x);. From Apr. 5 2018, it can also be written as [0..10, ...];
    let a2 = a[2...4];
    println(a2);
}

The above code prints [2, 3, 4] as expected(The actual output will be something like [List<int>, 2...4:1] because it prints the result of calling ToString on it). The type of a2 will be a slice, which is also a builtin type. Even though Rust has the Slice type as well and it also allows us to write like that, other programming languages don't. So it is a strong point of Expresso.
In Kotlin you can create ranges for floats(because they don't make sense I may get it wrong), but in Expresso you can do so for ints only. Note that it might raise an exception when you try to create a range outside of the range of the int(Added on Apr. 5 2018: Actually the compiler complains because a number outside of the int range will be interpreted as a double and the intseq expression doesn't accept a double).
In addition, the range operator is one of the two ternary operators in Expresso. The other ternary operator is the conditional operator( ? : ).
Added on Apr. 5 2018: As shown in the comment of initialization of a, you can now initialize a sequence with an intseq. Other languages such as Rust, Kotlin and Swift don't support this syntax, so as far as I know it's unique to Expresso only. You can create an array with [0..10]; and of course, with a step: [0..10:2];.

2018年3月16日金曜日

オレオレ言語、Expressoについて・・・intseq編


こんにちは、はざまです。今回も懲りもせずにExpressoについての記事です。

特定の型に関する記事は特に書くつもりなかったのですが、面白い事実に気付いてしまったので、記事にすることと相成りました。
さて、Expressoのintseq型ですが、これは組み込みの型で、Pythonのxrangeや、RustのRange型を思い浮かべていただくと理解が早いかと思います。まあ、有り体に言えば、整数列を生成するgeneratorなので、そこらへんの基本機能は、他の言語と一緒です。Kotlinのrangeはちょっと強くて演算子で包含確認ができるみたいですが、ExpressoはIncludesというメソッド経由です。Expressoでもinはキーワードではあるものの、for文の右辺にしか使えません。
module main;


def main()
{
    for let i in 0..10 {    // start..end:stepは3項演算子。stepを省略すると1になる
        println(i);
    }

    for let j in 9...0:-1 { //stepを負にすれば、マイナス方向にも行ける。なお、整合性はチェックしてません(2018/4/5 追記: リテラルで指定している場合のみ、整合性をチェックするようになりました。0...9:-1と書くと警告が出ます。変数などを使ってるとチェックされません)
        println(j);
    }

    for let k in 0..10:3 {  //もちろん、stepは1以上でもいい
        println(k);
    }
    let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...]; //将来的には(0..10).select(|x| x);などと書けるようにしたいところ(2018/4/5追記: [0..10, ...];と書けるようになりました)
    let a2 = a[2...4];
    println(a2);
}

上記のコードで、想定通り[2, 3, 4]が出力されます(まあ、Slice型のToString()の結果なので、[List<int>, 2...4:1]みたいな感じですが)。a2の型はこちらも組み込みのslice型になります。Slice型自体は、Rustにもあるものの、このような書き方ができる言語がないので(修正: Rustでもできましたね、この書き方)、特筆すべきところはそこになります。
Kotlinだと、floatに対してもrangeが定義されてるみたいですが(floatの数列って意味をなさない気がするから気のせいなのかな)、Expressoの場合は、intだけです。その範囲外は多分死にます(型しか見てないので、範囲外が来ても明示的なエラーにできず、intへの型変換で落ちるはず)(2018/4/5追記: これは誤りでした。実際にはintの範囲外はdoubleと解釈され、intseqはdoubleを受け付けないと怒られます)。
ちなみにrange operatorは、Expressoに2種類ある3項演算子の1つです。もう一つは、有名な条件演算子( ? : )です。
2018/4/5追記: aの宣言のコメントにあるように、intseqでシーケンスを初期化できるようになりました。意外にも、RustやKotlin、Swiftなどではこの表記は採用されていないので、私の観測範囲ではExpresso固有の機能になります。なお、[0..10];と書けば、arrayにもできます。もちろん、stepを指定して、[0..10:2];などと書くこともできます。機能限定のリスト内包表記みたいな感じですね。

2018年3月15日木曜日

My original programming language, Expresso -- About functions

Hi, this is HAZAMA. And this is an-another blog entry for Expresso this month. We'll be talking a bit about the grammar this time around.

One of the commonest language constructs is the functions and Expresso, of course, has ones. Specifically, Expresso has module-level functions and methods in class definitions. They are implemented as static methods in module classes, and ordinary methods in class definitions, respectively.
module main;


def test()
{
    let a = 10;
    return a + 10;
}

def test2(n (- int)
{
    return n + 10;
}

def test3(n (- int) -> int
{
    return n + 20;
}

def test4(n (- int) -> int
{
    if n >= 100 {
        return n;
    }else{
        return test4(n + 10);
    }
}

def main()
{
    let a = test();
    let b = test2(20);
    let c = test3(20);
    let d = test4(80);

    println(a, b, c, d);
}

This code snippet originated from the test codes again. Return types of Expresso functions will be inferred from the body, but I'm worried about whether to change it or not(In the code above, all the functions will be inferred to return an int). In Kotlin, they are inferred only if the return type is Unit(Void), so I've not decided to make Expresso do that.
Parameters of functions are inferred only when they have the optional values(In the code above there isn't). In the code above, each of the functions:

  1. takes no parameters, and the return type is implicit.
  2. takes a parameter, and the return type is implicit.
  3. takes a parameter, and the return type is explicit.
  4. takes a parameter, and the return type is explicit and it contains a recursive call.
I guess there are no special differences to those in other programming languages.
Note that these are unnecessary comments. Although the parser can parse variadic parameters, the program isn't emitting any code for that so you can't use variadic parameters yet. I added those for the print* functions, but I don't come up with many use cases so I've not decided whether to implement them. Maybe I should implement them because doing so isn't that hard. Likewise, I've not decided to implement so-called string interpolation. This will replace the printFormat function if it exists. This is a difficult problem.(Apr. 8 2018 added: The string interpolation has been implemented and the printFormat function has been removed)

オレオレ言語、Expressoについて・・・関数編

こんにちは、はざまです。今回も例に漏れず、Expressoについての記事です。今回はちょっとだけ具体的な文法に触れます。

どんなプログラミング言語にも当たり前にある要素の1つとして、関数が挙げられます。もちろん、Expressoにも存在しますが、Expressoの場合、モジュールの関数と、クラスのメソッドが存在します。実装上は、前者はモジュールクラスのstaticメソッド、後者は普通にクラスのメソッドです。
module main;


def test()
{
    let a = 10;
    return a + 10;
}

def test2(n (- int)
{
    return n + 10;
}

def test3(n (- int) -> int
{
    return n + 20;
}

def test4(n (- int) -> int
{
    if n >= 100 {
        return n;
    }else{
        return test4(n + 10);
    }
}

def main()
{
    let a = test();
    let b = test2(20);
    let c = test3(20);
    let d = test4(80);

    println(a, b, c, d);
}

このコードもテストコードから引っ張ってきたものですが、Expressoの関数は、戻り値は常に省略しても、本体から推論されますが、この仕様を変えるか悩んでいます(上記の例は、全てintを返す関数と解釈されます)。Kotlinでは、Unit(Voidとほぼ同義)の時のみ推論が効くので、Expressoもそうすべきかもと思っています。
引数の方は、デフォルト値がある時のみ推論が効きます(上記の例には存在しませんね)。
上記の例は上から解説すると、

  1. 引数なし、戻り値省略
  2. 引数あり、戻り値省略
  3. 引数あり、戻り値明示
  4. 引数あり、戻り値明示の再帰呼び出し
になります。まあ、他の言語と大きく違うところはないかと思います。
余談ですが、可変長引数をとる関数のパースはできるようになっているものの、コード生成をするようにしてないので、まだ動きません。とりあえず、print*系のために導入したもので、C#にもあるからまあいいかと思っているものですが、具体的なユースケースがそれほど思いつかず、どうしようか悩んでいます。実装自体はそんなに難しくないので、とりあえず入れてしまうのが正解なのかな〜・・・同様に、一般にString interpolationと呼ばれる機能も導入するか迷っています。これがあると、printFormat関数を置き換えることができるんですよね。実に悩ましいところです。(2018/4/8 追記: string interpolationを実装し、printFormat関数を廃止しました)