Python - プログラムと機械 - プログラムの意味 - 操作的意味論(式、文、スモールステップ、仮想機械(virtual machine))

アンダースタンディング コンピュテーション
(オライリージャパン)
Tom Stuart (著) 笹田 耕一(著) 笹井 崇司 (翻訳)
原書

開発環境

• OS X El Capitan - Apple (OS)
• Emacs(Text Editor)
• Python 3.5 (プログラミング言語)

アンダースタンディング コンピュテーション (Tom Stuart (著)、 笹田 耕一(著)、笹井 崇司 (翻訳)、オライリージャパン)の第1部(プログラムと機械)、1章(プログラムの意味)、2.3(操作的意味論)、2.3.1(スモールステップ意味論)、2.3.1.1(式)、2.3.1.2(文)を Python (本書ではRuby) で取り組んでみる。

2.3.1.1(式)、2.3.1.2(文)

コード(Emacs)

sample1.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class Number:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return False

class Add:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} + {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self):        
        if self.left.is_reducibale():
            return Add(self.left.reduce(), self.right)
        if self.right.is_reducibale():
            return Add(self.left, self.right.reduce())
        return Number(self.left.value + self.right.value)
    
class Multiply:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} * {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self):
        if self.left.is_reducibale():           
            return Multiply(self.left.reduce, self.right)
        if self.right.is_reducibale():
            return Multiply(self.left, self.right.reduce)
        return Number(self.left.value * self.right.value)

class Machine:
    def __init__(self, expression):
        self.expression = expression

    def step(self):
        self.expression = self.expression.reduce()

    def run(self):
        while self.expression.is_reducibale():
            print(self.expression)
            self.step()
        print(self.expression)

class Boolean:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return False

class LessThan:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} < {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self):
        if self.left.is_reducibale():
            return LessThan(self.left.reduce(), self.right)
        if self.right.is_reducibale():
            return LessThan(self.left, self.right.reduce())
        return Boolean(self.left.value < self.right.value)
        
if __name__ == '__main__':
    print(Number(1).is_reducibale())
    print(Add(Number(1), Number(2)).is_reducibale())
    print()
    
    expression = Add(Multiply(Number(1), Number(2)),
                     Multiply(Number(3), Number(4)))
    print(expression)
    while expression.is_reducibale():
        expression = expression.reduce()
        print(expression)
    print()
    Machine(Add(Multiply(Number(1), Number(2)),
                Multiply(Number(3), Number(4)))).run()
    print()
    
    Machine(LessThan(Number(5), Add(Number(2), Number(2)))).run()

入出力結果(Terminal, IPython))

$ ./sample1.py
False
True

1 * 2 + 3 * 4
2 + 3 * 4
2 + 12
14

1 * 2 + 3 * 4
2 + 3 * 4
2 + 12
14

5 < 2 + 2
5 < 4
False
$

sample2.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class Number:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return False

class Add:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} + {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):        
        if self.left.is_reducibale():
            return Add(self.left.reduce(environment), self.right)
        if self.right.is_reducibale():
            return Add(self.left, self.right.reduce(environment))
        return Number(self.left.value + self.right.value)
    
class Multiply:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} * {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.left.is_reducibale():           
            return Multiply(self.left.reduce, self.right)
        if self.right.is_reducibale():
            return Multiply(self.left, self.right.reduce)
        return Number(self.left.value * self.right.value)

class Machine:
    def __init__(self, expression, environment):
        self.expression = expression
        self.environment = environment

    def step(self):
        self.expression = self.expression.reduce(self.environment)

    def run(self):
        while self.expression.is_reducibale():
            print(self.expression)
            self.step()
        print(self.expression)

class Boolean:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return False

class LessThan:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} < {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.left.is_reducibale():
            return LessThan(self.left.reduce(environment), self.right)
        if self.right.is_reducibale():
            return LessThan(self.left, self.right.reduce(environment))
        return Boolean(self.left.value < self.right.value)
        
class Variable:
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return str(self.name)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        return environment[self.name]

class DoNothing:
    def __str__(self):
        return 'do-nothing'

    def __repr__(self):
        return '<<{}>>'.format(self)

    def __eq__(self, other):
        return type(other) == type(self)

    def is_reducibale(self):
        return False

class Assign:
    def __init__(self, name, expression):
        self.name = name
        self.expression = expression

    def __str__(self):
        return '{0} = {1}'.format(self.name, self.expression)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.expression.is_reducibale():
            return [Assign(self.name, self.expression.reduce(environment)),
                    environment]
        new_environment = environment.copy()
        new_environment.update({self.name:self.expression})
        return [DoNothing(), new_environment]

if __name__ == '__main__':
    Machine(Add(Variable('x'), Variable('y')),
            dict(x=Number(3), y=Number(4))).run()
    print()

    old_environment = {'y':Number(5)}
    print(old_environment)

    new_environment = old_environment.copy()
    new_environment.update({'x': Number(3)})
    print(new_environment)
    print(old_environment)
    print()
    
    statement = Assign('x', Add(Variable('x'), Number(1)))
    print(statement)
    environment = {'x': Number(2)}
    print(environment)
    print(statement.is_reducibale())
    statement, environment = statement.reduce(environment)
    print(statement, environment)
    statement, environment = statement.reduce(environment)
    print(statement, environment)
    statement, environment = statement.reduce(environment)
    print(statement, environment)
    print(statement.is_reducibale())

入出力結果(Terminal, IPython))

$ ./sample2.py
x + y
3 + y
3 + 4
7

{'y': <<5>>}
{'y': <<5>>, 'x': <<3>>}
{'y': <<5>>}

x = x + 1
{'x': <<2>>}
True
x = 2 + 1 {'x': <<2>>}
x = 3 {'x': <<2>>}
do-nothing {'x': <<3>>}
False
$

sample3.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class Number:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return False

class Add:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} + {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):        
        if self.left.is_reducibale():
            return Add(self.left.reduce(environment), self.right)
        if self.right.is_reducibale():
            return Add(self.left, self.right.reduce(environment))
        return Number(self.left.value + self.right.value)
    
class Multiply:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} * {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.left.is_reducibale():           
            return Multiply(self.left.reduce(environment), self.right)
        if self.right.is_reducibale():
            return Multiply(self.left, self.right.reduce(environment))
        return Number(self.left.value * self.right.value)

class Machine:
    def __init__(self, statement, environment):
        self.statement = statement
        self.environment = environment

    def step(self):
        self.statement, self.environment = \
            self.statement.reduce(self.environment)

    def run(self):
        while self.statement.is_reducibale():
            print('{0}, {1}'.format(self.statement, self.environment))
            self.step()
        print('{0}, {1}'.format(self.statement, self.environment))

class Boolean:
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def __eq__(self, other):
        return type(self) == type(other) and self.value == other.value
    def is_reducibale(self):
        return False

class LessThan:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __str__(self):
        return '{0} < {1}'.format(self.left, self.right)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.left.is_reducibale():
            return LessThan(self.left.reduce(environment), self.right)
        if self.right.is_reducibale():
            return LessThan(self.left, self.right.reduce(environment))
        return Boolean(self.left.value < self.right.value)
        
class Variable:
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return str(self.name)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        return environment[self.name]

class DoNothing:
    def __str__(self):
        return 'do-nothing'

    def __repr__(self):
        return '<<{}>>'.format(self)

    def __eq__(self, other):
        return type(other) == type(self)

    def is_reducibale(self):
        return False

class Assign:
    def __init__(self, name, expression):
        self.name = name
        self.expression = expression

    def __str__(self):
        return '{0} = {1}'.format(self.name, self.expression)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.expression.is_reducibale():
            return [Assign(self.name, self.expression.reduce(environment)),
                    environment]
        new_environment = environment.copy()
        new_environment.update({self.name:self.expression})
        return [DoNothing(), new_environment]

class If:
    def __init__(self, condition, consequence, alternative):
        self.condition = condition
        self.consequence = consequence
        self.alternative = alternative

    def __str__(self):
        return 'if ({0}) {{ {1} }}  else {{ {2} }}'.format(
            self.condition, self.consequence, self.alternative)

    def __repr__(self):
        return '<<{0}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.condition.is_reducibale():
            return [
                If(self.condition.reduce(environment), self.consequence,
                   self.alternative),
                environment]
        if self.condition == Boolean(True):
            return [self.consequence, environment]
        if self.condition == Boolean(False):
            return [self.alternative, environment]

class Sequence:
    def __init__(self, first, second):
        self.first = first
        self.second = second

    def __str__(self):
        return '{0}; {1}'.format(self.first, self.second)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        if self.first == DoNothing():
            return [self.second, environment]
        reduced_first, reduced_environment = self.first.reduce(environment)
        return [Sequence(reduced_first, self.second), reduced_environment]

class While:
    def __init__(self, condition, body):
        self.condition = condition
        self.body = body

    def __str__(self):
        return 'while ({0}) {{ {1} }}'.format(self.condition, self.body)

    def __repr__(self):
        return '<<{}>>'.format(self)

    def is_reducibale(self):
        return True

    def reduce(self, environment):
        return [If(self.condition, Sequence(self.body, self), DoNothing()),
                environment]
        
if __name__ == '__main__':
    Machine(Assign('x', Add(Variable('x'), Number(1))), {'x': Number(2)}).run()
    print()

    Machine(If(Variable('x'), Assign('y', Number(1)), Assign('y', Number(2))),
            {'x':Boolean(True)}).run()
    print()

    Machine(If(Variable('x'), Assign('y', Number(1)), DoNothing()),
            {'x': Boolean(False)}).run()
    print()

    Machine(Sequence(Assign('x', Add(Number(1), Number(1))),
                     Assign('y', Add(Variable('x'), Number(3)))),
            {}).run()
    print()

    Machine(While(LessThan(Variable('x'), Number(5)),
                  Assign('x', Multiply(Variable('x'), Number(3)))),
            {'x':Number(1)}).run()

入出力結果(Terminal, IPython))

$ ./sample3.py
x = x + 1, {'x': <<2>>}
x = 2 + 1, {'x': <<2>>}
x = 3, {'x': <<2>>}
do-nothing, {'x': <<3>>}

if (x) { y = 1 }  else { y = 2 }, {'x': <<True>>}
if (True) { y = 1 }  else { y = 2 }, {'x': <<True>>}
y = 1, {'x': <<True>>}
do-nothing, {'y': <<1>>, 'x': <<True>>}

if (x) { y = 1 }  else { do-nothing }, {'x': <<False>>}
if (False) { y = 1 }  else { do-nothing }, {'x': <<False>>}
do-nothing, {'x': <<False>>}

x = 1 + 1; y = x + 3, {}
x = 2; y = x + 3, {}
do-nothing; y = x + 3, {'x': <<2>>}
y = x + 3, {'x': <<2>>}
y = 2 + 3, {'x': <<2>>}
y = 5, {'x': <<2>>}
do-nothing, {'y': <<5>>, 'x': <<2>>}

while (x < 5) { x = x * 3 }, {'x': <<1>>}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<1>>}
if (1 < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<1>>}
if (True) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<1>>}
x = x * 3; while (x < 5) { x = x * 3 }, {'x': <<1>>}
x = 1 * 3; while (x < 5) { x = x * 3 }, {'x': <<1>>}
x = 3; while (x < 5) { x = x * 3 }, {'x': <<1>>}
do-nothing; while (x < 5) { x = x * 3 }, {'x': <<3>>}
while (x < 5) { x = x * 3 }, {'x': <<3>>}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<3>>}
if (3 < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<3>>}
if (True) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<3>>}
x = x * 3; while (x < 5) { x = x * 3 }, {'x': <<3>>}
x = 3 * 3; while (x < 5) { x = x * 3 }, {'x': <<3>>}
x = 9; while (x < 5) { x = x * 3 }, {'x': <<3>>}
do-nothing; while (x < 5) { x = x * 3 }, {'x': <<9>>}
while (x < 5) { x = x * 3 }, {'x': <<9>>}
if (x < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<9>>}
if (9 < 5) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<9>>}
if (False) { x = x * 3; while (x < 5) { x = x * 3 } }  else { do-nothing }, {'x': <<9>>}
do-nothing, {'x': <<9>>}
$