ljpurcell

SICP Notes: Chapter 1 Section 1

#js #ocaml #sicp #functional programming

The first chapter is called Building Abstractions with Functions and contains three sections.

The Elements of Programming

I want to reiterate once more. The theme of this chapter is Building Abstractions with Functions, and this section is called The Elements of Programming. It’s important we remember that as it provides useful context for the information and why we are covering it.

In short, this section brings awareness to the primordial pieces of a programming language, and how we can use them to construct ideas and guide computational processes.

The authors state:

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:

Primitive Expressions

The primitive elements of a programming language are the smallest units we can use to create our computational process. There are 3 of these we need to be aware of.

1. Literals

These are literal values such true, 123, and 3.14.

2. Bindings

Values associated with (i.e., bound to) identifiers, such as const x = 6 (JavaScript) and let age = 31 (OCaml).

In procedural languages these are referred to as “variables.” Functional languages still use this nomenclature due to how pervasive it is, but the terminology betrays the reality.

Purely functional languages do not have assignment statements. Assignment statements create a side-effect; something has changed within the state of the program after it is run. These kinds of functional languages (again, often referred to as “pure”) do not have side-effects; they strive for platonic mathematical ideals. If something is something, then it is that something for the course of the program. It doesn’t change from one moment to the next. Computer programs of this type are declarative statements of fact that produce a result, as opposed to a sequence of statements that manipulate values.

As we will see, OCaml is a predominantly functional language, but it is not pure. OCaml has many procedural escape hatches - for the purpose of making it a more useful language overall. As such, it allows for bindings but these are immutable by default. A sensible middleground.

JavaScript is probably best described as a procedural language with a decent chunk of functional qualities. It has various types of bindings, let, val, and const. However, as SICP emphasises the ability to easily reason about programs - a strength of functional programming - the authors of the JS edition refrain from using let and val. They only use const, better mimicking the original Scheme version.

A JavaScript example from the book:

const pi = 3.14159;
const radius = 10;

pi * radius * radius; // 314.159

const circumference = 2 * pi * radius;

circumference; // 62.8318

Relevant quote:

Constant declaration is our language’s simplest means of abstraction, for it allows us to use simple names to refer to the results of compound operations, such as the circumference computed above. In general, computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them. Indeed, complex programs are constructed by building, step by step, computational objects of increasing complexity.

Section 1.1.2 - SICP:JS

3. Conditionals

In order to construct programs that can do meaningful things, we need the ability to make decisions and conditionally execute code. For this we have if/else constructs that are familiar to essentially all languages.

However, rather than the C-like syntax of if-gates, the JavaScript version makes use of the ternary operator. The reasons for this is it better aligns with the theme of SICP, striving for simplicity and conciseness, as well as the similarity to expression-based conditionals in functional programming.

In JavaScript this looks like:

const can_drive = is_adult ? true : false;

In OCaml we have:

let can_drive = if is_adult then true else false

These constructions can then be joined together to enable more complex conditional logic.

The Means of Combination

Combinational operators are how we produce compound expressions from the primitive elements and allow us to begin the journey from simple and silly programs to complex and meaningful.

Noting, though, that not all simple programs are silly nor does complexity necessitate meaning.

We have 2 primary ways of combining primitives.

1. Arithmetic operators

The expected+, -, *, /, for addition, subtraction, multiplication, and division, respectively. Modulo is% in JavaScript and mod in OCaml.

Notably, OCaml has specific operators for floating-point arithmetic. These are the same, only followed by a period (i.e., +. for addition).

As such, and due to its static typing, the following expressions are invalid OCaml syntax:

(* integer operator being applied to float operands *)
1.0 + 2.0;;

(* float operator being applied to integer operands *)
3 *. 100;;

(* mixing integer and float types *)
100 / 2.5

2. Logical operators

All the usual suspects are presents when it comes to logical operators. There’s&& for logical-and, || for logical-or, === (JavaScript) and = (OCaml) for equality, !== (JavaScript) and <> (OCaml) for not-equals, >= greater-than or equal to, etc.

Note: Both JavaScript and OCaml have another type of equality check, == which represents loose equality in JavaScript and physical equality in OCaml, but neither are relevant for the purposes of this section.

The Means of Abstraction

Abstraction is where things start to get really powerful. Through abstraction, we can encapsulate complete units of functionality, often called a module, that may be comprised of many smaller but related pieces of functionality.

When using abstraction effectively, one can user-defined functionality as if they were native to the language and computing environment. This can allow for exaggerated productivity and readability of programs.

But abstraction is not without its risks. It can easily distort a programmer’s intentions and make deciphering code a nightmare. One of the goals of SICP is to gain an appreciation, almost an aesthetic taste, for what good abstraction looks and feels like.

At this stage, we are only exposed to one method abstraction, which is defining functions.

Defining Functions

The definition of functions allow us to give meaningful name to a series of compound expressions, which may include other function calls (including the very function being defined).

This allows us, for example, to compute much more complex mathematical results with the triviality of calling the addition operator on a pair of operands.

In JavaScript we can calculate the square of a number, as well as exponentiate a base to power using the following:

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

// recursive
function exponentiate(base, power) {
	return power === 0
		   ? 1
		   : power === 1
		   : base
		   : exponentiate(base * base, power-1);;
}

square(5); // 25
exponentiate(3, 4); // 81

And in OCaml:

let square n = n * n;;

(* recursive *)
let rec exponentiate base power =
	if power = 0 then 1
	else if power = 1 
	then base
	else exponentiate (base * base) (power-1)
;;

square 5;; (* 25 *)
exponentiate 3 4;; (* 81 *)

Unfinished beneath here - published anyway :)

Evaluation

Functions as black box abstractions?

Exercises

Exercise N
Description of the exercise goes here