समानता के लिए सरल अज्ञात पायथन कार्यों का परीक्षण करने के लिए एक ह्युरिस्टिक विकसित करना

Question

मुझे पता है कि फ़ंक्शन तुलना पाइथन 3 (केवल स्मृति में पता की तुलना में) में कैसे काम करती है, और मैं समझता हूं कि क्यों।

मैं यह भी समझता हूं कि "सत्य" तुलना (f और g कार्य करता है, वही परिणाम देता है, किसी भी तर्क के लिए, समान तर्क देता है?) व्यावहारिक रूप से असंभव है।

मैं बीच में कुछ ढूंढ रहा हूं। मैं तुलना समान कार्यों का सरलतम मामलों पर काम करना चाहता है, और संभवतः कुछ कम तुच्छ लोगों:

lambda x : x == lambda x : x # True 
lambda x : 2 * x == lambda y : 2 * y # True 
lambda x : 2 * x == lambda x : x * 2 # True or False is fine, but must be stable 
lambda x : 2 * x == lambda x : x + x # True or False is fine, but must be stable 

ध्यान दें कि मैं गुमनाम कार्य (lambda) के लिए इस समस्या को हल करने में रुचि है, लेकिन कोई फ़र्क नहीं पड़ेगा अगर समाधान नामित कार्यों के लिए भी काम करता है।

इसके लिए प्रेरणा यह है कि blist मॉड्यूल के अंदर, यह सत्यापित करना अच्छा होगा कि दो sortedset उदाहरणों पर यूनियन करने से पहले एक ही तरह का कार्य होता है।

नामित फ़ंक्शंस कम रुचि वाले हैं क्योंकि मैं उन्हें अलग होने पर अलग मान सकता हूं। आखिरकार, मान लें कि किसी ने key तर्क में नामित फ़ंक्शन के साथ दो सॉर्टिडेट बनाए हैं। यदि वे इन परिचालनों को सेट ऑपरेशंस के प्रयोजनों के लिए "संगत" होने का इरादा रखते हैं, तो वे संभवतः एक ही कार्य का उपयोग करेंगे, दो अलग-अलग नामित फ़ंक्शंस जो समान संचालन करते हैं।

मैं केवल तीन दृष्टिकोणों के बारे में सोच सकता हूं। वे सभी कड़ी मेहनत करते हैं, इसलिए किसी भी विचार की सराहना की।

1. तुलना bytecodes काम हो सकता है, लेकिन यह कष्टप्रद है कि यह कार्यान्वयन निर्भर है हो सकता है (और इसलिए कोड है कि एक अजगर पर काम किया दूसरे पर टूट जाता है)।

2. टोकनयुक्त स्रोत कोड की तुलना करना उचित और पोर्टेबल लगता है। बेशक, यह कम शक्तिशाली है (क्योंकि समान कार्यों को अस्वीकार करने की अधिक संभावना है)।

3. कुछ प्रतीकात्मक गणना पाठ्यपुस्तक से उधार ली गई एक ठोस ह्युरिस्टिक सैद्धांतिक रूप से सबसे अच्छी दृष्टिकोण है। यह मेरे उद्देश्य के लिए बहुत भारी प्रतीत हो सकता है, लेकिन यह वास्तव में एक अच्छा फिट हो सकता है क्योंकि लैम्ब्डा फ़ंक्शन आमतौर पर छोटे होते हैं और इसलिए यह तेज़ दौड़ जाएगा।

संपादित

एक अधिक जटिल उदाहरण, @delnan द्वारा टिप्पणी के आधार पर:

# global variable 
fields = ['id', 'name'] 

def my_function(): 
    global fields 
    s1 = sortedset(key = lambda x : x[fields[0].lower()]) 
    # some intervening code here 
    # ... 
    s2 = sortedset(key = lambda x : x[fields[0].lower()]) 

मैं s1 और s2 के लिए महत्वपूर्ण कार्य के रूप में बराबर का मूल्यांकन करने के लिए उम्मीद करेंगे?

यदि हस्तक्षेप कोड में कोई फ़ंक्शन कॉल शामिल है, तो fields का मान संशोधित किया जा सकता है, जिसके परिणामस्वरूप s1 और s2 के लिए विभिन्न महत्वपूर्ण कार्य होते हैं। चूंकि हम स्पष्ट रूप से इस समस्या को हल करने के लिए नियंत्रण प्रवाह विश्लेषण नहीं करेंगे, इसलिए यह स्पष्ट है कि हमें इन दो लैम्ब्डा कार्यों को अलग-अलग मूल्यांकन करना होगा, अगर हम रनटाइम से पहले इस मूल्यांकन को करने का प्रयास कर रहे हैं। (भले ही fields वैश्विक नहीं था, हो सकता है कि इसका कोई दूसरा नाम हो, आदि) यह इस पूरे अभ्यास की उपयोगिता को गंभीर रूप से कम करेगा, क्योंकि कुछ लैम्ब्डा कार्यों में पर्यावरण पर कोई निर्भरता नहीं होगी।

संपादित करें 2:

मुझे एहसास हुआ कि यह के रूप में वे क्रम में मौजूद समारोह वस्तुओं की तुलना करने के लिए बहुत महत्वपूर्ण है। इसके बिना, बाहरी कार्यक्षेत्र से चर पर निर्भर सभी कार्यों की तुलना नहीं की जा सकती है; और सबसे उपयोगी कार्यों में ऐसी निर्भरताएं होती हैं। रनटाइम में माना जाता है, एक ही हस्ताक्षर वाले सभी कार्यों को एक साफ, तार्किक तरीके से तुलनात्मक रूप से तुलनात्मक रूप से तुलनात्मक रूप से तुलनात्मक रूप से तुलनात्मक, तार्किक तरीके से तुलनीय है, चाहे वे अशुद्ध हैं, आदि

नतीजतन, मुझे केवल बाइटकोड की आवश्यकता नहीं है बल्कि यह भी वैश्विक स्थिति उस समय के रूप में जब कार्य ऑब्जेक्ट बनाया गया था (संभवतः __globals__)। फिर मुझे __globals__ से बाहरी दायरे से सभी चरों से मिलान करना होगा।

Answer 1

यह जांचने के लिए संपादित किया गया है कि बाहरी राज्य सॉर्टिंग फ़ंक्शन को प्रभावित करेगा या साथ ही यदि दोनों कार्य समकक्ष हैं।

---

मैं एक वैश्विक फ़ाइल जैसी वस्तु को dis.dis और उत्पादन के लिए दोस्तों को हैक कर लिया। तब मैंने रेखा संख्याओं और सामान्यीकृत चर नामों को हटा दिया (स्थिरांक को छूए बिना) और परिणाम की तुलना की।

आप इसे dis.dis और दोस्तों yield एड आउट लाइनों को साफ़ कर सकते हैं ताकि आपको उनके आउटपुट को फँसाना पड़े। लेकिन यह कम से कम परिवर्तनों के साथ फ़ंक्शन तुलना के लिए dis.dis का उपयोग करने के लिए एक कामकाजी प्रमाण-अवधारणा है।

import types 
from opcode import * 
_have_code = (types.MethodType, types.FunctionType, types.CodeType, 
       types.ClassType, type) 

def dis(x): 
    """Disassemble classes, methods, functions, or code. 

    With no argument, disassemble the last traceback. 

    """ 
    if isinstance(x, types.InstanceType): 
     x = x.__class__ 
    if hasattr(x, 'im_func'): 
     x = x.im_func 
    if hasattr(x, 'func_code'): 
     x = x.func_code 
    if hasattr(x, '__dict__'): 
     items = x.__dict__.items() 
     items.sort() 
     for name, x1 in items: 
      if isinstance(x1, _have_code): 
       print >> out, "Disassembly of %s:" % name 
       try: 
        dis(x1) 
       except TypeError, msg: 
        print >> out, "Sorry:", msg 
       print >> out 
    elif hasattr(x, 'co_code'): 
     disassemble(x) 
    elif isinstance(x, str): 
     disassemble_string(x) 
    else: 
     raise TypeError, \ 
       "don't know how to disassemble %s objects" % \ 
       type(x).__name__ 

def disassemble(co, lasti=-1): 
    """Disassemble a code object.""" 
    code = co.co_code 
    labels = findlabels(code) 
    linestarts = dict(findlinestarts(co)) 
    n = len(code) 
    i = 0 
    extended_arg = 0 
    free = None 
    while i < n: 
     c = code[i] 
     op = ord(c) 
     if i in linestarts: 
      if i > 0: 
       print >> out 
      print >> out, "%3d" % linestarts[i], 
     else: 
      print >> out, ' ', 

     if i == lasti: print >> out, '-->', 
     else: print >> out, ' ', 
     if i in labels: print >> out, '>>', 
     else: print >> out, ' ', 
     print >> out, repr(i).rjust(4), 
     print >> out, opname[op].ljust(20), 
     i = i+1 
     if op >= HAVE_ARGUMENT: 
      oparg = ord(code[i]) + ord(code[i+1])*256 + extended_arg 
      extended_arg = 0 
      i = i+2 
      if op == EXTENDED_ARG: 
       extended_arg = oparg*65536L 
      print >> out, repr(oparg).rjust(5), 
      if op in hasconst: 
       print >> out, '(' + repr(co.co_consts[oparg]) + ')', 
      elif op in hasname: 
       print >> out, '(' + co.co_names[oparg] + ')', 
      elif op in hasjrel: 
       print >> out, '(to ' + repr(i + oparg) + ')', 
      elif op in haslocal: 
       print >> out, '(' + co.co_varnames[oparg] + ')', 
      elif op in hascompare: 
       print >> out, '(' + cmp_op[oparg] + ')', 
      elif op in hasfree: 
       if free is None: 
        free = co.co_cellvars + co.co_freevars 
       print >> out, '(' + free[oparg] + ')', 
     print >> out 

def disassemble_string(code, lasti=-1, varnames=None, names=None, 
         constants=None): 
    labels = findlabels(code) 
    n = len(code) 
    i = 0 
    while i < n: 
     c = code[i] 
     op = ord(c) 
     if i == lasti: print >> out, '-->', 
     else: print >> out, ' ', 
     if i in labels: print >> out, '>>', 
     else: print >> out, ' ', 
     print >> out, repr(i).rjust(4), 
     print >> out, opname[op].ljust(15), 
     i = i+1 
     if op >= HAVE_ARGUMENT: 
      oparg = ord(code[i]) + ord(code[i+1])*256 
      i = i+2 
      print >> out, repr(oparg).rjust(5), 
      if op in hasconst: 
       if constants: 
        print >> out, '(' + repr(constants[oparg]) + ')', 
       else: 
        print >> out, '(%d)'%oparg, 
      elif op in hasname: 
       if names is not None: 
        print >> out, '(' + names[oparg] + ')', 
       else: 
        print >> out, '(%d)'%oparg, 
      elif op in hasjrel: 
       print >> out, '(to ' + repr(i + oparg) + ')', 
      elif op in haslocal: 
       if varnames: 
        print >> out, '(' + varnames[oparg] + ')', 
       else: 
        print >> out, '(%d)' % oparg, 
      elif op in hascompare: 
       print >> out, '(' + cmp_op[oparg] + ')', 
     print >> out 

def findlabels(code): 
    """Detect all offsets in a byte code which are jump targets. 

    Return the list of offsets. 

    """ 
    labels = [] 
    n = len(code) 
    i = 0 
    while i < n: 
     c = code[i] 
     op = ord(c) 
     i = i+1 
     if op >= HAVE_ARGUMENT: 
      oparg = ord(code[i]) + ord(code[i+1])*256 
      i = i+2 
      label = -1 
      if op in hasjrel: 
       label = i+oparg 
      elif op in hasjabs: 
       label = oparg 
      if label >= 0: 
       if label not in labels: 
        labels.append(label) 
    return labels 

def findlinestarts(code): 
    """Find the offsets in a byte code which are start of lines in the source. 

    Generate pairs (offset, lineno) as described in Python/compile.c. 

    """ 
    byte_increments = [ord(c) for c in code.co_lnotab[0::2]] 
    line_increments = [ord(c) for c in code.co_lnotab[1::2]] 

    lastlineno = None 
    lineno = code.co_firstlineno 
    addr = 0 
    for byte_incr, line_incr in zip(byte_increments, line_increments): 
     if byte_incr: 
      if lineno != lastlineno: 
       yield (addr, lineno) 
       lastlineno = lineno 
      addr += byte_incr 
     lineno += line_incr 
    if lineno != lastlineno: 
     yield (addr, lineno) 

class FakeFile(object): 
    def __init__(self): 
     self.store = [] 
    def write(self, data): 
     self.store.append(data) 

a = lambda x : x 
b = lambda x : x # True 
c = lambda x : 2 * x 
d = lambda y : 2 * y # True 
e = lambda x : 2 * x 
f = lambda x : x * 2 # True or False is fine, but must be stable 
g = lambda x : 2 * x 
h = lambda x : x + x # True or False is fine, but must be stable 

funcs = a, b, c, d, e, f, g, h 

outs = [] 
for func in funcs: 
    out = FakeFile() 
    dis(func) 
    outs.append(out.store) 

import ast 

def outfilter(out): 
    for i in out: 
     if i.strip().isdigit(): 
      continue 
     if '(' in i: 
      try: 
       ast.literal_eval(i) 
      except ValueError: 
       i = "(x)" 
     yield i 

processed_outs = [(out, 'LOAD_GLOBAL' in out or 'LOAD_DECREF' in out) 
          for out in (''.join(outfilter(out)) for out in outs)] 

for (out1, polluted1), (out2, polluted2) in zip(processed_outs[::2], processed_outs[1::2]): 
    print 'Bytecode Equivalent:', out1 == out2, '\nPolluted by state:', polluted1 or polluted2 

उत्पादन True, True, False, और False है और स्थिर है। "प्रदूषित" बूल सत्य है यदि आउटपुट बाहरी राज्य पर निर्भर करेगा - या तो वैश्विक स्थिति या बंद होना।

Answer 2

तो, चलिए कुछ तकनीकी मुद्दों को पहले संबोधित करते हैं।

1) बाइट कोड: शायद यह कोई समस्या नहीं है क्योंकि, पीईसी (बाइनरी फाइल) का निरीक्षण करने के बजाय, आप "बाइटकोड" प्राप्त करने के लिए dis मॉड्यूल का उपयोग कर सकते हैं। जैसे

>>> f = lambda x, y : x+y 
>>> dis.dis(f) 
    1   0 LOAD_FAST    0 (x) 
       3 LOAD_FAST    1 (y) 
       6 BINARY_ADD   
       7 RETURN_VALUE 

प्लेटफ़ॉर्म के बारे में चिंता करने की आवश्यकता नहीं है।

2) टोकनयुक्त स्रोत कोड। फिर पाइथन में आपको नौकरी करने की ज़रूरत है। कोड को पार्स करने और अस्थिर प्राप्त करने के लिए आप ast मॉड्यूल का उपयोग कर सकते हैं।

>>> a = ast.parse("f = lambda x, y : x+y") 
>>> ast.dump(a) 
"Module(body=[Assign(targets=[Name(id='f', ctx=Store())], value=Lambda(args=arguments(args=[Name(id='x', ctx=Param()), Name(id='y', ctx=Param())], vararg=None, kwarg=None, defaults=[]), body=BinOp(left=Name(id='x', ctx=Load()), op=Add(), right=Name(id='y', ctx=Load()))))])" 

तो, सवाल हम वास्तव में पता है चाहिए: निर्धारित यह संभव है करने के लिए है कि दो कार्यों बराबर विश्लेषणात्मक कर रहे हैं?

यह कहना आसान है कि x+x के बराबर है, लेकिन हम इसे साबित करने के लिए एल्गोरिदम कैसे बना सकते हैं?

यदि यह आप क्या हासिल करना चाहते है, तो आप इस बाहर की जाँच कर सकते हैं: http://en.wikipedia.org/wiki/Computer-assisted_proof

हालांकि, अगर अंत में आप बस दो अलग-अलग डेटा सेट पर जोर करना चाहते हैं उसी क्रम में हल कर रहे हैं, तो आप सिर्फ करने की जरूरत है सॉर्ट फ़ंक्शन ए को डेटासेट बी पर चलाएं और इसके विपरीत, और फिर परिणाम देखें। यदि वे समान हैं, तो कार्य शायद कार्यात्मक रूप से समान हैं। बेशक, चेक केवल डेटासेट के लिए मान्य है।