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


 

Forums >

comp.lang.lisp

self referential types, is CL over specified

Jim Newton

2/18/2016 10:37:00 AM

According to the specification of DEFTYPE CL implementation are forbidden from allowing self-referential types.

Here is the quote from the DEFTYPE spec.
Recursive expansion of the type specifier returned as the expansion must terminate, including the expansion of type specifiers which are nested within the expansion.


Isn't this over specified. Why could it not have said, something like the following? Implementations are not required to implement self-referential types. The consequences are undefined if recursive expansion of the type specifier returned as the expansion does not terminate.


Wouldn't such a specification have allowed implementations to expand types lazily if they chose to?

Here is an example of what I'd like to do, but is forbidden. I want to define a type whose elements are 1, (1), ((1)), (((1))), ((((1)))), etc.

CL-USER> (deftype unary-tree ()
`(or (eql 1)
(cons unary-tree)))

UNARY-TREE
CL-USER> (typep '(1) 'rte::unary-tree)

Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.
[Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED]

Restarts:
0: [RETRY] Retry SLIME REPL evaluation request.
1: [*ABORT] Return to SLIME's top level.
2: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING {1012FF8003}>)

Backtrace:
5 Answers

Didier Verna

2/18/2016 11:05:00 AM

0

Jim Newton wrote:

> Isn't this over specified. Why could it not have said, something like
> the following? Implementations are not required to implement
> self-referential types. The consequences are undefined if recursive
> expansion of the type specifier returned as the expansion does not
> terminate.
>
>
> Wouldn't such a specification have allowed implementations to expand
> types lazily if they chose to?

Probably, but I doubt any implementation would have cared to do so,
given the applicative order approach for evaluation that we have
(imagine that a SATISFIES predicate does side effects ;-)).

--
Resistance is futile. You will be jazzimilated.

Lisp, Jazz, Aïkido: http://www.didier...

Jim Newton

2/19/2016 9:23:00 AM

0

On Thursday, February 18, 2016 at 12:05:14 PM UTC+1, Didier Verna wrote:
> > Wouldn't such a specification have allowed implementations to expand
> > types lazily if they chose to?
>
> Probably, but I doubt any implementation would have cared to do so,
> given the applicative order approach for evaluation that we have
> (imagine that a SATISFIES predicate does side effects ;-)).
>

"would have cared to?" In my opinion it is just a wart in the spec, that an implementation
is forbidden from allowing well-defined recursive types. I'm not suggesting it should be required,
but if I want to experiment with recursive types, does that mean I have to use a different language
than Common Lisp? That seems unfortunate to me.

Barry Margolin

2/19/2016 3:41:00 PM

0

In article <97c2be0a-dd82-470f-afc4-16f95d53c3e1@googlegroups.com>,
Jim Newton <jimka.issy@gmail.com> wrote:

> On Thursday, February 18, 2016 at 12:05:14 PM UTC+1, Didier Verna wrote:
> > > Wouldn't such a specification have allowed implementations to expand
> > > types lazily if they chose to?
> >
> > Probably, but I doubt any implementation would have cared to do so,
> > given the applicative order approach for evaluation that we have
> > (imagine that a SATISFIES predicate does side effects ;-)).
> >
>
> "would have cared to?" In my opinion it is just a wart in the spec, that an
> implementation
> is forbidden from allowing well-defined recursive types. I'm not suggesting
> it should be required,
> but if I want to experiment with recursive types, does that mean I have to
> use a different language
> than Common Lisp? That seems unfortunate to me.

I don't think there's anything prohibiting implementations allowing it
as an extension. The section of the spec that you quoted is a
restriction on programs, not a requirement of implementations.

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

Kaz Kylheku

2/19/2016 5:42:00 PM

0

On 2016-02-19, Jim Newton <jimka.issy@gmail.com> wrote:
> On Thursday, February 18, 2016 at 12:05:14 PM UTC+1, Didier Verna wrote:
>> > Wouldn't such a specification have allowed implementations to expand
>> > types lazily if they chose to?
>>
>> Probably, but I doubt any implementation would have cared to do so,
>> given the applicative order approach for evaluation that we have
>> (imagine that a SATISFIES predicate does side effects ;-)).
>>
>
> "would have cared to?" In my opinion it is just a wart in the spec, that an implementation
> is forbidden from allowing well-defined recursive types. I'm not suggesting it should be required,
> but if I want to experiment with recursive types, does that mean I have to use a different language
> than Common Lisp? That seems unfortunate to me.

C has recursive types, luckily, so you don't have to look far.

struct list { struct list *next; void *data };

:)

Barry Margolin

2/19/2016 7:24:00 PM

0

In article <20160219094144.22@kylheku.com>,
Kaz Kylheku <330-706-9395@kylheku.com> wrote:

> On 2016-02-19, Jim Newton <jimka.issy@gmail.com> wrote:
> > On Thursday, February 18, 2016 at 12:05:14 PM UTC+1, Didier Verna wrote:
> >> > Wouldn't such a specification have allowed implementations to expand
> >> > types lazily if they chose to?
> >>
> >> Probably, but I doubt any implementation would have cared to do so,
> >> given the applicative order approach for evaluation that we have
> >> (imagine that a SATISFIES predicate does side effects ;-)).
> >>
> >
> > "would have cared to?" In my opinion it is just a wart in the spec, that
> > an implementation
> > is forbidden from allowing well-defined recursive types. I'm not
> > suggesting it should be required,
> > but if I want to experiment with recursive types, does that mean I have to
> > use a different language
> > than Common Lisp? That seems unfortunate to me.
>
> C has recursive types, luckily, so you don't have to look far.
>
> struct list { struct list *next; void *data };
>
> :)

But C doesn't have TYPEP, so it never has to traverse the type
definition tree.

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