;;;; Note: this program is for CHICKEN Scheme Version 5.0. ;;;; It may need some tweaks to run under another Scheme implementation (import ; a sleep function which pauses for fractions of a second (rename srfi-18 (thread-sleep! sleep)) (chicken string)) ;; Hi! My name is Erik Falor, and I like parentheses. ;; I mean, I *really* like them, and am not ashamed to admit it anymore. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A brief demonstration of Scheme's awesomeness ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; Convert this song to an endless list of chars, and play it forever (define lyrics "This is the song that never ends It just goes on and on my friends Some people started singing it, not knowing what it was And they'll continue singing it forever just because ") (define lyrics-list (apply circular-list (string->list lyrics))) (define sing (lambda (song) (print* (car song)) (sleep .01) (sing (cdr song)))) ;; You call this function by writing this expression: ; (sing lyrics-list) ;;;;;;;;;;;;;;;; ;; LISP's legacy ;;;;;;;;;;;;;;;; ;; ;; At this point I should mention that this is a talk about Scheme, which is a ;; dialect of LISP. I will use these names in a way that makes them seem ;; interchangeable, but I use them very particularly. When I say LISP, I am ;; speaking about LISP-like languages in general. When I say Scheme, I mean ;; that language in particular. ;; ;; Did you know that LISP is the 2nd oldest programming language still enjoying ;; widespread use today? The first FORTRAN compiler was delivered in 1957, ;; while LISP was released the following year. (define current-year 2019) (define lisp-birthday 1958) (define scheme-birthday 1975) (- current-year lisp-birthday) ; => 61 ;; LISP's name is a contraction of LISt Processing. It was designed to be ;; really good at processing singly-linked lists used by early AI researchers. ;; ;; Scheme is a dialect of LISP that stresses conceptual elegance and ;; simplicity. First described in a 1975 paper, it has since been implemented ;; many times in many different ways because it is such a simple and small ;; language. ;; ;; Some nerds write their own text editor, some create their own command shell, ;; some nerds build their own lightsaber... you know, rites of passage! (- current-year scheme-birthday) ; => 44 ;; Together, LISP and Scheme have pioneered many important features now used by ;; virtually every mainstream programming language. ; ; ,--. ,--. ,--. ; | | `--' ,---. ,---. | |,---. ; | | ,--.( .-' | .-. |`-'( .-' ; | '--.| |.-' `)| '-' ' .-' `) ; `-----'`--'`----' | |-' `----' ; ,--. `--'-. ,--. ; | |,--,--,,--. ,--.,---. ,--,--, ,-' '-.`--' ,---. ,--,--, ,---. ; | || \\ `' /| .-. :| \'-. .-',--.| .-. || \( .-' ; | || || | \ / \ --.| || | | | | |' '-' '| || |.-' `) ; `--'`--''--' `--' `----'`--''--' `--' `--' `---' `--''--'`----' ; ; * Interpreter/REPL (Read, Eval, Print, Loop) ; ; * Dynamically-typed variables ; ; * Variables are references (everything's a pointer) ; ; * Garbage collection (automated memory-management) ; ; * Syntactic conditionals (if/then/else vs. goto) ; ; * Functions are first-class values (can be assigned to vars, passed to functions) ; ; * Recursion!!! ; * (Scheme introduced tail-call elimination) ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; The REPL and simple expressions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; I'm running this presentation live in a REPL - the Read Eval Print Loop. ;; If your language has an interpreter/REPL you have LISP to thank for that. ;; ;; The REPL *reads* input, *evaluates* and *prints* the result, then *loops* ;; back to await a new input. Immediate feedback makes for a great way to ;; experiment with and learn the language. ;; ;; One declares variables in Scheme with `define`. (define one 1) (define two "two") (define the-number-three!@# 33/11) ;; As you can see, LISPs are very permissive with what are considered valid ;; identifiers. ;; ;; Variables don't have types; values have types. LISP was the first language ;; to support dynamic typing. Assign a new value to a variable with `set!`: (set! one "1") (set! two 2.0) ;; Why am I putting a parenthesis in front of the name of the function instead ;; of behind it? Like so many of LISP's weird features, they are an accident ;; of history. If after 60 years LISP still carries some weird baggage, it's ;; not because nobody thought of alternatives. ;; ;; LISP was meant to be written in a more conventional syntax. What you see ;; now are called Symbolic Expressions or s-expressions, which represent a ;; structure called an Abstract Syntax Tree (AST). ;; ;; As your favorite programming language goes through the compiler, it, too, is ;; made into an AST along the way. ;; ;; Asking programmers write LISP code directly in this intermediate form was ;; meant to be a temporary situation because it was easier for the early LISP ;; compiler to work with pre-parsed code. ;; ;; LISP hackers decided that s-expressions are easier for programmers to work ;; with, too. So they stuck, and that more conventional syntax was never ;; finished ;;;;;;;;;;;;;;; ;; Conditionals ;;;;;;;;;;;;;;; ;; ;; If you use conditional statements in your programming language, you have ;; LISP to thank. Before LISP invented the syntax for branches, programmers ;; used `gotos` in assembly language or similar constructs in their then ;; state-of-the-art languages. ; 1 FUNCTION ARCTAN(X) ; IF(X) 2, 3, 3 ; 2 STOP ; 3 ARCTAN = 0.0 ; IF (X - 1.0) 10, 10, 5 ; 5 TERM = -1.0/X ; ARCTAN = 1.57079 ; GO TO 11 ; 10 TERM = X ; 11 PREVXP = 1.0 ; Y = TERM ** 2.0 ; 12 ARCTAN = ARCTAN + TERM ; PRESXP = PREVXP + 2.0 ; 13 TERM = - PREVXP/PRESXP * Y * TERM ; PREVXP = PRESXP ; 14 IF (TERM - 0.00005) 15, 12, 12 ; 15 IF (-TERM - 0.00005) 16, 12, 12 ; 16 RETURN ; 20 END (2, 2, 2, 2, 2) ;; In most languages we might call these "if statements". ;; ;; LISPs don't have if *statements*, or any other kind of statement. ;; Everything is an expression which results in a value. ;; ;; This is in contrast to mainstream languages which have a distinction between ;; "expressions", which are pieces of code which yield a value, and ;; "statements", which do not. ; ; /* This construct doesn't work in C-derived languages */ ; double r = if (x < 13) ; 13.37 ; else ; 3133.7; ; ; ; /* If/Else as an expression in C/C++/Java/C#, etc. */ ; double r = x < 13 // condition ; ? 13.37 // consequent ; : 3133.7; // else ;; This construct is quite natural in a LISP-derived language (define x 12) (define r (if (< x 13) ; condition 13.37 ; consequent 3133.7)) ; else ; /* Function calls are expressions which yield a value. ; * ; * For this example to work in C, one must place the ; * `for` loop into a function. ; */ ; double guess = 1.0; ; double root2 = for (int i = 1000; i > 0; i--) { ; guess = 0.5 * (2.0 / guess + guess); ; } ; printf("%f\n", root2); ;; The LISP way (define root-2 (let loop ((guess 1.0) (i 1000)) (if (zero? i) guess (loop (* 1/2 (+ guess (/ 2.0 guess))) (sub1 i))))) ;; The parentheses which delimit lists can also be thought of as *expression ;; delimiters*. Whenever you see one, you know that you're seeing the end of ;; an expression. The result of the entire expression is the last value before ;; the closing parenthesis. Simple. This is why LISP programmers have put up ;; with so many parentheses for so long. ;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Lists as function calls ;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; You may have heard that LISP has almost no syntax. They key piece of ;; syntactic knowledge that one must master is that of the list. ;; ;; As a LISt Processing language, LISP's fundamental data structure is the ;; singly-linked list. LISP source code is written in lists. When a LISP ;; encounters a list, it interprets the 1st item as the function and remaining ;; items as arguments. ;; ;; So, instead of ;; ;; set!(the-number-three!@# 'three) ;; ;; One writes ;; ;; (set! the-number-three!@# 'three) ;; ;; Lists are delimited by parentheses instead of square or curly brackets, and ;; items are separated by whitespace instead of commas. ;; Imagine if Python source code was written in the form of dictionaries and ;; C++ source code was written as arrays. ;; ;; Imagine if JavaScript programs were written in JSON: ; { "variable": { ; "name": "factorial", ; "value": { "function": { ; "arity": 1, ; "formal-parameters": [ "n" ], ; "code": { ; "if": { ; "test": { "expression": [ "n", "===", "0" ] }, ; "consequent": { "expression": [ "return", "1" ] } ; "else": { ; "expression": [ "return", "n", "*", { ; "function-call": { ; "function": "factorial", ; "parameters": [ { ; "expression": [ "n", "-", "1" ] ; } ] ; } ; } ; } ; } ; } ; } ; } ; } ; } ;; This illustrates the characteristic pile-up of closing parentheses at the ;; tail-end of LISP code! ;; ;; The upside is you could use the built-in facilities of the language itself ;; to process the source code of that language! JavaScript could easily parse ;; its own code were it written in JSON. ;; ;; These are hypotheticals when discussing other languages, but with LISP, the ;; concept of writing code to write code is the reality! ;; Some functions don't care about *arity* (the number of parameters they accept). ;; Who needs a sum function? (+ 1 2 3 4 5) ;; Who needs a product (or a factorial) function? (* 1 2 3 4 5) ;; How many times have you wanted to find out whether a sequence of numbers ;; was already sorted? (< 1 2 3 4 5) ;; One of these things is not like the others... (= 9 9 9 9 9 9 9 9 9 9 9 6 9 9 9) ;; As long as the first thing in a list is a function, LISP is able to execute ;; a list to produce a result. ;;;;;;;;;;;;;;;;;;;;; ;; `quote` and `eval` ;;;;;;;;;;;;;;;;;;;;; ;; ;; The only kink in this plan is that sometimes you don't want your list to ;; *do* anything; you would like it to just be data. How to I keep LISP from ;; trying to execute my data structures? ;; ;; `quote` renders a list inert by suppressing evaluation. (quote (+ 1 2 3 4 5)) ;; Ack! More parentheses! As a shorthand, `quote` may be written as an ;; apostrophe immediately in front of an s-expression. '(+ 1 2 3 4 5) ;; To "run" your data structure, use the `eval` function. (eval '(+ 1 2 3 4 5)) ; => 15 (define a-thing-to-do '(+ 1 2 3 4 5)) (eval a-thing-to-do) ; => 15 ;; `eval` and `quote` form a complimentary pair. ;; ;; If your language has an `eval` function, what can I say but "you're ;; welcome!" ;;;;;;;;;;;;;;;;;;;;;;;;;; ;; car, cdr, list and cons ;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; Speaking of lists, let's use this LISt Processing language to manipulate ;; some lists. ;; ;; A function called `car` gives us the item at the head of a list (car a-thing-to-do) ; => + ;; A function called `cdr` (pronounced "could-er") skips over the head and ;; returns the rest of a list (cdr a-thing-to-do) ; => (1 2 3 4 5) ;; Now, I know what you're thinking: ;; "`car` and `cdr` are stupid names. `first` and `rest` would be better." ;; ;; You're not wrong. ;; ;; These names are another piece of historical baggage. The reason why we ;; haven't gotten rid of them in 60 years is because we have created functions ;; which are compositions of `car` and `cdr` and are given names which are ;; mnemonics of their constitutions. ;; ;; Suppose I want the 2nd item from this list? (car (cdr a-thing-to-do)) ; => 1 ;; Or the 3rd? (car (cdr (cdr a-thing-to-do))) ; => 2 ;; Each of these operations have a shorter notation: (cadr a-thing-to-do) ; => 1 (caddr a-thing-to-do) ; => 2 ;; Functions representing all combinations of 'a's and 'd's ;; up to a length of 4 are defined in LISP (car (cdr (cdr (cdr a-thing-to-do)))) ; => 3 (cadddr a-thing-to-do) ; => 3 ;; So far I've been making list literals with `quote`. How to form a new list ;; at runtime? ;; ;; Lisp lists are formed from a pair of pointers called a "cons cell". A linked ;; list is just a chain of "cons cells" pointing to one another. Cons cells have ;; two fields, a "car" and a "cdr". The "cdr" field contains a pointer to the ;; next cons cell in the list. ;; ;; The expression ;; ;; (cons 1 (cons 2 (cons 3 '()))) ;; ;; constructs the list ;; ;; (1 2 3) ;; ;; ;; .---.---. .---.---. .---.---. ;; |car|cdr|--> |car|cdr|--> |car|cdr|--> '() ;; '---'---' '---'---' '---'---' ;; | | | ;; '--> 1 '--> 2 '--> 3 ;; ;; ;; Each list element may be of a different type. ;; ;; The list is terminated by a cons cell with the empty list in its cdr field. ;; LISP's linked-lists are formed ;; There is a function called `list` which more conveniently constructs a new ;; list from its arguments. (cons 1 (cons 2 (cons 3 '()))) ; => (1 2 3) (list 1 2 3) ; => (1 2 3) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Calling and making functions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; The `lambda` special form creates a function. It takes as arguments names ;; of the formal parameters followed by expressions which make up the body ;; of the function. There is no `return` statement. A function naturally ;; 'returns' the value of the final expression of its body ;; ;; When a function is placed in the 'head' position of a list, the function is ;; invoked with remaining items in the list bound to its formal parameters. ;; The identity function returns its argument unchanged (lambda (x) x) ; => # ((lambda (x) x) 'me) ; => me ;; The `square` function multiplies its argument by itself (lambda (n) (* n n)) ; => # ((lambda (n) (* n n)) root-2) ; => 2.0 ((lambda (n) (* n n)) +i) ; => -1 ;; Functions are first-class values. ;; ;; Our functions are given names in exactly the same way as names are given to ;; any value, through variable assignment. (define identity (lambda (x) x)) (identity 'me) ; => me (define square (lambda (n) (* n n))) (square root-2) ; => 2.0 (square +i) ; => -1 ;; Values are passed to functions. ;; Functions are values. ;; Therefore, we may pass functions to functions. ;; ;; `map` is a function which takes two arguments: a function and a list. The ;; input function is applied to each item of the list in order, and the outcome ;; of each function call is collected into a new list returned by `map` (map identity '(12 2/7 +i)) ; => (12 2/7 0+1i) (map square '(12 2/7 +i)) ; => (144 4/49 -1) (map square '(1 2 3 4 5)) ; => (1 4 9 16 25) ;; `filter` is a function that takes two arguments: a predicate function and a ;; list. The predicate is applied to each item of the list in order, and those ;; values which cause the predicate to return #t are collected into a new list ;; returned by `filter` (filter even? (map square '(1 2 3 4 5))) ; => (4 16) ;; Anywhere a function is needed one may supply either a named function, ;; or a function literal formed with `lambda`. (filter (lambda (n) (> n 10)) (map square '(1 2 3 4 5))) ; => (16 25) (define >10 (lambda (n) (> n 10))) (filter >10 (map square '(1 2 3 4 5))) ; => (16 25) ;; Typing out this list of numbers all of the time is becoming a drag. ;; Let's use what we know to write a function to construct a list of numbers ;; from 1 to n. ;; ;; ;; The list we want to make has a recursive structure that looks like this: ;; ;; (cons 1 (cons 2 (cons 3 '()))) ;; ;; There are two ways we can approach this; by starting at the front of the ;; list with 1, or by going backwards from N. ;; ;; If we start from the *END* of the list and go backwards, we begin by consing ;; N onto the empty list '() ;; ;; Working back from N to 0, we'll recur with two parameters, N-1 and the list ;; we're building from back to front. When N is zero, stop and return the list. (define count-to/list (lambda (n lst) (if (zero? n) lst (count-to/list (sub1 n) (cons n lst))))) (count-to/list 4 '()) ; => (1 2 3 4) (count-to/list 20 '()) ; => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) (count-to/list 200 '()) ; => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ... 200) ;; I don't like needing to pass '() in each time. Let's define a more ;; convenient function for the user interface which calls `count-to/list` as ;; a helper function: (define count-to (lambda (n) (count-to/list n '()))) (count-to 20) ; => (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) (map square (count-to 20)) (filter even? (map square (count-to 20))) (filter even? (map square (count-to 200))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; You should apply yourself to the problem ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; Remember that *, when applied to the numbers 1 ... N is essentially the ;; factorial function? Let's try it with `count-to`. What's 200!? ;(* (count-to 200)) => ERROR! ;; Oops, that didn't work. Why not? ;; ;; `count-to` results in one list (1 2 3 4 5 ...), so the call to * ;; looks like (* (1 2 3 4 5 ...)) ;; ;; But `*` expects many numbers, not one list: ;; (* 1 2 3 4 5) ;; ;; Here is a situation where we can take advantage of the fact that LISP code ;; is a list, and put LISP's list-processing functions to work for us. ;; ;; Use `cons` to put `*` at the front of our list of numbers, yielding this list: (cons * (count-to 200)) ; => (* 1 2 3 4 5 ...) ;; Now use `eval` to execute this list: (eval (cons * (count-to 200))) ; => 78865786736479050355236321393218506229513...000000000000000000000000000000000000000 ;; This is pretty handy. We should make this into a function so we can easily ;; do it whenever we want. (define apply (lambda (fn lst) (eval (cons fn lst)))) ;; `apply` is already built in to the language for you, but we shouldn't let ;; that stop us from thinking about how it works. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Code like you `mean` it - n-ary functions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; We've seen how to write functions which take a particular number of named ;; parameters. How do we write a function like `*` or `+` which take an ;; arbitrary number of parameters? ;; ;; Formal parameters are named in a list after the symbol `lambda`. An n-ary ;; function is created with a single formal parameter which is *not* surrounded ;; by parens. The arguments are available to the body as a list, and when no ;; arguments are given the list is empty. ;; ;; Here is a function which computes the arithmetic mean of its arguments. ;; Because Scheme's arithmetic functions are themselves n-ary, I am able to ;; write this without resorting to recursion or iteration: (define mean (lambda lst (if (null? lst) 'LOLwut? ;; obvious div-by-zero is obvious (/ (apply + lst) (length lst))))) (mean 42 (sqrt 2.0) 1337 +i 311/99) ; => 276.711125540757+0.2i (apply mean (count-to 100)) ; => 101/2 (mean) ; => lolwut? ;;;;;;;;;;;;;;;;;;; ;; The grand finale ;;;;;;;;;;;;;;;;;;; ;; ;; Because functions are first class values and we've been passing them into ;; functions, doesn't this mean that we can write a function which returns ;; a new function? ;; ;; Suppose I want to square the square of the square of a number: (square 2) ; => 4 (square (square 2)) ; => 16 (square (square (square 2))) ; => 256 ;; That is a lot of typing! Let's make a function which, given a unary ;; function, will return a new unary function that has the effect of repeatedly ;; calling our unary function the number of times we wish. ;; ;; In other words, we want to create a function which calculates the value of ;; calling `square` upon the value of our number squared... and so on. ;; ;; This is problem with a recursive definition. ;; ;; For the base case of n == 1, we want our new function to have the same ;; effect as calling unary `square` once. Hey! `square` is a unary function ;; that has the same effect as calling `square` once! Let's just return that! ;; ;; Now we just need to think about the recursive step. This is where I'll lose ;; some of you, but don't give up hope! This stuff used to lose me, too. I'm ;; not particularly smart, and if I can figure this out, you can, too. ;; ;; Remember that we want to return a unary function, *not* a number! (define repeated (lambda (fn n) (if (= n 1) fn ; a unary function (lambda (p) ((repeated fn (- n 1)) (fn p))) ; another unary function ))) ;; If this worked, we can use our newly-returned function right away: (square (square (square 2))) ; => 256 ((repeated square 3) 2) ; => 256 ;; We might want give our awesome function a befittingly awesome name to save ;; it for later (define square^3 (repeated square 3)) (square^3 2) ; => 256 (square^3 1/7) ; => 1/5764801 ;; We now have a way to create *any* repeated function we want, whenever we want! (add1 (add1 (add1 1))) ; => 4 ((repeated add1 3) 1) ; => 4 (define excited (lambda (str) (string-concatenate (list str "!")))) (excited "Thank You") ; => Thank You! (define really-excited (repeated excited 10)) (really-excited "Thank You") ; => Thank You!!!!!!!!!! (define crazy-excited (repeated really-excited 10)) (crazy-excited "Thank You") ; => Thank You!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ;;;;;;;;;;;;;;;; ;; In conclusion ;;;;;;;;;;;;;;;; ;; ;; I am not trying to persuade you that LISP is better than your favorite ;; language. What I do want to convince you of is that there is value in ;; learning a language that will change the way you think about programming. ; _ _ ;( | ) LISP is worth learning for [...] the profound enlightenment ; V V experience you will have when you finally get it. That experience _ _ ; will make you a better programmer for the rest of your days, even ( | ) ; if you never actually use LISP itself a lot. V V ; ; -- Eric S. Raymond ; How To Become A Hacker ; ;; Getting started with the Scheme programming language ; ; ************************************************************************************** ; /*/////////////////////////////////////////////////////////////////////////////////////* ; /* /* ; /* Scheme Implementations /* ; /* * Chicken (A Scheme->C compiler; used for this presentation) /* ; /* https://call-cc.org /* ; /* /* ; /* * Racket (Most user-friendly; includes GUI IDE) /* ; /* https://racket-lang.org/ /* ; /* /* ; /* * Chez Scheme (Recently open-sourced; best performance) /* ; /* https://www.scheme.com/ /* ; /* /* ; /* * Lists and Lists (Scheme Tutorial as Interactive Fiction by Andrew Plotkin /* ; /* https://www.eblong.com/zarf/zweb/lists/ /* ; /* /* ; /* Online Tutorials /* ; /* * Teach Yourself Scheme in Fixnum Days /* ; /* http://ds26gte.github.io/tyscheme/ /* ; /* /* ; /* * The Scheme Programming Language 4th ed. /* ; /* http://www.scheme.com/tspl4/ /* ; /* /* ; /* * Structure and Interpretation of Computer Programs /* ; /* (a.k.a. "The Wizard Book") /* ; /* https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html /* ; /* /* ; /*************************************************************************************** ; ///////////////////////////////////////////////////////////////////////////////////////