type expressions 
Author Message
 type expressions

I have a question regarding type specifiers in dylan.
  The BNF (as specified in the DRM) indicates that any expression
(excepting keywords and binary/unary operators) can be used to specify a
type.  The DRM does not indicate whether there are any restrictions on the
complexity of these expressions.
  For example, I should be able to specify a parameter type using an
expression that pops up a menu for the user to select from.
  However, it seems to me, that for type specifiers to be useful, the
compiler needs to be able to evaluate them at compile time otherwise
optimisation of the code isn't possible (type checking would have to be
done dynamically and generic-function dispatch cannot be eliminated).

Are there any restrictions on what a type specifier expression can do?  If
not, at what point would a compiler "give up" trying to evaluate one at
compile time?  If evaluation is left for run time, exactly *when* do these
expressions get executed?

Thanks in advance,

Louis Madon



Mon, 20 Sep 1999 03:00:00 GMT  
 type expressions


Quote:
>I have a question regarding type specifiers in dylan.
>  The BNF (as specified in the DRM) indicates that any expression
>(excepting keywords and binary/unary operators) can be used to specify a
>type.  The DRM does not indicate whether there are any restrictions on the
>complexity of these expressions.
>  For example, I should be able to specify a parameter type using an
>expression that pops up a menu for the user to select from.
>  However, it seems to me, that for type specifiers to be useful, the
>compiler needs to be able to evaluate them at compile time otherwise
>optimisation of the code isn't possible (type checking would have to be
>done dynamically and generic-function dispatch cannot be eliminated).

>Are there any restrictions on what a type specifier expression can do?  If
>not, at what point would a compiler "give up" trying to evaluate one at
>compile time?  If evaluation is left for run time, exactly *when* do these
>expressions get executed?

There are no restrictions on what a type expression can do.  The model is
that type expressions are just ordinary expressions which get executed in
the normal course of program execution flow like any other expressions, but
which happen to be required to return an instance of <type>.  However, the
compiler is
encouraged to move the computation as early as possible while still
maintaining the same semantics.  Thus, for example, the common case of a
specializer which is just a named reference to a constant binding defined
via "define class" can be safely and correctly hoisted to compile-time (as
with any other form of constant analysis), and the information gained from
doing so can then be used in further compile-time analysis.

The rationale for this approach is that it eliminates the need for an
additional kind of expression with its own (potentially idiosyncratic and
inconsistent with other parts of the language) execution semantics.
Instead, there is just one kind of expression and one set of execution
semantics to learn.

Of course, it is certainly possible to use type expressions that are opaque
to the compiler, limiting the ability to provide compile-time error
checking and optimization.  The common cases that one sees in real programs
are not a problem though, and presumably if a programmer writes a program
involving some complex and unanalyzable type expressions the programmer had
a reason for doing so, and is willing to pay some cost in compile-time
error checking and run-time execution in order to get the benefit of the
greater expressiveness.  This is in line with the philosophy of providing
varying degrees of dynamism and late binding, under the control of the
programmer.

The time at which the evaluation occurs depends on time when the enclosing
form is executed and the semantics of the enclosing form.  Some examples:

* Definitions are executed at load time, so a type expression that is part
of a definition form (such as the specializers in a "define method" or the
superclasses in a "define class") are executed then.

* The specializers in a "method" form are executed at the time the method
is executed.  Thus, the following example:

  define constant make-type-checker (t :: <type>) => <function>;
    method (x :: t) x end;
  end;

  make-type-checker(<integer>) => a function of one argument which returns the
                                  argument if it is an <integer> and signals
                                  an error otherwise.

* The specializers in a "let" form are executed at entry to the form.  (I
don't remember whether the order of execution of the specializers with
respect to the value expression is specified.  I would guess that the
specializers would be executed first, but I don't have time right now to
hunt for a reference.)  Thus, the following example:

  define constant type-checker
    = method (x, t :: <type>)
       let checked :: t = x;
       checked;
      end;

The function type-checker returns the first argument if it is an instance
of the second argument, signaling an error otherwise.



Wed, 22 Sep 1999 03:00:00 GMT  
 type expressions



Quote:

>* The specializers in a "method" form are executed at the time the method
>is executed.  Thus, the following example:

>  define constant make-type-checker (t :: <type>) => <function>;

          ^^^^^^^^-- should be "method" right? :-)

Quote:
>    method (x :: t) x end;
>  end;

  Hmm, so...

   define method make-type-checker ( t :: union( <type-x> <type-y>)) ;
    ....
   end method;

  That union is dynamically recreated on each invocation of the Generic
  Function..... even if I don't end up dispatching through this
  particaluar method ( assuming there were more than one ) ....

  I'd hope there were some special case code for when the type is the
  result of the singleton expression when the argument is a literal.
  I guess that particular kind of expression is just a constant propogation
  though.

--

Lyman S. Taylor          "Any sufficiently advanced technology is

                                   -- paraphrased Arthur C. Clarke
                                        seen somewhere on the USENET



Thu, 23 Sep 1999 04:00:00 GMT  
 type expressions


Quote:
>In article


>>* The specializers in a "method" form are executed at the time the method
>>is executed.  Thus, the following example:

>>  define constant make-type-checker (t :: <type>) => <function>;
>          ^^^^^^^^-- should be "method" right? :-)
>>    method (x :: t) x end;
>>  end;

>  Hmm, so...

>   define method make-type-checker ( t :: union( <type-x> <type-y>)) ;
>    ....
>   end method;

>  That union is dynamically recreated on each invocation of the Generic
>  Function..... even if I don't end up dispatching through this
>  particaluar method ( assuming there were more than one ) ....

>  I'd hope there were some special case code for when the type is the
>  result of the singleton expression when the argument is a literal.
>  I guess that particular kind of expression is just a constant propogation
>  though.

Oh bother!  I really botched some of that.

Quote:
>>* The specializers in a "method" form are executed at the time the method
>>is executed.  Thus, the following example:

That should have been

  * The specializers in a "method" form are executed at the time the method
    form is executed.

In other words, specializers are free expressions executed prior to the
execution of the method form and captured by the method form, much like
closed over free variable references.

Quote:
>>  define constant make-type-checker (t :: <type>) => <function>;
>          ^^^^^^^^-- should be "method" right? :-)
>>    method (x :: t) x end;
>>  end;

That should have been

  define constant make-type-checker
    = method (t :: <type>) => f :: <function>;
        method (x :: t) x end;
      end;

So no, that union type in your example is not recreated on each invocation
of the generic function.  It is created once when the "define method" is
executed.  Sorry I didn't proof that message more carefully.  I hope there
aren't any more braino's in there...



Fri, 24 Sep 1999 03:00:00 GMT  
 type expressions

Quote:
>There are no restrictions on what a type expression can do.
>The model is that type expressions are just ordinary expressions
>which get executed in the normal course of program execution
>flow like any other expressions, but which happen to be required
>to return an instance of <type>.

In considering ways to enhance the expressiveness of type
specifications, it might be helpful to introduce the Curry-Howard
isomorphism.  This was the "surprising" discovery that the type
inferences in a functional programming language operate just like
the proof sequents of predicate logic.  The area is fairly active
and has been stimulated by such recent arrivals as the "linear
logic" of Yves Girard.

Handling type validation with a resolution theorem prover might
at first glance seem inefficient, but it would serve the aim of
performing as much of this work as possible at compile time.

Introducing a type validation protocol, on the other hand, may
force the compiler to leave much of the checking until run-time;
and it leaves lots of room to mix up an already complicated type
system.



Fri, 24 Sep 1999 03:00:00 GMT  
 type expressions



Quote:

>So no, that union type in your example is not recreated on each invocation
>of the generic function.  It is created once when the "define method" is
>executed.

  Ah so given:

       define method foo ( arg :: t )
       ...
       end method foo;

  then if  the variable t were initially bound to

        define variable t :: <type> =  <byte-string>

  FOO would dispatch on <byte-string>   even if later on during
  execution  t were changed ( e.g.  t := <arrray> ).  And if the
  variable t were not initially bound:

       define variable t :: <type> ;

  Then this should be a compile ( or perhaps "link" ) time error.
  [ i.e. it has to be an expression that is bound at definition time. ]

  Otherwise, it would be kind of tough to make efficient. :-)

--

Lyman S. Taylor          "Any sufficiently advanced technology is

                                   -- paraphrased Arthur C. Clarke
                                        seen somewhere on the USENET



Fri, 24 Sep 1999 03:00:00 GMT  
 type expressions


Quote:
>  Ah so given:

>       define method foo ( arg :: t )
>       ...
>       end method foo;

>  then if  the variable t were initially bound to

>        define variable t :: <type> =  <byte-string>

>  FOO would dispatch on <byte-string>   even if later on during
>  execution  t were changed ( e.g.  t := <arrray> ).

Correct.

Quote:
>  And if the
>  variable t were not initially bound:

>       define variable t :: <type> ;

That isn't a syntactically valid expression, so doesn't cause any problems
for the issue at hand...


Sat, 25 Sep 1999 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Intermediate type of mixed-type expressions

2. Expression conformance and anchored types

3. types of the limit expressions of FOR statements

4. type of limit expressions of FOR loops

5. Intermediate expressions and modular types

6. : Determination of Expression Type

7. using expressions in derived type assignments

8. Type specification and initialization expressions

9. PGF90-S-0087-Non-constant expression where constant expression required

10. PGF90-S-0087-Non-constant expression where constant expression required

11. Non-constant expression where constant expression required.

12. IF { EXPRESSION or EXPRESSION }

 

 
Powered by phpBB® Forum Software