Zenn
📕

小さなコンピュータ入門

2023/12/14に公開
#
uec
#
comlit
tech
この記事はUEC 2 Advent Calendar 2023 14日目の記事です。

https://adventar.org/calendars/8704

昨日のUEC Advent Calendarの記事はもっちゃんさんの「モチ娘、サークルをUEC大学公認まで育成ダービーの話。」でした。奇しくも去年の調布祭で東方サークルを訪れていたのですが、その裏の苦労が身に染みて感じました。私もサークル運営に携わっている身ですので、参考にしたい点が多くありました。

その2の方は、VIPERさんの「オタク寝ろ~ポケモンスリープで睡眠を改善した話~」でした。ポケモンスリープの上手な使い方だけでなく、いい睡眠の取り方に関する知見も紹介されていて、非常に教育的な記事でした。睡眠の取り方について深く考えたことがなかったので、勉強になりました。

導入

弊学の某講義では、プログラミングの導入として、小さなコンピュータ(以下SCS)という独自のアセンブラライクな言語を扱います。しかし、SCSの厳密な仕様については、あまり言及されることはありません(授業内で話すには細かすぎるためですが)。また、解説記事もなぜか見つかりませんでした。そこで、この記事ではSCS初学者のために、私の理解の範囲内でその仕様や便利なイディオムなどを紹介します。

言い訳タイム
私はこの講義まで(それ以降も)アセンブリ言語を触ったことがなかったので、有識者にとっては退屈な内容や正確性、一般性に欠ける議論になるかもしれませんがご了承ください。アセンブリ言語の話とは被らないように意識はしておりますが、一学生の開拓として見ていただけるとありがたいです。

この記事の構成について

この記事は、昨日のアドカレその1と同じくクソ長い記事です。ご注意ください。次の3部構成となっております。

  1. SCSマニュアル
  2. イディオム
  3. SCSのTips

上の方は基礎的な内容なので、すこし難しいです。逆に、下の方は応用的な内容なので、触ったことがある人にとってはとっつきやすいと思います。理解度に合わせて好きな順番で読んでいただければと思います。

環境

開発環境

シンタックスハイライトが作りやすそうだったので、Sublime Text 3を用いました。

シンタックスの設定ファイル

以下のファイルをSublimeTextのPagckages/User/配下においてください。

small_computer.sublime-syntax
%YAML 1.2
---
# See http://www.sublimetext.com/docs/syntax.html
file_extensions:
  - scs
  - scsa
name: SmallComputer
scope: source.smallcomputer
contexts:
  main:
    # Strings begin and end with quotes, and use backslashes as an escape
    # character
    - match: '\b(nop|stop|load|loadx|store|storex|add|sub|iload|iadd|isub|ifz|ifnz|ifp|ifn|jump|neg)\b'
      scope: keyword.control.c

    # Comments begin with a '//' and finish at the end of the line
    - match: '#'
      scope: punctuation.definition.comment.example-c
      push: line_comment

    # Keywords are if, else for and while.
    # Note that blackslashes don't need to be escaped within single quoted
    # strings in YAML. When using single quoted strings, only single quotes
    # need to be escaped: this is done by using two single quotes next to each
    # other.
    # - match: '\b(if|else|for|while)\b'
    #   scope: keyword.control.example-c

    # - match: '\b#.+$\b'
    #   scope: comment.line

    # Numbers
    - match: '\b(-)?[0-9.]+\b'
      scope: constant.numeric.example-c

    - match: '\b[a-z|A-Z|0-9]+?: \b'
      scope: markup.bold

    - match: '\b[a-z|A-Z|0-9]+[^: ]\b'
      scope: variable.variable


  # double_quoted_string:
  #   - meta_scope: string.quoted.double.example-c
  #   - match: '\\.'
  #     scope: constant.character.escape.example-c
  #   - match: '"'
  #     scope: punctuation.definition.string.end.example-c
  #     pop: true

  line_comment:
    - meta_scope: comment.line.example-c
    - match: $
      pop: true

また、このような開発は何らかのファイルとして編集したいですが、(おそらく)先駆者がいなかったため、拡張子を.scsと定めました。

開発補助ツール

一般的なプログラミング言語には、コメントという重要な機能があります。これは、指定した部分を実行しないという機能で、メモなどを書くのに用います。
しかし、SCSにはコメント機能が存在しません。そのため、.scsファイル上でコメントを使うためのトランスパイラを作成しました。#から行末までが削除されます。

https://gist.github.com/kanaru0928/1119d957e83f2783ef0994e98f4fdb8e

作成した.scsファイルをPythonファイルにD&Dすることで、公式環境で実行可能な.scsaファイルが生成されます。なお、コメントだけでなく、インデントも削除してくれます。

実行環境

公式が用意している実行環境を使いたいと思います。「site:uec.ac.jp a small computer simulator」と検索すると出てくると思います。もちろん、当該科目履修者の方はMoodleのリンクでも構いません。

公式の実行環境では500行以上のコードが実行できません。そのため、それ以上のコードを書くには次の方法で500行の上限を突破する必要があります。

  1. ソースコードの89行目～136行目(run関数とstep関数)をコピー
  2. run関数2行目(91行目だった部分)とstep関数1行目(99行目だった部分)の500を十分に大きな値に変更(推奨は65535)
  3. コンソールに貼り付け

SCSマニュアル

用語の定義

ここでは、これから出てくる用語の定義を行います。公式の用語と合わせる努力はしていますが、一部異なる場合があります。

プログラム(Program)

実行画面に「program」として表示されている部分。命令と値(10進法)を書くことができます。

メモリ(Memory)

実行画面に「result」として表示されている部分。値が配列の形で格納されており、内容は16進法で表示されます。実体はJavaScriptの配列です。

アドレス(Address)

実行画面に「addr」として表示されている部分。メモリ上の場所(何番目など)を指す数値です。画面には20までしか表示されていないですが、20までしか存在しないというわけではないです。また、数値ではなくラベルによって表現することも可能です。実体はJavaScriptのnumberです。

アキュムレータ(Accumulator)

実行画面に「Acc」として表示されている部分。プログラムから値を操作できます。計算などのために、一時的に値を保存するのに使います。実体はJavaScriptのnumberです。「Acc」と略します。

インデックス(Index)

実行画面に「Idx」として表示されている部分。プログラムから値を操作できます。主にxがつくの命令で、アドレスを指すために使います。実体はJavaScriptのnumberです。「Idx」と略します。

値(Value)

メモリ上の数値のこと。

ラベル(Label)

アドレスに対してつけられる名前。命令内でアドレスを指定するのに使えます。ラベルは次の条件を満たす必要があります。

  • ラベル名はアルファベットから始まる
  • ラベル名アルファベットと数字のみで構成される
  • ラベル名は固有の値でなければならない

命令(Operator)

命令一覧にあるもの。命令文中で使用することで、その命令を表す値が対応するアドレスに入ります。

プログラムカウンタ(Program Counter)

実行しているメモリのアドレス。実行すると0が入り、命令文を処理するごとに1ずつ増えていきます。「PC」と略します。

プログラムの文法

プログラムの1行は、命令文か10進法の数値を指定することができます。

命令文は、ラベル: 命令 オペランドの形で表されます。オペランドとは、命令に対して渡すことのできる値です(addならAccに足す値など)。オペランドはラベル名か数値を入力します。

  • 先頭のラベルは必須ではありません
  • オペランドは入力しないと数値0と解釈されます
  • オペランドに数値を入れると値指定、文字列を入れるとラベル指定と解釈されます

10進法の数値は、ラベル: 数値の形で表されます。命令文と同様、ラベルは省略可能です。実行すると、数値の部分に指定した数値がそのまま値としてメモリに入ります。

命令一覧

命令 16進(値指定) 16進(ラベル指定) 動作
nop 00 01 何もしない。
stop 00 01 実行を終了(どこかで終了しないとエラー)。
load 04 05 Accに値を代入。値指定の場合はその値、ラベル指定の場合はそのアドレスの値を代入。Idxが0の時のloadxに相当。
loadx 06 07 Accに値を代入。値指定の場合はIdxに値を足したもの、ラベル指定の場合はそのアドレスからIdx進んだ場所の値を代入。
store 08 09 Accの値をメモリに格納。値・ラベル指定問わずそのアドレスが格納先。Idxが0の時のstorexに相当。
storex 0a 0b Accの値をメモリに格納。値・ラベル指定問わずそのアドレスからIdx進んだ場所が格納先。
add 0c 0d Accに値を加算。値指定の場合、加数はその値。ラベル指定の場合、加数はそのアドレスの値。
sub 0e 0f Accから値を減算。値の指定方法はaddと同様。
iload 10 11 Idxに値を代入。値の指定方法はaddと同様。
iadd 12 13 Idxに値を加算。値の指定方法はaddと同様。
isub 14 15 Idxから値を減算。値の指定方法はaddと同様。
ifz 16 17 Accが0の時、PCを指定したアドレスに移動。値を入れるとアドレスとして解釈される。ラベル指定の場合は、移動先はそのラベルのついたアドレス。
ifnz 18 19 Accが0でない時、PCを指定したアドレスに移動。移動先の指定はifzと同様。
ifp 1a 1b Accが正の時、PCを指定したアドレスに移動。移動先の指定はifzと同様。
ifn 1c 1d Accが負の時、PCを指定したアドレスに移動。移動先の指定はifzと同様。
jump 1e 1f PCを指定したアドレスに移動。移動先の指定はifzと同様。
neg 20 21 Accの値の符号を反転。

処理の流れ

この言語の本質はプログラムは全てメモリ上の「値」として管理されるということです。
入力されたプログラムは、実行ボタンを押すと次のように処理されます。

  1. プログラムが値に変換され、メモリの対応するアドレスに格納される。このとき、空行は無視される。変換規則は命令一覧のコードの通り。
  2. メモリのアドレス0から順に数値が読み込まれ、プログラムとして解釈された後に実行される。
命令文と16進の変換規則

実行すると命令文が数値に変換されます。規則は次の通りです。
[命令の16進2桁][オペランドのアドレスor値4桁]
ただし、16進法です。
例えば、

hex_sample.scs
load 140

というコードは16進数04008cに変換されます。命令文はloadの値指定(04)なので上2桁が04、指定したオペランド140の16進表記は8cなので、下4桁が008cとなります。

また、オペランドにラベル名を指定した場合は、そのラベルが置かれているアドレスが数値として下4桁に書き込まれます。

メモリについて

アドレスを指定する際は、(通常)ラベル名を使う必要があります。

label_sample.scs
load Data
stop
Data: 1
# 実行結果：Acc→1

また、loadx、storexを使うことで、指定したアドレスからIdx番目の値にアクセスできます。

x_sample1.scs
load 100
iload 2
loadx Data
stop
Data: 10
20
30
40
# 実行結果：Acc→30

この記事内では、便宜上、数を0番目から数えることとします。上の例では、Dataアドレスから数えて2番目の値である30が取り出されています。

ここで、次のプログラムを実行するとどうなるでしょうか。

x_sample2.scs
load 100
iload 4
storex Data
stop
Data: 10
20
30
40

本来であればDataから4番目の領域は何もないはずですが、SCSでは次のように書き込むことができます。
メモリ領域外への書き込み
赤線の場所は本来領域外だが、確かに100(0x64)が書き込まれている。

この仕様は、JavaScriptの配列が領域外への書き込みを許可していることに起因しています。

この仕様のおかげで、メモリ上でプログラム領域と記憶領域を分けて考えられます。

イディオム

以上の仕様を踏まえ、SCSで使えるイディオムを紹介します。

条件分岐

if_sample.scs
ifp Continue
  # 処理
Continue: nop

1行目の条件を満たさないときに処理を実行します。

比較

compare_sample.scs
load X
sub Y

Accは次のようになります。

条件 Acc
X = Y 0
X > Y >0
X < Y <0

繰り返し

do-while型

条件を満たす間、繰り返します。判定は処理が終わってから行います。

dowhile_sample.scs
Loop: nop
  # 処理
# 条件
ifX Loop

ifXはifzなど条件でPCを動かす命令のいずれかを表します。

while型

条件を満たす間、繰り返します。判定は処理の前に行います。

while_sample.scs
Loop: nop
# 条件
ifX LoopRet
  # 処理
jump Loop
LoopRet: nop

for型

処理をN回繰り返します。アドレスIには何回目のループかが入ります(0スタート)。

for_sample.scs
load 0
store I
Loop: load I
sub N
ifz LoopRet
  #処理
load I
add 1
store I
jump Loop
LoopRet: nop

I: 0

何回目のループかという情報をIdxではなくメモリ上に保存しておくことで、ネストに対応できる、ループ内でIdxが使用できるなどのメリットが生まれます。

サブルーチン

処理をサブルーチンに分割します。ここでのサブルーチンは引数を取ることができますが、再帰することはできません。つまり、サブルーチンから同じサブルーチンを呼ぶことはできません。

定義は次のように行います。

subroutine_define_sample.scs
FuncArg1: 0
Func: nop
  # 処理
FuncRet: stop
Ret: 0

FuncArg2, FuncArg3…というようにアドレスを増やしていけば、引数の数を増やせます。同様に、FuncArg1を書かなければ引数のないサブルーチンが作れます。
また、戻り値はRetに格納します。

また、呼び出しは次のように行います。

subroutine_call_sample.scs
load X
store FuncArg1
load JFuncRet
store FuncRet
jump Func
JFuncRet: jump FuncCallRet
FuncCallRet: load Ret

Xは引数です。

解説

処理をサブルーチンに分割するためには、次のステップを踏む必要があります。

  1. サブルーチンの先頭に飛ぶ
  2. 呼び出し元に戻る

1はjumpを使って実現できますが、2は少し工夫する必要があります。
2は要するに、サブルーチンの実行が終了したら呼び出し元のアドレスにjumpするということです。この呼び出し元のアドレスにjumpするという情報を伝えるために、そのためのコマンドを呼び出し元の方に書いておきます(JFuncRet)。そして、呼び出し時にそれをサブルーチンの最後(FuncRet)にコピーすることで、2が実現できます。

動的メモリ

メモリの性質より、プログラムの最後に次のように記述することで動的にメモリ領域を使うことができます。

mem_sample.scs
...

MemEnd: 0
Mem: 0

以降「メモリ」ということばが2つの意味を持つ可能性があることに注意してください。

メモリの割り当て

メモリ領域を動的に割り当てます。AllocIには割り当てる領域の数を格納しておきます。また、割り当てられたアドレスはRetに格納されます。

alloc_sample.scs
Alloc: load MemEnd
store Ret
iload MemEnd
add AllocI
store MemEnd

AllocL: load AllocI
ifz AllocRet
sub 1
store AllocI
load 0
storex Mem
iadd 1
jump AllocL

AllocRet: nop
AllocI: 0

メモリのアクセス

割り当てられたメモリにアクセスします。Mem上のアドレスPの、Iバイト目を取得します。loadxをstorexにすれば保存も可能です。

load_pointer_sample.scs
iload P
iadd I
loadx Mem

ラベルと数値の変換

そのラベルのあるアドレスを数値の形で取得します。

label_addr_sample.scs
Label: nop

...

A: nop Label
load A
sub 65535
sub 1

数値指定のjump

アドレスNにjumpします。

jump_by_num.scs
Addr: N
load Addr
add Jump
store B
B: jump
Jump: jump

下2つはまだ実用したことがないのですが、今後スタックの実装などで活用したいと思っています。

SCSのTips

ここからは、SCSを取り扱う上で意識すべきことを紹介します。

メモリ管理

アドレスにラベルをつけて、そこに格納されたデータを処理するといった課題があったと思います。その際、処理するためのデータはプログラムの最後に書くようにしましょう。

理由としては、SCSはプログラムとデータの区別をせずメモリの上から順に実行するからです。例えば、次のように記述することを考えます。

sum_sample1.scs
A: 10
B: 20
Sum: 0

load A
add B
store Sum
stop

これをメモリ上の表現に直すと、

    a
   14
    0
50000
d0001
90002
30000

となります。ここで、SCSは上から実行されることになりますから、1行目のaが読み込まれます。これをプログラムとして解釈すると、(幸いなことに)nopですから、何も起こりません。そこから下2行も同様です。
このように、(一般的な大きさの)データであればどの場所に置いても同じ結果になりますが、無駄にnopを実行してしまっているということになります。ただでさえ公式環境は実行速度が遅いのに、 これは明らかな無駄です。
このような理由から、データはなるべくプログラムの最後に置くようにしましょう。

sum_sample2.scs
load A
add B
store Sum
stop

A: 10
B: 20
Sum: 0

AccとIdxの扱い

AccとIdxはできるだけ使わないことが重要です。AccやIdxはあくまでも計算やコピーのための一時的な領域として使いましょう。ループ回数を記録するためなどに使ってはいけません。
こうすることで、より複雑な処理を書けるだけでなく、コーディング中の自分の頭も整理することができます。

インデント

これはSCSに限らず全てのプログラミング言語に共通することですが、インデントを取ることがプログラムの見通しを良くするために重要です。SCSでのインデントルールは、イディオムに従うのが統一感があっていいと思います。

最後に

ここまで、SCS様々な仕様やイディオムについて言及してきましたが、個人的にはまだまだ不完全燃焼な感じがしています。今後の展望として、より使いやすい言語にするために、イディオムや命名規則などのルールを考えていきたいなと思っています。その一環として、現在SCSのエミュレータを開発中ですが、期待はしないでください。

それと、Advent Calenderなのに長文&マニュアルっぽいものを投下してしまいすいませんでした。なんか違うかなとは思ったのですが、エゴには抗えませんでした。

それでは、よきSCSライフを。

Discussion