connections

the rules of how to compose (and decompose) expressions

abstract algebra

combinators

scheme lists

a scheme list is a union of just the empty list and pair types.

with the pair type, think of it as a daisy chain, the daisy chain has 2 ends, it is a pair type of daisy and stalk and this is all you need to build a chain

Follow the Grammar!

When defining a procedure that operates on inductively defined data, the
structure of the program should be patterned after the structure of the data.

• Write one procedure for each nonterminal in the grammar. The procedure will be responsible for handling the data corresponding to that nonterminal, and nothing else.
  
• In each procedure, write one alternative for each production corresponding to that nonterminal. You may need additional case structure, but this will get you started.
  
• For each nonterminal that appears in the right-hand side, write a recursive call to the procedure for that nonterminal.

Recursion

n > Recursion provides a data-structure for free, the call stack

so linking Recursion to Induction,

the call stack gives you an isolated scope in which you can have the next n in the sequence [nb. in computer the sequence can be any itterable string array etc]

and your function(s) can run in that scope

the return back to the previous step can determine the combining operator.

Summary of Induction

step 1 – show the base case u(1) holds

step 2 – assume that (the thing you are trying to prove) is true for u(k)

step 2 – prove it is true for u(k+1) normally you will use the assumed truth of u(k) to do this.

a common strategy it to look at the difference between u(k+1) and u(k) – try to extract u(k) in the formula for u(k+1) and then substitute the occurance of u(k) with the (thing you are trying to prove)

eg. prove that 17^n is odd

17 ^ 1 = 17 — 17 is odd

formula for odd = 2p-1

assume 17^n is odd

so u(n) = 17^n = 2p-1

u(n+1) = 17^(n-1)

u(n+1) = 17 * 17^n

u(n+1) = 17 * (2p – 1)

any multiple of 2 odd numbers is odd

Basic Induction

A typical induction problem is a two-step problem.

The first step is to find a pattern.

The second step is to prove that it holds.

Induction is a proof technique, not a discovery technique, so it applies to the second step, not the first.

Mathematical Induction

The Principle of Mathematical Induction:

Suppose we have a row of dominoes;
– with each domino labeled by a positive integer.

Suppose also that the dominoes are arranged so that
– (a) ​If domino n falls, it knocks over domino n + 1.

Now suppose that
–  (b) ​The first domino falls.

What will be the result? Clearly it will be that All the dominoes fall.

This is nothing more or less than the principle of mathematical induction.

Let’s formalize this.
– Let D(n) be the statement that domino n falls.
Condition (a) is the statement that If D(n) is true, then D(n + 1) is also true,
Condition (b) is the statement that D(1) is true
– and our conclusion is the statement that D(n) is true for every positive integer n.(1) If P(1) is true

(2) if P(n) is true => P(n+1) is true
conclusion: P(n) is true for all positive integer n.So we can say:(1) The first domino falls

(2) if domino n falls, it knocks over domino (n+1)

Conclusion: All dominoes fall.

Condition 1 is called ‘the base case’ – “the first domino falls”
Condition 2 is called ‘the inductive step’ – if domino n falls it knocks over domino n+1

CLEAR?

 

To emphasize that ‘if a domino n falls it knocks over domino n+1’ is a conditional one, and that is it’s power, we are allowed to assume that ‘domino n falls’ is true to prove that ‘it knocks over all the dominos’

It’s usually easy to prove the ‘base case’ is true (the first domino falls) the work comes with showing the inductive step is true.

The Type System

The Type System helps us remove invalid programs from the set of programs that can be generated from the Grammar.

It is part of the static symantics.

Programming Languages

One can think of programs as strings of lexemes rather than of characters

concepts of programming languages – Robert W. Sebasta

Notes from DDD

The most significant complexity of many applications is not technical. It is in the domain itself, the activity or business of the user, the business logic or business rules.