why properties should be flat

[juan_gandhi]

My talk from 2014
 

Comments

[bytebuster]

Потерялся после 13-го слайда. :( Но считаю, как для самоучки без базового матана по теории категорий — нормально. :)

Вот хорошие слайды, очень близко к вашей лекции: Railway Oriented Programming



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

[juan_gandhi]

Да, наверно, без сопровождающего рассказа сложно понять, о чем там речь-то вообще.

Тайский парсить! Там задача сегментации...

[bytebuster]

Начало я понял, это ж типичная проблема, сплошь и рядом возникает при кодировании. Но вот потом я уперся в то, что если у нас есть строго последовательность вычислений (вот там, где на 12/13-м слайде про DOB), то чаще всего дальнейшие вычисления не имеют смысла.

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

А если не зависит, то речь идет о concurrent tasks, и программист должен был бы это разделить средствами языка. А если не разделил, то бить по рукам, потому что он подложил мину под будущее scalability.

Разве нет?

[bytebuster]

Тайский. Парсить. Parsec'ом. Точнее, его FSharp'овым клоном, FParsec. Собственно, автор ФПарсека меня на StackOverflow и пригласил.

Он потом еще где-то в блоге писал, что это единственный известный ему случай, где монадическим парсером парсится natural human language; он-то привык к DSL'ям. :))

Точнее, не сегментации, а syllabification. Потому там и FParsec, что накопительно парсим и, в случае чего, rollback.

[sassa_nf]

Well, flattening the structure also means you cannot distinguish absence of the object:

was: {x: {y: z, s: t}} - missing x means both y and s are also missing
flat: {x.y: z} - is x missing or not?

[sassa_nf]

rather, the piece that produces x: {y:..., z:...} now needs to be aware of where in the resulting structure it is. And the piece producing y:... needs to be aware where in the x:... it is. Etc.

[juan_gandhi]

Oh, no. No way. That's another principle. Children should not be aware of their parents.

[sassa_nf]

Right. So how does one produce a flat structure from a tree?

function* toJSON(x) {
  if (typeof x === 'string') {
    yield '"';
    yield escape(x);
    yield '"';
    return;
  }
  if (typeof x === 'number') {
...  }
  if (typeof x === 'boolean'
...
  }
  yield '{';
  let first = true;
  for (let k in x) {
    if (!first) yield ',';
    first = false;
    yield '"' + k + '": ';
    yield* toJSON(x[k]);
  }
  yield '}';
}

Straightforward streaming of keys, values, delimiters. No one is aware of anyone's parents or children.

If we were to flatten it first, then somewhere need to distinguish that they are part of objects, so the correct keys can be produced in the output.

function* toJSON(k, x) {
  if (typeof x === 'object') {
    for (let k1 in x) {
      yield* toJSON(k? k + '.' + k1: k1, x[k1]);
    }
    return;
  }
  if (k) {
    yield '"';
    yield k;
    yield '":';
  }

  if (typeof x === 'string') {
    yield '"';
    yield escape(x);
    yield '"';
    return;
  }
  if (typeof x === 'number') {
...  }
  if (typeof x === 'boolean'
...
  }
}

[juan_gandhi]

There's a 1-1 correspondence with a tree-like structure, so it's up to you to decide what it means, "missing".

[sassa_nf]

Not sure what you mean by 1-1 correspondence.

[{"a": 1}, {"b": 2}] JSON has a corresponding flat structure of ....?

ok, then:
{"a":[{"b": 1}, {"c": 2}]} JSON has a corresponding flat structure of "a.0.b: 1", "a.1.c: 2". But what JSON does the flat structure "a.0.b: 1", "a.2.c: 2" correspond to?

[juan_gandhi]

1. 0.a -> 1, 1.b -> 2
2. 1.0.b -> 1, a.1.c -> 2
3. ("a.0.b: 1", "a.2.c: 2") ===> {"a":{"0":{"b":"1"}, "2":{"c":"2"}}

Remember, we are dealing with JavaScript object notation.

[sassa_nf]

No, it's not quite like that.

> x = {0:1, 2:3}
{ '0': 1, '2': 3 }
> x.length
undefined
> [1,,3]
[ 1, , 3 ]
> [1,,3].length
3

[juan_gandhi]

That's because of types are ascribed to the values.
If we could pass around [1,,3] as Json, then the mapping can be improved; but in "regular languages" having arrays with holes is questionable.

[sassa_nf]

It's not about arrays with holes. JSON for them will have null instead of a hole. That's not the same as {0: 1, 2: 3}. Arrays have length and order of elements.

Maybe I am a bit slow, but yes, we can ascribe properties to certain objects. But you need to encode those properties so that you can restore them upon decoding. Like in JSON those properties are encoded by using square brackets. In a flat structure everything looks the same, so you need to invent markers, like extra constructed fields (length? plus _isArray?).

I recall what stunts people adopt to read a list of properties from Java's .properties files, which _are_ flat. :-)

[arstmas]

кот хорош