Addition, subtraction, multiplication, division, exponents, roots, are all just abstractions, or syntactic sugars representing different combinations of a basic building block, from here further called a primitive.
Understanding a primitive means one has the basic datum from which to align all data built from the primitive. It simplifies and explains all abstraction, syntactic sugar, and other building blocks built from it.
One can think of this like a triangle. At the very tip is the basic primitive(s). As you go down from the tip the triangle gets wider. The wideness is more abstraction, syntax, data, complexity. If one were to take a view from the base toward the tip, one would immediately see all the abstraction, all the data, all the complexity. It could look like one big unwieldy mass of unexplained stuff. To a greater or lesser degree I think this is what a lot of people see when they first look into a science or a technology.
If you understood the primitive(s) and looked into the triangle from the opposite direction, from the tip towards the base, aligning data from the tip forward, you could understand the whole subject. The outer complexities are explained and simple.
In this post, the primitive I am talking about is the idea "one more", or "add one" or 1+. That's all that addition, subtraction, multiplication, division, exponentiation and roots are. Related subjects built entirely from these things are also just "one more".
So, here's how you build up math with plus one:
A number besides 1 is our first abstraction, or syntactic sugar. A number is just short hand for 1+ a number of times. Example:
5 = 1 + 1 + 1 + 1 + 1
Addition is short hand for adding a number of plus ones to another number of plus ones:
5 + 3 = (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1) or 5 + 3 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Multiplication. Since the addition abstraction is now defined, I'll use that abstraction to build further abstractions, starting with multiplication. Multiplication is short hand syntax for starting with a value 0 and adding a number a number of times.
5 * 4 = 20 means 4 + 4 + 4 + 4 + 4 = 20
Subtraction is an abstraction or short hand way of adding negative numbers.
10 - 3 = 7 means: 10 + (-3) = 7
Negative numbers. Zero is nothing or zero +1s. Less than zero +1s is a negative number. An abstraction for one less than zero +1s could be represented as "-1". Example:
-7 = -1 - 1 - 1 - 1 - 1 - 1 - 1 Another example: 5 + (-3) Same as: 1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 = 1 + 1
Division is how many times you can add a negative number to a number to get 0.
6 / 2 = 3 or (1 + 1 + 1 + 1 + 1 + 1) / (1 + 1) = (1 + 1 + 1)
Math doesn't have an alternative equation syntax to express what the division abstraction is doing. Therefore I have made up a syntax that shows what division is doing.
The parts that are enclosed by the bars is a counter that gets incremented each time a subtraction occurs. When the number being subtracted from reaches 0 the counter value is returned as the value of the equation.
6 / 2 is equal to this syntax: 6 - 2 |0 + 1| 4 - 2 |1 + 1| 2 - 2 |2 + 1| = 3 or taking out the abstraction of subtraction: 6 + (-2) |0 + 1| 4 + (-2) |1 + 1| 2 + (-2) |2 + 1| = 3 and taking out the abstraction of numbers: 1 + 1 + 1 + 1 + 1 + 1 - 1 - 1 |+ 1| 1 + 1 + 1 + 1 - 1 - 1 |1 + 1| 1 + 1 - 1 - 1 |1 + 1 + 1| = 1 + 1 + 1
How exponents and roots are built up from +1 and/or its abstractions is left to the reader.
Marc wrote Confessions of a Terrible Programmer. Some insightful things in there about writing great software.
Here's a quote:
Over the years I’ve learned more ways to hide my programming failings. One technique: let the program crash—This works, just stay with me. I’d joined a development project where the original developers had so many problems with run-time exceptions that they simply starting including "null exception handlers", i.e., catch all unexpected exceptions, suppress them, and keep on going. Needless to say, the system would run fine for awhile, sometimes hours, and then slowly start to...hmm..."veer off".
When I got the chance to redesign the system, one thing I immediately forbade was those null exception handlers (though handlers for recognized exceptional conditions were permitted). If an exception occurred, I wanted it to propagate up until it took the application down so that we would know about it and could fix it right then and there. I got my wish, but was almost found out in the process. The program manager got wind that we were seeing a lot of system crashes during testing, and he wanted to know why the redesigned system was crashing so much more often than the one it was replacing. Explaining that we were uncovering errors and getting them fixed now, and fixed right, didn’t really give him the warm fuzzy he was looking for, as there were deadlines approaching and the reported error rate wasn’t declining as fast as he liked. The team stuck with this practice, though, and when we were done (on time and on budget) the system ran reliably and correctly for days under both light and heavy loads.
This made me laugh:
Now if you look at my code you might find it to be pretty bad, and that’s normal, pretty much any programmer that looks at almost any other programmer’s code will judge it to be a pile of offal and then proclaim that the only way to fix it is to rewrite it. (I wonder why this is?)
This was an insightful comment by masklinn on programming.reddit.com:
Thing is, well-defined, strong, extensive type systems (such as Ada's, OCaml's or Haskell's) are test cases that were already built for you by the authors of the language.
Even better, there are automated test generators that can leverage the language's type system to automatically generate test cases, see Haskell's QuickCheck and SmallCheck.
I'm not arguing against dynamic typing, I love Python, Ruby and Erlang and would use any of them over Java any time of the day, but the thing is, for every type annotation you write or every type your compiler infers in a good static type system you will need to write multiple test cases in a dynamically typed language.
Soo, if you have a type system worth using (which Java's isn't), you can see it as specifications autogenerating series of tests for you.
Bryan O'Sullivan on processing log files, includes performance figures and parallel programming in Haskell. Nice response to Tim Bray's "Wide Finder" post.
I'm continually amazed by Javascript. It is such a secretly amazing language. Look at this Javascript array:
listfun = [["My RSS image", "http://nickmudge.info/valid-rss.png"],
["Google Birthday image", "http://www.google.com/logos/9th_birthday.gif"],
["Blogger image", "http://www.blogger.com/img/logo100.gif"]]
Beautiful, but it doesn't look like an array, it looks like a list! A list of lists. So is it an array or a list?
What does a list definition look like in Haskell? It looks the same! This code compiles as Haskell and interprets as Javascript. So is it Haskell or Javascript?
I started writing lists, I mean arrays, like this in my Javascript code recently. It's a bit of concrete evidence for me that Haskell/functional programming is sneaking into my programming in other languages. I didn't realize that this Javascript is Haskell until tonight.
On another note: Check out this 3D animated graphics written in pure Javascript/css/html, no images, no flash, nothing else. Got to love borders and triangles.
stesch from programming.reddit.com: "JavaScript is a magic thing. Everybody sees something from his favorite language in it."
I came across this raytracer written in Haskell in one day about 7 years ago.
Here's a quote from the source code:
-- I wrote this in a day to learn Haskell. I was pretty impressed by -- the speed of development. Compared to C/C++/Java, you spend much -- more time thinking about the problem rather than the implementation -- language. You don't need to worry about memory management. Your -- code isn't littered with detail about *how* to do things (ie. in -- Haskell you'd use map in places where you'd have a for loop in C, -- and you don't have to explicitly state the loop variable or the -- number of iterations). The strict typechecking and the interpreted -- nature of hugs means that most errors are flagged quickly. It -- doesn't stop you making logic errors though, but it's quite easy to -- test functions individual to work out what's going wrong (big win -- for interpreters). It's pretty concise too (around 160 lines of -- actual code). And the performance isn't all that bad.
Raytracer on programming.reddit.com
I also came across a raytracer written entirely in javascript and runs in your browser. Pretty insightful about the capabilities of javascript.
This post is with reference to the parsing library for the book Programming in Haskell, chapter 8.
To combine multiple parsers into a single parser you can use the sequence operator <<= or do notation.
The nice thing about the sequence operator is that it is more descriptive about how parsers are combined. And with the definition of the sequence operator you can work out and understand how the parsers are combined.
The nice thing about do notation is that it is nice. It is more concise and elegant. It is syntactic sugar for using the sequence operator.
item is a parser that takes a string and returns a pair with the first part containing the first character of the string and the second part containing the rest of the string.
Using the sequence operator, here is how to combine two item parsers into one parser with the result of returning the first two characters, making them a string, and the second part containing the rest of the string:
twoChar = item >>= \v1 -> item >>= \v2 -> return (v1:v2:[])
parse is just a function that takes input and applies it to a parser function. Here's an example of applying twoChar:
> parse twoChar "hello"
[("he", "llo")]
A couple things to notice: the syntax \ -> denotes a lambda or anonymous function. The return function accumulates values generated by the parsers, makes them a string, and returns the string along with any left over string. If input is less than two characters, the twoChar function will return an empty list [] denoting failure.
Here's twoChar defined with do notation:
twoChar = do v1 <- item
v2 <- item
return (v1:v2:[])
That's cleaner. Check out this definition:
twoChar = do v1 <- item
do v2 <- item
return (v1:v2:[])
+++ return (v1:[])
+++ is a conditional operator. In this case it says that if trying to parse a second character fails (because the string is one character long), then just return the first character and the rest of the string. The function will work if an input string is one character long or longer. Notice the nested do notation. Since do notation is just syntactic surgar for using the sequence operator, how do you write the equivalent nested do notation using the sequence operator?
twoChar = item >>= \v1 -> (item >>= \v2 -> return (v1:v2:[])) +++ return (v1:[])
But I think it is clearer in this case to use prefix notation, like this:
twoChar = item >>= \v1 -> (+++) (item >>= \v2 -> return (v1:v2:[])) (return (v1:[]))
For kicks: Here's do notation with prefix notation:
thingy = do v1 <- item
(+++)
(do v2 <- item
return (v1:v2:[]))
(return (v1:[]))
Peter Seibel's Practical Common Lisp is a good lisp tutorial.
I did all of the exercises in the book Programming in Haskell to chapter 8. I'm starting over from the beginning. If you are interested in doing the exercises in the book, it would be fun to compare solutions. Let me know.
The functional programming meeting in San Francisco on Thursday was great. I was "the guy who came all the way from Sacramento". One programmer suggested that the meeting be called the Northern California Functional Programming Meeting.
I counted 26 people there. That's a lot of people at one table. There were people from OCaml, Haskell, Erland and Scala.
For next meetings it looks like speakers are being organized for various talks. Included in these is Alex Jacobson on HAppS, and Bryan O'Sullivan on Mad Protocol Craziness.
In studying Haskell, the term primitive recursion keeps coming up without any definition really. Haskell seems to have this vast advanced mathematics background that seeps into the language and into the literature of the language. This can be balking and repelling for a programmer wanting to learn Haskell but without an advanced degree in math. But maybe it has benefits like maybe this definitive, discrete, articulate, specific knowledge is useful. Perhaps it keeps only smart people part of the user community of Haskell.
So I set out to find out what primitive recursion is. With math and computer science terms Wikipedia is often harder to understand than the term you're looking up.
In my search for knowledge that a mere mortal could digest, I found this online dictionary by NIST called Dictionary of Algorithms and Data Structures that is surprisingly human and well structured.
I followed a highly educational trail on the subject of function definitions. Let's look at some definitions from this dictionary:
Function: "(1) A computation which takes some arguments or inputs and yields an output. Any particular input yields the same output every time. More formally, a mapping from each element in the domain to an element in the range."
Yes, but what is meant by domain, and range?
Domain: "(1) The inputs for which a function or relation is defined. For instance, 0 is not in the domain of reciprocal (1/x). (2) The possible values of a variable."
Relation?
Relation: "A computation which takes some inputs and yields an output. Any particular input may yield different outputs at different times. Formally, a mapping from each element in the domain to one or more elements in the range."
Ah, for any input a function always returns the same result. Whereas a relation can return the same or different results. A relation is more generalized than a function. A function is a specialization of a relation.
Range: "The possible results of a function or relation. For instance, the range of cosine is [-1,+1]."
Under the definitions of words this dictionary provides lists of words under headings such as Generalization, which gives words that are generalizations of the word you are looking up, and Specialization, which are words that are specializations of the word, and Aggregate child, which shows you what words the word is contained in. Showing these relations of words is extremely useful in understanding the relations, similarities and differences between related words. Awesome.
Okay, let's look at the definition of primitive recursion.
Primitive recursion: "A total function which can be written using only nested conditional (if-then-else) statements and fixed iteration (for) loops."
Woah, I almost undertood that. Total function?
Total function: "A function which is defined for all inputs of the right type, that is, for all of its domain." It has an example: "Note: Square (x²) is a total function. Reciprocal (1/x) is not, since 0 is a real number, but has no reciprocal."
There's a "See also partial function."
Partial function: "A function which is not defined for some of its domain. For instance, division is (usually) a partial function since anything divided by 0 is undefined."
Wow, now I understand! and a whole lot of other things!
Paul Johnson wrote this pitch on the Haskell-cafe mailing list:
For software developers who need to produce highly reliable software at minimum cost, Haskell is a pure functional programming language that reduces line count by 75% through reusable higher order functions and detects latent defects with its powerful static type system. Unlike Ada and Java, Haskell allows reusable functions to be combined without the overhead of class definitions and inheritance, and its type system prevents the hidden side effects that cause many bugs in programs written in conventional languages.
I used to think of and describe programming as writing a bunch of instructions for a computer to execute. In low level programming where you are more closely approximating how the inner details of how a computer works, this is more closely the case.
High-level programming — where many lower level computing details are automated behind the scene by the programming language and operating system — and where you can define and use many other coding abstractions/automaticities, writing instructions for a computer to execute isn't really what you're doing.
In high-level programming, you aren't telling a computer what to do, you're describing scenarios and problems and solutions in a language that a computer can mathematically translate into its own computations.
High-level programming is about communicating, it's expression. You want to write your code so that it describes clearly and succinctly what is going on. It's about how well you communicate, and when you get into this sort of thing you get into art, because what is art but how well you communicate something, aesthetics, quality of communication1.
When you write a high-level program, a computer reads it and duplicates it, that is it parses it and translates it into its own data structures and computations. It doesn't necessarily follow your exact instructions. It looks at what you said and makes computations based on ways that are most efficient for the computer to compute, and maybe other criteria such as interoperability between systems. In your code you may say addition, and your computer might actually do multiplication. You might say to call a function at line 42 of your program, but the computer doesn't actually call this function until line 45. The point of the computer is to give you the result you describe in your code, how it actually achieves this result is its own business.
When you are writing code, you're not writing it for the computer really, you're writing it for your and other's understanding. The computer incidentally just has to be able to duplicate the code and come up with its own computations that match the program description. It's like you're writing a story, but it happens that you can feed it into a computer and the computer animates it, like it's happening in real life!
Why does it matter how clearly and succinctly you write code? Why does art in programming matter? Because great software depends entirely on how well it is understood. It is people that make software great. Great software is great because someone(s) really understood it. How structured, clear, and succinct a program is written determines how well and how fast it can be understood if you begin to write programs of any complexity. How short a program is matters because it is generally easier and faster to understand programs of shorter length. This isn't always the case however. You can write short code which obscures clarity. Skill, expertise and experience enters into this as conciseness with clarity is entirely possible.
When you really understand a software application, your flexibility with it is enormous. You can change it pretty easily, add functionality, etc. Bugs are pretty much nothing because they are easy to fix. You are really efficient with this code and application. You can duplicate it and change it a lot for a new application for a different use. You can do lots of things. Programming is fun.
When you start dealing with a lot of software, and you write code that depends on other code or systems (including your own code and systems), it matters whether you understand that other code or systems. Other code is not just "Yippee! the work is already done. I can just use this without understanding it." By entering in code or systems you do not know about, you are entering in non-understanding into your software. As programming is expression or communication, you're adding elements to your communication that you don't know about. If you did this enough you could say that you didn't know what you were talking about. What kind of quality of communication is that?
If code that you have written or others have written is a good program description, i.e. does what it is supposed to do well and is clear and concise, then it provides a developer the opportunity to take the time and effort to really understand it and so use it well in other code and applications.
Other people's reusable software and systems aren't free, it costs the work and time to understand them, which can still be faster than writing everything from scratch. Perhaps a good way to write software is to study how someone else did it and model your software off that.
There's been a noticable spark of interest in Damien Katz's CouchDB.
He's great at writing about programming. I think I first got the idea that I don't really need a RDBMS from reading Damien's blog.
I got an email today from Government Technology about their new briefcase tutorial. Pretty cool. It shows how to use the briefcase functionality on the site.
Also noticed that their's a new video with Vint Cerf about future Internet applications.
In June I bought Paul Graham's ANSI Common LISP, and Peter Seibel's Practical Common Lisp, getting really interested in Common Lisp. They are great books. I spent a lot of my spare time in June and July studying and writing Common Lisp.
I'd found out about Common Lisp from reading Paul Graham's essays, like how it says on wikipedia. In checking it out some I decided that I could really like it and decided to seriously take up the subject and so bought the books.
The thing about Common Lisp is that I found that I just really liked it. It was also very different. The mystery of the language really lured me. I thought maybe there's something that I could really use here and really like. In the past I had gotten a taste of different approaches in programming by learning Python, and it was sweet.
Lisp gave me the idea that you could be much more productive as a programmer by how you wrote code. And you could write great small or large systems by how you wrote them. And you need a programming language that allows you to write code in a way that is really good and productive. By productive I mean things like a lot of capability or functionality written in a short amount of time and the code is short, expressive, smart and artistic. And at the same time, as a programmer, having great flexibility with what you can write.
In studying Common Lisp I was being exposed to the larger subject of functional programming and other functional programming languages. One of these functional programming languages was Haskell. I kept seeing and reading Haskell blog posts and webpages linked to on programming.reddit.com, probably Don Stewart's fault. Part of it is that I read a number of times that Haskell was a purely, lazy functional programming language. I'd figured out what a functional programming language was from Common Lisp. But what is a purely functional programming language? And what the heck is lazy? I just had to find out really what this means in terms of programming.
I've studied Haskell all August, and it is a lot harder for me to learn than Common Lisp, but is also really rewarding. It is really different and interesting. I want to know two or three programming languages really well, at least one of them to be a high-level programming language. I think this might be Haskell.
Haskell is also exposing me to a lot of other new things. A lot of things I didn't know anything about, but am slowly learning more about such as Lambda calculus, Logic, Type Theory and Category Theory.
This month I rediscoverd IRC. I've known about IRC for years but haven't really used it. In the past couple weeks I've been on IRC, channel #haskell. My nick is mudge (my name is also nick mudge). It has been great. I've gotten a lot of help and learned new things. I got to talk to new people that I now admire and know about. I got to talk to Peter Seibel who wrote Practical Common Lisp, and Slava Akhmechet, whose articles on defmacro I've really enjoyed.
![[Valid RSS]](/web/20190727193529im_/http://nickmudge.info/valid-rss.png "Validate my RSS feed")