{"id":319,"date":"2018-11-04T11:59:10","date_gmt":"2018-11-04T11:59:10","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=319"},"modified":"2018-11-04T12:08:44","modified_gmt":"2018-11-04T12:08:44","slug":"evaluating-expression","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/evaluating-expression\/","title":{"rendered":"Evaluating Expressions"},"content":{"rendered":"

We’ve seen how Functional Programs can have arbitrarily long lists of operands<\/a> passed to most operators and we’ve also looked at how we can manipulate lists<\/a>. This section will look at how we these together to see how to evaluate these expressions.<\/p>\n

Let’s take this expression:\u00a0(- 10 3 2 1)<\/strong><\/p>\n

The algorithm for evaluating is:<\/p>\n

\r\n\r\nGet the car and cdr\r\n\r\nSubtract the car of the cdr from the car\r\n\r\nSet the head equal to the answer\r\n\r\nRepeat while there is something in the tail\r\n\r\n<\/pre>\n
This might look a little confusing at first, but remember how important it is to be able to design code in which we have very simple functions that are executed many times. Here’s what would happen when we run this algorithm:<\/p>\n
\r\n\r\nGet the car and cdr [That is, 10 and (3 2 1)]\r\n\r\nSubtract the car of the cdr from the car [That is, subtract 3 from 10 to give 7]\r\n\r\nSet the head equal to the answer [This gives us (- 7 2 1)]\r\n\r\nRepeat while there is something in the tail [Go back to the start and repeat!]\r\n\r\n<\/pre>\n
What happens is that the list will get progressively smaller until there is nothing left except our answer. Here is each step laid out:<\/p>\n
\r\n\r\nExpression\u00a0 \u00a0 \u00a0 car\u00a0 \u00a0 \u00a0 cdr\u00a0 \u00a0 \u00a0car(cdr)\r\n\r\n(-10 3 2 1)\u00a0 \u00a0 \u00a0 \u00a010\u00a0 \u00a0 (3 2 1)\u00a0 \u00a0 \u00a0 3\r\n\r\n(- 7 2 1)\u00a0 \u00a0 \u00a0 \u00a0 7\u00a0 \u00a0 \u00a0 \u00a0 (2 1)\u00a0 \u00a0 \u00a0 2\r\n\r\n (- 5 1)\u00a0 \u00a0 \u00a0 \u00a0 5\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0(1)\u00a0 \u00a0 \u00a0 1\r\n\r\n<\/pre>\n
So we do the\u00a0same<\/strong> thing multiple times, and only ever have to subtract two items. What’s very nice about this is we can use the same algorithm no matter what the operator is; the only difference is the operation we carry out in Step #5 above. For example, if we have\u00a0(\/ 20 5 4 2)<\/strong>, then the only difference is that each time we need to do the calculation we carry out a division.<\/p>\n
\r\nExpression\u00a0 \u00a0 \u00a0 car\u00a0 \u00a0 \u00a0 cdr\u00a0 \u00a0 \u00a0car(cdr)\r\n\r\n(\/ 20 5 4 2)\u00a0 \u00a0 \u00a0 \u00a020\u00a0 \u00a0 (5 4 2)\u00a0 \u00a0 \u00a0 5\r\n\r\n  (\/ 4 4 2)\u00a0 \u00a0 \u00a0 \u00a0  4\u00a0 \u00a0 \u00a0 (4 2)\u00a0 \u00a0 \u00a0 4\r\n\r\n    (\/ 1 2)\u00a0 \u00a0 \u00a0 \u00a0 1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0(2)\u00a0 \u00a0 \u00a0 2\r\n\r\n<\/pre>\n
And our final answer is …<\/p>\n\\(\\frac{1}{2}\\)\n
yes, often in Functional Programming we prefer to use fractions, as they give better precision than decimals.<\/p>\n
What does this mean for ASTs? It means that they are\u00a0smaller<\/strong>, because now we can have fewer operators. Our general form is now:<\/p>\n
\"\"
General form of an AST<\/p><\/div>\n
We can have multiple operands attached to a single operator, like here:<\/p>\n
\"\"
Example AST with three operands<\/p><\/div>\n
We’re still missing something, though, and that’s the ability to use variables. Remember this guy?<\/p>\n\\(\\frac{-b \\pm \\sqrt{b^2-4ac\\;\\;}}{2a}\\)\n
What makes it useful is that although it always does the same thing, the specific way it behaves differs depending on the suer input. Let’s say we had this simple AST:<\/p>\n
\"\"
A simple AST with one variable.<\/p><\/div>\n
How do we tell it what value we want that AST to have? The answer, my friends, lies in the magic of Lambda Calculus!!<\/p>\n","protected":false},"excerpt":{"rendered":"
We’ve seen how Functional Programs can have arbitrarily long lists of operands passed to most operators and we’ve also looked at how we can manipulate lists. This section will look at how we these together to see how to evaluate 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-319","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/319","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=319"}],"version-history":[{"count":12,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/319\/revisions"}],"predecessor-version":[{"id":335,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/319\/revisions\/335"}],"wp:attachment":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/media?parent=319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}