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.
Pages: 1 2
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.