`tuple` too complex and breaks LSP

[Chamber6821]

Simpler implementation

Just use polymorhism with head.at

# Tuple.
[head tail] > tuple
  # Empty tuple.
  [] > empty
    0 > length!
    error "Given index is out of tuple bounds" > [i] > at!
  # Obtain the length of the tuple.
  head.length.plus 1 > length!

  # Take one element from the tuple, at the given position.
  [i] > at
    if. > @
      closed-i.eq (^.length.minus 1)
      tail
      head.at closed-i
    i > cached-i!
    if. > closed-i!
      cached-i.ge 0
      cached-i
      ^.length.plus cached-i

Breaks LSP

Current implementation breaks LSP in attribute as-fast:

 [tup len] > at-fast
      if. > @
        (len.plus -1).gt ^.index
        ^.at-fast
          tup.head
          len.plus -1
        tup.tail

tup may not have head and tail. Example:

[t1 t2] > zip
  min t1.length t2.length > length!
  [i] > at
    * > @
      t1.at i
      t2.at i

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i

More useful tuple

I think tuple constructor may be more useful if tuple will be implemented via binary tree:

# Tuple.
[head tail] > tuple
  # Empty tuple.
  [] > empty
    0 > length!

    [i] > at!
      error "Given index is out of tuple bounds"

  # Tuple of one element.
  [el] > single
    1 > length!

    [i] > at!
      if. > @
        i.eq 0
        el
        error "Given index is out of tuple bounds"

  # Obtain the length of the tuple.
  head.length.plus tail.length > length!

  # Take one element from the tuple, at the given position.
  [i] > at
    if. > @
      closed-i.lt ^.head.length
      head.at closed-i
      tail.at (closed-i.minus ^.head.length)
    i > cached-i!
    if. > closed-i!
      cached-i.ge 0
      cached-i
      ^.length.plus cached-i

You can use tuple to concat two other tuples:

tuple > concated
  *
    print-A
    print-B
  *
    print-C
    print-D

[github-actions[bot]]

@Chamber6821 thanks for the report, here is a feedback:

Problems

• Clear Title: Modify the title from "tuple too complex and breaks LSP" to a more descriptive one.
• Specificity: Provide specific details about the issue with the tuple implementation.
• Reproduction Steps: Include clear and concise steps to reproduce the issue.

I would recommend including clear reproduction steps linked to specific code snippets to better illustrate the issue.

Please fix the bug report in order it to get resolved faster. Analyzed with gpt-4

[Chamber6821]

I want create PR, but this is more complex work than just modify EO implementation. Because I need to rewrite part of parser works with * syntax and all parts that uses attribute with. I want to get approval to move in this direction or reject

[Chamber6821]

About attribute with. I think it is shouldn't be part of tuple because the tuple itself plays the role of this attribute. It also leads to duplication when trying to write new implementations of the tuple. Example:

[t1 t2] > zip
  min t1.length t2.length > length
  [i] > at
    * > @
      t1.at i
      t2.at i
  tuple ^ x > [x] > with # same as tuple.with

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i
  tuple ^ x > [x] > with # same as tuple.with

[yegor256]

@maxonfjvipon wdyt?

[maxonfjvipon]

@Chamber6821 such tuple optimization with at-fast is made in order to performance improvements (we validate index and validate own length only once), you may check it here. at-fast is kind of "hidden" inside at attribute and not supposed to be used from outside, only for internal usage.

[maxonfjvipon]

@Chamber6821 about tuple.with attribute. If your object decorates tuple you may not to rewrite with attribute, it'll be called from "decoratee".

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i

map > m
  * 1 2 3
  [el]
    ... # some action here
m.with 4 > new-m # it's valid, you'll get `tuple` with new element injected here

Ofc if you have to rewrite with attribute if you want to get a new map object:

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i
  [x] > with
    map > @
      ^.t.with x
      action

But in such case there'll be no duplication here for every new implementation

[maxonfjvipon]

@Chamber6821 I didn't really understand which part of * you want to rewrite. The * is just syntax sugar for "tuple-ladder":

* 1 2 3
# The same as
tuple
  tuple
    tuple
      tuple.empty
      1
    2
  3

[Chamber6821]

@maxonfjvipon about *. Sorry, it is my mistake. I didn't know what exactly * was turning into (nested tuple or chained tuple.with)

[Chamber6821]

@maxonfjvipon as-fast breaks LSP. Example:

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i

tuple > t1
  map
    * 1 2 3
    [x]
      x.times 2
  "Tail"

Expected that t1 is * 2 4 6 "Tail", but because tuple.at expects that head is kind of tuple we got * 1 2 3 "Tail"

[Chamber6821]

@maxonfjvipon similar problem with zip that has no head and tail

[Chamber6821]

@maxonfjvipon perfornace issue is not reason to break LSP. If you want optimize index calculation you can use special implementation inside compiler:

[head tail] > fast-tuple
  head.length.plus 1 > length!
  # Take one element from the tuple, at the given position.
  [i] > at
    if. > @
      i.eq (^.length.minus 1)
      tail
      head.at i

* 1 2 3
# Turns to
tuple
  fast-tuple
    fast-tuple
      tuple.empty
      1
    2
  3

[Chamber6821]

@maxonfjvipon about with. No. You can't use with from decorated object. Ofc, technically it is possible, but it has no sence

[t action] > map
  t > @
  [i] > at
    action > @
      ^.t.at i

with. > m
  map
    * 1 2 3
    [x]
      x.times 2
  "Tail"

Expected that m is * 2 4 6 "Tail", but because tuple.with links to internal tuple instead of map we got * 1 2 3 "Tail"

[maxonfjvipon]

@Chamber6821 I can agree about LSP in tuple.at attribute, you're right here. The with attribute should belong to tuple and should be rewritten on every new decorator and it won't be the same

[Chamber6821]

@maxonfjvipon but it leads to code repetitions. I think it is significant issue. Logic of tuple.with correct for any decorator. This logic will never be changed in decorators, so we don't need polymorphism here, but user must copy the same implementation that leads to boilerplate

[maxonfjvipon]

@Chamber6821 why it leads to code repetitions?

[head tail] > tuple
  ...
  [x] > with
    tuple ^ x > @

[t action] > map
  ...
  [x] > with
    map > @
      ^.t.with x
      action 

[t1 t2] > zip
  ...
  [x] > with
    zip > @
      ^.t1.with x
      ^.t2.with x

Every new decoration requires new implementation of with attribute. Otherwise when you do map.with - you'll end up with tuple, but not map

[Chamber6821]

@maxonfjvipon because your implementations breaks LSP and principle of least astonishment. map.with and zip.with don't "Create a new tuple with this element added to the end of it." (docstring of tuple.with). Examples

[url] > remote-image
  ...
[filename] > local-image
  ...
map > images
  * "url1" "url2" "url3"
  remote-image
with. > all-images
  images
  local-image "./Picture.png"

Expects: all-images is just tuple of some images Result: undefined behavior for all-images.at -1 because local-image will be provided into remote-image constructor

zip.with is not that bad, but it does something different from the description, making the user wonder what implementation he got in the arguments.

I think there is no reason for with to exist as part of a tuple. it's just not needed for anything

[maxonfjvipon]

@Chamber6821 what's the point of creating new tuple in map.with or zip.with. Imagine tuple is an interface and map and zip implement it. The tuple.with is generator method - the method that returns new instance of an object of the same "type" with new element injected. Why should map.with return tuple but not map. LSP is not broken here.

[Chamber6821]

@maxonfjvipon this is how I perceive thple. And I believe that the decorator is better than the additional method. I don’t know how correct it is to refer to the book Elegant Objects, but chained methods are designated there as an antipattern or undesirable

I think it:

new TpWith(
  tuple
  element
)

better than

tuple.with(element)

[Chamber6821]

@maxonfjvipon This interface imposses more responsibilities to user

interface Tuple {
  Int length()
  Object at(i)
  Tuple with(t, x)
}

than that

interface Tuple {
  Int length()
  Object at(i)
}

[maxonfjvipon]

@Chamber6821 imagine you have multiple implementations of Tuple interface, for every new implementation you would need to create new TpWith type of class. TpWith is just a convenient decorator which may use inner generator method as well. We use it in eo-runtime in many places: here or here. There's nothing wrong with methods chaining if objects are immutable and every method creates new object.

So In order finish this discussion: I agree that we probably should change implementation of tuple.at and make it self-recursive, but we won't move tuple.with out and won't make it a separated object.

[Chamber6821]

@maxonfjvipon maybe I don't understand something about the idea. What difference between tuple constructor and tuple.with. I mean ideologically. Now your explanation of motivation for tuple.with like: we have + 1 2 in Lisp, but we need to add 1 + 2 just because

[maxonfjvipon]

@Chamber6821 for now we have just tuple.with and that's it, it would work the same as tp-with but would require extra object in eo-runtime which we don't want, at least for now

[Chamber6821]

@maxonfjvipon I don't understand why it is require extra object. tp-with is the same as just tuple. Why do we need to add new object in eo-runtime? Just use tuple

[maxonfjvipon]

@Chamber6821 actually you're right, tuple.with was introduced when tuple was an atom and had a way different implementation. Now it's more clear. Maybe we don't really need it now because we can "add" new element just by tuple old element instead old.with element. @yegor256 WDYT?

[Chamber6821]

@maxonfjvipon I also wrote about changing the tuple itself from gluing an element to the end, to gluing two tuples. This implementation can replace chaining tuple.with. Example: Current implementation:

tuple.empty
.with 1
.with 2
.with 3
.with 4
# or
tuple
  tuple
    tuple
      tuple.empty
      1
    2
  3
4

Implementation via binary tree:

tuple
  tuple
    tuple.single 1
    tuple.single 2
  tuple
    tuple.single 3
    tuple.single 4

Last implementation have better asymptotics O(log(N)) vs current implementation O(N). Also I think bin-tree implementation more useful for users. Example:

[t wrap] > rounded
  tuple > @
    wrap
    tuple
      t
      wrap

WDYT?

[maxonfjvipon]

@Chamber6821 how are you going to convert * 1 2 3 to your tuple implementation?

[Chamber6821]

@maxonfjvipon recursive turn it in half (rounded down). Examples:

* 1 2 3 4
# the same
tuple
  tuple
    tuple.single 1
    tuple.single 2
  tuple
    tuple.single 3
    tuple.single 4

* 1 2 3 4 5
# the same
tuple
  tuple
    tuple.single 1
    tuple.single 2
  tuple
    tuple.single 3
    tuple
      tuple.single 4
      tuple.single 5

* 1
# the same
tuple.single 1

I can describe algorithm if you interested

[Chamber6821]

@maxonfjvipon I also think about optimizing compiler that can use native array in real program, but it is raw idea

[maxonfjvipon]

@Chamber6821 we don't want to use native arrays because current java implementation is not forever. We already have javascript runtime, maybe we'll have more. The more objects are implemented in pure EO - the better.

[Chamber6821]

@maxonfjvipon I think the same

[maxonfjvipon]

@yegor256 WDYT about tuple implementation via binary tree? I kind of like but I'm not sure if we really need it, at least for now.

[levBagryansky]

@Chamber6821 If I understood your idea correctly, adding of element to current tuple force us to create a new tuple with changed structure instead of referencing to existing tuple. You have

tuple > my-tuple
  tuple
    tuple.single 1
    tuple.single 2
  tuple
    tuple.single 3
    tuple.single 4

And you want to declare my-tuple.with 5 Which will will be

tuple
  tuple
    tuple.single 1
    tuple.single 2
  tuple
    tuple.single 3
    tuple
      tuple.single 4
      tuple.single 5

I mean it can be too expensive to add a new element to tuple

[Chamber6821]

@levBagryansky No, read about tuple.with in this thread. I think that tuple.with useles and leads to code duplications. If you want add element into end just use tuple

# For current chain implementation 
tuple my-tuple 5
# For implementation via binary tree
tuple
  my-tuple
  * 5

[levBagryansky]

@Chamber6821 I see. So tuple.at will be smth like

[start tail] > tuple
  [i] > at
    if > @
      i.gte start
      tail.at (i.minus start.length)
      start.at i

Looks good

[maxonfjvipon]

@Chamber6821 we're not sure about implementation via binary tree. For now you can fix the bug in a separated PR with tuple.at which breaks LSP as we discussed above

[Chamber6821]

@maxonfjvipon what about tuple.with?

[maxonfjvipon]

@Chamber6821 let's leave it for now, the less changes in PR - the better