Re: Arrays and general function representation
In article <[EMAIL PROTECTED]> [EMAIL PROTECTED] writes: > >In any case, I think it is high time that we free ourselves of an >imperative view of arrays and functions, and the differences between >the two. > You are right that too much of an imperative view *is* taken of functional programming. Most textbooks implicitly promote this view. Of course we get the platitudes at the beginning of textbooks - a few lines saying that functional programs are based on maths (the *most* important thing, IMHO), they are not "instruction-based", there are no assignments, they have referential transparency. Then, off they go throughout the rest of the book giving us a very "instruction-based" view of functions and functional programming! Regarding the `set of ordered pairs' view of functions, the syntax may not be too clever, but you can get something similar by saying (for an example `double' function): double 0 = 0 double 1 = 2 double 2 = 4 double 3 = 6 ... etc Rob -- -- Rob Turner, Dept. of Computer Science, University of Hull, UK. Internet: [EMAIL PROTECTED] Phone: (0482) 465212
Re: Arrays and general function representation
> From: Paul Otto <[EMAIL PROTECTED]> >>And finally, it makes sense to have separate syntax for arrays >>and general functions, because different behavior is expected >>for the two. > That argument would suggest that you should use a different > syntax for each different implementation of an abstract data > type. (Since their performance tradeoffs are usually different.) > Do you advocate that? Ideally, no. Practically yes. If compilers were smart enough to determine which would be the most efficient implementation for the most abstract version of a function, who would ever want to worry about such details? In fact, many algorithms are efficient by expoiting various features of imperative arrays. If I want to encode such an algorithm, I want my performance to be guaranteed to be no worse than those imperative arrays. If you deny the programmer control over efficiency, why use the language? Oh, maybe as a specification language, but it certainly won't be used in industrial strength programming. Further, in a typical program I will mix functions that compute values by rules and arrays -- if the compiler has no ability to determine which should be implemented as which, I certainly should be able to make that specification. Ken
Re: Arrays and general function representation
date: Thu, 3 Sep 92 15:58:43 CST from: [EMAIL PROTECTED] (Ken Sailor) >Arrays and general functions are isomorphic, certainly in theory. >In practice, however, they are different and the differences >are significant. >And finally, it makes sense to have separate syntax for arrays >and general functions, because different behavior is expected >for the two. That argument would suggest that you should use a different syntax for each different implementation of an abstract data type. (Since their performance tradeoffs are usually different.) Do you advocate that? Paul
Re: Arrays and general function representation
My humble opinion about arrays and general functions... Arrays and general functions are isomorphic, certainly in theory. In practice, however, they are different and the differences are significant. In general, although the set theoretic definition of a function is a set of ordered pairs, it is convenient to think of a function as a rule. That is, given an input, the rule tells how to compute the output. It may be that for some special functions, we want to encode the rule as a lookup on some table, but in fact this technique is not generally applicable. Why store a gazillion values for + when we can implement the rule in hardware? Typically arrays are boxes which contain values. That is, they are multi-dimensional tables in which values can be looked up. In the imperative world, the lookup cost is typically a constant, guaranteeing timing behavior for various algorithms. In the functional world, nobody has figured out how to get all the practical benefits of imperative arrays, for a variety of reasons. Until these benefits are achieved, functional languages will not be practical for most, if not all, scientific programming applications. (apologies to the sisal community in advance -- my own interest is in lazy functional languages like Haskell, where arrays are in greater disorder). It entirely misses the point of why arrays are hard to say that there are no differences between arrays and general functions. In theory, arrays are a snap. You can have them in a variety of interesting forms, but they don't come with the performance guarantees they have in the imperative world, and that is the problem of arrays in a nutshell. And finally, it makes sense to have separate syntax for arrays and general functions, because different behavior is expected for the two. Ken Sailor [EMAIL PROTECTED]
Re: Arrays and general function representation
My humble opinion about arrays and general functions... Arrays and general functions are isomorphic, certainly in theory. In practice, however, they are different and the differences are significant. In general, although the set theoretic definition of a function is a set of ordered pairs, it is convenient to think of a function as a rule. That is, given an input, the rule tells how to compute the output. It may be that for some special functions, we want to encode the rule as a lookup on some table, but in fact this technique is not generally applicable. Why store a gazillion values for + when we can implement the rule in hardware? Typically arrays are boxes which contain values. That is, they are multi-dimensional tables in which values can be looked up. In the imperative world, the lookup cost is typically a constant, guaranteeing timing behavior for various algorithms. In the functional world, nobody has figured out how to get all the practical benefits of imperative arrays, for a variety of reasons. Until these benefits are achieved, functional languages will not be practical for most, if not all, scientific programming applications. (apologies to the sisal community in advance -- my own interest is in lazy functional languages like Haskell, where arrays are in greater disorder). It entirely misses the point of why arrays are hard to say that there are no differences between arrays and general functions. In theory, arrays are a snap. You can have them in a variety of interesting forms, but they don't come with the performance guarantees they have in the imperative world, and that is the problem of arrays in a nutshell. And finally, it makes sense to have separate syntax for arrays and general functions, because different behavior is expected for the two. Ken Sailor [EMAIL PROTECTED]
Re: Arrays and general function representation
I like David Barton's idea of distinguishing between the array representation of functions and the more familiar computational representation at the declaration level but not at the reference level. With this appraoch references to arrays and references to functions would look the same in expressions, which is appealing because they express the same concepts. Declarations would give the processor hints about possible economies of implementation. At least one language I know of suggests, in its syntax, the similarity between functions and arrays: Fortran. Subsequent languages have, unfortunately, failed to follow Fortran's good example in this regard. I tried to get the Fortran 90 standards committee to continue the metaphor to data structures so that references to components would look like function references and be distinguished from them only in the declarations. The committee didn't buy the idea, however. A question that came up in the Fortran 90 discussions on the syntax of references to components of data structures: Which is the function and which the argument? Fortran syntax views the array as the function and the subscript as the argument. The other way around seems better for data structures because component names are constant entities and different instances of the data structure are the (variable) data that might act as arguments to (selector) functions denoted by the names of components. This might work for arrays, too: traditional references (array is function, a 1, a 2, ... subscript is argument) other way around (subscript is function, 1 a, 2 a, ... array is argument) In the alternative formulation, the integers name polymorphic functions mapping arrays of various types into the base type of those arrays. But there is a problem with dereferencing a variable subscript in this formulation: (n a) should mean "apply the function named by the integer value of n to the array a" rather than "apply the function named n to a". The traditional formulation gets the referencing right, though, doesn't it? And it seems to apply equally well to lists. Writing (lst n) to select the n-th element of lst looks good and draws an appropriate analogy to functions. Rex Page
