30

可能な限り最小の言語インタープリターを作成しようとしました。参加して試してみませんか？

ゲームのルール：

  • 解釈しているプログラミング言語を指定する必要があります。あなたが発明した言語の場合は、コメントにコマンドのリストが含まれているはずです。
  • コードは、コードとデータ変数に割り当てられたサンプル プログラムとデータで開始する必要があります。
  • コードは、結果の出力で終了する必要があります。中間ステップごとに debug ステートメントがあることが望ましいです。
  • コードは記述どおりに実行できるはずです。
  • データは 0 と 1 (int、string、または boolean から選択) であり、出力は 1 ビットであると想定できます。
  • 言語は、チューリング マシン、マルコフ連鎖などの標準モデルで記述された任意のアルゴリズムについて、実行後にプログラムを作成する方法が合理的に明白 (または説明) であるという意味で、チューリング完全である必要があります。インタプリタによってアルゴリズムが実行されます。
  • コードの長さは、入力部分、出力部分、デバッグ ステートメント、および不要な空白を取り除いた後のコードの長さと定義されます。結果のコードとその長さを投稿に追加してください。
  • eval()など、コンパイラにコードを実行させる関数は使用できませんexec()。

これはコミュニティ Wiki です。つまり、質問も回答も投票から評判ポイントを得ることはありません。でもとにかく投票！

4

11 に答える 11

15

Python、250 バイト。

これは ilya n. の Python ソリューションよりも長いですが、言語は少し理解しやすいです。この言語 (ドイツ語で「壊れた」を意味するKaputtと呼びます) の各コマンドは 1 バイトです。次の 6 つのコマンドが定義されています。

  • 0: ゼロをスタックに積む
  • 1: スタックに 1 をプッシュします。
  • I: (if) スタックから値をポップします (0 または 1 でなければなりません)。1 の場合は、次のコード ブロックを (" i" まで) 実行します。ゼロの場合はブロックをスキップします。
  • i: (endif) if ブロックを終了し、ブロックが実行されなかった場合は 1 をプッシュします (" I" がゼロをポップしたため)。後者の説明については、以下を参照してください。
  • D: (def) 定義される関数の名前をスタックからポップし (以下を参照)、次のブロック (" d" まで) をその名前にバインドします。
  • d: (enddef) 関数定義を終了します。
  • その他の任意のバイト: この (1 バイト; ただし、以下の編集を参照) 名前で機能があるかどうかを確認します。その場合は、この関数を実行します。そうでない場合は、このバイトをスタックにプッシュして、 がすぐに使用できるようにしDます。

ネストされた if は正当です。ネストされた関数定義はそうではありません。i対応する if ブロックが実行されなかった場合にのみ (endif) が 1 をプッシュするという事実により、if/else/endif 構造に似た次のイディオムが可能になります。

# [code that left a one or zero on the stack]
I    # abbreviated "(" below
# [code to be run if it was a one]
0iI  # abbreviated "/" below
# [code to be run if it was a zero]
1iIi # abbreviated ")" below
# [continuing...]

コメント、改行、スペースなどは実際には許可されていないことに注意してください。

一般的な関数の例をいくつか示します。( / )これらは、上記の略語を使用します。

<D(/)d

<値を何にも使用せずにスタックからポップする関数 (pop) を定義します。

&D((1/0)/<0)d

&スタックの 2 つの値をポップし、両方の値が 1 の場合は 1 をプッシュし、それ以外の場合は 0 をプッシュする関数 (and) を定義します。

~D((11/10)/(01/00))d

スタックの上位 2 つの値を交換する関数~(swap) を定義します。

RD(R/<)d

Rスタックの一番上からすべての 1 を再帰的に削除し、さらに 2 つの値を削除する関数 (remove) を定義します(そのうちの一番上の値はゼロでなければなりません)。

次のインタープリター関数は、文字列 (またはその他の反復可能なバイト) であるプログラム p と、バイトの (おそらく空の) リストである入力スタック S を想定しています。インタープリターが実行された後、このリストには出力スタックが含まれます。

def i(p,S,F=0):
 A=S.append
 F=F or{}
 C=0
 k=[]
 for c in p:
  h=0in k
  if c=="d":C=0
  elif C!=0:C+=[c]
  elif c=="I":k+=[int(h or S.pop())]
  elif c=="i":k.pop()or A("1")
  elif 1-h:
   if c=="D":C=F[S.pop()]=[]
   else:i(F.get(c)or A(c)or"",S,F)

明らかに、エラー チェックの余地がなかったため、正当なKaputtコードがi()期待されます。テストケース:

script = "<D(/)d"                 # < = pop
script += "&D((1/0)/<0)d"         # & = and
script += "~D((11/10)/(01/00))d"  # ~ = swap
script += "RD(R/<)d"              # R = remove
script += "|D(<1/(1/0))d"         # | = or
script=script.replace("(","I")   
script=script.replace("/","0iI")
script=script.replace(")","1iIi") # ( and / and ) are no real commands of the language.

S=[]
i(script+"1111010111111111R",S)
assert S == ["1","1","1","1","0"]

S=[]
i(script+"00&",S)
assert S == ["0"]

S=[]
i(script+"01~",S)
assert S == ["1","0"]

S=[]
i(script+"00|",S)
assert S == ["0"]

S=[]
i(script+"01|",S)
assert S == ["1"]

幸せなコーディング:-)

編集:トークンを 1 バイトのみにすることを強制するインタープリター固有のものはありません。これを要求するのは、組み込みコマンド (インタープリターが短くなるため 1 バイトです) との一貫性のためです。文字列の代わりに文字列のリストを渡すと、次のようにより読みやすいKaputtコードを記述できます。

script = """
inc D
    (
        (
            0 0
        /
            1 0
        )
    /
        1
    )
d
""".replace("(","I").replace("/","0 i I").replace(")","1 i I i").split()

incこれは、スタックの一番上の 2 ビット数 (一番上の LSB) をインクリメントする関数を定義します。

テスト：

for n in xrange(4):
    S=[]
    i(script + [str((n & 2)/2), str(n & 1), "inc"], S)
    assert S == [str(((n+1) & 2)/2), str((n+1) & 1)]

マルチバイト関数名を言語拡張と呼びましょう :-)

于 2009-06-28T21:05:54.900 に答える
9

作成したばかりの言語を解釈する Python プログラム:

from random import randint
z = [randint(0,1), None]  # example: input data is 0 or 1
x = '_b_ed_a_i____d_ai'   # this program will set p = data[1] = not data[0]

# input x[i], data z[k]
# jumper j
# p is +1 or -1 each step
# commands:
#    a   set data = 0 or 1
#    b   j += 0 or +-9 depending on data
#    d   move data left or right
#    e   perform jump left or right
#    j   set jumper to 0
#    i   end program
# output: p or some data[x], both possible

g = globals()
p = i = 1
a = b = d = j = e = k = 0
while i:
    h = x[i]
    g[h] = p = -p
    i += 1 + j*e
    if a: z[k] = i % 2
    if z[k]: j += 9*b
    k += d
    g[h] = 0        
#    print(a, b, d, e, i, j, k, h, z)

print('Input:', z, 'Output:', p > 0)

最適化されたバージョン:

g=globals()
p=i=1
a=b=d=j=e=k=0
while i:
 h=x[i]
 g[h]=p=-p
 i+=1+j*e
 if a:z[k]=i%2
 if z[k]:j+=9*b
 k+=d
 g[h]=0

114バイト

更新:私のプログラムのポイントは、実用的な言語を作成することではなく、何らかの形で「最高の」(==「最短」) インタープリターを使用することでもなく、興味深いプログラミングのトリックを示すことであることを付け加えたいと思います。たとえば、私は を介し​​たグローバル変数への直接アクセスに依存してglobals()いるため、コマンドをテストすることさえなくj、貴重なバイトを節約できます:)

于 2009-06-28T00:38:26.590 に答える
9 
#include "/dev/tty"
于 2009-08-12T03:41:38.907 に答える
6

私のものではありませんが、210ビットバイナリ ラムダ計算セルフ インタープリターをご覧ください。

于 2009-08-09T18:29:24.793 に答える
4

Perlで書かれており、シェル呼び出しとフラグを含めて 140 文字です。

perl -ne'push@a,split;if(eof){$i=0;while($i>=0){($a,$b,$c)=@a[$i..$i+2];$b>-1?$a[$b]-=$a[$a]:print chr$a[$a];$i=$b>-1&&$a[$b]<=0?$c:$i+3;}}'

読み取り可能なバージョン:

#!/usr/bin/perl -n
push @prog, split /\s+/, $_;
if(eof) {
  $i = 0;
  while($i >= 0) {
    ($a, $b, $c) = @prog[$i .. $i + 2];
    if($b > -1) {
      $prog[$b] -= $prog[$a];
    } else {
      print chr $prog[$a];
    }
    if($b > -1 and $prog[$b] <= 0) {
      $i = $c;
    } else {
      $i + 3;
    }
  }
}

上記は、その命令を使用する1 つの命令セットのコンピューター用の疑似マシン コードのインタープリターですsubleq。基本的に、ソース コードは、空白で区切られた数字の集まりである必要があります。私の結果を確認するための簡単なテスト プログラム ("Hi" と Unix 改行を出力する必要があります):

0 0 6 72 105 10 3 -1 9 4 -1 12 5 -1 15 0 0 -1

テスト入力の読み取り可能なバージョン (同様に機能します):

0    0     6
72   105   10
3   -1     9
4   -1     12
5   -1     15
0    0    -1
于 2009-08-26T09:25:41.180 に答える
4

私自身のエントリ、Ruby でのOISCの実装。これは 85 バイトの長さであり、いくつかの巧妙なトリックを使用して、さらに数バイトを絞り込むことができると確信しています。プログラムには、コード (スペースで区切られた数字の行) にデータが含まれている必要があります。現時点では、OISC で書かれた動作するプログラムを提供することはできませんが、後で提供します。

p,m=0,gets.chomp.split.map(:to_i)
while p>0
p=(m[m[b]]-=m[m[a]])>0?p+3:c
end
$><<m[0]

コードは非常に簡単です。mプログラムとデータを含む「メモリ」です。最初の行mは、提供されたコードで初期化され、p- メモリ ポインター。メインループはsubleq三項演算子で書かれた演算です。最後の行は、メモリに含まれる数値を出力するスマートな方法です。

于 2009-08-26T09:36:16.153 に答える
2

以前の code-golf エントリーに基づいて構築された、(IO 用に少し一般化された) OISCエミュレーターを次に示します。

Fortran77

難読化され、読み込みスキャフォールドなし ( 655 文字):

  subroutine o(n,m)
  integer m(n)              
  l=1;                      
  do while (l.ne.0)
     i=m(l)
     j=m(l+1)
     k=m(l+2)
     mi=mg(n,m,i)
     mj=mg(n,m,j)
     if(j.eq.(n+2)) then
        write(6,*)mj-mi
     else
        m(l+1)=mj-mi
     endif
     if (m(l+1).lt.0) then
        l=mg(n,m,k)
     else
        l=l+3
     endif
  end do
  return
  end
  function mg(n,m,i)
  integer m(n)
  if (i.eq.n+2) then
     read(5,*)mg
  elseif (i.eq.n+1) then
     mg=0
  else
     mg=m(i)
  endif
  return
  end

コメント、足場の読み込みなど (2435 文字):

      program c
      parameter (n=1024)        ! The size to use for memeory
      integer m(n)              ! represent the memory
c     Load a program into memory
      i=1
 1    read(5,*,end=2)l
c     write (6,*) "Load ",l," into location ",i
      m(i)=l
      i=i+1
      goto 1
c     Run the computer
 2    call o(n,m)
      stop
      end

      subroutine o(n,m)
c     Simulate a simple computer that supports only a single
c     instruction. Memory is a fixed size array of integers.
c
c     The supported instruction is subtract-branch-negative which we
c     give the assembly syntax
c
c     sbn i j k
c
c     and acts by subtracting the value in memeory location i from that
c     in location j and storing the result in j. If the result is
c     negative, the PC is set to k. Because there is only one opcode, it
c     is not represented, so a program consists simply of a series of
c     triplet (i,j,k), and the PC is generally incremented by 3. The
c     program counter starts at 1
c
c     Povisions for IO and halting are by way of special memory
c     location:
c
c     * PC=0 means halt
c     * writes (opcode argument j) to memory location n+1 send
c       output, reads from n+1 evaluate as 0
c     * reads (opcode argument i, j, k) from memory location n+2 fetch
c       input, writes to n+2 are forbidden
c     * All others reads and writes outside of memeory are forbidden

c     n                         ! the size of the computers memory 
      integer m(n)              ! an array representing the computers memory
      l=1;                      ! program counter
      do while (l.ne.0)
         i=m(l)
         j=m(l+1)
         k=m(l+2)
c        write (6,*) "Executing from PC=",l,": (",i,", ",j,", ", k,")"
c        handle the write special case for output
         mi=mg(n,m,i)
         mj=mg(n,m,j)
         if(j.eq.(n+1)) then
            write(6,*)mj-mi
         else
c           write (6,*) "Setting location ",j," to ",mj-mi
            m(l+1)=mj-mi
         endif
         if (m(l+1).lt.0) then
            l=mg(n,m,k)
         else
            l=l+3
         endif
      end do
      return
      end

c     Handle the various read special cases
      function mg(n,m,i)
      integer m(n)
      if (i.eq.n+2) then
         read(5,*)mg
      elseif (i.eq.n+1) then
         mg=0
      else
         mg=m(i)
      endif
c     write (6,*) "Read ",mg," from location ",i
      return
      end

サンプルプログラム:

13
1025
0

14 
1025
0

14
15
0

0
0
0

-1
1
0

出力結果：

$ cat trivial.oisc | ./a.out 
           1
          -1

これは予想どおりです。

これは非常に単純なコードです。ここでのポイントは、どれだけ厳密にコード化できるかということではなく、Turing の完全性のためにどれだけ単純な言語が必要かということです。

于 2009-08-09T17:43:04.060 に答える
1

106バイトのソリューションがcodegolf.comコンテストに投稿されました。これはperlで書かれており、Brainfuckを解釈します。現時点では、それを確認する方法はありません、afaik。

これは私の解決策ではありませんが、現在のエントリよりも短いと思います。チューリング完全言語としてBrainfuckを使用する必要がないため、考えられる解決策は短くする必要があります。

于 2009-08-26T08:46:21.277 に答える
0

CoffeeScriptのURMインタープリター、 143 バイト(改行で 167 バイト)。

このバージョンの URM は、無制限の量のレジスターで構成されており、ゼロ、後続、およびジャンプ演算子があります。これがチューリング完全であることはよく知られています。

URM プログラムは配列c (コマンド) に記述され、入力は配列r(レジスタ) にあります。計算後、出力は にr[0]なり、この値が表示されます。

サンプル プログラムと 32+13 を計算する入力 (実際には 45 を出力する) を含むインタープリター:

# Addition program, similar to http://planetmath.org/examplesofunlimitedregistermachines
c = [['j', 1, 2, 4], ['s', 0], ['s', 2], ['j', 1, 1, 0]]

# Input: 32, 13, thus the desired output is: 45
r = [32, 13]

k = 0
while k < c.length
    t = c[k]
    k += 1
    if t[0] == 'z'
        r[t[1]] = 0
    if t[0] == 's'
        if !r[t[1]]?
            r[t[1]] = 0
        r[t[1]] += 1
    if t[0] == 'j' && r[t[1]] == r[t[2]]
        k = t[3]
alert r[0]

縮小版:

k=0
while k<c.length
 t=c[k]
 k+=1
 if t[0]=='z'
  r[t[1]]=0
 if t[0]=='s'
  if !r[t[1]]?
   r[t[1]]=0
  r[t[1]]+=1
 if t[0]=='j'&&r[t[1]]==r[t[2]]
  k=t[3]
alert r[0]

このコードで私が本当に気に入っているのは、非常に単純で理解しやすいことです。

于 2013-04-29T14:47:26.653 に答える
-1

カスタム言語: SLA
キーワード:
i - SLB を解釈する q - 終了する

カスタム言語: SLB
キーワード:
cp("text") - テキストを C プログラムとして解釈する

例:
cp("#include \nint main() { puts(\"Hi!\n\");return 0}")

通訳者 (SLA で記述): i q

3キャラ！

于 2009-08-12T03:26:04.710 に答える