HN 日本語サマリー

← 一覧へ戻る
プログラミング

Easy-Lang: Evangel Quiwaのプログラミング言語

Easy-Lang: Evangel Quiwa's Programming Language (github.com)

5 pointsby jjuliano0 コメント

要約

Easy-Langは、Evangel P. Quiwa氏が著書『Data Structures』で紹介した教育用プログラミング言語の記法を解釈・実行するインタプリタです。GitHubリポジトリから簡単にインストールでき、コードの実行だけでなく、ステップごとの実行トレースや面接用の説明生成機能も備えています。この言語は、基本的な制御構造、配列、構造体、手続きなどをサポートしています。

全文翻訳

easy-lang

Evangel P. Quiwa著『Data Structures』(Manila: Electronics Hobbyists Publishing House, 2007)に記載されている教育用記法であるEasyのインタプリタです。Quiwaは、この記法をEllis HorowitzとSartaj Sahni著『Fundamentals of Data Structures』(Computer Science Press, 1976)のpp. 8–15にあるSPARKS、および1970年代半ばにフィリピン大学でOscar Ibarraが教えたデータ構造コースに遡ります。

このプログラムは、それらのステートメント形式を実行します。教科書は含まれていません。examples/内の例は、このインタプリタのために書かれました。

インタプリタはjjuliano/easy-langです。MITライセンスで、著作権はJoel Bryan Julianoにあります。15回のセッションの手続きはjjuliano/datastructuresの各セッションのeasy/フォルダにあります。このリポジトリの例は、より小さなチェックです。

インストール

一度インストールしてください。HomebrewのPythonは、この行を拒否し、externally-managed-environmentと報告します。

python3 -m pip install --user git+https://github.com/jjuliano/easy-lang.git

--break-system-packagesは渡さないでください。代わりにインストーラーを使用してください。これは~/.easy-langにプライベート環境を構築し、Easyをこのpython3にリンクします。Homebrewのパッケージはそのままです。

curl -fsSL -A easy-lang https://raw.githubusercontent.com/jjuliano/easy-lang/main/install.py | python3

お使いのマシンでコマンドがpython3ではなくpythonの場合、そのインストーラーをpythonにパイプしてください。

実行

インストール後、任意のディレクトリからファイルまたはリンクを実行します。GitHubのブロブリンクはファイルページです。インタプリタはファイル自体を読み込みます。

python3 -m easy insertion.easy
python3 -m easy https://github.com/jjuliano/datastructures/blob/main/session03-algorithms/easy/insertion.easy
python3 -m easy https://github.com/jjuliano/datastructures/blob/main/session03-algorithms/easy/search.easy

insertionプログラムは1 2 2 3を出力します。searchプログラムは3、次に0を出力します。インストールをスキップした場合、python3 -m easyはNo module named easyで停止します。

各ステップを表示

ファイルまたはリンクの前に--explainを付けてください。-xも同じフラグです。プログラムの行のみが必要な場合は、これを省略してください。

python3 -m easy --explain https://github.com/jjuliano/datastructures/blob/main/session03-algorithms/easy/search.easy
python3 -m easy -x insertion.easy

ステップは標準エラー出力に先に表示されます。各ステップは+で始まります。手続き内のステップは、その手続き名のインデントの下に表示されます。←は値を格納し、→はそのステップが生成した値です。whileとcaseは→ trueまたは→ falseで終わります。プログラム自身の行は標準出力に続きます。

+ procedure MAIN
+   procedure Find(a=array, n=5, key=7)
+     lo ← 1
+     hi ← n → 5
+     while (lo ≤ hi) → true
+     mid ← floor(((lo + hi) / 2)) → 3
+     case (key = a(mid)) → true
+     return 3
+   output Find(row, 5, 7) → 3
3
0

最後の2行がプログラムの出力です。3の上のステップにはreturn 3と表示されています。コマンドがusage:と表示されて停止した場合、インストーラーを再度実行してください。

面接用に説明する

--interviewはプログラムを実行しません。面接で提示できる短い箇条書きリストを出力します。

  • それは何であるか
  • 主要なステップ(ステップがすでに独立した文である場合は、各ステップのサブ箇条書き)
  • 時間計算量と空間計算量
  • 注意点
python3 -m easy --interview examples/stack.easy
python3 -m easy --interview examples/paths.easy
python3 -m easy --interview https://github.com/jjuliano/datastructures/blob/main/session04-stacks/easy/pile.easy

このツールは、このリポジトリの例のカタログと、データ構造の教科書のセッションリストからプログラムを検索します。プログラムは、¤ Interview:で始まるコメントに独自の解説を含めることもできます。

このリポジトリをクローンした場合、クローン内で実行すれば、インストールせずに同じコマンドが機能します。

python3 -m easy examples/gcd.easy
python3 -m unittest tests.test_easy

標準入力がターミナルでない場合、inputはその空白区切りのトークンを読み込みます。Pythonからは、easy.run(source, inputs=['2', 'oak'], explain=True)が同様のことを行います。.outputはプログラムの行、.traceはステップ、.valueはMAINが返した値、.globalsはグローバルセルを保持します。

記法

プログラムは1つ以上の手続きで構成されます。実行はMAINから開始されます。print形式とタイプライター形式は同じ言語です。

middle ← floor((lower + upper) / 2)

<-は←と同じ矢印です。*、<=、>=、<>、!=は、×、≤、≥、≠のタイプライター表記です。コメントは¤から行末までです。nil、lambda、Λはヌルアドレスです。

/は実数除算です。整数演算にはmodとfloor(⌊ ⌋、ceil、⌈ ⌉、log2も含む)を使用します。^はべき乗で、右結合性があります。そのため2^3^2は512です。先頭のマイナスは全体のべき乗に適用されるため、-2^2は−4です。notは=よりも優先順位が高く結合します。andとorは早期終了し、関係演算子よりも優先順位が低く結合します。関係演算子は連鎖しません。

if cond then S1
else S2

S1とS2は1つのステートメント、または[と]で囲まれた複数のステートメントです。elseは最も近いifに属します。endifはありません。

case
: cond1: S1
: cond2: S2
: else: S3
endcase
while cond do
  S
endwhile

repeat
  S
until cond

loop
  S
forever

for i ← start to finish by step do
  S
endfor

byはデフォルトで1であり、負の値も可能です。start、finish、stepは、エントリー時に一度だけ読み取られます。正のステップでは、変数がfinish以下である間実行されます。exitは最も内側のループを終了します。go to labelは同じ手続き内のlabel:にジャンプします。stopはプログラムを終了します。returnなしでendに到達すると、nilが返されます。

outputは1行を出力します。項目はスペースまたはカンマで区切られ、文字列は引用符なしで表示されます。inputは次のトークンを変数に読み込みます。input row(1:m)は、同じステートメントの前の名前が読み取られた後に、そのスライスを埋めます。

array row(1:n), grid(1:n, 1:m)

上限のみを指定した場合、下限は1とみなされます。したがって、array a(n)はa(1:n)となります。設定されていないセルはnilです。範囲外のインデックスはエラーです。すでに配列であるパラメータの宣言は、その配列を文書化するものであり、2番目の配列を割り当てるものではありません。

node(info, link)
call GETNODE(p)
info(p) ← "oak"
link(p) ← nil
call RETNODE(p)

field(address)はそのノード内のセルです。アドレスは1から始まる整数です。プールはプログラムがpool Nと指定しない限り、1024ノードを保持します。GETNODEの失敗はプログラムを停止させます。同じ名前の手続きがプログラムで定義されている場合、組み込みのもののかわりに使用されます。

パラメータは参照渡しされます。call Swap(x, y)は、呼び出し元のセルを共有します。call Move(n - 1, src, dst, spare)は、式n - 1を一時セルにコピーするため、呼び出し元のnは変更されません。新しい名前に代入すると、グローバル変数が作成されます。パラメータ、開かれた構造体フィールド、または手続き内で宣言された配列は、同じ名前のグローバル変数を隠します。

書籍の構造S = [S(1:n), top]は、ここでは宣言と変数として記述されます。

structure Pile(n) = [slot(1:n), top]
Pile pile(4)
call Push(pile, x)

pileを渡すと、呼び出し先でslot、top、nが開かれます。外部からは、top(pile)がスカラーフィールドです。1つの配列を持つ構造体は直接インデックス指定できます。リンクされた形式は次のとおりです。

structure Chain = [(info, link), head]

括弧内の名前はノードレイアウトです。

手続き名はスペースを含むことができます(例: end Add One)。キーワードは大文字小文字を区別しません。MAINを定義しないプログラムは拒否されます。