2019/04/13
I made blog using GatsbyJS.
I will write an English article.
Blog Repository:kgtkr/kgtkr.net
2019/04/13
GatsbyJSを使ってブログを作ってみました。
これまで通りTwitterメインですが、長い文章はなるべくQiitaなどではなくこっちに書いていきたいなと思います。はてなブログは記事移行したら閉鎖します。
英語での発信も積極的にしていきたい。
ブログのリポジトリ:kgtkr/kgtkr.net
2019/04/12
この記事はTS3.4.3で動作確認をしています。
ハイパー演算子とは
hyper(1,a,b)=a+b
hyper(2,a,b)=a*b
hyper(3,a,b)=a^b
︙
のような演算子です(雑)
詳しくはWikipediaを見て下さい。
定義だけ貼っておきます。
hyper(1,a,b)=a+b
hyper(_,a,1)=a
hyper(i,a,1)=hyper(i-1,a,hyper(i,a,b-1))
型レベルタプル操作
型レベルのタプル操作を行うので以下の記事を読んでおくといいかもしれません。
TypeScript 3.0のExtracting and spreading parameter lists with tuplesで遊ぼう
ちなみに今回は上の記事の型レベルタプル操作などをまとめた自作ライブラリtypeparkを使いますが機能は上の記事の通りです。
再帰制限回避テク
FやGが複雑な関数だと以下のような書き方をするとコンパイルエラーが発生することがあります。
type Hoge<T>=F<Cast<G<T
2019/04/11
TypeScriptのランタイム型チェック
TypeScriptにはランタイム型チェック機能がありません。
次のようなコードも正常にコンパイルされエラーが発生することなく動作します。
const x: string = JSON.parse("1");
これはパフォーマンスなどとのトレードオフなので仕方ないのですが、部分的に動的な型チェックをしたいときもあります。
このような時の解決策としてio-tsを紹介します。
io-tsのメリット
JSON Schemaなどは型とスキーマを2つ書く必要があり大変です。
また大変なだけでなく型とスキーマが異なるといったバグを型システムでチェックすることが出来ません。
コードジェネレーターを使うことで解決できますが、TypeScript上で完結しないのでめんどくさいです。
このような問題はio-tsを使うことで解決します。
ただし再帰型については型推論の関係で型とスキーマを2回書く必要がありますが、型チェックでスキーマと型が違っていればコンパイルエラーが発生します。
基本的な使い方
import
2019/03/20
初めに
以下のコードはstateの値が変わった時どのような動作をすると思いますか?
本質ではないのでclearInterval等の処理は省略しています。
const [x, setX] = useState(0);
useEffect(() => {
setInterval(() => {
console.log(x);
}, 1000);
}, []);
このコード、思うようには動かずstateの値が変わってもずっと0が出力され続けます。
何故でしょうか?JSのクロージャをある程度理解している人なら分かると思います。
コンポーネント関数が呼ばれた時の動作を考えてみましょう。
初回呼び出しではuseState(0)を呼ぶとxに0という値が入ります。
useEffectのコールバックも呼び出されます。この時setIntervalのコールバックはxという変数をキャプチャしています。
2回目以降の呼び出しではxは現在のstateです(このコードだけでは具体的な値は分からない)
useEffectの第二引数が[]なのでコールバック
2018/12/09
問題
https://joi2019-yo.contest.atcoder.jp/tasks/joi2019_yo_e
解法
まず{(L,R)}の前処理をします。
サイズNのリストを用意して自分が入っている区間[L,R]のうちRが最大のもので初期化をします。どの区間にも入っていなければ0です。
ただ普通に実装するとO(MN)で間に合わないので工夫が必要です。
まず{(L,R)}(以後LRと呼ぶ)をR→Lの優先順位で降順ソートします。
次に用意したリストを右から埋めていく(既に埋めた所は埋めない)をしていくとO(N)となり間に合います。
疑似コードは以下のような感じです。
let m_list = make_vec(init=0,len=N);
my_sort(LR) // my_sortはLRをR→Lの優先順位で降順ソートする関数
let cur = N;
for (l, r) in LR {
for i in range(l,min(cur-1, r)) {
m_list[i] = r;
}
2018/12/02
はじめに
Haskellでwasmにコンパイルする言語を実装してみたので記事にしました。
LLVMなどには依存せず直接wasmを出力します。
また、現段階ではエラー処理などは未完成なので間違ったコードを入力するとコンパイラがクラッシュするか不正なwasmを出力するかその他色々おかしな事が起きたりします。
メモリアロケータはこの記事で実装したものを使っています。
GCは実装は一応終わっているのですが(記事)まだコンパイラ側の対応が終わっていません。
このようにまだかなりひどい状態ですが少しずつ改善していけたらなと思っています。
リポジトリ
https://github.com/kgtkr/cl8w
サンプルソース
先にサンプルを見たほうがイメージしやすいと思うので置いておきます。
まず実行の為のJSのソースです。
main.wasmはコンパイル結果、./memory/memory.wasmはメモリアロケータです。
数値のprintも欲しいのでprint関数をimportしています。
エントリポイントはmain.wasmのmain関数とな
2018/12/01
初めに
この記事でメモリアロケータを実装したので今回はGCを実装してみます。
様々な事情でアロケータのコードが少し変わっているのでソースはここを見て下さい。
大きな変更点はfreeの返り値でfreeしたブロックのポインタを取得出来るようになった事くらいです(ブロックが消失した時は0が返ります)。
今回もwatでとりあえず動く物を作る事を目標に実装していきます。
方針
参照カウントとmark and sweepを組み合わせたような実装をします。
ローカル変数などからの参照のみを参照カウントで管理し(これはコンパイラがinc_countとdec_countを呼び出すコードを挿入する必要がある)、参照カウントが0でないブロックをルートセットとして扱いmark and sweepします。
ブロックには2種類あり「データブロック」と「参照ブロック」です。
これはmark and sweepで使用し、データブロックの場合はbodyをただのバイト列として扱うのでmark and sweepの再帰的なマークには影響しません。参照ブロックの場合はbodyを全
2018/12/01
初めに
WebAssemblyには線形メモリがあるだけで動的なメモリ管理機能はありません。
ライブラリを使うことも出来ますが、今回はmallocとfreeを実際に実装してみます。
方針
パフォーマンスは気にしない。とにかく動くものを作るwasmのテキストフォーマットであるwatで実装する
仕様
mallocを呼び出すとメモリブロックが作られます。
メモリブロックにはヘッダ部とボディ部があり、mallocはボディ部の先頭アドレスを返します。
このボディ部の先頭アドレスをブロックのポインタとします。
メモリアドレスは0から始まり、ボディの前にヘッダが入ることからブロックのポインタが0になることはないことがわかるかと思います。
ブロックの間には隙間がなく、またmallocは要求サイズ以上確保するのではなくぴったり要求サイズ確保するものとします。
ヘッダのメモリ配置
サイズ 名前 説明1 flag 終端ブロック:0、未使用:1、使用中:2
4 size ボディのサイズ
4 prev 前ブロックのポインタ。先頭ブロックなら0
終端ブロックはこ
2018/10/13
何かツイート流れてきたので
証明
n, an,\ an, aが整数の時、n0+n1+n2n^0+n^1+n^2n0+n1+n2、すなわちn+n2n+n^2n+n2が6a+56a+56a+5の倍数にならないことを証明する
6a+56a+56a+5の倍数はkkkを整数とすると(6a+5)k(6a+5)k(6a+5)kと表す事が出来る
1+n+n21+n+n^21+n+n2が6a+56a+56a+5の倍数だと仮定すると、
1+n+n2=(6a+5)k1+n+n^2=(6a+5)k1+n+n2=(6a+5)k
n, an,\ an, aが555の倍数の時、p, qp,\ qp, qを整数としn=5pn=5pn=5p、a=5qa=5qa=5qとすると、
(左辺)=1+5p+(5p)2=1+5p+25p2=1+5(p+5p2)\begin{aligned} \text{(左辺)} &=& 1+5p+(5p)^2 \\ &=& 1+5p+25p^2 \\ &=& 1+5(p+5p^2) \end{aligned}(左辺)===1+5p+(5p)21+5p