Back to Questions
1.2k
views6
comments
Problems with the code sample from Expert F#
f#book

Hi!

I'm trying to build a code sample from "Expert F#" (Don Syme). It's in the chapter 12,
in the section "Representing Propositional Formulae Efficiently Using BDDs". I can't compile it.

At first, I thought that I have missed something from the previous listings, and I was right because it requires types from "Representing Propositional Logic" (one of the previous sections). After I've added those types some errors disappeared, but not all.

It still gives me a bunch of errors: FS0039 "The value or constructor 'x' is not defined", and the same for other 6 variables. I thought that it's my bad and downloaded this sample from official book site: [link:www.expert-fsharp.com]. But I still have the same errors... I have looked through errata, but there is nothing simular there.

I don't want to post this code here because it's rather big and you can download it easily (link is here, it takes 20 sec) and see where are this errors. Please help me to solve this problem. I'm interested in BDDs and really want to see this code working.

.

Hi,There's two issues, one which is due to changes in the CTP version (which came out after the book):

1
2

let stringOfEnv env = 
    Map.fold_right(fun k v acc -> sprintf "%s=%s;" k (stringOfBit v)+acc) env ""

Change fold by fold_right (actually I don't reallly know that this is correct, but the types match :)The second issue confused me a bit, here's the correct code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Construct the BDD for a conjunction "m1 AND m2"
    let rec mkAnd(m1,m2) = 
        if m1 = falseIdx or m2 = falseIdx then falseIdx
        elif m1 = trueIdx then m2 elif m2 = trueIdx then m1
        else
            let (Node(x,l1,r1)) = idxToNode(m1)
            let (Node(y,l2,r2)) = idxToNode(m2)
            let v,(la,lb),(ra,rb) = 
                match order x y with 
                | c when c = 0 -> x,(l1,l2),(r1,r2)
                | c when c < 0 -> x,(l1,m2),(r1,m2)
                | c            -> y,(m1,l2),(m1,r2)
            mkNode(v,mkAnd(la,lb), mkAnd(ra,rb))

Note the extra parens in the two let (Node(...)) bindings in the else branch.Without these parens, F# did not recognize the x, l1,r1 etc variables, although it doesn't complain about the let bindings itself. So, can anyone answer, what is the meaning of the let bindings in the original code without the parens?

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// Construct the BDD for a conjunction "m1 AND m2"
    let rec mkAnd(m1,m2) = 
        if m1 = falseIdx or m2 = falseIdx then falseIdx
        elif m1 = trueIdx then m2 elif m2 = trueIdx then m1
        else
            let Node(x,l1,r1) = idxToNode(m1) //no errors here, but x,l1,r1 are not defined?
            let Node(y,l2,r2) = idxToNode(m2)
            let v,(la,lb),(ra,rb) = 
                match order x y with //compile errors here because x,y,l1 etc are not known
                | c when c = 0 -> x,(l1,l2),(r1,r2)
                | c when c < 0 -> x,(l1,m2),(r1,m2)
                | c            -> y,(m1,l2),(m1,r2)
            mkNode(v,mkAnd(la,lb), mkAnd(ra,rb))
By on 4/22/2009 11:22 PM ()

Thank you very much, Kurt! It works, and everything is all right. This book is one of the greatest books I have ever read about programming, and it is very distracting to see such errors in the code samples. I hope they will add this to errata...

By on 4/23/2009 9:49 AM ()

Hi there,

Thanks for the kind words about the book. We'll be sure to add the case above to the errata on our next update. Please also let us know if you spot any other ways the book can be improved!

Kind regards

don

By on 4/23/2009 3:05 PM ()

let Node(x,l,r) = blah()

defines a new function named 'Node' that takes three arguments and has blah() as a body.

let (Node(x,l,r)) = blah()

calls blah() right now, and binds the result to the pattern Node(x,l,r), resulting in three new bindings (for x, l, & r) in the current scope.

By on 4/23/2009 5:41 AM ()

    let Node(x,l,r) = blah()

defines a new function named 'Node' that takes three arguments and has blah() as a body.

    let (Node(x,l,r)) = blah()

calls blah() right now, and binds the result to the pattern Node(x,l,r), resulting in three new bindings (for x, l, & r) in the current scope.

Ah - of course.This is a historical question, but how did the pre-CTP compiler distinguish the two cases? Or ws it really an error?

By on 4/24/2009 12:21 AM ()

The early version of F# did a name resolution of the name "Node" and decided between a function or patten based on this. This rule allowed OCaml compatibility here, but the rule also has problems: it makes code fragile if you introduce new union types or active patterns. As it is also possible to just parenthesize the pattern we deprecated the rule in April 2008.

Kind regards

don

By on 4/24/2009 1:24 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper