Introduction to Systematic Programming – Locals & Abstraction (Week 7)

Dara Monasch / Thursday, August 22, 2013

Week 7 brought in the concepts of both local and abstract expressions. As seems to be the case with me, this week was half a review from other courses that was nice and refreshing, and then BAM, a new concept that completely threw me for a loop. Not complaining about this per-se, because I think it’s a great way to add things to my concept toolbox (reviewing old things and then throwing in something new), but it *is* a bit of a rollercoaster.

Lesson 1: Introduction to Local Expressions

The first exciting element in this week is another language upgrade! Now we’re moving into Intermediate Student Language. Score.

As far as local expressions, we learn in this introductory lesson that local expressions are expressions that have functions and constants that only work in one part of a program. That’s all we get here. More to come on this later...

Lesson 2: Local Expressions – Forming & Intuition

Upgrading our lives to Intermediate Student Language gives us the ability to utilize local expressions, as vaguely defined in lesson 1. Basically, local expressions are small, packaged expressions with their own functions and variables that cannot interact with the rest of the program, outside of their local container. Here’s the anatomy of a local:

In this example, both of the “defines” are definitions for variables that will only exist within this local container, meaning that if “a” is referenced on the top level of the program, aka, outside of this local, whatever we do to a within this local DOES NOT MATTER to the other instances of “a”. Why? Because if “a” is used in a local, it ONLY exists within that local, and has no interaction with any other “a” that might be within the program. This means you can also use “a” in all of your locals, and nothing will happen between them, as long as you structure your local correctly.

Lesson 3: Local Expressions – Lexical Scoping

Scope contours answer your questions about where you can access your local definitions. Lexical scoping states, essentially, that you use the definition of a function or variable that is within the innermost inclosing area to where your expression is being evaluated.

Lesson 4: Local Expressions – Evaluation Rules

As previously mentioned, locals are expressions, they don’t affect the things outside of their purview. Here are the steps for evaluation!

Renaming

- Take the definitions in the local, find all the references to them, come up with new, globally unique names for them and replace all instances of the old name with this new, unique one.

2. Lifting

- Move the renamed definitions into the top level.

3. Replace

- Replace the entire local with just its body, with the renamed definitions.

It’s interesting to note that by evaluating your local expression in this fashion, you’re actually eliminating its existence as a local, and thus your program could theoretically have been written in the Basic Student Language!

Lesson 5: Local Expressions – Encapsulation

Encapsulation is taking each part of a program and turning it into a little package that only interacts with a few small items on the top level. Essentially, it is making single functions with locals inside them. When you encapsulate a function, it’s important to remember that you can no longer access it globally. HOWEVER, this also means that as an encapsulated function, you don’t have to write signatures and tests, which will end up saving you lots of time. BUT, you may still want to test them, so don’t forget about doing that!

How can you tell if a function is a good candidate for encapsulation? WELL….

- Does it exist as one function with closely linked helpers?

- Does the outside program REALLY only need to call the one main function, not the helpers?

If you answered yes to both of these, you’re likely looking at a great candidate for encapsulation!

How do you encapsulate a function?

Group all functions you want to encapsulate together.
Open your definition with a new global function name and the necessary parameters.
Open a local expression and then the definition part of the local with [, right before the original function definition.
Close the definition part with a ] after the original function definition.
Add a trampoline call of the function, defined in the local, to the end.
Delete unnecessary tests, signatures and stubs.
Rename the tests and necessary stubs
RUN FREE! YOU GOT IT!

It’s also important to note that you can have encapsulation in your templates, but keep in mind that if you do this, it will disallow your ability to test for a base case.

Additional Notes from This Lesson:

Another topic covered in this lesson is refactoring, which is a structural change to a program that does NOT change the behavior of the program. You can, however, refactor something and ALSO change its behavior, but it’s not recommended to make both of these changes at the same time (it’s easier to make mistakes by trying to do too much at once!).

Lesson 6: Local Expressions – Avoiding Recomputation

FINALLY we’re getting to the concept of code efficiency in this class. YAY! This lesson begins with the idea that you should worry about efficiency of code AFTER your program works. In some ways I agree with this, particularly for beginners, but I also disagree a bit. I think code efficiency should be engrained from the beginning of your coding career, so it becomes a natural way of thinking, rather than an afterthought. That said, this lesson focuses on eliminating exponential growth. Essentially, the solution here is very situational, so I don’t want to go into it too much. However, the takeaway is that when you’re working with arity trees, if you can localize your searching, it will make your code more succinct and efficient. J

Lesson 7: Introduction to Abstraction

Abstraction, in programming, is the way to manage complexity in your program. #IAbstractedThatLessonForYou

Lesson 8: Abstraction from Examples, Part 1

When you’re abstracting, you need to pull out the common parts of functions into abstract functions. (Note: the differing portions are called “points of variance.”)

In a function, you rename it as more general, put a parameter to represent the point of variance, and replace the point of variance with the parameter that you renamed (remember to pass the parameter in any recursions as well!).

Why would you want to abstract functions?

WELL!

A higher order function can consume more than one function. It can also produce a function.

So, get used to it. It’s better. Promise.

Lesson 9: Abstraction from Examples, Part 2

Lesson 9 mostly works through a continued example from Lesson 8, so I’m going to operate as usual and get rid of the example run-through and give you the important takeaways:

Functions can consume other functions as arguments.
Abstraction exists and works in the majority of programming languages.
For abstractions, statements of purpose are very difficult to write, so start practicing.

Lesson 10: Abstraction from Examples, Part 3

Writing the signature comes last when doing an abstraction, because it’s even more difficult than writing a statement of purpose. Here’s a tip on how to work through it: Use type inference! Type inference goes a little like this:

Find the most basic thing that a function produces, that becomes the result in the signature.
Find the arguments that are passed/required. Those are the argument types for the signature.

It sounds easy, but there’s so much going on with abstraction that it can be pretty disconcerting. Don’t get discouraged, just try and focus on simplifying what you’re working on, as you do with the entire design recipe theory, and you’ll be just fine.

Additional Notes from This Lesson:

When a function is passed as an argument, write its signature in () in the larger signature.
Lists can be written in an alternate way. You can now use (listof X) in place of ListOfX

Lesson 11: Using Built-In Abstract Functions

Map and Filter are two of the more commonly used built-in abstract functions, and the language page in the coursera course lists all of them. (If you’re not taking the coursera class, here’s an external link you can check out with the same info: BSL Built-In Abstract Functions.)

The built-in abstracts are pretty sweet, and the reality is, if it’s pretty generic feeling, trust your intiuition and check out the list – it probably is a built-in!

Lesson 12: Closures

Sometimes the function you’re passing as an argument to an abstract function doesn’t exist yet…. If this is the case, you can always define it with a local.

HOWEVER

In some cases, you don’t have a choice. You MUST stop and define it.

When is that?

When the body of a function you want to pass to an abstract function refers to a parameter in the outer function. The function definition of the outer function thus closes AROUND the inner one, making it a closure. (Remember that lexical scoping? YEAH!)

Lesson 13: Abstract Fold Functions

This lesson gives a quick overview on going directly from templates to abstract functions, literally cutting out all of the goo in the middle, optimizing your time writing your code. YAY. In short, a fold function is an abstract function based directly on the template.

Week 7 Summary

As I mentioned at the start, this lesson was looooooooooooooooooong in the second half, because a lot of it was new to me. If you have any tips or tricks of your own related to abstract functions, let me know! Also! Week 8 is the last week of class so the next blog will be the last in the series. Don't worry though, I have lots of plans for upcoming entries. :)

Questions/Comments?

Feel free to comment here on my blog, or find me on Twitter @DokiDara.

By Dara Monasch