ラムダ計算と無限ラムダ多項式(1)

「関数プログラミングと無限論理多項式」でLisp の簡単な処理系を作ってクロージャーの調査をしようとしたのですが、Lisp で動作確認をするのはたいへんそうなので、まずは C# の例から徐々に Lisp 風に移行していきたいと思います。ラムダ式で書くと Lisp に移行しやすくなると思ったのですが、この方向からはあまり進展しそうになかったので、C# の例の中にラムダ計算風のものを取り入れていこうと思います。

その前に Lisp に処理系で使われている任意の桁数の小数を扱うことができるものを実装します。C# の例で使っていた LongDecimal クラスでは小数点以下任意の桁数の正の小数(小数点以上は一桁)を扱うことができたのですが、これを拡張して(この数に掛ける) 10 の累乗の指数を表す整数を付け加えたものを BigDecimal クラスとします。これに符号を付け加えて BigNum クラスとします。

    internal class BigDecimal
    {
        private LongDecimal dec;
        private int exp;
        public BigDecimal()
        {
            dec = new LongDecimal();
            exp = 0;
        }
        public BigDecimal(int n)
        {
            dec = new LongDecimal(n);
            exp = 0;
        }
        public BigDecimal(int n, int e)
        {
            dec = new LongDecimal(n);
            exp = e;
        }
        public BigDecimal(IEnumerable<int> numbers)
        {
            dec = new LongDecimal(numbers);
            exp = 0;
        }
        public BigDecimal(LongDecimal dec, int exp)
        {
            this.dec = dec;
            this.exp = exp;
        }
        public BigDecimal(string src)
        {
            int index = 0;
            int start_index = index;
            for (; index < src.Length && char.IsDigit(src[index]); index++)
            {
            }
            for (; start_index < src.Length && src[start_index] == '0'; start_index++)
            {
            }
            IEnumerable<int> left = src.Substring(start_index, index - start_index).Select(c => Convert.ToInt32(c.ToString()));
            if (index < src.Length && src[index] == '.')
            {
                index++;
            }
            start_index = index;
            for (; index < src.Length && char.IsDigit(src[index]); index++)
            {
            }
            IEnumerable<int> right = src.Substring(start_index, index - start_index).Select(c => Convert.ToInt32(c.ToString()));
            if (index < src.Length && (src[index] == 'e' || src[index] == 'E'))
            {
                index++;
            }
            int sgn = 1;
            if (index < src.Length && (src[index] == '+' || src[index] == '-'))
            {
                if (index < src.Length && src[index] == '-')
                {
                    sgn = -1;
                }
                index++;
            }
            start_index = index;
            for (; index < src.Length && char.IsDigit(src[index]); index++)
            {
            }
            int e = Convert.ToInt32("0" + src.Substring(start_index, index - start_index));
            dec = new LongDecimal(left.Concat(right));
            exp = left.Count() - 1 + e;
        }
        public override bool Equals(Object obj)
        {
            if ((obj == null) || !this.GetType().Equals(obj.GetType()))
            {
                return false;
            }
            else
            {
                return this == (BigDecimal)obj;
            }
        }

        public override int GetHashCode()
        {
            return dec.GetHashCode() ^ exp;
        }
        private static LongDecimal Align(LongDecimal dec, int e)
        {
            if (e > 0)
            {
                return dec.Shift(e);
            }
            else
            {
                return dec;
            }
        }
        public static BigDecimal operator +(BigDecimal x, BigDecimal y)
        {
            int m = Math.Max(x.exp, y.exp);
            int e = y.exp - x.exp;
            return (Align(x.dec, e) + Align(y.dec, -e)).ToBigDecimal(m);
        }
        public static BigDecimal operator -(BigDecimal x, BigDecimal y)
        {
            int m = Math.Max(x.exp, y.exp);
            int e = y.exp - x.exp;
            return (Align(x.dec, e) - Align(y.dec, -e)).ToBigDecimal(m);
        }
        public static BigDecimal operator *(BigDecimal x, BigDecimal y)
        {
            return (x.dec * y.dec).ToBigDecimal(x.exp + y.exp);
        }
        public bool IsZero()
        {
            return dec.IsZero();
        }
        public static bool operator ==(BigDecimal x, BigDecimal y)
        {
            int e = y.exp - x.exp;
            return Align(x.dec, e) == Align(y.dec, -e);
        }
        public static bool operator !=(BigDecimal x, BigDecimal y)
        {
            return !(x == y);
        }
        public static bool operator <(BigDecimal x, BigDecimal y)
        {
            int e = y.exp - x.exp;
            return Align(x.dec, e) < Align(y.dec, -e);
        }
        public static bool operator <=(BigDecimal x, BigDecimal y)
        {
            return x < y || x == y;
        }
        public static bool operator >(BigDecimal x, BigDecimal y)
        {
            return !(x <= y);
        }
        public static bool operator >=(BigDecimal x, BigDecimal y)
        {
            return !(x < y);
        }
        public string Print()
        {
            return dec.Print(exp);
        }
    }

    internal class BigNum
    {
        private BigDecimal nat;
        private int sgn;
        public BigNum()
        {
            nat = new BigDecimal();
            sgn = 1;
        }
        public BigNum(int n)
        {
            nat = new BigDecimal(n);
            sgn = 1;
        }
        public BigNum(int n, int e)
        {
            nat = new BigDecimal(n, e);
            sgn = 1;
        }
        public BigNum(IEnumerable<int> numbers)
        {
            nat = new BigDecimal(numbers);
            sgn = 1;
        }
        public BigNum(LongDecimal dec, int exp)
        {
            nat = new BigDecimal(dec, exp);
            sgn = 1;
        }
        public BigNum(string src)
        {
            int index = 0;
            sgn = 1;
            if (index < src.Length && (src[index] == '+' || src[index] == '-'))
            {
                if (index < src.Length && src[index] == '-')
                {
                    sgn = -1;
                }
                index++;
            }
            nat = new BigDecimal(src.Substring(index));
        }
        public BigNum(BigDecimal nat, int sgn)
        {
            this.nat = nat;
            this.sgn = sgn;
        }
        public override bool Equals(Object obj)
        {
            if ((obj == null) || !this.GetType().Equals(obj.GetType()))
            {
                return false;
            }
            else
            {
                return this == (BigNum)obj;
            }
        }

        public override int GetHashCode()
        {
            return nat.GetHashCode() ^ sgn;
        }
        public static BigNum operator +(BigNum x, BigNum y)
        {
            if (x.sgn == y.sgn)
            {
                return new BigNum(x.nat + y.nat, x.sgn);
            }
            else
            {
                if (x.nat >= y.nat)
                {
                    return new BigNum(x.nat - y.nat, x.sgn);
                }
                else
                {
                    return new BigNum(y.nat - x.nat, y.sgn);
                }
            }
        }
        public static BigNum operator -(BigNum x)
        {
            return new BigNum(x.nat, -x.sgn);
        }
        public static BigNum operator -(BigNum x, BigNum y)
        {
            return x + -y;
        }
        public static BigNum operator *(BigNum x, BigNum y)
        {
            return new BigNum(x.nat * y.nat, x.sgn * y.sgn);
        }
        public bool IsZero()
        {
            return nat.IsZero();
        }
        public static bool operator ==(BigNum x, BigNum y)
        {
            return x.nat == y.nat && x.sgn == y.sgn || x.IsZero() && y.IsZero();
        }
        public static bool operator !=(BigNum x, BigNum y)
        {
            return !(x == y);
        }
        public static bool operator <(BigNum x, BigNum y)
        {
            if (x.IsZero() && y.IsZero())
            {
                return false;
            }
            else if (x.sgn < y.sgn)
            {
                return true;
            }
            else if (x.sgn > y.sgn)
            {
                return false;
            }
            else if (x.sgn > 0)
            {
                return x.nat < y.nat;
            }
            else
            {
                return x.nat > y.nat;
            }
        }
        public static bool operator <=(BigNum x, BigNum y)
        {
            return x < y || x == y;
        }
        public static bool operator >(BigNum x, BigNum y)
        {
            return !(x <= y);
        }
        public static bool operator >=(BigNum x, BigNum y)
        {
            return !(x < y);
        }
        public string Print()
        {
            if (sgn > 0)
            {
                return nat.Print();
            }
            else
            {
                return "-" + nat.Print();
            }
        }
    }

LongDecimal クラスには以下を付け加えます。

        public BigDecimal ToBigDecimal(int e2)
        {
            const int radix = 10;
            if (decimals.Count >= 1)
            {
                if (decimals[0] == 0)
                {
                    int e = 0;
                    for (int i = 0; i < decimals.Count && decimals[i] == 0; i++, e++)
                    {
                    }
                    return new BigDecimal(new LongDecimal(decimals.Skip(e)), -e + e2);
                }
                if (decimals[0] >= radix)
                {
                    int d = decimals[0];
                    LinkedList<int> ds = new LinkedList<int>();
                    while (d >= radix)
                    {
                        ds.AddFirst(d % radix);
                        d /= radix;
                    }
                    return new BigDecimal(new LongDecimal(ImmutableList<int>.Empty.Add(d).AddRange(ds).AddRange(decimals.Skip(1))), ds.Count + e2);
                }
            }
            return new BigDecimal(this, e2);
        }
        public bool IsZero()
        {
            return decimals.All(d => d == 0);
        }

初めての人のためのLISP［増補改訂版］