On Sat, 22 Dec 2007 17:18:18 +0200, Philippa Cowderoy wrote:

...

The thing is I think that for a language to have "first-class" functions, it must be "homoiconic" if I understand the terms correctly.

You're confusing functions with the terms that are used to define them.

The terms aren't first-class, the functions are. This is intentional: the only way you can tell functions apart is if they give you different results for the same parameter. Otherwise, what you have isn't a function but a combination of a function and some extra structure.

I also confuse numbers with the terms that are used to define them (like 1.2) I guess I have to study more about this.

Cristian Baboi wrote:

While reading the Haskell language report I noticed that function type is not an instance of class Read.

I was told that one cannot define them as an instance of class Show without breaking "referential transparency" or printing a constant.

f :: (a->b)->String f x = "bla bla bla"

How can I define a function to do the inverse operation ? g :: String -> ( a -> b )

This time I cannot see how referential transparency will deny it. What's the excuse now ?

The new excuse is that a better name for g is full-fledged-compiler :: String -> (Int -> Int) (the function returned by g better not have a polymorphic type). Which programming language should the argument String be written in? Regards apfelmus

2007/12/24, Cristian Baboi :

On Mon, 24 Dec 2007 11:27:11 +0200, apfelmus wrote:

...

Cristian Baboi wrote:

...

...

How can I define a function to do the inverse operation ? g :: String -> ( a -> b ) This time I cannot see how referential transparency will deny it. What's the excuse now ?

It seems to me that "referential transparency" as well as "the executable don't embed it's source" aren't simple excuses, though you don't seem to understand that Haskell isn't an interpreted language... Similarly, the languages that offer an "eval()" as it is mostly called are always interpreted, most other languages push this capability (if they have it at all) on libraries, in Haskell you can try to use hs-plugins for example. -- Jedaï

On Mon, 2007-12-24 at 11:15 +0200, Cristian Baboi wrote:

While reading the Haskell language report I noticed that function type is not an instance of class Read.

I was told that one cannot define them as an instance of class Show without breaking "referential transparency" or printing a constant.

f :: (a->b)->String f x = "bla bla bla"

How can I define a function to do the inverse operation ? g :: String -> ( a -> b )

This time I cannot see how referential transparency will deny it. What's the excuse now ?

Referential transparency has nothing to with this. The problem here is parametricity. However, if you give a non-parametric type (or add appropriate class constraints on a and b, or add (phantom) type information to the input), e.g. String -> (Int -> Int) then there is no trouble at all. The compiler (or something non-portably using extremely unsafe features) could provide a primitive String -> a that reads in a string and interprets it somehow as a value of type a. If the value represented by the string doesn't match the type that a is instantiated to, something bad is going to happen. Adding such a primitive would utterly destroy parametricity.

Hi Cristian, Cristian Baboi wrote:

While reading the Haskell language report I noticed that function type is not an instance of class Read. I was told that one cannot define them as an instance of class Show without breaking "referential transparency" or printing a constant... How can I define a function to do the inverse operation ? g :: String -> ( a -> b ) This time I cannot see how referential transparency will deny it. What's the excuse now ? ...I finished reading the Haskell Language Report and I noticed that the class Show and Read are "toys".

Actually, they are not toys at all. They are very useful, and they do their job well. But it looks like they are not the right tool for what you want to do. What exactly are you trying to accomplish? Why would you want there to be instances like that? Are you thinking of program development and debugging? There are great tools for that. Are you thinking of reflection? There are great tools for that also. But because of the power of Haskell's type system, you need that much less than in many other languages. Regards, Yitz

On 12/26/07, Cristian Baboi wrote:

The reason I want to build functions of type String -> (a -> b) is because I want to see how far I can get with "functions are first class citizens" in Haskell. I thought that if I read the function from an external source, there is no way the compiler could know what I'll read. I want to see if I can build a Haskell function at runtime, not a data structure that I can interpret.

Those two questions are intimately related, though. Consider the following simple program:

{-# LANGUAGE GADTs #-} module Compile where

data Term a where App :: Term (a -> b) -> Term a -> Term b Prim :: a -> Term a

Implementation of lambda-abstractions is left as an exercise for the reader.

compile :: Term a -> a compile (Prim x) = x compile (App x y) = compile x $ compile y

While "compile" looks like an interpreter (and it is), there is no reason why "a" has to be a concrete data type; it could be a function type, as demonstrated here:

uncompiled_func :: Term (Int -> Int) uncompiled_func = App (Prim (+)) (Prim 1)

compiled_func :: Int -> Int compiled_func = compile uncompiled_func

The first time you evaluate "compiled_func", you'll run the "compiler" which will create a function for you. Consider the lazy evaluation order of this program:

result :: Int result = compiled_func 3 + compiled_func 4

I'll use "let" to represent sharing and "plus#" to represent the primitive operation of adding two numbers which (+) is defined in terms of. That is, (+) = \x y -> plus# x y result => compiled_func 3 + compiled_func 4 => (\x y -> plus# x y) (compiled_func 3) (compiled_func 4) => plus# (compiled_func 3) (compiled_func 4) => let compiled_func = compile uncompiled_func in plus# (compiled_func 3) (compiled_func 4) (evaluating compiled_func) compile (App (Prim (+)) (Prim 1)) => compile (Prim (+)) (compile (Prim 1)) => (+) (compile (Prim 1)) => (\x y -> plus# x y) (compile (Prim 1)) => (\y -> plus# (compile (Prim 1)) y) which is WHNF => let compiled_func = (\y -> plus# (compile (Prim 1)) y) in plus# (compiled_func 3) (compiled_func 4) => let inner = (compile (Prim 1)); compiled_func = \y -> plus# inner y in plus# (compiled_func 3) (compiled_func 4) => let inner = (compile (Prim 1)) in plus# (plus# inner 3) ((\y -> plus# inner y) 4) => let inner = 1 in plus# (plus# inner 3) ((\y -> plus# inner y) 4) => plus# 4 ((\y -> plus# 1 y) 4) => plus# 4 (plus# 1 4) => plus# 4 5 => 9 Note that "compile" only gets run once on each subexpression; the end result is that you end up with a regular Haskell function which does no interpretation at all! All that remains is creation of something of type "Term a" from an untyped representation. Oleg's done the work here and you can see a full implementation in this message: http://www.haskell.org/pipermail/haskell-cafe/2007-October/032591.html -- ryan