dhrnameのブログ

プログラミング関連を語るよ

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

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

　フローチャートを圏とすると、文(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を「並行」、「同時に動く」という意味にとらえる(「競争相手、ライバル、競合他社」という意味でとらえない)グループ
  • チャールズ・アントニー・リチャード・ ホーア（イギリス）
  • ニクラウス・ヴィルト （スイスのドイツ語圏）
  • バーバラ・リスコフ（アメリカ、「構造化プログラミング」から派生した「抽象データ型」の提唱者）

まとめ

　こうした点から、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)構造化の関係となるのである。

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

オランダ語のConcurrentの意味

WordReference.comによると、「concurrent」はオランダ語で「競争相手、ライバル、競合他社」を意味する。concurrentの意味はオランダ語で「競争相手」、英語で「同時に起きる」と異なっている。

www.wordreference.com

念のため、DeepL翻訳やAI(Copilot)でも調べたが、同じ意味だった。ちなみに、「concurreren」はオランダ語で「競争する」という意味がある。

ダイクストラはオランダ出身

 次のIEEEのサイトによれば、ダイクストラはオランダ(netherlands)のロッテルダム出身である。

www.computer.org

　よって、ダイクストラが述べている「Concurrent programming」*1とは、「競合プログラミング」と訳すべきである。

　彼が英語*2とオランダ語の違いを理解できなかったし、イギリス出身のホーアなど、非オランダ語圏の他の科学者たちも気づけなかったからだ。

*1:「Solution of a problem in concurrent programming control」E. W. Dijkstra著、Communications of the ACM, P.569 https://dl.acm.org/doi/10.1145/365559.365617

*2:英語のconcurrentには競争相手という意味はなく、「同時に起きる」という意味がある