Re-learning computer science from a different perspective

9 posts


I did an undergrad in computer science. I learned about deterministic finite automata, nondeterministic finite automata, Turing machines, universal Turing machines, diagonalization, countability, the halting problem, Chomsky's hierarchy, and pumping lemma. (I forget what the last one was about, I'll have to review)

After hearing about the superiority of functional programming, and developing a curiosity in it, I started studying it's foundations: the lambda calculus devised by Alonzo Church.

I just googled a few links and read up on things after the course of a week in order to get what's going on. (I like sleeping on things. I find it makes it easier to progress the very next day)

I was stuck today for about 20 minutes trying to understand how the successor function is defined.

I was stuck on the following. Actually, this is the example that helped to make things clear. Other examples use different notations and it was probably messing me up.

succ c2
= λn. λs. λz. s (n s z) (λs. λz. s (s z))
-> λs. λz. s ((λs. λz. s (s z)) s z)
-> λs. λz. s (s (s z))
We get from the first line to the second line with beta-redex and likewise from the second line to the third.

We have the form λx.y(z)
Where λ is the statement for a function. (functions are not named in this language, they are anonymous)
x is the formal parameter for the function. In lambda calculus, functions only have one parameter.
y is the body of the function.
z is an expression for which the function λ is applied to.

Any function of this form: λx.x is the identity function. Any expression that this function is applied to returns the expression.
λx.x(z) = z
λy.y(x) = x

The two functions above are both the identity function. Since they are functionally equivalent, we say that they are alpha-equivalent. Any two functions which act the same on all applications are said to be alpha-equivalent.

The application of a function to an expression is a beta-redex.
To perform a beta-redex on the above, we substitute all occurences of the argument (the first x) in the body of the function (the second x) with the expression that the function is being applied to it (the y)

λx.x(y) = y
λx.z(y) = z
λy.y(x) = x
λw.y(y) = y
λx.xv(y) = yv
λp.qrtp(ff) = qrtff

and so on.

Will add more later on so that we can get back to my original problem.


Also, a little more on beta reduction: (page 5)

λx . t
Occurences of x in the body t are bound .
Nonbound variable occurrences are called free .
( λx . λy . z x ( yx )) x

The general rule is, if a variable is enclosed by a lambda statement, then it is bound. We see x and y enclosed in λx and λy above.

In the following, the first x in the left expression is bound, and the y is not. The y is bound in the expression on the right.
( λ x.xy)( λ y.y)

We should be careful when performing substitutions to avoid mixing up free occurrences
of an identifier with bound ones. In the expression
( λ x.( λ y .x y )) y
the green y is bound , whereas the y at the right is free . An
incorrect substitution would mix the two identifiers in the erroneous result
( λ y.yy)
Simply by renaming the bound y to t we obtain
( λ x.( λ t.xt))y = ( λ

The renaming works because of alpha-equivalance. When we swap the bound "y" variables for the bound "t" variables, we are not changing the meaning of the statement.


Next post I do some more beta reduction, and then eta reduction. After that, we define numbers (church numerals)

harrison partch
Ben S. Kanake

i can do all this shit with my ALPHA CALCULUS. it's entirely based on the NEG operation.


I tried learning Lisp, but got distracted because lisp hackers suggest learning to use Emacs before doing Lisp. Since I am familiar with the editor wars (emacs vs. vi) and I was being pushed in one direction, I started learning about the editors.

After several bouts of using Vi, and hating the whole edit vs. command mode things, I decided to give Emacs a shot. I'm liking it. A lot.

This nicely ties back into the "different perspective" of CS, because Emacs is primarily a Lisp interpreter. Lisp is a functional programming language inspired by the lambda calculus. Emacs has it's own dialect of Lisp, called elisp. Basically, there are programs within Emacs (the main one being a text editor) and other programs. I've become pretty good with the text editor, I've gotten used to the built-in directory management/navigation program, and now I'm starting to use it as a mail client. Soon, I'll be adding my own functions which will be available for use in these programs.

I really like how it handles configuration. Emacs loads up, reads it's init file, which points to my emacs init file in the dropbox folder, and then all the configuration options and functions are read from there. The best thing about all this, is that even if my computer gets wiped out, I can just re-install emacs and I'll have all my configuration options and functions ready for use again. I'll never have to re-configure for my email again. I won't have to code up functions again for some new programming environment. I won't have to re-learn a new editing tool, or deal with the quirks of a new OS or GUI. Most of the commands in emacs that I use have been there the last 20 years, and they won't change. In fact, other then web-browsing or playing games, I do pretty much everything in the command line and in emacs. (still need to find a decent IM program or two to run within emacs)

Now, I am learning/getting used to elisp, since it's necessary to use for configuring emacs. Being able to configure it gives me MORE POWER.

I will learn another lisp dialect next. Scheme. I start here: and move on to "The Seasoned Schemer" next. After this, I will start getting more comfortable with Clojure or Haskell.

blaq ghetto orgies

nerd, neckbeard fagot



its simple LAWGIC