This is my implementation with some extras like optional input to procedures, macros, templates, line break- and comment support.
https://github.com/imrehorvath/CS61A/tree/master/Logo
#UCB #CS61A #Scheme #Logo
Education
Why learning… 2nd Edition
Main Document
Appendix
Why learning about the big ideas in Computer Science already in an introductory course matters
Ruby is fun!
It’s so easy and natural to solve problems in Ruby!
Consider the problem of finding and printing the second prime number found in the interval 10,000 – 1,000,000.
Side note. One approach can be the usual imperative solution, where the different kinds of computations like enumerating the interval, checking for primality and collecting the solution are interleaving resulting in an effective BUT cryptic solution. It’s much harder to understand -and possibly modify later- the different parts if they are mixed together to form one big monolithic chunk of code. On the other hand one might want to express this idea using the sequence paradigm, where each phase of the computation is done by a function box, these boxes are linked to form a chain, which in turn represents the program. Though this latter approach is very expressive, easy to understand and maintain, BUT it can be very ineffective. Eg. When enumerating big amounts of data, no transition to the next function box is possible until all the data is computed. However there is a clever way to have the best from both worlds. It’s the stream paradigm as shown in the SICP. With this we gain the clarity and elegant style of programming from the sequence paradigm, and the effective computation from the imperative style at the same time.
Fortunately Ruby has lazy enumerators which can support the same idea. In Ruby using lazy enumerators it might look something like:
require 'prime' primes_in_interval = (10_000..1_000_000).lazy.select(&:prime?) p primes_in_interval.first(2)[1]
Without the .lazy method call it would filter the whole interval for primes and only when all the primes are filtered and collected into an array, could the printing of the second element be done. It’s a terrible waste. BUT calling the .lazy method on the interval -which returns a lazy Enumerator object- makes a huge difference, since now NO primes are searched and collected, UNTIL they are really needed. With this, only the first two primes are computed, which is a huge gain.
References
Recursive anonymous functions?
Introduction
The Lambda Calculus, invented by Alonzo Church back in the 1930s, can be referred to as the smallest universal programming language. It’s Turing complete, meaning everything which is computable, can be computed in it.
It has only a few basic constructs, like – anonymous – functions and function application. These are the primitives. By adding Church Numerals, representation of Booleans, conditionals, lists and recursion with the help of combinators, we get a fully usable language.
Functional programming was born to Lambda Calculus. Functional programming is getting more and more attention nowadays, because it makes parallel programming so much easier.
Recursion
Recursion is amazing, since it enables us to compute and process self-similar structures in a natural way. It also helps to solve a more complex problem by breaking it down into similar, but simpler problems to be solved separately. Finally recursion can be thought of an alternative to iteration.
Side note. The conventional programming languages are equipped with looping-constructs like, while, for, etc. The interesting thing is that it turns out these are unnecessary, since the same can be accomplished by using functions and function-application. By adding Tail Call Optimisation (TCO for short) and having the underlying system translate them to primitive loops in the machine language, we can achieve the same performance as we were using the usual looping-constructs to express iteration.
To get recursion working, we need to have a “handle” on the function itself. But functions in Lambda Calculus are anonymous. (Meaning, we cannot really refer to them by their names.) So how can we make it work then? Well, we can bind expressions to function parameters. That’s all what’s offered by Lambda Calculus. But as you will see shortly, it’s sufficient to make it work. U and Y combinators to the rescue!
The U combinator is a higher-order function, that applies its parameter to its parameter. It provides a way to get a handle on the function through parameter binding, hence making recursion possible.
Side note. The smallest non-terminating program can be written using the U combinator like this: U(U)
The Y combinator is a bit more complicated compared to the U combinator, and it’s better-known too.
The funny thing is that today’s programming languages, which are functional, or multi-paradigm but supporting the functional paradigm as well, are capable of this kind of programming. That’s because they are descendants of the Lambda Calculus.
Next let’s see how to do recursion with anonymous functions in some mainstream programming languages. And, also in Scheme for those who are not afraid of this beautiful, minimalistic LISP dialect.
Code Examples
Side note. While in Lambda Calculus we bind the name (parameter of the function) to the expression to which the function is applied, they’re bound to the values of the expressions in the following examples, since they use applicative order evaluation. That’s why it’s better to call these combinators applicative order combinators.
function (f) { return f(f); }
(function (f) {
return f(f);
}(function (h) {
return function(n) {
return n <= 1 ? 1 : n * h(h)(n - 1);
};
}))(5);
-> f { f.call(f) }
-> f { f.call(f) }.call(
lambda do |h|
lambda do |n|
n <= 1 ? 1 : n * h.call(h).call(n - 1)
end
end
).call(5)
(lambda (f) (f f))
(((lambda (f) (f f))
(lambda (h)
(lambda (n)
(if (<= n 1)
1
(* n ((h h) (- n 1)))))))
5)
References
About archiving my SICP related stuff on GitHub
Well, I have done some exercises offered by the books Simply Scheme and the SICP for my own personal development and joy.
One interesting example is the representation of pairs as procedures. Instead of using a data structure we can use ordinary procedures to achieve the same, with identical semantics.
;;; Procedural representation of pairs
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Only 0 or 1 is allowed as argument -- CONS" m))))
dispatch)
(define (car z)
(z 0))
(define (cdr z)
(z 1))
Another example
;;; Procedural representation of pairs (define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))
Or another example introducing mutation on top of that
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
((z 'set-car!) new-value)
z)
(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)
To see more, please take a look at: SICP and Simply Scheme.
Related stuff:
- MIT Scratch
- Snap!
- BJC course at UCB
- Morphic.js by Jens Moenig
About some of the Big Ideas in CS, based on the SICP
I created a new repo on GitHub, where I plan to collect some cool ideas in CS based on the influential work of Harold Abelson, Gerald J. Sussman with Julie Sussman, the SICP.
My goal is to write about these Big Ideas and also to show them in various programming languages like Scheme, Ruby, JavaScript, etc.
If you understand these concepts, then using them in different programming languages is easy, since you only need to learn the particular notation. (Of course only if the given language supports the particular feature necessary…)
It’s quite amazing, that there are only a few very powerful features required anyways. (Read the SICP to learn about them!)
My GitHub repo about the topic can be accessed here. Check it out!
Thinking about Software Engineering
Why companies are looking for coding skills in a particular programming language, instead of looking for understanding of the set of abstract ideas behind the programming languages?
When someone understands the big ideas behind, then picking up one particular language’s syntax and semantics is pretty straightforward. Given that you already know the concepts, pairing the language’s syntax with a familiar concept is the remaining work you need to put into.
The other way around, if you know only one or two languages with a limited set of paradigms and concepts behind, it is much harder to pick up UNDERSTANDING of other languages…
Programming languages can come and go, and you will be in big trouble if you lack understanding…
References
- Why Structure and Interpretation of Computer Programs matters, by senior lecturer Brian Harvey UCB
- Scheme vs. Python, by senior lecturer Brian Harvey UCB
Imre's blog 