[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

implementing a CL-like type calculus in Python (the language not the compiler

Jim Newton

1/23/2016 10:12:00 AM

I was discussing this week whether the Python language is sufficiently flexible to implement
a CL-like type calculus. It looks like it almost is, but since I'm not a Python expert, I can't say
whether it's impossible.

I did a few searches to see if anyone had done this already and didn't find anything.

Does someone know of an attempt, either successful or unsuccessful, or is any comp.lang.lisp
reader familiar enough with CL and Python to comment on this possibility?

I'm also happy to explain why I want to do this if anyone is interested in knowing.

Here's what I've found out so far: (sorry that my Python-speak is not correct and I mix up some terms)

There is a type in Python called "type", and I (the programmer) can create a subclass of it named combo_type,
and then proceed to make or_type, and_type, not_type and empty_type subclasses of combo_type.
The methods corresponding to the CL typep and subtypep are available can be overwritten on these classes. E.g., if A is an instance of or_type (corresponding to (or int string), one would like to ask
are int and (and A string) subclass/superclass of A.

The thing that seems to be missing is the following.

A class knows is superclasses in Python but apparently not its subclasses.
This might be related to the feature that classes can be local to lexical scopes, not really sure the motivation, that's just my guess.

In order to figure out whether the intersection of two types is empty, the algorithm needs to trace down the
type lattice from both types in question to find whether the paths intersect before arriving at the empty type.
This sounds impossible to me in Python.

I'm happy to hear anyone's thoughts.
8 Answers

Pascal J. Bourguignon

1/23/2016 12:21:00 PM

0

Jim Newton <jimka.issy@gmail.com> writes:

> I was discussing this week whether the Python language is sufficiently
> flexible to implement a CL-like type calculus.

Questions like that are almost always answered by the positive, given
Turing Equivalence.

> It looks like it almost is, but since I'm not a Python expert, I can't say
> whether it's impossible.

On the other hand, nowadays we know that it's impossible in standard
ANSI C11, since standard ANSI C11 doesn't guarantee that there won't be
a stack overflow on the first function call, it is therefore not Turing
complete. In CL we at least have CALL-ARGUMENTS-LIMIT ;-) (on the other
hand, a formalization of CL remains to be done).


Joke apart, it's always possible Turing non-completeness
non-withstanding, given that our computers have finite memories and
therefore are not Turing complete anyways. That doesn't prevent us to do
it. The question is whether you would rather do it in CL, in Python, in
brainfuck or in C. Oops, I meant in C or in brainfuck.


> I did a few searches to see if anyone had done this already and didn't
> find anything.
>
> Does someone know of an attempt, either successful or unsuccessful, or
> is any comp.lang.lisp reader familiar enough with CL and Python to
> comment on this possibility?

I fail to see the point of implementing the CL type system in
Python. Why would you want to do meta-CL programming in any language
that's not CL?

You would rather do the opposite, implement the python type system in
CL, so that you can analyse python programs with a CL tool, and use it
to translate those python programs to CL, or stuff.


> I'm also happy to explain why I want to do this if anyone is
> interested in knowing.

Well, I guess you could always try to explain why you want to write
python programs, when you have a nicer and superior language like Common
Lisp available to write them, but it will take a long time for us here
to understand, if any of us was interested at all.


> Here's what I've found out so far: (sorry that my Python-speak is not
> correct and I mix up some terms)
>
> There is a type in Python called "type", and I (the programmer) can
> create a subclass of it named combo_type, and then proceed to make
> or_type, and_type, not_type and empty_type subclasses of combo_type.
> The methods corresponding to the CL typep and subtypep are available
> can be overwritten on these classes. E.g., if A is an instance of
> or_type (corresponding to (or int string), one would like to ask are
> int and (and A string) subclass/superclass of A.
>
> The thing that seems to be missing is the following.
>
> A class knows is superclasses in Python but apparently not its
> subclasses. This might be related to the feature that classes can be
> local to lexical scopes, not really sure the motivation, that's just
> my guess.
>
> In order to figure out whether the intersection of two types is empty,
> the algorithm needs to trace down the type lattice from both types in
> question to find whether the paths intersect before arriving at the
> empty type. This sounds impossible to me in Python.
>
> I'm happy to hear anyone's thoughts.

Can't you have a list of all the classes or of all the types?

Perhaps you can reconstitute the subclasses relationship by enumerating
all the classes and using the superclass relationship?

Again, if you implemented the python type system in CL (it is already
done in CL-Python), then you could easily maintain the subclasses to
each class if that wasn't already done.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Jim Newton

1/23/2016 2:24:00 PM

0

On Saturday, January 23, 2016 at 1:21:05 PM UTC+1, informatimago wrote:
> Jim Newton <jimka.issy@gmail.com> writes:
>
> I fail to see the point of implementing the CL type system in
> Python. Why would you want to do meta-CL programming in any language
> that's not CL?
>
> You would rather do the opposite, implement the python type system in
> CL, so that you can analyse python programs with a CL tool, and use it
> to translate those python programs to CL, or stuff.
>

Yes, it is natural that you (or anyone) would not see the point, as I explicitly didn't
explain it. The motivation may be interesting but it is not necessary to understand
in order to discuss the feasibility.



>
> Can't you have a list of all the classes or of all the types?
>

I can look, but I don't think there is a way to get the list of all types. As I understand types
are not accessible by name.

Kaz Kylheku

1/23/2016 6:14:00 PM

0

On 2016-01-23, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> Jim Newton <jimka.issy@gmail.com> writes:
>
>> I was discussing this week whether the Python language is sufficiently
>> flexible to implement a CL-like type calculus.
>
> Questions like that are almost always answered by the positive, given
> Turing Equivalence.

Not necessarily if the obvious implicit conversational restriction applies.

Namely: "...CL-like type calculus, where 'type' refers to actual
Python type, and not some type notion invented for the sake of
the calculus."

Alan Bawden

1/24/2016 8:39:00 AM

0

Jim Newton <jimka.issy@gmail.com> writes:

> A class knows is superclasses in Python but apparently not its subclasses.

It looks to me like it does:

Python 3.3.3 (default, Nov 25 2013, 16:10:55)
>>> class Foo(object):
... pass
...
>>> class Bar(Foo):
... pass
...
>>> Foo.__subclasses__()
[<class '__main__.Bar'>]

Of course these subclass lists can change whenever new modules are
loaded, so I'm dubious that you can do reasonable type inferencing based
on what you find in them unless you are very careful about your
assumptions.

You should also know that Python 3 has been working towards some kind of
soft-typing scheme for quite a while. I don't know the first thing
about it, but if you want to reason about types in Python, you should
surely educate yourself about that before you go any further.

And comp.lang.lisp is surely the wrong place to be talking about this.
Try comp.lang.python.

--
Alan Bawden

Kaz Kylheku

1/24/2016 5:23:00 PM

0

On 2016-01-24, Alan Bawden <alan@csail.mit.edu> wrote:
> Jim Newton <jimka.issy@gmail.com> writes:
>
>> A class knows is superclasses in Python but apparently not its subclasses.
>
> It looks to me like it does:
>
> Python 3.3.3 (default, Nov 25 2013, 16:10:55)
> >>> class Foo(object):
> ... pass
> ...
> >>> class Bar(Foo):
> ... pass
> ...
> >>> Foo.__subclasses__()
> [<class '__main__.Bar'>]

This proves that Python has an API for obtaining the subclasses, not
that a class "knows" them. (There could be a global list of classes,
which has to be walked in order to get this information).

Mark Tarver

1/24/2016 6:13:00 PM

0

On Saturday, January 23, 2016 at 10:12:21 AM UTC, Jim Newton wrote:
> I was discussing this week whether the Python language is sufficiently flexible to implement
> a CL-like type calculus. It looks like it almost is, but since I'm not a Python expert, I can't say
> whether it's impossible.
>
> I did a few searches to see if anyone had done this already and didn't find anything.
>
> Does someone know of an attempt, either successful or unsuccessful, or is any comp.lang.lisp
> reader familiar enough with CL and Python to comment on this possibility?
>
> I'm also happy to explain why I want to do this if anyone is interested in knowing.
>
> Here's what I've found out so far: (sorry that my Python-speak is not correct and I mix up some terms)
>
> There is a type in Python called "type", and I (the programmer) can create a subclass of it named combo_type,
> and then proceed to make or_type, and_type, not_type and empty_type subclasses of combo_type.
> The methods corresponding to the CL typep and subtypep are available can be overwritten on these classes. E.g., if A is an instance of or_type (corresponding to (or int string), one would like to ask
> are int and (and A string) subclass/superclass of A.
>
> The thing that seems to be missing is the following.
>
> A class knows is superclasses in Python but apparently not its subclasses.
> This might be related to the feature that classes can be local to lexical scopes, not really sure the motivation, that's just my guess.
>
> In order to figure out whether the intersection of two types is empty, the algorithm needs to trace down the
> type lattice from both types in question to find whether the paths intersect before arriving at the empty type.
> This sounds impossible to me in Python.
>
> I'm happy to hear anyone's thoughts.

Several years ago Shen was implemented in Python independently by two programmers - a Python version by Ramil Farkshatov is available from www.shenlanguage.org. A CL version is also available there too. The Shen type system is programmable to a high degree. I've implemented a compiler from ML style algebraic datatypes definitions in 60 lines. You might look at Ramil's work.

Mark

Pascal J. Bourguignon

1/24/2016 6:15:00 PM

0

Kaz Kylheku <609-576-4089@kylheku.com> writes:

> On 2016-01-24, Alan Bawden <alan@csail.mit.edu> wrote:
>> Jim Newton <jimka.issy@gmail.com> writes:
>>
>>> A class knows is superclasses in Python but apparently not its subclasses.
>>
>> It looks to me like it does:
>>
>> Python 3.3.3 (default, Nov 25 2013, 16:10:55)
>> >>> class Foo(object):
>> ... pass
>> ...
>> >>> class Bar(Foo):
>> ... pass
>> ...
>> >>> Foo.__subclasses__()
>> [<class '__main__.Bar'>]
>
> This proves that Python has an API for obtaining the subclasses, not
> that a class "knows" them. (There could be a global list of classes,
> which has to be walked in order to get this information).

This is an irrelevant implementation detail.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Kaz Kylheku

1/24/2016 7:42:00 PM

0

On 2016-01-24, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> Kaz Kylheku <609-576-4089@kylheku.com> writes:
>
>> On 2016-01-24, Alan Bawden <alan@csail.mit.edu> wrote:
>>> Jim Newton <jimka.issy@gmail.com> writes:
>>>
>>>> A class knows is superclasses in Python but apparently not its subclasses.
>>>
>>> It looks to me like it does:
>>>
>>> Python 3.3.3 (default, Nov 25 2013, 16:10:55)
>>> >>> class Foo(object):
>>> ... pass
>>> ...
>>> >>> class Bar(Foo):
>>> ... pass
>>> ...
>>> >>> Foo.__subclasses__()
>>> [<class '__main__.Bar'>]
>>
>> This proves that Python has an API for obtaining the subclasses, not
>> that a class "knows" them. (There could be a global list of classes,
>> which has to be walked in order to get this information).
>
> This is an irrelevant implementation detail.

Yes, but that detail is what it means for an object to *know* something.
"Know" refers to the implementation. It means we can navigate from that
object directly, or at least somewhat directly to whatever it knows.

If some global structure is consulted then this is the same kind of
"know" like when someone says "I know that, hold on!" and then types
a query into Google on their mobile device. :)

Maybe I'm behind the times, clinging to an outdated definition of
"know".