構造化プログラミングのobj.x()構文をSMALLTALK80言語はサポートしていなかった件

　「構造化プログラミング」の書籍に載っていたobj.x()の構文を、SMALLTALK80言語はサポートしていなかったことを、この記事で示す。

構造化プログラミング

　まず、75年に出版された『構造化プログラミング』*1に載っているソースコードを引用する。

class Gauss(n); integer n;

begin array W, X[1 : n];

    real procedure integral (f, a, b);

    real procedure f; real a, b;

(中略)

end of Gauss;

   ......

ref(Gauss) G5, G7;

   ......

G5 :- new Gauss(5); G7 :- new Gauss(7);

   ......

G5.integral(F, A, B)   ......  G7.integral(F, A, B)  ......

(『構造化プログラミング』p.207より引用)

SMALLTALK80言語

　続けて、SMALLTALK80言語のソースコードを抜粋してみよう。

Time now

Date today

Point x:100 y:150

Rectangle

     orgin:(Point x:50 y:50)

     corner:(Point x:250 y:300)

(『SMALLTALK-80 -言語詳解-』*2p.69より抜粋)

二つの言語の比較

　まず、SMALLTALK-80言語にobj.x()構文はどこにも存在していなかった。開発者のゴールドバーグが執筆した『SMALLTALK-80 -言語詳解-』を見る限り、.(ドット)で中間演算子のようにつなげて使うソースコードは見当たらなかった。

　一方で、「構造化プログラミング」の第三部で、上記のように、G5.integral(F, A, B)と書かれたソースコードが見つかった。

　ここで、「構造化プログラミング」第三部では次のような記述があるので、引用しておく。

　この小論では、プログラムを構造化するいくつかの方法を調べ、それらが概念の形成に関係していることを示す。

　とくにその構造化の機構を重視して、プログラミング言語 SIMULA 67 を用いることにする。

『構造化プログラミング』p.197より引用)

　このように、構造化プログラミングの例として、ダイクストラ達はSIMULA67言語を紹介したのである。このSIMULA 67言語がobj.x()のような構文をサポートしていたと考えらる。

　実際に、その後のソースコードでも似た文が登場する。

current.wait(Q)

(『構造化プログラミング』p.244より引用)

結論

　構造化プログラミングのobj.x()構文をSMALLTALK80言語はサポートしていないことが明らかとなった。このことは、言語の体系を考察する上で重要である。

*1:『構造化プログラミング』ダイクストラ/ホーア/ダール　共著、　野下/川合/武市　共訳、サイエンス社、1975年8月）

*2:『SMALLTALK-80 -言語詳解-』(Adele Goldberg、David Robson著、相磯秀夫訳、株式会社オーム社、1987年6月、ISBN 4-274-07325-4

構造化圏 - 圏論と構文論の対応

　ちょっと思いついたので備忘録に書いておく。

　フローチャートを圏とすると、文(statement)が対象であり、計算の順序が射であるような圏ができる。

　今、Algol60言語より前のブロックが存在しない疑似コードを次のように書いてみる。1行が文となる。

x = 12;

if x >0 : x = x + 1;

while x < 15 : x = x + 1;

そうすると、

文「x=12;」-> 文「if x >0 : x = x + 1;」-> 文「while x < 15 : x = x + 1;」

であり、このダイクストラ連接は合成射となる。

if文に着目すると、何もしなかった暗黙のelse文が挿入されるわけだから

前の文「x=12;」-> 文「if x >0 : x = x + 1;」-> 後の文「while x < 15 : x = x + 1;」

                  前の文「x=12;」  ->  後の文「while x < 15 : x = x + 1;」

となり、このダイクストラ選択は可換図式である。

　最後に、文「while x < 15 : x = x + 1;」に注目すると、結局のところ、一つの文をダイクストラ繰り返ししているわけなのだから、恒等射となる。

　ブロックはどうなるのかは調査中である。結論として、構文論と数学的構造は、意味論よりも深遠な関係にあるのではないかと思われる。

追記

暗黙のelse文がなくとも、if文と前後の文において、三角形のような可換図式が成立するので、訂正した。

BNW言語の解説 - EBNFのXML化(その3)

解説

　文字列の定義は省略する。なお、<name>...</name>のような文字列nameをタグ名という。

空白類文字

　「空白類文字」とは、複数の空白、改行文字、タブ文字などの文字列である。終端記号以外で使われるときには構文解析の対象にはならない。

記号

　「記号」とは、空白類文字と「"」とタグ名以外の文字列。終端記号と非終端記号の２種類がある。

終端記号

　「終端記号」とは、"と"で囲まれた記号であり、他の記号に置き換え不能である。

非終端記号

　「非終端記号」とは記号であり、他の記号に置き換えが可能である。

開始記号

　開始記号とは<開始記号>と</開始記号>で囲まれた構文(syntax)である。この構文を足がかりに、構文解析を行う。この構文内において、すべての非終端記号が別の記号に置き換えられたならば、構文解析は終了する。

　ただし、開始記号の要素が二つ以上あるときは、構文解析器(パーサ)は一つが終われば、別の開始記号の解析を始める。

連接

　「連接」とは、記号の連なりを示す非終端記号。このつながった連なりは<連接>と</連接>で囲んでおく。そして、囲まれた連なりにおいて、すべての非終端記号が別の記号に置き換わるまで解析が進んでいく。

選択

　「選択」とは複数の記号から選べることを示す非終端記号である。「|」をはさんだ二つ以上の記号が<選択>と</選択>で囲まれる。たとえば、二つの記号a,bから一つを選ぶときは「<選択>a|b</選択>」のように書く。

反復

　「反復」とは、0回以上の繰り返しを示す非終端記号。記号をB、空文字をεとおくと、<反復>B</反復>とは、

A=<選択>A B|ε</選択>

　となり、Bを0回以上反復させたことを意味する。

有無

　「有無」とは、ある記号が0回もしくは1回だけであることを示す。記号をA、空文字をεとおくと、

<有無>A</有無> = <選択>A|ε</選択>

である。

　これで、反復と有無の要素を使えば、空文字を使わずに済むようになる。

定義の要素

　「定義の要素」とは非終端記号の定義である。定義の要素の中にある名前要素には、非終端記号の形象を入れる。その名前要素の後ろには、置き換えるべき記号を並べておく。

参考資料

『ヴィルトのコンパイラ構成法』(ニクラウス・ヴィルト著、滝沢徹・牧野裕子訳、アジソン・ウェスレイ・パブリッシャーズ・ジャパン社、1997.11.28、ISBN4-7952-9706-1 C3055)

BNW言語の文法 - EBNFをXML化(続き)

BNW言語について

　前回の記事でEBNFをXML化したので、それを仮に「BNW言語」と名付けておく。このBNW言語はHTML言語を拡張したXMLである。

　さて、今回は、そのBNW言語の文法をBNW言語自身で記述する。ただし、HTML言語の文法についてはあらかじめ取り除いておく。

BNW言語の文法

<開始記号><連接>開始記号の要素 空白類文字 <反復>定義の要素</反復></連接></開始記号>
        
<定義><名前>開始記号の要素</名前>
            <連接>"&lt;開始記号&gt;"　構文　"&lt;/開始記号&gt;"</連接>
</定義>

<定義><名前>定義の要素</名前>
            <連接>"&lt;定義&gt;"　空白類文字　名前の要素　構文　"&lt;/定義&gt;"</連接>
</定義>

<定義><名前>名前の要素</名前>
            <連接>"&lt;名前&gt;"　空白類文字　文字列　空白類文字　"&lt;/名前&gt;"</連接>

</定義>

<定義><名前>構文</名前>
            <反復>空白類文字　"&lt;"　<選択>連接の要素|選択の要素|反復の要素|有無の要素|終端記号</選択>　空白類文字</反復>
</定義>

<定義><名前>連接の要素</名前>
            <連接>"連接&gt;"　<選択>構文|連接リスト</選択>　"&lt;/連接&gt;"</連接>
</定義>

<定義><名前>連接リスト</名前>
            <連接>文字列　<反復><連接>空白類文字　文字列</連接></反復></連接>
</定義>

<定義><名前>選択の要素</名前>
            <連接>"選択&gt;"　<選択>構文|選択リスト</選択>　"&lt;/選択&gt;"</連接>
 </定義>

<定義><名前>選択リスト</名前>
            <連接>文字列　空白類文字　<反復><連接>"|"　空白類文字　文字列</連接></反復></連接>
</定義>

<定義><名前>反復の要素</名前>
            <連接>"反復&gt;"　構文　"&lt;/反復&gt;"</連接>
</定義>

<定義><名前>有無の要素</名前>
            <連接>"有無&gt;"　構文　"&lt;/有無&gt;"</連接>
</定義>

<定義><名前>空白類文字</名前>
            <反復><選択>" "|"\n"|"\r\n"|"\t"|"　"</選択></反復>
</定義>

<定義><名前>終端記号</名前>
            <連接>"&quot;"　文字列　"&quot;"</連接>
</定義>

<定義><名前>文字列</名前>
            <連接>文字
                <反復>文字</反復>
            </連接>
</定義>

<定義><名前>文字</名前>
            <選択>アルファベット|ひらがな|カタカナ|漢字</選択>
</定義>

ヴィルト拡張バッカスナウア記法(EBNF)をXML化する

この記事の目的

　ソフトウェア開発者のために、EBNFをXML文書化するのが、今回の目的である。

EBNFとXMLについてのおさらい

拡張バッカスナウア記法(EBNF)とは

　拡張バッカスナウア記法(EBNF)とは、Algol60言語で採用されたバッカスナウア記法(BNF)をヴィルトが拡張したものである*1。形式言語の文法を記述したいときに使う。

拡張マークアップ言語(XML)とは

　拡張マークアップ言語(XML)とは、W3Cが提唱したマークアップ言語である。当初はISO SGMLのサブセット規格として出発した。

EBNFをXML文書に落とし込む

　簡単のため、HTML言語を拡張したものを「XML文書」として扱うよう約束しておく。そうすると、sample.xmlのような、ファイルの拡張子に「xml」を付けた文書のソースは次のようになる。

sample.xmlのソースコード

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja"><head>
 <title>EBNFをXML化</title>
    <link rel="stylesheet" href="style.css"/>
 <meta http-equiv="content-type" content="application/xml; charset=UTF-8"/>
</head>

<body>
 <h1>EBNFをXML化</h1>
    <section>
        <h2>文法</h2>
        <開始記号>
            <連接>主語　目的語　述語</連接>
        </開始記号>
        <定義><名前>主語</名前>文字列
        </定義>
        <定義><名前>述語</名前>文字列
        </定義>
        <定義><名前>目的語</名前>文字列
        </定義>
        <定義><名前>文字列</名前>
            <連接>文字
                <反復>文字</反復>
            </連接>
        </定義>
        <定義><名前>文字</名前>
            <選択>英字|ひらがな|カタカナ|漢字</選択>
        </定義>
        <定義><名前>英字</名前>
            <選択>"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"|"A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"</選択>
        </定義>
</section>
</body></html>

スタイルシートを用いる

　さらに、以下のようなstyle.cssというスタイルシートを作っておいて、sample.xmlと同じディレクトリ(フォルダ)に置いておく。

style.cssのソースコード

連接{display:inline;}
連接::before{content:"("}
連接::after{content:")"}
選択{display:inline;}
選択::before{content:"("}
選択::after{content:")"}
反復{display:inline;}
反復::before{content:"("}
反復::after{content:")*"}
有無{display:inline;}
有無::before{content:"("}
有無::after{content:")?"}
開始記号{display:block; color:blue;}
定義{display:block;}
名前{display:inline;}
名前::after{content:":="}

ブラウザで表示させる

　今回はFirefox145.0.1 (Win11 HOME)を用いて、sample.xmlをローカルで表示させたところ、

            主語　目的語　述語        
       
主語:=文字列        
       
述語:=文字列        
       
目的語:=文字列        
       
文字列 :=           ( 文字                 (文字)*)                    
       
文字:=             (英字|ひらがな|カタカナ|漢字)

英字:=             ("a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"|"A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z")

と表示された。 

注意点

.htmlのように拡張子が「html」だと失敗するので、xmlの拡張子を付けるようにしなければならない。

課題

　まだ、スタイルシートを使った装飾という点では、問題がある。例えば、開始記号は青い文字色で表現しているだけである。しかし、DOMで処理させればコンパイラの処理も楽になるのではないかという期待もある。EBNFとの比較と解説はいずれ時間があるときに書いていく。

*1:『ヴィルトのコンパイラ構成法』(ニクラウス・ヴィルト著、滝沢徹・牧野裕子訳、アジソン・ウェスレイ・パブリッシャーズ・ジャパン社、1997.11.28

concurrentの訳についてドイツ語と英語以外の言語は「競争相手、ライバル、競合他社」という意味で、「同時に動く」という意味はないよ

オランダ語のconcurrentは「競争相手」

　前回の記事で、オランダ語の「concurrent」の意味を調べた。

ダイクストラの言う「concurrent programming」は「競合プログラミング」と訳すべき - オランダ語でconcurrent(コンカレント)の意味は「競争相手」 - dhrnameのブログ

オランダ語以外の言語について

　今回は、DeepL翻訳で他の言語についても調べていたのだが、以下の言語では、concurrentに英語やドイツ語の「同時に動く」や「並行」という意味はなかった。

• デンマーク語
• ノルウェー語

オランダ語と同様に、concurrentは「競争相手」などの意味を持つのである。

科学者たちの出自から分類する

　以前、Wikipediaを用いて科学者の出身国をまとめたことがあった。

構造化プログラミングに関わった人たちの出身国をWikipediaで調べてみた - dhrnameのブログ

　これらが事実だとすると、母国語の観点から、次のような二つの流れになる。

concurrentを「競争相手、ライバル、競合他社」という意味でとらえる（「並行」という意味にはとらえない)グループ

• エドガー・ウィベ・ダイクストラ (出身国：オランダ）
• オーレ＝ヨハン・ダール （ノルウェー）
• クリステン・二ゴール(ニガードとも表記。ノルウェー)
• ピーター・ナウア（デンマーク）
• ブリンチ・ハンセン（デンマーク、「Concurrent Pascal」言語の開発者)
• Theodorus・Jozef・デッカー (Dirk・デッカー。オランダ）

concurrentを「並行」、「同時に動く」という意味にとらえる(「競争相手、ライバル、競合他社」という意味でとらえない)グループ

• チャールズ・アントニー・リチャード・ ホーア（イギリス）
• ニクラウス・ヴィルト （スイスのドイツ語圏）
• バーバラ・リスコフ（アメリカ、「構造化プログラミング」から派生した「抽象データ型」の提唱者）

まとめ

　こうした点から、concurrentは北欧を中心とした出身者の科学者が使用する際には、「競合(英語でrace)」という訳がふさわしい。もちろん、DeepLやWikipedia以外のソースを調べる課題をクリアした後での話である。

構造化のダイクストラ連接 (concatnation)は入れ子 (nest)構造。だから、is-a関係でもhas-a関係でもないよ

構造化のダイクストラ連接 (concatnation)は入れ子 (nest)構造

まず、連接(concatnation)の疑似コードを次のように書いてみる。

int a = 5;

int b = a + 10;

int c = b + 12;

これは次のような入れ子(nest)構造と等価である。

{

    int a = 5;

    {

        int b = a + 10;

        {

            int c = b + 12;

        }

    }

}

ダール・オブジェクトクラスの疑似コード

SIMULA67言語のbeginとendを{}に変えた疑似コードを書いてみる。

class SuperClass() {int a = 5;}

SuperClass, class SubClass() {int b = a + 10;}

subClass, class SubSubClass() { procedure method() {int c = b + 12;} }

ref(SuperClass) obj0 :- SuperClass();

ref(SubClass) obj1 :- SubClass();

ref(SubSubClass) obj2 :- SubSubClass();

obj2.method();

そうすると、構造化プログラミングにより、

SuperClass:{

    int a = 5;

    SubClass:{

        int b = a + 10;

        SubSubClass:{

            procedure method() {

                int c = b + 12;

            }

        }

    }

}

ref(SuperClass) obj0 :- SuperClass();

ref(SubClass) obj1 :- SubClass();

ref(SubSubClass) obj2 :- SubSubClass();

obj2.method();

これらのクラスの関係は、SuperClass >= SubClass >= SubSubClass の関係となる。つまり、is-a関係でもなくhas-a関係でもなく、入れ子となった階層(hierarchy)構造化の関係となるのである。