One thing that strikes me is how much effort we humans put into writing highly precise rules for machines. As I grow older, one thing that preoccupies my thoughts is how I can effectively reduce the verbiage that the machine needs.
Current programming methodologies require an army of programmers. A ton of people to implement a solution to a problem. And, if I were to trust my intuition, the reason everyone underestimates the time to make something arises from a natural high-level view rather than a fine-combed every-detail accounted for view.
What has happened, then, to give a high level view is a massive number of functions. Really, a ton of functions. Highly specialized functions. Want to delete a file, there's a function. Want to list all folders, another function, etc. etc. there is little consistency amongst the APIs.
But, let's step back a bit. What are we actually working with? Linear algebra has this nice notion of a vector space. As long as certain basic rules are obeyed, then a set is a vector space. Then what is the verbiage that we see so often in programming languages?
First, the data. It's all dictionaries. An array is a dictionary with unsigned integer values as keys. A set is a dictionary with just keys, nil values. A queue is a dictionary with keys always increasing and the minimum key being removed... File systems are dictionaries of dictionaries. A 3D scene is a dictionary forming a tree of dictionaries.
We can even further simplify it to a tree. A binary tree. As a dictionary can be implemented using one...
If we can access all data uniformly, then what do we do with logic? Bring the most common logic into the API. Find through the file system is the same as find a node in a scene graph. This essentially forces consistency across the entire API.
If we want to drop the learning curve and increase the speed of development, then it is this that we must consider. Focus on what is peculiar to the software at hand, not get marred in the details that all software reinvents as a rite of passage.
Friday, October 18, 2013
Thursday, October 10, 2013
The Lambda Calculus and Lazy Evaluation
For quite some time I've been looking into building a programming language that is both functional and supports lazy evaluation. I may not have the energy to actually write the code, but I do keep thinking about it.
First thing I should have realized earlier: studying the theoretical foundations of functional languages (ie. The lambda calculus) would help me achieve my goals.
First, what is lazy evaluation? Essentially, an expression is only evaluated as long as the calculations lead to the final result. In a Haskell-like fictional language, I would say function "Pi" calculates Pi to an infinite number of digits. Then "take 100 Pi" would take the first 100 digits of Pi and stop computing any further digits.
My initial mental model of this process was very convoluted. Essentially, requiring back-tracking on the stack. Now, looking at the lambda calculus, it makes a lot more sense.
Recall that the lambda calculus consists of a series of variables and production rules. Rules are of the form: \xy.yx, where \ is a make-shift lambda, xy are the input, and yx the output. Essentially flipping the values.
Execution in a functional language starts with a function. Let's call it R. Well, R does nothing on its own, so let's evaluate it. We get T 3 P. Yup, same as the pseudo-Haskell above, except 3 digits. Let's try parsing this.
First, some syntax. : means element in a list. So x:P means x is the first element from P...
I expand it to something like:
(a:b:c.P)
At each step in T n, we take the head of the list from P and recursively call T (n-1). In the end, we are matching a set of 3 elements to the infinite list P. Notice that once P evaluates 3 elements, the matching is complete and any further evaluation of P is not needed.
This is what escaped me! That means structured properly I could evaluate and match expressions and get lazy evaluation for free! Or so I believe. I'll keep on reflecting on the corner cases, but for now "early match and discard" seems to do the trick.
First thing I should have realized earlier: studying the theoretical foundations of functional languages (ie. The lambda calculus) would help me achieve my goals.
First, what is lazy evaluation? Essentially, an expression is only evaluated as long as the calculations lead to the final result. In a Haskell-like fictional language, I would say function "Pi" calculates Pi to an infinite number of digits. Then "take 100 Pi" would take the first 100 digits of Pi and stop computing any further digits.
My initial mental model of this process was very convoluted. Essentially, requiring back-tracking on the stack. Now, looking at the lambda calculus, it makes a lot more sense.
Recall that the lambda calculus consists of a series of variables and production rules. Rules are of the form: \xy.yx, where \ is a make-shift lambda, xy are the input, and yx the output. Essentially flipping the values.
Execution in a functional language starts with a function. Let's call it R. Well, R does nothing on its own, so let's evaluate it. We get T 3 P. Yup, same as the pseudo-Haskell above, except 3 digits. Let's try parsing this.
First, some syntax. : means element in a list. So x:P means x is the first element from P...
I expand it to something like:
(a:b:c.P)
At each step in T n, we take the head of the list from P and recursively call T (n-1). In the end, we are matching a set of 3 elements to the infinite list P. Notice that once P evaluates 3 elements, the matching is complete and any further evaluation of P is not needed.
This is what escaped me! That means structured properly I could evaluate and match expressions and get lazy evaluation for free! Or so I believe. I'll keep on reflecting on the corner cases, but for now "early match and discard" seems to do the trick.
Subscribe to:
Posts (Atom)