2d:null 2e:["$","title",null,{"children":"Functional Blockchain | Lance Galletti | Observable"}] 33:T605,md` We want our CLI to be easily extendable to include new functions and improvements of old functions. We thus implement our CLI as follows: ${html ``} Our blockchain works as such: 1. define miners/users 2. make transactions (valid or otherwise) 3. write/execute smart contract 4.a. decide who will mine the next block 4.b. mine the above (which executes the transactions and code) 5. view the balance of users 6. view the blockchain and/or repeat from 1/2 User input is treated as a linear stream and hence our CLI is very memory efficient and guarantees not to leak any user input once the CLI terminates. You can read more about linear streams [here](http://ats-lang.github.io/DOCUMENT/INT2PROGINATS/HTML/INT2PROGINATS-BOOK-onechunk.html#programming-with-linear-views-and-types). Walking through the code we see the bulk of the work is done in the **read_loop** function. If the input's first word is "exit" then we call **cli_stop()** and free from memory the resource that is the stream of input. Otherwise, we call **cli_do()** followed by a recursive call to **read_loop()**. The **cli_do()** function is deliberately simple - we want adding functionalities to be as easy as possible. Each of these do functions (in do.dats) is expected to either write locally or send a message to a peer. `34:T7b3,md` Without worrying about the validity of transactions, mining is simply finding the nonce that makes the hash of the header valid. Notice that we encode the header into a string before hashing it. Although we omit its implementation here, the encoder should, for consistency, be the same regardless of the miner. ${html ``} Notice that we filter out the invalid transactions using **list0_filter** before recursively mining the block. The **is_valid_transact()** function has the intended side effect of executing the transactions as it validates them. This is necessary for the following scenario: User A has 2 dollars and makes two transactions: 1. A sends 1 dollar to B 2. A sends 2 dollars to C Each transaction is valid but both transactions cannot be executed together - otherwise A's account would have a negative balance. The side effect of **is_valid_transact()** allows for transaction 2 to be invalidated once transaction 1 has been executed. We can easily modify the order in which these transactions are executed to minimize or maximize a desired quantity. For example, a miner can decide to minimize the number of invalid transactions, or maximize the total amount transferred, or even maximize the sum of the fees of the transactions. The [tail-recursive](http://ats-lang.github.io/DOCUMENT/INT2PROGINATS/HTML/INT2PROGINATS-BOOK-onechunk.html#tail-call-and-tail-recursion) implementation of **mine()** is inline with the memory efficiency of the CLI. Also, notice that the target hash that miners aim to meet is, here, a hash starting with 4 zeros but is easily adjustable. Finally, we again utilize ATS-C co-programming in the **get_time()** function which returns the timestamp at which the block was mined. `35:Td69,md` To facilitate parsing of our language we have decided to give it the following lisp-like syntax: **Integers** ${html`1 is represented as (TMint 1), 2 as (TMint 2) ...etc.`} **Bool** ${html`True is (TMint 1) and False is (TMint 0)`} **String** ${html`"hello, world!" is defined as (TMstr hello, world!)`} **Variable** ${html`a variable x is declared as (TMvar x)`} **Tuples** ${html`a tuple (t0, t1, t2) for example is defined as (TMtup t0 t1 t2)`} **Operations** 2 + 3 + 4 is defined as ${html`(TMopr + (TMint 2) (TMint 3) (TMint 4))`} **Lambda Function** ${tex` \lambda x.x + x`} can be defined as ${html`(TMlam x (TMopr + (TMvar x) (TMvar x))) `} **Function application** Applying the above lambda function to 1 can be done as such: ${html`(TMapp (TMlam x (TMopr + (TMvar x) (TMvar x))) (TMint 1))`} **Fixed Point** the fibonacci function can be written as ${html` (TMfix f x (TMifnz (TMvar x) (TMifnz (TMopr - (TMvar x) (TMint 1)) (TMopr + (TMapp (TMvar f) (TMopr - (TMvar x) (TMint 1))) (TMapp (TMvar f) (TMopr - (TMvar x) (TMint 2))) ) (TMint 1)) (TMint 0)) ) `} **Sequential operations** let val () = println!("hello, world!") in add(2, 3) end can be encoded as ${html` (TMseq (TMopr println (TMstr hello, world!)) (TMapp (TMapp (TMlam y (TMlam x (TMopr + (TMvar x) (TMvar y)) ) ) (TMint 2)) (TMint 3)) ) `} `36:T5c7,md` As you can see, this language is not fit for encoding complex functions - although it is possible because of turing completeness. It is hence discouraged to write directly in this language and instead we recommend generating lambda code from ATS. This allows for extending the lambda language to allow for more succinct verbosity, in addition to which one can utilize the typechecker and compiler of ATS for static syntactic debugging. For example, here are a few functions we can use to overload symbols and make our syntax more practical ${html ``} In ATS, we can now write ${html `TMint(1) + TMint(1)`} Instead of ${html `TMopr("+", TMint(1), TMint(1))`} When generating our pure lambda code, both, of course, translate to the same ${html `(TMopr + (TMint 1) (TMint 1))`} But the former is easier to write and visually debug, which makes effective programming in our lambda language much more productive. That is why this method is prefered. `37:T7ed,md` Before we design an interpreter for our lambda language, we need to define a value datatype - that is the value of the interpreted term. ${html ``} The above should be intuitive in that an integer term is expected to evaluate to an integer value etc. We can define our interpreter as follows. ${html ``} Notice that our interpreter for the ${html`TMopr`} term can easily be extended in a way to include transactional operations on the blockchain for example or to facilitate writing code in this language. The next step for this **interp** function is to interpret terms into an **Option(value)** where **Option** is a datatype with two constructors: **None()** and **Some(value)**. In this way, we can implement error messages for our lambda language. That is, if the term provided cannot be interpreted into a value, without the **Option** datatype, the program will report a runtime type error (because some function that was expecting a value will be given a term). In this case, if we expect an **Option** type, we can use pattern matching to handle the case where the **Option** type is **None()** (which is when the interpreter has failed to convert a term into a value). If you are thinking you can also use exception handling for this, you are correct. But in this case it is not recommended because the same error in ATS can be produced from different lambda errors. This means either the code will increase in complexity, or the quality of the error messages recieved from the lambda language will diminish. `38:T9e6,md` A lot of very interesting research is currently being conducted on programming languages for the blockchain. In general, but especially in blockchain applications, we want to be absolutely sure that the code will do exactly what we expect it to do - and on the first time it is executed. This is due to 1. the immutability of the blockchain and hence the infinite persistence of your code (and its potential bugs) 2. the difficulty of performing runtime tests on a fully decentralized network If you miscalibrate your slot machine, there is nothing you can do but weep for your lost coins - the bug will forever persist on the blockchain for users to freely exploit. To solve this issue, a number of languages try to combine theorem proving with programming. [ATS](http://www.ats-lang.org/), for example, uses types (more precisely [dependent types](http://ats-lang.github.io/DOCUMENT/INT2PROGINATS/HTML/INT2PROGINATS-BOOK-onechunk.html#programming-with-dependent-types)) to flush out potential bugs at compile time (i.e. before running the code). This is enhanced by an ability to construct mathematical proofs about your code via special dynamic functions that exist only as compile-time helpers. In this way, provable guarantees can be provided without the need for runtime testing, and without impacting runtime efficiency. Please find some introductory examples on dependent types in ATS [here](https://github.com/galletti94/magnificATS/tree/master/INTRO/DepTypesIntro) and on theorem proving in ATS [here](http://ats-lang.github.io/DOCUMENT/INT2PROGINATS/HTML/INT2PROGINATS-BOOK-onechunk.html#theorem-proving_in_ats_lf). The full code for this article is online [here](https://github.com/galletti94/ATS-blockchain). I plan to evolve the lambda language and enhance the CLI to include distribution of the blockchain using [session types](https://beta.observablehq.com/@steinwaywhw/selected-topic-in-programming-languages-session-types/2). Pull Requests on GitHub are welcome and encouraged (especially if you would like to contribute more lambda code examples). Special thanks to [Hongwei Xi](https://www.cs.bu.edu/~hwxi/) and [Hanwen Wu](http://steinwaywu.com/) for ATS related support. Show your support by starring the repo! ${html ``} Part 2 is [here](https://beta.observablehq.com/@galletti94/functional-blockchain-part-2)! `39:[] 31:{"id":"fca4075fab76fd90","slug":"functional-blockchain","title":"Functional Blockchain","thumbnail":"c065cb9822d35ee910e5e4daf2f2286ee33a4ea34a840beb9e77ddc25df6c5ee","access_level":"public","create_time":"$D2018-04-22T16:33:49.330Z","update_time":"$D2018-08-08T19:25:24.477Z","view_time":null,"first_public_time":"$D2018-04-23T17:25:37.462Z","has_unpublished_edits":null,"fork":false,"stars":17,"starred":false,"owner":{"type":"team","id":"791792a5343379f7","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":"starter_2024"},"version":340,"publish_version":340,"role":null,"authored":false,"authors":[{"type":"individual","id":"2c1e218ff962bf94","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":null}],"members":[{"type":"individual","id":"2c1e218ff962bf94","login":"galletti94","name":"Lance Galletti","avatar_url":"https://avatars-next.observableusercontent.com/e2e4b1ce10cf5bb72cfe2694371c020ca4d5f76e844e1f20aa2585ecd4fcc75d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":17,"collection":null,"type":"notebook","body":{"title":"Functional Blockchain","cells":[{"id":0,"value":"md`# Functional Blockchain`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"md`\n${html `

`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"md`## Introduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"md`\nIf you are unfamiliar with blockchain, please first take a look at the following [video](https://anders.com/blockchain/). \n\nThis article aims to take you step by step through the implementation of a blockchain and a smart contract language, from scratch and in a functional programming style. \n\nSmart contracts provide users with an alternative to third party entities whose role is to ensure contracts are enforced/respected. For example consider user A wants to create a slot machine on the blockchain so that users can gamble with their cryptocurrency. Without smart contracts, taking part in this gamble is risky beyond the odds set by the machine. Consider that a slot machine is simply a random number generator (RNG). User B must trust that sending a coin over to A will result in A running a well-calibrated (i.e. calibrated as specified in the unspoken contract made by playing the game) RNG. And, should B win, that the appropriate reward (if any) will be sent over.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"md`\nUser A can write what is called a smart contract to specify the calibration and semantics of the slot machine for user B to review before deciding to partake in the game. To ensure that these contracts are upheld, they are written in a programming language that miners of the blockchain execute. The effect and result of this code persists in the blockchain (as would ordinary transactions) for all to view and verify. In this case, user B is no longer required to trust any third party and can simply read the smart contract (as any person would read any ordinary contract) to understand the terms and/or conditions.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"md`For more information, please take a look at the following [documentation](http://solidity.readthedocs.io/en/develop/introduction-to-smart-contracts.html) on creating smart contracts using a programming language called Solidity in Ethereum`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"md`## About`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"md`\nThe goal is to implement a blockchain and a smart contract language in a functional style that can be interacted with through a command line interface. The following article will walk through some high-level key features of the implementation, including:\n\n- Blockchain Definition\n- CLI\n- Mining\n- Smart Contract Language\n\nIn this way, I hope to demonstrate some neat functional features of the programming language [ATS](http://ats-lang.org/) while leaving aside some details of the implementation for the reader to think about and build for themselves. Also, I hope this article will make contributing to the repository easier.\n\n**Note**: to get the most out of this tutorial/ article, please spend the necessary time reading through the code displayed below and, if possible, interact with the code through the given interfaces. Try things out, make changes, be curious!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"md`## Blockchain Definition`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"md `### Definition`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"md`\nWe define the blockchain datatype as follows\n\n${html ``}\n\nAs an exercise and to get familiar with the ATS typechecker, please try to create your own block and blockchain in the main function. As you can see from reading the code above, a single block will have the following simple interface:\n\n${html `

`}\n\nTuples in ATS are immutable and are statically defined by their size. In this way, if we wish to extend our blockchain datatype (by adding some elements to the tuple), the typechecker will easily catch functions we forgot to update. This will make future enhancements of our code very productive!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"md `### Hash function`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"md `ATS has numerous meta-programming capabilities and injecting code from another language into ATS is made extremely easy. Here, we utilize the [openssl](https://github.com/openssl/openssl) C library and define a hash function as follows\n\n${html ``}\n\nNotice that everything between **%{** and **%}** is pure C code. The function **sha256_c** is usable in ats via the **mac#** symbol, binding the C implementation to the external ATS function **sha256**. The **char* ** type of C and **string** type of ATS are equivalent. This convenient way of co-programming in ATS and C lets us combine the powerful type system of ATS with extensive library functions of C.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"md`## CLI`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"md`## Mining`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"md` ## Smart Contract Language`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"md`### Lambda Calculus`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"md`\nThe programming language we will design to create smart contracts will be based on [untyped lambda calculus](http://www.cs.bu.edu/~hwxi/academic/courses/CS520/Spring18/notes/utlc.pdf). As such, our language will be turing complete but, as you will see, it will be extremely impractical since defining complex functions will be tedious.\n\nTo start, let us define a datatype called \"term\" to represent lambda calculus terms.\n\n${html ``}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"md`### Parser`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"md` \nParsing a file with the above syntax can be done as follows\n\n${html ``}\n\nOur parser is also very memory efficiency since it treats the contents of the file to be parsed as a linear stream of the characters. The **tokenize()** function maps the stream of characters into a stream of strings which can be in turn mapped to a term (via our **parse_tokens()** function) that will be interpreted into a value through an **interp** function we will define later.\n\nYou can view the full parsing implementations [here](https://github.com/galletti94/ATS-blockchain/blob/master/lambda/lisp_parser.dats)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"md`### Interpreter`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"md`\n### Code Generation\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"md`\nFor fun, we implemented, in this lambda language, various functions such as the fibonacci, the factorial, 8-queen... etc. Each of the .dats files [here](https://github.com/galletti94/ATS-blockchain/tree/master/lambda/example) will generate a .txt file with code written in our lambda language that can be parsed and interpreted to produce a value. These files can be accessed in the CLI through the **do_execute()** function. Currently, only the return values of files executed by **do_execute()** are stored on the blockchain. In the future, we would like to store the compiled byte code onto the blockchain along with the result so that validation can be done.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":190,"value":"md`## Closing Note`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 32:"$31:body"