Python Lispミニインタープリター

John Monganの著書 『 Programming Interviews Exposed 』の「Binary Trees」の章を読みながら、私は再帰が初心者プログラマーに最もよく説明される方法について考えました。 より興味深い例を見つけることは本当に不可能ですか？ Lispは意識の裏通りから脱出しました。それは本質的に、再帰の概念と不可分です。 さらに、小さなLispインタープリターは、再帰を探索するための素晴らしい例です。



Pythonで書かれた最小限のLispインタープリターは何ですか？ 驚いたことに、このソリューションは7行に収まりました！ Pythonの表現とLispの美しさと単純さの両方がこれに役割を果たしました。



最初に、式を計算する文法と方法を決定する必要があります。

list := (item0, item1, ...) item := list | atom atom := stringliteral | numliteral
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

計算規則は他のLisp方言と同じです：リストの最初の要素は関数で、残りは関数の引数です：

 fn = list[0] args = list[1:]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リストはPythonタプルの形式で記述されていることに注意してください。 このチートにより、字句解析および構文解析のタスクをPython自身の肩に移すことができます。 さらに、インタープリター自体には組み込みの演算子と特殊な形式は含まれていません。 これらはすべて拡張機能として追加できます。



インタプリタのコードとそれを拡張する関数に移る前に、いくつかの例を挙げましょう。

  (quote, 1, 2, 3) # >>> (1, 2, 3) (plus, 1, 2, 3) # >>> 6 (inc, 10) # >>> 11
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それで、きれいな歌詞、プログラミングに移りましょう！

Tiny Lispインタープリター

 def eval(list_or_atom): if isinstance(list_or_atom, tuple): #  ,   StreetStrider  Amper fn, *fn_args = [eval(item) for item in list_or_atom] return fn(*fn_args) else: return list_or_atom
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以上です！ そして、それは次のように機能します：

1. まず、入力のタイプをチェックします。それはアトムかリスト（この場合はタプル）ですか？ アトムの場合、その値は変更されずに返されます。 つまり 例： eval(1)
   
   
   
   は1
   
   
   
   を返します。
2. 引数がタプルの場合、リストの最初の要素を関数として、リストの他のすべての要素を関数の引数として示します。 この場合、各引数はeval()
   
   
   
   再帰呼び出しを使用して所定の場所で計算されます。

あなたは裸の通訳と一緒には行きません。 少し拡大してみましょう。

プラス

簡単な数学的加算関数から始めましょう。 さまざまなLisp方言では、追加は+



記号で示されます（どう思いますか？）ただし、Python構文の制限のため、 (+, 2, 3)



書くことはできません。 したがって、加算演算を単語plus



と呼びます。

 def plus(*args): """Sums up the input arguments.""" return sum(args) eval((plus, 3, 4, 5)) >>> 12 #   eval((plus, 3, (plus, 2, 10), 5)) >> 20
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

引用

Lispのデータからコードを分離するには、特別な形式の「引用」データquote



使用しquote



。 たとえば、Emacs-Lispでは： (quote 1 2 3)



。 このエントリは、データの前に単一引用符で引用符を書くことで短縮できます： '(1 2 3)



。 「引用」なしでは、Lispはこの式を次のように見なします： 1



は関数の名前、 2 3



は関数の引数であり、実行時エラーを引き起こします。 なぜなら Python構文では、単一引用符でデータを書き込むことはできません。関数としてquote



を使用する必要があります。

 def quote(*args): """Returns a list without evaluating it.""" return tuple(args) eval((quote, 'x', 3, 0.7)) >>> ('x', 3, 0.7) eval((quote, 1, 2, (quote, 3, 4))) >>> (1, 2, (3, 4))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

UPD： kmeawは、本格的なLispの引用では異なる動作をするはずであると非常に正確に指摘しました。リストの単一の要素は評価されません。 たとえば、Elispの場合：

 '(1 2 '(3 4)) >>> (1 2 (quote 3 4))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この記事の解説では、この欠点を修正するためのさまざまなオプションについて説明しています。

適用する

関数の入力がリスト形式のデータであるとします(plus, (quote, 1, 2, 3))



例(plus, (quote, 1, 2, 3))



。 私たちのインタープリターはこれを生き残りません。なぜなら、その内部ではすべてがsum([(1,2,3), ])



呼び出しで終わるからです Lispでこの状況を解決するために、 apply



関数がありapply



：

 def apply(fn, args): """Applies a function to a list of arguments.""" return fn(*args) eval((apply, plus, (quote, 1, 2, 3))) >>> 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

地図と株式会社

クラシックmap



機能なしの場所！ Mapはこの関数をこのリスト内の各要素に適用し、結果を新しいリストとして返します。 例： (map, inc, (quote, 1, 2, 3))



は(2, 3, 4)



(map, inc, (quote, 1, 2, 3))



返します。 ここで、 inc



はインクリメント関数です。たとえば、 (inc 10)



は11を返します。

 def map(fn, lst): """Applies the function to each element of the list and returns the results in a new list.""" return tuple(fn(item) for item in lst) def inc(arg): """Increases the argument by 1.""" return arg + 1 eval((map, inc, (quote, 1, 2, 3))) >> (2, 3, 4)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ラムダス

物語はラムダ式で終わります。 Python構文を使用すると、ラムダ関数の本体内でeval()



を自動的に呼び出すことはできません。

 eval((map, lambda x: (plus, x, 1), (quote, 1, 2, 3)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

動作しない、なぜなら 式(plus, x, 1)



評価されません。 希望する結果を得るには、ラムダ関数の本体を次のように書き換えます。

 eval((map, lambda x: eval(plus, x, 1), (quote, 1, 2, 3)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

もちろん、これは構文シーケンスに違反します。



このインタープリターは、他の多数の便利な関数で拡張できます。 しかし、何といっても、Pythonの構文と本格的なLipsによって制限されることはありません。



あなたがあなた自身のために新しくて有用な何かを学んだこと、そしてLispをブラケットの複雑なセットとして考えたHabravitesが彼らの意見を再考することを願っています:)