diff options
| -rw-r--r-- | books/Little Schemer | 108 | ||||
| -rw-r--r-- | books/Seasoned Schemer | 139 | ||||
| -rw-r--r-- | software/functional programming | 52 | ||||
| -rw-r--r-- | software/git | 7 | ||||
| -rw-r--r-- | software/ruby | 67 | ||||
| -rw-r--r-- | software/scheme | 67 |
6 files changed, 440 insertions, 0 deletions
diff --git a/books/Little Schemer b/books/Little Schemer new file mode 100644 index 0000000..394de5b --- /dev/null +++ b/books/Little Schemer @@ -0,0 +1,108 @@ +============================ +The Little Schemer +============================ + +:by: Daniel Friedman and Matthias Felleisen +:Edition: Fourth (4rth) + +See also `Scheme </k/software/scheme/>`__. + +I read this book before starting on a scheme/physics project. I had programmed +in scheme previously as an algebra/analysis tool, but never really sat down +and got comfortable with the language. Working through all the examples +has made me *much* more comfortable with this style of programming. Despite +the humble tone and ambitions of the book I think I learned deeply. + +The first 7 chapters were very straight forward, the end of chapter 8 took +some more thought and I'm not sure how happy I am with the description of +collectors and continuations. + +For a better description of the Y-combinator, see these `course notes +<http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html>`__. + +This book is followed by `The Seasoned Schemer </k/books/seasonedschemer/>`__ +and The Reasoned Schemer. + +Preface Definitions +------------------------ +This primitive function is required for most of the functions in the book:: + + (define atom? + (lambda (x) + (and (not (pair? x)) (not (null? x))))) + +Laws +----------------------- +Law of Car + The primitive *car* is defined only for non-empty lists. + +Law of Cdr + The primitive *cdr* is defined only for non-empty lists. The *cdr* of any + non-empty list is always another list. + +Law of Cons + The primitive *cons* takes two arguments. The second argument to *cons* + must be a list. The result is a list. + +Law of Null? + The primitive *null?* is defined only for lists. + +Law of Eq? + The primitive *eq?* takes two arguments. Each must be a non-numeric atom. + +Commandments +------------------------ + +The First Commandment + When recurring on a list of atoms, *lat*, ask two questions about it: + *(null? lat)* and **else**. When recurring on a number, *n*, ask two + questions about it: *(zero? n)* and **else**. + + When recurring on a list of S-expressions, *l*, ask three questions + about it: *(null? l)*, *(atom? (car l))*, and **else**. + +The Second Commandment + Use *cons* to build lists. + +The Third Commandment + When building a list, describe the first typical element, and then + *cons* it onto the natural recursion. + +The Fourth Commandment + Always change at least one argument while recurring. It must be changed to + be closer to termination. The changing argument must be tested in the + termination condition: + + when using *cdr*, test termination with *null?* and + + when using *sub1*, test termination with *zero?*. + +The Fifth Commandment + When building a value with +, always use 0 for the value of the terminating + line, for adding 0 does not change the value of an addition. + + When building a value with x, always use 1 for the value of the terminating + line, for multiplying by 1 does not change the value of a multiplication. + + When building a value with cons, always consider () for the value of the + terminating line. + +The Sixth Commandment + Simplify only after the function is correct. + + +The Seventh Commandment + Recur on the subpart that are of the same nature: + + * on the sublists of a list. + * on the subexpressions of an arithmetic expression. + +The Eighth Commandment + Use help functions to abstract from representations. + +The Ninth Commandment + Abstract common patterns with a new function. + +The Tenth Commandment + Build functions to collect more than one value at a time. + diff --git a/books/Seasoned Schemer b/books/Seasoned Schemer new file mode 100644 index 0000000..0bc6346 --- /dev/null +++ b/books/Seasoned Schemer @@ -0,0 +1,139 @@ +============================ +The Seasoned Schemer +============================ + +:by: Daniel Friedman and Matthias Felleisen +:Edition: First (1st) + +See also `Scheme </k/software/scheme/>`__. This book is a sequel +to `The Little Schemer`_; The Reasoned Schemer is a paralel exploration of +logical programming. + +One of the things I liked about learning a programming language this way, or +maybe just about scheme in general, is the seperation between the specification +and implementations. Usually when I start learning a new language I try to +break it as fast as possible and I am most interested in how certain little +tricky bits are handled (are the file handles cross platform? does it catch +infinite recursion? what kind of errors are thrown when? how big are the +primitives and simple objects/user defined data types?). These are the +imporant day to day issues and are a good basis for choosing a language to get +work done in, but it's kind of like searching for anti-aliasing in digital +photos or scanning the edges of a wall for painting mistakes. Sometimes the +big picture is the whole point and it's worth putting up with small flaws. + +.. _The Little Schemer: /k/books/littleschemer/ + +Issues/Omissions +-------------------------- +The Y combinator function is never defined in this book, I had to copy it out of +`The Little Schemer`_; + + (define Y + (lambda (thing) + ((lambda (le) + ((lambda (f) (f f)) + (lambda (f) (le (lambda (x) ((f f) x)))))) + thing))) + +Also ``eqlist?``:: + + (define eqlist? + (lambda (a b) + (cond + ((and (null? a) (null? b)) #t) + ((or (null? a) (null? b)) #f) + ((and (atom? (car a)) (atom? (car b))) + (and (eqlist? (cdr a) (cdr b)))) + ((or (atom? (car a)) (atom? (car b))) #f) + (else (and (eqlist? (car a) (car b)) (eqlist? (cdr a) (cdr b))))))) + +MIT/GNU Scheme doesn't seem to have ``letcc`` or ``try``; I stuck with +``call-with-current-continuation``: + + (call-with-current-continuation (lambda (hook) ...) + ; is the same as + (letcc hook (...)) + + ; as noted in the book (p. 89) + (try x a b) + ; is the same as + (letcc success + (letcc x + (success a)) + b) + ; is the same as + (call-with-current-continuation + (lambda (success) + (begin + (call-with-current-continuation + (lambda (x) + (success a))) + b))) + +When reimplementing scheme at the end of the book, I'm kind of miffed that the +(letcc ...) definition basically just uses letcc, because magic North Pole +compasses seem like the most interesting part. + +Notes +----------------- +Y-bang is the "applicative-order imperative Y combinator":: + + (define Y-bang + (lambda (f) + (letrec + ((h (f (lambda (arg) (h arg))))) + h))) + +At one point I wondered:: + + Is there any language/interpreter which, when it runs into an undefined + value, lets you define it on the spot? Would be great for learners. + +MIT/GNU Scheme, of course, has this feature in the error REPL. But I never +noticed it. + +The Next 10 Commandments +-------------------------- + +The Eleventh Commandment + Use additional arguments when a function needs to know what other + arguments to the function have been like so far. + +The Twelfth Commandment + Use (letrec ..) to remove arguments that do not change for + recursive applications. + +The Thirteenth Commandment + Use (letrec ...) to hide and protect functions. + +The Fifteenth Commandment + Use (let ...) to name the values of repeated expressions in a function + definition if they may be evaluated twice for one and same use of the + function. And use (let ...) to name the values of expressions (without + set!) that are re-evaluated every time a function is used. + +The Sixteenth Commandment + Use (set! ...) only with names define in (let ...)s + +The Seventeenth Commandment + Use (set! x ...) for (let ((x ..)) ..)) only if there is at least one + (lambda .. between it and the (let ..), or if the new value for x is a + function that refers to x. + +The Eighteenth Commandment + Use (set! x ...) only when the value that x refers to is no longer needed. + +The Nineteenth Commandment + Use (set! ...) to remember valuable things between two distinct uses of a + function. + +The Twentieth Commandment + When thinking about a value created with (letcc ...), write down the + function that is equivalent but does not forget. Then, when you use it, + remember to forget. + +**I love that last sentence!** + + + + diff --git a/software/functional programming b/software/functional programming new file mode 100644 index 0000000..4720280 --- /dev/null +++ b/software/functional programming @@ -0,0 +1,52 @@ +=================================== +Functional Programming +=================================== + +Recursion +-------------- +**Partial** functions can recurse endlessly over a finite input. **Total** +functions will terminate/halt over a finite input. (TODO: check this +definition) + +Collectors +-------------- +The collector concept/pattern/paradigm is the one I am least familiar with +in functional programming. + +My current understanding is that they essentially allow allow recursive +functions to maintain something like state by wrapping immutable functions +or variables in layer after layer of functions and just holding on to +the outermost layer. For instance, the typical way to write a ``length`` +function in python would be:: + +>>> def how-long(x): +>>> l = 0 +>>> while x.has_next() +>>> l = l+1; +>>> x.pop() +>>> return l + +Using recursion, we could do:: + +>>> def how-long-recurse(x): +>>> if x.has_next() +>>> x.pop() +>>> return how-long-recurse(x) + 1 +>>> else +>>> return 0 + +Using the collector paradigm, we could do:: + +>>> def add1(x): return a+1; +>>> def how-long-col(x, col): +>>> if x.has_next() +>>> return col(0) +>>> else +>>> x.pop() +>>> return how-long-col(x, lambda a: col(add1(a))) + +The first two ways, the plus one operation is actually executed at any given +time, while with the collector implementation we're really creating a +function step by step which will give the answer at the end when it is all +executed. + diff --git a/software/git b/software/git new file mode 100644 index 0000000..cd0da69 --- /dev/null +++ b/software/git @@ -0,0 +1,7 @@ +======================= +Git +======================= + +Quick tip: when you have ``.gitignore`` ignoring everything (with a ``*`` +entry), you need to use ``git-update-index --add FILE`` to actually add the +file, instead of just ``git-add FILE``. diff --git a/software/ruby b/software/ruby new file mode 100644 index 0000000..e64f73e --- /dev/null +++ b/software/ruby @@ -0,0 +1,67 @@ +================== +Ruby +================== + +.. note:: This information is very rough, it's mostly my notes about what is + different about Ruby syntax compared to similar modern interpreted + pan-paradigm languages like Python. + +A unique intro to ruby is `"Why's Poignant Guide to Ruby"`__, a web-comic-y +short free online book by why the luck stiff. The more serious reference is +the "pickax" book. + +__ http://poignantguide.net/ + +Blocks +--------- +Blocks of code can be passed to functions, making ruby code more of a first +order data type. + +Ranges +---------- + +>>> 2..7 # => 2..7 +>>> (2..7).to_a # => [2, 3, 4, 5, 6, 7] +>>> (2...7).to_a # => [2, 3, 4, 5, 6] +>>> ('e'..'h').to_a # => ["e", "f", "g", "h"] + +Control Structures +-------------------- +Can use ``if`` after a statement:: + +>>> a = c if c > b + +Along with the usual ``break`` and ``next``, there is ``redo`` which redoes +the current loop (initial conditions may have been changed). + + +Boolean Operators +-------------------- +Anything that is not ``nill`` or ``false`` is true. To force interpretation +as boolean, use ``!!`` (not not):: + +>>> !!(nil) # => false +>>> !!(true) # => true +>>> !!('') # => true +>>> !!(0) # => true +>>> !!({}) # => true + + +Misc +---------------- +Can use nasty Perl style regular expression stuff:: + +>>> re1 = /\d+/ +>>> "There are 5 kilos of chunky bacon on the table!" =~ re1 # => 10, the index +>>> $~ # => #<MatchData:0xb7c36754> +>>> $~.pre_hash # => "There are " + +Also $1, $2, etc. + +The "splat operator", '*', either collects or expands extra arguments depending +on syntax (I think this is kind of icky):: + +>>> a, b = 1, 2, 3, 4 # a=1, b=2 +>>> a, *b = 1, 2, 3, 4 # a=1, b=[2,3,4] +>>> c, d = 5, [6, 7, 8] # c=5, d=[6,7,8] +>>> c, d = 5, *[6, 7, 8] # c=5, b=6 diff --git a/software/scheme b/software/scheme new file mode 100644 index 0000000..258343b --- /dev/null +++ b/software/scheme @@ -0,0 +1,67 @@ +================== +Scheme +================== + +``mit-scheme`` with the ``scmutils`` package is assumed; the command +``mechanics`` starts in interactive edwin prompt. + +See also notes on `The Little Schemer </k/books/littleschemer/>`__. + +Scheme Implementations +----------------------- + +Very partial list, mostly just the ones which are interesting to me. + +MIT/GNU Scheme + The 7.9.0 release (last stable as of 01/01/2009) is not R5RS compatible, + and is generally a pain in the ass to compile on new systems. The 9.0 + release should be easier to compile and distribute because it will use + a C compiler to bootstrap (true?). + +SCM + SCM is a fairly minimal, very small footprint R5RS-compatible + implementation. Apparently very portable and easy to compile. Includes + the Hobbit compiler. Part of the GNU project, maintained at MIT? + +SIOD + SIOD (scheme in one day) is a super small (75k binary?) Scheme + implementation. + +Coding in ``edwin`` +----------------------- + +..note: this section should be spun off as emacs. edwin is essentially a + scheme version of emacs. See this + `http://static.bryannewbold.com/mirror/sheets/emacs.pdf`:emacs cheatsheet: + +Common keyboard commands (usually 'M' is alt button, 'C' is ctrl, and 'S' is +meta/super/"windows"): + +========= ==================================================================== +C-x C-f Open a file, or create a new one +C-x C-s Save the file +C-x k Kill (close) a buffer +C-x C-c Exit the editor +C-g Abort a command +C-x C-e Evaluate the previous expression +M-z Evaluate the surrounding expression +M-o Evaluate the entire buffer (everything) +C-c C-c Kill evaluation after an error +C-y Paste (yank) +C-x 2 Split screen vertically +C-x 5 Split screen horizontally +C-x o Switch to next buffer window +C-x 1 Return to non-split screen +M-x Enter a command by name in minibuffer (use tab to complete) +C-x C-b Show buffer menu +C-x b Select buffer +C-x u Undo +C-y Paste +========= ==================================================================== + +Scope +-------------- + +``set!`` looks up a symbol name and permanently changes the first value it comes +across. ``let`` (and ``letrec``) create a new symbol with the given value. +But wait, you need a ``lambda`` block to make everything work? |