Quantcast

I Need a Better Functional Language!

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

I Need a Better Functional Language!

Grigory Sarnitskiy
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Vo Minh Thu
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Andrew Butterfield
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Andrew Butterfield
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Dan Doel
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

paul r-2
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Tillmann Rendel-5
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
KC
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

KC


On Thu, Apr 5, 2012 at 11:59 AM, 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

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Gábor Lehel
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Strake
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Alexander Solla
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!

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.

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Ryan Ingram
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:
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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Ertugrul Söylemez
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.
Static optimizations like this one can be done, when you have an
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Grigory Sarnitskiy
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: I Need a Better Functional Language!

Conal Elliott
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:
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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Loading...