On the fly generation of representations of function calls
Author Message
On the fly generation of representations of function calls

Hello,

I am a fair novice with respect to the real world of functional programming
and I have a question. I don't know whether it is quite FAQ-ish, but here
it goes.

I have two datastructures and two functions defined on those datastructures:

[]      data ConsList a = Nilc | Cons (a) (ConsList a)
[]      data SnocList a = Nils | Snoc (SnocList a) (a)
[]
[]      singlec x = Cons (x) (Nilc)
[]      singles x = Snoc (Nils) (x)
[]
[]      delta (Nilc) x = singlec x
[]      delta (Cons a b) x = Cons (a) (delta b x)
[]
[]      gamma (Nils) = Nilc
[]      gamma (Snoc l x) = delta (gamma l) x

What the gamma/delta pair does is convert an element from SnocList to an
equivalent element in ConsList.

This works fine. But what I would like to be able to have is an extension
to the definitions of gamma and delta such that at the end of the derivation
I also have a list of derivation (rewrite) steps at my disposal.

So instead of only the final result of the conversion I would also like a
list like:

["gamma (Snoc (Snoc (Nils) 6) 5)",
"delta(gamma (Snoc (Nils) 6)) 5",
"delta(delta(gamma Nils) 6) 5",
"delta(delta(Nilc) 6) 5",
"delta(Cons 6 (Nilc)) 5",
"Cons (6) (delta Nilc 5)",
"Cons (6) (Cons (5) (Nilc))"]

So I would like to obtain a list of (representations of) intermediate
results.

If anyone has any solutions to my problem or suggestions please let me know.

Thank you very much in advance,

--

Harold Weffers      c/o Eindhoven University of Technology
Department of Mathematics and Computing Science
/_/  /   /          HG 6.64
/ /. /_/_/.          P.O. Box 513, 5600 MB  EINDHOVEN, The Netherlands
Telephone: (+31) (0)40 - 474231

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#
| Disclaimer: I say what?  |      - To err is human, to forgive divine -  |
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~#

Sat, 18 Nov 1995 15:20:26 GMT
On the fly generation of representations of function calls

Quote:
>I am a fair novice with respect to the real world of functional programming
>and I have a question. I don't know whether it is quite FAQ-ish, but here
>it goes.
>[]  data ConsList a = Nilc | Cons (a) (ConsList a)
>[]  data SnocList a = Nils | Snoc (SnocList a) (a)
>[]
>[]  singlec x = Cons (x) (Nilc)
>[]  singles x = Snoc (Nils) (x)
>[]
>[]  delta (Nilc) x = singlec x
>[]  delta (Cons a b) x = Cons (a) (delta b x)
>[]
>[]  gamma (Nils) = Nilc
>[]  gamma (Snoc l x) = delta (gamma l) x
>    ["gamma (Snoc (Snoc (Nils) 6) 5)",
>     "delta(gamma (Snoc (Nils) 6)) 5",
>     "delta(delta(gamma Nils) 6) 5",
>     "delta(delta(Nilc) 6) 5",
>     "delta(Cons 6 (Nilc)) 5",
>     "Cons (6) (delta Nilc 5)",
>     "Cons (6) (Cons (5) (Nilc))"]

This is easy if you've studied functional languages for a while - you just
need to simulate the language's reduction mechanism. I do this with a function
called contract which searches for a redex and contracts it. The main program
(called "doit") applies this to the initial expression repeatedly and prints
the result out. This was written in Gofer:

data DG = Delta DG DG | Gamma DG | Nilc | Nils | Integer Int | Cons DG DG |
Snoc DG DG

instance Eq DG where
(Delta a b) == (Delta c d) = (a == c) && (b == d)
(Gamma a) == (Gamma b)     = (a == b)
Nilc == Nilc               = True
Nils == Nils               = True
(Integer i) == (Integer j) = (i == j)
(Cons a b) == (Cons c d)   = (a == c) && (b == d)
(Snoc a b) == (Snoc c d)   = (a == c) && (b == d)
x == y                     = False

instance Text DG where
showsPrec p (Delta a b) s = s++"(delta "++show a++" "++show b++")"
showsPrec p (Gamma a) s = s++"(gamma "++show a++")"
showsPrec p Nilc s = s++"Nilc"
showsPrec p Nils s = s++"Nils"
showsPrec p (Integer i) s = s++(show i)
showsPrec p (Cons a b) s = s++"(Cons "++show a++" "++show b++")"
showsPrec p (Snoc a b) s = s++"(Snoc "++show a++" "++show b++")"

contract :: DG -> DG
contract (Delta Nilc x) = Cons x Nilc
contract (Delta (Cons a b) x) = Cons a (Delta b x)
contract (Delta x y) = Delta (contract x) y
contract (Gamma Nils) = Nilc
contract (Gamma (Snoc l x)) = Delta (Gamma l) x
contract (Gamma x) = Gamma (contract x)
contract (Cons (Integer i) y) = Cons (Integer i) (contract y)
contract (Cons x y) = Cons (contract x) y
contract Nilc = Nilc
contract Nils = Nils

expr :: DG
expr = Gamma (Snoc (Snoc Nils (Integer 6)) (Integer 5))

doit = (layy.(map show).tofix) (iterate contract expr)

tofix :: Eq a => [a] -> [a]
tofix [] = []
tofix [a] = [a]
tofix (a:b:cs) | a == b    = [a]
| otherwise = a:(tofix (b:cs))

layy :: [String] -> String
layy [] = ""
layy (x:xs) = x ++ "\n" ++ (lay xs)

Comments on my programming style are welcome.

Output is:

Gofer session for:
standard.prelude
dg
? doit
(gamma (Snoc (Snoc Nils 6) 5))
(delta (gamma (Snoc Nils 6)) 5)
(delta (delta (gamma Nils) 6) 5)
(delta (delta Nilc 6) 5)
(delta (Cons 6 Nilc) 5)
(Cons 6 (delta Nilc 5))
(Cons 6 (Cons 5 Nilc))

(856 reductions, 2391 cells)

John

Sun, 19 Nov 1995 08:08:36 GMT
On the fly generation of representations of function calls

Quote:

> >I am a fair novice with respect to the real world of functional programming
> >and I have a question. I don't know whether it is quite FAQ-ish, but here
> >it goes.

> >[]     data ConsList a = Nilc | Cons (a) (ConsList a)
> >[]     data SnocList a = Nils | Snoc (SnocList a) (a)
> >[]
> >[]     singlec x = Cons (x) (Nilc)
> >[]     singles x = Snoc (Nils) (x)
> >[]
> >[]     delta (Nilc) x = singlec x
> >[]     delta (Cons a b) x = Cons (a) (delta b x)
> >[]
> >[]     gamma (Nils) = Nilc
> >[]     gamma (Snoc l x) = delta (gamma l) x

> >       ["gamma (Snoc (Snoc (Nils) 6) 5)",
> >        "delta(gamma (Snoc (Nils) 6)) 5",
> >        "delta(delta(gamma Nils) 6) 5",
> >        "delta(delta(Nilc) 6) 5",
> >        "delta(Cons 6 (Nilc)) 5",
> >        "Cons (6) (delta Nilc 5)",
> >        "Cons (6) (Cons (5) (Nilc))"]

>   This is easy if you've studied functional languages for a while - you just
> need to simulate the language's reduction mechanism. I do this with a function
> called contract which searches for a redex and contracts it. The main program
> (called "doit") applies this to the initial expression repeatedly and prints
> the result out. This was written in Gofer:

> data DG = Delta DG DG | Gamma DG | Nilc | Nils | Integer Int | Cons DG DG |
>           Snoc DG DG

[interesting program deleted]

Quote:

>   Comments on my programming style are welcome.

John Farrell's solution is a very interesting one but I would like to
comment not so much on his programming style but on a simplification he
types:

data ConsList a = Nilc | Cons (a) (ConsList a)
data SnocList a = Nils | Snoc (SnocList a) (a)

data DG = Delta DG DG | Gamma DG | Nilc | Nils | Integer Int | Cons DG DG |
Snoc DG DG

which includes the constructors for both as well as new things.

To be strictly accurate, it would be necessary to 'unite' the two by

data DG' = Delta DG' DG' | Gamma DG' | ConsType ConsList | SnocType
SnocList |
Integer Int

but this then complicates the pattern matching. Nevertheless this kind on
union seems to crop up quite a lot in Haskell-like languages.

Tony Davie               Department of Mathematical and Computational
Sciences
Tel: +44 334 63257       St.Andrews University
Fax: +44 334 63278       North Haugh

Scotland
KY16 9SS

Sun, 19 Nov 1995 16:33:02 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages