Hacker News new | past | comments | ask | show | jobs | submit login

To be even more minimal, you can get rid of custom definitions, and encode everything as calls to the following two functions:

    k =
      -> x {
        -> y {
          x
        }
      }

    s =
      -> x {
        -> y {
          -> z {
            x[z][y[z]]
          }
        }
      }
For example, 'k[x][y]' returns 'x', so

    TRUE = k
FALSE is a little trickier, so we'll need to calculate its implementation based on the definition. It can't be 'k' (since that behaves like 'TRUE'), and 's' requires three arguments rather than two. Let's assume it's 'S[A]' for some argument 'A':

    Let FALSE[x][y] = s[A][x][y]
                    = A[y][x[y]]
We need to find a value for 'A', such that 'A[y][x[y]]' returns 'y'. We can use 'k', hence 'FALSE' can be implemented as 's[k]':

    FALSE[x][y] = s[k][x][y]
                = k[y][x[y]]
                = y
We can follow a similar procedure for the other sections of this article (numbers, lists, etc.)

https://en.wikipedia.org/wiki/SKI_combinator_calculus

Note that there are alternative systems with only one definition, like https://news.ycombinator.com/item?id=31473127 , but those single definitions are quite complex, compared to s and k.




FYI there’s an (explicitly interpreted, not proc-encoded) implementation of this in https://computationbook.com, including compilation from lambda calculus: https://github.com/tomstuart/computationbook/tree/master/uni...

And also, as you imply, iota: https://github.com/tomstuart/computationbook/tree/master/uni...




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: