大域脱出用の新しい構文

2014/09/26

本題に入る前に

二つほど今あるものについて説明する.

例外による大域脱出

一般に関数を跨いだ大域脱出にはtry-catch方式の例外システムが用いられる. 例えば以下のようなコードが考えられる.

#!/usr/bin/env python

##########################
# イメージなので動きません #
##########################

# 木をDFSしてほしいものがあれば例外を投げる.なければFalseをかえす
def dfs(node,to_find):
    if node.value == to_find:
        # ここから一気にtryのところまで飛ぶ
        raise Exception(node)
    else:
        for c in node.children:
            dfs(c,to_find)
        return False

def main():
    tree = build_tree()
    try:
        dfs(tree.top(),to_find)
        print("not found")
    except Exception as inst:
        where = inst.args
        print("found " + str(where))

このコードでは,発見したいノードを発見したら,即座にジャンプする. これは例外システムやそれに準ずるものがなければ不可能である.

なお,仮に継続がサポートされていたとしても継続オブジェクトをexplicitに持ちまわすことになるため,簡便には書けない.

問題

Maybeによる失敗表現

失敗を表現する方法としては,例えば例外を使ったり,nullを返したりすることが考えられる. しかしながら,nullを返すのは一般に嫌だという意見が最近多くなっている.理由としては

そこでHaskellでいうMaybe,OCamlでいうOption型を使うことが最近になって流行っている. これは以下のように定義される.

type 'a option = Some of 'a
               | None

OCamlやHaskellでは,Some of 'aをパターンマッチによって取り出すことを強制される. これにより,nullチェックを強制することが可能になる.

let f = function Some a -> a ;;

このコードはエラー(もしくはwarning)となり,

# let f = function Some a -> a;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
None

と怒られる.

また,HaskellにおいてはMaybeはモナドであり,

instance  Monad Maybe  where
    (Just x) >>= k   =  k x
    Nothing  >>= k   =  Nothing
    return           =  Just
    fail s           =  Nothing

と定義されている.参考

これにより,

sub_1 0 = Nothing
sub_1 n = Just $ n-1

sub_4 n = sub_1 n >>= sub_1 >>= sub_1 >>= sub_1

main = do
  print $ sub_4 5
  print $ sub_4 2
Just 1
Nothing

といった感じで,Nothingをexplicitにチェックせずに伝搬することができる.

本題

ここでは以下のような構文を提案する.

def dfs(node,to_find):
    if node.value == to_find:
        jump node
    else:
        # 略
        return None

def main():
    # 略
    #  jumpがない場合 ! jumpした場合の変換
    found = dfs(tree) ! Some
    switch found
        Some node -> print(node)
        None      -> print("Nothing")

これにより,例外処理の関数を跨いだ大域脱出とMaybeによる失敗を結合する.

また,競技プログラミング等の場合,成功したときにはInteger,失敗したときにはStringを要求する場合がある. これはEitherを使って簡単に書くことができる.

def can_be_solved(input):
    if len(input) >= 100:
        jump "NO ANSWER"

# input is [Integer]
def solve(input):
    can_be_solved(input)
    return input[0]

def main():
    result = (Left solve(input)) ! Right
    switch result
        Left i -> print(i)
        Right s -> print(s)

問題点