Python の lambda 関数の挙動について

Question

lambda 関数を用いて、以下のような処理をしたいと考えています。

実現したい処理

• 文字列 s を解析して、対応する無名関数を返す関数 calc(s) を定義して実行
• 文字列 x+3 を受け取りf=calc("x+3") とする（入力は x+[1桁の整数] or [1桁の整数]+x の形式（+ の部分には +, -, *, / のいずれかが入る）とする）
• f(1) の値を実際に計算してみる

やったこと

次のようなコードを書いたのですが、 TypeError: unsupported operand type(s) for +: 'function' and 'int' となってしまい、 lambda と int の計算は型が合わないためできないとなってしまいます。

原因は分かっているのですが、このような処理を実行するために適切なコードの書き方が分かりません。教えていただけると助かります。

def calculator(x, op, y):
    if op == "+":
        return x + y
    elif op == "-":
        return x - y
    elif op == "*":
        return x * y
    else:
        return x // y

def read_char(c):
    if c == "x":
        return lambda x: x
    else:
        return int(c)

def calc(s):
    lf = read_char(s[0])
    op = s[1]
    rf = read_char(s[2])
    def func(x):
        return calculator(lf, op, rf)
    return func

実行結果

>>> f = calc("x+3")
>>> f(1)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
 in ()
----> 1 f(1)

 in func(x)
     20     rf = read_char(s[2])
     21     def func(x):
---> 22         return calculator(lf, op, rf)
     23     return func

 in calculator(x, op, y)
      1 def calculator(x, op, y):
      2     if op == "+":
----> 3         return x + y
      4     elif op == "-":
      5         return x - y

TypeError: unsupported operand type(s) for +: 'function' and 'int'

Comments

[meg_]

「f(1)」の結果は何を期待されていますか？

[bighope]

失礼しました、f(1) に対して 4 が返ってきてほしいです！

Answer 1

read_char が数値を返したり関数を返したりするからややこしくなっている気がします。
常に関数オブジェクトを返すようにすれば良いのでは。

def read_char(c):
    if c == "x":
        return lambda x: x
    else:
        n = int(c)
        return lambda _: n

"x" を恒等関数に置き換えたのと同じように、"3" を定数関数に置き換えれば良いのです。
そして、呼び出すときは一律に引数を与えてやります。たとえ無視されるとしても。

def calc(s):
    lf = read_char(s[0])
    op = s[1]
    rf = read_char(s[2])

    def func(x):
        return calculator(lf(x), op, rf(x))

    return func

実質二行変更するだけで実現できました。使うのも簡単です。

f = calc("x+3")
print(f(1))      # => 4
print(f(4))      # => 7

Wandbox

Comments

[bighope]

ありがとうございます。定数関数にする発想はありませんでした。

Answer 2

これはなかなか難しい問題です。やっていることが小さいプログラミング言語を作ることと同じだからです。詳しいことは「ラムダ計算」や「コンパイラ 実装」、「抽象構文木」で検索するとでてくるでしょう。ここでは概要のみにとどめます。

まず単純な計算から考えます。

1 + 2

これはすぐにこう計算できるでしょう。

3

では次の例ではどうでしょうか。

x + 3

xの正体がわかりませんね。もしかしたらx = 4と外側で決まっていて

4 + 3
7

こうなるかもしれません。ありうる話です。こういったときのxを自由変数と呼びます。
さて、xは絶対に関数の引数として与えられる、つまり

f(x) = x + 3

と書けるとしましょう。この時のxを束縛変数と呼びます。xに具体的に値を入れたとします。

f(5) = 5 + 3 = 8

このときの動作を5を関数f(x)に適用したと呼びます。

大変雑ですが、以上の説明がラムダ計算の概要になります。この処理を実装することができれば意図した動作も実装できるでしょう。また、こういった計算の構造を表すには抽象構文木が便利です。まずは変数の含まない電卓から作成し、抽象構文木の理解から始めると良いでしょう。そしてラムダ計算について学び適用を抽象構文木で表すことができれば実装できます。

道のりは長いですが楽しいので頑張ってみてください。

Answer 3

ほとんど教科書通りのラムダ計算機を作ってみました。計算部分は純粋に関数だけで書かれています。

# 自然数とチャーチ数の相互変換
# チャーチ数とは自然数をネストした関数の数で定義したもの。
n2c = lambda n: (lambda a: lambda b: b) if n == 0 else (lambda f: lambda x: f(n2c(n - 1)(f)(x)))
c2n = lambda c: c(lambda n: n + 1)(0)


# 定数を関数で定義
ZERO = lambda f: lambda x: x # n2c(0)と同じ
ONE = lambda f: lambda x: f(x)
TRUE = lambda a: lambda b: a
FALSE = lambda a: lambda b: b

# n + 1を返す関数
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))
# n - 1を返す関数
PRED = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda u: x)(lambda u: u)

# Yコンビネータ
Y = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

# 条件分岐
IF = lambda cond: lambda t: lambda f: cond(t)(f)

# 算術演算子を関数で定義
PLUS = lambda m: lambda n: lambda f: lambda x: n(f)((m(f))(x))
MULT = lambda m: lambda n: lambda f: m(n(f))
SUB = lambda m: lambda n: n(PRED)(m)
DIV = Y(lambda f: lambda n: lambda m: IF(LE(m)(n))(lambda x: SUCC(f( SUB(n)(m) )(m))(x))(ZERO))

# 論理演算子を関数で定義。
IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)
# <=
LE = lambda n: lambda m: IS_ZERO(SUB(n)(m))



def calculator(x, op, y):
    if op == "+":
        return PLUS(x)(y)
    elif op == "-":
        return SUB(x)(y)
    elif op == "*":
        return MULT(x)(y)
    else:
        return DIV(x)(y)


def read_char(c):
    if c == "x":
        return lambda x: n2c(x)
    else:
        n = int(c)
        return lambda _: n2c(n)


def calc(s):
    lf = read_char(s[0])
    op = s[1]
    rf = read_char(s[2])

    def func(x):
        return calculator(lf(x), op, rf(x))

    return func

f = calc("x+3")
print(c2n(f(1)))

f = calc("3+4")
print(c2n(f(None)))

f = calc("9/3")
print(c2n(f(None)))

結果

4
7
3