I have a question about a particular case I'm working on. I'm studying
OOP. To ask the question, I'm going to have to introduce you my context
here, so you'll need to bear with me. If you'd like to see the question
right away, go to the section ``My difficulty in encapsulating a
union''.

(*) Introduction

I wrote the classes

class Empty:
...
class Pair:
...

With them, I can (sort of) make a union of them and build a Lisp-like
list by defining that my Lisp-like list is either Empty or a Pair. For
instance, here's a Lisp-like sequence that represents the string "abc".

>>> Pair.fromIterable("abc")
Pair('a', Pair('b', Pair('c', Empty())))

So far so good. (``Full'' code at the end of this message, if you'd
like to more carefully look into my reasoning there.)

(*) How to build a stack?

These Lisp-like sequences are clearly a stack. You pop an element from
it by grabbing the first element. You push an element on to it by just
pairing the new element with the current stack. For instance, let's pop
the 1-string "a" off of the stack.

>>> ls = Pair.fromIterable("abc")
>>> ls.first
'a'
>>> ls = ls.rest
>>> ls
Pair('b', Pair('c', Empty()))

Done. Let's push it back on.

>>> ls = Pair("a", ls)
>>> ls
Pair('a', Pair('b', Pair('c', Empty())))

So far so good, but when it comes to building a better user interface
for it I have no idea how to do it. I think one of the purposes of OOP
is to organize code hierarchically so that we can reuse what we wrote.
So I tried to make a Stack by inheriting Pair.

class Stack(Pair):
pass

>>> Stack(1, Empty())
Stack(1, Empty())

Then I wrote pop and push.

>>> Stack(1, Empty()).pop()
1

>>> Stack(1, Empty()).push(2)
Stack(2, Stack(1, Empty()))

So far so good. Now let me show you what I can't do.

(*) The difficulty of encapsulating a union

The Lisp-like sequences we're building here are union-like data
structures. A /sequence/ is either Empty() or Pair(..., /sequence/). I
have not found a way to represent this either-or datastructure with a
class. For example, there is no way right now to build an empty Stack
by invoking the Stack constructor.

>>> Stack()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: Pair.__init__() missing 2 required positional arguments: 'first' and 'rest'

As I designed, an empty Stack is represented by Empty(), which is a
whole other object. Users will have to know this. I wish I did not
have to burden my users with such knowledge. For instance, I wish the
answer was "Stack()" to the question of -- ``how can I build an empty
stack?''

My desire seems to imply that I need a union-like data structure. If
Stack is invoked with no arguments, it should produce Empty(), otherwise
it produces Pair() as it does today.

How can I achieve that?

(*) Code

class Pair:
def __init__(self, first, rest):
if not isinstance(rest, Pair) and not isinstance(rest, Empty):
raise ValueError("rest must be Empty or Pair")
self.first = first
self.rest = rest
def fromIterable(it):
if len(it) == 0:
return Empty()
else:
return Pair(it[0], Pair.fromIterable(it[1:]))
def __str__(self):
return "{}({!r}, {})".format(self.__class__.__name__, self.first, str(self.rest))
def __repr__(self):
return str(self)
def __len__(self):
return 1 + self.rest.__len__()

class Empty:
def __len__(self):
return 0
def __str__(self):
return "Empty()"
def __repr__(self):
return self.__str__()
def __new__(clss):
if not hasattr(clss, "saved"):
clss.saved = super().__new__(clss)
return clss.saved

class Stack(Pair):
def pop(self):
return self.first
def push(self, x):
return Stack(x, self)

Julieta Shem <jshem@yaxenu.org> writes:
>My desire seems to imply that I need a union-like data structure.

You only need to worry about such things in languages with
static typing. For example, to have a function that can
sometimes return an int value and at other times a string
value in C, one would need a union.

In Python with its dynamic typing, one does not need unions.

def an_int_sometimes_and_sometimes_a_string( x ):
if x:
return 2
else:
return "two"

a_name_for_an_int_sometimes_and_sometimes_string = 2
a_name_for_an_int_sometimes_and_sometimes_string = "abc"

. If you should, however, be talking about the new "type hints":
These are static and have "Union", for example, "Union[int, str]"
or "int | str".

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Julieta Shem <jshem@yaxenu.org> writes:
>>My desire seems to imply that I need a union-like data structure.
>
> You only need to worry about such things in languages with
> static typing. For example, to have a function that can
> sometimes return an int value and at other times a string
> value in C, one would need a union.
>
> In Python with its dynamic typing, one does not need unions.
>
> def an_int_sometimes_and_sometimes_a_string( x ):
> if x:
> return 2
> else:
> return "two"

Nice. This means that I can solve my stack-union problem by writing a
procedure --- say stack(...) --- that sometimes gives me Empty() and
sometimes gives me Stack().

>>> stack()
Empty()

>>> stack(1,2,3,4)
Stack(4, Stack(3, Stack(2, Stack(1, Empty()))))

The user interface of this non-empty case is that we're stacking up the
arguments, hence the number 1 ends up at the bottom of the stack.

def stack(*args):
if len(args) == 0:
return Empty()
else:
return Stack(args[-1], stack(*args[:-1]))

I realize now that I'm using the same solution of the /open()/
procedure. Depending on the arguments, open() produces a different type
of object.

> . If you should, however, be talking about the new "type hints":
> These are static and have "Union", for example, "Union[int, str]"
> or "int | str".

I ended up locating such features of the language in the documentation,
but I actually am not interested in declaring the type to the compiler
(or to the reader).

I was looking for a solution like yours --- thank you! ---, although I
was hoping for handling that situation in the construction of the Stack
object, which was probably why I did not find a way out. Right now I'm
looking into __new__() to see if it can somehow produce one type or
another type of object depending on how the user has invoked the class
object.

Terminology. By ``invoking the class object'' I mean expressions such
as Class1() or Class2(). ``Class1'' represents the object that
represents the class 1. Since the syntax is that of procedure
invokation, I say ``invoking the class object''.

Julieta Shem <jshem@yaxenu.org> writes:

[...]

>> . If you should, however, be talking about the new "type hints":
>> These are static and have "Union", for example, "Union[int, str]"
>> or "int | str".
>
> I ended up locating such features of the language in the documentation,
> but I actually am not interested in declaring the type to the compiler
> (or to the reader).
>
> I was looking for a solution like yours --- thank you! ---, although I
> was hoping for handling that situation in the construction of the Stack
> object, which was probably why I did not find a way out. Right now I'm
> looking into __new__() to see if it can somehow produce one type or
> another type of object depending on how the user has invoked the class
> object.
>
> Terminology. By ``invoking the class object'' I mean expressions such
> as Class1() or Class2(). ``Class1'' represents the object that
> represents the class 1. Since the syntax is that of procedure
> invokation, I say ``invoking the class object''.

An experiment. What's my definition of Stack? It's either Empty or
Pair, so it's a union. So let us create two inner classes (that is,
inner to Stack) and make them behave just like Empty and Pair. Using
__new__(), we can produce a Stack object that is sometimes Empty() and
sometimes Pair(...).

class Stack:
class StackEmpty(Empty):
pass
class StackPair(Pair):
pass
def __new__(clss, *args):
if len(args) == 0:
return Stack.StackEmpty()
else:
return Stack.StackPair(*args)

This does it. However, we are exposing the different types to the user.

>>> Stack()
Empty()

>>> Stack(1, Stack())
Pair(1, Empty())

Since we have our own copies of Empty and Pair inside Stack, we change
their representation.

class Stack:
class StackEmpty(Empty):
def __str__(self):
return "Stack()"
def __repr__(self):
return str(self)
class StackPair(Pair):
def __str__(self):
return "Stack({!r}, {})".format(self.first, str(self.rest))
def __repr__(self):
return str(self)
[...]

>>> Stack()
Stack()

>>> Stack(1, Stack())
Stack(1, Stack())

That's it. That's what I was looking for. However, I don't really like
the OOP approach here because of what's going to happen next.

Now we are free to move on with implementing push and pop, say. But
since Stack is really a union, we need to define push and pop on each of
these inner types that make up Stack. Let's do it and see what we get.

class StackEmpty(Empty):
[...]
def pop(self):
raise ValueError("cannot pop from an empty stack")
def push(self, x):
return Stack(x, self)

class StackPair(Pair):
def pop(self):
return self.first
def push(self, x):
return Stack(x, self)

The job is done.

>>> Stack().push("it")
Stack('it', Stack())

>>> Stack(1, Stack()).push(2).push(3)
Stack(3, Stack(2, Stack(1, Stack())))

We may observe that we had to write the same exact procedure /push/ in
both types. Sounds funny to say that it seems that we are too modular
here. I'm pretty sure you'll find a way to grab the procedure of one
class and apply it on the other, so I really think there's a way out of
not wasting keyboard-typing work and keeping things with a ``single
point of control''.

(*) Complete code

class Stack:
class StackEmpty(Empty):
def __str__(self):
return "Stack()"
def __repr__(self):
return str(self)
def pop(self):
raise ValueError("cannot pop from an empty stack")
def push(self, x):
return Stack(x, self)
class StackPair(Pair):
def __str__(self):
return "Stack({!r}, {})".format(self.first, str(self.rest))
def __repr__(self):
return str(self)
def pop(self):
return self.first
def push(self, x):
return Stack(x, self)
def __new__(clss, *args):
if len(args) == 0:
return Stack.StackEmpty()
else:
return Stack.StackPair(*args)

Il 30/10/22 15:54, Julieta Shem ha scritto:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> Julieta Shem <jshem@yaxenu.org> writes:
>>> My desire seems to imply that I need a union-like data structure.
>>
>> You only need to worry about such things in languages with
>> static typing. For example, to have a function that can
>> sometimes return an int value and at other times a string
>> value in C, one would need a union.
>>
>> In Python with its dynamic typing, one does not need unions.
>>
>> def an_int_sometimes_and_sometimes_a_string( x ):
>> if x:
>> return 2
>> else:
>> return "two"
>
> Nice. This means that I can solve my stack-union problem by writing a
> procedure --- say stack(...) --- that sometimes gives me Empty() and
> sometimes gives me Stack().
>
I think that Stefan Ram's suggestion provides a solution to the problem
of the stack, but not in a real OOP flavor.

You may find useful to learn about the possibilities of using Python
tools to implement a stack data structure and its manipulation methods.
A good introduction is at
https://realpython.com/how-to-implement-python-stack/

Giorgio

Giorgio Pastore <pastgio@units.it> writes:
>You may find useful to learn about the possibilities of using Python
>tools to implement a stack data structure and its manipulation methods.
>A good introduction is at
>https://realpython.com/how-to-implement-python-stack/

I can't see how lists are not stacks.

|>>> s=[]
|>>> s.append(1)
|>>> s.append(2)
|>>> s.pop()
|2
|>>> s.pop()
|1
|>>> s.pop()
|Traceback (most recent call last):
| File "<stdin>", line 1, in <module>
|IndexError: pop from empty list

So, for practical purposes, there is no need to implement a
stack class as far as I can understand it.

Maybe the OP wanted to implement a stack in a special way,
so that this stack is immutable and its implementation is
based on something like dotted pairs.

On Mon, 31 Oct 2022 at 09:05, Julieta Shem <jshem@yaxenu.org> wrote:
>
> Julieta Shem <jshem@yaxenu.org> writes:
>
> [...]
>
> >> . If you should, however, be talking about the new "type hints":
> >> These are static and have "Union", for example, "Union[int, str]"
> >> or "int | str".
> >
> > I ended up locating such features of the language in the documentation,
> > but I actually am not interested in declaring the type to the compiler
> > (or to the reader).
> >
> > I was looking for a solution like yours --- thank you! ---, although I
> > was hoping for handling that situation in the construction of the Stack
> > object, which was probably why I did not find a way out. Right now I'm
> > looking into __new__() to see if it can somehow produce one type or
> > another type of object depending on how the user has invoked the class
> > object.
> >
> > Terminology. By ``invoking the class object'' I mean expressions such
> > as Class1() or Class2(). ``Class1'' represents the object that
> > represents the class 1. Since the syntax is that of procedure
> > invokation, I say ``invoking the class object''.
>
> An experiment. What's my definition of Stack? It's either Empty or
> Pair, so it's a union. So let us create two inner classes (that is,
> inner to Stack) and make them behave just like Empty and Pair. Using
> __new__(), we can produce a Stack object that is sometimes Empty() and
> sometimes Pair(...).
>

The most straight-forward way to represent this concept in an
object-oriented way is subclassing.

class Stack:
... # put whatever code is common here

class Empty(Stack):
... # put Empty-specific code here, possibly overriding Stack methods

class Pair(Stack):
... # ditto, overriding or augmenting as needed

This way, everything is an instance of Stack, but they are still
distinct types for when you need to distinguish.

ChrisA

I don’t understand your implementation enough to comment specifically. What’s the definition of Pair? (i.e. what methods and public attributes does it have?) (I manage to escape Lisp as an undergrad)

To answer your question generally, Union’s are not OO. If you want Pair and Stack to have the same interface create an abstract base class and derive both of them from it.

https://docs.python.org/3/library/abc.html

From: Python-list <python-list-bounces+gweatherby=uchc.edu@python.org> on behalf of Julieta Shem <jshem@yaxenu.org>
Date: Sunday, October 30, 2022 at 5:51 PM
To: python-list@python.org <python-list@python.org>
Subject: an oop question
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

I have a question about a particular case I'm working on. I'm studying
OOP. To ask the question, I'm going to have to introduce you my context
here, so you'll need to bear with me. If you'd like to see the question
right away, go to the section ``My difficulty in encapsulating a
union''.

(*) Introduction

I wrote the classes

class Empty:
...
class Pair:
...

With them, I can (sort of) make a union of them and build a Lisp-like
list by defining that my Lisp-like list is either Empty or a Pair. For
instance, here's a Lisp-like sequence that represents the string "abc".

>>> Pair.fromIterable("abc")
Pair('a', Pair('b', Pair('c', Empty())))

So far so good. (``Full'' code at the end of this message, if you'd
like to more carefully look into my reasoning there.)

(*) How to build a stack?

These Lisp-like sequences are clearly a stack. You pop an element from
it by grabbing the first element. You push an element on to it by just
pairing the new element with the current stack. For instance, let's pop
the 1-string "a" off of the stack.

>>> ls = Pair.fromIterable("abc")
>>> ls.first
'a'
>>> ls = ls.rest
>>> ls
Pair('b', Pair('c', Empty()))

Done. Let's push it back on.

>>> ls = Pair("a", ls)
>>> ls
Pair('a', Pair('b', Pair('c', Empty())))

So far so good, but when it comes to building a better user interface
for it I have no idea how to do it. I think one of the purposes of OOP
is to organize code hierarchically so that we can reuse what we wrote.
So I tried to make a Stack by inheriting Pair.

class Stack(Pair):
pass

>>> Stack(1, Empty())
Stack(1, Empty())

Then I wrote pop and push.

>>> Stack(1, Empty()).pop()
1

>>> Stack(1, Empty()).push(2)
Stack(2, Stack(1, Empty()))

So far so good. Now let me show you what I can't do.

(*) The difficulty of encapsulating a union

The Lisp-like sequences we're building here are union-like data
structures. A /sequence/ is either Empty() or Pair(..., /sequence/). I
have not found a way to represent this either-or datastructure with a
class. For example, there is no way right now to build an empty Stack
by invoking the Stack constructor.

>>> Stack()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: Pair.__init__() missing 2 required positional arguments: 'first' and 'rest'

As I designed, an empty Stack is represented by Empty(), which is a
whole other object. Users will have to know this. I wish I did not
have to burden my users with such knowledge. For instance, I wish the
answer was "Stack()" to the question of -- ``how can I build an empty
stack?''

My desire seems to imply that I need a union-like data structure. If
Stack is invoked with no arguments, it should produce Empty(), otherwise
it produces Pair() as it does today.

How can I achieve that?

(*) Code

class Pair:
def __init__(self, first, rest):
if not isinstance(rest, Pair) and not isinstance(rest, Empty):
raise ValueError("rest must be Empty or Pair")
self.first = first
self.rest = rest
def fromIterable(it):
if len(it) == 0:
return Empty()
else:
return Pair(it[0], Pair.fromIterable(it[1:]))
def __str__(self):
return "{}({!r}, {})".format(self.__class__.__name__, self.first, str(self.rest))
def __repr__(self):
return str(self)
def __len__(self):
return 1 + self.rest.__len__()

class Empty:
def __len__(self):
return 0
def __str__(self):
return "Empty()"
def __repr__(self):
return self.__str__()
def __new__(clss):
if not hasattr(clss, "saved"):
clss.saved = super().__new__(clss)
return clss.saved

class Stack(Pair):
def pop(self):
return self.first
def push(self, x):
return Stack(x, self)
--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!iK-T12707FwUmb1Qqxlxawj0i9z1tR9aCPWPoHzh5veCzlaFBY9pKfFZwGqg3sDjUqLPC2IZgGw4QI3sRg$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!iK-T12707FwUmb1Qqxlxawj0i9z1tR9aCPWPoHzh5veCzlaFBY9pKfFZwGqg3sDjUqLPC2IZgGw4QI3sRg$>

Chris Angelico <rosuav@gmail.com> writes:

> On Mon, 31 Oct 2022 at 09:05, Julieta Shem <jshem@yaxenu.org> wrote:
>>
>> Julieta Shem <jshem@yaxenu.org> writes:
>>
>> [...]
>>
>> >> . If you should, however, be talking about the new "type hints":
>> >> These are static and have "Union", for example, "Union[int, str]"
>> >> or "int | str".
>> >
>> > I ended up locating such features of the language in the documentation,
>> > but I actually am not interested in declaring the type to the compiler
>> > (or to the reader).
>> >
>> > I was looking for a solution like yours --- thank you! ---, although I
>> > was hoping for handling that situation in the construction of the Stack
>> > object, which was probably why I did not find a way out. Right now I'm
>> > looking into __new__() to see if it can somehow produce one type or
>> > another type of object depending on how the user has invoked the class
>> > object.
>> >
>> > Terminology. By ``invoking the class object'' I mean expressions such
>> > as Class1() or Class2(). ``Class1'' represents the object that
>> > represents the class 1. Since the syntax is that of procedure
>> > invokation, I say ``invoking the class object''.
>>
>> An experiment. What's my definition of Stack? It's either Empty or
>> Pair, so it's a union. So let us create two inner classes (that is,
>> inner to Stack) and make them behave just like Empty and Pair. Using
>> __new__(), we can produce a Stack object that is sometimes Empty() and
>> sometimes Pair(...).
>>
>
> The most straight-forward way to represent this concept in an
> object-oriented way is subclassing.
>
> class Stack:
> ... # put whatever code is common here
>
> class Empty(Stack):
> ... # put Empty-specific code here, possibly overriding Stack methods
>
> class Pair(Stack):
> ... # ditto, overriding or augmenting as needed
>
> This way, everything is an instance of Stack, but they are still
> distinct types for when you need to distinguish.

Can you provide a small example? I can't see what you mean, but it
seems interesting.

On 31/10/2022 09.22, Stefan Ram wrote:
> Giorgio Pastore <pastgio@units.it> writes:
>> You may find useful to learn about the possibilities of using Python
>> tools to implement a stack data structure and its manipulation methods.
>> A good introduction is at
>> https://realpython.com/how-to-implement-python-stack/
>
> I can't see how lists are not stacks.

Agreed - in terms of functionality(!)

> |>>> s=[]
> |>>> s.append(1)
> |>>> s.append(2)
> |>>> s.pop()
> |2
> |>>> s.pop()
> |1
> |>>> s.pop()
> |Traceback (most recent call last):
> | File "<stdin>", line 1, in <module>
> |IndexError: pop from empty list
>
> So, for practical purposes, there is no need to implement a
> stack class as far as I can understand it.
>
> Maybe the OP wanted to implement a stack in a special way,
> so that this stack is immutable and its implementation is
> based on something like dotted pairs.

Code is for humans to read too. Accordingly, instead of "s", preference
for "stack" - per OP terminology.

The OP has coded pop() and push() methods, which are familiar/taught as
'the' stack operations in every 'intro to algorithms' (or intermediate
'data-structures') class.

Sadly, whereas there is list.pop(), the equivalent "push" method is
append(). Thus, a (small) dissonance in one's mind.

Writing a Stack class is unnecessary - at least given list, it is.
However, having called the structure "stack" to be descriptive and
helpful, it seems logical to continue by referring to the methods as
"push" and "pop".
(which is why many of us have such 'utilities'/snippets sitting-ready in
a personal library)

The OP has already coded such, so no cost to keep.

(returning to the OP)
Like @Gerard, am confused. There are two types: Pair and Empty.
Thereafter the need is to keep them on a stack. The stack is a
collection, an aggregate of 'whatever'. Why inherit from/to Stack?
(is this a 'Lisp thing'?)

--
Regards,
=dn

On Mon, 31 Oct 2022 at 14:38, Julieta Shem <jshem@yaxenu.org> wrote:
>
> Chris Angelico <rosuav@gmail.com> writes:
>
> > The most straight-forward way to represent this concept in an
> > object-oriented way is subclassing.
> >
> > class Stack:
> > ... # put whatever code is common here
> >
> > class Empty(Stack):
> > ... # put Empty-specific code here, possibly overriding Stack methods
> >
> > class Pair(Stack):
> > ... # ditto, overriding or augmenting as needed
> >
> > This way, everything is an instance of Stack, but they are still
> > distinct types for when you need to distinguish.
>
> Can you provide a small example? I can't see what you mean, but it
> seems interesting.

Sure. The easiest way would be to take your existing Empty and Pair
classes, have them subclass Stack, and don't bother putting any code
at all into Stack. Then construct an Empty and a few Pairs, and what
you'll see is that all of them are also instances of Stack.

After that, it's really a question of what you expect to be able to do
with either an Empty or a Pair. Anything that should be possible with
both types (that is, anything that should be possible with either
variant of Stack) should get moved into the Stack type, while anything
that is specific to one or the other stays in its own class. So here's
a very very simple example:

class Stack:
def prepend(self, other):
return Pair(other, self)

class Empty(Stack):
def is_last(self):
return True
def get_current(self):
raise ValueError("Stack empty")
def get_next(self):
raise ValueError("Stack empty")

class Pair(Stack):
def __init__(self, item1, item2):
self.item1 = item1
self.item2 = item2
def get_current(self):
return self.item1
def get_next(self):
return self.item2
def is_last(self):
return isinstance(self.item2, Empty)

With this setup, you can build a stack by prepending items onto an
Empty endpoint, and can iterate over it with the get_current and
get_next methods. (Making this actually iterable, so that it works
with a Python 'for' loop, would be a good exercise.)

In this example, there isn't much code in the Stack class. But you
could easily add more, and it would apply to both Empty and Pair.

ChrisA

On 30/10/2022 14:01, Julieta Shem wrote:

> I wrote the classes
>
> class Empty:
> ...
> class Pair:
> ...
>
> (*) How to build a stack?
>
> These Lisp-like sequences are clearly a stack.

That is a very important observation. A Pair IS-A Stack(sort of).
If you had a stack you could create a Pair from it certainly.

> So far so good, but when it comes to building a better user interface
> for it I have no idea how to do it. I think one of the purposes of OOP
> is to organize code hierarchically so that we can reuse what we wrote.

One of the purposes of classes certainly. I'm not so sure it's a purpose
of OOP. They are not the same thing. A class is a programming construct
OOP is a programming style. Classes facilitate OOP but can be used
outside of OOP too.

> So I tried to make a Stack by inheriting Pair.

But you said above that a Pair was a Stack. Inheritance implies an
IS-A relationship, so Stack inheriting Pair would mean that a Stack
was a Pair. That is not really true.

A Stack could use a Pair (or many of them) but it is not a Pair.

Trying to use inheritance inappropriately is one of the
biggest (and commonest) mistakes in OOP. It invariably leads
to complications. If in doubt use delegation instead.

> class Stack(Pair):
> pass
>
>>>> Stack(1, Empty())
> Stack(1, Empty())
>
> Then I wrote pop and push.
>
>>>> Stack(1, Empty()).pop()
> 1
>
>>>> Stack(1, Empty()).push(2)
> Stack(2, Stack(1, Empty()))
>
> So far so good. Now let me show you what I can't do.
>
> (*) The difficulty of encapsulating a union
>
> The Lisp-like sequences we're building here are union-like data
> structures. A /sequence/ is either Empty() or Pair(..., /sequence/). I
> have not found a way to represent this either-or datastructure with a
> class. For example, there is no way right now to build an empty Stack
> by invoking the Stack constructor.
>
>>>> Stack()
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> TypeError: Pair.__init__() missing 2 required positional arguments: 'first' and 'rest'
>

The usual Python approach to such things is to put some default
values(often None but could be an Empty instance in your case)
in the init() method parameter list. Then test if the inputs
are None and if so take the appropriate action.

> class Pair:
> def __init__(self, first=Empty(), rest=Empty()):

Like this.

> if not isinstance(rest, Pair) and not isinstance(rest, Empty):
> raise ValueError("rest must be Empty or Pair")
> self.first = first
> self.rest = rest
> def fromIterable(it):
> if len(it) == 0:
> return Empty()
> else:
> return Pair(it[0], Pair.fromIterable(it[1:]))
> def __str__(self):
> return "{}({!r}, {})".format(self.__class__.__name__, self.first, str(self.rest))
> def __repr__(self):
> return str(self)
> def __len__(self):
> return 1 + self.rest.__len__()
>
> class Empty:
> def __len__(self):
> return 0
> def __str__(self):
> return "Empty()"
> def __repr__(self):
> return self.__str__()
> def __new__(clss):
> if not hasattr(clss, "saved"):
> clss.saved = super().__new__(clss)
> return clss.saved
>
> class Stack(Pair):
> def pop(self):
> return self.first
> def push(self, x):
> return Stack(x, self)

--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos

"Weatherby,Gerard" <gweatherby@uchc.edu> writes:
>To answer your question generally, Union’s are not OO.

What's more non-OO to me here is immutability.

The functions/methods of the OP do not actually
change a stack but they return a new stack. This
style is being used in purely functional programming.

Object-oriented programming, however, uses objects
that have a state which may change in time. The whole
definition of a stack talks about how it is being
/modified/ by push and pop operations. So, I think that
object-oriented programming embraces change. At least
one can say that OOP by itself does not encourage
immutability even though sometimes one wants to have
immutability for some other reasons (for example,
immutability may help in parallel programming).

"Weatherby,Gerard" <gweatherby@uchc.edu> writes:
>I don’t understand your implementation enough to comment specifically. Wh=
>at’s the definition of Pair? (i.e. what methods and public attributes doe=
>s it have?) (I manage to escape Lisp as an undergrad)

When I learned LISP, it was still spelled "LISP". Below,
I am using the traditional LISP terms as I learned them,
while modern dialects may use different terms and names.

The peculiar usage of spaces is my own style and not
necessarily used by other LISP programmers.

A pair in LISP is the same as a pair in math or in English!

The low-level basic kind of a pair in LISP is called a
"dotted pair", because it is written as "( A . B )"
(to tell it from the list "( A B )", which is written
without a dot and is not the same as the dotted pair
"( A . B )").

A dotted pair is created with CONS, and one could take as
a definition the interrelation between CONS, CAD, and CDR,
which is:

( CAR( CONS A B )) is x, where x is the result of the evaluation of A
( CDR( CONS A B )) is y, where y is the result of the evaluation of B

. LISP uses a modified Cambridge notation by which the
application of the function f to the arguments x, y, z is
written as "( f x y z )" and not as "f( x, y, z )".

The evaluation of "( CONS A B )" yields the dotted pair
( x . y ), where
x is the result of the evaluation of A and
y is the the result of the evaluation of B.

Dotted pairs are used to build lists. For example, the
list (B A) is represented by

( B . ( A . NULL ))

where NULL is a special value used to mark the end of
a list. NULL can also be written as "()".

|
V
..---.---. .---.---.
| B | o----->| A | o---->|
'---'---' '---'---'

So,

( C . ( B A ))

is the list

( C B A )

|
V
..---.---. .---.---. .---.---.
| C | o----->| B | o----->| A | o---->|
'---'---' '---'---' '---'---'

. The terminating NULL is not shown in the list notation,
just as the terminating \0 is not shown for a C string.
But in dotted pair notation the last list is

( C .( B .( A . NULL )))

.

Application programmers in LISP usually would not think much
about the "lower tier" of dotted pairs that is used to implement
lists. So a pair of values in LISP usually would be implemented
by an application programmer as the list "( A B )", which internally
would be stored by the nesting of dotted pairs which is

"( A .( B . NULL ))"

|
V
..---.---. .---.---.
| B | o----->| A | o---->|
'---'---' '---'---'

.

Chris Angelico <rosuav@gmail.com> writes:

> On Mon, 31 Oct 2022 at 14:38, Julieta Shem <jshem@yaxenu.org> wrote:
>>
>> Chris Angelico <rosuav@gmail.com> writes:
>>
>> > The most straight-forward way to represent this concept in an
>> > object-oriented way is subclassing.
>> >
>> > class Stack:
>> > ... # put whatever code is common here
>> >
>> > class Empty(Stack):
>> > ... # put Empty-specific code here, possibly overriding Stack methods
>> >
>> > class Pair(Stack):
>> > ... # ditto, overriding or augmenting as needed
>> >
>> > This way, everything is an instance of Stack, but they are still
>> > distinct types for when you need to distinguish.
>>
>> Can you provide a small example? I can't see what you mean, but it
>> seems interesting.
>
> Sure. The easiest way would be to take your existing Empty and Pair
> classes, have them subclass Stack, and don't bother putting any code
> at all into Stack. Then construct an Empty and a few Pairs, and what
> you'll see is that all of them are also instances of Stack.
>
> After that, it's really a question of what you expect to be able to do
> with either an Empty or a Pair. Anything that should be possible with
> both types (that is, anything that should be possible with either
> variant of Stack) should get moved into the Stack type, while anything
> that is specific to one or the other stays in its own class. So here's
> a very very simple example:
>
> class Stack:
> def prepend(self, other):
> return Pair(other, self)
>
> class Empty(Stack):
> def is_last(self):
> return True
> def get_current(self):
> raise ValueError("Stack empty")
> def get_next(self):
> raise ValueError("Stack empty")
>
> class Pair(Stack):
> def __init__(self, item1, item2):
> self.item1 = item1
> self.item2 = item2
> def get_current(self):
> return self.item1
> def get_next(self):
> return self.item2
> def is_last(self):
> return isinstance(self.item2, Empty)
>
> With this setup, you can build a stack by prepending items onto an
> Empty endpoint, and can iterate over it with the get_current and
> get_next methods. (Making this actually iterable, so that it works
> with a Python 'for' loop, would be a good exercise.)
>
> In this example, there isn't much code in the Stack class. But you
> could easily add more, and it would apply to both Empty and Pair.

Thank you so much for the example. It's very interesting as it sort of
reverses my intuition. It seems non-obvious. I had in mind to build a
Stack out of Empty and Pair, but you seem to have done it the other way
around.

But I still don't see a way of using your classes up there in which I
have a single name to build empty and non-empty stacks. Let me
clarify. If I wish for an empty stack, I wish I could just say

>>> Stack()
Stack()

and if I wish for a nonempty stack, I'd write

>>> Stack(1, Stack(2, Stack(3, Stack())))
Stack(1, Stack(2, Stack(3, Stack())))

With your classes, I think I must write

>>> Empty() # That's an empty stack
....

>>> Pair(1, Pair(2, Empty())) # That's a non-empty stack
....

In other words, I need to memorize two different names for using stacks.
I'm trying to have a single name for both parts of the union (that is my
design of a stack).

Thanks so much!

Alan Gauld <learn2program@gmail.com> writes:

> On 30/10/2022 14:01, Julieta Shem wrote:
>
>> I wrote the classes
>>
>> class Empty:
>> ...
>> class Pair:
>> ...
>>
>> (*) How to build a stack?
>>
>> These Lisp-like sequences are clearly a stack.
>
> That is a very important observation. A Pair IS-A Stack(sort of).
> If you had a stack you could create a Pair from it certainly.

Yes, they are the same thing --- in my mind ---, except possibly for the
user interface, names and stuff. I do prefer to make the user think he
has something else simply because it has a different name. It is not
the user's business to know what things are on the inside.

>> So far so good, but when it comes to building a better user interface
>> for it I have no idea how to do it. I think one of the purposes of OOP
>> is to organize code hierarchically so that we can reuse what we wrote.
>
> One of the purposes of classes certainly. I'm not so sure it's a purpose
> of OOP. They are not the same thing. A class is a programming construct
> OOP is a programming style. Classes facilitate OOP but can be used
> outside of OOP too.

That's an interesting observation. I like that. Classes are one thing
and OOP is another. Of course, at the extreme I think I will get
nowhere in trying to detect in high-precision what is OOP and what is
not. The same for classes. I always liked to think of C structures as
some class. Instead of saying ``new Whatever()'', I'd say
``malloc(sizeof ...)''. I'd then have many procedures whose first
argument were a pointer to Whatever. They're the methods. So the
structure Whatever si the class itself. Is this use of C outside of
OOP? I say it is not because my notion of OOP is that --- a way to make
objects and have methods operate on them, changing them or not.

Should I allow the non-change of objects to be OOP as well? I think so.
To me what distinguishes functional from imperative is, for example,
imperative has side-effects. We can take an imperative set of tools and
do not produce any side-effects (locally speaking, of course) and that
would be indisguishable from functional programming. We can say that
imperative languages are more general than functional ones. (That's my
non-educated guess for the moment anyhow.)

>> So I tried to make a Stack by inheriting Pair.
>
> But you said above that a Pair was a Stack. Inheritance implies an
> IS-A relationship, so Stack inheriting Pair would mean that a Stack
> was a Pair. That is not really true.

That's another interesting observation. I do not have much
understanding of how to really think of these things and that's most
likely why I never tried to understand OOP or imperative programming.
It seems very difficult.

What I meant is that a Pair was a Stack and a Stack was a Pair. The
reason I was creating a Stack at all was just to make the user think
it's something different --- and with more obvious names for the case
under analysis, which was the use of a stack-like data structure.

> A Stack could use a Pair (or many of them) but it is not a Pair.

Is this how I should design it? I tried that, actually. It seemed to
complicate my life because I had to provide to my Stack class various
other methods my Pair class already had.

> Trying to use inheritance inappropriately is one of the
> biggest (and commonest) mistakes in OOP. It invariably leads
> to complications. If in doubt use delegation instead.

What is delegation?

I think that's why I never went into OOP and imperative languages. It
just seems bloody difficult to get anything right. Call me stupid or
what you will, but it seems very difficult.

Any book recomendations on getting this thing mathematics-clear?

Thank you!

Julieta Shem <jshem@yaxenu.org> writes:
>clarify. If I wish for an empty stack, I wish I could just say
>>>> Stack()
>Stack()
>and if I wish for a nonempty stack, I'd write
>>>> Stack(1, Stack(2, Stack(3, Stack())))
>Stack(1, Stack(2, Stack(3, Stack())))

If this is all,

main.py

class Stack:
def __init__( self, *args ):
self.data = [ args[ 0 ], args[ 1 ]]if len( args ) else []
def __str__( self ):
if len( self.data ):
return f"Stack({self.data[0]}, {self.data[1]})"
else:
return f"Stack()"

print( Stack() )

print( Stack(1, Stack(2, Stack(3, Stack()))) )

output

Stack()
Stack(1, Stack(2, Stack(3, Stack())))

.

Julieta Shem <jshem@yaxenu.org> writes:
>Any book recomendations on getting this thing mathematics-clear?

OOP cannot be mathematics-clear because it is an /attempt/ to
abstract from several different programming languages.

When you ask Alan Kay (and I did!), the man who coined the term
"object-oriented", he will tell you (in my words):
"Object-oriented programming is possible in Smalltalk only.".

So, to get OOP crystal clear from the one who coined the
term, go ahead an learn Smalltalk!

But while Kay coined the term, many ideas of OOP are based
on Simula. So, you might think about learning Simula to get
the Dahl-flavor of OOP.

This is comp.lang.python. Here we do Python programming.

10 or 20 years ago there were still famous people, such as
Robert C. Martin, hanging around in "comp.object", and I would
have told you to go there, but today that newsgroup is deserted.

Here's an excerpt from an older post by me, written in May this year:

In 2003, I became aware of the fact that Alan Kay, the man
who coined the term "object-oriented programming" in 1967
(or in the temporal proximity of this year), never has given
a definition for it. I asked him via e-mail, and he kindly
responded. In that e-mail he also wrote something to the effect
that for him only Smalltalk allows object-oriented programming.
(On another occasion, he also said, "I invented the term Object-
Oriented and I can tell you I did not have C++ in mind.".) So,
I think that this point of view by Alan Kay is similar to what
Liam wrote about Smalltalk!

So, what did Alan Kay write to me in 2003? Here's the crucial excerpt:

|OOP to me means only messaging, local retention and protection and
|hiding of state-process, and extreme late-binding of all things. It
|can be done in Smalltalk and in LISP. There are possibly other
|systems in which this is possible, but I'm not aware of them.
Alan Kay, 2003

. I should add that the deepest insight I gained into what is the
actual point of OOP (as I wrote in my previous post in this thread)
I got from the writings of Robert C. Martin who clarified that
OOP makes it easy to add new types but hard to add new operations,
while procedural programming makes it easy to add new operations,
but hard to add new types.

|Procedural code (code using data structures) makes it easy to
|add new functions without changing the existing data
|structures. OO code, on the other hand, makes it easy to add
|new classes without changing existing functions.
Robert Cecil Martin

|Procedural code makes it hard to add new data structures
|because all the functions must change. OO code makes it hard
|to add new functions because all the classes must change.
Robert Cecil Martin

When one first reads this, it might not be obvious why this
is so spot on, but one can find this quotation in the book
"Clean Code" by Robert C. Martin and read more explanations
about it there.

Objects with data abstraction can already be found in CLU by
Barbara Liskov. But this is not yet OOP. The crucial feature
OOP adds to this is polymorphism ("late binding").

ram@zedat.fu-berlin.de (Stefan Ram) writes:
>The crucial feature OOP adds to this is polymorphism ("late binding").

If polymorphism is so crucial, the idea of subclasses
has something to it! So here's another way to code your
requirements, using subclasses:

main.py

class Stack:
def __new__( self, *args ):
return nonempty_stack( *args )if len( args ) else empty_stack()
def __str__( self ):
return str( self.data )

class nonempty_stack( Stack ):
def __new__( self, *args ):
return object().__new__( self )
def __init__( self, *args ):
self.data =[ args[ 0 ], args[ 1 ]]
def __str__( self ):
return f"Stack({self.data[0]}, {self.data[1]})"

class empty_stack( Stack ):
def __new__( self, *args ):
return object().__new__( self )
def __init__( self, *args ):
self.data = []
def __str__( self ):
return f"Stack()"

print( Stack() )
print( Stack(1, Stack(2, Stack(3, Stack()))) )

print()
print( type( Stack() ))
print( type( Stack(1, Stack(2, Stack(3, Stack()))) ))

output

Stack()
Stack(1, Stack(2, Stack(3, Stack())))

<class '__main__.empty_stack'>
<class '__main__.nonempty_stack'>

I think:

class Stack:
def __init__( self, *args ):
self.data = args

def __str__( self ):
return f"Stack({','.join(str(x) for x in self.data)})"

gives equivalent output for the if len(args) is 0 or 2, if it’s okay for self.data to be a tuple.

class Stack:
def __init__( self, *args ):
self.data = list(args)

def __str__( self ):
return f"Stack({','.join(str(x) for x in self.data)})"

If it’s desired self.data be a list.

From: Python-list <python-list-bounces+gweatherby=uchc.edu@python.org> on behalf of Stefan Ram <ram@zedat.fu-berlin.de>
Date: Tuesday, November 1, 2022 at 3:43 PM
To: python-list@python.org <python-list@python.org>
Subject: Re: an oop question
*** Attention: This is an external email. Use caution responding, opening attachments or clicking on links. ***

Julieta Shem <jshem@yaxenu.org> writes:
>clarify. If I wish for an empty stack, I wish I could just say
>>>> Stack()
>Stack()
>and if I wish for a nonempty stack, I'd write
>>>> Stack(1, Stack(2, Stack(3, Stack())))
>Stack(1, Stack(2, Stack(3, Stack())))

If this is all,

main.py

class Stack:
def __init__( self, *args ):
self.data = [ args[ 0 ], args[ 1 ]]if len( args ) else []
def __str__( self ):
if len( self.data ):
return f"Stack({self.data[0]}, {self.data[1]})"
else:
return f"Stack()"

print( Stack() )

print( Stack(1, Stack(2, Stack(3, Stack()))) )

output

Stack()
Stack(1, Stack(2, Stack(3, Stack())))

.

--
https://urldefense.com/v3/__https://mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!itEYnwU5jJ0z8_rkW_q_ogw3ZJUNdHdMNkMLpSAqBdozBNrr7NqPs_gNsbx8W9uXRLZpG38C9an17Yx2zUf-mSA$<https://urldefense.com/v3/__https:/mail.python.org/mailman/listinfo/python-list__;!!Cn_UX_p3!itEYnwU5jJ0z8_rkW_q_ogw3ZJUNdHdMNkMLpSAqBdozBNrr7NqPs_gNsbx8W9uXRLZpG38C9an17Yx2zUf-mSA$>

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Julieta Shem <jshem@yaxenu.org> writes:
>>clarify. If I wish for an empty stack, I wish I could just say
>>>>> Stack()
>>Stack()
>>and if I wish for a nonempty stack, I'd write
>>>>> Stack(1, Stack(2, Stack(3, Stack())))
>>Stack(1, Stack(2, Stack(3, Stack())))
>
> If this is all,
>
> main.py
>
> class Stack:
> def __init__( self, *args ):
> self.data = [ args[ 0 ], args[ 1 ]]if len( args ) else []
> def __str__( self ):
> if len( self.data ):
> return f"Stack({self.data[0]}, {self.data[1]})"
> else:
> return f"Stack()"
>
> print( Stack() )
>
> print( Stack(1, Stack(2, Stack(3, Stack()))) )
>
> output
>
> Stack()
> Stack(1, Stack(2, Stack(3, Stack())))

Thanks! But we've left behind a more basic requirement --- the Stack
class wishes for all the methods already written in some class called
Pair, which has a certain connection with a class Empty. This
requirement has been implicit in the first message in this thread,
though. I didn't make it explicit. (In other words, this part of the
thread only makes sense by taking into account all the previous messages
up in the thread.)

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>The crucial feature OOP adds to this is polymorphism ("late binding").
>
> If polymorphism is so crucial, the idea of subclasses
> has something to it! [...]

I wonder what Rich Hickey would say here. Didn't he design Clojure with
``multimethods'' so that we can get some kind of polymorphism without
subclassing?

On 2/11/22 9:54 am, Julieta Shem wrote:
> But we've left behind a more basic requirement --- the Stack
> class wishes for all the methods already written in some class called
> Pair,

Is that *really* what you want, though?

To my way of thinking, a Stack and a Pair are quite different
data structures, each having their own characteristic operations.

Things I want to be able to do with a Stack:
- Create an empty stack
- Push an item onto the top of the stack
- Pop an item off the top of the stack

Things I want to be able to do with a Pair:
- Create a pair containing two given objects
- Get the first item
- Get the second item

I don't see any overlap between these at the conceptual level.
Possibly I might want to use Pairs as part of the *implementation*
of a stack, but that doesn't mean that any Pair methods should
appear as Stack methods.

Here's how I might do this in a functional style using Python:

class Pair:
def __init__(self, first, second):
self._first = first
self._second = second
def first(self):
return self._first
def second(self):
return self._second

class Stack:
def __init__(self):
self._data = None
def push(self, item):
result = Stack()
result._data = Pair(item, self._data)
return result
def pop(self):
rest = Stack()
rest._data = self._data.second()
return self._data.first(), rest

Note that neither Stack nor Pair inherits from the other.

--
Greg

Julieta Shem <jshem@yaxenu.org> writes:
>Thanks! But we've left behind a more basic requirement --- the Stack
>class wishes for all the methods already written in some class called
>Pair, which has a certain connection with a class Empty. This
>requirement has been implicit in the first message in this thread,
>though. I didn't make it explicit. (In other words, this part of the
>thread only makes sense by taking into account all the previous messages
>up in the thread.)

Sorry! So, I combine the "Stack" class from my other post with
your two classes "Pair" and "Empty":

main.py

class Stack:
def __new__( self, *args ):
return Pair( args[ 0 ], args[ 1 ])if args else Empty()

class Pair:
def __init__(self, first, rest):
if not isinstance(rest, Pair) and not isinstance(rest, Empty):
raise ValueError("rest must be Empty or Pair")
self.first = first
self.rest = rest
def fromIterable(it):
if len(it) == 0:
return Empty()
else:
return Pair(it[0], Pair.fromIterable(it[1:]))
def __str__(self):
return "{}({!r}, {})".format(self.__class__.__name__, self.first, str(self.rest))
def __repr__(self):
return str(self)
def __len__(self):
return 1 + self.rest.__len__()

class Empty:
def __len__(self):
return 0
def __str__(self):
return "Empty()"
def __repr__(self):
return self.__str__()
def __new__(clss):
if not hasattr(clss, "saved"):
clss.saved = super().__new__(clss)
return clss.saved

print( Stack() )
print( Stack(1, Stack(2, Stack(3, Stack()))) )

print()
print( type( Stack() ))
print( type( Stack(1, Stack(2, Stack(3, Stack()))) ))

output:

Empty()
Pair(1, Pair(2, Pair(3, Empty())))

<class '__main__.Empty'>
<class '__main__.Pair'>

You also could have inherit them from "Stack",
but then they would need a custom __new__ method
with "return object().__new__( self )".

Julieta Shem <jshem@yaxenu.org> writes:
>ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>The crucial feature OOP adds to this is polymorphism ("late binding").
>>If polymorphism is so crucial, the idea of subclasses
>>has something to it! [...]
>I wonder what Rich Hickey would say here. Didn't he design Clojure with
>``multimethods'' so that we can get some kind of polymorphism without
>subclassing?

Yes. In general, one can have polymorphism without subclassing, but
in class-based OOP, such as in Python, inheritance is the standard
way to enable polymorphism. In other languages, such as Clojure, Self,
or the original JavaScript, one might use other means than inheritance.