Skip to content

Instantly share code, notes, and snippets.

@plasma-effect

plasma-effect/Program.cs

Last active April 4, 2019 12:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save plasma-effect/a2f67a157de434801492e30a32a2a750 to your computer and use it in GitHub Desktop.
Save plasma-effect/a2f67a157de434801492e30a32a2a750 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
_readme.md

Recursion Functionの定義にそって関数を書いた時どういう挙動するか見たいな～
↓
でもtemplateですると書くの面倒だな～
↓
じゃあテキストで定義できるようにしよう
↓
これ

コマンド

関数定義

def <funcname>(<arguments>)=<definition>

出力

print <expression>

ファイル読み込み

load <filename>

table出力

table <filename> <funcname> <firstval> <lastval> <othervals>

関数定義について

基本の関数

def basic1(x) = succ(x)
def basic2(x) = x

合成

def compose(x) = basic1(basic1(x))

原始再帰

def add(x, y) = pr{y}(x, succ(this))
def fun(x, y) = pr{x}(y, add(this, x))

f(x,succ(y)) = h(x,y,f(x,y))のf(x,y)に相当するのがthis
後者の例はfun(succ(x),y)=add(f(x,y),x)に相当する

最小作用素

def prev(x) = pr{x}(0, x)
def sub(x, y)= pr{y}(x, prev(this))
def add(x, y)= pr{y}(x, succ(this))
def twice(x) = add(x, x)
def min2(x) = mu{z}(sub(x, twice(z)))

エラーについて

めっちゃ雑なので注意

意見要望エラー報告について

@plasma_eまで

Raw
Program.cs
//#define _DEBUG
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
namespace RecursiveFunction
{
class Program
{
interface RF
{
BigInteger Run(BigInteger[] args);
int Size { get; }
bool HasVariable(int index);
}
class Composite : RF
{
public RF[] funcs;
public RF func;
public int Size
{
get
{
int ret = 0;
foreach(var f in funcs)
{
ret = Math.Max(ret, f.Size);
}
return ret;
}
}
public bool HasVariable(int index)
{
foreach(var f in funcs)
{
if(f.HasVariable(index))
{
return true;
}
}
return false;
}
public BigInteger Run(BigInteger[] args)
{
var v = new BigInteger[funcs.Length];
for(int i = 0; i < funcs.Length; ++i)
{
v[i] = funcs[i].Run(args);
}
return func.Run(v);
}
public Composite(RF bfunc,RF[] afuncs)
{
funcs = afuncs;
func = bfunc;
}
}
class Succ : RF
{
RF func;
public BigInteger Run(BigInteger[] args)
{
return func.Run(args) + 1;
}
public bool HasVariable(int index)
{
return func.HasVariable(index);
}
public Succ(RF func)
{
this.func = func;
}
public int Size => func.Size;
}
class Variable : RF
{
int index;
public int Size => index + 1;
public BigInteger Run(BigInteger[] args)
{
return args[index];
}
public bool HasVariable(int index)
{
return index == this.index;
}
public Variable(int index)
{
this.index = index;
}
}
class Constant : RF
{
public BigInteger value;
public int Size => 0;
public BigInteger Run(BigInteger[] args)
{
return value;
}
public bool HasVariable(int index)
{
return false;
}
public Constant(BigInteger value)
{
this.value = value;
}
}
class PRcursion : RF
{
RF init;
RF next;
int index;
public int Size => Math.Max(init.Size + 1, next.Size - 1);
public BigInteger Run(BigInteger[] args)
{
var vals = new BigInteger[Size + 1];
Array.Copy(args, vals, Size);
vals[Size] = init.Run(args);
if (vals[index] != 0 && !next.HasVariable(Size))
{
--vals[index];
return next.Run(vals);
}
for (vals[index] = 0; vals[index] != args[index]; ++vals[index])
{
vals[Size] = next.Run(vals);
}
return vals.Last();
}
public bool HasVariable(int index)
{
return index == this.index || init.HasVariable(index) || next.HasVariable(index);
}
public PRcursion(RF init,RF next,int index)
{
this.init = init;
this.next = next;
this.index = index;
}
}
class Minimam : RF
{
public RF func;
public int Size => func.Size - 1;
public BigInteger Run(BigInteger[] args)
{
if (!func.HasVariable(func.Size - 1))
{
if (func.Run(args) == 0)
{
return 0;
}
else
{
throw new ArgumentOutOfRangeException("params", "this function can't stop");
}
}
var vals = new BigInteger[Size + 1];
Array.Copy(args, vals, Size);
while (func.Run(vals) != 0)
{
++vals[Size];
}
return vals[Size];
}
public bool HasVariable(int index)
{
return func.HasVariable(index);
}
public Minimam(RF func)
{
this.func = func;
}
}
class Extend : RF
{
RF func;
int size;
public int Size => size;
public bool HasVariable(int index)
{
return func.HasVariable(index);
}
public BigInteger Run(BigInteger[] args)
{
return func.Run(args);
}
public Extend(RF func,int size)
{
this.func = func;
this.size = size;
}
}
static int? isnumber(string str, int beg, out int val)
{
if ('0' <= str[beg] && str[beg] <= '9')
{
for(int i = beg; i < str.Length; ++i)
{
if (!('0' <= str[i] && str[i] <= '9'))
{
val = int.Parse(str.Substring(beg, i - beg));
return i - 1;
}
}
val = int.Parse(str.Substring(beg));
return str.Length - 1;
}
val = 0;
return null;
}
static bool IsAlpha(char c)
{
return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
}
static bool IsNumber(char c)
{
return ('0' <= c && c <= '9');
}
static bool IsToken(char c)
{
return IsNumber(c) || IsAlpha(c) || (c == '_');
}
static void Skip(string str, ref int index, Func<char, bool> cond)
{
for (; index < str.Length; ++index)
{
if (!cond(str[index]))
{
return;
}
}
}
static void Check(string str,int index,Func<char,bool> cond)
{
if (str.Length == index || !cond(str[index]))
{
throw new Exception("parsing error");
}
}
class DefineParser
{
string str;
int index;
Dictionary<string, RF> funcs;
public DefineParser(string str,Dictionary<string,RF> funcs,int index = 4)
{
this.str = str;
this.funcs = funcs;
this.index = index;
}
public void Run()
{
var s = Name();
if (s.name == "mu" || s.name == "pr" || s.name == "this")
{
throw new Exception("invalid function name");
}
if (s.argument.Count == 0)
{
EvalParser eval = new EvalParser(str, funcs, index);
funcs.Add(s.name, new Constant(eval.Run()));
}
else
{
funcs.Add(s.name,new Extend(Definition(s.argument),s.argument.Count));
}
Console.WriteLine("definition [{0}] was succeed:argument={1}", s.name, s.argument.Count);
}
public RF Definition(Dictionary<string, int> argument)
{
Skip(str, ref index, c => c == ' ');
if (IsAlpha(str[index]))
{
int start = index;
Skip(str, ref index, IsToken);
string target = str.Substring(start, index - start);
Skip(str, ref index, c => c == ' ');
int val;
if (argument.TryGetValue(target,out val))
{
return new Variable(val);
}
RF func;
if(funcs.TryGetValue(target,out func))
{
if (func.Size == 0)
{
return func;
}
else
{
Check(str, index, c => c == '(');
var fs = new RF[func.Size];
for (int i = 0; i < func.Size - 1; ++i)
{
++index;
Skip(str, ref index, c => c == ' ');
fs[i] = Definition(argument);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ',');
}
++index;
Skip(str, ref index, c => c == ' ');
fs[func.Size - 1] = Definition(argument);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ')');
++index;
return new Composite(func, fs);
}
}
if (target == "mu")
{
return DefinitionMu(argument);
}
if (target == "pr")
{
return DefinitionPR(argument);
}
}
else if (IsNumber(str[index]))
{
int start = index;
Skip(str, ref index, IsNumber);
return new Constant(BigInteger.Parse(str.Substring(start, index - start)));
}
throw new Exception("parsing error");
}
private RF DefinitionPR(Dictionary<string, int> argument)
{
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '{');
++index;
Skip(str, ref index, c => c == ' ');
Check(str, index, IsAlpha);
int start = index;
Skip(str, ref index, IsToken);
string valname = str.Substring(start, index - start);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '}');
++index;
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '(');
++index;
int s = argument.Count;
int _;
if (!argument.TryGetValue(valname, out _))
{
throw new Exception("variable error");
}
argument.Remove(valname);
RF init = Definition(argument);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ',');
++index;
argument.Add(valname, _);
argument.Add("this", s);
RF next = Definition(argument);
argument.Remove("this");
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ')');
++index;
return new PRcursion(init, next, _);
}
public RF DefinitionMu(Dictionary<string, int> argument)
{
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '{');
++index;
Skip(str, ref index, c => c == ' ');
Check(str, index, IsAlpha);
int start = index;
Skip(str, ref index, IsToken);
string valname = str.Substring(start, index - start);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '}');
++index;
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '(');
++index;
int s = argument.Count;
int _;
if(argument.TryGetValue(valname,out _))
{
throw new Exception("variable error");
}
argument.Add(valname, s);
RF inside = Definition(argument);
argument.Remove(valname);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ')');
++index;
return new Minimam(inside);
}
public (string name,Dictionary<string,int> argument) Name()
{
Skip(str, ref index, c => c == ' ');
if (!IsAlpha(str[index]))
{
throw new Exception("function name must start alphabet");
}
int start = index;
Skip(str, ref index, IsToken);
string name = str.Substring(start, index - start);
Skip(str, ref index, c => c == ' ');
Dictionary<string, int> argument = new Dictionary<string, int>();
if (str[index] == '(')
{
int count = 0;
while (true)
{
++index;
Skip(str, ref index, c => c == ' ');
Check(str, index, IsAlpha);
int startn = index;
Skip(str, ref index, IsToken);
argument.Add(str.Substring(startn, index - startn), count++);
Skip(str, ref index, c => c == ' ');
Check(str, index, c => true);
if (str[index] == ',')
{
continue;
}
else if (str[index] == ')')
{
++index;
break;
}
}
}
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == '=');
++index;
return (name, argument);
}
}
class EvalParser
{
int index;
string str;
Dictionary<string, RF> funcs;
public EvalParser(string str,Dictionary<string,RF> funcs,int index = 6)
{
this.index = index;
this.str = str;
this.funcs = funcs;
}
public BigInteger Run()
{
Skip(str, ref index, (c) => c == ' ');
if (IsAlpha(str[index]))
{
int start = index;
Skip(str, ref index, IsToken);
var f = funcs[str.Substring(start, index - start)];
var size = f.Size;
Skip(str, ref index, (c) => c == ' ');
return f.Run(size == 0 ? new BigInteger[0] : FuncRun(size));
}
if (IsNumber(str[index]))
{
int start = index;
Skip(str, ref index, IsNumber);
return BigInteger.Parse(str.Substring(start, index - start));
}
throw new Exception("parsing error");
}
BigInteger[] FuncRun(int size)
{
var arg = new BigInteger[size];
Check(str, index, (c) => c == '(');
for (int i = 0; i < size - 1; ++i)
{
++index;
arg[i] = Run();
Skip(str, ref index, (c) => c == ' ');
Check(str, index, c => c == ',');
}
++index;
arg[size - 1] = Run();
Skip(str, ref index, c => c == ' ');
Check(str, index, c => c == ')');
++index;
return arg;
}
}
static void Main(string[] args)
{
var funcs = new Dictionary<string, RF>();
funcs.Add("succ", new Succ(new Variable(0)));
while (true)
{
var str = Console.ReadLine();
#if !_DEBUG
try
{
#endif
if (str.Length >= 4 && str.Substring(0, 4) == "def ")
{
var parser = new DefineParser(str, funcs);
parser.Run();
}
else if (str.Length >= 6 && str.Substring(0, 6) == "print ")
{
var parser = new EvalParser(str, funcs);
Console.WriteLine(parser.Run());
}
else if (str.Length >= 6 && str.Substring(0, 5) == "load ")
{
var filename = str.Split(' ')[1];
using (var fs = new System.IO.StreamReader(filename))
{
string data;
while (fs.Peek() > -1)
{
data = fs.ReadLine();
Console.WriteLine(data);
if (data.Length >= 4 && data.Substring(0, 4) == "def ")
{
var parser = new DefineParser(data, funcs);
parser.Run();
}
else if (data.Length >= 6 && data.Substring(0, 6) == "print ")
{
var parser = new EvalParser(data, funcs);
Console.WriteLine(parser.Run());
}
}
}
}
else if (str.Split(' ').Length >= 5 && str.Split(' ')[0] == "table")
{
var ns = str.Split(' ');
var func = funcs[ns[2]];
using (var fs = new System.IO.StreamWriter(ns[1]))
{
var start = BigInteger.Parse(ns[3]);
var end = BigInteger.Parse(ns[4]);
var arg = new BigInteger[ns.Length - 4];
for(var i = 0; i < arg.Length - 1; ++i)
{
arg[i + 1] = BigInteger.Parse(ns[i + 5]);
}
for(var i = start; i <= end; ++i)
{
arg[0] = i;
fs.WriteLine("{0},{1}", i, func.Run(arg));
}
}
}
else if (str == "end")
{
break;
}
else
{
throw new Exception("command error");
}
#if !_DEBUG
}
catch (Exception exp)
{
Console.Error.WriteLine(exp.Message);
}
#endif
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment