Ticket #148 (closed defect: invalid)

Opened 5 years ago

Last modified 5 years ago

DDC fails the man or boy test.

Reported by: erikd Owned by: erikd
Priority: blocker Milestone: 0.1.3
Component: Unknown Version: 0.1.2
Keywords: Cc:

Description

The test was proposed by Donald Knuth:

http://rosettacode.org/wiki/Man_or_boy_test

DDC currently fails. My disciple version of the program below:

a :: Int -> a -> a -> a -> a -> a -> Int
a k x1 x2 x3 x4 x5
 = do	b () = do { k := k - 1 ; a k b x1 x2 x3 x4 }
	if k <= 0 then x4 () + x5 () else b ()

fn n = \() -> n

main ()	-- Function 'a' should return -67
 = do	out = a 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)
 	if out /= -67
	 then println $ "Output was " % show out % ". Should have been -67."
	 else println "Passed!"

Change History

Changed 5 years ago by erikd

  • owner set to erikd
  • status changed from new to assigned

Test is T148-ManOrBoy?.

Changed 5 years ago by erikd

I think the problem here is a lack of differentiation between pass-by-value and pass-by-reference semantics. Or rather, it seems that disciple is pass-by-reference by default and if the value is not mutated inside the function, then it behaves like pass-by-value.

Consider an Ocaml version of the same function (known to be correct):

let rec a k x1 x2 x3 x4 x5 =
    let m = ref k in
    let rec b () =
        decr m ;
        a !m b x1 x2 x3 x4
    in
    if k <= 0 then x4 () + x5 ()
    else b ()

Here, the parameter k passed to function a is an int. From this value, a mutable copy is made called m. In the inner function b, m is decremented and then passed by value (!m dereferences m to get the int value) before being passed into function a again.

In the disciple version:

a :: Int -> a -> a -> a -> a -> a -> Int
a k x1 x2 x3 x4 x5
 = do   b () = do { k := k - 1 ; a k b x1 x2 x3 x4 }
        if k <= 0 then x4 () + x5 () else b ()

we don't need to use a reference because we have mutable values. However, in function b, after we mutate the value k, does k get passed into function a as a reference or as a value?

By contrast, the javascript version:

function A(k,x1,x2,x3,x4,x5) {
   var B = function() { return A(--k, B, x1, x2, x3, x4) }
   return k<=0 ? x4()+x5() : B()
}
function K(n) {
  return function() { return n }
}
alert( A(10, K(1), K(-1), K(-1), K(1), K(0) ) )

allows mutation of the value passed into the function, but when it in turn passes it in the next call, uses pass-by-value semantics.

Changed 5 years ago by erikd

  • status changed from assigned to closed
  • resolution set to invalid

With pass-by-reference semantics, mutable variables and recursion, we need to make a copy of the value we're mutating.

Two correct solutions to this problem follow:

a0 :: Int -> a -> a -> a -> a -> a -> Int
a0 k x1 x2 x3 x4 x5
 = do	b () = do { k := k - 1 ; a0 (copy k) b x1 x2 x3 x4 }
	if k <= 0 then x4 () + x5 () else b ()
a1 :: Int -> a -> a -> a -> a -> a -> Int
a1 k x1 x2 x3 x4 x5
 = do	m = copy k
	b () = do { m := m - 1 ; a1 m b x1 x2 x3 x4 }
	if k <= 0 then x4 () + x5 () else b ()

I'll close this bug as invalid and add this to the test suite.

Note: See TracTickets for help on using tickets.