{"id":525,"date":"2018-11-18T18:06:46","date_gmt":"2018-11-18T18:06:46","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=525"},"modified":"2018-11-20T08:36:56","modified_gmt":"2018-11-20T08:36:56","slug":"logic-and-%ce%bb-calculus","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/logic-and-%ce%bb-calculus\/","title":{"rendered":"Logic and\u00a0\u00a0\u03bb calculus"},"content":{"rendered":"

Let’s run through some simple Boolean expressions and their associated ASTs.<\/p>\n

(or #t #f)<\/strong> evaluates to #t.<\/strong><\/p>\n

\"\"

An AST with the or operator<\/p><\/div>\n

Similarly,\u00a0(not #t)<\/strong> is #f<\/strong>, which is fair, after all, something that’s not true has to be false. Play around with these in Racket to get a feel for them, as they can be arbitrarily complex.<\/p>\n

Here is the AST for\u00a0(or (and #t #f) (or #t #f))<\/strong><\/p>\n

\"\"

An AST with multiple levels of Boolean operators.<\/p><\/div>\n

Then we get:<\/p>\n

\"\"

The AST with the lowest level resolved<\/p><\/div>\n

 <\/p>\n

What happens if we pass numbers to these operators? In\u00a0\u03bb calculus and Racket,\u00a0all numbers are considered true<\/strong>. Note that this might be different from what you may be used to in other programming languages, for example, in some languages, -1 or 0 are considered false.<\/p>\n

Let’s run through some examples, they are written in Racket, but are the same in\u00a0\u03bb calculus.<\/p>\n

> (if 1 \"first\" \"second\")\r\n\"first\"\r\n> (or 1 0)\r\n1\r\n> (or 0 1)\r\n0\r\n> (or 31 #t)\r\n31\r\n> (or #t 31)\r\n#t\r\n<\/pre>\n
So what exactly is going on here? If all numbers are considered to be true, shouldn’t\u00a0or<\/strong>\u00a0return true? As far as it is concerned, it\u00a0is<\/strong> returning true, because it is returning a number, so now the question becomes how does it know which number to return? The rule for\u00a0or<\/strong> is that it returns the first TRUE value it can find, otherwise it returns FALSE. The fact that sometimes that first TRUE value is not a Boolean doesn’t matter,\u00a0or\u00a0<\/strong>will happily return whatever it is given.<\/p>\n
What about\u00a0and<\/strong>? It basically does the opposite of\u00a0or<\/strong> and returns the last TRUE value it can find, otherwise it returns FALSE. Look at these examples:<\/p>\n
> (and 3 -1)\r\n-1\r\n> (and -1 3)\r\n3\r\n> (and 1 #f)\r\n#f\r\n> (and #f 2)\r\n#f\r\n<\/pre>\n
This means that for\u00a0and\u00a0<\/strong>to return TRUE, it must test every value given to it, while for\u00a0or<\/strong> to return FALSE, it must evaluate everything.\u00a0 You might guess from the way we described these that operators such as\u00a0or\u00a0<\/strong>and\u00a0and<\/strong> can take any number of arguments, just like other prefix operators, and this is exactly true, and we can apply the exact same rules we did when there were two arguments.<\/p>\n
What about\u00a0and<\/strong>? It basically does the opposite of\u00a0or<\/strong> and returns the last TRUE value it can find, otherwise it returns FALSE. Look at these examples:<\/p>\n
> (and 1 2 3 4)\r\n4\r\n> (or 1 2 3 4)\r\n1\r\n> (not 1 2 3 4)\r\nnot: <\/strong>arity mismatch<\/pre>\n
Okay, so they don’t all take multiple arguments; specifically,\u00a0not<\/strong> is only defined for a single argument, and that’s fair enough, given that it simply inverts the truth of what it is given.<\/p>\n
We’ve seen strings floating around in some of these examples, typically as return values. However, with Functional Programming languages, whatever one function returns another one could take as a parameter, so we need to understand the implication of strings being passed to Boolean operators too. As with numbers, all strings are true, and the operators all work the same way.<\/p>\n
> (and \"hello\" \"goodbye\")\r\n\"goodbye\"\r\n> (or \"hello\" \"goodbye\")\r\n\"hello\"\r\n<\/pre>\n
In the next section we’ll look at how to use these conditionals in functions<\/a>.<\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Let’s run through some simple Boolean expressions and their associated ASTs. (or #t #f) evaluates to #t. Similarly,\u00a0(not #t) is #f, which is fair, after all, something that’s not true has to be false. Play around with these in Racket Continue Reading<\/a><\/span><\/p>\n","protected":false},"author":4,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-525","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/525","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/comments?post=525"}],"version-history":[{"count":5,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/525\/revisions"}],"predecessor-version":[{"id":538,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/525\/revisions\/538"}],"wp:attachment":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/media?parent=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}