![[Home]](http://www.bayleshanks.com/cartoonbayle.png)
Table of Contents for Programming Languages: a survey
https://en.wikipedia.org/wiki/Structured_program_theorem
" The structured program theorem, also called Böhm-Jacopini theorem,[1][2] is a result in programming language theory. It states that a given class of algorithms can compute any computable function if those algorithms combine subprograms in only three specific ways. In other words, any algorithm can be expressed using only three control structures. They are
Executing one subprogram, and then another subprogram (sequence)
Executing one of two subprograms according to the value of a boolean expression (selection)
Executing a subprogram until a boolean expression is true (iteration)Note that these can be represented, respectively, by the concatenation, union, and star operations of a regular expression. "
the construction to transform a procedure into one using only these 3 is:
(note: i think a 'while' fulfills both of the last two conditions; you can do 'if' with 'while' like this:
if condition: stuff
replaced by:
x = condition while x: stuff x = 0
)
goto considered harmful
finalizers etc during unwind?
Also called TCO or tail call elimination.
clojure recur: Clojure does not do implicit tail call optimization, but for direct recursion (where a function calls itself recursively; as opposed to mutual recursion, where two or more functions call each other recursively), one can get the same effect with 'recur'. "Evaluates the exprs in order, then, in parallel, rebinds the bindings of the recursion point to the values of the exprs. If the recursion point was a fn method, then it rebinds the params. If the recursion point was a loop, then it rebinds the loop bindings. Execution then jumps back to the recursion point" -- http://clojure.org/special_forms#recur. What that means is that (todo: i think) is that when the compiler sees 'recur', it traverses up the chain of containing lexical scopes until it hits either a loop or a function definition; this becomes the 'recursion point'. The arguments to 'recur' are expressions for updating the local variables defined at the recursion point. When recur is hit the current stack frame is recycled; this is an optimized tail call, or 'non-stack-consuming', as Clojure puts it.
clojure trampoline: for mutual recursion in clojure, instead of calling another function directly, you return an anonymous function that calls that function. then you invoke the initial function with 'trampoline'. trampoline calls the initial function, and if it returns a non-function, terminates and returns that, but if it returns a function, trampoline then tail-recursively iterates, calling the function that was returned. In other words, it's implementing CPS (continuation-passing style), with the restriction that there is no way to 'really' return a function as the final return value without escaping it. See also http://pramode.net/clojure/2010/05/08/clojure-trampoline/
Here is the clojure.core implementation of `trampoline':
(defn trampoline ([f] (let [ret (f)] (if (fn? ret) (recur ret) ret))) ([f & args] (trampoline #(apply f args))))
e.g. in C: condition ? do-if-true : do-if-false
note: C switch and fall-thru; many languages don't have fall-thru because it's more verbose and has the potential for bugs if you forget a 'break'
also called "higher order functions", "hof", "reified functions"
example: python's 'map' function that takes a function and a list as arguments
example: python 2.5's 'sort' function that takes a comparator cmp function and a list (actually, it only needs a multiset) as arguments (bad example b/c python 3.0 has not cmp, instead a 'key' function: https://wiki.python.org/moin/HowTo/Sorting ; mb use On Lisp's example " (sort ’(1 4 2 5 6 7 3) #’<)" instead)
example: python's 'filter' function that takes a predicate and a list as arguments
see also On Lisp's section 2.2 and 2.3 for more examples
In C#, instead of first-class functions, instead appears (I don't know C# as of this writing) something called 'delegates'.
Delegates aren't exactly functions, rather they are a choice of an object and a method on that object. Presumably the method on that object could be reassigned in the interim between when a delegate is created and called, making this different from a function, although i'm not sure if that is actually possible in C#.
Delegates have two more special features.
First, a delegate can, instead of specifing both a target object and a method on that object, only specify a method name, leaving the target object to be specified at the time they are called.
Second, a delegate can be 'chained', meaning that when a delegate is invoked, it calls its target and then invokes another delegate.
note: it's tricky to combine lightweight partial function application (where partial function application looks the same as normal function applicaton, just with some of the arguments left out) with default arguments to functions, because at any time when the mandatory arguments are bound, you will be wondering if the function should execute, using defaults for all optional arguments, or if it should wait for the optional arguments to be given.
also clojure sequence protocols, IEnumerable
you can call 'continue' in a ruby block
prob: foldl, foldl', foldr, foldr', memory (dont hold onto your head?/space leak)
when you call a function/method, which code actually gets executed?
('one dimensional dispatch', according to http://www.jot.fm/issues/issue_2008_03/article4/ ):
1-1 relationship between function names and the code
same source code in all cases, but possibly different object code
can be implemented via templates
you can have different source code executed for the same function/method name depending on context
Choose the code to be executed based on both the method name, as also the type of 'receiver'. This terminology comes from considering a function call as a message to an object instance, the object instance being the 'receiver' of the message.
This way of doing things is called 'single dispatch polymorphism' (to contrast it with 'multiple dispatch', see below).
The method implementation executes within the context of its receiver, by which we mean that the private fields and methods of the instance are available during the execution of the method. In some languages, such as C++, the fields and methods of the receiver instance become in-scope for variable lookup, as if they were local variables.
OOP type systems often have subtypes and inheritance. This means that, if an object is of some type T, and T is a subtype of another type Tp, and Tp implements method name M, then objects of type T can also handle calls to method name M even without writing a separate implementation of method name M for type T. We say that type T inherits Tp's implementation of method M.
Now consider if type Tp is itself a subtype of another Tpp. Since subtype-ness is transitive, this means that T is also a subtype of Tpp. Perhaps Tpp also has its own implementation of method M. In this case, we have to have a procedure to determine which implementation of method M is used by T. The rule 'if T is a subtype of T2, and T has no implementation of M and T2 does, then T uses T2's implementation of M' is ambiguous, since either Tp or Tpp could fill the role of T2 in that rule.
If you have single inheritance, then there's an obvious solution. You recursively climb up the inheritance chain looking for an implementation of method M and stop at the first one you find. So, first you look at T, and it doesn't have an implementation of M, so you keep going. Then you look at Tp, and it does have an implementation of M, so you stop. The principal is that you want to use the 'most specific' implementation of M (in that a subtype is 'more specific' than its parent type).
If you have multiple inheritance, though, then this simple procedure does not suffice to eliminate ambiguity.
Note that, if one ignores access visibility restrictions on private fields and methods, than rather than thinking of the method as executing with the context of its receiver, you can model the 'receiver' as an actual argument passed to a function. Python makes this somewhat explicit; when you define a method inside a class, when that method is called, a value containing the object instance is prepended to the arguments which are passed by the caller. Traditionally in Python, this first argument is called 'self'. For example:
class A: def __init__(self, some_field_of_A): self.some_field_of_A = some_field_of_A def b(self, x): print repr(self) print repr(x) print repr(self.some_field_of_A)
a = A(1) a.b(2) print; print A.b(a,2)
Results in:
<__main__.A instance at 0x7f688028e5f0> 2 1
<__main__.A instance at 0x7f688028e5f0> 2 1
As you can see, the result of calling the 'b' method on instance 'a' was equivalent to calling the function A.b with the argument 'self' bound to the instance a, and the argument 'x' bound to 2. Also, even within the methods of the object instance a, the fields of a must be referenced through the 'self' variable.
todo the diamond problem
Now we consider all three of the method name, the type of the receiver, and the type of the 'sender' of the message in the selection of which code to actually execute.
See 'Three-dimensional dispatch' is http://www.jot.fm/issues/issue_2008_03/article4/ , and R. B. Smith and D. Ungar. A simple and unifying approach to subjective objects. TAPOS special issue on Subjectivity in Object-Oriented Systems, 2(3):161-178, 1996.
Also called 'multiple dispatch'.
Above, in section "OOP-style receiver type based dispatch", we saw that one can think of receiver-based dispatch equivalently as if the method definition is executed inside the context of its instance; equivalently (ignoring access restrictions), one can think of it as if a receiver is actually passed as an argument to a function. Generalizing the latter concept, we ask, if we can dispatch the method based on the type of the receiver argument, why not dispatch based on other arguments as well?
As with multiple inheritance, in this setting it is possible to have multiple implementations that match, so we need a way to resolve ambiguity. Often people try to come up with appropriate generalizations of 'most specific' and then to choose the 'most specific' method implementation when there is more than one to choose from. For example, a method implementation with more dependencies on the types of the arguments would be chosen over an otherwise identical method implementation which doesn't care about the types of some arguments.
Muschevici, Radu; Potanin, Alex; Tempero, Ewan; Noble, James (2008). "Multiple dispatch in practice". Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications. OOPSLA '08 (Nashville, TN, USA: ACM): 563–582. doi:10.1145/1449764.1449808. surveyed some programs in languages with multimethods and found that approximately 20% of polymorphic methods were multimethods (i.e. "13%-32% of generic functions utilize the dynamic type of a single argument, while 2.7%-6.5% of them utilize the dynamic type of multiple arguments", to quote Wikipedia).
An example of where you might want multimethods is when you are defining an operator such as "addition", which takes two arguments each of which may be various types such as integer or float.
See http://nice.sourceforge.net/visitor.html for a discussion of how multimethods can be used in some places where you might have used the Visitor pattern.
See also https://en.wikipedia.org/wiki/Multiple_dispatch .
In the above, we dispatched based on the method name and possibly also on the types of receivers, senders, and/or method arguments.
Guards enable dispatching to depend also on the values of method arguments.
As with multiple inheritance, in this setting it is possible to have multiple implementations that match, so we need a way to resolve ambiguity. Often people try to come up with appropriate generalizations of 'most specific' and then to choose the 'most specific' method implementation when there is more than one to choose from. For example, a method implementation with a matching guard would be chosen over an otherwise identical method implementation but with no guard.
Now we consider four things when determining dispatch: the method name, the type of the receiver, the type of the sender of the message, and also the 'context', which is a dynamically-determined value.
The difference between "context-oriented programming" and guards is that in context-oriented programming (see http://www.jot.fm/issues/issue_2008_03/article4/ ), the "context" is specified as a sequence of 'layers'. Each 'layer' may contain one or more method implementations.
Note that elsewhere in this book we use the word 'context' in an informal sense to mean various different things; don't assume that we are talking about 'context-oriented programming' when you see the word 'context'.
If, instead of grouping functions together as methods on objects, we just have unattached polymorphic functions, one thing we miss from receiver-oriented dispatch is the grouping together of various methods into an object. This was key to the idea of OOP encapsulation, that is, the idea that internal representations can be encapsulated by encapsulating data representations within objects with various methods by which their data can be accessed. As long as the rest of the program only accessed the data through these methods, you could change the representation of the data without breaking the rest of the program as long as you changed the methods at the same time. So every object's methods form a little API for accessing the data in that object.
If you just have unattached functions, even if those functions can be ad-hoc polymorphic depending upon the types of their arguments, you would still like a way to take a group of functions and put them together into a grouping, analogous to your object API (set of OOP methods for a class). You want to be able to say, e.g., "If something is a number, it should support addition, subtraction, multiplication, and division." Such a grouping is called a 'type class'. The signature of methods within a type class is polymorphic depending on the type. An implementation of a type class for a particular type is called a 'type class instance'.
Multimethods correspond to multi-parameter type classes. For example, an addition function which is ad-hoc polymorphic in both of its arguments could be contained within an 'arithmetic number' type class of addition, subtraction, multiplication, and division with two type arguments. There might be an instance of such a type class for the tuple of types (int, int), and another instance for (int, float) and another one for (float, int) and another one for (float, float).
