feldmark@hanako.stars.flab.Fujitsu.JUNET (08/09/88)
I have been reading about miranda and am trying to understand a simple program given in the article "An Overview of Miranda" from SIGPLAN Notices, December 1986. It should be easy for anyone who has actually programmed in miranda and I'm wondering if someone would mind giving me a hand. The problem is: answer = twice twice twice suc 0 twice f x = f (f x) suc x = x + 1 I'm trying to apply partial paramaterization at each step and get an exact picture of what's going on as far as the execution mechanism is concerned, but keep coming up with weird results. I think the parenthesis are confusing me. I am assuming that functions inside parenthesis should be applied to arguments and then parenthesis removed. I know I am doing something simple fundamentally wrong but can't figure it out. Has anyone looked at this before? Thanks. Mark Feldman Fujitsu Laboratories Ltd. Kawasaki, Japan feldmark@hanako.stars.flab.fujitsu.junet (Japan) feldmark%hanako.stars.flab.fujitsu.junet@uunet.uu.net (USA) -- feldmark@hanako.stars.flab.fujitsu.junet (Japan) feldmark%hanako.stars.flab.fujitsu.junet@uunet.uu.net (USA)
rej@eagle.ukc.ac.uk (R.E.Jones) (08/10/88)
In article <FELDMARK.88Aug9114727@hanako.stars.flab.Fujitsu.JUNET> feldmark@hanako.stars.flab.Fujitsu.JUNET writes: > >I have been reading about miranda and am trying to understand a simple >program given in the article "An Overview of Miranda" from SIGPLAN >Notices, December 1986. > >answer = twice twice twice suc 0 >twice f x = f (f x) >suc x = x + 1 > >I'm trying to apply partial paramaterization at each step and get an >exact picture of what's going on as far as the execution mechanism is >concerned, but keep coming up with weird results. I think the >parenthesis are confusing me. I am assuming that functions inside >parenthesis should be applied to arguments and then parenthesis >removed. I don't think your model of evaluation helps. You must remember that Miranda uses lazy evaluation - arguments will not be evaluated unless they are needed. Thus if const a b = a then const 3 (reverse [1..]) evaluates to 3. Note: [1..] is the list of all natural numbers. This expression terminates precisely because the second argument to const is not needed, and so (reverse [1..]) is not evaluated. I suspect that your problem does indeed lie with the brackets. You need to remember that Miranda functions are curried: they take just ONE argument. Thus f a b = (f a) b Notice the difference between this and the definition of twice. Anyway, the evaluation proceeds as follows. We'll use with simpler examples. I'll try not to play too fast and loose with the brackets :-). [ => means 'evaluates to', == means 'is the same as'.] twice suc 0 => suc (suc 0) => (suc 0) + 1 => (0 + 1) + 1 => 2 twice twice suc 0 == (twice twice suc) 0 => twice (twice suc) 0 => (twice suc) (twice suc 0) == twice suc (twice suc 0) => suc (suc (twice suc 0)) => (suc (twice suc 0)) + 1 => ((twice suc 0) + 1) + 1 => ... => 4 ...and similarly, answer => ... => 16 (eventually!).
caldwell@akhenaten.steinmetz.ge.com (James Caldwell) (08/10/88)
twice f x = f (f x)
s x = x + 1
answer = twice twice twice s 0
= twice (twice twice) s 0
= twice twice (twice twice s) 0
= twice (twice (twice twice s)) 0
= twice (twice twice s)((twice (twice twice s)) 0)
= (twice twice s)((twice twice s))((twice (twice twice s)) 0)
= twice (twice s)((twice twice s))((twice (twice twice s)) 0)
= (twice s)((twice s)((twice twice s)))((twice (twice twice s)) 0)
= s (s ((twice s)((twice twice s))))((twice (twice twice s)) 0)
= s ((twice s)((twice twice s)))((twice (twice twice s)) 0) + 1
= ((twice s)((twice twice s)))((twice (twice twice s)) 0) + 1 + 1
= s (s (((twice twice s))))((twice (twice twice s)) 0) + 1 + 1
= s (((twice twice s)))((twice (twice twice s)) 0) + 1 + 1 + 1
= (twice twice s)((twice (twice twice s)) 0) + 1 + 1 + 1 + 1
= twice (twice s)((twice (twice twice s)) 0) + 1 + 1 + 1 + 1
= (twice s)((twice s)((twice (twice twice s)) 0)) + 1 + 1 + 1 + 1
= (s (s((twice s)((twice (twice twice s)) 0)))) + 1 + 1 + 1 + 1
= (s((twice s)((twice (twice twice s)) 0))) + 1 + 1 + 1 + 1 + 1
= ((twice s)((twice (twice twice s)) 0))) + 1 + 1 + 1 + 1 + 1 + 1
= (s (s (((twice (twice twice s)) 0)))) + 1 + 1 + 1 + 1 + 1 + 1
= (s (((twice (twice twice s)) 0))) + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice (twice twice s)) 0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice twice s) ((twice twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice (twice s)) ((twice twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice s) ((twice s) ((twice twice s) 0))) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s (s ((twice s) ((twice twice s) 0)))) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s ((twice s) ((twice twice s) 0))) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice s) ((twice twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s (s ((twice twice s) 0))) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s ((twice twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice twice s) 0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice (twice s)) 0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice s) ((twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s (s ((twice s) 0))) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s ((twice s) 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= ((twice s) 0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s (s 0)) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= (s 0) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 0 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 6 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 7 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 8 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 9 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 10 + 1 + 1 + 1 + 1 + 1 + 1
= 11 + 1 + 1 + 1 + 1 + 1
= 12 + 1 + 1 + 1 + 1
= 13 + 1 + 1 + 1
= 14 + 1 + 1
= 15 + 1
= 16
--
Jim Caldwell caldwell%akhenaten@steinmetz.UUCP
uunet!steinmetz!akhenaten!caldwellwillc@tekcrl.TEK.COM (Will Clinger) (08/11/88)
I've never programmed in Miranda, but the standard practice in functional
languages is to associate to the left. Thus I believe the Miranda program
answer = twice twice twice suc 0
twice f x = f (f x)
suc x = x + 1
would be written in Scheme as
(define twice
(lambda (f)
(lambda (x)
(f (f x)))))
(define suc
(lambda (x)
(+ x 1)))
(define answer
((twice
(twice
(twice suc)))
0))
and so the answer is 8.
William Clinger
Semantic Microsystems, Inc.stevev@tekchips.CRL.TEK.COM (Steve Vegdahl;6010;50-662;LP=A;) (08/11/88)
In article <2921@tekcrl.CRL.TEK.COM> willc@tekchips.CRL.TEK.COM (Will Clinger) writes: >I've never programmed in Miranda, but the standard practice in functional >languages is to associate to the left. Thus I believe the Miranda program > > answer = twice twice twice suc 0 > twice f x = f (f x) > suc x = x + 1 > >would be written in Scheme as > > (define twice > (lambda (f) > (lambda (x) > (f (f x))))) > > (define suc > (lambda (x) > (+ x 1))) > > (define answer > ((twice > (twice > (twice suc))) > 0)) > >and so the answer is 8. Will is correct that application associates to the left, but his transformation to Scheme code does not reflect that, in that the definition of "answer" associates the applications of "twice" to the right. The definition of "answer" should be: (define answer ((((twice twice) twice) suc) 0)) yielding the value 16. Steve Vegdahl Computer Research Lab Tektronix Labs Beaverton, Oregon