[Nemerle] Problem K - Декларативное программирование

Здравствуйте, Kisloid, Вы писали:

K>Честно говоря я не задавался целью хорошего дизайна, цель была сделать как можно проще.

В условии задачи было написано, что алгоритмической сложности в ней нет. Вся сложность в том, чтобы правильно задизайнить решение.

K>Expr -> Sheet: Expr знает только о Sheet, т.к. ему нужно по ходу вычислений менять другие ячейки.

У тебя Expr знает не только о Sheet, но и о Cell и активно учавствует в их вычислении.

А ведь модуль Expr можно было сделать совершенно самостоятельным и готовым к повторному использованию ...

K>Cell <-> Sheet: все ячейки хранят ссылку на Sheet т.к. если он является выражением, то он нужен для вычисления. Sheet
K>состоит из массива Cell'ов.

Он нужен только в предложенной тобой реализации.

-----------

В качестве альтернативы может выступать такое решение на java (основыне классы, опущена логика построения выражений из строк).

CExpr — константа.
Expr — выражение оперирующее константами, инфиксными функциями и переменными (ссылками на константы).
IVarResolver — контекст из которого можно доставать значения связанные с переменными.

Cell — ячейка, содержит выражение и вычисляет его значение
Sheet — содержит набор ячеек, умеет их вычислять и контролировать циклы.

abstract class CExpr
{
    public abstract String toFormattedString();

    public static class Error extends CExpr
    {
        private String message;
        public Error(String message) {  this.message = message; }
        public String toFormattedString() { return "#" + message; }
    }

    public static class Number extends CExpr
    {
        private int value;
        public Number(int value) { this.value = value; }
        public int getValue() { return value; }
        public String toFormattedString() { return Integer.toString(value); }
    }

    public static class Text extends CExpr
    {
        private String value;
        public Text(String value) { this.value = value; }
        public String toFormattedString() { return "'" + value; }
    }
}

interface IVarResolver
{
    CExpr resolve(String value);
}

abstract class Expr
{
    public abstract CExpr evaluate(IVarResolver resolver);

    public static class Const extends Expr
    {
        private CExpr value;
        public Const(CExpr value) { this.value = value; }
        public CExpr evaluate(IVarResolver resolver) {  return value; }
    }

    public static class Var extends Expr
    {
        private String value;
        public Var(String value) { this.value = value; }
        public CExpr evaluate(IVarResolver resolver) { return resolver.resolve(value); }
    }

    public static class Func extends Expr
    {
        private BinaryFunction f;
        private Expr a, b;

        public Func(BinaryFunction f, Expr a, Expr b)
        {
            this.f = f;
            this.a = a;
            this.b = b;
        }

        public CExpr evaluate(IVarResolver resolver)
        {
            return f.evaluate(a.evaluate(resolver), b.evaluate(resolver));
        }
    }
}

interface BinaryFunction
{
    char getName();

    CExpr evaluate(CExpr a, CExpr b);
}

class Add implements BinaryFunction
{
    public char getName() { return '+'; }

    public CExpr evaluate(CExpr a, CExpr b)
    {
        if (a instanceof CExpr.Number && b instanceof CExpr.Number)
        {
            return evaluate((CExpr.Number) a, (CExpr.Number) b);
        }
        return new CExpr.Error("add");
    }

    public CExpr evaluate(CExpr.Number a, CExpr.Number b)
    {
        return new CExpr.Number(a.getValue() + b.getValue());
    }
}

class Cell
{
    enum State { NotEvaluated, Evaluating, Evaluated
    }

    private Expr expr;
    private CExpr value = null;
    private State state = State.NotEvaluated;

    public Cell(Expr expr)
    {
        this.expr = expr;
    }

    public boolean isEvaluating()
    {
        return state == State.Evaluating;
    }

    public CExpr evaluate(IVarResolver resolver)
    {
        switch (state)
        {
            case NotEvaluated:
                state = State.Evaluating;
                value = expr.evaluate(resolver);
                state = State.Evaluated;
                break;
            case Evaluated:
                return value;
        }
        throw new InternalError();
    }

}

class Sheet implements IVarResolver
{
    private Cell[][] cells;

    public void evaluate()
    {
        for (Cell[] row : cells)
        {
            for (Cell cell : row)
            {
                cell.evaluate(this);
            }
        }
    }

    public CExpr resolve(String value)
    {
        Cell cell = getCellByName(value);
        if (cell.isEvaluating())
        {
            return new CExpr.Error("cycle");
        }
        return cell.evaluate(this);
    }

    private Cell getCellByName(String value)
    {
        return null;
    }
}

Описание проблемы (и решение на Хаскеле) можно найти здесь.

Тоже не удержался и попробовал решить задачу К на Немерле. Полные исходники можно скачать отсюда.

Проектировать начал снизу вверх (кажется Пол Грэхэм говорил, что bottom up это круто).
Сначала опишем, что такое выражение (описал в виде АТД):

    public variant Expr
    {
        | Literal { v  : int;             }
        | String  { s  : string;          }
        | Add     { e1 : Expr; e2 : Expr; }
        | Sub     { e1 : Expr; e2 : Expr; }
        | Mul     { e1 : Expr; e2 : Expr; }
        | Div     { e1 : Expr; e2 : Expr; }
        | Ref     { i  : int;  j  : int;  }

        static public BuildExpr(s : string) : Expr
        {
             <skipped>
        }

        public Eval(sheet : Sheet) : Expr
        {
             <skipped>
        }
    }

Итак, оно может быть создано из строки и вычислено. Eval принимает как параметр указатель на Sheet, т.к. ему нужно будет вычислять другие ячейки Sheet'а. Может было бы правильнее ссылку на Sheet хранить как член данных, но для простоты я передаю его как параметр (иначе нужно все дерево обходить устанавливая эту ссылку).

Теперь опишем, что есть ячейка:

    public variant Cell
    {
        [Accessor(flags = WantSetter)]
        private mutable position : int * int;
        
        [Accessor(flags = WantSetter)]
        private mutable parent : Sheet;
    
        | Expression { e : Expr;   }
        | Number     { n : int;    }
        | Text       { s : string; }
        | Error      { s : string; }
        | Nil

        public Eval() : Cell
        {
             <skipped>
        }

        public override ToString() : string
        {
             <skipped>
        }
    }

Я думаю в особо комментариях не нуждается, он умеет вычисляться и показывать себя.

А теперь наконец опишем, что такое Sheet:

    public class Sheet
    {
        [Accessor] mutable rows    : int;
        [Accessor] mutable columns : int;
        
        [Accessor(flags = WantSetter)]
        mutable marks : Hashtable[(int * int), bool];
        
        mutable sheet : array [2, Cell];
    
        public this(n : int, m : int, a : array [2, Cell])
        {
             <skipped>
        }
        
        public Eval() : void
        {
             <skipped>
        }
        
        public override ToString() : string
        {
             <skipped>
        }
        
        public Item [i : int, j : int] : Cell
        {
            get { sheet[i, j] }
            set { sheet[i, j] = value }
        }
    }

Тоже умеет вычисляться и показывать себя.

Можно скачать, откомпилить и проверить. К сожалению это не студийный проект, все писал в емаксе. Специально нарушил условия, вместо стандартных потоков использовал файлы, для простоты тестирования.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>не хватает только решения на самом языке K

Вот, чисто для коллекции. Люди K, надеюсь, так не пишут даже на К.

O:"+-*/"; o:(+;-;*;_%)
split:{(&x _in\: y)_ x}
mkr:{:[(x<W)&(y<H);"ref[",($y),";",($x),"]";`badref]}
mkv:{x}
mka:{:[x _sm "[a-z][0-9]"; mkr[(_ic*x)-97; (_ic x[1])-49]
       x _sm "[A-Z][0-9]"; mkr[(_ic*x)-65; (_ic x[1])-49]
       x _sm "[0-9]*"; mkv[x]; `err]}
mkf:{t:split["+",1_ x;O]; `form, +{(o[O?*x]; mka[1_ x])}'t}
parse: {:[x~"";`; *x _sm "[0-9]*"; 0$x;(*x)="'"; 1_ x; (*x)="="; mkf[x]; `err]}
read:{in: {1_'split["\t",x;,"\t"]}'0: x; wh:0$*in; W::wh[0]; H::wh[1]; S::parse''1 _ in}
show:{x 0:{x,"\n",y}/{x,"\t",y}/'$S}
ref:{if[~4:S[x;y]; force[x;y]]; S[x;y]}
force:{t:S[x;y]; if[`eval~*t; S[x;y]:`cycle]; if[`form~*t; S[x;y;0]:`eval; S[x;y]:eval[t]]}
apply:{y[x;z]}
eval:{a: .:'x[2];:[&/1={4:x}'a; apply/[0;x[1];a]; `err]}

read[`in];(!W)force'\:!H;show[`out]

Здравствуйте, Kisloid, Вы писали:

K>Тоже не удержался и попробовал решить задачу К на Немерле.

дурной пример заразителен

Здравствуйте, VladD2, Вы писали:

VD>1. Перенести рассчеты в Sheet.
VD>2. Убрать Marks из списка полей, сделав его параметром.
VD>3. Убрать обратные ссылки из Cell и Expr.
VD>4. (под вопросом) Отказаться от Cell. Оно похоже лишний.

Можно как нить на досуге попробовать сделать такой вариант и сравнить.

VD>Хороший дизайн всегда легко оценить, но тудно создать. Иными словами трепаться про Хороший дизайн (тм) всегда проще, чем сделать его самому.

А еще сложней понять, хороший ли у тебя дизайн, если никто со стороны об этом дизайне не потреплется

Здравствуйте, geniepro, Вы писали:

G>Ещё вот
G>И ещё
G>А вот
G>А вот
G>Ну и до кучи

не хватает только решения на самом языке K

Здравствуйте, VladD2, Вы писали:

VD>Он только каркас описал. Причем не сильно думая о будущем расширении. Там еще писать и писать.

Поясни, плз, что ты имеешь ввиду. О каких именно расширениях идёт речь? Что, кроме парсера, там нужно ещё написать?

VD>В том-то и разница, что каркас на Яве больше по объему чем решение на языке с паттерн-матчингом.

Строчек, конечно, больше получается... Но суть-то в том, что наличие паттерн-матчинга и вариантов не гарантирует хорошего дизайна и, в какой-то степени, даже поощряет дублирование кода, как это видно в примере решения на немерле.
А кодирование упрощает, да.

На хаскеле писать решение мне больше понравилось, чем на java: http://nggu.livejournal.com/663.html

Expr <-> Sheet, Expr <-> Сell, Cell <-> Sheet — меджу всеми парами двунаправленные зависимости.
Особенно примечательно поле marks. Нельзя разобраться в том, как работает проверка на цикл, не разобравшись с каждым из методов вычисления (в Sheet, Сell, Expr)...

Данные дублируются: координты cell хранятся в Sheet и в каждой cell...

Приседание

 sheet[i, j] = sheet[i, j].Eval();
 sheet[i, j].Position = (i, j);

говорит о том, что Expr знает не только об интерфейсе Cell, но и о том, как устроен метод Eval в нём!

Добавление новой функции приведёт к изменению в 6-х местах, причём это будет "ещё один копипаст":

1. | Power     { e1 : Expr; e2 : Expr; }
2. | Power => Expr.Power(build(tokens, ind - 2 ), parse(tokens[ind]))
3. | '^' => Expr.Power(build(tokens, ind - 2 ), parse(tokens[ind]))
4. if (['+', '-', '*', '/', '^'].Contains(c))
5. | (e1 is Literal, e2 is Literal, _ is Power) => Literal(e1.v + e2.v)
6. | Power     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)

...

Задача была про "хороший" дизайн. Разве это хороший дизайн?

Здравствуйте, VladD2, Вы писали:

NGG>>На хаскеле писать решение мне больше понравилось, чем на java: http://nggu.livejournal.com/663.html

VD>Это понятно. Но мне как раз интересно работающее и полное решение на Яве. Вообще оптимально было бы если она на J# было бы, а то возиться с Явой влом

.

Было бы много времени свободного и желание — дописал бы до конца. Но ни того, ни другого пока нет.
После хаскелля у меня небольшая аллергия на java/c# образовалась

Таки думаю, как то совсем ненаглядно, лучше покажу полный исходный код:

Expression.n

    public variant Expr
    {
        | Literal { v  : int;             }
        | String  { s  : string;          }
        | Add     { e1 : Expr; e2 : Expr; }
        | Sub     { e1 : Expr; e2 : Expr; }
        | Mul     { e1 : Expr; e2 : Expr; }
        | Div     { e1 : Expr; e2 : Expr; }
        | Ref     { i  : int;  j  : int;  }

        static public BuildExpr(s : string) : Expr
        {
            def parse(s)
            {
                try
                {
                    if (Char.IsDigit(s[0]))
                        Expr.Literal(Convert.ToInt32(s))
                    else
                    {
                        def i = Convert.ToInt32(s.Substring(1)) - 1;
                        def j = Convert.ToInt32(Char.ToUpper(s[0])) - Convert.ToInt32('A');
                        Expr.Ref(i, j)
                    }
                }
                catch
                { | e => throw ParseException(e) }
            }
            
            def build(tokens, ind)
            {
                if (ind >= 2)
                    match (tokens[ind - 1][0])
                    {
                        | '+' => Expr.Add(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '-' => Expr.Sub(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '*' => Expr.Mul(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '/' => Expr.Div(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | _   => throw ParseException()
                    }
                else
                    parse(tokens[ind])
            }
        
            // preprocessing source string
            mutable str = "";
            s.Iter(fun(c) {
                if (['+', '-', '*', '/'].Contains(c))
                    str += " " + c.ToString() + " " 
                else
                    str += c.ToString()
            });

            def tokens = 
                str.Split(array [' '], StringSplitOptions.RemoveEmptyEntries);
            build(tokens, tokens.Length - 1)
        }
        
        public Eval(sheet : Sheet) : Expr
        {
            def eval(e1, e2, root)
            {
              | (e1 is Literal, e2 is Literal, _ is Add) => Literal(e1.v + e2.v)
              | (e1 is Literal, e2 is Literal, _ is Sub) => Literal(e1.v - e2.v)
              | (e1 is Literal, e2 is Literal, _ is Mul) => Literal(e1.v * e2.v)
              | (e1 is Literal, e2 is Literal, _ is Div) =>
                  when (e2.v == 0)
                      throw EvalException("eval");
                  Literal(e1.v / e2.v)

              | (_, _, _) => throw EvalException("eval")
            }

            match (this)
            {
                | Literal (_) => this
                | String  (_) => this
                | Add     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Sub     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Mul     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Div     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Ref     (i,  j ) => 
                    sheet[i, j] = sheet[i, j].Eval();
                    sheet[i, j].Position = (i, j);
                    match (sheet[i, j])
                    {
                        | Number (n) => Literal(n)
                        | Text   (s) => String(s)
                        | _          => throw EvalException("eval")
                    }
            }
        }
    }

Cell.n

    public variant Cell
    {
        [Accessor(flags = WantSetter)]
        private mutable position : int * int;
        
        [Accessor(flags = WantSetter)]
        private mutable parent : Sheet;
    
        | Expression { e : Expr;   }
        | Number     { n : int;    }
        | Text       { s : string; }
        | Error      { s : string; }
        | Nil

        public Eval() : Cell
        {
            match (this)
            {
                | Expression (e) =>
                    when (parent.Marks.Contains(position))
                      throw EvalException("cycle");
                    parent.Marks[position] = true;

                    match (e.Eval(parent))
                    {
                        | Literal (l) => Cell.Number(l)
                        | String  (s) => Cell.Text(s)
                        | _           => throw EvalException("eval")
                    }

                | _ => this
            }
        }

        public override ToString() : string
        {
            match (this)
            {
                | Expression (e) => e.ToString()
                | Number     (n) => n.ToString()
                | Text       (s) => s
                | Error      (s) => "#" + s
                | Nil        => ""
            }
        }
    }

Sheet.n

    public class Sheet
    {
        [Accessor] mutable rows    : int;
        [Accessor] mutable columns : int;
        
        [Accessor(flags = WantSetter)]
        mutable marks : Hashtable[(int * int), bool];
        
        mutable sheet : array [2, Cell];
    
        public this(n : int, m : int, a : array [2, Cell])
        {
            rows    = n;
            columns = m;
            
            sheet = a;
            for (mutable i = 0; i < rows; i++)
                for (mutable j = 0; j < columns; j++)
                {
                    sheet[i, j].Parent   = this;
                    sheet[i, j].Position = (i, j);
                }
        }
        
        public Eval() : void
        {
            for (mutable i = 0; i < rows; i++)
                for (mutable j = 0; j < columns; j++)
                {
                    try
                    {
                        marks = Hashtable();
                        sheet[i, j] = sheet[i, j].Eval();
                    }
                    catch
                    {
                        | e is EvalException =>
                            sheet[i, j] = Cell.Error(e.Message)

                        | _ => throw
                    }
                }
        }
        
        public override ToString() : string
        {
            mutable res = "";
            for (mutable i = 0; i < rows; i++)
            {
                for (mutable j = 0; j < columns; j++)
                    res += sheet[i, j].ToString() + "\t";
                res += "\n"
            }
            res
        }
        
        public Item [i : int, j : int] : Cell
        {
            get { sheet[i, j] }
            set { sheet[i, j] = value }
        }
    }

Здравствуйте, Kisloid, Вы писали:

Не понял сложностей в реализации Expr.Eval:

public Eval(sheet : Sheet) : Expr
{
        // Зачем этот метод?
        def eval(e1, e2, root)
        {
            // Зачем эти is-ы?
            | (e1 is Literal, e2 is Literal, _ is Add) => Literal(e1.v + e2.v)
            | (e1 is Literal, e2 is Literal, _ is Sub) => Literal(e1.v - e2.v)
            | (e1 is Literal, e2 is Literal, _ is Mul) => Literal(e1.v * e2.v)
            | (e1 is Literal, e2 is Literal, _ is Div) =>
                    when (e2.v == 0)
                            throw EvalException("eval");
                    Literal(e1.v / e2.v)

            | (_, _, _) => throw EvalException("eval")
        }

        match (this)
        {
                | Literal (_) => this
                | String  (_) => this
                | Add     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Sub     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Mul     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Div     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
                | Ref     (i,  j ) => 
                        sheet[i, j] = sheet[i, j].Eval();
                        sheet[i, j].Position = (i, j);
                        match (sheet[i, j])
                        {
                                | Number (n) => Literal(n)
                                | Text   (s) => String(s)
                                | _          => throw EvalException("eval")
                        }
        }
}

Почему было не написать так:

public Eval(sheet : Sheet) : Expr
{
        def eval(expr)
        {
            match (expr.Eval(sheet))
            {
                | Literal(val) => val
                | _            => throw EvalException("eval: vlalue not literal")
            }
        }

        match (this)
        {
                | Literal | String => this
                | Add (e1, e2)     => Literal(eval(e1) + eval(e2))
                | Sub (e1, e2)     => Literal(eval(e1) - eval(e2))
                | Mul (e1, e2)     => Literal(eval(e1) * eval(e2))
                | Div (e1, e2)     => when (e2.v == 0) throw EvalException("eval: div by zero");
                                      Literal(eval(e1) / eval(e2))
                | Ref     (i,  j ) => 
                        sheet[i, j] = sheet[i, j].Eval();
                        sheet[i, j].Position = (i, j);
                        match (sheet[i, j])
                        {
                            | Number(n) => Literal(n)
                            | Text  (s) => String(s)
                            | _         => throw EvalException("eval")
                        }
        }
}

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, NotGonnaGetUs, Вы писали:

....

Добавлю так же, что использование двумерного массива решение крайне не экономичное и приведет к большому оверхэду по памяти на таблицах где имеются ячейки с большим номеро строк и/или колонок. Вместо массива "sheet" нужно использовать хэш-таблицу.

NGG>Задача была про "хороший" дизайн. Разве это хороший дизайн?

Лиха беда начало...

К тоу же по ссылке рассказвается о том, что задача выявляла супер-людей-К просто фактом ее решения. Так что даже не оптимальное решение — это зачет.

В прочем, задача сложна для решения на С++ или Яве, а на языках с паттерн-матчнгом она именно что выявляет инженерные (архитекторские) способности.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Expr <-> Sheet, Expr <-> Сell, Cell <-> Sheet — меджу всеми парами двунаправленные зависимости.
NGG>Особенно примечательно поле marks. Нельзя разобраться в том, как работает проверка на цикл, не разобравшись с каждым из методов вычисления (в Sheet, Сell, Expr)...

Expr -> Sheet: Expr знает только о Sheet, т.к. ему нужно по ходу вычислений менять другие ячейки.
Cell <-> Sheet: все ячейки хранят ссылку на Sheet т.к. если он является выражением, то он нужен для вычисления. Sheet состоит из массива Cell'ов.
Cell -> Expr: ячейка может быть выражением, а может быть просто числом, текстом...

NGG>Данные дублируются: координты cell хранятся в Sheet и в каждой cell...

Координаты Cell не хранятся в Sheet, Cell'ы могли быть представлены, списком, мапом итд. Cell'У нужно знать свои координаты, для обнаружения циклов, а координаты не доступны из Sheet'а.

NGG>Приседание
NGG>

NGG> sheet[i, j] = sheet[i, j].Eval();
NGG> sheet[i, j].Position = (i, j);
NGG>

NGG>говорит о том, что Expr знает не только об интерфейсе Cell, но и о том, как устроен метод Eval в нём!

Ну тут да, кривость

. Только это говорит не о том, как устроен метод Eval. Просто Cell по сути immutable, не может менять свою внутреннюю структуру. Надо пересоздавать его, а при этом теряется Position. Я думаю просто в сеттере надо было копировать Position.

NGG>Добавление новой функции приведёт к изменению в 6-х местах, причём это будет "ещё один копипаст":
NGG>

NGG>1. | Power     { e1 : Expr; e2 : Expr; }
NGG>2. | Power => Expr.Power(build(tokens, ind - 2 ), parse(tokens[ind]))
NGG>3. | '^' => Expr.Power(build(tokens, ind - 2 ), parse(tokens[ind]))
NGG>4. if (['+', '-', '*', '/', '^'].Contains(c))
NGG>5. | (e1 is Literal, e2 is Literal, _ is Power) => Literal(e1.v + e2.v)
NGG>6. | Power     (e1, e2) => eval(e1.Eval(sheet), e2.Eval(sheet), this)
NGG>

NGG>...

Эммм... я думаю тут главное, что это затрагивает только Expr.

NGG>Задача была про "хороший" дизайн. Разве это хороший дизайн?

Честно говоря я не задавался целью хорошего дизайна, цель была сделать как можно проще.

Здравствуйте, VladD2, Вы писали:

VD>Добавлю так же, что использование двумерного массива решение крайне не экономичное и приведет к большому оверхэду по памяти на таблицах где имеются ячейки с большим номеро строк и/или колонок. Вместо массива "sheet" нужно использовать хэш-таблицу.

Согласен, просто не задавался целью оптимального решения. Premature optimization типа

NGG>>Задача была про "хороший" дизайн. Разве это хороший дизайн?

VD>Лиха беда начало...

Вот как разгонюсь...

VD>В прочем, задача сложна для решения на С++ или Яве, а на языках с паттерн-матчнгом она именно что выявляет инженерные (архитекторские) способности.

Не покажешь высший пилотаж?

Здравствуйте, VladD2, Вы писали:

Хотел показать как легко и просто можно будет добавить например конкатенацию строк через '+', потом честно гря просто стало в лом...
VD>Не понял сложностей в реализации Expr.Eval:
VD>

VD>public Eval(sheet : Sheet) : Expr
VD>{
VD>        // Зачем этот метод?
VD>        def eval(e1, e2, root)
VD>        {
VD>            // Зачем эти is-ы?
VD>            | (e1 is Literal, e2 is Literal, _ is Add) => Literal(e1.v + e2.v)
               | (e1 is String,  e1 is String,  _ is Add) => String (e1.s + e2.s)
VD>            | (e1 is Literal, e2 is Literal, _ is Sub) => Literal(e1.v - e2.v)
VD>            | (e1 is Literal, e2 is Literal, _ is Mul) => Literal(e1.v * e2.v)
VD>            | (e1 is Literal, e2 is Literal, _ is Div) =>
VD>                    when (e2.v == 0)
VD>                            throw EvalException("eval");
VD>                    Literal(e1.v / e2.v)

VD>            | (_, _, _) => throw EvalException("eval")
VD>        }

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Особенно примечательно поле marks. Нельзя разобраться в том, как работает проверка на цикл, не разобравшись с каждым из методов вычисления (в Sheet, Сell, Expr)...

Про Expr не понял, не надо знать как работает Expr.Eval(), чтобы разобраться в проверке на цикл. А Sheet <-> Cell, Marks является частью внешнего интерфейса Sheet. Cell пользуется Marks, чтобы понять, не зациклился ло он. Предложите, как поступить иначе?

NGG>Задача была про "хороший" дизайн. Разве это хороший дизайн?

Эммм... может покажете, что такое хороший дизайн?

Здравствуйте, VladD2, Вы писали:

VD>К тоу же по ссылке рассказвается о том, что задача выявляла супер-людей-К просто фактом ее решения.

какой-либо попытки проверки решения я здесь не заметил

Здравствуйте, Kisloid, Вы писали:

K>Согласен, просто не задавался целью оптимального решения. Premature optimization типа

Там в условиях сказано:

Представьте, что это требования к первой фазе проекта. Необходимо реализовать
только то, что нужно на этой фазе. Однако, известно, что планируется вторая
фаза, в которой требования будут расширены следующими:
— Расширить формулы операциями над строками,
— Оптимизировать производительность для громадных таблиц.

VD>>В прочем, задача сложна для решения на С++ или Яве, а на языках с паттерн-матчнгом она именно что выявляет инженерные (архитекторские) способности.

K>Не покажешь высший пилотаж?

На плюсах то? Не, я лучше гавкну. Меня последние 3 года тошнит когда приходится на этом языке писать. Ощущения такие как будто в наручниках сидишь.

Вот твою версию можно, наверно, на досуге немного причесать и подоптимизировать.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Kisloid, Вы писали:

K>Хотел показать как легко и просто можно будет добавить например конкатенацию строк через '+', потом честно гря просто стало в лом...
VD>>Не понял сложностей в реализации Expr.Eval:
VD>>

VD>>public Eval(sheet : Sheet) : Expr
VD>>{
VD>>        // Зачем этот метод?
VD>>        def eval(e1, e2, root)
VD>>        {
VD>>            // Зачем эти is-ы?
VD>>            | (e1 is Literal, e2 is Literal, _ is Add) => Literal(e1.v + e2.v)
K>               | (e1 is String,  e1 is String,  _ is Add) => String (e1.s + e2.s)
VD>>            | (e1 is Literal, e2 is Literal, _ is Sub) => Literal(e1.v - e2.v)
VD>>            | (e1 is Literal, e2 is Literal, _ is Mul) => Literal(e1.v * e2.v)
VD>>            | (e1 is Literal, e2 is Literal, _ is Div) =>
VD>>                    when (e2.v == 0)
VD>>                            throw EvalException("eval");
VD>>                    Literal(e1.v / e2.v)

VD>>            | (_, _, _) => throw EvalException("eval")
VD>>        }
K>

Ясно...

Но тогда опять же... зачем is? Можно же так:

def eval(e1, e2, root)
{
    // Зачем эти is-ы?
    | (Literal(e1), Literal(e2), Add) => Literal(e1 + e2)
    | (String(e1),  String(e2),  Add) => String (e1 + e2)
    | (Literal(e1), Literal(e2), Sub) => Literal(e1 - e2)
    | (Literal(e1), Literal(e2), Mul) => Literal(e1 * e2)
    | (Literal(e1), Literal(e2), Div) =>
            when (e2 == 0)
                    throw EvalException("eval");
            Literal(e1.v / e2.v)

    | (_, _, _) => throw EvalException("eval")
}

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Kisloid, Вы писали:

K>Expr -> Sheet: Expr знает только о Sheet, т.к. ему нужно по ходу вычислений менять другие ячейки.

Тогда разумно переместить вычисление в Sheet... наверно.

K>Cell <-> Sheet: все ячейки хранят ссылку на Sheet т.к. если он является выражением, то он нужен для вычисления. Sheet состоит из массива Cell'ов.

Опчть же. Если вычисления в Sheet, то и ячейкам ничего знать про себя кроме содержимого не надо. По сути Cell и Expr — это хранилища данных. Ты ведь не даром их вариантами представил?

K>Cell -> Expr: ячейка может быть выражением, а может быть просто числом, текстом...

Ну, это понятно.

NGG>>Данные дублируются: координты cell хранятся в Sheet и в каждой cell...

K>Координаты Cell не хранятся в Sheet, Cell'ы могли быть представлены, списком, мапом итд. Cell'У нужно знать свои координаты, для обнаружения циклов, а координаты не доступны из Sheet'а.

Опять же стоит подумать над тем, чтобы перенести логику обнаружения циклов в Sheet.

Мне еще не понравилось то, что свойства Parent и Parent класса Sheet можно менять извне Sheet-а.

Мне кажется, что по минимуму нужно сделать Sheet вложенным в Cell а сеттеры приватными. В прочем решение явно кривоватое.

Лучше все же перенести вычисления в Sheet, а Cell и Expr сделать чистыми хранилищами данных. В прочем, мне так же не ясно зачем вообще нужен Cell. Возможно разумнее было бы отказаться от него добавив в Expr вхождение позволяющиее хранить сообщение об ошибке.

Ну, и наврено более разумно не менять, при вычислении, значение в саомо Sheet, а создавать новый Sheet с вычесленными значениями.

K>Честно говоря я не задавался целью хорошего дизайна, цель была сделать как можно проще.

Ну, получилось, мне кажется, немного сложнее чем могло бы быть. Понятно, что соврешенство всегда оставляет простор для фантазии. Но мне кажется, если ты учтешь замечения, то код будет и проще, и чище.

Кстати, вместо сакроса Acssesor теперь удобнее использовать упрощенный синтаксис объявления свойств. Так твои свойства можно будет объявить следующим образом:

public partial class Sheet
{
    public Rows    : int                          { get; private set; }
    public Columns : int                          { get; private set; }
    public Marks   : Hashtable[(int * int), bool] { get; private set; }
    public Sheet   : array [2, Cell]              { get; private set; }
  ...

И Marks, наверно, не стоит делать полем. Это структура нужна только на время вычисления. Ее следут созоавать в функции вычисления.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Kisloid, Вы писали:

K>Про Expr не понял, не надо знать как работает Expr.Eval(), чтобы разобраться в проверке на цикл. А Sheet <-> Cell, Marks является частью внешнего интерфейса Sheet. Cell пользуется Marks, чтобы понять, не зациклился ло он. Предложите, как поступить иначе?

1. Перенести рассчеты в Sheet.
2. Убрать Marks из списка полей, сделав его параметром.
3. Убрать обратные ссылки из Cell и Expr.
4. (под вопросом) Отказаться от Cell. Оно похоже лишний.

K>Эммм... может покажете, что такое хороший дизайн?

Хороший дизайн всегда легко оценить, но тудно создать. Иными словами трепаться про Хороший дизайн (тм) всегда проще, чем сделать его самому.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, VladD2, Вы писали:

VD>На плюсах то? Не, я лучше гавкну.

этим ты нас не удивишь

что касается хорошего дизайна — то знания всех обо всём, на мой взгляд, не обязательны. expr для вычисления нужно только передать функцию (интерфейс) "номер ячейки -> значение". sheet должен предоставлять энумератор. операции должны быть представлены лямбдами. и т.д.

Здравствуйте, VladD2, Вы писали:

VD>Лучше все же перенести вычисления в Sheet

в конечном счёте у тебя выходит, что всю логику надо перенести в sheet и там уж приготовить знатное спагетти

Здравствуйте, VladD2, Вы писали:

K>>Согласен, просто не задавался целью оптимального решения. Premature optimization типа

VD>Там в условиях сказано:
VD> — Оптимизировать производительность для громадных таблиц.

ясно, просто я не обратил на это внимания

VD>>>В прочем, задача сложна для решения на С++ или Яве, а на языках с паттерн-матчнгом она именно что выявляет инженерные (архитекторские) способности.

K>>Не покажешь высший пилотаж?

VD>На плюсах то? Не, я лучше гавкну. Меня последние 3 года тошнит когда приходится на этом языке писать. Ощущения такие как будто в наручниках сидишь.

Ну почему же на плюсах, на Немерле хочется увидеть близкий к идеалу вариант.

Здравствуйте, VladD2, Вы писали:

VD>Ясно...

VD>Но тогда опять же... зачем is? Можно же так:
VD>

VD>def eval(e1, e2, root)
VD>{
VD>    // Зачем эти is-ы?
VD>    | (Literal(e1), Literal(e2), Add) => Literal(e1 + e2)
VD>    | (String(e1),  String(e2),  Add) => String (e1 + e2)
<skipped>
VD>

Понятно, просто плохо умею готовить матчи

Здравствуйте, VladD2, Вы писали:

K>>Expr -> Sheet: Expr знает только о Sheet, т.к. ему нужно по ходу вычислений менять другие ячейки.

VD>Тогда разумно переместить вычисление в Sheet... наверно.

Как раз таки мне кажется, что это совсем не разумно. Тогда я думаю получится каша, все переместится в Sheet. Я пытался выделить минимально зависимые друг от друга отдельные сущности. А так получается, выражению для вычисления грубя говоря нужно знать только свой контекст (контекст в данном случае это Sheet).

K>>Координаты Cell не хранятся в Sheet, Cell'ы могли быть представлены, списком, мапом итд. Cell'У нужно знать свои координаты, для обнаружения циклов, а координаты не доступны из Sheet'а.

VD>Опять же стоит подумать над тем, чтобы перенести логику обнаружения циклов в Sheet.

Можно подумать.

VD>Мне еще не понравилось то, что свойства Parent и Parent класса Sheet можно менять извне Sheet-а.

У Sheet'а нет свойства Parent, он есть у Cell'ов. Они хранят ссылку на тот Sheet, которому они принадлежат. То что их можно менять, да минус, сделано для простоты, иначе надо думать вот над чем. Если Parent передавать в конструкторе, то возникает ситуация, что Cell'ы иногда нужно создавать без Sheet'a. Точнее сначала создаются Cell'ы, потом только Sheet.

VD>Лучше все же перенести вычисления в Sheet, а Cell и Expr сделать чистыми хранилищами данных. В прочем, мне так же не ясно зачем вообще нужен Cell. Возможно разумнее было бы отказаться от него добавив в Expr вхождение позволяющиее хранить сообщение об ошибке.

Как то мне это не нравится. У меня была такая простая мысль, которая первая в голову наверное и пришло: Sheet хранилище Cell'ов, а Cell'ы в свою очередь могут быть либо числом, текстом, ошибкой, пустотой или формулой (да, надо было назвать это формулой, на Expr). А в свою очередь формула (Expr) по сути AST, может быть умножением, сложением, ..., числом, строкой. Все это сразу нарисовалось в виде АТД.

VD>Ну, и наврено более разумно не менять, при вычислении, значение в саомо Sheet, а создавать новый Sheet с вычесленными значениями.

Да я думал над этим, изначально хотел, чтобы все мои структуры были по природе immutable. Только вот по ходу решения для упрощения (наверное на самом деле получилось наоборот) пришлось от этой мысли отказаться.

VD>Кстати, вместо сакроса Acssesor теперь удобнее использовать упрощенный синтаксис объявления свойств. Так твои свойства можно будет объявить следующим образом:
VD>

VD>public partial class Sheet
VD>{
VD>    public Rows    : int                          { get; private set; }
VD>    public Columns : int                          { get; private set; }
VD>    public Marks   : Hashtable[(int * int), bool] { get; private set; }
VD>    public Sheet   : array [2, Cell]              { get; private set; }
VD>  ...
VD>

VD>И Marks, наверно, не стоит делать полем. Это структура нужна только на время вычисления. Ее следут созоавать в функции вычисления.

Ясно, а насчет Marks согласен, сам сначала тоже так хотел сделать, передавать его в Cell.Eval(marks = null) как параметр по умолчанию. При первом вызове при передаче null создать marks и далее уже передавать ссылку на этот marks. Вот.

Здравствуйте, Kisloid, Вы писали:

K>Ну почему же на плюсах, на Немерле хочется увидеть близкий к идеалу вариант.

Времени мало. Да и не гений я. Меж тем тут рядом бегает куча генеев с морем свободного времени. Будет время — попробую что-то подоптимизировать в твоем коде.

Кстати, поглядеть на плюсовый вариант я бы не отказался. Ну, или на C#-пный.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, BulatZiganshin, Вы писали:

BZ>в конечном счёте у тебя выходит, что всю логику надо перенести в sheet и там уж приготовить знатное спагетти

Дык, а накой ее запихивать в варианты, особенно если это приводит к проблемам?

Как вариант, можно оставить алгоритмы как есть, а вынести только зависимости. Скажем, можно передавать ссылки на интерефейсы или функции которые отделят реализацию от знаний о структуре других классов.

... << RSDN@Home 1.2.0 alpha rev. 637>>

С учетом замечаний немного улучшил дизайн. Поменял способ детектирования циклов. А основное улучшение подсмотрел у NotGonnaGetUs, через введение интерфейса (честно сам я до такого почему то не додумался, точнее не подумал об этом

):

IContext.n

    public interface IContext
    {
        GetCell(i : int, j : int) : Cell;
        GetCellPosition(cell : Cell) : int * int;
        GetStartPosition() : int * int;
    }

Теперь Sheet реализует этот интерфейс, а Cell и Expr в методе Eval получают ссылку на этот интерфейс. Что уменьшает связность и уменьшает потенциально возможность ошибок.

Expression.n

    public variant Expr
    {
        | Literal { v  : int;             }
        | String  { s  : string;          }
        | Add     { e1 : Expr; e2 : Expr; }
        | Sub     { e1 : Expr; e2 : Expr; }
        | Mul     { e1 : Expr; e2 : Expr; }
        | Div     { e1 : Expr; e2 : Expr; }
        | Ref     { i  : int;  j  : int;  }

        static public BuildExpr(s : string) : Expr
        {
            def parse(s)
            {
                try
                {
                    if (Char.IsDigit(s[0]))
                        Expr.Literal(Convert.ToInt32(s))
                    else
                    {
                        def i = Convert.ToInt32(s.Substring(1)) - 1;
                        def j = Convert.ToInt32(Char.ToUpper(s[0])) - Convert.ToInt32('A');
                        Expr.Ref(i, j)
                    }
                }
                catch
                { | e => throw ParseException(e) }
            }
            
            def build(tokens, ind)
            {
                if (ind >= 2)
                    match (tokens[ind - 1][0])
                    {
                        | '+' => Expr.Add(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '-' => Expr.Sub(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '*' => Expr.Mul(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | '/' => Expr.Div(build(tokens, ind - 2 ), parse(tokens[ind]))
                        | _   => throw ParseException()
                    }
                else
                    parse(tokens[ind])
            }
        
            // preprocessing source string
            mutable str = "";
            s.Iter(fun(c) {
                if (['+', '-', '*', '/'].Contains(c))
                    str += " " + c.ToString() + " " 
                else
                    str += c.ToString()
            });

            def tokens = 
                str.Split(array [' '], StringSplitOptions.RemoveEmptyEntries);
            build(tokens, tokens.Length - 1)
        }
        
        public Eval(context : IContext) : Expr
        {
            def eval(e1, e2, root)
            {
              | (Literal(e1), Literal(e2), _ is Add) => Literal(e1 + e2)
              | (Literal(e1), Literal(e2), _ is Sub) => Literal(e1 - e2)
              | (Literal(e1), Literal(e2), _ is Mul) => Literal(e1 * e2)
              | (Literal(e1), Literal(e2), _ is Div) =>
                  when (e2 == 0)
                      throw EvalException("div to 0");
                  Literal(e1 / e2)

              | (_, _, _) => throw EvalException("eval")
            }

            match (this)
            {
                | Literal (_) => this
                | String  (_) => this
                | Add     (e1, e2) => eval(e1.Eval(context), e2.Eval(context), this)
                | Sub     (e1, e2) => eval(e1.Eval(context), e2.Eval(context), this)
                | Mul     (e1, e2) => eval(e1.Eval(context), e2.Eval(context), this)
                | Div     (e1, e2) => eval(e1.Eval(context), e2.Eval(context), this)
                | Ref     (i,  j ) => 
                    match (context.GetCell(i, j).Eval(context))
                    {
                        | Number (n) => Literal(n)
                        | Text   (s) => String(s)
                        | _          => throw EvalException("eval")
                    }
            }
        }
    }

Cell.n

    public variant Cell
    {
        | Expression { e : Expr;   }
        | Number     { n : int;    }
        | Text       { s : string; }
        | Error      { s : string; }
        | Nil

        public Eval(context : IContext, firstEval : bool = false) : Cell
        {
            match (this)
            {
                | Expression (e) =>
                    unless (firstEval)
                    {
                        def stPos = context.GetStartPosition();
                        def pos   = context.GetCellPosition(this);
                        when (stPos[0] == pos[0] && stPos[1] == pos[1])
                            throw EvalException("cycle");
                    }

                    match (e.Eval(context))
                    {
                        | Literal (l) => Cell.Number(l)
                        | String  (s) => Cell.Text(s)
                        | _           => throw EvalException("eval")
                    }

                | _ => this
            }
        }

        public override ToString() : string
        {
            match (this)
            {
                | Expression (e) => e.ToString()
                | Number     (n) => n.ToString()
                | Text       (s) => s
                | Error      (s) => "#" + s
                | Nil        => ""
            }
        }
    }

Sheet.n

    public class Sheet : IContext
    {
        [Accessor] mutable rows    : int;
        [Accessor] mutable columns : int;

        mutable startPosition : int * int;

        mutable sheet : array [2, Cell];
    
        public this(n : int, m : int, a : array [2, Cell])
        {
            rows    = n;
            columns = m;
            sheet   = a;
        }
        
        public Eval() : void
        {
            for (mutable i = 0; i < rows; i++)
                for (mutable j = 0; j < columns; j++)
                {
                    try
                    {
                        startPosition = (i, j);
                        sheet[i, j] = sheet[i, j].Eval(this, true);
                    }
                    catch
                    {
                        | e is EvalException =>
                            sheet[i, j] = Cell.Error(e.Message)

                        | _ => throw
                    }
                }
        }

        public GetCell(i : int, j : int) : Cell
        {
            sheet[i, j]
        }

        public GetCellPosition(cell : Cell) : int * int
        {
            mutable res = (-1, -1);
            for (mutable i = 0; i < rows; i++)
                for (mutable j = 0; j < columns; j++)
                    when (sheet[i, j].Equals(cell))
                        res = (i, j);
            res
        }

        public GetStartPosition() : int * int
        {
            startPosition
        }
        
        public override ToString() : string
        {
            mutable res = "";
            for (mutable i = 0; i < rows; i++)
            {
                for (mutable j = 0; j < columns; j++)
                    res += sheet[i, j].ToString() + "\t";
                res += "\n"
            }
            res
        }
        
        public Item [i : int, j : int] : Cell
        {
            get { sheet[i, j] }
            set { sheet[i, j] = value }
        }
    }

Здравствуйте, VladD2, Вы писали:

VD>Кстати, поглядеть на плюсовый вариант я бы не отказался. Ну, или на C#-пный.

Лично я нафиг, на плюсах писать решение никакого желания нет, кстати тут рядом, человек решил на Джаве. Я вот время будет, попробую на CL привести решение.

Здравствуйте, Kisloid, Вы писали:

VD>>Кстати, поглядеть на плюсовый вариант я бы не отказался. Ну, или на C#-пный.

K>Лично я нафиг, на плюсах писать решение никакого желания нет, кстати тут рядом, человек решил на Джаве. Я вот время будет, попробую на CL привести решение.

Он только каркас описал. Причем не сильно думая о будущем расширении. Там еще писать и писать. В том-то и разница, что каркас на Яве больше по объему чем решение на языке с паттерн-матчингом.

Ну, а поглядеть хотелось бы именно чтобы сравнить выразительность. Причем Явский и C#-пный варианты — это конечно хорошо, но хотелось бы и С++-ный увидить. У С++ большие пробемы в облсти управления памтью, но зато много разных хитростей которые так же кое что могут.

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, NotGonnaGetUs, Вы писали:

Здорово отвечаешь.

Кстати по твоему решению на Жабе — решение хорошее, тока не прокомментируешь интерфейс IVarResolver? Странный он какой-то — берет строку, и преобразует ее в CExpr (так у тебя мое Value называется). Что в строке? Какой смысл у него — простым человеческим языком?

Здравствуйте, Kisloid, Вы писали:

М-дя. Страшно как-то получается. ОО дизайн, приправленный паттерн-матчингом. Брр...

На мой взгляд, некрасиво получилось. На Немерле, мне кажется, можно сделать лучше.

Здравствуйте, Gaperton, Вы писали:

G>Кстати по твоему решению на Жабе — решение хорошее, тока не прокомментируешь интерфейс IVarResolver? Странный он какой-то — берет строку, и преобразует ее в CExpr (так у тебя мое Value называется). Что в строке? Какой смысл у него — простым человеческим языком?

На пальцах примерно так...

Выражение Expr — состоит из констант, функций и именованных значений.
Например, в выражении 1 + 2 * variable1 — variable2 используются
константы — 1, 2
функции — +,*
именованные значения — variable1, variable2

Чтобы вычислить выражение нужно уметь доставать значения по их имени и вычислять функции.

IVarResolver { CExpr resolve(String variableName); } служит для получения значений по их именам.
На входе имя — на выходе значение.
Откуда будут браться значения уже не важно.

В частности, имена переменных могут соответствовать "именам" ячеек в таблице.

В принипе, можно было бы преобразовать IVarResolver в IVarContext c интерфейсом
bool isBoundedVariable(String)
CExpr getVariableValue(String)
setVariableValue(String, CExpr)
и добавить функцию связывания ':=' в expr.

Тогда модуль expr можно было бы использовать не только в ячейках таблицы, но и как скриптовый язык

Но поскольку рефакторинг к этому достаточно очевиден, а нужны в переменных пока не видно, то я ограничился IVarResolver'om.

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Поясни, плз, что ты имеешь ввиду. О каких именно расширениях идёт речь? Что, кроме парсера, там нужно ещё написать?

Так по мелочи. От прокета/мэйка до реализации методов и вспомогательных классов.
Идеологически все конечно ясно. Но интересно поглядеть на полную реализацию.

NGG>Строчек, конечно, больше получается... Но суть-то в том, что наличие паттерн-матчинга и вариантов не гарантирует хорошего дизайна и, в какой-то степени,

Согласен. Это в общем-то очевидно. Вопрос только в том, что иногда с точки зрения императивного программиста "хороший дизайн" это нечто понятное ему, а плохой — нечто не понятное. В данном случае я со многими твоими замечаниями согласен.

NGG>даже поощряет дублирование кода, как это видно в примере решения на немерле.

А что в нем видно то? Ну, решил человек как пришло в глову с первого раза. Писал бы он на Яве получил бы тот же эффект только с еще большим объемом кода.

NGG>А кодирование упрощает, да.

Он и чтение упрощает. Суть понять проще.

NGG>На хаскеле писать решение мне больше понравилось, чем на java: http://nggu.livejournal.com/663.html

Это понятно. Но мне как раз интересно работающее и полное решение на Яве. Вообще оптимально было бы если она на J# было бы, а то возиться с Явой влом

... << RSDN@Home 1.2.0 alpha rev. 637>>

Здравствуйте, Gaperton, Вы писали:

G>М-дя. Страшно как-то получается. ОО дизайн, приправленный паттерн-матчингом. Брр...

А можно подробнее, где именно, какие минусы с точки зрения дизайна? Например можешь сравнить со своим решением на Эрланге.

G>На мой взгляд, некрасиво получилось. На Немерле, мне кажется, можно сделать лучше.

Естественно можно

ЗЫ: кстати я немного улучшал, смотреть нужно здесь.

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Здравствуйте, Gaperton, Вы писали:

G>>Кстати по твоему решению на Жабе — решение хорошее, тока не прокомментируешь интерфейс IVarResolver? Странный он какой-то — берет строку, и преобразует ее в CExpr (так у тебя мое Value называется). Что в строке? Какой смысл у него — простым человеческим языком?

NGG>IVarResolver { CExpr resolve(String variableName); } служит для получения значений по их именам.

То есть, то что он берет аргументом строку, а не ref — это у тебя сделано специально. Таким образом, движок формул не знает, что такое ссылка, он просто резолвит аргумент, который, не является числом. Круто, зачот! Полная развязка движка выражений от таблицы.

Ну, дружище, что я могу сказать — это самый крутой дизайн из тех, что я видел!

Только я бы этот интерфейс реально "контекстом" назвал, как ты ниже написал.

И еще небольшое замечание — уже за рамками задания, но у тебя и дизайн крут, он такие вопросы провоцирует. При добавлении операции вида SUM(A1:A10) что делать будешь?

Здравствуйте, Gaperton, Вы писали:

G>>>Кстати по твоему решению на Жабе — решение хорошее, тока не прокомментируешь интерфейс IVarResolver? Странный он какой-то — берет строку, и преобразует ее в CExpr (так у тебя мое Value называется). Что в строке? Какой смысл у него — простым человеческим языком?

NGG>>IVarResolver { CExpr resolve(String variableName); } служит для получения значений по их именам.

G>То есть, то что он берет аргументом строку, а не ref — это у тебя сделано специально. Таким образом, движок формул не знает, что такое ссылка, он просто резолвит аргумент, который, не является числом. Круто, зачот! Полная развязка движка выражений от таблицы.

G>Ну, дружище, что я могу сказать — это самый крутой дизайн из тех, что я видел!

Только я бы этот интерфейс реально "контекстом" назвал, как ты ниже написал.

G>И еще небольшое замечание — уже за рамками задания, но у тебя и дизайн крут, он такие вопросы провоцирует. При добавлении операции вида SUM(A1:A10) что делать будешь?

Я конечно не NotGonnaGetUs, но захотелось влезть со стороны.

На первый взгляд для SUM(A1:A10) поступать примерно как в Excel
1. В CExpr добавить Array
2. A1:A10 считать или Var-ом или вводить Range
3. В IVarResolver.resolve в ответ на A1:A10 возвращать Array
4. Доработать напильником Expr.Func для произвольного кол-ва аргументов
5. Поправить Add и прочие в соответствии с новым Func
6. Добавить функцию SUM
6. Доработать парсер

Вроде все.

... << RSDN@Home 1.2.0 alpha rev. 784>>

Здравствуйте, VladD2, Вы писали:

VD>Ну, а поглядеть хотелось бы именно чтобы сравнить выразительность. Причем Явский и C#-пный варианты — это конечно хорошо, но хотелось бы и С++-ный увидить. У С++ большие пробемы в облсти управления памтью, но зато много разных хитростей которые так же кое что могут.

Вот, например, решение на С++ от _winnie: http://www.everfall.com/paste/id.php?c9dn0t8ffx43

Ещё вот от some41: http://eltoder.pisem.net/temp/tbl.cc.html

И ещё от Alex Mizrahi: http://thesz.livejournal.com/288662.html#cutid1

А вот на Си от Ivan A. Kosarev: http://unicals.com/download/excel.zip

А вот на Java от Anatoli Klassen http://www.26th.net/public/development/SpreadSheet.java

Ну и до кучи другие попавшиеся мне решения (в порядке появления):

На Хаскелле:

от Сергея: http://thesz.livejournal.com/281937.html
от Булата: http://www.haskell.org/haskellwiki/Ru/Problem_K
(скромно так) моё: http://geniepro.livejournal.com/2722.html
от NotGonnaGetUs: http://nggu.livejournal.com/663.html

и на Ерланге: окончательное решение Гапертона: http://gaperton.livejournal.com/7229.html

Здравствуйте, geniepro, Вы писали:

me> Ну и до кучи другие попавшиеся мне решения (в порядке появления):

Забыл упомянуть решение на Лиспе от Alex Mizrahi: http://thesz.livejournal.com/289017.html#cutid1

Здравствуйте, Gaperton, Вы писали:

G>И еще небольшое замечание — уже за рамками задания, но у тебя и дизайн крут, он такие вопросы провоцирует. При добавлении операции вида SUM(A1:A10) что делать будешь?

Примерно так:

Новый тип значений + поддержка произвольных функций:

abstract class CExpr
{
    ...
    public static class Array extends CExpr
    {
        private CExpr[] values;
        public Array(CExpr... values) { this.values = values; }
        public  CExpr[] getValues() { return values; }
        public String toFormattedString() { return Arrays.asList(values).toString(); }
    }
}

abstract class Expr
{
    ...
    public static class Func extends Expr
    {
        private IFunction f;
        private Expr[] args;

        public Func(IFunction f, Expr... args) { this.f = f; this.args = args; }
        public CExpr evaluate(IVarResolver resolver) { return f.evaluate(resolver, args); }
    }
}

interface IFunction {
    enum Type {UnaryPostfix, UnaryPrefix, Infix, Standart }

    //информация о функции для парсера
    String getName();
    Type getType();
    int getPriority();

    CExpr evaluate(IVarResolver resolver, Expr... args);
}

Список поддерживаемых функций зависит от контекста использования Expr:

class ExprParser {
    IFunction[] supportedFunctions;
    public ExprParser(IFunction[] supportedFunctions) { this.supportedFunctions = supportedFunctions; }
    Expr parse(String text) { ...; }
}

Переделка уже существующих функций минимальна.

abstract class Function implements IFunction
{
    public int getPriority() { return 0; }

    public CExpr evaluate(IVarResolver resolver, Expr... args)
    {
        CExpr[] evaluatedArgs = new CExpr[args.length];
        for (int i = 0; i < args.length; i++)
            evaluatedArgs[i] = args[i].evaluate(resolver);
        return evaluate(evaluatedArgs);
    }

    protected abstract CExpr evaluate(CExpr... args);
}

abstract class BinaryFunction extends Function {
     public  Type getType() { return Type.Infix; }
     public final CExpr evaluate(CExpr... args) {
         if (args.length != 2) return new CExpr.Error("ArgsCount");
         return evaluate(args[0], args[1]);
     }
     public abstract CExpr evaluate(CExpr a, CExpr b);
}

class Add extends BinaryFunction
{
    public String getName() { return "+"; }
    public int getPriority() { return 1; }

    public CExpr evaluate(CExpr a, CExpr b)
    {
        if (a instanceof CExpr.Number && b instanceof CExpr.Number)
        {
            return evaluate((CExpr.Number) a, (CExpr.Number) b);
        }
        return new CExpr.Error("add");
    }

    public CExpr evaluate(CExpr.Number a, CExpr.Number b)
    {
        return new CExpr.Number(a.getValue() + b.getValue());
    }
}

Реализация SUM(A1:A10):

class Sum extends Function
{
    public String getName() { return "SUM"; }
    public IFunction.Type getType() { return IFunction.Type.Standart; }

    public CExpr evaluate(CExpr... args) { 
       ...;  //в качестве аргументов могут быть числа и/или массивы чисел.
    }
}

class CellRange implements IFunction
{
    public String getName() { return ":"; }
    public int getPriority() { return 3; }
    public Type getType() { return Type.Infix; }

    public CExpr evaluate(IVarResolver resolver, Expr... args)
    {
        if (args.length != 2) return new CExpr.Error("Range");
        Expr a = args[0];
        Expr b = args[1];
        if (a instanceof Expr.Var && b instanceof Expr.Var) {
            String[] names = getNamesInRange(((Expr.Var)a).getName(), ((Expr.Var)b).getName());
            ...; //по именам достаём значения переменных и кладём в массив
            return new CExpr.Array(...);
        } 
        return new CExpr.Error("Range");
    }
}

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>После хаскелля у меня небольшая аллергия на java/c# образовалась

Да не говори...
Какая-то ломка наступает

Но, после вот поста Mirrorerа есть ощущение, что не всё потеряно

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Здравствуйте, Gaperton, Вы писали:

G>>И еще небольшое замечание — уже за рамками задания, но у тебя и дизайн крут, он такие вопросы провоцирует. При добавлении операции вида SUM(A1:A10) что делать будешь?

NGG>Примерно так:

А это ничего, что у тебя Array наследуется от CExpr? Видишь ли, Array не может являться валидным значением клетки таблицы, и, следовательно, не может быть использован во всех контекстах, где применяется CExpr. Имеет место быть нарушение принципа подстановки Лисков.

Здравствуйте, Gaperton, Вы писали:

G>А это ничего, что у тебя Array наследуется от CExpr? Видишь ли, Array не может являться валидным значением клетки таблицы, и, следовательно, не может быть использован во всех контекстах, где применяется CExpr. Имеет место быть нарушение принципа подстановки Лисков.

А Барбара идёт мимо. Её принцип говорит о том, что при наследовании B от A, В должен соблюдать контракты навешанные на A.
А какие контракты нарушает Array?

CExpr не является значением клетки. Это примитив в expression-языке, который знать не ведает о том, что бывают Cell'ы и какие на них накладываются ограничения.

Ограничение на возможные значения в Cell задаются в методе Cell.Evaluate. Чтобы сделать это ограничение явным, можно ввести класс CellValue:

сlass CellValue {
    public CellValue(CExpr value) {
         this.value = isNotValidValue(value) ? new CExpr.Error("Type") : value;
    }
    public CExpr getValueAsCExpr() { return value; }
}

Мне, конечно, стоило привести изменения в классе Cell после добавления Array, но мы ведь тут примерчиками забавляемся.
И так пол обеда времени потратил на то сообщение

Кстати, CExpr — это невычислимая константа. Название образовано от ConstantExpr, а не СellExpr. Это второвой вариант перевода вызвал к жизни прозвучавший вопрос ?

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Здравствуйте, Gaperton, Вы писали:

G>>А это ничего, что у тебя Array наследуется от CExpr? Видишь ли, Array не может являться валидным значением клетки таблицы, и, следовательно, не может быть использован во всех контекстах, где применяется CExpr. Имеет место быть нарушение принципа подстановки Лисков.

NGG>А Барбара идёт мимо. Её принцип говорит о том, что при наследовании B от A, В должен соблюдать контракты навешанные на A.
NGG>А какие контракты нарушает Array?

Ее принцип про "контракт" ничего не говорит

. Он гласит, для любого подтипа А, и подсистемы С, использующей А, поведение подсистемы С останется валидным при подстановке В вместо А.

Отсюда и "подстановка". Такое определение покрывает и неявные контракты в том числе. Можно по сути применять Array во всех контекстах, что и CExpr, я о найн?

NGG>CExpr не является значением клетки. Это примитив в expression-языке, который знать не ведает о том, что бывают Cell'ы и какие на них накладываются ограничения.

NGG>Ограничение на возможные значения в Cell задаются в методе Cell.Evaluate. Чтобы сделать это ограничение явным, можно ввести класс CellValue:

Убедительно.

Тока типы значения ячейки и expression-языка все равно лучше разделить от греха. Потому как контракт таки нарушается — массив значений нельзя ввести в клетку, и он не может являться ее значением, и быть приведенным к тексту клетки. Вот и не можешь ты подставить Array вместо CExpr, контракт у тебя неявный просто, вот и все.

NGG>

NGG>сlass CellValue {
NGG>    public CellValue(CExpr value) {
NGG>         this.value = isNotValidValue(value) ? new CExpr.Error("Type") : value;
NGG>    }
NGG>    public CExpr getValueAsCExpr() { return value; }
NGG>}
NGG>

NGG>Мне, конечно, стоило привести изменения в классе Cell после добавления Array, но мы ведь тут примерчиками забавляемся.
NGG>И так пол обеда времени потратил на то сообщение

Нормально, это на самом деле мелочи. Круто дизайнишь, палюбому

. Реально, лучше тебя эту задачу не решал никто на моей памяти. А мы на этой задаче в CQG человек сто просеяли.

Эй, коллеги,я нашел живого Человека К!

Здравствуйте, NotGonnaGetUs, Вы писали:

NGG>Кстати, CExpr — это невычислимая константа. Название образовано от ConstantExpr, а не СellExpr. Это второвой вариант перевода вызвал к жизни прозвучавший вопрос ?

Да, ты совершенно прав, именно так я и подумал.

Здравствуйте, Gaperton, Вы писали:

G>Ее принцип про "контракт" ничего не говорит

. Он гласит, для любого подтипа А, и подсистемы С, использующей А, поведение подсистемы С останется валидным при подстановке В вместо А.

Суть-то всё равно такая же. С типом А связан набор утверждений (явных, в форме языковых конструкций выполнение которых гарантируется компилятором, и неявных — остающихся на совести разработчика). Любая подсистема С обязана использовать А основываясь только на этих утверждениях. Если это не так, то подсистема добавляет неявное утверждение. Проблемы начинаются, когда неявные утверждения входят в противоречие друг с другом (тогда можно говорить об LSP) или когда их так много, а документации так мало, что разобраться в них становится крайне затруднительно (хреновый дизайн).

У нас же Сell.evaluate использовал неявное утверждение (верное на тот момент) — любой тип CExpr может быть значением Сell. И это хорошо (с)KISS. Добавление нового подтипа CExpr.Array сделало утверждение неверным и заставило изменить подсистему полагающуюся на него. У нас просто изменилась постановка задачи и это привело к необходимости внести исправления в существующий код. Аналогичная ситуация была с CellRange — потребовалось изменить интерфейс Function, т.к. возникла потребность в вычислении Expr -> CExpr. Я бы не говорил в данном случае о нарушении LSP. В крайнем случае, если бы потребовалось вносить много изменений, можно было бы обвинить в игнорировании OCP (с)Бертран Мейер и/или плохом анализе задачи, пропустившим вероятные изменения требований.

На самом деле, серьёзной переработки требуют реализации функций (Add, Sum, etc), т.к.
каждая не типизированная функция CExpr* -> CExpr это, на самом деле, набор типизрованных функций + алгоритм выбора подходящей функции.
Чтобы избавиться от дублирования логики выбора и гирлянд instanseof, нужно
— сделать типизированные функции явными и определиться с форматом их описания (для алгоритма выбора).
— вынести перобразования типов (CExpr.Text -> CExpr.Number, etc) в интерфейс.
— вынести стратегии выбора типизрованных функций (разрешение конфликтов, использование преобразования типов, etc).
— определить интерфейсы фабрик функций, чтобы каждый контекст мог "тюнинговать" функции под себя.
Для задачи в начальной постановке это слишком, но с поступлением новых пожеланий вполне себя окупит.

G>Нормально, это на самом деле мелочи. Круто дизайнишь, палюбому

. Реально, лучше тебя эту задачу не решал никто на моей памяти. А мы на этой задаче в CQG человек сто просеяли.

G>Эй, коллеги,я нашел живого Человека К!

Я просто в восторге от этой новости

	От:	BulatZiganshin
	Дата:	26.11.07 15:40
	Оценка:

	От:	NotGonnaGetUs
	Дата:	21.11.07 15:04
	Оценка:	52 (4)

	От:	Kisloid
	Дата:	20.11.07 17:51
	Оценка:	35 (2)

	От:	Трурль
	Дата:	26.11.07 09:22
	Оценка:	23 (2)

	От:	BulatZiganshin
	Дата:	20.11.07 18:00
	Оценка:	-1

От:	VladD2	www.nemerle.org
Дата:	21.11.07 11:16
Оценка:

От:	Gaperton	http://gaperton.livejournal.com
Дата:	22.11.07 11:36
Оценка:

	От:	Дьяченко Александр
	Дата:	22.11.07 18:20
	Оценка:

От:	geniepro	http://geniepro.livejournal.com/
Дата:	22.11.07 19:33
Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	23.11.07 14:21
Оценка: