stackにはHakyll用のテンプレートもあるので、ブログ制作そのものは簡単にできる。 Github Pagesの仕様にあわせるため若干のハックが必要だった。 具体的には、記事作成そのものはblogブランチで行い、_site/以下をmasterブランチにコピーしpushするということをしている。 stack exec blog deployでその辺の作業を自動化した。
CのVariable-length array
C99では, 実行時に配列の長さを指定できる機能が追加された.
#include <stdio.h> int foo(int n) { int array[n]; int array[0] = 1; int array[1] = 1; for (int i = 2; i < n; i++) { array[i] = array[i-1] + array[i-2]; } return array[n-1]; }
sizeofは実行時に計算される.
ただし, C11ではオプション機能に格下げされている. VLAが実装されていない処理系では, __STDC_NO_VLA__というマクロが定義されている.
問題点として, メモリがアロケートされるのがスタックかヒープかが実装依存である点がある. GCCではスタックらしい. また, 巨大なVLAを定義しようとするとプログラムはクラッシュする. ある状況では非常に便利だが, 慎重に扱う必要がある.
ちょっと身内で話題になったので簡単にまとめてみた.
参考URL
詳しくはWebで!
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.yamlのflags: {}を次のように書き換える
flags:
llvm-hs:
shared-llvm: true
GHCでFizzBuzz
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(Guarded Horn Clauses)のインストール
GHCとは
https://ja.wikipedia.org/wiki/Guarded_Horn_Clauses/
インストール方法
今回は、SWI-Prolog上に実装されたGHCの処理系をインストールする。
SWI-Prologは SWI-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-llvmでLLVM 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
SML/NJで最新コンパイラ構成技法のソース読み込んだら(CMで)、"unbound structure: TextIO in path TextIO.instrem"とか言われて詰んだ
— こうの (@takoeight0821) 2017年5月3日
sources.cmに$/basis.cmを追加したらうまくいった(あと、smlnj-lib.cmも$/smlnj-lib.cmにした)
— こうの (@takoeight0821) 2017年5月3日
あーなるほど(cmの書き換えとmlton、cm2mlbの学習コストを天秤にかけ左に傾く音)
— こうの (@takoeight0821) 2017年5月3日
