Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Seem like GolfScript wins all of these. So you can't beat them, join them.

Write an Self-Contained Golfscript Interpreter

I'm using the definition of self-contained to mean, a single program:- So no passing the buck to some external program to do the work for you.

Test Cases:

Strings and blocks are represented as lists of ASCII codes. Types are not checked with these tests, but should be right anyway.

test("[50] [60]+", [[50, 60]]);
test("{a} {b}+", [[97, 32, 98]]);
test("'a' 'b'+", [[97, 98]]);

test("' ' 0+", [[32, 48]]);
test("' ' [50]+", [[32, 50]]);

test("{a} 0+", [[97, 32, 48]]);
test("{a} [50]+", [[97, 32, 53, 48]]);

test("5 ~", [-6]);
test('"1 2+"~', [3]);
test('{1 2+}~', [3]);
test('[1 2 3]~', [1, 2, 3]);

test('1`', [[49]]);
test("[1 [2] 'asdf']`", [[91, 49, 32, 91, 50, 93, 32, 34, 97, 115, 100, 102, 34, 93]]);
test('"1"`', [[34, 49, 34]]);
test("{1}`", [[123, 49, 125]]);

test("0!", [1]);
test("[]!", [1]);
test("{}!", [1]);
test("''!", [1]);

test("5!", [0]);
test("[[]]!", [0]);
test("{{}}!", [0]);
test("'asdf'!", [0]);

test("1 2 3 4 @", [1, 3, 4, 2]);

test("1 # 2", [1]);

test("1 2 3 4 5 1 $", [1, 2, 3, 4, 5, 4]);
test("'asdf' $", [[97, 100, 102, 115]]);
test("[5 4 3 1 2]{-1*}$", [[5, 4, 3, 2, 1]]);

test("5 7 +", [12]);
test("'a'{b}+", [[97, 32, 98]]);
test("[1 2 3][4 5]+", [[1, 2, 3, 4, 5]]);

test("1 2-3+", [1, -1]);
test("1 2 -3+", [1, -1]);
test("1 2- 3+", [2]);
test("[5 2 5 4 1 1][1 2]-", [[5, 5, 4]]);

test("2 4*", [8]);
test("2 {2*} 5*", [64]);
test("[1 2 3]2*", [[1, 2, 3, 1, 2, 3]]);
test("3'asdf'*", [[97,115,100,102,97,115,100,102,97,115,100,102]]);

test("[1 2 3]' '*", [[49, 32, 50, 32, 51]]);
test("[1 2 3][4]*", [[1,4,2,4,3]]);
test("'asdf'' '*", [[97,32,115,32,100,32,102]]);
test("[1 [2] [3 [4 [5]]]]' '*", [[49, 32, 2, 32, 3, 4, 5]]);
test("[1 [2] [3 [4 [5]]]][6 7]*", [[1, 6, 7, 2, 6, 7, 3, [4, [5]]]]);

test("[1 2 3 4]{+}*", [10]);
test("'asdf'{+}*", [414]);

test("7 3 /", [2]);
test("[1 2 3 4 2 3 5][2 3]/", [[[1], [4], [5]]]);
test("[1 2 3 4 5] 2/", [[[1, 2], [3, 4], [5]]]);

test("0 1 {10<} { .@+ } /", [8, [1, 1, 2, 3, 5, 8]]);
test("[1 2 3]{1+}/", [2, 3, 4]);

test("7 3 %", [1]);

test("'assdfs' 's'%", [[[97], [100, 102]]]);
test("'assdfs' 's'/", [[[97], [], [100, 102], []]]);

test("[1 2 3 4 5] 2%", [[1, 3, 5]]);
test("[1 2 3 4 5] -1%", [[5, 4, 3, 2, 1]]);
test("[1 2 3] {1+}%", [[2, 3, 4]]);

test("5 3 |", [7]);
test("[5 5 1] [1 3] |", [[5, 1, 3]]);

test("5 3 &", [1]);
test("[1 1 2 2][1 3]&", [[1]]);

test("5 3 ^", [6]);
test("[1 1 2 2][1 3]^", [[2, 3]]);

test("1 2 [\\]", [[2, 1]]);

test("1 2 3 \\", [1, 3, 2]);
test("1 2 3; ", [1, 2]);

test("3 4 <", [1]);
test('"asdf" "asdg" <', [1]);
test("[1 2 3] 2 <", [[1, 2]]);
test("{asdf} -1 <", [[97, 115, 100]]);

test("3 4 >", [0]);
test('"asdf" "asdg" >', [0]);
test("[1 2 3] 2 >", [[3]]);
test("{asdf} -1 >", [[102]]);

test("3 4 =", [0]);
test('"asdf" "asdg" =', [0]);
test("[1 2 3] 2 =", [3]);
test("{asdf} -1 =", [102]);

test("3,", [[0,1,2]]);
test("10,,", [10]);
test("10,{3%},", [[1, 2, 4, 5, 7, 8]]);

test("1 2 .", [1,2,2]);

test("2 8?", [256]);
test(" 5 [4 3 5 1] ?", [2]);
test(" 6 [4 3 5 1] ?", [-1]);

test("[1 2 3 4 5 6] {.* 20>} ?", [5]);

test("5(", [4]);
test("[1 2 3](", [[2, 3], 1]);

test("5)", [6]);
test("[1 2 3])", [[1, 2], 3]);

test("5 {1 0/} or", [5]);
test("5 {1 1+} and", [2]);
test("0 [3] xor", [[3]]);
test("2 [3] xor", [0]);

test("5{1-..}do", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}while", [4, 3, 2, 1, 0, 0]);
test("5{.}{1-.}until", [5]);

test("1 2 3 if", [2]);
test("0 2 {1.} if", [1, 1]);

test("[[1 2 3][4 5 6][7 8 9]]zip", [[[1, 4, 7], [2, 5, 8], [3, 6, 9]]]);

test("[1 1 0] 2 base", [6]);
test("6 2 base", [[1, 1, 0]]);
share|improve this question
3  
Warning to anyone who would try this: it's a very big task if you're not using a language closely related to Ruby. –  Peter Taylor Sep 3 '12 at 19:47
    
@PeterTaylor Where would you say the best documentation is for someone attempting this task? Is it the golfscript.com site, or would it be better to just dig into the golfscript.rb source itself? –  Gareth Sep 3 '12 at 21:05
1  
Would you get extra points for writing it in Golfscript? –  Mr Lister Sep 3 '12 at 21:54
3  
You know, for a task this complex the question-asker really ought to post a good set of test cases... –  Peter Taylor Sep 4 '12 at 6:40
4  
Do we have to support ruby's string evaluation, like "The time is #{Time.now}" ? How about arbitrary precision numbers ? –  copy Sep 4 '12 at 14:41

2 Answers 2

up vote 6 down vote accepted

Ruby, 5490 bytes

Well, I can golf the GolfScript interpreter from 8283 bytes down to 5490 ...

$m=[];class G;def g;$k<<self;end;def v;@v;end
'+-|&^'.each_byte{|i|eval'def%c(r);if r.class!=self.class
a,b=u(r);a%c b;else;f(@v%c r.v);end;end'%([i]*3)}
def==(r);@v==r.v;end;def eql?(r);@v==r.v;end;def hash
@v.hash;end;def<=>(r);@v<=>r.v;end;end;class H<G;def
initialize(i);@v=case i;when true then 1;when false then 0
else;i;end;end;def f(a);H.new(a);end
def t;J.new(@v.to_s);end;def to_int#for pack
@v;end;def s;t;end;def N;0;end;def u(b);[if b.class==I
I.new([self]);elsif b.class==J;t;else#K
t.to_s.w;end,b];end;def~;H.new(~@v);end;def R;H.new(@v==0)
end;'*/%<>'.each_byte{|i|eval'def%c(r);H.new(@v%c r.v)
end'%[i,i]};def E(r);H.new(@v==r.v);end;def q(b)
H.new(@v**b.v);end;def B(a);if I===a;r=0;a.v.each{|i|r*=@v
r+=i.v};H.new(r);else;i=a.v.abs;r=[];while i!=0;r.unshift
H.new(i%@v);i/=@v;end;I.new(r);end;end;def n;H.new(@v-1);end;def
p;H.new(@v+1);end;end;class I<G;def initialize(a);@v=a;end;def
f(a);I.new(a);end;def t;@v.inject(J.new("")){|s,i|s+i.t};end
def F#maybe name to_a ?
I.new(@v.inject([]){|s,i|s+case i;when J then i.v;when H then[i]
when I then i.F.v;when K then i.v;end});end;def s
J.new('[')+I.new(@v.map{|i|i.s})*J.new(' ')+J.new(']');end;def
g;$k<<self;end;def N;1;end;def u(b);if b.class==H
b.u(self).reverse;elsif b.class==J;[J.new(self),b];else
[(self*J.new(' ')).to_s.w,b];end;end;def n;[f(@v[1..-1]),@v[0]]
end;def p;[f(@v[0..-2]),@v[-1]];end;def*(b);if b.class==H
f(@v*b.v);else;return b*self if self.class==J&&b.class==I;return
self/H.new(1)*b if self.class==J;return;b.f([])if@v.size<1
r=@v.first;r,x=r.u(b)if r.class!=b.class#for size 1
@v[1..-1].each{|i|r=r+b+i};r;end;end;def/(b);if b.class==H
r=[];a=b.v<0 ?@v.reverse: @v;i=-b=b.v.abs
r<<f(a[i,b])while(i+=b)<a.size;I.new(r);else;r=[];i=b.f([])
j=0;while j<@v.size;if@v[j,b.v.size]==b.v;r<<i;i=b.f([])
j+=b.v.size;else;i.v<<@v[j];j+=1;end;end;r<<i;I.new(r);end;end
def%(b);if b.class==H;b=b.v
f((0..(@v.size-1)/b.abs).inject([]){|s,i|s<<@v[b<0 ?i*b-1:i*b]})
else;self/b-I.new([I.new([])]);end;end;def R;H.new(@v.empty?)
end;def q(b);H.new(@v.index(b)||-1);end;def E(b);b.class==H ?
@v[b.v] : H.new(@v==b.v);end;def<(b);b.class==H ? f(@v[0..b.v]):
H.new(@v<b.v);end;def>(b);b.class==H ?
f(@v[[b.v,-@v.size].max..-1]) : H.new(@v>b.v);end;def sort
f(@v.sort);end;def T;r=[];@v.size.times{|x|@v[x].v.size.times{|y|
(r[y]||=@v[0].f([])).v<<@v[x].v[y]}};I.new(r);end;def~;v;end;end
class J<I;def initialize(a);@v=case a;when String then
a.unpack('C*').map{|i|H.new(i)};when Array then a;when I then
a.F.v;end;end;def f(a);J.new(a);end;def t;self;end;def s
f(to_s.inspect);end;def to_s;@v.pack('C*');end;def N;2;end
def u(b);b.class==K ? [to_s.w,b]:b.u(t).reverse;end;def q(b)
if b.class==J;H.new(to_s.index(b.to_s)||-1);elsif b.class==I
b.q(t);else;H.new(@v.index(b)||-1);end;end;def~;to_s.w.g;nil;end
end;class K<I;def initialize(a,b=nil);@v=J.new(b).v
@n=eval("lambda{#{a}}");end;def g;@n.call;end;def f(b)
J.new(b).to_s.w;end;def N;3;end;def t;J.new("{"+J.new(@v).to_s+"}")
end;def s;t;end;def u(b);b.u(self).reverse;end;def+(b);if
b.class!=self.class;a,b=u(b);a+b;else
J.new(@v+J.new(" ").v+b.v).to_s.w;end;end;def*(b);if b.class==H
b.v.times{g};else;z b.v.first;(b.v[1..-1]||[]).each{|i|$k<<i;g}
end;nil;end;def/(b);if b.class==I||b.class==J;b.v.each{|i|z i;g}
nil;else#unfold
r=[];loop{$k<<$k.last;g;break if y.R.v!=0;r<<$k.last;b.g}
y;I.new(r);end;end;def%(b);r=[];b.v.each{|i|m=$k.size
$k<<i;g;r.concat($k.slice!(m..$k.size))};r=I.new(r)
J==b.class ? J.new(r):r;end;def~;g;nil;end
def sort;a=y;a.f(a.v.sort_by{|i|z i;g;y});end
def C(a);a.f(a.v.C{|i|z i;g;y.R.v==0});end
def q(b);b.v.find{|i|z i;g;y.R.v==0};end;end
class NilClass;def g;end;end
class Array;def^(r);self-r|r-self;end;include Comparable;end
e=gets(nil)||'';Q=$stdin;$_=Q.isatty ? '':Q.read;$k=[J.new($_)]
$l={};def x(name,v=nil);eval"#{s="$_#{$l[name]||=$l.size}"}||=v"
s;end;$j=0
class String;def W;K.new(self);end;def X;('a=y;'+self).W;end
def Y;('b=y;a=y;'+self).W;end;def Z;('c=y;b=y;a=y;'+self).W;end
def o;('b=y;a=y;a,b=b,a if a.N<b.N;'+self).W;end;def
w(a=scan(/[a-zA-Z_][a-zA-Z0-9_]*|'(?:\\.|[^'])*'?|"(?:\\.|[^"])*"?|-?[0-9]+|#[^\n\r]*|./m))
b=a.dup;c="";while t=a.slice!(0);c<<case t
when"{"then"$k<<"+x("{#{$j+=1}",w(a));when"}"then break
when":"then x(a.slice!(0))+"=$k.last"
when/^["']/ then x(t,J.new(eval(t)))+".g"
when/^-?[0-9]+/ then x(t,H.new(t.to_i))+".g"
else;x(t)+".g";end+"\n";end
d=b[0,b.size-a.size-(t=="}"?1:0)]*"";K.new(c,d);end;end
def y;($m.size-1).downto(0){|i|break if$m[i]<$k.size;$m[i]-=1}
$k.pop;end;def z a;$k.push(*a)if a;end
x'[','$m<<$k.size'.W;x']','z I.new($k.slice!(($m.pop||0)..-1))'.W
x'~','z~a'.X;x'`','z a.s'.X;x';',''.X;x'.','$k<<a<<a'.X
x'\\','$k<<b<<a'.Y;x'@','$k<<b<<c<<a'.Z;x'+','z a+b'.Y
x'-','z a-b'.Y;x'|','z a|b'.Y;x'&','z a&b'.Y;x'^','z a^b'.Y
x'*','z a*b'.o;x'/','z a/b'.o;x'%','z a%b'.o;x'=','z a.E(b)'.o
x'<','z a<b'.o;x'>','z a>b'.o;x'!','z a.R'.X
x'?','z a.q(b)'.o;x'$','z(a.class==H ? $k[~a.v]:a.sort)'.X
x',','z case a;when H then I.new([*0...a.v].map{|i|H.new(i)})
when K then a.C(y);when I then H.new(a.v.size);end'.X
x')','z a.p'.X;x'(','z a.n'.X
x'rand','z H.new(rand([1,a.v].max))'.X;x'abs','z H.new(a.v.abs)'.X
x'print','print a.t'.X;x'if',"#{x'!'}.g;(y.v==0?a:b).g".Y
x'do',"loop{a.g;#{x'!'}.g;break if y.v!=0}".X
x'while',"loop{a.g;#{x'!'}.g;break if y.v!=0;b.g}".Y
x'until',"loop{a.g;#{x'!'}.g;break if y.v==0;b.g}".Y
x'zip','z a.T'.X;x'base','z b.B(a)'.Y
'"\n":n;{print n print}:puts;{`puts}:p;{1$if}:and;{1$\if}:or;{\!!{!}*}:xor;'.w.g
e.w.g;z I.new($k);'puts'.w.g
share|improve this answer

Javascript, 2227 bytes

@Peter Taylor: Challenge Accepted!

_='S=b9b?b^3?"{"+)+"}":\'"\'+)+\'"\':"["+b6SB" ")+"]":""+b};$=b||!b99b:[b]b6$B""L;M=b9$(bb+""};A=b?(gb.charCodeAt(0)A(b1))v=g,v=3,g,v};C=b9(k=b6Ck=b,kb};a=g,s,O,r=Wj,uX,d,c,i,yPb=(b?$(bb+"").match(/\'(.|[^\'])*\'|"(.|[^"])*"|-?\\d+|\\043[^\\n]*|[a-z_]\\w*|./imgFi=y=0;z=b[i++];)"{"Yz?!y++Zk=iy?"}"Yz!--yZe=A(bk,i-1B""))e=4\'"\'YzQ?A(eval(z.replace("\\n","n")))"\'"YzQ?A(z1,-1).replace(/(|\')/g,"$1"))":"Yz?r[b[i++]]=(d=s[s-1])^4?S(dd:r[z]?r[z]z+"."-0.1?eval(z)eval("//~t;t98?ts=st~t\\140A(S(G)))//[O.uns]JEt,u@`vEuX,v%`I!u)t%u!tPt3?[32]:[]Xu+tV-5!~tc)RcL# q-t/`I!u)Math.floot/u)!tPv=0;j%tY0ZvRvv,vvcdvLu^4Pp=1 ITPFd;\'.\'u;)ds[s-1]tGdL#{D;HL//*7I!t)q*t!uPFd;u--;)T?td=dCUd=8;T||dL8^4P!u8Zu6M)6A)d=dC(j?t:[]cd=8;GdL#{q.)HL//zipt;Fv=c;v--;)!d[v]Zd[v]d[v]c[v]?7IT)HG)Zcu# t9tuMath.pow(uX)$t;u=0;t9(T?(u=t,G)t).sort(uZaua,bubb-a}C(s~t)Q)=`t!9ut)Q:0|$(u)Y$U>N$U|0:t0Xu>t|0V)K()]:[t+1](K.)]:[t-1]&5v;~tc)vc   &t|5dvt |t^5v;k,ut!~tc)^!~kc)vc ^tif`v=?u:t;v^4?A(S(v)v!+!randMath.random()*G)|0)".split("//"+z)[1]L,\'{1$if}:and{1$if}:or{!!{!}*}:xor{..0sZOQ=sFfoGs(HctIif(Js.splice(O.))Kt;s=st9[tXL)}N`q9t9$(u)P){Q[0]RdT8>3U(t)V8//Wfunction(b,X,tY==Z(`;qu';for(Y=0;$='q`ZYXWVUTRQPNLKJIHGFEDB98765#  '[Y++];)with(_.split($))_=join(pop());eval(_)

Note: Contains some control characters, nothing outside of ASCII though. Here's a direct link to the file: gs.js. The code provides a function a which takes the Golfscript code as a single parameter and returns the resulting stack as an array, with strings and blocks represented as ASCII.

Differences from the official interpreter:

  • Numbers have only 53 bits precision
  • No exact output and no direct print (would be easy to add though)
  • Double quoted strings are parsed using Javascript's eval, which might work different than Ruby's. Also no access to Ruby functions via strings
  • Undefined behaviour (I tried my very best)

I've also made a bunch of test cases and set up a small form for running Golfscript code: http://copy.sh/golfscript/

Here are some examples:

This is my standard Golfscript library, suggestions are welcome:

{1$if}:and
{1$\\if}:or
{\!!{!}*}:xor
{..0<2**-}:abs
{\{!}+\while}:until
{0$}:.
"\n":n
{\.[]*{0{2$*\(@+1$}do@;\;}{[{.@.@\\%@@.@\/.}do;;]-1%}if}:base
];
share|improve this answer
    
;[1 2]{+}* seems to loop forever rather than evaluating almost instantly to 3. Everything else I've tried so far has worked. Will do some more testing later. –  Peter Taylor Nov 3 '12 at 8:11
    
;[1 2]{+}* works for me (also all of the test cases pass), but this bug might appear because of global state. I'm looking into it ... –  copy Nov 3 '12 at 14:43
    
And a small issue that numbers are not treated as variables: 11:10 10 * does not show 121 as it should. Also it seems to handle the empty stack inconsistently: ;5 p 4 * p should not work at all but gives 20. –  Howard Nov 4 '12 at 8:17
    
@Howard numeric variables should work now. The other thing does not run as expected because p is not defined –  copy Nov 4 '12 at 13:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.