Compiler | Stanford Online を受講した

11月の頭から受講を始めて、5ヶ月弱かけてようやく受講しきりました。

何度か心が折れかけましたがどうにか完遂できました！

https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/aboutlagunita.stanford.edu

この講義は COOL (classroom object oriented language)という、講義のために作られた言語のコンパイラを理論を学びながら作っていくというものです。

リアルの講義スピードだと11週間のコースなのですが、修了するまでに5ヶ月弱も掛かってしまいました。 self paced だったので良かったですが、これが実際の講義だったら落単必死です。

※ 今後は edX で受講できます。 www.edx.org

講義の流れとしては動画を見て理論を学び、学んだことをもとにコンパイラを実装していくといった感じです。 各週の最後のクイズに加えて、約2週間に1度プログラミング課題(lexer, parser, semantic analyzer, code generator)が出ます。

講義の難易度としては、Cコンパイラで有名な Rui Ueyama さんにとってはちょっと簡単過ぎて、G社のエンジニアが弱音を吐くくらいらしいです。(Ueyama-san のは正規の講義で私が受けたのはネットで無料で受講できたものなので難易度が下がっているかも)

ちなみに、私の感想をいうと今まで受けた講義の中で最も難しかったです。最終課題を出すまでに5ヶ月、述べ230時間をこの講義のために費やしました。edX でのコースページを見ると Level: Introductory となっていますが、さすがにそれは過小評価だと思います。最低でも intermediate くらいの難しさはあると思います。

プログラミング課題提出した。CS143は俺にはちょっと簡単すぎるかも。コード量は多いから時間がかからないってわけじゃないんだけど。

— Rui Ueyama (@rui314) May 17, 2015

スタンフォードの単位は通わなくてもリモートで取れるよ、テストとかの難易度は同じで｜Rui Ueyama｜note

教科書はなくとも受講できるという触れ込みでしたが、配布資料とネットの情報だけでは限界を感じて以下の本を購入しました。

flex & bison: Text Processing Tools

Lexer, Parser の課題のときに大活躍でした！

Introduction to Compilers and Language Design

Introduction to Compilers and Language Design
GitHub - dthain/compilerbook-examples: Example code for compilers textbook.

PDF を著者のページからダウンロードできます。結局ほとんど読まなかったですが、GitHub に上がっている Flex や Bison のサンプルを見て Flex / Bison の使い方の理解が進みました。

Modern Compiler Implementation in ML (English Edition)

タイガーブックでおなじみの本ですね。不定期にやってくる Amazon の謎の値下げがちょうどあり、3700円と格安で買えました。 6章の Activation Record まで読みました。講義では LR Parsing がイマイチ理解できなかったのですがこの本のおかげで理解できました。 難しい本だと聞いていたのですが、少なからず私が読んだ6章までは CS のバッググラウンドがない私でも読みやすかったです。

プログラミング言語StandardML入門

タイガーブックは疑似コードで書かれている部分は良かったのですが、ML で書かれている部分は何をしているのかさっぱり理解できなかったので買いました。 初めて ML 触りましたが面白い言語ですね。パターンマッチが便利だなと思いました。

加えて正規言語、文脈自由文法といった予備知識が足りなかったので Automata Theory の講義の該当箇所も同時に受講しました。

www.edx.org

最後の Code Generation の課題は特に難しくて、要求される機能の実装方針が全く思いつきませんでした。講義を見返してもヒントになりそうなこともなかったので最終的に配布されているコンパイラ（バイナリのみ、ソースコードなし）の吐き出すアセンブリを読んで実装方法を推測するというリバースエンジニアリングっぽいことをしてどうにか課題を終わらせることが出来ました。

アセンブリから実装を推測するなんてよっぽどの変態優秀な人にしか無理な芸当だと思っていましたが、素人にも案外できるものですね。

おわりに

昨年の GoCon で Go コンパイラを作った方の話に触発されて軽い気持ちでコンパイラを作り始めましたが、思いの外時間がかかってしまいました。最初は毎日やっていれば1ヶ月もあれば終わるだろうと高をくくっていたのですが、全然そんなことなかったですね。

https://gocon.jp/sessions/selfhost_go_compiler/

今まで概念だけ知っていたクラスの継承などをコンパイラを作ることを通して実践的に理解することができたなと思います。

昨今ではコンパイラを作るのは珍しいことではないのかもしれませんが、自分で実際にコンパイラを作ったことがあるという経験は何事にも変え難いことだなと思います。

「なぜプログラムは動くのか」を読んだ

プログラムはなぜ動くのか　第２版　知っておきたいプログラムの基礎知識

ふと立ち寄ったブックオフで安く売っていたので買ってみました。200円とやけに安いと思ったら第1版のほうでしたが、内容自体が原理に近いものだったのでそこまで古さは感じませんでした。（フロッピーディスクなどは出てきますが。）

帯に「10年後も通用する”基本”を身につけよう」とありますが、出版から20年近くたった現在でも十分通用する内容だと思います。

この本の各章の初めには数問のクイズがあるのですが、後半のハードウェアに近い話になればなるほどどんどん答えられなくなって、自分のコンピュータへの理解が浅いことを思い知らされました。

現在わたしはスタンフォード大学のコンパイラの講義を受講していますが、これが終わったら OS でも作ってみようかなと思える本でした。 lagunita.stanford.edu

広く浅くといった本ですが、アセンブリ言語についても扱っており、コンピュータについてしっかり学びたいと思ったときに初めに読む本として丁度よいと思いました。

Hands-On Serverless Applications with Go を読んだ

AWS Lambda を Go で使う方法を学びたくなり、Hands-On Serverless Applications with Go を読んでみました。

Hands-On Serverless Applications with Go: Build real-world, production-ready applications with AWS Lambda (English Edition)

github.com

大まかな流れは

• Go で Lambda 関数を書く
• API Gateway とつなぐ
• DynamoDB とつなぐ
• CI / CD を入れる (Code Pipeline, Code Build)
• CloudFront で Website をホスティング
• Test / Monitoring / Security / Cost / IaaS

といった感じ。

Chapter 8: Scaling Up Your Application までは本の内容と現在の仕様との違いをなんとか吸収できたものの、Chapter 9 での CouldFront で動かす Website が思ったように動かずそこからは流し読みになってしまいました。 2018年に出版された本なのでそこそこコードも動いてくれるのではと期待したのですが、結構修正が必要でした。また AWS の UI も変わったようで本には書いていない項目があったりしてどうしたものかと少々悩みました。

後半は流し読みになってしまい消化不良なものの、今まで使ったことがなかった DynamoDB に触れることができ、また Lambda 関数がバージョン管理できるものだと知ることができたので読んでよかったと思います。

引っかかったところ

Send の仕様

GitHub issue にも上がっていますが、Send() を Send(context.Background()) としないと動かないコードがちょこちょこありました。

github.com

docs.aws.amazon.com

AWS CLI で API Gateway に DELETE methods を追加

GET, POST を追加するときはマネジメントコンソールからポチポチと追加したのですが、DELETE に関しては AWS CLI を使って追加するという内容でした。 本に書いてある通りにコマンドを打つと一応 DELETE が追加されているようでしたが、なぜか思った挙動をせず。一度それを消して、マネジメントコンソールから DELETE を追加すると想定した挙動になりました。

aws apigateway get-method と aws apigateway get-method-response を使ってそれぞれの方法での差を確認して本には書いていない aws apigateway put-integration-response を追加してみたらうまく動作するようになりました。

# --integration-http-method は POST にする
aws apigateway put-integration \
    --rest-api-id $API_ID \
    --resource-id $RESOURCE_ID \
    --http-method DELETE \
    --type AWS_PROXY \
    --integration-http-method POST \
    --uri arn:aws:apigateway:ap-northeast-1:lambda:path/2015-03-31/functions/arn:aws:lambda:ap-northeast-1:ACCOUNT_ID:function:DeleteMovie/invocations \
    --region ap-northeast-1

aws apigateway put-method-response \
    --rest-api-id $API_ID \
    --resource-id $RESOURCE_ID \
    --http-method DELETE \
    --status-code 200 \
    --response-models '{"application/json":"Empty"}' \
    --region ap-northeast-1


# 本には書いていないがこのコマンドも必要
aws apigateway put-integration-response \
    --rest-api-id $API_ID \
    --resource-id $RESOURCE_ID \
    --http-method DELETE \
    --status-code 200 \
    --selection-pattern "" \
    --region ap-northeast-1 \

aws apigateway create-deployment \
    --rest-api-id $API_ID \
    --stage-name default \
    --region ap-northeast-1

マネジメントコンソールで作った method との差を確認

aws apigateway get-method \
--rest-api-id $API_ID \
--resource-id $RESOURCE_ID \
--http-method DELETE

aws apigateway get-method-response \
--rest-api-id $API_ID \
--resource-id $RESOURCE_ID \
--http-method DELETE \
--status-code 200

どうやら AWS CLI でリソースを作る場合、マネジメントコンソールで作るときに暗黙的によしなにしてくれていることも全て自分の手でコントロールしないといけないようです。 以前 Terraform でリソースを使ったときにも同様なことで引っかかったので、この手の AWS の API を通して(?) リソースを作るのは難しいなぁと改めて実感。

stackoverflow.com

CodeBuild がうまく動かない

GitHub と連携して master ブランチに変更が入るたびに CI を回って、GitHub からコードを取得 -> コンパイル -> Lambda 関数を更新 という流れがあったのですが、どうにもコンパイルがうまくいかず。 S3 には GitHub 引っ張ってきたコードは置かれていたので、GitHub との連携の部分は問題なさそうだったもののコンパイルしたバイナリが S3 の所定の場所に置かれず。権限などでエラーにもなっていないので何が悪いのかもわからず。変な設定を入れてわざと CI を失敗させようとしても Succeed になってしまい、どうにも解決できませんでした。

Julia - キーボードからパスワードを入力する

環境

• ArchLinux
• Julia 1.3.0

CLI でのパスワード入力

readline() や Base.prompt で入力を受ける場合、入力した内容が丸見えでセキュリティもへったくれもない状態なため、パスワードを入力したい場合などには適しません。

goropikari.hatenablog.com

入力したものを値を表示させずにキーボードから入力するには Baes.getpass() を使います。

Base.getpass(message::AbstractString) -> Base.SecretBuffer

julia> s = Base.getpass("Enter your password")
Enter your password: 
SecretBuffer("*******")

julia> read(s, String) # 入力した値を取り出す
"password12345"

使わなくなった秘密情報はすぐに Base.shred! をしろ、String は秘密情報を保持しておくのには適していないということが Base.SecretBuffer の help に書いてあるものの、ならば SecretBuffer に入った秘密情報はどのように利用するのがベストなのか私にはよくわかっていません。

Base.shred! は確保した領域を 0 で埋めているということはソースコードから読み取れたので、そうするのが妥当だろうとは思いましたが（そうしないとクラッカーが該当の領域を直に覗きに来る）、SecretBuffer の利用方法までは読み取れませんでした。

どうするのが良いのかな？

参考

discourse.julialang.org

julia/secretbuffer.jl at v1.3.0 · JuliaLang/julia · GitHub

Julia - permutedims は何をやっているのか

環境

• Julia 1.3.0

がベクトル(1次元配列) or 行列のとき

$$ \mathrm{permutedims}(A)[i,j] = A[j,i] $$

ようするに転置を取るのに等しい。 ベクトルの場合は要素へのアクセスの仕方は変わらないが、 ベクトルは になり、その逆も然り。

$$ \mathrm{permutedims}(A) = A^t $$

しかし、transpose は各要素の中にまで transpose を作用させるのに対して permutedims は単に要素の位置が変わるだけ。また transpose は新しい配列を作成しないが、permutedims は新しい配列を作成する。

julia> a = rand(3,3)
3×3 Array{Float64,2}:
 0.938485  0.960965  0.773617
 0.462651  0.827826  0.143645
 0.622512  0.15178   0.565898

julia> pointer(a)
Ptr{Float64} @0x00007fb0aa55b610

julia> t = transpose(a)
3×3 LinearAlgebra.Transpose{Float64,Array{Float64,2}}:
 0.938485  0.462651  0.622512
 0.960965  0.827826  0.15178 
 0.773617  0.143645  0.565898`

julia> pointer(t.parent)
Ptr{Float64} @0x00007fb0aa55b610

julia> p = permutedims(a)
3×3 Array{Float64,2}:
 0.938485  0.462651  0.622512
 0.960965  0.827826  0.15178 
 0.773617  0.143645  0.565898

julia> pointer(p)
Ptr{Float64} @0x00007fb0aaf30c30

が多次元配列のとき

permutedims の前後での要素の対応関係は以下のようになる。

$$ \mathrm{permutedims}(A, [p_1, p_2, \cdots, p_n] )[i_{p_1}, i_{p_2}, \cdots, i_{p_n}] = A[i_1, i_2 \cdots i_n] $$

たとえば とすると $$ \mathrm{permutedims}(A, [2, 3, 1] )[i_{2}, i_{3}, i_{1}] = A[i_1, i_2, i_3] $$

julia> x = rand(2, 3, 4)
2×3×4 Array{Float64,3}:
[:, :, 1] =
 0.358402  0.109111  0.351109
 0.487991  0.634374  0.374851

[:, :, 2] =
 0.937965  0.0958944  0.0710523
 0.334342  0.871918   0.805091 

[:, :, 3] =
 0.836717  0.121055  0.806076
 0.934635  0.990332  0.768735

[:, :, 4] =
 0.822568  0.270672  0.420414
 0.23469   0.985192  0.016411

julia> y = permutedims(x, [2, 3, 1])
3×4×2 Array{Float64,3}:
[:, :, 1] =
 0.358402  0.937965   0.836717  0.822568
 0.109111  0.0958944  0.121055  0.270672
 0.351109  0.0710523  0.806076  0.420414

[:, :, 2] =
 0.487991  0.334342  0.934635  0.23469 
 0.634374  0.871918  0.990332  0.985192
 0.374851  0.805091  0.768735  0.016411

julia> for i₁ in 1:2
           for i₂ in 1:3
               for i₃ in 1:4
                   if x[i₁, i₂, i₃] != y[i₂, i₃, i₁]
                       println("Not match")
                   end
               end
           end
       end