{"id":2973,"date":"2021-10-28T18:04:48","date_gmt":"2021-10-29T02:04:48","guid":{"rendered":"https:\/\/wonghoi.humgar.com\/blog\/?p=2973"},"modified":"2025-11-30T22:56:03","modified_gmt":"2025-12-01T06:56:03","slug":"reading-lambda-calculus","status":"publish","type":"post","link":"https:\/\/wonghoi.humgar.com\/blog\/2021\/10\/28\/reading-lambda-calculus\/","title":{"rendered":"Reading Lambda Calculus"},"content":{"rendered":"\n<p><\/p>\n\n\n\n<p>Complex expressions in lambda calculus notation <a href=\"http:\/\/cs.rpi.edu\/academics\/courses\/spring11\/proglang\/handouts\/lambda-calculus-chapter.pdf\">here<\/a> is hard to parse in the head correctly until the day I started using Dart Language and noticed the <a href=\"https:\/\/wonghoi.humgar.com\/blog\/2021\/10\/28\/using-darts-c-style-syntax-to-make-chain-of-lambda-functions-concrete\/\" data-type=\"post\" data-id=\"2951\">connection <\/a>between <code>=&gt;<\/code> lambda notation and C-style function layout. Here&#8217;s what I learned:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The expressions are right-associative because the right-most expression is the deepest nested function<\/li>\n\n\n\n<li>Function application (feeding values to the arguments) always starts from left-to-right because you can only gain entry to a nest of functions starting from the outermost level, peeling it layer by later like an onion. So if applying <em>arg <\/em>to <em>statement <\/em>is denoted by (<em>statement arg<\/em>), the order of input would be (((<em>statement arg1<\/em>) <em>arg2<\/em>) <em>arg3<\/em>)<\/li>\n\n\n\n<li>Names showing up on the parameter list of the nearest layer sticks to it (local to the function) and excludes everybody else (variable shadowing): this means the same name have absolutely no bearing as a free variable or being a free variable anywhere, so you can (and should) replace it with a unique name. <\/li>\n<\/ul>\n\n\n\n<p>Here&#8217;s the calculus syntax in the book:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"497\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-11-1024x497.png\" alt=\"\" class=\"wp-image-2955\" srcset=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-11-1024x497.png 1024w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-11-300x146.png 300w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-11-768x373.png 768w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-11.png 1186w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>This example is the function application used above<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"493\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-12-1024x493.png\" alt=\"\" class=\"wp-image-2956\" srcset=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-12-1024x493.png 1024w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-12-300x144.png 300w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-12-768x370.png 768w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-12.png 1207w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity is-style-wide\"\/>\n\n\n\n<p>Here&#8217;s where reusing the variable <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-7e5fbfa0bbbd9f3051cd156a0f1b5e31_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> in multiple places to mean different things gets confusing as hell, and the author (as well as the nomenclature) do not emphasize the equivalence to variable shadowing rules:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"498\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-13-1024x498.png\" alt=\"\" class=\"wp-image-2957\" srcset=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-13-1024x498.png 1024w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-13-300x146.png 300w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-13-768x373.png 768w, https:\/\/wonghoi.humgar.com\/blog\/wp-content\/uploads\/2021\/10\/image-13.png 1206w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>This can be rewritten as having<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-d52885084e5b30568dac47ae0114d0a2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#119;&#32;&#46;&#32;&#119;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"49\" style=\"vertical-align: 0px;\"\/><\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-a69afcc893b90ae7b4eb801a86c8d6c4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#122;&#32;&#46;&#32;&#40;&#122;&#43;&#49;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -5px;\"\/><\/li>\n\n\n\n<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-41fa86f4289f6f77fe102ea65671a75a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#102;&#32;&#46;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#103;&#32;&#46;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#102;&#32;&#40;&#103;&#32;&#120;&#41;&#32;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"131\" style=\"vertical-align: -5px;\"\/><\/li>\n<\/ul>\n\n\n\n<p>Upon application,<\/p>\n\n\n\n<p class=\"has-text-align-center\"><span style=\"font-size: revert;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-c7aa15fe593872d3b584bf0e921f8392_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#40;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#102;&#32;&#46;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#103;&#32;&#46;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#102;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#40;&#103;&#32;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#120;&#41;&#32;&#41;&#32;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#119;&#32;&#46;&#32;&#119;&#94;&#50;&#41;&#32;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#122;&#32;&#46;&#32;&#40;&#122;&#43;&#49;&#41;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"391\" style=\"vertical-align: -5px;\"\/><\/span><\/p>\n\n\n\n<p class=\"has-text-align-center\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-bf09d08a45eee4a1e612e5298734351d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#109;&#112;&#108;&#105;&#101;&#115;&#32;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#103;&#32;&#46;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#119;&#32;&#46;&#32;&#119;&#94;&#50;&#32;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#40;&#103;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#120;&#41;&#32;&#41;&#32;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#122;&#32;&#46;&#32;&#40;&#122;&#43;&#49;&#41;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"364\" style=\"vertical-align: -5px;\"\/><\/p>\n\n\n\n<p class=\"has-text-align-center\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-42d8487963049a386f14085d6ef667f1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#109;&#112;&#108;&#105;&#101;&#115;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#119;&#32;&#46;&#32;&#119;&#94;&#50;&#32;&#92;&#113;&#113;&#117;&#97;&#100;&#32;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#122;&#32;&#46;&#32;&#40;&#122;&#43;&#49;&#41;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#120;&#41;&#32;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"281\" style=\"vertical-align: -5px;\"\/><\/p>\n\n\n\n<p>which clearly reads for an input of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-7e5fbfa0bbbd9f3051cd156a0f1b5e31_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/>, it&#8217;ll be incremented first then squared. Resolving further:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-d4fb0e4431ab854767734c6e0d9e3a65_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#109;&#112;&#108;&#105;&#101;&#115;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#119;&#32;&#46;&#32;&#119;&#94;&#50;&#32;&#92;&#113;&#117;&#97;&#100;&#32;&#40;&#120;&#43;&#49;&#41;&#32;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"198\" style=\"vertical-align: -5px;\"\/><\/p>\n\n\n\n<p class=\"has-text-align-center\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-4a09c4c67ff8f7cc52dc384db414921d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#105;&#109;&#112;&#108;&#105;&#101;&#115;&#32;&#92;&#108;&#97;&#109;&#98;&#100;&#97;&#32;&#120;&#46;&#40;&#120;&#43;&#49;&#41;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"125\" style=\"vertical-align: -5px;\"\/><\/p>\n\n\n\n<p>The evils of <a href=\"https:\/\/wonghoi.humgar.com\/blog\/2021\/10\/28\/using-darts-c-style-syntax-to-make-chain-of-lambda-functions-concrete\/\" data-type=\"post\" data-id=\"2951\">variable shadowing<\/a> again! Not only it makes the code hard to read and reason, it also make the mathematics hard to follow!<\/p>\n<div class=\"pvc_clear\"><\/div><p id=\"pvc_stats_2973\" class=\"pvc_stats all  \" data-element-id=\"2973\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg aria-hidden=\"true\" focusable=\"false\" data-prefix=\"far\" data-icon=\"chart-bar\" role=\"img\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 512 512\" class=\"svg-inline--fa fa-chart-bar fa-w-16 fa-2x\"><path fill=\"currentColor\" d=\"M396.8 352h22.4c6.4 0 12.8-6.4 12.8-12.8V108.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v230.4c0 6.4 6.4 12.8 12.8 12.8zm-192 0h22.4c6.4 0 12.8-6.4 12.8-12.8V140.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v198.4c0 6.4 6.4 12.8 12.8 12.8zm96 0h22.4c6.4 0 12.8-6.4 12.8-12.8V204.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v134.4c0 6.4 6.4 12.8 12.8 12.8zM496 400H48V80c0-8.84-7.16-16-16-16H16C7.16 64 0 71.16 0 80v336c0 17.67 14.33 32 32 32h464c8.84 0 16-7.16 16-16v-16c0-8.84-7.16-16-16-16zm-387.2-48h22.4c6.4 0 12.8-6.4 12.8-12.8v-70.4c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v70.4c0 6.4 6.4 12.8 12.8 12.8z\" class=\"\"><\/path><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p><div class=\"pvc_clear\"><\/div>","protected":false},"excerpt":{"rendered":"<p>Complex expressions in lambda calculus notation here is hard to parse in the head correctly until the day I started using Dart Language and noticed the connection between =&gt; lambda notation and C-style function layout. Here&#8217;s what I learned: Here&#8217;s &hellip; <a href=\"https:\/\/wonghoi.humgar.com\/blog\/2021\/10\/28\/reading-lambda-calculus\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n<div class=\"pvc_clear\"><\/div>\n<p id=\"pvc_stats_2973\" class=\"pvc_stats all  \" data-element-id=\"2973\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg aria-hidden=\"true\" focusable=\"false\" data-prefix=\"far\" data-icon=\"chart-bar\" role=\"img\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" viewBox=\"0 0 512 512\" class=\"svg-inline--fa fa-chart-bar fa-w-16 fa-2x\"><path fill=\"currentColor\" d=\"M396.8 352h22.4c6.4 0 12.8-6.4 12.8-12.8V108.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v230.4c0 6.4 6.4 12.8 12.8 12.8zm-192 0h22.4c6.4 0 12.8-6.4 12.8-12.8V140.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v198.4c0 6.4 6.4 12.8 12.8 12.8zm96 0h22.4c6.4 0 12.8-6.4 12.8-12.8V204.8c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v134.4c0 6.4 6.4 12.8 12.8 12.8zM496 400H48V80c0-8.84-7.16-16-16-16H16C7.16 64 0 71.16 0 80v336c0 17.67 14.33 32 32 32h464c8.84 0 16-7.16 16-16v-16c0-8.84-7.16-16-16-16zm-387.2-48h22.4c6.4 0 12.8-6.4 12.8-12.8v-70.4c0-6.4-6.4-12.8-12.8-12.8h-22.4c-6.4 0-12.8 6.4-12.8 12.8v70.4c0 6.4 6.4 12.8 12.8 12.8z\" class=\"\"><\/path><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p>\n<div class=\"pvc_clear\"><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[61,63],"tags":[],"class_list":["post-2973","post","type-post","status-publish","format-standard","hentry","category-functional-programming","category-programming-languages"],"_links":{"self":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/2973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/comments?post=2973"}],"version-history":[{"count":6,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/2973\/revisions"}],"predecessor-version":[{"id":6619,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/posts\/2973\/revisions\/6619"}],"wp:attachment":[{"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/media?parent=2973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/categories?post=2973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wonghoi.humgar.com\/blog\/wp-json\/wp\/v2\/tags?post=2973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}