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
ラムダ計算ABC - Sendai Logic Homepage https://sites.google.com/site/sendailogichomepage/files/ref/ref_03
ラムダ計算のモデルを使ってもチューリングマシンと同じ表現力がありますよというお話。
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っぽいものをやってみました。中々それっぽく出来ていい感じ。
パーサー
こっちのほうが難航したという。まず以下の部分で逆ポーランド記法に直してます。
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を得ます。
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言語のような原初の風景も感じますが、エディタの補完が強力なので気持ちよく書けます。今度は非同期処理とかもやってみたいですね。