juliaで可変ワード長の演算を試す - 数学と電気とプログラム

juliaが結構便利なので、勉強がてら有限ワード長のモジュールを作っています。その過程をメモ代わりにそのまま吐き出してみようと思います。

概要を考える

ワード長は可変にしたいので、値とワード長の二つのフィールドが必要になりそうです。値の方は、簡単のため UInt で済ませます。演算をするのであれば、コンストラクタと加減算、あとは、連結はほしいところです。

というざっくりしたイメージでスタートしました。

コンストラクタ

こちらは、特に悩む必要もなくtypeを使うだけで終わります。任意ワード長の RegVarのほかに、8bit固定の Reg8 も用意しておこうかと思い、これらをまとめる抽象型 AbstractReg も作りました。

abstract AbstractReg
type RegVar <: AbstractReg
  val :: UInt
  wl :: Int
end
type Reg8 <: AbstractReg
  val :: Uint
end

加算

Baseの+関数をimportして、ワード長を考慮しながら計算します。

import Base: +
export +
+(a::RegVar, b::RegVar) = addreg(a, b)
function addreg%(a::RegVar, b::RegVar)
  n = max(a.wl, b.wl)
  ub = 2^(n-1)-1
  lb = -2^(n-1)
  y = a.val + b.val
  if (y < lb)
    y = y + 2^n
  else (y > ub)
    y = y - 2^n
  end
  RegVar(y, n)
end

RegVar としてはこれでいいのですが、Reg8に適用しようとしてもReg8はwlをメンバに持っていないのでうまくいきません。かといって、Reg8にwlを追加するのも嫌だな……。と考えたところで、wl を総称関数にすればよいことに気づきました。

wl(::Reg8) = 8
wl(x::RegVar) = x.wl

これをつかって先ほどのaddregを書き換えると、こうなります。

import Base: +
export +
+(a::AbstractReg, b::AbstractReg) = addreg(a, b)
function addreg(a::AbstractReg, b::AbstractReg)
  n = max(wl(a), wl(b))
  ub = 2^(n-1)-1
  lb = -2^(n-1)
  y = a.val + b.val
  if (y < lb)
    y = y + 2^n
  else (y > ub)
    y = y - 2^n
  end
  RegVar(y, n)
end

a.wl などとしていたところを wl(a) にしてあげただけですが、これで Reg8 にも RegVar にも対応できるようになりました。

Juliaの場合、型のフィールドに対して自動的にアクセサが生成されるのですが、総称関数を定義するとこういうときに便利なのですね。納得。

減算

減算は、単項演算子のマイナスを定義して、先ほどの加算と組み合わせることにします。

import Base: -
export -
-(x::AbstractReg) = RegVar((1 << wl(x)) - x.val, wl(x))
-(a::AbstractReg, b::AbstractReg) = a + (-b)

ワード長が64の時にどうするんだという話はありますが、とくに問題ないようです。

julia> convert(UInt, 1) << 64 - 1
0xffffffffffffffff

連接

このあたりから自信がなくなってきます。演算子は ++ にすることにして、二項演算子としてはすぐに書けました。ただ、これを連続して使おうとした場合にどうするかで手が止まります。よくわからないので、julia本体から似たようなコードを探してみることに。sum なら可変長引数をとるかとおもって確認してみたところ、tuple.jlに記載がありそうです。

julia> methods(sum)
# 13 methods for generic function "sum":
sum(x::Tuple{Any,Vararg{Any,N<:Any}}) at tuple.jl:205
...

そこを確認したところ、ドット３つでタプルを展開してくれるような感じです。いわれてみれば、MATLABにそんなのがあったような気もします。

export ++
++(args...) = assoc(args)
assoc(x::Tuple{Any, Vararg{Any}}) = assoc(x...)
assoc(a::RegVar, args...) = assoc(a, assoc(args))
...

こんな感じで展開できました。

補足：表示、等号

書き始めた当初に、完全に忘れていたのが表示と等号。これらがないと REPL やテストで困ることに、後で気づきました。表示については、juliaの本体を検索すると、showという関数を定義すればよさそうなことがわかりました。

> ag "print\(" *.jl
...
version.jl
48:function print(io::IO, v::VersionNumber)
49:    v == typemax(VersionNumber) && return print(io, "∞")
50:    print(io, v.major)
51:    print(io, '.')
52:    print(io, v.minor)
53:    print(io, '.')
54:    print(io, v.patch)
...

というわけで、定義します。

import Base: show
function show(io::IO, x::AbstractReg)
  mroundup(x, n) = Int(ceil(x / n)) * n;
  print(io, wl(x));
  print(io, "'h");
  octmask = 1 << 4 -1;
  for i=mroundup(wl(x), 4)-4:-4:0
    z = octmask & (x.val >> i);
    if z < 10
      print(io, z);
    else
      print(io, 'a'+ (z-10));
    end
  end
end

これだけ定義すれば、REPL や print 関数などから自動的に呼んでもらえます。

julia> Reg8(10)
8'h0a

等号はこんな感じ。

==(a::AbstractReg, b::AbstractReg) = (a.val == b.val) && (wl(a) == wl(b))

できた。