What is Expressiveness in a Computer Language

[Pascal Bourguignon]

Matthias Blume <find at my.address.elsewhere> writes:

> Pascal Bourguignon <pjb at informatimago.com> writes:
>
>> Matthias Blume <find at my.address.elsewhere> writes:
>>
>>> Pascal Bourguignon <pjb at informatimago.com> writes:
>>>
>>>> Moreover, a good proportion of the program and a good number of
>>>> algorithms don't even need to know the type of the objects they
>>>> manipulate.
>>>>
>>>> For example, sort doesn't need to know what type the objects it sorts
>>>> are.  It only needs to be given a function that is able to compare the
>>>> objects.
>>>
>>> Of course, some statically typed languages handle this sort of thing
>>> routinely.
>>>
>>>> Only a few "primitive" functions need specific types.
>>>
>>> Your sort function from above also has a specific type -- a type which
>>> represents the fact that the objects to be sorted must be acceptable
>>> input to the comparison function.
>>
>> Well, not exactly.
>
> What do you mean by "not exactly".
>
>>  sort is a higher level function. The type of its
>> arguments is an implicit parameter of the sort function.
>
> What do you mean by "higher-level"? Maybe you meant "higher-order" or
> "polymorphic"?

Yes, that's what I wanted to say.

> [ rest snipped ]
>
> You might want to look up "System F".
> [...]
>>> ...or you type-check your "black box" and make sure that no matter how
>>> you will ever change the type of the inputs (in accordance with the
>>> interface type of the box) you get a valid program.
>>
>> When?
>
> When what?

When will you type-check the "black box"?

A function such as:

(defun f (x y)
   (if (g x)
      (h x y)
      (i y x)))

in the context of a given program could be type-infered statically as
taking an integer and a string as argument.  If the compiler did this
inference, it could perhaps generate code specific to these types.

But it's always possible at run-time that new functions and new
function calls be generated such as:

(let ((x "two"))
  (eval `(defmethod g ((self ,(type-of x))) t))
  (eval `(defmethod h ((x ,(type-of x)) (y string)) 
           (,(intern (format nil "DO-SOMETHING-WITH-A-~A" (type-of x))) x) 
           (do-something-with-a-string y)))
  (funcall (compile nil `(let ((x ,x)) (lambda () (f x "Hi!"))))))

Will you execute the whole type-inference on the whole program "black
box" everytime you define a new function?  Will you recompile all the
"black box" functions to take into account the new type the arguments
can be now?

This wouldn't be too efficient.  Let's just say that by default, all
arguments and variable are of type T, so the type checking is trivial,
and the generated code is, by default, totally generic.


Only the few concrete, low-level functions need to know the types of
their arguments and variables.  In these functions, either the lisp
compiler will do the type inference (starting from the predefined
primitives), or the programmer will declare the types to inform the
compiler what to expect.

(defun do-something-with-a-string (x)
  (declare (string x))
  ...)

(defun do-something-with-a-integer (x)
  (declare (integer x))
  ...)

...

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

PUBLIC NOTICE AS REQUIRED BY LAW: Any use of this product, in any
manner whatsoever, will increase the amount of disorder in the
universe. Although no liability is implied herein, the consumer is
warned that this process will ultimately lead to the heat death of
the universe.