Tag: Scheme

How to Design Worlds

Via PLT:

As some of you know, we have been working on a new way of writing interactive applications, such as games, using just pure functional programming. We call this the World style, and it is embodied in the world.ss Teachpack included in the DrScheme distribution.
In response to demand, we are creating extended materials on this style of programming:
http://world.cs.brown.edu/

Addendum: 26 October 2008
Some folks might find HTDW a little more interesting in that it is purely functional programming.

Teaching Programming Languages in a Post-Linnaean Age

Programming language “paradigms” are a moribund and tedious legacy of a bygone age. Modern language designers pay them no respect, so why do our courses slavishly adhere to them? This paper argues that we should abandon this method of teaching languages, offers an alternative, reconciles an important split in programming language education, and describes a textbook that explores these matters.

This is a nice paper explaining the author’s rationale for his approach.
(via PLT)

MPSCM: A Distributed Extension to MzScheme

MPSCM is an extension to the MzScheme dialect of Scheme that provides facil-ities for distributed programming with a message passing base and higher-level distributing constructs designed in a more functional style. This paper provides a description of the MPSCM environment and an analysis of the results in terms of performance, expressivity, and usability.

Sequencing in Scheme

When I was first learning about Functional Programming and Scheme, the idea that order-of-execution didn’t matter in purely functional programs, was “strange to me”, to put it nicely. When I first read about Scheme’s begin form, for example, I remember feeling satisfied that Scheme wasn’t totally insane as it had at least some way to force imperative execution (the fact that, at the time, I never considered how such a feature may be implemented using Scheme’s core constructs, I now consider to be both a ‘missed opportunity’ and ‘study flaw’, then again you could also call it ‘learning’). Nonetheless, much, much later, while reading LAMBDA: The Ultimate Imperative, I came upon page 5 on which the question of how we may model imperative constructs in languages based on lambda calculus (like Scheme, for example) was raised.
Continue reading “Sequencing in Scheme”

LAMBDA: The Ultimate GOTO

‘LAMBDA: The Ultimate GOTO’ (found here) is a paper that was written in 1977 by Guy Steele. It is fun to read, informative, and accessible to a wide-variety of programmers and interest levels. Here are some interesting bits about the paper (I will leave the detail to the paper, no sense in trying to re-state what Steele has already done so well):
(All bits are either copy-and-paste, or summaries directly from the referenced text, along with my comments)

  • Must programming language designers admit that they can’t possibly get it right for every programmer? Yes. Failure to do so results in programmers using the wrong structures to solve their problems.
  • There is a marked difference between programming language concepts and language constructs.
  • Tail-calls (tail-transfers) are really GOTOs.
  • In FORTRAN and APL (at the time the paper was written at least), a distinction is made between built-in and user-defined functions. For example, you can’t pass in a user-defined function as an argument to some built-in functions, whereas you can pass in a built-in function to a built-in function. This may be an interesting historical note for anyone wondering why Scheme lauds that it doesn’t introduce an artificial separation between built-in and user-defined functions.
  • Any notation should accentuate the unusual and make the unobtrusive the usual. To argue that today’s fashionable languages state this is as “Convention over configuration” is a very big stretch.
  • Tail-recursion (trail-transfer) is useful in many more situations than just iterative recursion. Calling tail-transfer tail-recursion was such a mistake. It has got nothing to do with recursion.
  • The difficulties in dealing with programming and programming languages stem from the fact that no distinction is made between the abstraction of program organization and the concrete embodiment of those notations as programming language constructs.
  • For every programming concept found to be useful, there ought to be more than one programming language construct to embody that concept. Philosophically, a marked difference from Python’s “my way or the highway” approach today.
  • The features of tail-recursion allow for a new mental approach for programming.
  • In trying to understand a program, it is necessary to determine not only what construct is being used, but what concept it is intended to express.
  • A language should be so designed that one is encouraged to use a construct if, and only if, it is appropriate; it must also provide enough constructs to cover all reasonable programming constructs.
  • Regarding GOTO, they tried to eliminate unwanted concepts and programming styles by banning a construct.
  • This paper is full of gems.

LAMBDA: The Ultimate Imperative

‘LAMBDA: The Ultimate Imperative’ (found here) is a paper that was written in 1976 by Guy Steele and Gerry Sussman. It is fun to read, informative, and accessible to a wide-variety of programmers and interest levels. Here are some interesting bits about the paper (I will leave the detail to the paper, no sense in trying to re-state what Sussman and Steele have already done so well):
(All bits are either copy-and-paste, or summaries directly from the referenced text, along with my comments)

  • Most programming language constructs can be modeled in terms of lambda, letrec, and if. This might seem pretty radical to folks used to so called “big languages” today. It also might offer some insight into the “minimalistic” nature of Scheme.
  • “Applicative order” of evaluation implies “Call-by-value”. In other words, arguments to functions are evaluated before passing control to the function receiving that value.
  • The paper demonstrates how you can conceptually go from a purely functional world, to one of an imperative nature by leverage call-by-value and macros. This is very, very cool.
  • ‘Tail-recursion’ is perhaps the biggest misnomer of the century. It should be called ‘tail-transfer’. After reading this paper, along with ‘LAMBDA: The Ultimate GOTO’, this becomes quite obvious.
  • Lazy evaluation is introduced, and discussed.
  • Be sure to read the conclusion. It contains numerous gems (both overt and covert) about the role of language, the programmer, and the programming language designer.
  • Keep in mind that this paper was written over 32 years ago. When you take into account the functionality that they describe, and the reasons for its importance; you must put as much effort into thinking about the computing landscape in 1976 as you put into wondering why these kinds of features aren’t in “fashionable languages” today (In my opinion, only Lisp is an acceptable Lisp, and additionally, what does that tell you about “fashionable languages”?).

The Lambda Papers

The Lambda Papers are a series of seminal works on programming language design and implementation written by Guy Steele and Gerry Sussman.
You may have heard about them because of the very popular Lambda the Ultimate website, or maybe you just heard about them because you are studying Scheme, or are a student of programming history. Whatever the case, they are very much worth reading (you’ll have to trust me on that).
You should start with ‘AIM-353 Lambda:The Ultimate Imperative’ and follow it with ‘AIM-443 Lambda: The Ultimate GOTO’. Both may be found here.

Addressing slow looping

In the comp.lang.lisp post [Slow Loop (alternatives in lisp?)] Francogrex asked how to implement pivot table functionality without it taking forever using inner loops. Folks posted clearly faster solutions along with good advice. By the way, taking forever means 12 hours for inputs of 1 million data points.
I wondered how you might lead someone down the path to understand how to approach solving a problem (this is pre-HTDP). Here is what I came up with, primarily for myself, mostly as a thought exercise.
Continue reading “Addressing slow looping”