Go使ってAWS Lambdaでラムダ計算した

tl; dr

ソースコードはこちら
エンドポイントは
https://nd88j25ztg.execute-api.ap-northeast-1.amazonaws.com/dev/lambda
でヘッダにContent-type: application/jsonとX-API-KEY: uwuZMJIWbqpmTpfzdEci2YaMGWFSvWz9ZfWFIjVfを仕込んで{"step":1,"src":"(λx.x)a"}みたいにPostしてください。curlでやると

$ curl -X POST -H "Content-type: application/json" -d '{"step":1, "src": "(λx.x)a"}' -H 'X-API-KEY: uwuZMJIWbqpmTpfzdEci2YaMGWFSvWz9ZfWFIjVf' https://nd88j25ztg.execute-api.ap-northeast-1.amazonaws.com/dev/lambda

みたいな感じ。なお予告なく削除することもあるのでご了承を。

前置き

AWS Lambdaでラムダ計算をするというしょうもないネタ、絶対誰かやってると思ったんですが案外誰もやってない。そんじゃいっちょやってみっかてな感じで、じゃあ言語どうするかって考えたらやっぱ静的型付けがいいよねということでGoに決定。Goやるやる詐欺やめて触ってみるいい機会なのでやってみました。パッケージわけが面倒だったので全部mainです。

そもそもラムダ計算とは

正しく説明できそうにないので参考文献を挙げるにとどめておきます……。ここでは形無しラムダ計算のみ考えます。

ラムダ計算入門 https://www.slideshare.net/_yingtai/lambda-guide
ラムダ計算ＡＢＣ - Sendai Logic Homepage https://sites.google.com/site/sendailogichomepage/files/ref/ref_03

ラムダ計算のモデルを使ってもチューリングマシンと同じ表現力がありますよというお話。

Goで実装する

ラムダ計算

型システム入門を読みながらポチポチやってたらめっちゃ簡単でした

lambda.go

package main

import (
    "sort"
    "strconv"
)

type Name string

type Names []Name

func (xs Names) Len() int{
    return len(xs)
}

func (xs Names) Less(i, j int) bool {
    return xs[i] < xs[j]
}

func (xs Names) Swap(i, j int) {
    xs[i], xs[j] = xs[j], xs[i]
}

type Var struct {
    name Name
}

type Lam struct {
    name Name
    expr Expr
}

type App struct {
    f Expr
    arg Expr
}

type Sym struct{
    symbol rune
}

type Expr interface {
    reduce() Expr
}

func (x Var) reduce() Expr {
    return x
}

func (x Lam) reduce() Expr {
    return x
}

func (x App) reduce() Expr {
    switch g := x.f.(type) {
    case Var:
        return App{g, x.arg.reduce()}
    case Lam:
        return subst(g.name, x.arg.reduce(), g.expr.reduce())
    case App:
        return App{x.f.reduce(), x.arg.reduce()}.reduce()
    default:
        panic("")
    }
}

func (x Sym) reduce() Expr {
    return x
}

var cnt = 0

func subst(x Name, s Expr, y Expr) Expr {
    switch z := y.(type) {
    case Var:
        if x == z.name {
            return s
        } else {
            return y
        }
    case Lam:
        if x == z.name {
            return z
        } else {
            if !elem(z.name, free(s)) {
                return Lam{z.name, subst(x, s, z.expr)}
            } else {
                n := Name((string)(z.name) + strconv.Itoa(cnt))
                cnt++
                return  Lam{n, subst(x, s, subst(z.name, Var{n}, z.expr))}
            }
        }
    case App:
        return App{subst(x, s, z.f), subst(x, s, z.arg)}

    default:
        panic("")
    }
}

func free(x Expr) Names {
    switch y := x.(type) {
    case Var:
        return Names{y.name}
    case Lam:
        return remove(y.name, free(y.expr))
    case App:
        return union(free(y.f), free(y.arg))
    default:
        return Names{}
    }
}

Go言語で union とか直和型のようなデータを表現したいときは interface を使う - 嵐の小舟より https://tmrtmhr.info/tech/sum-type-in-golang/
こちらを参考にADTっぽいものをやってみました。中々それっぽく出来ていい感じ。

パーサー

こっちのほうが難航したという。まず以下の部分で逆ポーランド記法に直してます。

parser.go

func toRpn(str string) ([]rune, error) {
    stack := []rune{}
    rpn := []rune{}
    isParam := false
    lamCnt := 0
    for _, c := range str {
        switch c {
        case '\\', 'λ':
            if isParam {
                return nil, errors.New("lmbda in parameters")
            }
            stack = push('\\', stack)
            isParam = true
        case '.':
            for {
                xs, x, err := pop(stack)
                if err != nil {
                    return nil, errors.New("mismatched lambda")
                }
                stack = xs
                if x == '\\' {
                    break
                }
                rpn = append(rpn, x)
            }
            isParam = false
        case '(':
            if isParam {
                return nil, errors.New("parens in parameters")
            }
            stack = push('(', stack)
        case ')':
            if isParam {
                return nil, errors.New("parens in parameters")
            }
            for {
                xs, x, err := pop(stack)
                if err != nil {
                    return nil, errors.New("mismatched parens")
                }
                stack = xs
                if x == '(' {
                    break
                }
                rpn = append(rpn, x)
            }
            for i := 0; i < lamCnt; i++ {
                rpn = append(rpn, '\\')
            }
            lamCnt = 0

        case ' ', '　':
        default:
            rpn = append(rpn, c)
            if isParam {
                lamCnt++
                rpn = append(rpn, '.')
            }
        }
    }
    if isParam {
        return nil, errors.New("lacking expression")
    }
    for {
        xs, x, err := pop(stack)
        if err != nil{
            break
        }
        if x == '(' || x == ')' || x == '\\' || x == '.' {
            return nil, errors.New("invalid tokens remain")
        }
        stack = xs
        rpn = append(rpn, x)
    }
    for i := 0; i < lamCnt; i++ {
        rpn = append(rpn, '\\')
    }
    return rpn, nil
}

逆ポーランド記法にすることにより括弧を除去できます。これをパーサに読み込ませてASTを得ます。

parser.go

func parse(str string) (Expr, error) {
    rpn, err := toRpn(str)
    if err != nil {
        return nil, err
    }
    stack := []Expr{}
    for _, t := range rpn {
        switch t {
        case '\\':
            lam := true
            for lam {
                xs, x, _ := popExpr(stack)
                ys, y, err := popExpr(xs)
                if err != nil {
                    return nil, errors.New("token exhausted")
                }
                stack = ys
                if w, ok := x.(Sym); ok {
                    x = Var{Name(string([]rune{w.symbol}))}
                }
                if z, ok := y.(Sym); ok {
                    if z.symbol == '.' {
                        vs, v, err := popExpr(stack)
                        if err != nil {
                            return nil, errors.New("argument notfound")
                        }
                        stack = vs
                        if u, ok := v.(Sym); ok {
                            stack = pushExpr(Lam{Name(string([]rune{u.symbol})), x}, stack)
                            lam = false
                        } else {
                            return nil, errors.New("argument must be symbol")
                        }
                    } else {
                        y = Var{Name(string([]rune{z.symbol}))}
                        stack = pushExpr(App{y, x}, stack)
                    }
                }
            }

        default:
            stack = pushExpr(Sym{t}, stack)
        }
    }
    for {
        xs, x, err1 := popExpr(stack)
        if err1 != nil {
            return nil, errors.New("no result")
        }
        if x0, ok := x.(Sym); ok {
            x = Var{Name(string([]rune{x0.symbol}))}
        } 
        ys, y, err2 := popExpr(xs)
        if err2 != nil {
            return x, nil
        } else {
            if y0, ok := y.(Sym); ok {
                y = Var{Name(string([]rune{y0.symbol}))}
            } 
            stack = pushExpr(App{y, x}, ys)
        }
    }
}

λでExprを消費しつつAppにまとめていってます。

prettify

てけとーにASTを文字列に直してるだけなので特に語ることなし。

main

Serverless Framework(Go) でHello worldしてみる - Qiita https://qiita.com/seike460/items/b54a61ec8d07b2be8c87

こちらを参考に、リクエストに対してレスポンスを返す関数を書くだけでした。簡単！

感想

AWS LambdaでWebAPIをさらっと作りたいときはserverless本当に便利ですね。Terraformの特化版のよう。Goは初めて書きましたが思いの外サクサク書けて良い感じ。C言語のような原初の風景も感じますが、エディタの補完が強力なので気持ちよく書けます。今度は非同期処理とかもやってみたいですね。