Clojure(Script) calculator

core.cljs

(ns calc.core)

(comment
  The art of programming is very difficult to explain.
  Without concrete examples, explaining programming is
  similar to explaining "what does the ocean taste like"
  to an alien who cannot taste salt.

  The simplest definition of programming is to say it is
  simply telling a computer what to do in a very precise way.
  This is 100% true, but not very insightful. It begs the questions:
  "What can a computer do?" and "how do you tell a computer to do things?"

  In essense, a computer can store information as a collection of Zeroes and Ones,
  and it can process that information. All of programming is the art of
  collecting zeroes and ones into a computer and then telling the computer
  how to transform those zeroes and ones into different zeroes and ones.

  For example, when you are using an old fashioned calculator,
  and you press the 1 button, then the plus button, then the 1 button again,
  you are telling the calculator's processor to take two numbers and add them.
  Assuming the calculator is an 8-bit calculator, which means that the number
  1 is represented internally as 00000001, as opposite to a 16-bit calculator,
  which stores 1 as 0000000000000001, then the calculator simply
  add 00000001 to 00000001. Since the computer processor and memory
  can only store zeroes and ones, there can be no 00000002, so the 1
  carries, making 00000010.

  If you've ever seen the annoying shirt, "There are 10 kinds of people, those
  who understand binary and those who do not," then you'll now realize that
  10 in binary (base 2) equals 2 in base 10 (our normal counting because we have 10 fingers).
  To the computer, 000000010 is the same thing as 2.

  Many kinds of information can be stored as a collection of zeroes and ones.
  For example, if you take every letter in the alphabet, and associate it with
  an integer value, you can then represent english text with zeroes and ones.
  In fact, that's exactly what ASCII does - for all 256 possible permutations of
  eight zeroes and ones, there is a textual character associated with it.
  As an aside, in our modern attempts to open up computer text to every language
  on earth, including emoji language, we have had quite a bit of trouble
  transitioning our computer programs which are used to the simplicity of ASCII
  and converting them to use a much more flexible and memory expensive solution,
  known as Unicode.

  So a computer can store information, and it can perform operations on that
  stored information. Thus, programming is the art of collecting and transforming
  data in some meaningful way. For example, Facebook collects usage information,
  such as when you load the website, when you scroll on the news feed, and when
  you send a message to another Facebook user. From these individual events, they
  are able to answer important questions such as, "How addicted to facebook is Nicholas?"
  The answer? Very.

  You may have heard the term "algorithm" before,
  and it may have been explained as "a series of steps which a computer performs
  in order to do... something." And this is true, but relatively unhelpful to the
  novice programmer. Put differently, an algorithm takes structured data and
  transforms it in some way, though it doesn't necessarily change the original data
  structure. The important thing about algorithms is that they operate on data
  independently of the computer which runs the algorithm. Any human could follow the
  algorithm's steps and perform exactly the same operations, in the same order, as the
  computer would, without ever needing to pause and think. Computers aren't naturally
  smart, they merely are able to transform data very, very quickly.

  Sorting algorithms are quite popular in basic computer science courses because there
  are many different ones, with different strengths and weaknesses, and they operate
  on the simplest data structure I know of: the ordered list. Ordered lists have many names
  and even more implementations. There is the linked-list, the array, the vector, etc. but
  fundamentally, they all store bits of data in a specific order. A sorting algorithm
  just sorts a list. But because a sorting algorithm is generic and will work on any list,
  you also need to provide the algorithm some notion of order, such that the algorithm
  knows that one comes before two and "apple" precedes "banana". Most sorting algorithms
  thus require two pieces of data in order to function: a list and a comparator.

  What does the comparator do? Well, if you have a collection of names stored in a list, and you want an
  alphabetical list, you would use a comparator that is able to tell the algorithm that
  "apple" should come after "aardvark" but before "banana." That comparator would need to use
  an algorithm which understands the order of the alphabet in order to work.

  A simpler comparator can sort integer numbers. A computer can easily compare two numbers and
  tell you which is larger, because 01000000 has a one further to the left than 00010000.

  So algorithms transform data structures, and a computer can store data and execute algorithms
  on that data. Most everything can be represented as data. For example, inside the computer
  which you are reading this on, there's a data structure known as a "screen buffer" which does
  nothing but hold the data which the computer's screen transforms into light waves which find
  their way into your eyes. Some data structures are simple, such as the list, and some are
  a bit more complicated, such as the bloom filter. A bloom filter is a fairly interesting
  and strange data structure which can tell you if you have ever given the bloom filter some
  other data structure before. Bloom filters usually sit on top of a database and filter out
  requests for information which is 100% sure not to be in the database.

  Bloom filters are able
  to use significantly less memory than the database because they are a probabalistic data structure,
  because sometimes it will tell you the data exists in the database when it does not, in which
  base the program will have to wait for the database to fully complete a data query or lookup
  before being told that the data doesn't exist.

  So data structures and algorithms are important because they allow us to abstract
  our mental models away from the "bare metal", that is, the fact that all the computer is doing
  is storing and transforming zeroes and ones. With enough data structures and algorithms,
  you could build Photoshop or a Web Browser or a MMORPG from nothing but zeroes and ones,
  but it would take you a long, long time.

  Thus, programmers work at a much higher level of abstraction than the computer does. In this way,
  we trade control of the computer for productivity. It is through layering our abstractions
  that we gain massive productivity boosts. Thus, as a programmer, part of our art involves
  discovering and refining abstractions which are relevant to the program we want to build.

  In general, a computer program solves some domain of problems.  Effective programmers write
  programs by first understanding the problems they are trying to solve, and then building
  data structures which represent the domain, and algorithms which can transform those data
  structures. For example, Photoshop manipulates millions of individual bits of color, known as pixels,
  very quickly. A pixel can be represented as a list of the amount of each primary light color
  which goes into making some color on the screen. Since humans are trichromatids, we see light
  made up of 3 colors: red green, and blue, and so a pixel is simply 3 numbers in order.

  An image, then, is just a list of pixels. Usually, the list is broken into sub-lists, because images
  are two-dimensional and it's easier to see that [[0 0 0] [0 1 0]] has a 1 in the bottom middle, as opposed to
  [0 0 0 0 1 0]. In general, photoshop users think of it as an Image Manipulation tool.

  What about the abstrctions which photoshop provides to manage the domain of "editing pixels"?
  Photoshop has layers, paintbrushes, filters, and many other tools, all of which
  allow an artist to directly manipulate pixels in a meaningful way. A layer is a group of pixels which should stay the same
  distance from each other. A blue filter is like a layer that sits on top and makes all the pixels
  a little bit more blue. It does this by increasing the amount of blue in the pixel's data structure.

  The paint brush tool is especially interesting, because it can apply any color or shape directly
  to the image, allowing artists to create digital works just as they would with physical medium
  such as paint or ink.

  The programmers behind photoshop don't need to reinvent the wheel every time they want to add a new
  kind of paintbrush. Instead, they only need to change the paintbrush's shape. This is because they
  built photoshop with very flexible abstractions. If you've ever fine tuned the opacity, size, and
  orientation of a brush, you've directly manipulated the brush's underlying data structure, and photoshop's
  algorithms are generic enough to work regardless.

  In order to give you a concrete example of what it means to program by layering abstractions, I've
  built a very simple calculator using the Clojure language. The problem domain is simple: performing
  arithmetic on integers. In order to make this interesting, my core abstraction involves counting up
  or down by 1. From this, I build addition, subtraction, multiplication, truncating division, exponentiation,
  and logarithm functions. I chose clojure because it is a simple enough language to understand
  if you are willing to take some time to flex your brain.


  The code is short but very dense, and every line matters, so don't worry about being confused. Any lasting
  confusion is my fault, for not explaining clearly enough.
  )

(comment
  The first and only thing you must understand is that in clojure, functions operate on data.
  Clojure is a Lisp dialect, which means that it uses parentheses to group function statements.
  A function statement is constructed by an opening parenthesis, then a function name, then some
  data to give that function.

  For example, to add one and one:
  (+ 1 1)

  From there, you can add one and two:
  (+ 1 (+ 1 1))

  or

  (+ 1 1 1)

  or

  (+ 1 2)

  A function is a bit of code which, when given data, will transform that data into something else.
  You can think of functions as reusable steps, and you can compose functions together freely in Clojure.

  Clojure lets you define values as well
  (def two (+ 1 1))
  (= 3 (+ two 1)) ;; = is a function which checks equality, and in this case becomes the  primitive value "true"

  Of course, you can define functions too
  (defn addOne [a] (+ 1 a))

  defn is a special form known as a macro. A macro is code that writes code, because computer code is just
  data, and why should programmers have all the fun?
  In this case, the macro would replace our defn with

  (def addOne (cljs.core$macros/fn ([a] (inc a))))

  As you can see, the def function associates some human readable name with some bit of data, thus bridging
  the gap between the human and the computer.

  Clojure's core library, which is the code we always have available when we write clojure, is expansive.

  For example, the addOne function we defined earlier is included, and it's called "inc", for "increment".
  It has a sister function "dec", for decrement, which subtracts one from a number. These two functions
  serve as the basis of my calculator which calculates by counting up and down by one.

  I chose a calculator because we all know what the functions should do, and so you are free to focus on
  learning how to read the clojure code and understand how I build a domain specific language for basic
  arithmetic.
  )

(comment
  First, we define addition. Note that I don't handle adding negative numbers in any way.

  For us, addition requires counting up from some number a, by one, b times.

  The easiest way to express that notion with Clojure is through a technique known as recursion.

  You'll notice that so long as b is greater than 1, the add function calls itself after adding
  one to a by removing one from b.

  If b is equal to 1, then simply increment a. In recursive programming, this is known as the base case,
  because we stop calling the add function, and instead provide it with a solid value.

  Don't worry if that's confusing. Recursion causes a lot of people to drop out of Computer Science courses.

  In essence, recursion involves taking some large problem, like adding 5 to 4 (+ 4 5) and breaking it into
  a simpler problem, (+ (inc 4) 4), until you have made the problem so small that the answer is obvious:
  (inc (inc (inc (inc (inc 4))))).

  In the following definition of add, I've directly inlined the "body" of the add function a second time,
  so that it becomes obvious that recursion is a repetitive operation.

  (defn add [a b]
  (if (> b 1)
    (if (> (dec b) 1)
      (add (inc (inc a)) (dec b))
      (inc (inc a)))
    (inc a)))

  And once more because I can:

  (defn add [a b]
  (if (> b 1)
    (if (> (dec b) 1)
      (if (> (dec (dec b)) 1)
        (add (inc (inc (inc a))) (dec (dec (dec b))))
        (inc (inc (inc a))))
      (inc (inc a)))
    (inc a)))

  To get back on topic, addition is simply repeatedly counting up, by one, from some first number a, b times.
)


(defn add [a b]
  (if (> b 1)
    (add (inc a) (dec b))
    (inc a)))

(comment
  subtraction is the opposite of addition, we count down from a instead of up)

(defn subtract [a b]
  (if (> b 1)
    (subtract (dec a) (dec b))
    (dec a)))

(comment
  summation is simply repeated addition. In the function definition's binding vector, the [& args] is
  a special form which lets us know that args is a list of all the arguments passed.

  (= 3 (sum 1 1 1)) ;; true

  Note the keyword "reduce", which is doing all the heavy lifting here. Because our addition function only
  allows us to input two values, if we want to add three things, we would have to write

  (add 1 (add 1 1))

  which is quite a pain.

  "Reduce" is a function which reduces an entire collection or list into a single value.

  When you give a function two arguments, as in (+ 1 1), it only returns a single value, 2.

  Reduce takes advantage of that by recursively pulling values out of the collection and
  adding them to the reducing function.

  Every time the reducing function returns, reduce uses the return value, also known as the
  "accumulator",  as the starting point for the next step in the reduction.

  By understanding reduce, we can easily take a function which works on two arguments, and make it
  work on infinitely many.)

(defn sum [& args]
  (reduce add args))

(defn diff [& args]
  (reduce subtract args))

(comment
  just as addition is repeated counting by one, multiplication is repeated addition by some number.

  Strictly speaking, to multiply four by five means to create five groups of four,, then sum all those groups.

  In clojure, we can use "repeat" to build a vector for us, and we can use "apply" to allow our summation
  function to accept this vector (normally, a vector counts as one argument. Apply "unpacks" that vector for us.))

(defn product [a b]
  (apply sum (repeat b a)))

(defn trunc-div [a b]
  (if (>= a b)
    (let [c (subtract a b)]
      (if (>= c b)
        (inc (trunc-div c b))
        1))
    0))

(defn square [a]
  (product a a))

(defn exp [a b]
  (reduce product (repeat b a)))

(defn log [a b]
  (let [c (trunc-div a b)]
    (if (> c 1)
      (inc (log c b))
      c)))

(exp 2 4)
(log 16 2)
(log 16 16)
(= 2 (log (exp 2 4) 4))

(def square (partial #(exp %2 %1) 2))