はじめに Haskellでwasmにコンパイルする言語を実装してみたので記事にしました。 LLVMなどには依存せず直接wasmを出力します。 また、現段階ではエラー処理などは未完成なので間違ったコードを入力するとコンパイラがクラッシュするか不正なwasmを出力するかその他色々おかしな事が起きたりします。 メモリアロケータはこの記事で実装したものを使っています。 GCは実装は一応終わっているのですが(記事)まだコンパイラ側の対応が終わっていません。 このようにまだかなりひどい状態ですが少しずつ改善していけたらなと思っています。 リポジトリ https://github.com/kgtkr/cl8w サンプルソース 先にサンプルを見たほうがイメージしやすいと思うので置いておきます。 まず実行の為のJSのソースです。 main.wasmはコンパイル結果、./memory/memory.wasmはメモリアロケータです。 数値のprintも欲しいのでprint関数をimportしています。 エントリポイントはmain.wasmのmain関数とな

初めに この記事でメモリアロケータを実装したので今回は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を全

初めに WebAssemblyには線形メモリがあるだけで動的なメモリ管理機能はありません。 ライブラリを使うことも出来ますが、今回はmallocとfreeを実際に実装してみます。 方針 パフォーマンスは気にしない。とにかく動くものを作るwasmのテキストフォーマットであるwatで実装する 仕様 mallocを呼び出すとメモリブロックが作られます。 メモリブロックにはヘッダ部とボディ部があり、mallocはボディ部の先頭アドレスを返します。 このボディ部の先頭アドレスをブロックのポインタとします。 メモリアドレスは0から始まり、ボディの前にヘッダが入ることからブロックのポインタが0になることはないことがわかるかと思います。 ブロックの間には隙間がなく、またmallocは要求サイズ以上確保するのではなくぴったり要求サイズ確保するものとします。 ヘッダのメモリ配置 サイズ 名前 説明1 flag 終端ブロック:0、未使用:1、使用中:2 4 size ボディのサイズ 4 prev 前ブロックのポインタ。先頭ブロックなら0 終端ブロックはこ

何かツイート流れてきたので 証明 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

Extracting and spreading parameter lists with tuples TS3.0で追加されたタプル型をより強力に扱うための機能です。 型パラメーターとして受け取ったタプルを展開したり出来ます。 基本的な構文は解説しないので公式ブログあたりを見ておいて下さい。 参考 Tuples in rest parameters and spread expressions #24897 このPRで紹介されているものを主に解説していきます。 注意 TypeScript3.0.xにはバグがありコンパイラやエディタ(正格にはtsserver)がクラッシュすることがあるのでTypeScript3.1.xを使って下さい。 前提知識 TSの基本的な型システムの知識宣言的なリスト操作(Haskellなどでやるあれ) 用語 この記事では、type F<T>=...;を関数のように扱うので、Fを関数、Tを引数、タプル型をリスト、type V=...;を値と表現します。 紹介 Head リストの先頭の要素を返す基本的な関数で

メモ -- リスト(右結合) [1,2,3,4,5] ++ ([6,7] ++ [8]) [1,2,3,4,5] ++ [6,7,8] -- コスト2(合計2) [1,2,3,4,5,6,7,8] -- コスト5(合計7) -- リスト(左結合) ([1,2,3,4,5] ++ [6,7]) ++ [8] [1,2,3,4,5,6,7] ++ [8] -- コスト5(合計5) [1,2,3,4,5,6,7,8] -- コスト7(合計12) -- 差分リスト(右結合) fromDiffList(toDiffList [1,2,3,4,5] <> (toDiffList [6,7] <> toDiffList [8])) fromDiffList((\a->[1,2,3,4,5] ++ a) <> ((\b->[6,7] ++ b) <> (\c->[8] ++ c))) fromDiffList((\a->[1,2,3,4,5] ++ a) <> (\x->(\b->[6,7] ++ b) ((\c->[8] ++ c) x))) fro

はじめに TypeScript(TS)には高カインド型(HKT)がありません。一応提案がありますが… しかし様々な機能を組み合わせればHKTを実現することが出来るのでそれの方法と解説を行います。 この記事ではHKTとは何かなどといった解説は行いません。表記は*->*のような表記を使います。 またfp-tsというライブラリを参考にしています。 使う機能 interfaceのマージ(Declaration Merging) TypeScriptでは同名のinterfaceを複数定義出来ます。 そしてこれらは自動的にマージされます。 例えば次の2つの宣言は同等です。 export interface Hoge { x: number; } export interface Hoge { y: number; } export interface Hoge { x: number; y: number; } そしてこの機能は別ファイルや別モジュールで既に定義されているinterfaceを拡張する事も出来ます

やり方 準備 test.ts export type TypeEq<A, B> = (<T>() => T extends A ? 1 : 2) extends (< T >() => T extends B ? 1 : 2) ? true : false export function assertType<_T extends true>() {} export function assertNotType<_T extends false>() {} 色々複雑になっていますが、これは any や union、never などに対応するためです。 ここらへんの型は少し特殊なため、このようにしないと正常にテスト出来ません。 テストの書き方 assertType<TypeEq<1, 1>>() assertNotType<TypeEq<1, 2>>() テストが正しくなければコンパイルエラーが発生します。 例 import { TypeEq, assertType, assertNotType } from "./t

spread operator interface Tweet{ id:string; user:string; body:string; } //tweetはTweet型、userはUser型とする let tw={...tweet,...{user:user}}; この時の変数twの型を定義したい時どうしますか？ 素直に書いてみましょう interface Tweet2{ id:string; user:User; body:string; } 面倒ですね。プロパティが増えるともっと大変です。 typelevel-ts typelevel-tsという便利なライブラリがあります。 このライブラリを使うとこう書けます。 import {ObjectOverwrite} from 'typelevel-ts'; type Tweet2=ObjectOverwrite<Tweet,{user:User}>; これだけです。 他のライブラリ type-zootypical というライブラリもあります。

競プロで標準入力のパースがめんどうだったのでマクロ作りました。 AtCoderのRust(1.15.1)でテスト済みです。 ソースコード https://github.com/kgtkr/procon-lib-rs/blob/master/src/parser.rs 使い方 事前準備 標準入力を全て読み込む let text = { let mut s = String::new(); io::stdin().read_to_string(&mut s).unwrap(); s }; 例 入力値 5 10 20 1 a 2 b 3 c 4 d 5 e 1 2 3 4 5 input!(text=> (n:usize) (a:i64 b:i64) {n;list:(i64,#)} (arr:[i64]) ); assert_eq!(n, 5); assert_eq!(a, 10); assert_eq!(b, 20); assert_eq!(list, vec![(1,"a"