問題タブ [language-theory]

私は、意図的に (設計により) 同じコードを 2 回評価できない (つまり、ループできない) 専用の「プログラミング言語」を作成しました。基本的に、フローチャートの各要素が同じデータセットに対して異なるテストを実行する条件である、フローチャートのようなプロセスを説明するために作られています (変更することはできません)。ブランチは分割およびマージできますが、循環することはありません。フローチャートはそれ自体にループバックできません。分岐の最後に到達すると、現在の状態が返され、プログラムが終了します。

書き留めると、典型的なプログラムは表面的には純粋関数型言語のプログラムに似ていますが、再帰の形式が許可されておらず、関数が何も返すことができないという点が異なります。関数を終了する唯一の方法は、別の関数を呼び出すか、現在の状態を返す一般的な exit ステートメントを呼び出すことです。同様の効果は、構造化プログラミング言語を使用してすべてのループ ステートメントを削除するか、「非構造化」プログラミング言語を使用して、コード内で逆方向に進む goto または jmp ステートメントを禁止することによっても実現できます。

ここで私の質問は次のとおりです。そのような言語を簡潔かつ正確に説明する方法はありますか? 私は正式な CS のバックグラウンドがなく、オートマトン理論や形式言語理論に関する記事を理解するのが難しいので、少し途方に暮れています。私は自分の言語がチューリング完全ではないことを知っており、苦労して、自分の言語がおそらく「通常の言語」(つまり、読み取り専用のチューリング マシンによって評価できる言語) として分類できることを確信することができました。もっと具体的な用語はありますか？

一般的なプログラミングの概念に精通しているが、正式な CS のバックグラウンドを持っていない聴衆にとって、用語が直感的に理解できる場合はボーナス ポイントです。また、そのような言語を評価する特定の種類の機械または自動機械があれば、ボーナス ポイントも得られます。そうそう、データ ストリームを評価しているわけではないことに注意してください。すべての要素は、入力データの完全なセットに (読み取り専用で) アクセスできます。:)

関係を管理することには一種の美しさがあります。次の例を検討してください。

1. 原子は亜原子粒子で構成され、分子は原子で構成され、細胞は分子で構成され、器官は細胞で構成され、人は器官で構成され、社会は人で構成されます。
2. 囲碁のゲームの複雑な戦略は、生き残るために「両目」で構造を作る必要性に基づいています。ただし、「両目」のことはルールに記載されていませんが、それ自体が囲碁の非常に単純なルール。
3. Conwayのs_Game_of_Lifeのチューリング完全性は、グライダー、銃、宇宙船の観点から証明できます。これらは、オンとオフの概念と非常に単純なルールのセットに基づいています。

すべての場合において、最小限のオブジェクトのセットと最小限のルールのセットは、最終的に非常に複雑な構造になります。

私の最初の質問： OOP言語を構築するために使用できるプログラミング「オブジェクト」と「ルール」の小さくてミニマルなセットの概要を説明することは可能ですか？

さて、賢いコンピューター科学者はおそらくルール110のチューリング完全性を指摘し、これがあなたが必要とするすべてであると言うでしょう！しかし、それは私が探しているものではありません。むしろ、明確に定義されていない質問を投げかけるリスクを冒して、オブジェクト指向プログラミング言語に組み込むことができる最も単純で人間が理解できる概念は何ですか？

私が欲しいものを示唆する悪い不完全な例については、3つの概念オブジェクトを定義します：参照、関数、および情報ホルダー。次に（レベル2？）、他の情報フォルダーへの参照を介して他の情報を保持する情報ホルダーとなる構造を定義します。初歩的なクラス（レベル3？）は、関数への参照で構造を拡張しますが、プライベート関数とパブリック関数の概念を処理するには、追加の構造を構築する必要があります。最終的には、基本的な概念のみに基づいて構築されたフル機能のOOP言語に到達する必要があり、どこにも不正行為はありませんでした。ハードコーディングの最適化またはマシンコードとの構文ソルトによる。そして理想的には、最終結果は依然として魅力的で読みやすいコードです。

私の2番目の質問：すでにこれに近づいているOOP言語はありますか？

関連するいくつかの 質問を読んで、HTMLの理論的な性質について考えさせられました。

ここでは、XHTMLのようなコードについて話しているのではありません。私はこのクレイジーなマークアップのようなものについて話している、それは完全に有効なHTML（！）

では、SGMLがここに注入する非常に複雑なことを考えると、HTMLは文脈自由言語ですか？とにかくそれは形式言語ですか？文法で？

HTML5はどうですか？

_{私は形式言語の概念に慣れていないので、ご容赦ください。そして、はい、私はウィキペディアの記事を読みました;）}

ステートメントの後にセミコロンが必要であることは知っていますが（Java、C ++、および同様の言語について話しています）、角かっこの後には必要ありません。なぜそうなのか？

理由は何ですか？つまり、この背後にある理論は何ですか？

メインの Javascript インタープリターには最適化が組み込まれていますか? 私は次のような非常に単純なケースを考えています

少なくとも3つを見つけたい数字のリストがあります...これは例です

SQLデータベースに（たとえば）の形式で多数の数字のリストがあります

etc etc 基本的には 0 から 99 までの 6 つの乱数です。

ここで、指定された一連の数字のうち少なくとも 3 つが発生する文字列を見つけたいと考えています。例えば：

与えられた: 01-02-03-10-11-12 は、それらの数字を少なくとも 3 つ含む文字列を返します。例えば

これに一致するアルゴリズムまたは正規表現が存在する可能性があると考えています... しかし、コンピューター サイエンスの教科書の経験が不足しているため、つまずいていると思います。

いいえ、これは宿題の質問ではありません。これは実際のアプリケーション用です。

私はルビーで開発していますが、言語の回答をいただければ幸いです

次の文法があるとしましょう。

その文法がϵ関与していなかった場合、私は次のような最初の状態を構築します。

しかし、ϵシンボルはどうですか？含める必要があります：

それも？

もしそうなら...次の状態を作成するとき...私はGOTO(Io,ϵ)その最初の状態であるIoである必要がありますか？

接尾辞から中置へのコンバーターを作成しようとしていますが、接尾辞式の文法を作成できません。私もしばらくの間それを探していましたが、成功しませんでした。

有効な接尾辞式を認識するためにどの文法を使用できますか？

必要なトークンは、、、、numberおよび（pow ）です。+*^

Pythonについて私が尊敬していることの1つは、可変型と不変型の違いです。Pythonに来る前にcでプログラミングをしていたので、Pythonがcで私を怒らせるポインター逆参照のすべての複雑さを簡単に取り除くことができることに驚きました。Pythonでは、すべてが期待どおりに機能し、可変/不変の区別がその中で重要な役割を果たしていることにすぐに気付きました。

もちろん、まだいくつかのしわがあります（可変関数の引数のデフォルトが注目に値する例です）が、全体として、可変/不変の区別は、変数とその値が何であるか、およびそれらがどのように動作するかという問題を大いに明確にすると思います。

しかし、それはどこから来たのでしょうか？私は、GvRがこの区別を思いついた最初の人ではなく、Pythonがそれを使用した最初の言語ではなかったと仮定する必要があります。私は、この概念を使用した初期の言語と、それに関する初期の理論的議論について聞くことに興味があります。

同じ数の部分文字列「ab」と「ba」を持つアルファベット「a、b、c」上のすべての文字列の言語は規則的ですか？

答えはノーだと思いますが、正式なデモンストレーションでなくても、正式なデモンストレーションを行うことは困難です。

これにアプローチする方法について何かアイデアはありますか？