Skip to content

Instantly share code, notes, and snippets.

@youz
Last active August 9, 2021 06:40
Show Gist options
  • Save youz/15a965d62bbc5f6ae924681b85bce697 to your computer and use it in GitHub Desktop.
Save youz/15a965d62bbc5f6ae924681b85bce697 to your computer and use it in GitHub Desktop.
Grass with call/cc extension ( forked from https://github.com/youz/grasses/blob/master/Ruby3/grass.rb )
#!/usr/bin/ruby
#
# grass.rb - Grass interpreter
# with call/cc extension
# http://www.blue.sky.or.jp/grass/
#
# Copyright (C) 2020-2021 Yousuke Ushiki All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions and the following disclaimer in
# the documentation and/or other materials provided with the
# distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
# BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
# OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
# IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
require 'pp'
class Grass
App = Struct.new(:fun, :arg)
Abs = Struct.new(:arity, :code)
Fn = Struct.new(:arity, :code, :env)
Cont = Struct.new(:dump)
Succ = ->(c){ c.succ & 0xff }
Out = ->(c){ putc(c); c }
In = ->(eof){ ch = $stdin.read(1); ch ? ch.ord : eof }
ChurchTrue = ->(x){->(y){ x }}
ChurchFalse = ->(x){->(y){ y }}
DebugPrint = ->(v){ pp v }
private
def eval(code, env, dump)
pc = 0
while true
if pc == code.length
ret = env[0]
if dump.empty?
return ret
end
code, env, pc = dump.pop
env = [ret] + env
else
insn = code[pc]
case insn
when App
f, a = env[insn.fun-1], env[insn.arg-1]
if f == :CallCC
f = Fn.new(1, [App.new(2, 1)], [a])
a = Cont.new(dump + [[code, env, pc]])
end
case f
when Fn
if f.arity == 1
if pc < code.length - 1
dump.push [code, env, pc+1]
end
code, env, pc = f.code, f.env, -1
val = a
else
val = Fn.new(f.arity-1, f.code, [a] + f.env)
end
when Integer
val = f == a ? ChurchTrue : ChurchFalse
when Proc
val = f[a]
when Cont
dump = f.dump.dup
code, env, pc = dump.pop
val = a
end
when Abs
val = Fn.new(insn.arity, insn.code, env)
end
env = [val] + env
pc += 1
end
end
end
def parse(src)
src.tr("\uFF37\uFF57\uFF56","Wwv").gsub(/[^Wwv]/, "").sub(/\A[^w]*/, "")
.split(/v+/).map {|s|
l = s.scan(/w+|W+/).map(&:size)
arity = s[0] == 'w' ? l.shift : 0
code = l.each_slice(2).map{|m, n|
raise "syntax error" unless n
App.new(m, n)
}
arity > 0 ? [Abs.new(arity, code)] : code
}.flatten(1)
end
public
def run(src)
code = parse(src)
e0 = [Out, Succ, 'w'.ord, In, :CallCC, DebugPrint]
d0 = [[[App.new(1, 1)], [], 0]]
eval(code, e0, d0)
end
end
if $0 == __FILE__ then
if $*.length == 0
puts "usage: ruby grass.rb <source.grass>"
exit
end
Grass.new.run $<.read
end
wwwv # let f _ x y = y
wWWWWWWww # let echo self = let c = In f in
Ww # let b = c c in
Wwwwww # let _ = b Out b c in
Www
Wwwww
WWWWwwwwww # let t = b self in
Ww # let u = t t in
Wwwwwwwwwv # u self
Ww # echo echo
wv # let id x = x
WWWWWWwv # let jmp = call/cc id
wWWWWWWWw # let echo k = let c = In k in
Ww # let _ = c c in
WWWWWWww # let _ = Out c in
WWWWWwwwwwv # jmp jmp
wWWWWWWWWWww # let main _ = call/cc echo
wv id x = x
WWWWWWw jmp = call/cc id
WWWwwwww _ = out 119
WWww _ = jmp jmp
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment