Hello! I've just realized that Haskell is no good for working with functions!
First, what are 'functions' we are interested at? It can't be the usual set-theoretic definition, since it is not constructive. The constructive definition should imply functions that can be constructed, computed. Thus these are computable functions that should be of our concern. But computable functions in essence are just a synonym for programs. One could expect from a language that bears 'functional' as its characteristic to be able to do everything imaginable with functions. However, the only thing Haskell can do with functions is to apply them to arguments and to feed them as arguments, run in parallel (run and concatenate programs). Obviously, that's not all of the imaginable possibilities. One also can rewrite programs. And write programs that rewrite programs. And write programs that rewrite programs that rewrite the first programs and so on. But there is no such possibility in Haskell, except for introducing a DSL. So now I wonder, what are the languages that are functional in the sense above? With a reasonable syntax and semantics, thus no assembler. I guess Lisp might be of this kind, but I'm not sure. In addition, I'm not a fan of parentheses. What else? Pure? Mathematica? Maxima? Note, that the reflectivity is important. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Le 5 avril 2012 16:14, Grigory Sarnitskiy <[hidden email]> a écrit :
> Hello! I've just realized that Haskell is no good for working with functions! > > First, what are 'functions' we are interested at? It can't be the usual set-theoretic definition, since it is not constructive. The constructive definition should imply functions that can be constructed, computed. Thus these are computable functions that should be of our concern. But computable functions in essence are just a synonym for programs. > > One could expect from a language that bears 'functional' as its characteristic to be able to do everything imaginable with functions. However, the only thing Haskell can do with functions is to apply them to arguments and to feed them as arguments, run in parallel (run and concatenate programs). > > Obviously, that's not all of the imaginable possibilities. One also can rewrite programs. And write programs that rewrite programs. And write programs that rewrite programs that rewrite the first programs and so on. But there is no such possibility in Haskell, except for introducing a DSL. > > So now I wonder, what are the languages that are functional in the sense above? With a reasonable syntax and semantics, thus no assembler. I guess Lisp might be of this kind, but I'm not sure. In addition, I'm not a fan of parentheses. What else? Pure? Mathematica? Maxima? Hello, You might be interested in https://github.com/MikeHaskel/Constructiva/wiki Cheers, Thu _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
On 5 Apr 2012, at 15:14, Grigory Sarnitskiy wrote: > Hello! I've just realized that Haskell is no good for working with functions! > > .... > > Obviously, that's not all of the imaginable possibilities. One also can rewrite programs. And write programs that rewrite programs. And write programs that rewrite programs that rewrite the first programs and so on. But there is no such possibility in Haskell, except for introducing a DSL. > > So now I wonder, what are the languages that are functional in the sense above? With a reasonable syntax and semantics, thus no assembler. I guess Lisp might be of this kind, but I'm not sure. Probably - but the semantics is dreadful... > > > Note, that the reflectivity is important. Intel developed a reflective functional language/system called Forte that is the basic of a lot of their formal hardware verification process... http://www.cs.ox.ac.uk/tom.melham/res/forte.html > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group Director of Teaching and Learning - Undergraduate, School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ -------------------------------------------------------------------- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
Addendum:
Intel's Forte was the framework, reFLect was the language : http://www.cs.ox.ac.uk/tom.melham/res/reflect.html Quoting that page: "reFLect is a functional programming language designed and implemented by a team at Intel Corporation's Strategic CAD Labs under the direction of Jim Grundy. The language is strongly typed and similar to ML, but provides certain reflection features intended for applications in industrial hardware design and verification. Like LISP, reFLect has quotation and antiquotation constructs that may be used to construct and decompose expressions in the language itself. Unlike LISP, these mechanisms are typed. The language also provides a primitive mechanism for pattern-matching, and in particular for defining functions over code by pattern-matching on the structure of reFLect expressions." On 5 Apr 2012, at 15:14, Grigory Sarnitskiy wrote: > Hello! I've just realized that Haskell is no good for working with functions! > > First, what are 'functions' we are interested at? It can't be the usual set-theoretic definition, since it is not constructive. The constructive definition should imply functions that can be constructed, computed. Thus these are computable functions that should be of our concern. But computable functions in essence are just a synonym for programs. > > One could expect from a language that bears 'functional' as its characteristic to be able to do everything imaginable with functions. However, the only thing Haskell can do with functions is to apply them to arguments and to feed them as arguments, run in parallel (run and concatenate programs). > > Obviously, that's not all of the imaginable possibilities. One also can rewrite programs. And write programs that rewrite programs. And write programs that rewrite programs that rewrite the first programs and so on. But there is no such possibility in Haskell, except for introducing a DSL. > > So now I wonder, what are the languages that are functional in the sense above? With a reasonable syntax and semantics, thus no assembler. I guess Lisp might be of this kind, but I'm not sure. In addition, I'm not a fan of parentheses. What else? Pure? Mathematica? Maxima? > > Note, that the reflectivity is important. > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group Director of Teaching and Learning - Undergraduate, School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ -------------------------------------------------------------------- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
On Thu, Apr 5, 2012 at 10:14 AM, Grigory Sarnitskiy <[hidden email]> wrote:
> First, what are 'functions' we are interested at? It can't be the usual set-theoretic definition, since it is not constructive. The constructive definition should imply functions that can be constructed, computed. Thus these are computable functions that should be of our concern. But computable functions in essence are just a synonym for programs. This is a flawed premise. The point of working with functions is abstraction, and that abstraction is given by extensional equality of functions: f = g iff forall x. f x = g x So functions are not synonymous with programs or algorithms, they correspond to an equivalence class of algorithms that produce the same results from the same starting points. If you can access the source of functions within the language, this abstraction has been broken. And this abstraction is useful, because it allows you to switch freely between programs that do the same thing without having to worry that someone somewhere is relying on the particular algorithm or source. This is the heart of optimization and refactoring and the like. There are places for metaprogramming, or perhaps even a type of algorithms that can be distinguished by means other than the functions they compute. But to say that functions are that type is false, and that functions should mean that is, I think, wrong headed. -- Dan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
Grigory> So now I wonder, what are the languages that are functional in Grigory> the sense above? With a reasonable syntax and semantics, thus Grigory> no assembler. I guess Lisp might be of this kind, but I'm not Grigory> sure. In addition, I'm not a fan of parentheses. What else? Grigory> Pure? Mathematica? Maxima? Indeed you want a *different* programming language. But it won't be *better*, just different. Indeed, as soon as your program react to the implementation of its functions, you will be in a land where you lose a fundamental abstraction, so you won't be able to change implementation anymore whithout changing callers as well. I am curious what are interesting use-cases for that ? Symbolic analysis ? self-compilers ? -- Paul _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Paul R wrote:
> I am curious what are interesting use-cases for that? Symbolic > analysis? self-compilers? Optimization. For example, imagine the following definition of function composition: map f . map g = map (f . g) f . g = \x -> f (g x) In Haskell, we cannot write this, because we cannot pattern match on function calls. Tillmann _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, Apr 5, 2012 at 11:59 AM, Tillmann Rendel <[hidden email]> wrote: -- So, we're not talking about optimization as in Mathematical Programming but optimization in language constructs. You might want to take a look at MIN by Stephen Tse. -- Regards, KC _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Tillmann Rendel-5
On Thu, Apr 5, 2012 at 8:59 PM, Tillmann Rendel
<[hidden email]> wrote: > Paul R wrote: >> >> I am curious what are interesting use-cases for that? Symbolic >> analysis? self-compilers? > > > Optimization. For example, imagine the following definition of function > composition: > > map f . map g = map (f . g) > f . g = \x -> f (g x) > > In Haskell, we cannot write this, because we cannot pattern match on > function calls. > > Tillmann On the one hand, yes we can, with RULES: http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/rewrite-rules.html On the other hand, I've never used it, but this sounds a bit like Pure: http://code.google.com/p/pure-lang/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
On 05/04/2012, Grigory Sarnitskiy <[hidden email]> wrote:
> One could expect from a language that bears 'functional' as its > characteristic to be able to do everything imaginable with functions. > However, the only thing Haskell can do with functions is to apply them to > arguments and to feed them as arguments, run in parallel (run and > concatenate programs). > > Obviously, that's not all of the imaginable possibilities. One also can > rewrite programs. And write programs that rewrite programs. And write > programs that rewrite programs that rewrite the first programs and so on. > But there is no such possibility in Haskell, except for introducing a DSL. > > Note, that the reflectivity is important. For x86 machine: http://hackage.haskell.org/package/hdis86 Truly, I often wish to be able to pattern match on functions myself. Alas, the function is not an algebraic data type. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Grigory Sarnitskiy
On Thu, Apr 5, 2012 at 7:14 AM, Grigory Sarnitskiy <[hidden email]> wrote:
Hello! I've just realized that Haskell is no good for working with functions! The usual set theoretic definition is constructive -- it is the extension of the definition which is non-constructive. We can restrict the extension to constructive domains. Note that we do not need the law of the excluded middle or double negation to define a function.
We can easily define: > newtype Function a b = Function (Set (a,b)) > apply :: (Function a b) -> a -> b > apply f a = findMin . filter (\(a',_) -> a == a') $ f
and enforce the function definition/axioms with a smart constructor. (A Map is probably a better data structure for this purpose) Obviously, that's not all of the imaginable possibilities. One also can rewrite programs. And write programs that rewrite programs. And write programs that rewrite programs that rewrite the first programs and so on. But there is no such possibility in Haskell, except for introducing a DSL. You will always need a DSL of some kind. Otherwise, what will you quantify over? This is an important point. In order to give a function semantics, it /must/ be interpreted. This will either happen by the compiler, which interprets a function definition in terms of machine code (or Haskell code, if you use Template Haskell), or at run-time, as in the "Function a b" type above. With some appropriate constraints, you can even rewrite a (->)-function in terms of a "Function"-function, and vice-versa.
toFunction :: (Enum a, Bounded a) => (a -> b) -> (Function a b) toFunction f = Set.fromList . fmap f $ [minBound..maxBound] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Dan Doel
A concurring opinion here, and an example.
iff :: Bol -> a -> a -> a iff True x _ = x iff False _ x = x f, g :: Bool -> Bool f x = x g x = iff x True False Are these two functions equal? I would say yes, they are. Yet once you can pattern match on functions, you can easily tell these functions apart, and create a function h :: (Bool -> Bool) -> Bool such that h f => True but h g => False. -- ryan On Thu, Apr 5, 2012 at 8:52 AM, Dan Doel <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Tillmann Rendel-5
Tillmann Rendel <[hidden email]> wrote:
> > I am curious what are interesting use-cases for that? Symbolic > > analysis? self-compilers? > > Optimization. For example, imagine the following definition of > function composition: > > map f . map g = map (f . g) > f . g = \x -> f (g x) > > In Haskell, we cannot write this, because we cannot pattern match on > function calls. abstraction layer above the actual functions. In fact you can even write efficient statically and dynamically self-organizing networks of functions, as long as there is an algebraic type to support it. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/ _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe signature.asc (853 bytes) Download Attachment |
In reply to this post by Ryan Ingram
10.04.2012, 02:00, "Ryan Ingram" <[hidden email]>:
> A concurring opinion here, and an example. > > iff :: Bol -> a -> a -> a > iff True x _ = x > iff False _ x = x > > f, g :: Bool -> Bool > f x = x > g x = iff x True False > > Are these two functions equal? I would say yes, they are. Yet once you can pattern match on functions, you can easily tell these functions apart, and create a function > > h :: (Bool -> Bool) -> Bool > such that h f => True but h g => False. > > -- ryan I've just remembered an interesting statement that there is a language where each equivalence class of programs Dan Doel mentioned (f = g iff forall x. f x = g x) has a single program in it. That is there is a one-to-one correspondence between programs and functions. Though as far as I understood one cannot construct a translator from this language to another language. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Dan Doel
Agreed. The original note confuses programs (syntax) with functions (semantics). -- Conal
On Thu, Apr 5, 2012 at 8:52 AM, Dan Doel <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |