Easy-Lang: Evangel Quiwaのプログラミング言語
Easy-Lang: Evangel Quiwa's Programming Language (github.com)
要約
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を定義しないプログラムは拒否されます。