2008/06/16
■ [Haskell]λ式のde Bruijn Index化と評価 
data Term = Var Int | App Term Term | Lam Term | Con String deriving Show eval :: Term -> Term eval (Var n) = Var n eval (Con s) = Con s eval (Lam b) = Lam b eval (App (Lam b) opd) = eval (replace 0 b (eval opd)) eval (App opr opd) = eval (App (eval opr) opd) replace :: Int -> Term -> Term -> Term replace var (Lam b) arg = Lam (replace (var+1) b arg) replace var (App opr opd) arg = App (replace var opr arg) (replace var opd arg) replace var (Con s) arg = Con s replace var (Var n) arg | n < var = Var n replace var (Var n) arg | n == var = fixfree 0 var arg replace var (Var n) arg | n > var = Var (n-1) fixfree :: Int -> Int -> Term -> Term fixfree depth var (Lam b) = Lam (fixfree (depth+1) var b) fixfree depth var (App opr opd) = App (fixfree depth var opr) (fixfree depth var opd) fixfree depth var (Con s) = Con s fixfree depth var (Var n) | n <= depth = Var n fixfree depth var (Var n) | n > depth = Var (n+var-1) -- examples icomb = Lam (Var 0) kcomb = Lam (Lam (Var 1)) scomb = Lam (Lam (Lam (App (App (Var 2) (Var 0)) (App (Var 1) (Var 0))))) bcomb = Lam (Lam (Lam (App (Var 2) (App (Var 1) (Var 0))))) ccomb = Lam (Lam (Lam (App (App (Var 2) (Var 0)) (Var 1)))) ycomb = Lam (App (Lam (App (Var 1) (App (Var 0) (Var 0)))) (Lam (App (Var 1) (App (Var 0) (Var 0))))) -- eval (App (App (App scomb kcomb) kcomb) (Con "a")) => Con "a" data Expr = V String | A Expr Expr | L String Expr | C String deriving Show compile :: [String] -> Expr -> Term compile namestack (C s) = Con s compile namestack (A opr opd) = App (compile namestack opr) (compile namestack opd) compile namestack (L p b) = Lam (compile (p:namestack) b) compile namestack (V v) = Var (find 0 v namestack) where find index var (name:rest) = if var == name then index else find (index+1) var rest -- compile [] (L "x" (L "y" (V "x"))) => Lam (Lam (Var 1)) -- compile [] (L "f" (A (L "x" (A (V "f") (A (V "x") (V "x")))) (L "x" (A (V "f") (A (V "x") (V "x"))))))
コメント
2007/11/30
目次
- [Python] 型推論をPythonで実装してみる
- 言語定義
- eval
- 型推論
- inference関数
- unify関数
- check_cycric関数
- TypeCheckErrorクラス
- TypeEnvクラス
- TypeMapクラス
- concrete_type関数
- 型推論実行例
- 例コード
- まとめとか
- リンク
■ [Python] 型推論をPythonで実装してみる 
プログラミング言語での型チェックというのは、簡単に言うと、
- プログラム中の式が、それを構成する要素（部分式や、それ自体では式にならない項）の間で型情報の関係が整合性が取れているかどうかをチェックすること。
型情報のつけ方には種類があって、
- 項そのものを見るだけで型がわかるタイプ: (現時点での)Java, Cなど
- 関数や変数すべてにそれ自体に具体的な型情報がついている
- 項だけじゃ型がわからないかもしれないタイプ: OCaml、Haskellなど
- 関数や変数の型は、その関連する式から「推論」する必要がある
型推論の実装とは、後者の型チェックを行うための仕組み。
以下はソースコード。
言語定義
ここでは、パーザーではなく、抽象構文木（AST)を定義する。型推論(や型チェック)は構文木に対して行われるものだからパーザーは省略している。
x = 10 func = \num -> x + num func(5)
というプログラムは、
expr0 = Let("x", Val(10),
Let("func", Lambda(["num"],
Add(Ref("x"), Ref("num"))),
Apply(Ref("func"), [Val(5)])))
という構文木として表現するものになります。
(以下ずっと上から順につなげて、最後に例題をつなげれば実行できます。)
# syntax tree nodes for the lang class Expr: """absctract expression base class""" def __repr__(self): return self.__class__.__name__ + repr(self.__dict__) pass class Val(Expr): """value, literal""" def __init__(self, python_value): self.value = python_value pass pass class Add(Expr): """+""" def __init__(self, left, right): self.left = left self.right = right pass pass class Let(Expr): """set variable. let name = value; body""" def __init__(self, name, value, body): self.name = name self.value = value self.body = body pass pass class Ref(Expr): """variable reference by the name""" def __init__(self, name): self.name = name pass pass class Lambda(Expr): """anonymous function. \param1, param2, ... -> body """ def __init__(self, params, body): self.params = params self.body = body pass pass class Apply(Expr): """apply function and args. func(arg1, arg2, ...) """ def __init__(self, func, args): self.func = func self.args = args pass pass class Typed(Expr): """ for type declaration expr :: type """ def __init__(self, expr, type): self.expr = expr self.type = type pass pass # types for the lang class Type: """abstract type base class""" pass class TAtom(Type): """atomic type""" def __init__(self, label): self.label = label pass def __repr__(self): return self.label pass class TFunc(Type): """ function type """ def __init__(self, params_t, ret_t): self.params_t = params_t self.ret_t = ret_t pass def __repr__(self): return VarNames().repr(self) pass class TVar(Type): """variable type: must instanciate for each point of code """ def __init__(self): pass def __repr__(self): return "<vtype: %s>" % str(id(self)) pass class VarNames: """Utility for manage human-readable names for TVar""" def __init__(self): self.names = {} self.current = ord("a") pass def append(self, vtype): """register the name for vtype""" if self.names.has_key(vtype): return self.names[vtype] = "$%s" % chr(self.current) self.current += 1 pass def __getitem__(self, vtype): self.append(vtype) return self.names[vtype] def repr(self, type): """get human-readable string for the type""" if type.__class__ is TVar: return self[type] if type.__class__ is TAtom: return repr(type) if type.__class__ is TFunc: params = [] for param_t in type.params_t: params.append(self.repr(param_t)) pass ret = self.repr(type.ret_t) return "(%s)->%s" % (", ".join(params), ret) pass def __repr__(self): return repr(self.names) pass
最後のVarNamesはTVarやTVar入りのTFuncを人間が読める型変数名にして文字列化するユーティリティ。
一応文法定義すると、プログラム自体はEXPRで以下のようになる
- EXPR = VAL | LET | REF | LAMBDA | APPLY | ADD | TYPED
- VAL = <literal>
- LET = <identifier> '=' EXPR (';'|<lf>) EXPR
- REF = <identifier>
- LAMBDA = '\' (<identifier> ',')* <identifier> '->' EXPR
- APPLY = EXPR '(' (EXPR ',')* EXPR ')'
- ADD = EXPR '+' EXPR
- TYPED = EXPR '::' <type>
型は
- TYPE = ATOM | FUNC | VAR
- ATOM = int | string
- FUNC = '(' (TYPE ',')* TYPE ')' '->' TYPE
- VAR = '$'<identifier>
文や再帰関数はない。
eval
型推論にはまったく不要だが、簡単だしチェックにも使えるので、evaluatorも用意しておいた。
# for evaluator class VarNotFound(Exception): pass class Env: """ Env table""" def __init__(self, parent=None): self.parent = parent self.table = {} pass def put(self, name, value): self.table[name] = value pass def get(self, name): try: return self.table[name] except: if self.parent is not None: return self.parent.get(name) else: raise VarNotFound(name) pass pass pass # for runtime value class Value: pass class VInt(Value): def __init__(self, value): self.value = value pass def __repr__(self): return repr(self.value) pass class VFunc(Value): def __init__(self, code, env): self.env = env self.code = code pass def __repr__(self): return "func: %s" % repr(self.code) pass def evaluate(expr, env): """ (Expr, Env) -> Val """ if expr.__class__ is Val: return VInt(expr.value) if expr.__class__ is Add: return VInt(evaluate(expr.left, env).value + \ evaluate(expr.right, env).value) if expr.__class__ is Let: child_env = Env(env) child_env.put(expr.name, evaluate(expr.value, env)) return evaluate(expr.body, child_env) if expr.__class__ is Ref: return env.get(expr.name) if expr.__class__ is Lambda: return VFunc(expr, env) if expr.__class__ is Apply: func = evaluate(expr.func, env) body = func.code.body child_env = Env(func.env) for index, name in enumerate(func.code.params): arg_value = evaluate(expr.args[index], env) child_env.put(name, arg_value) pass return evaluate(body, child_env) if expr.__class__ is Typed: return evaluate(expr.expr) raise Exception("Not supported Expr: %s" % expr.__class__.__name__)
一応使い方は、
expr0 = Let("x", Val(10),
Let("func", Lambda(["num"],
Add(Ref("x"), Ref("num"))),
Apply(Ref("func"), [Val(5)])))
print(evaluate(expr0, Env()))
型推論
型推論実装のコードは大きいので、トップレベルでごとに解説をつけます。
inference関数
型推論機構のトップレベル関数。
式の構造をチェックしあっていれば、同一視する型のペアを作っていく。たとえばApplyなら第一引数の型は関数、Applyの引数の型とApplyの型で作った関数とそれを同一視させる。
結果として、引数の式の型と、その型の具体型を導出するための情報が返ってくる。
def inference(expr, table, type_map): """type inference: returns type for the expr. (Expr, TypeEnv, TypeMap) -> Type, TypeMap """ if expr.__class__ is Val: return TAtom(type(expr.value).__name__), type_map if expr.__class__ is Add: parametric = TVar() func_type = TFunc([parametric, parametric], parametric) left_type, type_map = inference(expr.left, table, type_map) right_type, type_map = inference(expr.right, table, type_map) ret_type = parametric compare_type = TFunc([left_type, right_type], ret_type) try: type_map = unify([(func_type, compare_type)], type_map) return ret_type, type_map except: print "Type Error at: %s" % repr(expr) raise pass if expr.__class__ is Let: value_type, type_map = inference(expr.value, table, type_map) table = TypeEnv(table) value_type = concrete_type(value_type, type_map, {}) table.put(expr.name, value_type) body_type, type_map = inference(expr.body, table, type_map) return body_type, type_map if expr.__class__ is Ref: name_type = table.get(expr.name) return name_type, type_map if expr.__class__ is Lambda: table = TypeEnv(table) for key in expr.params: table.put(key, TVar()) pass body_type, type_map = inference(expr.body, table, type_map) arg_types = [concrete_type(table.get(key), type_map, {}) \ for key in expr.params] func_type = TFunc(arg_types, body_type) # check cycric try: check_cycric(func_type, type_map) except: print "Type Error at: %s" % repr(expr) raise return func_type, type_map if expr.__class__ is Apply: func_type, type_map = inference(expr.func, table, type_map) func_type = concrete_type(func_type, type_map, {}) arg_types = [] for arg in expr.args: arg_type, type_map = inference(arg, table, type_map) arg_types.append(arg_type) pass ret_type = TVar() compare_type = TFunc(arg_types, ret_type) try: type_map = unify([(func_type, compare_type)], type_map) return ret_type, type_map except: print "Type Error at: %s" % repr(expr) raise pass if expr.__class__ is Typed: expr_type, type_map = inference(expr.expr, table, type_map) try: type_map = unify([(expr.type, expr_type)], type_map) return expr_type, type_map except: print "Type Error at: %s" % repr(expr) raise pass raise Exception("Not supported Expr: %s" % expr.__class__.__name__)
更新: Applyのとき、func_typeを一旦具体化させてからunifyさせてる。id=\x->x; ((id id) 10)対策。
unify関数
queueに入っている型のペアを同一視させる関数。
- ペアになってる型同士の構造が不整合がないかチェック
- たとえば、TFuncとTAtomは絶対に同一視できない
- ペアがTFuncのような構造型どうしだったら、再帰的に要素の型を同一視させる
- ペアに変数型があれば、それを推移（もう一方がTVarじゃない場合）か同値（もう一方もTVarの場合）として型対応情報を作る
戻り値は結果としての型対応情報
def unify(queue, type_map): """unify type-pairs on the queue. - check structures of the pair could be same. - recursively unify component types(TFunc) in structred types. - make reduction or equation for TVar in the pairs. ([(Type, Type)], TypeMap) -> TypeMap""" if len(queue) == 0: return type_map left, right = queue.pop() if left.__class__ is TVar: type_map = TypeMap(type_map) if right.__class__ is TVar: type_map.put_eq(left, right) pass else: type_map.put(left, right) pass return unify(queue, type_map) if left.__class__ is TFunc and right.__class__ is TFunc: if len(left.params_t) != len(right.params_t): raise TypeChechError("mismatched param size: %s <=> %s" %\ (left, right)) for param_l, param_r in zip(left.params_t, right.params_t): queue.append((param_l, param_r)) pass queue.append((left.ret_t, right.ret_t)) return unify(queue, type_map) if left.__class__ is TAtom and right.__class__ is TAtom: if left.label != right.label: raise TypeChechError("mismatched atomic types: %s <=> %s" %\ (left.label, right.label)) return unify(queue, type_map) if right.__class__ is TVar: queue.append((right, left)) return unify(queue, type_map) raise TypeCheckError("mismatched structure of types: %s <=> %s" %\ (repr(left), repr(right)))
check_cycric関数
Lambdaの型は、無限型(..->t->tのように無限に続く型)にならないようにする。Lambdaを推論した結果に無限に循環する型がないかチェックする。これは
そのための関数。
無限ループの原因になる。再帰関数を作るためのYコンビネータもこの型になる。再帰関数を可能にする場合、Y相当のものを特別に独自の「構文要素(たとえばLetRecとか)として」用意する。
def check_cycric(func_type, type_map): """raise error if find cyclic function type in its params""" def check(type, vcache): if type.__class__ is TFunc: for pt in type.params_t: check(pt, vcache) pass return if type.__class__ is TVar: if type in vcache: raise TypeCheckError("cyclic found: %s" % repr(type)) concrete = type_map.reduction(type) if concrete == type: return if concrete.__class__ is TFunc: vcache.append(type) check(concrete, vcache) if concrete.__class__ is TFunc: vcache.pop() return if type.__class__ is TAtom: return pass try: check(func_type, []) except TypeCheckError, ex: concrete_tfunc = concrete_type(func_type, type_map, {}) raise TypeCheckError("cycric type: %s" % repr(concrete_tfunc)) pass
TypeCheckErrorクラス
推論が失敗したことを表す例外クラス。つまり型エラー時起きる。
この推論の実装では例外を、どの式で型エラーが起きたかまでの、中間脱出としても使っている。
class TypeCheckError(Exception): pass
TypeEnvクラス
名前と型を対応付けるクラス。
LetやLambdaごとに追加で用意され、Refで引かれる。外側には波及しない。実行のEnvと似たような形のライフサイクルをとる。
class TypeEnv: """ Type of Name Table for inferencing """ def __init__(self, parent=None): self.table = {} self.parent = parent pass def put(self, name, type): self.table[name] = type pass def get(self, name): try: return self.table[name] except: if self.parent is not None: return self.parent.get(name) else: raise TypeCheckError("%s not found in type env" % name) pass pass pass
TypeMapクラス
変数型(TVar)同士の同値関係(get/putメソッド)や、TVarから具体型への推移関係(put_eqメソッド)の情報を保持して、問い合わせで同値と推移結果を解決する(reductionメソッド)クラス。この型推論実装でのキモ。
class TypeMap: def __init__(self, parent=None): self.parent = parent self.table = {} pass def put(self, vtype, type): try: self.table[vtype].add(type) except: self.table[vtype] = set([type]) pass pass def put_eq(self, vtypea, vtypeb): self.put(vtypea, vtypeb) self.put(vtypeb, vtypea) pass def reduction(self, vtype): types = list(self.get_types(set([vtype]))) types.sort() #print types for type in types: if not isinstance(type, TVar): return type pass return types[0] def get_types(self, types): eq_types = self._collect_types(types) if self.parent is not None: p_types = self.parent.get_types(eq_types) if p_types != eq_types: return self.get_types(p_types) else: return eq_types pass else: return eq_types pass def _collect_types(self, types): eq_types = set().union(types) for type in types: if not isinstance(type, TVar): continue try: eq_types = eq_types.union(self.table[type]) except KeyError: pass pass if types != eq_types: return self._collect_types(eq_types) else: return types pass def __repr__(self): return repr(self.table) + repr(self.parent) pass
更新: setを使うようにしました。
concrete_type関数
「表示可能な形で」具体型を解決する関数。つまり無限型だと途中で止めるようキャッシュしてる。
def concrete_type(type, type_map, cache): """resolve printable concrete type for the type""" if cache.has_key(type): ret = cache[type] return ret if type.__class__ is TAtom: cache[type] = type return type if type.__class__ is TFunc: tfunc = TFunc([], None) cache[type] = tfunc for param_t in type.params_t: concrete_p = concrete_type(param_t, type_map, cache) tfunc.params_t.append(concrete_p) pass tfunc.ret_t = concrete_type(type.ret_t, type_map, cache) return tfunc if type.__class__ is TVar: concrete_t = type_map.reduction(type) cache[type] = concrete_t return concrete_t raise TypeCheckError("mismatched structure of types: %s <=> %s" %\ (repr(left), repr(right)))
型推論実行例
実行と表示のための便利関数
def print_type(expr, label): print "== %s ==" % label try: print expr print expr_type, type_map = inference(expr, TypeEnv(), TypeMap()) print "[raw expression type]" print " " + repr(expr_type) print "[type map]" print " " + repr(type_map) print "[concrete expression type]" print " " + repr(concrete_type(expr_type, type_map, {})) except: import sys, traceback extype, exvalue, trback = sys.exc_info() traceback.print_exception(extype,exvalue, trback, file=sys.stdout) print "<<%s is INVALID>>" % label pass print pass
で、例いろいろ。うしろのeとついた式が型エラーを「起こす」式。ついてないのは型エラーにならない式。
例コード
# examples # valid: <type=int> # x = 10 # func = \num -> x + num # func(5) expr0 = Let("x", Val(10), Let("func", Lambda(["num"], Add(Ref("x"), Ref("num"))), Apply(Ref("func"), [Val(5)]))) print_type(expr0, "expr0") # structral error: # x = 0 # func = \num -> x + num # func(\x -> 5) expr1e = Let("x", Val(10), Let("func", Lambda(["num"], Add(Ref("x"), Ref("num"))), Apply(Ref("func"), [Lambda(["x"], Val(5))]))) print_type(expr1e, "expr1e") # valid: # x = 0 # func = y = 6 # \num -> x + num # func(5) expr1_1 = Let("x", Val(10), Let("func", Let("y", Val(6), Lambda(["num"], Add(Ref("x"), Ref("num")))), Apply(Ref("func"), [Val(5)]))) print_type(expr1_1, "expr1_1") # structral error: # x = 0 # func = y = 6 # \num -> x + num # func(\x -> 5) expr1_1e = Let("x", Val(10), Let("func", Let("y", Val(6), Lambda(["num"], Add(Ref("x"), Ref("num")))), Apply(Ref("func"), [Lambda(["x"], Val(5))]))) print_type(expr1_1e, "expr1_1e") # valid # x = 0 # func = \num -> y = 6 # x + num # func(z = 5 # z) expr1_2 = Let("x", Val(10), Let("func", Lambda(["num"], Let("y", Val(6), Add(Ref("x"), Ref("num")))), Apply(Ref("func"), [Let("z", Val(5), Ref("z"))]))) print_type(expr1_2, "expr1_2") # structral error: # x = 0 # func = \num -> y = 6 # x + num # func(z = 5 # \x -> z) expr1_2e = Let("x", Val(10), Let("func", Lambda(["num"], Let("y", Val(6), Add(Ref("x"), Ref("num")))), Apply(Ref("func"), [Let("z", Val(5), Lambda(["x"], Ref("z")))]))) print_type(expr1_2e, "expr1_2e") # invalid? # \x->x x expr1_3e = Lambda(["x"], Apply(Ref("x"), [Ref("x")])) print_type(expr1_3e, "expr1_3e") # valid # (\x->x) 10 expr1_4 = Apply(Lambda(["x"], Ref("x")), [Val(10)]) print_type(expr1_4, "expr1_4") # valid: <var> -> <var> # id = \x -> x # id expr2_0 = Let("id", Lambda(["x"], Ref("x")), Ref("id")) print_type(expr2_0, "expr2_0") # valid: int # id = \x -> x # id 10 expr2_1 = Let("id", Lambda(["x"], Ref("x")), Apply(Ref("id"), [Val(10)])) print_type(expr2_1, "expr2_1") # valid: <var> -> <var> # id: 'a->'a # id(id): 'a->'a expr2_2 = Let("id", Lambda(["x"], Ref("x")), Apply(Ref("id"), [Ref("id")])) print_type(expr2_2, "expr2_2") # invalid: # idid = \x -> x(x) # idid: (('a->'b)->'b)->'b) expr2_3e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Ref("idid")) print_type(expr2_3e, "expr2_3e") expr2_3_1e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Let("id", Lambda(["x"], Ref("x")), Apply(Ref("idid"), [Ref("id")]))) print_type(expr2_3_1e, "expr2_3_1e") # invalid: # idid = \x -> x(x) # id = \x -> x # idid(id)(10) print "expr2_3_2e" expr2_3_2e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Let("id", Lambda(["x"], Ref("x")), Apply(Apply(Ref("idid"), [Ref("id")]), [Val(10)]))) print_type(expr2_3_2e, "expr2_3_2e") # print(evaluate(expr2_3_2e, Env())): but could evaluate # invalid: # idid = \x -> x(x) # idid(idid)=>idid(idid)=>... expr2_4e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Apply(Ref("idid"), [Ref("idid")])) print_type(expr2_4e, "expr2_4e") # print(evaluate(expr2_4, Env())): infinite loop # invalid: # idid = \x -> x(x) # idid(10) expr2_5e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Apply(Ref("idid"), [Val(10)])) print_type(expr2_5e, "expr2_5e") # invalid: # idid = \x -> x(x) # idid(10) expr2_5_1e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Apply(Apply(Ref("idid"), [Ref("idid")]), [Val(10)])) print_type(expr2_5_1e, "expr2_5_1e") # invalid: # idid = \x -> x(x) # idid(\x->x)(10) expr2_5_2e = Let("idid", Lambda(["x"], Apply(Ref("x"), [Ref("x")])), Apply(Apply(Ref("idid"), [Lambda(["x"], Ref("x"))]), [Val(10)])) print_type(expr2_5_2e, "expr2_5_2e") # print(evaluate(expr2_5_2e, Env())): but could evaluate
まとめとか
とりあえず、きちんと動き、型推論できるようにはなっている。言語としてLetRecは入れたいところ。
式要素が7つで、これだけなので、要素が数十ある普通の言語だとどうなるんだろうか。構造チェックと同一視を行う推論部分は型構造に対してのべた書きだけど、汎用の推論エンジン(ってある？)をつかえば減らせるのかもしれない。そうなったらそうなったで推論エンジンの使い方に戸惑いそうだけど。
リンク
動機とか紆余曲折とか、あとアルゴリズムの情報源も
2007/10/22
■ [Python][OpenCV] すごく遅まきながらOpenCVを使ってみた 
しかも動くが(OpenCVの使い方が)完璧理解できてないという状態。
デフォルトでPythonインタフェースが入ってるのはうれしいですが、使い方がよくわからないのが難しかった。とくにイメージ間操作が。
OpenCVが出たとき作られてた顔にイメージを当てるcgiを書いてみた。とりあえず、sample/python/facedetect.pyを元に、imageは2次元配列っぽく操作できるところまではできた。
int(rect.height * image_scale)),
このcgiのほかに、cacheとconvertedのディレクトリ、スタンプ用のstamp.pngと、OpenCV付属のhaarcascade_frontalface_alt.xmlも必要。
長いけど、OpenCV部分は_convertメソッド内で閉じてます。ほかはWSGIの処理で、その中でURLの?以降の文字列をそのままリソースをとってきて、画像でなければそこにリダイレクト、画像なら保存して変換、変換したファイルへリダイレクトしてます。
_convert部分は、facedetectほぼそのまま、なぜscale変換をしてるのかもよくわかってない。検出できた顔部分のrectから、stampをそのサイズにリサイズするまではいいが、それを埋め込むときどうするかで悩む。もしかして行列操作なのかな。
2007/07/19
■ [C#][DirectShow] DirectShowフィルタを列挙するコマンドラインツール 
.NET 2.0以上でかつDirectShowLibを使います。
ソースコード
listfilters.cs
using System; using System.Runtime.InteropServices; using System.Runtime.InteropServices.ComTypes; using DirectShowLib; namespace listfilters { class Program { static void Main(string[] args) { IFilterMapper3 filterMapper = new FilterMapper2() as IFilterMapper3; ICreateDevEnum devEnum; filterMapper.GetICreateDevEnum(out devEnum); Guid[] categories = new Guid[] { FilterCategory.LegacyAmFilterCategory, FilterCategory.AudioCompressorCategory, FilterCategory.VideoCompressorCategory, //FilterCategory.BDASourceFiltersCategory, }; foreach (Guid category in categories) { //Console.WriteLine(); //Console.WriteLine("new category: " + category); IEnumMoniker monikers; devEnum.CreateClassEnumerator(category, out monikers, CDef.None); monikers.Reset(); IntPtr count = new IntPtr(); IMoniker[] moniker = new IMoniker[1]; while (monikers.Next(1, moniker, count) == 0) { Console.WriteLine("Filter: \"" + GetFilterName(moniker[0]) + "\""); try { IBaseFilter filter = GetFilter(moniker[0]); IEnumPins pins; filter.EnumPins(out pins); int pinCount; IPin[] pin = new IPin[1]; while (pins.Next(1, pin, out pinCount) == 0) { PinInfo info; pin[0].QueryPinInfo(out info); Console.WriteLine(" Pin " + info.dir + ": \"" + info.name + "\""); } } catch (Exception ex) { //Console.WriteLine(ex); } finally { Marshal.ReleaseComObject(moniker[0]); } } Marshal.ReleaseComObject(monikers); } Marshal.ReleaseComObject(devEnum); } static IBaseFilter GetFilter(IMoniker filterMoniker) { object filterObj; Guid baseFilterId = typeof(IBaseFilter).GUID; filterMoniker.BindToObject(null, null, ref baseFilterId, out filterObj); IBaseFilter filter = filterObj as IBaseFilter; return filter; } static string GetFilterName(IMoniker filterMoniker) { object bagObj; Guid propertyBagId = typeof(IPropertyBag).GUID; filterMoniker.BindToStorage(null, null, ref propertyBagId, out bagObj); IPropertyBag bag = bagObj as IPropertyBag; object nameObj; bag.Read("FriendlyName", out nameObj, null); string name = nameObj as string; Marshal.ReleaseComObject(bagObj); return name; } } }
ビルド
csc.exe /r:DirectShowLib-2005.dll /platform:x86 listfilters.cs
実行例
$ ./listfilters.exe Filter: "WMAudio Decoder DMO" Pin Input: "in0" Pin Output: "out0" Filter: "WMAPro over S/PDIF DMO" Pin Input: "in0" Pin Output: "out0" Filter: "WMSpeech Decoder DMO" Pin Input: "in0" Pin Output: "out0" ...
コマンドラインツールだけれど、フィルタによっては、アクセス時にダイアログを出すものがあります。
また、実際にピンを接続したあとで新たなピンが出てくるフィルタもあります(AVI MuxのInputなど)。
ヒント
履歴
2007/06/10
■ [ruby] RunHaskell moduleのデモ 
で書いたような
result = RunHaskell.run do main!(:mfoldr, "[]", [1,2,3]).where(%q{ mfoldr = foldr (\elem bot -> "[" ++ (show elem) ++ ", " ++ bot ++ "]") }) end
という感じで使えるもの。
とりあえず版だけど、show出力はパーズしてRubyオブジェクトにしてる。
require "tempfile" module RunHaskell class HsRunner @@command = "runhaskell" def run(source) file = Tempfile.new "runhaskell" fname = file.path + ".hs" File.rename file.path, fname hsfile = File.new(fname, "w") hsfile.puts(source) hsfile.close io = IO.popen(@@command + " " + hsfile.path) result = io.read() io.close File.unlink hsfile.path result end end class HsParser def initialize(code) @code = code @index = 0 @tokens = [] tokenize end def parse() tok = shift case tok[0] when :numeric return HsNumeric.new(eval(tok[1])) when :string return HsString.new(eval(tok[1])) when :identifier return HsData.new(tok[1].to_sym, parse()) when :lparen elems = [] while true elem = parse() break if elem == nil elems << elem tok = shift case tok[0] when :rparen break when :comma next else unshift tok return nil end end return HsTuple.new(elems) when :lbracket elems = [] while true elem = parse() break if elem == nil elems << elem tok = shift case tok[0] when :rbracket break when :comma next else unshift tok return nil end end return HsList.new(elems) when :lbrace elems = {} while true tok = shift unless tok[0] == :identifier unshift tok break end key = tok[1] tok = shift unless tok[0] == :equal unshift tok return nil end elem = parse() break if elem == nil elems[key] = elem tok = shift case tok[0] when :rbracket break when :comma next else unshift tok return nil end end return HsRecordPart.new(elems) else unshift tok return nil end nil end def tokenize while @index < @code.size token = next_token(@code[(@index)..-1]) @index += token[1].size @tokens << token unless token[0] == :space end end def shift() @tokens.shift end def unshift(token) @tokens.unshift token end def next_token(code) case code when /^(\s+)/ [:space, $1] when /^(\{)/ [:lbrace, $1] when /^(\})/ [:rbrace, $1] when /^(\[)/ [:lbracket, $1] when /^(\])/ [:rbracket, $1] when /^(\()/ [:lparen, $1] when /^(\))/ [:rparen, $1] when /^([,])/ [:comma, $1] when /^([=])/ [:equal, $1] when /^([A-Za-z_][A-Za-z0-9_]*)/ [:identifier, $1] when /^([-+]?[0-9]+([.][0-9]+)?(e[0-9]+)?)/ [:numeric, $1] when /^(\"(\\\"|[^"])*\")/ [:string, $1] end end end class HsNumeric def initialize(str) @core = str end def to_hs @core.to_s end def to_rb @core end end class HsString def initialize(str) @core = str end def to_hs core = @core.to_s.sub("\\", "\\\\") core = core.sub("\"", "\\\"") core = core.sub("\n", "\\n") core = core.sub("\r", "\\r") core = core.sub("\t", "\\t") core = core.sub("\b", "\\b") result = "\"" + core + "\"" result end def to_rb @core end end class HsList def initialize(array) @core = array end def to_hs result = "[" i = 0 @core.each do |elem| i += 1 result += elem.to_hs result += ", " unless i == @core.size end result += "]" result end def to_rb result = [] @core.each do |elem| result << elem.to_rb end result end end class HsTuple def initialize(array) @core = array end def to_hs result = "(" i = 0 @core.each do |elem| i += 1 result += elem.to_hs result += ", " unless i == @core.size end result += ")" result end def to_rb result = [] @core.each do |elem| result << elem.to_rb end result end end class HsData def initialize(name, child) @name = name @child = child end def to_hs result = @name.to_s result += @child.to_hs unless @child result end def to_rb @child.to_rb unless @child end end class HsRecordPart def initialize(child) @child = child end def to_hs result = "{" i = 0 @core.each do |key, elem| i += 1 result += key.to_s + " = " + elem.to_hs result += ", " unless i == @core.size end result += "}" result end def to_rb result = {} @core.each do |key, elem| result[key] = elem.to_rb end result end end class Source def initialize(source="") @source = source @main = nil end def main!(name, *args) @main = Decl.new(:main) body = "putStrLn.show $ " + name.to_s args.each do |arg| body += " " + arg.to_hs end body += "\n" @main.body = body @main end def to_s source = @source source += "\n" + @main.to_s if @main source end end class Decl def initialize(name, *args) @name = name @args = args @body = "" @where = nil end attr_accessor :body def where(source) @where = source end def to_s result = @name.to_s @args.each do |arg| result += " " + arg.to_hs end result += " = " + @body if @where result += " where \n" result += @where end result end end def self.run(code="", &block) src = Source.new code src.instance_eval(&block) if block runner = HsRunner.new result = runner.run(src.to_s) parser = RunHaskell::HsParser.new(result) parser.parse.to_rb end end class String def to_hs RunHaskell::HsString.new(self).to_hs end end class Numeric def to_hs RunHaskell::HsNumeric.new(self).to_hs end end class Array def to_hs hs_list.to_hs end def hs_list RunHaskell::HsList.new(self) end def hs_tuple RunHaskell::HsTuple.new(self) end end class Hash def hs_data(name) RunHaskell::HsData.new(name, RunHaskell::HsRecordPart.new(self)) end end class Symbol def to_hs self.to_s end end