ski-in-asm

ski-in-asm copied to clipboard

#+TITLE: SKI in asm An interpreter for extended SKI combinators (including C, B, S', C', B* plus for Z (zero) and U (succ) for church numerals). The comportment of each combinator and an algorithm to translate lambda calculus yo those combinators can be found [[https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf][here]]. This repository is inspired by [[https://crypto.stanford.edu/~blynn/lambda/sk.html][this]] blog post by Ben Lynn.

• How to use Each combinator is represented by a number from 0 to 9, any other number is an application. | Number | Combinator | |--------+------------| | 0 | S | | 1 | K | | 2 | U | | 3 | Z | | 4 | I | | 5 | B | | 6 | C | | 7 | S' | | 8 | B* | | 9 | C' | To create a program you need to lists, the stack which represents the program and the nodelist which is list of internal nodes (application). The nodelist consist of a list of pair of two values, they can be combinators or other internal nodes. An internal node is described by a number n superior to ten. It is the application of nodelist[n - 10] and nodelist[n - 9]. For instance, UZ can be compiled as: stack = [3, 2] (note, the stack list has to be in reverse order) and nodelist = [] or stack = [10] and nodelist = [2, 3]. To create a file with that does that you can use the script src/ski.sh. You can invoke it by giving it as an argument the name of a file which contains 2 lines, the stack and the nodelist. It will produce a binary called a.out that when executed is going to return a church numeral in the exit status (you can see it by using ~echo $?~ just after executing the program).