kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

オーバーロードされたメソッドをeta-expansionする

eta-expansionとは、メソッドを関数に変換する処理です。 たとえば、

def add(x: Int, y: Int): Int = x + y
val addFunc = add _

で、add _によって、eta-expansionが行われ、メソッドaddが関数に変換されます。このeta-expansion、メソッドがオーバーロードされていると一見正しく行うことができないように見えます。

object O {
  def add(x: Double, y: Int): Double = x + y
  def add(x: Int, y: Double): Double = x + y
}
O.add _
<console>:13: error: ambiguous reference to overloaded definition,
both method add in object O of type (x: Int, y: Double)Double
and  method add in object O of type (x: Double, y: Int)Double
match expected type ?
       O.add _
         ^

これに対して、次のようにしてやればeta-expansionを行うことができます。

object O {
  def add(x: Double, y: Int): Double = x + y
  def add(x: Int, y: Double): Double = x + y
}
O.add _:((Double, Int) => Double)

要はどのような型の関数に変換するか明示してやればいいわけです。eta-expansionは変換先の型を意識せずにできるのがメリットなのでこうしなければいけない時点でメリットが半減シますが、一応回避策はある、ということで。

そういえばOnionにもあるClass Delegation

Onion

先日、Kotiln勉強会というものに行って来ました。まあ、自分の発表は拙作kollectionライブラリの発表という割とどうでもいいものでしたが、それはそうとKotlinエバンジェリストたろーさんがClass Delegationという機能について紹介していました。

speakerdeck.com

要は、

class CountingSet<E>(private val set: MutableSet<E>): MutableSet<E> by set

のようにすると、MutableSetの実装がプロパティsetに委譲されるという機能です。これ、既視感あるなーと思ってみたら、自分が昔作った言語Onion(2005〜) にそのまんまの機能があったではないかということを思い出しました。

OnionはGenericsがなかったりするので（これは単に手抜き）ちょっと違いますが、同じことが

class CountingSet <: Set {
    forward @n :Set;
public:
    def new {
        @n = new HashSet
    }
}

こんなふうに書けます。クラスのヘッダ部分かフィールド部分のどちらに委譲の宣言が現れるかという点で若干の違いがありますが機能的にほぼおなじです。自分も割と先見の明があった（？）のだなあなどと思ったのでした。ちなみに、Onionを作った時期はRubyに大きな影響を受けていたので、メソッド定義がdefだったりフィールドが@で始まっていたりとRubyに影響を受けた節があちこちにあります。今再設計するならだいぶ文法は変わるだろうなと思います。

まあ、今はKlassic開発中なので、Onionはあまり手を入れる気はないですが。

Kotlin用不変コレクションライブラリkollection 0.3リリース

今回のリリースでは、不変キューを追加しました。

github.com

これは各操作の償却計算量が定数時間のキューで、非償却計算量で定数時間にはなっていないので改良が必要なのですが、とりあえず実装が手っ取り早かったのでまずはこちらを実装しました。リアルタイムキューも、PFDSを参考にして次のバージョンで実装したいと思います。

Nim勉強日誌（１） Hello, Parser Combinator!

そろそろ新しい言語に触れないとなあということでこれまでちらっと見たことがあったプログラミング言語Nim

index - Nim Programming Language

を触ってみることに決定。(1)とついていますが、これで飽きてやめるかもしれませんが悪しからず。

  • Python風味のインデント文法
  • マクロ
  • 演算子オーバーローディング
  • 実行速度を上げるためのいろいろな工夫

とかがあるみたいです。自分にとってのHello, World!はパーザコンビネータを作成することだと以前書いたことでもあるし、さっさとパーザコンビネータを作ってみました。

gist.github.com

つまづいたポイントをいくつか：

  • GenericsはC++のtemplateの様に展開されてから型チェックが行われるので、定義したあとに呼び出して初めて型エラーがわかることが多い
  • 謎のinternal errorがしばしば発生する
  • 無名関数(Anonymous Proc)の型を表記する構文がしんどい： proc(arg: type): type のように書かなければならず、しかも、型であるにもかかわらず仮引数名はどうやら省略できないらしい。
  • Anonymous Proc自体の構文もしんどい。無名関数の返り値だけでなく引数の型もすべて表記しなければいけないため、複雑な型を受け取る無名関数を書こうとするとかなり面倒くさい。
  • インデントすべきところとしないで良いところの区別が不明瞭
    • 一行に押しこもうとすると、複雑な行はインデントしてくださいという旨のコンパイルエラーが出る
  • タプルがあるのは良い
  • Genericsもおおむね素直に書ける

今のところの感想としては、内部DSLを書くのにはあまり向いていない言語だなあ…というところでしょうか。

PEGでa1 + a2 + ... + an = bを判定する

PEG Formal Language

このネタは

parser.connpass.com

でToshihiro Kogaさんに教えてもらったもので、私のオリジナルではないのですが、ちょっとおもしろいので貼ってみます。

まず、非負整数nについて、1の出現数によってエンコードします。

0 = 
1 = 1
2 = 11
3 = 111
4 = 1111
...

といった具合です。このようにエンコードされた非負整数について、

a_1 + a_2 + ... a_n = b

が真であるかどうかを通常のPEGで判定できるというお話です。

S <- A !.
A <- "1" A "1" / "+" A / "=";

このようなPEGにおいて、Sは

  • =: 0 = 0
  • 1+1=11: 1 + 1 = 2
  • 11+1=111: 2 + 1 = 3
  • 11+11+11=111111: 2 + 2 + 2 = 6

という文字列を受理しますが、

  • 11+1=1: 2 + 1 = 1

という文字列を受理しません。とてもシンプルなPEGで（Macro PEGでなく）このような計算を表現できるのは少し面白いと思ったので、紹介してみました。

プログラミング言語の好き嫌いと人の好き嫌いは別物である

Language

という至極当然のことを改めて言っておきたいです。

たとえば、自分は今はScalaをメイン言語として使っていて、Javaの色々な部分がイケてないなーと感じることは多々あり、時折ディスることもありますが、Javaユーザを見下したりしたことはないと思っていますし、Twitter上でもJavaメインで使っている人と仲良く（？）やり取りします。JavaScriptは、今のなんでもWebアプリを招いた元凶だとすら思っており最も好ましく思っていない言語のひとつですが、JavaScriptユーザに含むところは何らありません。等々

一方、好きな言語のユーザであっても、この人とは根本的に考えが相いれないなーとか、言動があまりにも攻撃的過ぎてまともにやり取りしたくない人も多いです。個人名はあえて出しませんが。自分の言動が攻撃的過ぎると感じる方ももちろんいらっしゃると思います（自戒を込めて）。

とりあえず書き残しておきたくなったので、ここに記す。

Klassic言語の開発状況

リテラル

  • Byte
  • Short
  • Int
  • Long
  • Float
  • Double
  • Boolean
  • Unit
  • String

演算

加減乗除、比較、論理演算、などなど。異なる数値型の暗黙変換は禁止（Int + LongなどはNG）

リスト

[ [1 2 3]
  [4 5 6]
  [7 8 9]
]

こんな風に、改行だけでなく空白がセパレータになることもできる（実験的文法）。

無名関数

val add = (x, y) => x + y

関数定義

def add(x, y) = x + y

while式

while(condition) expression

foreach式

  • 今のところiterator()メソッドを持っているオブジェクトすべてに適用できる
foreach(var in expression) expression

if式

if(condition) thenClause else elseClause

ヒアドキュメント

println("#{<<TAG1 + 1} #{<<TAG2 + 2} #{<<TAG3 + 3}")
tag1
TAG1
tag2
TAG2
tag3
TAG3

ヒア式

  • ヒアドキュメント実装の副産物として生まれた
println(<<$EXP1 * <<$EXP2); //(1 + 2) * (3 + 4) → 21
1 + 2
EXP1
3 + 4
EXP2

String Interpolation

  • ${}じゃなくて#{}な辺りはRuby風味。
val x = 10
val y = 20
println("x = #{x}, y = #{y}")
println("x + y = #{x + y}")

オブジェクト生成とかメソッド呼び出しとかJava FFIとか

val list = new java.util.ArrayList
list.add(1)
list.add(2)
println(list)
val buffer = new java.lang.StringBuffer
buffer.append("A").append("B").append("C")
println(buffer)
println([
  "FOO"
  "BAR"
  "BAZ"
])
println("FOO".substring(0, 1))

型チェック

  • 実装始めたばっかり
  • ごく基本的な型チェックが動く 
{ val i = 1;
  i } // 型はInt
val a = 1
val b: Long = a //NG。IntからLongへの暗黙変換は許されない
b

クラスシステム(Klass System)

  • 未実装。
  • サブタイピングはオプショナルにしたい

ほとんどメモ書きですが…。