ギークもどきの日記帳

雑多な知識が垂れ流される場所。ほとんど無害。

stack ghciでllvm-hs読み込めないときにすること

$ stack ghci
Configuring GHCi with the following ...

lookupSymbol failed in relocateSection (relocate external)
/usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a: unknown symbol `__ZN4llvm3lto11thinBackendERNS0_6ConfigEjNSt3__18functionIFNS3_10unique_ptrINS0_18NativeObjectStreamENS3_14default_deleteIS6_EEEEjEEERNS_6ModuleERNS_18ModuleSummaryIndexERKNS_9StringMapINS3_3mapIyjNS3_4lessIyEENS3_9allocatorINS3_4pairIKyjEEEEEENS_15MallocAllocatorEEERKNSH_IyPNS_18GlobalValueSummaryESJ_NSK_INSL_ISM_SV_EEEEEERNS_9MapVectorINS_9StringRefENS_13BitcodeModuleENS_8DenseMapIS12_jNS_12DenseMapInfoIS12_EENS_6detail12DenseMapPairIS12_jEEEENS3_6vectorINSL_IS12_S13_EENSK_IS1C_EEEEEE'
ghc: Could not on-demand load symbol '__ZN4llvm11raw_ostream13SetUnbufferedEv'

GHC runtime linker: fatal error: I found a duplicate definition for symbol
   __ZN4llvm11raw_ostream13SetUnbufferedEv
whilst processing object file
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a
The symbol was previously defined in
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a(LTO.cpp.o)
This could be caused by:
   * Loading two different object files which export the same symbol
   * Specifying the same object file twice on the GHCi command line
   * An incorrect `package.conf' entry, causing some object to be
     loaded twice.
ghc: Could not on-demand load symbol '__ZN4llvm9StringMapIcNS_15MallocAllocatorEE11try_emplaceIJcEEENSt3__14pairINS_17StringMapIteratorIcEEbEENS_9StringRefEDpOT_'

GHC runtime linker: fatal error: I found a duplicate definition for symbol
   __ZN4llvm9StringMapIcNS_15MallocAllocatorEE11try_emplaceIJcEEENSt3__14pairINS_17StringMapIteratorIcEEbEENS_9StringRefEDpOT_
whilst processing object file
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a
The symbol was previously defined in
   /usr/local/Cellar/llvm-4.0/4.0.0/lib/llvm-4.0/lib/libLLVMLTO.a(LTOBackend.cpp.o)
This could be caused by:

などと吐いてstack ghciが死ぬ。 intero-modeはstack ghciに依存しているのでつらい。 REPLでゴニョゴニョできないのもつらい。

解決策

stack.yamlflags: {}を次のように書き換える

flags:
  llvm-hs:
    shared-llvm: true

GHCでFizzBuzz

GHCFizzBuzzを書いた。

gen_nats(Max, Ns) :-
    true |
    gen_integers(1, Max, Ns).

gen_integers(N, Max, Is) :-
    N =< Max |
    Is = [N | Is1],
    N1 := N + 1,
    gen_integers(N1, Max, Is1).

gen_integers(N, Max, Is) :-
    N > Max |
    Is = [].

map([], Fs) :-
    true |
    Fs = [].

map([N|Ns], Fs) :-
    N mod 15 =:= 0 |
    Fs = [fizzbuzz|Fs1],
    map(Ns, Fs1).

map([N|Ns], Fs) :-
    N mod 3 =:= 0, N mod 5 =\= 0 |
    Fs = [fizz|Fs1],
    map(Ns, Fs1).

map([N|Ns], Fs) :-
    N mod 3 =\= 0, N mod 5 =:= 0 |
    Fs = [buzz|Fs1],
    map(Ns, Fs1).

map([N|Ns], Fs) :-
    N mod 3 =\= 0, N mod 5 =\= 0 |
    Fs = [N|Fs1],
    map(Ns, Fs1).

print([S|Ss], IOs) :-
    true |
    IOs = [write(S), nl | IOs1],
    print(Ss, IOs1).

print([], IOs) :-
    true |
    IOs = [].

コードの見た目はPrologに近いが、逐次性が無い、ガード節がある、などの理由でPrologで書いたものとはかなり異なる…はず。

実行はこんな感じ

?- ghc genNats(10, Ns), map(Ns, Fs), print(Fs, Os), outstream(Os).
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Fs = [1, 2, fizz, 4, buzz, fizz, 7, 8, fizz|...],
Os = [write(1), nl, write(2), nl, write(fizz), nl, write(4), nl, write(...)|...].

GHCつながりでHaskell版も書いてみた。GHC版と似せるためにちょっと変な書き方をしている。

module Main where

genNats :: Int -> [Int]
genNats m = genIntegers 1 m

genIntegers :: Int -> Int -> [Int]
genIntegers n m | n <= m = n : genIntegers (n + 1) m
                | otherwise  = []

map' :: [Int] -> [String]
map' [] = []
map' (n:ns) | n `mod` 15 == 0 = "fizzbuzz" : map' ns
            | n `mod` 3 == 0  = "fizz" : map' ns
            | n `mod` 5 == 0  = "buzz" : map' ns
            | otherwise       = show n : map' ns

main :: IO ()
main = mapM_ putStrLn (map' (genNats 10))

実行するとこんな感じ

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz

GHCのコードはHaskellに似ている(これが言いたかっただけ)。

GHC(Guarded Horn Clauses)のインストール

GHCとは

https://ja.wikipedia.org/wiki/Guarded_Horn_Clauses/

インストール方法

今回は、SWI-Prolog上に実装されたGHCの処理系をインストールする。

SWI-PrologSWI-Prolog からインストールできる。

次に、 Software from UEDA Lab. から GHC system running on top of SWI-Prolog をダウンロード、展開する。

展開したディレクトリに移動し、

$ swipl
Welcome to ~...

?- ['ghcswi.pl'].
Warning ~...
true.

?- 

これでGHCプログラムを実行できる様になった。

GHCプログラムのコンパイルghccompile/1で行う

?- ghccompile('fib.ghc').
go/1', 'fibonacci/2', 'fib/4', 'outterms/2', ''END.'
true.

実行は

?- ghc go(10).
1
1
2
3
5
8
false.

fib.ghcはこんな感じ

go(Max) :- true |
           fibonacci(Max, Fs),
           outterms(Fs, Os), outstream(Os).

fibonacci(Max, Ns) :- true |
                      fib(Max, 0, 1, Ns).

fib(Max, N1, N2, Ns0) :- N2 =< Max |
                         Ns0 = [N2 | Ns1],
                         N3 := N1 + N2, fib(Max, N2, N3, Ns1).

fib(Max, N1, N2, Ns0) :- N2 > Max |
                         Ns0 = 0.

outterms([X|Xs1], Os0) :- true |
                          Os0 = [write(X), nl | Os1],
                          outterms(Xs1, Os1).

outterms([],      Os0) :- true |
                          Os0 = [].

"int main(void) { return 0; }"のLLVM IRを読んだメモ

とりあえずの学習メモとして残す。 理解が怪しいところは?や(?)などをつけている。 理解が進んだ後に整理したものを書きたい。

int main (void) {
  return 0;
}

このプログラムはCにおける(多分)最小のプログラムで、単にステータスコード0を返すだけのプログラム。

これをclang -S -emit-llvmLLVM IRに変換するとこうなった。(macOSで吐いた)

; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

; Function Attrs: noinline nounwind ssp uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  ret i32 0
}

attributes #0 = { noinline nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (tags/RELEASE_400/final)"}

まず、';‘から始まる行はコメントなのでプログラムとしては無視する。

source_filename = "hello.c"は見ての通り元のソースファイルの名前で、プロファイル時にユニークなローカル関数の識別子を生成するために使っているらしい。

target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"はメモリ上のデータレイアウトを記述している。

  • ‘-'が区切り文字。
  • ‘e'はリトルエンディアン。
  • ’m:o'は名前修飾の方法を指定している。'o'なので'Mach-O'式の名前修飾を行う。
  • ‘i64:64'は64bit整数のアライメントを64に指定している。この場合は64の倍数?
  • ‘f80:128'も浮動小数点数であること以外は上に同様
  • ‘n8:16:32:64'はありうる整数のbitを指定している。これはx86-64の場合。
  • ‘S128'はスタックのアライメント。
define i32 @main() #0 {
    %1 = alloca i32, align 4
    store i32 0, i32* %1, align 4
    ret i32 0
}

今回のプログラムの本体がここ。 LLVM IRはこのようにC+アセンブラっぽい文法で書かれている。

‘i32'は32bit整数。LLVMのドキュメントに様々な型について詳細な情報がある。Rustっぽい。

‘%1'のように’%‘で始まるものがローカル識別子。 この場合、%1はアライメント4, 32bit整数のレジスタとして定義されている。

‘store i32 0, i32* %1, align 4'で、%1に0を代入している。alignは%1のものと一致するように指定される(?)。

‘ret i32 0'はC言語の'return 0;'に対応する。

%1の意味は… 最適化のせいかと考えたが、-O0でも結果は変わらず。あとで調べる。 (2017 6/20追記) よく考えたら-Sだと-O0の結果が出力されてる。 clang -emit-llvm -S -01で出力させると削除される。

define i32 @main() local_unnamed_addr #0 {
  ret i32 0
}

(追記ここまで)

attributes #0 = { noinline nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

この一行は#0という名前のattribute groupを宣言している。先程のmain() #0の'#0'の部分へ代入されるっぽい。

0と#1という2つのattribute groupがあるとき、#0 #1と書くと2つが接続される。

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (tags/RELEASE_400/final)"}

ここではモジュール全体のメタデータを定義している。

もう少し複雑なプログラムについてはまた今度。

「最新コンパイラ構成技法」でハマったところのツイまとめ 5/3

RoswellでCommon Lisp環境をセットアップする

Roswellとは (ざっくりと)

Common Lispの処理系やQuicklisp、SLIMEなどのインストール、処理系ごとのオプションの違いの吸収などを行うすごい便利なツール。 Common Lisperなら使って損はない。

インストール

参照Wiki

1. Installation · roswell/roswell Wiki · GitHub

Arch Linux

AURに登録されているので、yaourtでインストールできる。

$ yaourt -S roswell

Homebrew

$ brew install roswell

Windows

1. Installation · roswell/roswell Wiki · GitHub

使っているOSのbitに合わせて、32bitならRoswell-i686.zip、64bitならRoswell-x86_64.zipをダウンロードし解凍、PATHを通す。

ソースからビルド

INSTALL.md参照。

Replの起動

ros runコマンドでREPLが起動する。

$ ros run
* (+ 1 2)

3
* (quit)
$ 

また、roswellはデフォルトでsbcl-1.2.11のバイナリ版を使う。 他の処理系や最新版のsbclを使いたいときは、以下の手順でインストールする。

処理系のインストール (例: Clozure CL)

$ ros install ccl-bin

処理系の切り替え (例: Clozure CL)

$ ros use ccl-bin
$ ros run
Welcome to Clozure Common Lisp Version 1.11-r16635  (DarwinX8664)!

CCL is developed and maintained by Clozure Associates. For more information
about CCL visit http://ccl.clozure.com.  To enquire about Clozure's Common Lisp
consulting services e-mail info@clozure.com or visit http://www.clozure.com.

? 

インストールできる処理系のリストは、ros list versionsで確認できる。

$ ros list version
candidates for ros list versions [impl] are:

abcl-bin
allegro
ccl-bin
clasp
clisp
cmu-bin
ecl
quicklisp
sbcl-bin
sbcl

インストールできるバージョンは、ros list versions [処理系の名前]で確認できる。

$ ros list versions sbcl
Installable versions for sbcl:
Checking version to install....
1.3.15
1.3.14
1.3.13
1.3.12
1.3.11
1.3.10
1.3.9
1.3.8
1.3.7
1.3.6

SLIME

みんなだいすきSLIMEも簡単に使える。 ros emacsで、.emacs.dの設定なしにSLIMEを使えるemacsが起動する。すごい便利。

普通のemacsで使うには以下の手順を踏む。

$ ros install slime

続いて~/.emacs.d/init.elに次の行を追記する。

(load (expand-file-name "~/.roswell/helper.el"))

より詳しい設定方法は、

1.1 Initial Recommended Setup · roswell/roswell Wiki · GitHub

を参照のこと。

Roswell Script

Common LispではRubyPythonと異なり、プログラムをロードしたREPLを用いることが多い。 スクリプト言語のようにバッチ処理を実行するには、処理系ごとに異なった方法を取らねばならず少し不便を感じる。

その点を解決するため、RoswellにはRoswell Scriptという仕組みがある。 ros init <ファイル名>で、Roswellがインストールされている環境上で、単体で実行できるCommon Lispが生成される。

$ ros init fact
Successfully generated: fact.ros

$ cat fact.ros
#!/bin/sh
#|-*- mode:lisp -*-|#
#| <Put a one-line description here>
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  (ros:ensure-asdf)
  ;;#+quicklisp (ql:quickload '() :silent t)
  )

(defpackage :ros.script.fact.ros.3698230850
  (:use :cl))
(in-package :ros.script.fact.ros.3698230850)

(defun main (&rest argv)
  (declare (ignorable argv)))
;;; vim: set ft=lisp lisp:

このファイルはEmacsVimの両方でCommon Lispソースコードとして認識される。

main関数がエントリーポイントとなる。main関数の引数には、適切にパースされたコマンドライン引数が渡される。 例えば、引数の階乗を返すコマンドは下のようになる。

#!/bin/sh
#|-*- mode:lisp -*-|#
#| <Put a one-line description here>
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  (ros:ensure-asdf)
  ;;#+quicklisp (ql:quickload '() :silent t)
  )

(defpackage :ros.script.fact.ros.3698230850
  (:use :cl))
(in-package :ros.script.fact.ros.3698230850)

(defun fact (n)
  (if (zerop n)
        1
              (* n (fact (1- n)))))

(defun main (n &rest argv)
  (declare (ignorable argv))
  (format t "~&Factorial ~D = ~D~%" n (fact 
  (parse-integer n)))
  0 ; 終了ステータス
)
;;; vim: set ft=lisp lisp:

実行例

$ ./fact.ros 3
Factorial 3 = 6

$ ./fact.ros 10
Factorial 10 = 3628800

さらに、Roswellがインストールされていない環境でも(おそらく)動作するexecutableも作れる。 ただし、処理系やライブラリのイメージを含むため、ファイルサイズが50MiBぐらい大きくなる。レッツブルジョア!!

$ time ./fact.ros 10
Factorial 10 = 3628800
./fact.ros 10  0.43s user 0.09s system 98% cpu 0.530 total

$ ros build fact.ros

$ time ./fact 10
Factorial 10 = 3628800
./fact 10  0.00s user 0.01s system 89% cpu 0.018 total

$ du -ah
 54M     ./fact
4.0K     ./fact.ros

割りと速くなった。気がする。もっと計算量の多い処理だと大きく変わるかも。

気が向き次第に更新、追記する予定です。

高校で得られた知見とか感想とか

最近流行りの卒業エントリってやつです。 退職エントリの仲間で、長らく仮説上の存在でしたが、近年その実在が証明され、これからは爆発的に普及すると予測されています。 大学を卒業してから書こうと思ってましたが、なんか書き上がってしまったので高校卒業エントリです。

ようは卒業文集に書いたりするアレです。

けっこうこっ恥ずかしいことも書いたので、リアルの僕を知っている方は「読んでないし存在も知らない」という体でお願いします。 思いやりと信頼ですよ?

授業とかテストとかの感想

知らないことをたくさん学べるし、テストがあることで理解度を大雑把に把握できます。 しかし、ペースが遅い。内容もやや単調。授業の魅力は教師ガチャの結果次第。 やることはモバマスや神撃のバハムートとあまり変わらず、得られる報酬の魅力も薄い。 無事にクリアした君にはオプーナを買う権利をやろう。

でも、面白いことには面白い。鯖落ちやメンテナンスもないし、興味のない分野の知識もある程度得られるので、まぁ一回はプレイしてもいいかなと言う感じです。

公立の普通科高校で一からプログラミングをやっていった話

自分の高校生活をまとめると、部活に打ち込んだ3年間、という感じで表現されるのではと考えています。 体験入部もせずにコンピュータ部に入り、そこから3年間、卒業の1週間ぐらい前まで色々やってました。

主にプログラミングについて色々やってたので、ここに問題点と解決策を残しときます。

まず問題になるのが、強すぎるフィルタリングサービスです。これはぶっ壊すわけにもいかないので、顧問と話して、必要なときはスマートフォンなどを使えるようにしました。不便なことには不便ですが、気合で乗り切ります。 単語を見るタイプのフィルターは、言語設定をポルトガル語とかにするとスルーできたりするので、やってみる価値はあるかも。

次に問題なのがPCです。予算もあまりなく、学校のパソコンは好き勝手にはいじれない。大問題です。 解決策として、僕はRaspberry Piを使いました。割りとなんとかなります。Emacs動きます。aptで入らなければ野良ビルドLinuxの勉強にもなるし一石二鳥。 自前のノートPCを利用するのももちろんありです。

もっとも大きな問題は、学習方法でした。教えてくれる先輩も先生もいないので、人類の叡智に頼るほかありません。 How To Become A Hacker: Japaneseはかなり参考になると思います。 プログラミング言語の入門書としては、主に「すごいHaskellたのしく学ぼう!」や「Land of Lisp」を読んでました。 他にも「たのしいRuby」や「すごいErlangゆかいに学ぼう!」、「リーダブルコード」など、とにかく読みまくりました。 プログラミングは独学でなんとかなるので、自分で情報を集めて学ぶ姿勢を身につければあとは楽勝です。(個人の感想です。効能には個人差があります。)

コンピュータ部の感想

ここからは完全に思い出話になります。

僕が入った当時は、幽霊部員の3年生が3人いるだけの、廃部待ったなしな部でした。 多分再来年ぐらいに京アニでアニメ化します。12割ぐらい脚色つけて。

1年生は僕含めて3人で、僕を除いた二人はたまたま小学校の同級生だったりして、世の中不思議な縁もあったものだなぁと感じたのを覚えています。 部のロッカーからなのはのステッカーが出てきたり、部のパソコンのパスワードのヒントが「らき☆すた」で、wikipedia見ながらパスワードを当てたり、なかなか面白いスタートでした。

帰ってきたヒトラー」がどうだとか人肉の味がどうだとかパンツレスリングがどうだとか、極めて雑な話をしながら各々が自分のしたい事をする、コワーキングスペースみたいな場所でした。コワーキングスペース知らないけど。

1年の文化祭ではRAPIROを動かして、大体あそこで学校でのキャラが確定したんじゃないかなと。 じわじわ部員も増えて、アニメ見たりアナログゲームやったりだべったり、あんまりコンピュータ関係ないことをしながら、僕はオセロのAI実装したりRAPIROいじったりしてました。

コンピュータ部は、作業場であり、制作物の発表の場であり、友達と遊ぶ遊び場であり、学校に行く大きな動機だったように思います。

伝えるタイミングを微妙に逃した気がしてるので、ここで感謝の意を公開しておきます。恥ずかしいので部員の皆様はこの記事を見なかったことにしてください。 変なテンションで鈍器を読み漁って黒い画面を見つめる僕と一緒に毎日数時間を共有してくれた部員の皆にはとても感謝しています。 わざわざ家まで来て、スプラトゥーンのウデマエをSまで上げておいてくれてありがとう。おかげですさまじい連敗を味わいました。 結局のところ、2015年4月某日にあの部屋に3人が集まったことで、僕は死にそうなほどブルーな日も高校に行く羽目になり、おかげで無事に卒業でき、ついでに18歳になることもできました。該当の2名には特別の感謝をしたいと思います。出会えた幸運に祝福を。あと顧問の先生二人にも。お世話になりました。

後輩も10人ちょっと入り、コンピュータ部は相変わらずの調子で続いていくようです。良かった良かった。

大学に進学します

おしかったりおいしかったりする県の、3つぐらい似た名前の大学があってややこしい大学の情報科学部に進学します。 特になにかしでかそうとは考えてませんが、とりあえずはAR面白そうだなぁとか考えてます。あとCをちゃんと書けるようになりたい。 関係者となる皆様方はよろしくお願いします。

3年間は早かった。でも疲れたのでしばらくのんびりします。