2020/04/05


1週間ほど前の深夜、ふと Go で連結リスト構造を書いていたら次第に car/cdr 形式になってしまい、気付いたら手が滑って Lisp 処理系を作り始めてしまいました。

初日は深夜だったのでパーサを書いた所で終了。次の日の夕方には四則演算と FizzBuzz が動きました。実は Lisp 処理系を書くのは人生でたぶん4回目くらいで、前回はC言語で書きました。

GitHub - mattn/cisp: Minimal Lisp Interpreter
https://github.com/mattn/cisp

今回のルールとして「過去の自分の実装や他の実装は見ない」というオレオレルールを作ってしまったので幾分時間が掛かってしまった様に思います。テストコードはさすがにいいだろという事で、cisp のテストコードは借りました。マクロを除いて cisp と互換性があります。

今回 Lisp 処理系を書きながらなんとなくやってみたいなと思っていたのが Lisp での非同期処理。Go言語の goroutine と channel を使って通信出来たらどんな物ができるだろう、という研究目的でした。

本日ようやく goroutine/channel が動いたのでブログで公開しておきます。

GitHub - mattn/golisp: Lisp Interpreter
https://github.com/mattn/golisp

(go:make-chan string) で chan を作る事ができ、(go:chan-send ch "foo") で送信、(go:chan-recv ch) で受信する事ができます。また (go (print 1) (print 2)) で goroutine が起動するので、以下の様な channel を使った通信ができます。

(setq time (go:import time))
(let ((ch (go:make-chan string 1)))
    (go
        (.Sleep time 1e9)
        (go:chan-send ch "1")
        (.Sleep time 1e9)
        (go:chan-send ch "2")
        (.Sleep time 1e9)
        (go:chan-send ch "3")
        (.Sleep time 1e9)
        (go:chan-send ch "ダーッ!")
    )
    (print (car (go:chan-recv ch)))
    (print (car (go:chan-recv ch)))
    (print (car (go:chan-recv ch)))
    (print (car (go:chan-recv ch)))
)

研究の成果としては、面白い動きが確認できたのでまずまずの成果と思います。上記の様に Go のパッケージを import して関数やメソッドを呼び出せる様になっています。例えば乱数を表示するには以下の様に実行します。

(setq time (go:import 'time))
(setq rand (go:import 'math/rand))
(.Seed rand (.UnixNano (.Now time)))
(print (.Int rand))

今の所、実用的ではありませんが、細々とメンテナンスしていってツールを書く程度に使えるまでは持っていきたいと思います。

Posted at by



2020/04/04


Go でスライスに挿入する例として Go の Wiki に以下の物が記載されている。

しかしこのコードは、挿入されるスライスから部分スライスを取り出し、そこに挿入するスライスを append に割り当てる為に展開し、さらに残りの部分スライスも append に割り当てる展開を行っている。なので実装コードとしては短いが、実際に実行されるオペレーションコードが冗長になる。また、スライスの伸長はおよそ2倍ずつ増える。なので例えば 5000 個のスライスに 1000 個のアイテムを挿入すると、キャパシティはおよそ 12000 近くになる。Go ではこういったスライスの操作も、基本的には自身で make によりメモリを確保し、ループで値を割り当てるのが良い(面倒かもしれないがその方がメモリも節約され速い)とされている。

以下、ベンチマークを取ってみる。

package main_test

import (
    "reflect"
    "testing"
)

type T int

func BenchmarkAppend(b *testing.B) {
    b.ResetTimer()

    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = append(input[:n], append(insert, input[n:]...)...)
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}

func BenchmarkNormal(b *testing.B) {
    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = make([]intlen(input)+len(insert))
        for l := 0; l < n; l++ {
            output[l] = input[l]
        }
        for l := 0; l < len(insert); l++ {
            output[l+n] = insert[l]
        }
        for l := n; l < len(input); l++ {
            output[l+len(insert)] = input[l]
        }
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}

func BenchmarkCopy(b *testing.B) {
    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = make([]intlen(input)+len(insert))
        copy(output, input[:n])
        copy(output[n:], insert)
        copy(output[n+len(insert):], input[n:])
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}
BenchmarkAppend-8          42700             26185 ns/op
BenchmarkNormal-8          70170             18005 ns/op
BenchmarkCopy-8            90902             15787 ns/op

Wiki に載っているコードは、手動でスライスを挿入するコードの1.5~2倍遅い。copy を使うともう少し速い。

Posted at by



2020/02/27


こういった場合に便利なのがオフィシャルが提供している解析コマンド shadow です。(相変わらずググらび...)

インストールは以下を実行します。

$ go get golang.org/x/tools/go/analysis/passes/shadow/cmd/shadow

ツイートされておられる以下のコードで実行してみます。

package main

import (
    "fmt"
)

var condition = true

func main() {

    var hoge *string
    if condition {
        hoge, err := do("word")
        if err != nil {
            return
        }
        fmt.Printf("checkpoint: %v\n", *hoge)
    } else {
        hoge = nil
    }

    fmt.Printf("RESUT: %v\n", hoge)

}

func do(v string) (*stringerror) {
    return &v, nil
}
.../main.go:13:3: declaration of "hoge" shadows declaration at line 11

便利。

Posted at by