summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorbryan newbold <bnewbold@snark.mit.edu>2009-01-22 23:04:17 -0500
committerbryan newbold <bnewbold@snark.mit.edu>2009-01-22 23:04:17 -0500
commit7218768aba3a43f1a62867f35f05cb85a30d7ed2 (patch)
treeacfc09cc29bcb6c543a760ede6a399375a8c92ab
parent0f238f885ff64a94c2bfb2906b5f1e8edb93dc0c (diff)
parentf18ba63a8b3d39bc9f2ca8dbe6d766d0dd5f77ec (diff)
downloadknowledge-7218768aba3a43f1a62867f35f05cb85a30d7ed2.tar.gz
knowledge-7218768aba3a43f1a62867f35f05cb85a30d7ed2.zip
Merge branch 'master' of ssh://animus.robocracy.org/srv/git/knowledge
-rw-r--r--books/Little Schemer108
-rw-r--r--books/Seasoned Schemer139
-rw-r--r--software/functional programming52
-rw-r--r--software/git7
-rw-r--r--software/ruby67
-rw-r--r--software/scheme67
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?