Just Showing Off
May 19, 2017
As I have mentioned on several previous occasions, I frequently receive email from students asking for homework help, which I routinely ignore. Less frequently, I receive email from someone who tells me that Scheme is a horrible programming language, they don’t understand it, it is unreadable, there are too many parentheses, blah, blah, blah, and wouldn’t it be better if I wrote my blog in C#. (I don’t know what’s wrong with C# people, but I get more of them than any other language zealots.) Usually I ignore them, too, but the other day I engaged one of those correspondents who singled out macros as a particular wart on the face of Scheme. So I wrote to him and gave him this macro, which I used to calculate fibonacci numbers; the whole story is on the next page:
(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc `(,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons `(,arg ...) val) cache))
val)))))))))
When I showed him how to speed up the calculation of fibonacci numbers by memoizing sub-computations, he grudgingly agreed there might be something there, but it wouldn’t translate to C# (I didn’t disagree with that comment).
Your task is to write a program that shows off some special feature of your favorite programming language; tell the story how it makes your language better than any others, and give a real-life example. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Can this also be done without a macro?
@Steve: You could write a memoizing
fibfunction without using a macro, by writing the memoization yourself inside the function, but you could not writedefine-memoizedwithout using a macro.Thanks.
MUMPS
When I first started programming, dealing with files could be a bit complicated. Then I started programming in MUMPS, and it became a non-issue, because in MUMPS everything is stored in a sparse, multi-dimensional array.
S ^PATIENTS(12,1)="SMITH, HARRY^M^12/22/1957^123-45-6789" ; Store Demographics (12 is the internal id) S ^PATIENTS(12,2)="123 45th Street^New York^New York^01234" ; Store Address S ^PINDEX("SMITH, HARRY",12)="" ; Name index S INDEX=$O(^PINDEX("SMITH, HARRY","")) Q:'INDEX ; Quit if no index for "SMITH, HARRY" S TXT=^PATIENTS(INDEX,1) W !,"NAME: ",$P(TXT,"^",1) S SEX=$P(TXT,"^",2) W !,"SEX: ",$S(SEX="M":"Male",SEX="F":"Female",1:"Unknown") W !,"DOB: ",$P(TXT,"^",3) W !,"SSN: ",$P(TXT,"^",4) ; S TXT=^PATIENTS(INDEX,2) W !,"ADDR: ",$P(TXT,"^",1) W !,"CITY: ",$P(TXT,"^",2) W !,"ST: ",$P(TXT,"^",3) W !,"ZIP: ",$P(TXT,"^",4)While I liked the way they handled storage, another feature was the ability to handle multiple tasks and multiple users on small systems. I heard of a fellow who had a side business he ran on a PC-AT (6 or 8 MHz 8086, < 3 MB RAM). It was for accounting and supported multiple simultaneous users. The only other language I have heard that had such a capability is Forth: I have actually heard of 1 Forth system which handled 50 tasks with a Z80 8-bit CPU.
Ah, hi.
The D programming language is, more or less, a simplified and regularized dialect of C++, and it may have had (through Andrei Alexandrescu, a D enthusiast and C++ committee member) significant influence on more modern versions of C++. In particular, the modern C++ “constexpr” keyword and compile-time execution of functions seem directly influenced by D.
To Schemers, metacircularity and hygienic macros are old hat. To those of us brought up in the C tradition, they are new and exciting. D provides the first by including a D interpreter in the D compiler, so that deterministic D code whose input is provably immutable can be executed and its result may be used as data in the compilation of the rest of the program. Just as a Scheme macro is only a Scheme function whose input is a list representing the abstract syntax tree of a program, so indeed are D functions executable by the compiler during the compilation. The following small program, when compiled with all optimizations disabled …
import std.stdio;private uint fib(in uint n) pure nothrow @nogc
{
if (n == 0) {
return 1;
}
return n * fib(n - 1);
}
private immutable uint f5 = fib(5); // 120, to be precise
int main()
{
stdout.writeln(f5);
return 0;
}
reduces to the equivalent program
import std.stdio;
int main()
{
stdout.writeln(120);
return 0;
}
Hygienic macros are not as easy to give small examples for, but a beautiful large example is found in D’s own standard library: in particular, the std.regex module, wherein typical messy regular expressions are compiled to D code and inlined thereafter using the facility above.
Yes, again, Scheme has done this for decades. It’s new and exciting for us plebeians though.
(Argh! I called the function above “fib” instead of “fac”! Please forgive me!)
In Python 3.2 they added the @lru_cache decorator (least recently used cache) which does function memoization (which until today I always read as memoRization) and allows the user to set a max size for the cache for long running processes. The docs use the Fibonacci sequence as their example. These ease of writing your own decorators is often an example I use as a non standard reason Python is great.
What I like about Python is the large number of libraries. An example (after Raymond Hettinger): a script that walks down a directory tree and lists all duplicate files (with the same content). I think Python is great, but there are, of course, many other great languages.
import os, hashlib, pprint, codecs, collections hashmap = collections.defaultdict(list) for path, dirs, files in os.walk('.'): for filename in files: fullname = os.path.join(path, filename) with open(fullname, errors='ignore') as f: d = codecs.encode(f.read(), 'utf-8', errors='ignore') h = hashlib.md5(d).hexdigest() hashmap[h].append(fullname) pprint.pprint([v for k, v in hashmap.items() if len(v) > 1])Personally I just love the concept of list comprehension. It facilitates a concise way of filtering and executing operations on the list members. Quite some programming languages support it. I mostly use it in Python now, had some fun with it in XQuery a few years back as well.
Specific to Python: if you change every defined list with [] to () in above example, everything becomes generators and gets computed lazily, i.e. the powers of 2 are computed first before the next number is even determined from the input string.
@Rutger: I like list comprehensions, too. That’s why I provide them in the Standard Prelude. Likewise pattern matching.
Using the Wolfram Language (also know as “Mathematica”), one can easily memoize functions. It’s even easier than the method shown above!
Let’s use the Fibonacci function as an example. A naive implementation,
fib, would look like:fib[0] := 1;
fib[1] := 1;
fib[n_] := fib[n - 1] + fib[n - 2];
Calculating the 30th Fibonacci number takes about 3 seconds on my machine. To memoize the function, we simply replace
fib[n_] := ...withfib[n_] := fib[n] = .... This gives usfib[0] := 1;
fib[1] := 1;
fib[n_] := fib[n] = fib[n - 1] + fib[n - 2];
Now computing the 30th Fibonacci number takes about 0.1 seconds on my machine (30x speedup). I like this idiom because of how easy it is to incorporate memoization into your code.