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


 

Forums >

comp.lang.lisp

nil subtype of function

Jim Newton

3/16/2016 5:35:00 PM

I took a look in the classic Baker paper
http://www.pipeline.com/~hbaker1/Sub...
which claims that subtypep and typep should not work with function types.

> Common Lisp also defines two additional type specifier constructs: function and values.
> However, these constructs are expressly prohibited from calls to typep, and hence from
> calls to subtypep [CL90,p.57]. If these specifiers were not prohibited by Common Lisp from
> appearing in calls to subtypep, they would make a decision procedure for subtypep
> impossible. For example, subtypep could then have been asked about the functional >
> equivalence of two lambda-expressions, a problem which is known to be undecidable.

However, I see the following results sbcl that it does give some interesting results with
respect to the nil and t types.

CL-USER> (subtypep '(function (nil) nil) nil)
NIL
T
CL-USER> (subtypep '(function (nil) t) nil)
NIL
T
CL-USER> (subtypep '(function (t) nil) nil)
NIL
T

My first guess would be that the type (function (nil) t) is itself nil.
Am I misunderstanding something?
If there is such a function, I'm very curious to understand what it is.
21 Answers

Kaz Kylheku

3/16/2016 6:51:00 PM

0

On 2016-03-16, Jim Newton <jimka.issy@gmail.com> wrote:
> I took a look in the classic Baker paper
> http://www.pipeline.com/~hbaker1/Sub...
> which claims that subtypep and typep should not work with function types.
>
>> Common Lisp also defines two additional type specifier constructs:
>> function and values. However, these constructs are expressly
>> prohibited from calls to typep, and hence from calls to subtypep
>> [CL90,p.57]. If these specifiers were not prohibited by Common Lisp

What is "CL90, p. 57", I wonder. Draft reference? CL was ratified in
1994 and has nice section numbers so we don't have to cite physical
page numbers.

>> from appearing in calls to subtypep, they would make a decision
>> procedure for subtypep impossible. For example, subtypep could then
>> have been asked about the functional > equivalence of two
>> lambda-expressions, a problem which is known to be undecidable.

But CL subtypep can be asked problems which are undecideable,
because it returns a pair of Boolean values.

If subtypep is not able to reach a conclusion, it can return
NIL NIL: it wasn't able to confirm the subtype relationship, but
it wasn't able to rule it out, either.

> However, I see the following results sbcl that it does give some interesting results with
> respect to the nil and t types.
>
> CL-USER> (subtypep '(function (nil) nil) nil)
> NIL
> T
> CL-USER> (subtypep '(function (nil) t) nil)
> NIL
> T
> CL-USER> (subtypep '(function (t) nil) nil)
> NIL
> T

Of course, every type is a supertype of nil, including nil itself.
There can be no exception to this, so there is no reason not
to give an authoritative answer.

> If there is such a function, I'm very curious to understand what it is.

Such a function as what? That is not a supertype of nil?

Jim Newton

3/17/2016 9:42:00 AM

0


> > CL-USER> (subtypep '(function (nil) nil) nil)
> > NIL
> > T
> > CL-USER> (subtypep '(function (nil) t) nil)
> > NIL
> > T
> > CL-USER> (subtypep '(function (t) nil) nil)
> > NIL
> > T
>
> Of course, every type is a supertype of nil, including nil itself.
> There can be no exception to this, so there is no reason not
> to give an authoritative answer.
>

No, what I mean is the following: Is (function (nil) nil)
a SUBTYPE of nil? Of course nil is a subtype of (function (nil) nil), but
my question is the other way around. My gut feel is that (subtypep (function (nil) nil) nil)
should return T,T in this case. Why? Because the set of functions which
this type signature is the empty set.

> > If there is such a function, I'm very curious to understand what it is.
>
> Such a function as what? That is not a supertype of nil?

I mean, is there a function which accepts and argument coming from the empty set.
I think the answer is no. If that is the case, it seems to me that
(function (nil) nil) specifies a subtype of nil.

If this is not the case there is probably something curious and interesting about function
types that I would like to better understand.

Barry Margolin

3/17/2016 10:13:00 AM

0

In article <27c84cc6-59a6-43fd-bed9-be9d0273f069@googlegroups.com>,
Jim Newton <jimka.issy@gmail.com> wrote:

> No, what I mean is the following: Is (function (nil) nil)
> a SUBTYPE of nil? Of course nil is a subtype of (function (nil) nil), but
> my question is the other way around. My gut feel is that (subtypep
> (function (nil) nil) nil)
> should return T,T in this case. Why? Because the set of functions which
> this type signature is the empty set.

Nothing can be a subtype of NIL. So (subtypep <anything> nil) should
always return NIL, T.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Madhu

3/17/2016 12:02:00 PM

0


* Barry Margolin <barmar-2F60D1.03124017032016@88-209-239-213.giganet.hu> :
Wrote on Thu, 17 Mar 2016 03:12:40 -0700:

| In article <27c84cc6-59a6-43fd-bed9-be9d0273f069@googlegroups.com>,
| Jim Newton <jimka.issy@gmail.com> wrote:
|
|> No, what I mean is the following: Is (function (nil) nil)
|> a SUBTYPE of nil? Of course nil is a subtype of (function (nil) nil), but
|> my question is the other way around. My gut feel is that (subtypep
|> (function (nil) nil) nil)
|> should return T,T in this case. Why? Because the set of functions which
|> this type signature is the empty set.
|
| Nothing can be a subtype of NIL. So (subtypep <anything> nil) should
| always return NIL, T.

With exactly one exception: (subtype nil nil) => T,T

[from subtype glos. "(Every type is a subtype of itself.)"
the spec for type nil says:
"The type nil is a subtype of every type. No object is of type nil."

The flip side of this: (subtype nil <anything>) => T, T

This should clarify the topic in 3 other threads. From the spec for
SUBTYPEP "The second return value has to be T if the first value is T."
Exceptional situations: None. (so subtypep is not required to signal an
undefined type.)

(BTW, the call to (values) takes no arguments and returns no
arguments.)]

Jim Newton

3/17/2016 1:01:00 PM

0


> With exactly one exception: (subtype nil nil) => T,T
>
> [from subtype glos. "(Every type is a subtype of itself.)"
> the spec for type nil says:
> "The type nil is a subtype of every type. No object is of type nil."
>
> The flip side of this: (subtype nil <anything>) => T, T
>

No, I dont' think that's correct! (subtype nil any-type-specifier) => T, T
(subtype nil 3) does not and should not return T,T

> This should clarify the topic in 3 other threads. From the spec for
> SUBTYPEP "The second return value has to be T if the first value is T."
> Exceptional situations: None. (so subtypep is not required to signal an
> undefined type.)

Doesn't "Exceptional situations: None" imply that there are no exceptional situations
as long as it is given two the specifiers? Otherwise (subtypep nil 3) would be forbidden
from raising an error?

Jim Newton

3/17/2016 1:08:00 PM

0

On Thursday, March 17, 2016 at 11:12:47 AM UTC+1, Barry Margolin wrote:
> Nothing can be a subtype of NIL. So (subtypep <anything> nil) should
> always return NIL, T.
>

Every empty type is a subtype of nil. For example (subtypep '(and string number) nil)
returns T,T. So if (function (nil) nil) is an empty type (subtypep '(function (nil) nil) nil)
should return T,T. Right? That subtypep returns T,T means (function (nil) nil) is
NOT empty.

I'd like to understand which functions are of type (function (nil) nil) as subtypep claims.
They contradict my understanding of CL functions, so I'm happy to try to understand
them better.

Nicolas Neuss

3/17/2016 1:50:00 PM

0

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

> I took a look in the classic Baker paper
> http://www.pipeline.com/~hbaker1/Sub...
> which claims that subtypep and typep should not work with function types.
>
>> Common Lisp also defines two additional type specifier constructs: function and values.
>> However, these constructs are expressly prohibited from calls to typep, and hence from
>> calls to subtypep [CL90,p.57]. If these specifiers were not prohibited by Common Lisp from
>> appearing in calls to subtypep, they would make a decision procedure for subtypep
>> impossible. For example, subtypep could then have been asked about the functional >
>> equivalence of two lambda-expressions, a problem which is known to be undecidable.
>
> However, I see the following results sbcl that it does give some interesting results with
> respect to the nil and t types.
>
> CL-USER> (subtypep '(function (nil) nil) nil)
> NIL
> T
> CL-USER> (subtypep '(function (nil) t) nil)
> NIL
> T
> CL-USER> (subtypep '(function (t) nil) nil)
> NIL
> T
>
> My first guess would be that the type (function (nil) t) is itself nil.
> Am I misunderstanding something?
> If there is such a function, I'm very curious to understand what it is.

In set theory functions (or, more generally, relations) are defined as
sets of pairs

{<x1,y1>, <x2,y2>, ...}

(usually containing infinitely or even uncountably many pairs)

Then, a function operating on the empty set is perfectly possible, and
would be represented simply by the empty set {}.

Nicolas

Nicolas Neuss

3/17/2016 1:54:00 PM

0

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

> On Thursday, March 17, 2016 at 11:12:47 AM UTC+1, Barry Margolin wrote:
>> Nothing can be a subtype of NIL. So (subtypep <anything> nil) should
>> always return NIL, T.
>>
>
> Every empty type is a subtype of nil. For example (subtypep '(and string number) nil)
> returns T,T. So if (function (nil) nil) is an empty type (subtypep '(function (nil) nil) nil)
> should return T,T. Right? That subtypep returns T,T means (function (nil) nil) is
> NOT empty.
>
> I'd like to understand which functions are of type (function (nil) nil) as subtypep claims.
> They contradict my understanding of CL functions, so I'm happy to try to understand
> them better.

See my previous answer. Such functions are well defined in mathematics.

In CL, examples for such a function might be:

(defun f(x)
(error "Illegal argument: ~A" x))

or

(defun f(x)
(error "Not yet implemented"))

Nicolas

Kaz Kylheku

3/17/2016 2:56:00 PM

0

On 2016-03-17, Jim Newton <jimka.issy@gmail.com> wrote:
>
>> > CL-USER> (subtypep '(function (nil) nil) nil)
>> > NIL
>> > T
>> > CL-USER> (subtypep '(function (nil) t) nil)
>> > NIL
>> > T
>> > CL-USER> (subtypep '(function (t) nil) nil)
>> > NIL
>> > T
>>
>> Of course, every type is a supertype of nil, including nil itself.
>> There can be no exception to this, so there is no reason not
>> to give an authoritative answer.
>>
>
> No, what I mean is the following: Is (function (nil) nil)
> a SUBTYPE of nil? Of course nil is a subtype of (function (nil) nil), but
> my question is the other way around.

It isn't, and it follows from a three line /reductio ad absurdum/.

1. Suppose (function (nil) nil) is a subtype of nil.
2. Only nil is a subtype of nil.
3. Thus by 1 and 2, (function (nil) nil) is nil.
4. That is a contradiction of that (function (nil) nil) isn't nil.

Kaz Kylheku

3/17/2016 3:00:00 PM

0

On 2016-03-17, Jim Newton <jimka.issy@gmail.com> wrote:
> On Thursday, March 17, 2016 at 11:12:47 AM UTC+1, Barry Margolin wrote:
>> Nothing can be a subtype of NIL. So (subtypep <anything> nil) should
>> always return NIL, T.
>>
>
> Every empty type is a subtype of nil.

Chuckle!

*THE* one and only empty type, is denoted by the specifier nil.