JS and Scheme, the similarities


So I have been reading the awesome SICP book for some time now and the striking thing is the resemblance between JS and Scheme in some areas. Not surprising considering that Scheme was one of the major influences for the JS language. Thus, another reason to learn more languages to become a better programmer.

1. begin and comma operators

Scheme has the begin operator which allows you to evaluate a series of expressions and return the value of the last evaluated expression. This immediately struck me as being related to the JS comma operator which does exactly the same thing!

Code Samples


//JS

var x = 1,2,3,4,5;

x; //5

//Scheme

(define a

    (begin 1 2 3 4 5))

a; 5

One difference though is the fact that I find begin more useful in Scheme than its JS comma counterpart.

2. Type coercion

Due to JavaScript’s loose typing and implicit coercion, values can be truthy or falsy (e.g. undefined, null or 0). Idiomatic JavaScript leverages this coercion into false values and that’s why you see expressions like the below:


if(value) {

   console.log("Value is truthy!);

}

Scheme behaves in a similar way too – values are coerced albeit with more rigidity than JS.

(if null
   (display "Null coerced to true!")
   3)
; Null coerced to true!

3. Lambdas, first-class functions, closures and maybe lexical Scope

Some say JavaScript helped fuel the widespread adoption of lambdas in mainstream languages. It made people see the value of the hidden gem which hitherto had been languishing in the murky depths of academia.

Scheme and JavaScript do share first-class functions support, closures and lambdas. Although there is no lambda keyword in JS, anonymous functions essentially do the exact same thing. The introduction of let in ES6 should bring JS to par with Scheme’s let 

And that’s about it for now.

SICP Section 2.2: New ideas and thoughts about programming


Here are 5 points to think about, hopefully they’ll trigger an ‘aha’ moment.

1. Leveraging the ‘Closure’ concept in programming

I am not talking about the ‘closure’ concept from programming (the one that involves free variables). This refers to the ‘closure‘ concept from mathematics and the power it brings to programming languages.

Mathematically, a set is closed under an operation if carrying out that operation on elements of the set will always give a result that is also in the set. For example, addition of positive integers is closed under the set of positive integers (subtraction is not: 1 – 3 = -2; which is not positive). Thus you can infinitely add positive numbers without worrying about ending up with non-positive numbers.

Lets take this to programming: closed operations allow chaining because the result will be always be a valid value for further operations. Does this strike a bell? Think fluent programming, think jQuery chains. This simple concept allows very complex actions by leveraging simple data and procedures.

2. Simple it might seem, difficult it might be

I initially thought Ex 2.18 would be dead easy; it was simple: reverse a scheme list. I realized my folly after spending the better part of an hour battling the task. Unlike pointer-based lists in C-like languages, the Scheme list is a chain of pairs, each pair points to another pair and so on. This negated walking down the list and reversing pointer directions.

Recursion was tricky since getting the second half of a list pair (i.e. cdr list) brought the entire sublist instead of just the element! The reversal task involved the following restrictions:

  • No variables allowed
  • Only the top element of a sublist can be retrieved while walking down the list
  • The procedure should recursively construct a new list simultaneously
  • Retrieval of elements at arbitrary positions is difficult; although possible, the absence of variables makes this useless.

My first approach worked but created a wrong data structure; Alhamdulillaah I eventually got the right solution. An elegant solution I found online solved the reversal problem simply – reversing a list is equivalent to appending the first element of the list to the reversal of the remaining elements.

3. Languages influence thinking and problem modelling

Languages play a big role in the way we think and write code, most of us see programming tasks through an ‘imperative’ pair of glasses. Alhamdulillah the SICP book is giving me a new pair of glasses. Don’t we all need a new pair of glasses every now and then?

Imagine a simple task: calculate the sum of the squares of the odd numbers in an array. The snippets below show both the imperative and functional styles of solving the problem.

function isOdd(num) {
    return (num %2 ) === 1;
}

function square(num) {
    return num * num;
}

//imperative style
function sumOddSq(arr) {
  var sumOddSq = 0;
  for(var i=0, l=arr.length; i < l; i++) {
      if(isOdd(arr[i])) {
          sumOddSq += square(arr[i]);
      }
  }
  return sumOddSq;
}

//functional style
function sumOddSq2(arr) {
  return arr.filter(isOdd)
            .map(square)
            .reduce(function (val, acc) {
                return val + acc;
            }, 0);
}

sumOddSq([1,2,3]);   //10
sumOddSq2([1,2,3]);  //10

The imperative approach involves walking through the array, checking for odd numbers, squaring those odd numbers and updating the sum as you go along. Using a functional programming approach, the task involves filtering the sequence for odd numbers, mapping the filtered numbers to their squares and then reducing these squares to a sum.

Functional programming relies heavily on the map, reduce and filter concepts and most problems can be solved based on these building blocks. For tasks involving non-list-like structures, converters can be used to create sequences and also generate structures from list results.

Did you notice? sumOddSq2 chains array operations; the map, reduce and filter operations can be said to be ‘closed’ over the set of arrays. Thus the result of any of these operations is always an array and can be reused immediately.

4. Software engineering is still engineering

Even though software engineers manipulate bits and not ‘real’ hardware; general engineering concepts still apply. There are a couple of interesting similarities; for example in electronics engineering, the diode can be viewed as an if statement while filters can be viewed as ‘filter‘ logic. The electronics engineer uses a filter, the software engineer uses a filter function. Both combine them to build even more complex abstractions.

Another example is the computer system and the various dependent layers; a simplified complexity order is shown below:

Transistors -> Logic gates  -> Circuits -> Processors -> Computers -> Distributed Systems

The same applies to software engineering, an application can be seen as:

Values -> Methods -> Classes -> Models -> Subsystems -> Modules -> Applications

We all start from something simple and progressively add complexity, each layer being shielded from the layer below it. A computer engineer can swap processors without breaking a computer; so should a software engineer be able to swap out layers in his code without bringing down the application.

5. Recursion

The 8 queens problem is one that a lot of people are familiar with and as you guessed, there was an exercise on that. The solution was quite simple – recursively build the board starting out with one queen. As the board grows, filter out positions that have queens attacking each other, finally return the list of all positions that have safe queens.

The functional-programming styled solution involved enumerating all positions, creating a safe? function to determine a valid board, passing this function to the filter and then outputting the results. It is great to see how functions can be composed and how the basic functional programming support for map, reduce and filter enable even higher levels of complexity.

I must admit I struggled a lot with this problem as it was difficult to understand and debug – walking up the call stack did expose some of its intricacies but it’s amazing how simple and how yet powerful the results of combining these simple concepts.

Conclusion

And that’s about it. Next is section 2.3 with about 20 questions; I skipped about 2 or 3 questions in 2.2 since I didn’t really feel they were worth solving. I hope I can get 2.3 done by mid January insha Allaah and create another post then!

Related Posts

Here are a couple more of my SICP-themed posts

1. SICP Section 2.1 : Thoughts

2. 5 things I have gained from SICP: Section 1.2

3. SICP Section 1.3 : Thoughts and Concepts

SICP Section 2.1 : Thoughts


Alhamdulillaah I wrapped up this section a few days ago – 13 of the solutions are here (if you are curious enough); the other three need proofs and I wasn’t in the ‘mood’ for too much interval arithmetic. So what did I learn?

1. More Scheme

This chapter introduced the concept of cons, car and cdr  for manipulating pairs which in turn can be used to create just about any data structure.

  • cons – means construct, allows you to build a pair from two arguments
  • car – contents of address part of register, returns the first element of a cons pair
  • cdr – contents of decrement part of register, returns the second element of a cons pair
  • cadr – contents of address part of contents of decrement part of register; this is equal to (car (cdr value)); you can do things like caadr too – every extra a represents a car while a d represents cdr. Thus (caadr x) is equal to (car (car (cdr x)))

2. Abstraction

Abstractions provide elegant ways of solving problems. They allow the programmer to think at a ‘higher’ level without worrying too much about implementation details. This leads to a cleaner design and more flexible code.

Lets take the ‘xor’ logic operator as an example; assuming you need to add negative integer support to a positive-integer only multiplication system, there are two ways to do this:

  • Evaluate every possible combination, have four if/else blocks and then assign the right sign afterwards
  • Leverage the xor operation.

Here is the xor table:

x y x xor y
+ + +
+
+
+

This matches the four scenarios for multiplying two numbers. Thus, you can create a wrapper around the existing system for multiplication and then use the xor operator to find the sign of the output. Worth a thought isn’t it?

3. Architecture

There was a brief mention of the onion layer style of architecture which allows you to build software in layers – its main advantage is the ability to swap out any layer without ‘breaking’ the system.

Each level relies on the layer below it through a well-defined interface; you can swap layers as you think fit, you just have to follow the interface specifications. Another step in separating between data abstraction and implementation.

4. Church Numbers – a new numbering system?

The Church encoding system is a way of representing numbers and their operators in lambda calculus. The book introduces the Church zero and add-1 procedures first, I thought the zero procedure would evaluate to the value zero but was shocked to realize it was a procedure. Alhamdulillaah I finally got to understand it after reading Bill’s excellent post.

The main thing to know is this: It is possible to represent numbers even without using numbers!

Assuming a theoretical language that has only functions and no inherent support for numbers whatsoever; how do you add or represent numbers? Surprisingly this is easy to do – you could model numbers by counting the number of times you apply a function. This is what the Church numbers do – they apply input functions for a number of times that corresponds to the expected integer value.

The zero procedure takes in a procedure (which itself accepts another procedure) and calls it ‘zero’ times (never called); similarly, the one procedure evaluates its input once (that’s one right?). Generalizing these allow you to do addition and subtraction. While it was good to learn about lambda calculus however I wonder how real number arithmetic would be represented…

5. The woes of Interval Arithmetic

There were a couple of exercises on interval arithmetic; what struck me about this was the way small changes in calculation could lead to huge differences in results. Two algebraically equivalent formulas could lead to varying results due to overlooked ‘assumptions’.

For example, if for some reason x / x is not equal to one (can happen in interval arithmetic); then every operation that includes this division (implicitly or explicitly) can deviate from accurate results. The more the ‘precision-losing’ operations carried out, the more significant the deviation.

And that’s about it again. Section 2.2 has about 36 exercises and I hope to complete it by December insha Allaah. And yes, insha Allaah I’ll write about my thoughts again…

SICP Section 1.3 : Thoughts and Concepts


This section exposed me to the full power and beauty of functional programming. The expressiveness of using functions as values is awesome. For example, a sum of cubes function can use a sum function which itself relies on a reduce function. Think of higher order differentiation in mathematics and you do get the idea.

An interesting concept involves using lambda function as operators, if the value of an expression is a function, then it can be used as an operator! This pattern allows using functions the same way numbers and strings are used. A derived usage can be found in JavaScript, which allows invoking function expressions using the function invocation operator ().

A lot of programmers are familiar with callbacks (which pass functions into functions). However callbacks might mask the full untapped potential of functional programming. A callback can be passed a function as a value – it doesn’t necessarily have to be a number / string all the time. The other issue with callbacks is that they do not return values and thus limit function composition.

There are no limits to using functions as values (provided there is language support). Alhamdulillaah I got my eye-opening experience after solving exercise 1.45. The main points are

  • The repeated procedure accepts a procedure and returns a new procedure.
  • Repeated’s return value (a procedure) also accepts a procedure as input (a lambda) and returns another new procedure.
  • The final return value is then passed into the fixed-point procedure which does return a non-procedure value (although it can also be written to return a procedure).

The subtle trick was to realize that functions could be substituted with values and used in just about every way a value could be (provided you handle it right).

The amazing expressive power and flexibility comes at a cost though – first-class procedures are difficult to support in languages and this explains why few languages provide this. The main challenge is finding a way to safely store and retrieve the procedure’s free variables when it is not currently executing.

A free variable is defined on c2.com as any value that meets the following conditions:

  • It is not defined in the body of a function
  • It is not passed in as an input parameter
  • It is not available in scope at the point of usage

Alhamdulillaah I completed the chapter in two weeks (I initially though it would take four). Chapter 2 is next with about 92 exercises, about 14 weeks insha Allaah? We’ll see!

5 things I have gained from SICP: Section 1.2


Alhamdulillaah I finally completed section 1.2 of the SICP classic. I was amazed I took almost 150 days to complete 61 pages. I definitely need to sit up! Reading the text was not challenging, the bottleneck was ‘forcing’ getting myself to finish the exercises.

I was going to start on section 1.3 but I felt it would be better to reflect on the knowledge gained first.

1. A deeper understanding of procedures and their processes

Not all procedures are created equal – seemingly recursive procedure can be iterative in execution. Moreover, there is nearly always a way to make a recursive procedure execute in an iterative manner. This can lead to speed gains and also help you handle HUGE data.

Programming is deeper than I thought…

2. Mathematics

My Mathematical forays are usually related to Computer Science or Machine learning however I got to dabble into new fields. First was the Ackermann function; a fascinating recursive function which grows with mind-boggling speed – you have to think hard to grasp this. Next came primality testing and probabilistic approaches to prime number verification.

The Fermat test is good enough however it is fooled by the Carmichael numbers. To be sure, use the Miller-Rabin test.

I do not know how much of these will be useful in real-life but yeah… it is good to know.

3. Algorithms – exponentiation

The rapid exponentiation algorithm was an eye-opener – do stuff twice as fast :). Once you implement the ‘speed-up’ and ‘slow-down’ functions and handle all cases properly, you can take down exponentiation from a O(n) operation to a O(log n) operation. Combining this with a ‘tweaked’ recursive-but-iterative-in-execution procedure leads to ‘tales’ of joy…

It was also interesting to see how minor changes to code could wipe out performance gains made from clever algorithms. Exercise 1.26  showed how easy it was to lose the O(log n) gains from exponentiation by doing irrelevant work. A subtle ‘refactoring’ might have huge implications…

5. Perseverance

I initially find most exercises daunting and struggle to understand the task. I force myself to think about the problem for at most 15 minutes; if I still do not get it, then I allow myself to look at available solutions.

Alhamdulillaah I usually figure out the solution during the time window and then look up existing solutions to see other problem-solving approaches. I have also looked up solutions when I got stuck too – I was seeking ‘inspiration‘ :). It’s great to know we can solve most problems if we only persevere insha Allaah.

And that’s about it! Section 1.3 has about 18 exercises; since I typically solve an exercise in about 2 – 3 days (I have a 25 minute daily study schedule), I hope to be done with this section in about 4 – 6 weeks insha Allaah. Watch out for a new update then insha Allaah.

Here are my solutions on Github.

Here are a couple of my more academic-themed musings

1. Research is hard!

2. Wrangling with HUGE data

3. MOOC Review: Machine Learning

How to add in programming languages


This is a tongue-in-cheek attempt to expose programming language expressiveness.

1. Scheme

(+ 1 2)          
(+ 1 2 3 4)  
  • Characters needed to add n digits: + 3
  • Prefix notation allows passing in multiple operands
  • Prefix notation is not popular

2. JavaScript/Python/Ruby/Octave/Matlab

1 + 2
  • Characters needed to add n digits: + (n – 1)
  • Very simple and generally accepted
  • Infix form requires two operands leading to (n – 1) operators

3. Java/C#

//CSharp
class Program
{
  static void Main(string[] args)
  {
    Console.WriteLine(1 + 2);
  }
}
  • Characters needed to add n digits: N (where N is a largeeeeeeee number 🙂 )
  • Too verbose – you need a class to add two numbers

4. SQL

SELECT 1 + 2;
  • Characters needed to add n digits: + 8
  • Simple but not popular
  • Declarative nature can impact clarity

Do you know of any other language examples? Feel free to share in the comments!

Here are a couple of other posts you might also like:

Reading the SICP BOOK


I have been longing to read the Structure and Interpretation of Computer Programs (SICP) for a long time – a lot of great programmers tout it as one of the ‘books‘ to read. In May I completed JS Allonge (a somewhat challenging read but got to understand the Y-combinator Alhamdulillaah) and I felt it was a good time to learn more about the SICP book; afterall how many 30-year old computing books still remain relevant?

The general consensus is that SICP is a classic every programmer should read and that it’ll make you a better programmer by changing the way you think. Reading such glowing appraisals awakened my interest (who doesn’t want to become a rockstar programmer?) and I decided to do it. However, there is a catch – reading the book is not enough, you have to do all the exercises! So I resolved to do all the exercises and read for at least 25 minutes daily (1 pomodoro).

The exercises appear deceptively simple until you try to solve them! Then you realize they are just as deceptively difficult!! For example, an exercise asks you to find the two largest numbers out of  a set of three – I bet a lot of people can write this in their sleep. However since the book expects programs to be written in Scheme; and Scheme variables haven’t been discussed yet, you have to make do without variables – now try that!

The good thing though is that the exercises are designed to fit the current context and buttress learning. Mathematical concepts and computer science principles are expertly interwoven into surprisingly simple explanations and real-life scenarios. Scheme is a nice language too – provided you can get past the scourge of parentheses.

Solving the exercises has been another eye-opener; I typically have to force myself to persevere. Alhamdulillaah I have been able to solve questions I typically would think were beyond me (I am probably too lazy). If I can’t solve a question in 25 minutes, I look for a solution online (see resources below); at times, I just want to compare my approach to others.

Here are some programming-perception changing concepts I picked up in the past few months:

1. Scope

A scope is just a group of expressions in which a binding has a name; it really does not have to be a function or class.

2. Free and bound variables

Free variables are those not defined in a procedure while bound variables are defined in it. Imagine the procedure below

function variable(){
   var a =1;
   var b = 2;
   return a + b;
}

and are bound variables however isn’t; it’s a free variable. Now try to think of what will happen if the ‘+’ operator can be bound to another value (quite possible in some languages). The original procedure works properly because the free variables are what they are expected to be; if they are changed, then you end in no mans land. Powerful right?

3. Recursive/Iterative processes and procedures:

Most recursive procedures can be re-written to spawn iterative processes. While this involves a couple of tricks, the performance and memory gains might require such fixes. Also not every recursive procedure spawns recursive processes, some actually are iterative in execution (see tail recursion).

Resources

If you are interested in reading the SICP books; here are a couple of helpful resources

1. My SICP exercise solutions

2. Unofficial ebook version

3. Solutions to SICP Exercises

4. Bill the Lizard; he undertook the SICP journey before me

5. Eli Bendersky, he also undertook the SICP journey some time ago

6. List of solutions

Quotes from the SICP book

Programming is like chess; you might know the rules but not know the strategy, tactics and methods

The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity…

To become experts, we must learn to visualize the processes generated by various types of procedures. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior.

Conclusion

Finally, believe! You can do it,  just persevere when it gets tough…