「プログラミング」カテゴリーアーカイブ

これから流行る言語

新言語にできることはまだあるかい

なんとかWIMPS

最近（1ヶ月くらい前）、こんな記事が出ました：

Kotlin, TypeScript, Rust, Swift以降にみんなが話題にするような新しい言語が出てこない、それはなぜか、みたいな趣旨です。客観的に見れば「新しい言語は常に出続けている」わけですが、「みんなが話題にするような」というのが多分曲者なんでしょうね。

例え話をすると、新しい若木は常に生えてきているんだけど、大木に成長するには時間がかかるので、大木にしか興味のない人には「この8年間で新しい大木は登場していない」と判断してしまうのかもしれません。

まあ私としても、Web (HTTP) APIを書く言語とか、JSON色付け係が使う言語はもう出揃ってしまったのかもしれないという気はしなくもないですが、それでも新しい言語が登場して話題を集め（新しい物好きの集団に絞れば「みんなが話題にする」かもしれません）、一定の地位を占める余地はあると考えています。そして、そういう「これから流行る言語」がすでに登場している可能性は十分あります。

（もちろん、どこかの組織または個人が裏でこっそり開発している言語の場合はまだ表には出ていないでしょう。Rustの場合は開発開始は2006年らしいですが、一般公開されたのは2011年で、「裏で開発している」期間が5年ほどあります。）

この記事では、私が独断と偏見で選んだ、「これから流行るかもしれない、（比較的）新しい言語」を紹介してみます。流行の可能性よりも「見るべきところがあるか」という観点で選んだものも含まれます。

なお、ここで紹介する言語は私の情報網に引っかかったというだけであって、必ずしも私自身が試しているわけではありません。不正確なことを書いていたら申し訳ありません。

続きを読む →

新しくプログラミング言語を作るときの区切り文字

コメントを残す

Haskellにはリストやステートメントを区切るカンマやセミコロンを行頭に置くスタイルがあります。

primes = [ 2
         , 3
         , 5
         , 7
         ]
main = do { putStrLn "Hello world!"
          ; print primes
          }

ですが、「カンマやセミコロンを行頭に置く」というスタイルは他の言語のユーザーには奇異に映るのではないでしょうか。以下、そういう前提で話を進めます。

MarkdownやYAMLでは * や - を行頭に置くので、「区切り文字が行頭にある」こと自体は悪くないはずです。Haskellで代数的データ型を定義するときの | を行頭に書いても初学者の違和感は少ないと思います（たぶん）。

普通のプログラミング言語で「行頭に区切り文字を置く」というスタイルを採用するとしたら、どういう区切り文字が適切なのでしょうか？

アスタリスク *, マイナス -, プラス +

この辺はデータ記述言語とかMarkdownでお馴染みですが、普通のプログラミング言語では演算子として使いたいのではないかと思います。

行頭に置いた場合のみ区切り文字として扱うという手も考えられますが、いずれにせよ「式を複数行にまたがって書くときに行頭に演算子を書く」というスタイルとの衝突が懸念されます。インデント量で識別するか、一部の言語のように継続行を表すマークを導入することになるでしょう。

あと、どっちみちインラインでリストを書くときの区切り文字には適していないので、従来のカンマも併用する必要があるかもしれません。

擬似コード：

primes = [
         * 2
         * 3
         * 5
         * 7
         ]

縦棒 |

ML系言語のデータ型定義で使われているやつです。

縦棒は慣習的に「または」の意味で使われることが多いので、リストや逐次実行などの順序が重要な用途には違和感があるのではないかと思います。まあMLのパターンマッチみたいに微妙に順序があるケースにも使われていたりしますが。

擬似コード：

primes = [
         | 2
         | 3
         | 5
         | 7
         ]

空白

レイアウトルールを採用している言語だとそもそも区切り文字が必要なかったりします。Haskellも逐次実行のdoはレイアウトルールによりセミコロンなしで書けます。

最近のHaskellにはQualifiedDoという拡張があって、それを使うと一時的にdo記法を乗っ取れるので、リストの構築に使えたりします：

module M where
import qualified Prelude

(>>) :: a -> [a] -> [a]
(>>) = (:)
{-# LANGUAGE QualifiedDo #-}
import qualified M

primes = M.do
           2
           3
           5
           7
           [] -- 型の関係で最後にこれが必要

他の例だと、Juliaは（多次元）配列を空白や改行区切りで書けるらしいです。空白と改行で意味が変わるみたいですが。

番号

番号から始めるという手もあります：

array =
  1. "first"
  2. "second"
  3. "third"
fn main() {
1. do_something()
2. do_something_else()
3. return 0
}

が、「行を削除したり、コピペで順序を入れ替えた時に修正が必要になる」という欠点があります。

それ以外

ASCIIの記号は少ないので、演算子と被らないように選ぶのは大変そうです。

ピリオド . は自然言語だと普通文末にあるのでカンマやセミコロンと同じ理由で向かない気がします。まあプログラミング言語だとメンバー名の区切りに使われることも多いし、Swiftだと識別子の前に置けたりするので大した問題ではないのかもしれない。

primes = [
         . 2
         . 3
         . 5
         . 7
         ]

コロン : は割とアリかもしれない？コロンは型注釈に使いたい気がするけど、行頭には使わないような？

primes = [
         : 2
         : 3
         : 5
         : 7
         ]

ハッシュ記号 # はどうかな。Markdownの見出しっぽいかもしれない。

primes = [
         # 2
         # 3
         # 5
         # 7
         ]

まとめ

なんか良さそうなのがあったら自分の言語に実装してみてください。擬似コードを載せた記事を書くのでも良いです。

あと、似たような趣旨の記事が既にあったみたいです：

言語処理系コミュニティーでの協働の在り方

コメントを残す

プログラミング言語処理系が好きな人の集まりというコミュニティーがあります。ここは言語処理系を作っている人が多く集まっています。自作言語界隈とも言えます。そこでの話題について、色々と思うところがあったので、記事を書いてみます。

続きを読む →

Standard MLに対する拡張のアイディア

拡張の必要性

私は現在、Standard ML処理系であるLunarMLを開発しています。しかし、Standard MLはほぼ進化の止まった言語です。一応Successor MLという取り組みがありますが、準拠を目指している処理系は多くはありません。

LunarMLが成功するためには、言語標準という枠に囚われずに「モダン」な機能を積極的に取り入れていくことが重要だと考えられます。つまり、拡張機能です。

Standard MLに足りない機能は何でしょうか。LunarMLにどんな拡張を入れれば、使いやすい言語になるでしょうか。

過去の記事ではすでにいくつか機能を挙げ、いくつかは実際に実装しました：

実装済みの拡張機能については以下に説明を書いています：

ここではもうちょっと色々アイディアを出してみます。

続きを読む →

整数除算を浮動小数点演算でエミュレートできるか

古典的な（BigInt以前の）JavaScriptは数値型が倍精度浮動小数点数のみでした。5.2までのLuaも同様です。

このような言語で整数除算を行いたい場合は、浮動小数点演算を経由して行うことになります。例えばJavaScriptで32ビット整数の除算をやるならこんな感じです：

// x, yは整数値とする
function Int_div(x, y) {
    return Math.floor(x / y);
}
function Int_quot(x, y) {
    return Math.trunc(x / y);
}
// 0除算やオーバーフローはここでは無視する

さて、浮動小数点演算と言えば誤差です。この「浮動小数点演算による整数除算のエミュレート」は誤差の影響を受けないのでしょうか？

続きを読む →

LunarMLの進捗2022

この記事では、私が数年前から作っているStandard ML処理系「LunarML」の今年の進捗を振り返ります。

これまでの進捗報告記事は以下です：

続きを読む →

2^53+1 は素数か

ふと \(2^{53}+1\) が素数かどうか気になりました。

短い答え：No

Linuxだと factor コマンドで素因数分解できます。

$ factor $((2**53+1))
9007199254740993: 3 107 28059810762433

macOSだとHomebrewやMacPortsでcoreutilsを入れる必要があります。

筆者のMacには factor コマンドは入っていなかったので、最初はMaximaで確認しました：

$ maxima    
Maxima 5.45.1 https://maxima.sourceforge.io
using Lisp SBCL 2.2.9
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) factor(2^53+1);
(%o1)                        3 107 28059810762433

というわけで、 \(2^{53}+1\) は\[2^{53}+1=3\times 107\times 28059810762433\]と素因数分解でき、素数ではありません。

暗算でもできるのでは？

今回調べたいのは \(2^{53}+1\) という形の数です。ちょっと頭を使えば、この数が3で割り切れることがわかります：\begin{align*}2^{53}+1&=2^{53}-(-1)^{53}\\&=(2-(-1))(2^{52}+\cdots+2^{52-i}\cdot(-1)^i+\cdots+(-1)^{52})\end{align*}と因数分解できます。

一般化すると、\(2^{2m+1}+1\)の形の整数はすべて3で割り切れることがわかります。つまり、\(m\neq 0\)で\(2^{2m+1}+1\)が3よりも大きくなる場合はこの形の数はすべて合成数です。

もっと一般化

もっと一般に、\(2^n+1\)の形の整数が素数となるのは\(n=0\)または\(n=2^k\ (k\geq 0)\)の場合に限られます。

\(n=2^k(2m+1)\)とおくと、\begin{align*}2^n+1&=2^{2^k(2m+1)}+1\\&=\left(2^{2^k}\right)^{2m+1}+1\\&=\left(2^{2^k}\right)^{2m+1}-(-1)^{2m+1}\\&=\left(2^{2^k}-(-1)\right)\left(\left(2^{2^k}\right)^{2m}+\cdots+\left(2^{2^k}\right)^{2m-i}\cdot(-1)^i+\cdots+(-1)^{2m}\right)\\
&=\left(2^{2^k}+1\right)\left(\left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2m-1}+\cdots+\left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2(m-i)+1}+\cdots+\left(2^{2^k}-1\right)\cdot 2^{2^k}+1\right)\\
&=\left(2^{2^k}+1\right)\left(\sum_{i=0}^{m-1} \left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2i+1}+1\right)\end{align*}と因数分解できます。

\(k\geq 0\)なので、\(2^{2^k}+1\geq 3\)であり、最初の因数は非自明です。そして、2番目の因数に登場する\(2^{2^k}-1\)は1以上で、\(m\geq 1\)ならば2番目の因数も非自明です。

よって、\(2^{2^k(2m+1)}+1\)の形の数が素数となるのは\(m=0\)の場合に限ることがわかりました。

フェルマー数

\(2^{2^k}+1\)の形の数はフェルマー数と呼ばれています。\(k=0,1,2,3,4\)の場合はこれは素数となり、フェルマー素数と呼ばれています。

ところでなんで \(2^{53}+1\) を調べたかったのか

一部のプログラミング言語では、倍精度浮動小数点数型を唯一の数値型として提供しています。BigInt以前のJavaScriptや、5.2までのLuaなど。

こういう言語では、絶対値が\(2^{53}\)以下の整数は正確に表現できます。そして演算結果の絶対値がそれを超えると、丸めが発生して正しい答えが返ってきません。JavaScriptで試してみましょう：

$ node
Welcome to Node.js v17.9.1.
Type ".help" for more information.
> 2**53 - 1
9007199254740991
> 2**53
9007199254740992
> 2**53 + 1
9007199254740992
> 2**53 + 2
9007199254740994
> 2**53 + 3
9007199254740996

2**53 + 1 を表現できておらず、「表現可能な最も近い値のうち、仮数部の末尾が偶数な方」が表示されています（最近接偶数丸め）。

では、演算結果が「正確に表現できる範囲」を超えたかどうかはどうやったらわかるでしょうか？まず、演算結果の絶対値が\(2^{53}+2\)以上であれば間違いなく超えています。

では、演算結果の絶対値が\(2^{53}\)以下なら結果は正確と言えるでしょうか？否ですね。2**53 + 1 の演算結果は\(2^{53}\)以下であるにも関わらず、不正確です。

一方、演算結果の絶対値が\(2^{53}-1\)以下であれば結果は正確であることが保証されます。この範囲、\([-(2^{53}-1),2^{53}-1]\)はJavaScript界隈ではsafe integerと呼ばれています。

さて、筆者が作っているStandard ML処理系、LunarMLでもsafe integerに相当する整数型を提供できると便利です。提供するとするとビット数は符号ビットも含めて54ビット、 Int54 みたいなものになります。

ですが、Standard MLの固定長整数は2の補数表現を仮定しており、表現できる範囲は\([-2^n,2^n-1]\)の形である必要があります。これとsafe integerを比べると、\(-2^{53}\)がはみ出ます。

なので、LunarMLで Int54 を提供するには、演算結果が\(-(2^{53}+1)\)の場合を何らかの方法で検出し、オーバーフロー例外を起こさなければなりません。この時、\(2^{53}+1\)が素数だったなら乗算の場合に演算結果が\(-(2^{53}+1)\)になる可能性を考慮しなくてよかったのに、現実は残酷でした、という話です。