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))

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

9 Responses to “Just Showing Off”

  1. Steve said

    Can this also be done without a macro?

  2. programmingpraxis said

    @Steve: You could write a memoizing fib function without using a macro, by writing the memoization yourself inside the function, but you could not write define-memoized without using a macro.

  3. Thanks.


    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"
    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)
    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.

  4. Tamayo said

    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()
        return 0;

    reduces to the equivalent program

    import std.stdio;

    int main()
        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.

  5. Tamayo said

    (Argh! I called the function above “fib” instead of “fac”! Please forgive me!)

  6. 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.

  7. Paul said

    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()
    pprint.pprint([v for k, v in hashmap.items() if len(v) > 1])
  8. Rutger said

    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.

    string = "Here is 1 example 2 demonstrate list comprehensions 4 you in 3 examples."
    numbers = [int(s) for s in string if s.isdigit()]
    even = sorted([n for n in numbers if not n % 2 ])
    exponentiation = [(n, [n**i for i in range(5)]) for n in even]
    for number, powers in exponentiation:
    	print(number, ':', powers)

    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.

  9. programmingpraxis said

    @Rutger: I like list comprehensions, too. That’s why I provide them in the Standard Prelude. Likewise pattern matching.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: