50 years ago — April 28, 1961

This is an excerpt from the forth coming LISP 1.5 Programmer's Manual.

Provision is made in LISP 1.5 for allocating blocks of storage for data. The data may consist of list structure or data words. Arrays may have up to three indicies.

To declare an array, us the function array. Its argument is a list of arrays to be declared. Each one must be for list structure or non-list structure.

Suppose ALPHA is to be a 10 x 10 array of list structure and BETA a 5 x 5 x 5 array of non-list structure. The array function is

ARRAY ((
     (ALPHA (10,10) LIST)
     (BETA (5,5,5) NONLIST)    ))

To find the value of B_3,4,2: (BETA 3,4,2) or (BETA I J K) with a pair list.

To set ALPHA_3,4 to "YES": (ALPHA (QUOTE SET) (QUOTE YES) 3 4)

Array uses marginal indexing for maximum speed. The total number of words used by an array whose size is D₁ x D₂ x D₃ is 4 + D₁ + D₁D₂ + D₁D₂D₃. If the array is 2 dimensional, D₁ = 1. If the array is 1 dimensional, D₁ and D₂ = 1.

To save space, specify the dimensions in increasing order.

ALPHA (3,4,5) takes less words than ALPHA (5,3,4).

Compatability of LISP 1 and LISP 1.5.

1. EVALQUOTE has two arguments while APPLY has three. To change a LISP 1 program for LISP 1.5 simply eliminate the p-list if it is null. If the p-list is needed, then the function apply is available in LISP 1.5,
2. Arithmetic in LISP 1.5 is new, improved, and generally incompatible with LISP 1.
3. LISP 1.5 has many extra features. There [sic, these] are being written up for the new LISP 1 Programmer's Manual. Until it comes, check in Room 26-265.

— Michael Levin

Artificial Intelligence Project

RLE and MIT Computation Center Memo 24

Arithmetic in Lisp 1.5

Fun with scammers

No Scheme or Lisp content today. I was amusing myself for a while with this email exchange. The strings of digits are courtesy www.random.org. I even found a site that creates fake Western Union receipts.

---

Hello,

I'm writing this with tears in my eyes,my family and I came down here to Edinburgh Scotland for a short vacation unfortunately we were mugged at the park of the hotel where we stayed,all cash,credit card and cell were all stolen from us but luckily for us we still have our passports with us.

We've been to the embassy and the Police here but they're not helping issues at all and our flight leaves in few hrs from now but we're having problems settling the hotel bills and the hotel manager won't let us leave until we settle the bills the amount needed now is just $2,700..I am so confused right now and thank God i wasn't injured because I complied immediately. Waiting to hear from you. Robert

I sent this message to Bob's other account:


I just got this message that supposedly came from you. It is plausible enough that your friends might fall for it! You should email your friends and assure them that you are OK and to NOT SEND MONEY
~jrm

Thanks for checking on me, well the message is from me and not a hoax. I'm presently stuck in UK and really in a bad situation.....I have been talking to the lazy embassy but it's taking them time process me help, and it's hard to get hold of a phone, that was why I had to send out email for help....I need a financial help with getting back home...all i need is $2,700.,but anything you could assist with now be helpful ..let me if can you have the money wire to me through western union

Thanks. 

Robert

I'm glad to hear your email is ok, it would be terrible to be mugged and hacked. Where do you need it sent?
~jrm

 Glad you replied back. I am full of panic now and the police only asked me to write a statement about the incident and directed me to the embassy,i have spoken to the Consulate here but they are not responding to the matter effectively,I really need your help to get myself out of this place. Well all i need now is just $2,700 but any amount you can afford will be appreciated, you can have it wired to my name via Western Union i'll have to show my passport as ID to pick it up here and i promise to pay you back as soon as i get back home.

 Here's the info you need at western union location below

 Name: Robert G 

Address: 48 Princes Street, Edinburgh, Scotland 

 Kindly email me the transfer details as soon as you have it done.Please let me know if you are heading out to western union now. 

Thanks

Robert

 What's going on?

 I was only able to wire $300 (I hit the limit on my ATM). I can send a lot more tomorrow, but will you have time to get it?
 ~jrm

 Please Let me have the western union confirmation number # M.T.C.N, so i can be able to pick up the Money. I'm freaked out at the moment please keep me posted. 

 Robert. 

 Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

 Thanks for your effort,Let me have the western union confirmation number # M.T.C.N. Awaiting for your reply. 

 Robert 

I left him dangling on this one.

 What's going on? 

 Robert . 

 My apologies, Robert, (I know you are in trouble, but I do have to sleep at times!) The MTCN is 2665592734

HOWEVER!!! IMPORTANT!!!!

I didn't want to broadcast that over email because it could be read by someone unscrupulous. So I added in your wife's birth date. Just subtract that out to get the real tracking number. I hope you can figure that out. Please let me know. If you want, I have an additional $500 I can send right away.

 What's going on,I just got back from Western Union and i was told there was no record for the transaction,kindly check the receipt and get back to me with the correct confirmation # 

 Awaiting to reply. 

 Robert .

 Trip number 1.  I'm shocked it didn't work.

What?! Did you remember to subtract your wife's birth date from the number I gave you?

 Omg!! I am full of panic now,Let me have the scanned receipt For Payment giving to you by the Western Union Agent.

Uh oh.  I'm busted... maybe I can vamp a bit....

How can I do that? You know I don't have a scanner. I've got an idea! What's the phone number of the hotel that is giving you problems? I'll call the manager myself and put it on my credit card.

No reply.  I was going to give up but it occurred to me to check for an on-line receipt generator (they have everything on line, don't they?) They do.  I sent him a nice receipt.

 Good news! I found a scanner. Please let me know if everything is ok.

 Thanks for your help.. i just got the money but there seems to be a problem with the conversion rate, i noticed the money came out here in $300but all i need is $2,700 as i requested, don't know that the conversion is that low, please i will need your further assistance so i will be needing $2,400. Please let me know when you will be heading out to western union. Waiting to read from you.

Hmm, he read the receipt, but didn't make a Western Union run.  I'll string him along a bit.

 I'll have to go by the bank (again) to get an additional check. I should be able to do that after work, in a few hours. Hang in there! I'm very worried.

 Ok,I will be waiting ,Do e-mail the full Western Union Transfer Details once you have it done. 

 Keep me posted.

 Robert.

I'm trying to get the guy to go `off script'.

 URGENT
 Robert, I need to know if you want the money in US Dollars, GB Pounds, or Euros, and what the exchange rate is. Can you get back to me as soon as you can? I'm really sorry about this, hope you are surviving.

No reply.  Better dangle some cash.

 I sent some more money. Did you get it? Is everything all right?

 OK...Can i have the full transfer details (MTCN) so i will be able to pick up the money. Waiting to read from you. 

 Thanks Robert.

 The MTCN is 4677254413 Please let me know when you get it!

 Are you there? 

 Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

 Let me have the confirmation details # M.T.C.N. Awaiting for your urgent reply. Robert 

 Please do get back to me with the Western Union Control Number M.T.C.N# Please Keep me posted. 

 Robert 

 This guy just has a one-track mind.  It seems impossible to get him `off script'.

Robert,
What is going on? Are you all right?

 I just checked with Western Union and they say you haven't picked up either of the two wires that I sent! Are you having difficulty getting them?

 The Western Union Control Number M.T.C.N # are these:
 2665591653 --- amount $300
 3207519347 --- amount $500

 Please let me know if you have any problems retrieving the money.
 ~jrm

 Are you kidding me or what,cause i was told at western union office the money you sent to me was not there. Please Let me know what's going on am freaked out here. 

 Robert.

 Yes!  Trip number 2.  He's probably figured out I'm playing him, though.  Let's goad him into one more trip.  A bit of an insane rant to allay his suspicions and we'll sweeten the pot just a bit more...

I don't know what to say, Robert. Perhaps they have a different system in Edinburgh and the numbers don't match? Are you sure that you are telling them the right numbers and didn't get them mixed up?

 I checked with Western Union, and the agent told me that the money was there and that you didn't pick it up. Why don't you go to the Royal Bank of Scotland? They are at 4 Princess Street, right around the corner from where you are staying. They should be able to straighten this out right away.

 I'm surprised you suggest that I am kidding. Why would I be so cruel? I have $800 on the line, and I'm doing this for your benefit. I'm not the victim here, you are. Do you think I would wire you this kind of money and then make a joke about it? Do you think I get a kick out of imagining you walk back and forth to Western Union for no reason? This is a bad situation and you seem to think I'm making it worse! I'm not sure you are taking this as seriously as I am. Are you sure you didn't get injured?

 I'm going to try this one more time, and I expect action on your part. I have wired an additional $200 dollars for a total of One Thousand ($1000) dollars. I really cannot afford any more, so I hope this is enough. The details are these: 

Sender: Joseph Marshall
 Receiver: Robert G, 48 Princess Street, Edinburgh Scotland
 Amount: $1000.00 (One Thousand) 
Money Transfer Control Number: 1822631749
 Transfer Fee: 50.00
 Number: 10341731365

 And I am enclosing a receipt. Please be sure to get these details correct. I am awaiting to hear that you have collected the cash.
 ~jrm

The receipt was fake and I included a “security question”: Who's your daddy? I was sure this would tip my hand, but....

 Robert, it has been 7 hours since I sent this. Did you get it?
 ~jrm

No i didn't,I will like to go back to western union and make this complain to them that all the confirmation number they give you was invalid ok..

YES!  Three trips!  Well, that's good enough for me.

Oops

I made a mistake that has lead to a lot of confusion. It is a common mistake, so I have a lot of company. To assuage the trauma to my ego, I'll point out that no one who argued with me (or, for that matter, agreed with me) identified it. Allow me to explain it and correct myself.

The Church-Turing thesis is often stated as follows:

Anything that can be computed by some means can also be computed by a Turing machine.

And this is usually coupled with Rosser's observation that λ-calculus and recursion theory are equivalent formulations.

The problem is that phrasing, while not exactly incorrect, is not exactly right, either. It is vagueness disguised as definition. Because it is a definition, it is “correct, by definition”, but it is vague enough to admit interpretations that are absurd. Thus, if one isn't careful, one can deduce several absurdities that are “correct, by defintion”.

So what is the correct statement? The Church-Turing thesis is a statement about “effective calculability”. This is an intuitive concept which tries to generalize on the idea of an algorithm, or “plug and chug” math formulas, or “mechanistic” procedures like Newton's method. Many mathematicians have attempted to formalize the notion of “effective calculability”, among them Church and Turing, but also Gödel, Kleene, Rosser, and Post (and many others after them, but these are the big names). A correct statement of the Church-Turing thesis is more like this:

The formal terms “computable by a Turing machine” and “λ-definable” fully capture the intuitive notion of “effectively calculable”.

Naturally, the bulk of what a modern digital computer does is in fact an “effective calculation” and thus a Turing machine or λ-calculus is a very good model for what a computer can calculate. However, there are things a modern digital computer can do other than calculate. These activities fall outside the scope of the Church-Turing thesis and there is no reason to believe that they would be subject to the limitations of computability.

Does anybody really know what time it is?

— Robert Lamm of Chicago

A good example of a non-computable, yet common task that a digital computer performs is to determine the current time. There is no algorithm or calculation that you can perform that will yield the current time. You simply must check a clock. Even if you somehow know the elapsed time since some event, you nonetheless have to check a clock in order to determine the beginning of the ‘epoch’ (baseline time).

A whole set of non-computable quantities can be made available via reflection. Recall the definition of a Turing machine. The next state of a Turing machine is a function of the current state and the symbol on the tape under the head. It is not a function of, for example, the the size of the state transition table. This is not to say that these quantities are unknowable, but that they cannot be calculated without introspection (certainly bounds can calculated, and certainly any machine can be instrumented or even simulated, but consider this: any Turing machine can be augmented by any number of inaccessible states. There is no way to calculate the size of the state table without knowing the number of these states.) Also note, that there is nothing magic about these quantities, you can calculate to your heart's content with them after you obtain them. It is obtaining them in the first place that involves something other than computation.

My mistake is this: I didn't specifically and explicitly state when I was referring to the informal “effective calculation” and the superset that is the informal “computing” that one can do on a modern digital computer. In other words, I applied the Church-Turing thesis to too broad a class.

Given that, I'll rephrase my Exercise 1 and see how people react:

Exercise 1: Write a program for a class of universal Turing machines that, when run, calculates whether the machine it is on is imposing additional space complexity.

When I phrase it that way, it sort of sounds obvious that there are going to be problems.

On the other hand, this is a far more satisfying rewording than

Write a portable program that is non-portable.

Too much exercise

I've spent the past few days thinking about how to answer the exercises in my previous post. I think I finally came up with a good analogy. (Bear with me.)

These days, it is not uncommon to run programs on virtual hardware. Programs like VMWare or Virtual Box provide nearly undetectable emulation of an x86 PC. In fact, modern x86 CPUs actually emulate the x86 instruction set through hardware accelerated interpretation or jit compiling. Although it can be tricky to emulate the entire body of computer hardware and peripherals that might go into a PC, it is straightforward to emulate the bare bones PC hardware with close to perfect fidelity, even down to the CPUID.

So could one write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can reliably and predictably detect whether it is being “run directly” or “just being emulated”? The entire raison d'être of virtualization rests on the fact that, given enough effort, you can fool all of the programs all of the time. (Bugs notwithstanding.)

So let's reconsider Exercise 1:  Write a program that returns 1 if run on any tail-recursive implementation of a language, but returns 0 if run on any non tail-recursive implementation of that same language.

Restate this as: Write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can NOT ONLY reliably and predictably detect whether it is being “run directly” or “just being emulated”, BUT FURTHERMORE can reliably and predictably detect whether the underlying execution mechanism is “recursive” or “iterative”?

I assert that this question is barely worth thinking about (unless you work at VMWare) and that the answer could hardly be anything but “No.”

Exercise 1a (extra credit):  Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.

If a program cannot detect whether or not it is being emulated, perhaps it can “half” detect. If it could reliably crash the emulator, then you could at least demonstrate that some sort of emulation is being done even if you couldn't perform a conditional branch in this situation. Suppose the program were being emulated. Suppose further that the emulator is recursive (for whatever reason). One could, in theory, crash the emulator via a stack overflow or out-of-memory error (maybe that emulator is recursive, but it uses heap-allocated stack frames). Alas, this isn't what we asked for. We are looking for a program that can reliably crash an iterative emulator. We're out of luck.

Exercise 1b, essay (extra extra credit): Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs (woah, my apologies, programs don't have semantics, languages do. Pretend I wrote “languages”). In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

The implication is this: the semantics of a programming language are logically independent of the implementation of the language. (If they were not, virtual machines would be impossible.)

Exercise 2: What trivial change can Louis make to his code for smaller that will disable tail recursion?

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (let ((answer
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
        answer)))

There is no need for a flag to enable or disable tail recursion. Tail recursion only “works” when the caller does nothing to the return value but immediately return it itself. A LET expression is syntactic sugar:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      ((lambda (answer) answer)
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate)))))

You can now see that the value of the conditional expression is not immediately returned, but rather passed as an argument to a (rather trivial) lambda expression. (Yes, a smart compiler could notice that the lambda expression is simply the identity function in this case. If that is a problem, simply make sure that the function you use to disable the tail recursion is late-bound so that the compiler cannot prove that it can be elided.)

Exercise 3: What trivial change can Louis make to his code for smaller that will enable tail recursion on all but the initial call to smaller?

(define (smallest list predicate)
  ;; Returns the smallest element of list.

  (define (smallest list predicate)
    (if (null? list)
        #f
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
  (let ((answer (smallest list predicate)))
    answer))

Again, we don't need special flags to have fine control over tail recursion.

Exercise 4: Implement disable-tail-recursion as a macro.

;;; For example:
(define-syntax disable-tail-recursion
  (syntax-rules ()
    ((disable-tail-recursion form)
     (let ((answer form)) answer))))

You could be more sophisticated and invoke a late-bound function, but this is, frankly, overkill. You hardly need macros, special forms, flags, decorations, etc. to control tail recursion. This is especially true if all you want is a pretty stack trace for debugging. Tail recursion is as easy to turn on and off as a printf.

Exercises

Apparently I was not as clear with my questions as I thought I was. I've edited the questions to make them more precise. The additional text is in this alternative color.

---

Exercise 1: Write a program that returns 1 if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.  The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer whether on not any supplied language implementation supports tail recursion by examining its own behavior.

Exercise 1a (extra credit): Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.  The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer that any supplied implementation does not support tail recursion (this is a weaker condition because we do not require that the program correctly infer support of tail recursion, but only lack of support).

Exercise 1b, essay (extra extra credit): Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs. In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

Louis Reasoner wrote this program to sort numbers:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (if (predicate (car list) (cadr list))
          (smallest (cons (car list) (cddr list)) predicate)
          (smallest (cdr list) predicate))))

(define (louis-sort list predicate)
  (do ((remainder list (cdr remainder))
       (answer '() (append answer (cons (smallest remainder predicate) '()))))
      ((null? remainder) answer)))

(define test-list
  (do ((i 0 (+ i 1))
       (answer '() (cons i answer)))
      ((>= i 100) answer)))

He complains “I am unable to debug this because smallest tail calls itself and leaves no trace on the stack. Look!

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are 9 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    do-loop                 (cons (smallest remainder predicate) (quote ()))
3    do-loop                 (append answer (cons (smallest remainder predi ...
4    do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
5    %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
6    %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
7    do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
8    loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

“I was expecting to see pending stack frames as the program recursively called smaller, but since they are all tail-recursive calls, I don't have a way of knowing how deep it went. I wish I could selectively enable or disable tail recursion for this one call...”

Exercise 2: What trivial change can Louis make to his code for smaller that will disable tail recursion?

Louis again has a problem. “I have a stack trace, but, but, well, just LOOK at it!

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are more than 50 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    smallest                (let ((answer (if (predicate (car list) (cadr  ...
3    smallest                (let ((answer (if (predicate (car list) (cadr  ...
4    smallest                (let ((answer (if (predicate (car list) (cadr  ...
5    smallest                (let ((answer (if (predicate (car list) (cadr  ...
6    smallest                (let ((answer (if (predicate (car list) (cadr  ...
7    smallest                (let ((answer (if (predicate (car list) (cadr  ...
8    smallest                (let ((answer (if (predicate (car list) (cadr  ...
9    smallest                (let ((answer (if (predicate (car list) (cadr  ...
10   smallest                (let ((answer (if (predicate (car list) (cadr  ...
11   smallest                (let ((answer (if (predicate (car list) (cadr  ...
12   smallest                (let ((answer (if (predicate (car list) (cadr  ...
13   smallest                (let ((answer (if (predicate (car list) (cadr  ...
14   smallest                (let ((answer (if (predicate (car list) (cadr  ...
15   smallest                (let ((answer (if (predicate (car list) (cadr  ...
16   smallest                (let ((answer (if (predicate (car list) (cadr  ...
17   smallest                (let ((answer (if (predicate (car list) (cadr  ...
18   smallest                (let ((answer (if (predicate (car list) (cadr  ...
19   smallest                (let ((answer (if (predicate (car list) (cadr  ...
20   smallest                (let ((answer (if (predicate (car list) (cadr  ...
21   smallest                (let ((answer (if (predicate (car list) (cadr  ...
22   smallest                (let ((answer (if (predicate (car list) (cadr  ...
23   smallest                (let ((answer (if (predicate (car list) (cadr  ...
24   smallest                (let ((answer (if (predicate (car list) (cadr  ...
25   smallest                (let ((answer (if (predicate (car list) (cadr  ...
26   smallest                (let ((answer (if (predicate (car list) (cadr  ...
27   smallest                (let ((answer (if (predicate (car list) (cadr  ...
28   smallest                (let ((answer (if (predicate (car list) (cadr  ...
29   smallest                (let ((answer (if (predicate (car list) (cadr  ...
30   smallest                (let ((answer (if (predicate (car list) (cadr  ...
31   smallest                (let ((answer (if (predicate (car list) (cadr  ...
32   smallest                (let ((answer (if (predicate (car list) (cadr  ...
33   smallest                (let ((answer (if (predicate (car list) (cadr  ...
34   smallest                (let ((answer (if (predicate (car list) (cadr  ...
35   smallest                (let ((answer (if (predicate (car list) (cadr  ...
36   smallest                (let ((answer (if (predicate (car list) (cadr  ...
37   smallest                (let ((answer (if (predicate (car list) (cadr  ...
38   smallest                (let ((answer (if (predicate (car list) (cadr  ...
39   smallest                (let ((answer (if (predicate (car list) (cadr  ...
40   smallest                (let ((answer (if (predicate (car list) (cadr  ...
41   smallest                (let ((answer (if (predicate (car list) (cadr  ...
42   smallest                (let ((answer (if (predicate (car list) (cadr  ...
43   smallest                (let ((answer (if (predicate (car list) (cadr  ...
44   smallest                (let ((answer (if (predicate (car list) (cadr  ...
45   smallest                (let ((answer (if (predicate (car list) (cadr  ...
46   smallest                (let ((answer (if (predicate (car list) (cadr  ...
47   smallest                (let ((answer (if (predicate (car list) (cadr  ...
48   smallest                (let ((answer (if (predicate (car list) (cadr  ...
49   smallest                (let ((answer (if (predicate (car list) (cadr  ...
50   smallest                (let ((answer (if (predicate (car list) (cadr  ...
51   smallest                (let ((answer (if (predicate (car list) (cadr  ...
52   smallest                (let ((answer (if (predicate (car list) (cadr  ...
53   smallest                (let ((answer (if (predicate (car list) (cadr  ...
54   smallest                (let ((answer (if (predicate (car list) (cadr  ...
55   smallest                (let ((answer (if (predicate (car list) (cadr  ...
56   smallest                (let ((answer (if (predicate (car list) (cadr  ...
57   smallest                (let ((answer (if (predicate (car list) (cadr  ...
58   smallest                (let ((answer (if (predicate (car list) (cadr  ...
59   smallest                (let ((answer (if (predicate (car list) (cadr  ...
60   smallest                (let ((answer (if (predicate (car list) (cadr  ...
61   smallest                (let ((answer (if (predicate (car list) (cadr  ...
62   smallest                (let ((answer (if (predicate (car list) (cadr  ...
63   smallest                (let ((answer (if (predicate (car list) (cadr  ...
64   smallest                (let ((answer (if (predicate (car list) (cadr  ...
65   smallest                (let ((answer (if (predicate (car list) (cadr  ...
66   smallest                (let ((answer (if (predicate (car list) (cadr  ...
67   smallest                (let ((answer (if (predicate (car list) (cadr  ...
68   smallest                (let ((answer (if (predicate (car list) (cadr  ...
69   smallest                (let ((answer (if (predicate (car list) (cadr  ...
70   smallest                (let ((answer (if (predicate (car list) (cadr  ...
71   smallest                (let ((answer (if (predicate (car list) (cadr  ...
72   smallest                (let ((answer (if (predicate (car list) (cadr  ...
73   smallest                (let ((answer (if (predicate (car list) (cadr  ...
74   smallest                (let ((answer (if (predicate (car list) (cadr  ...
75   smallest                (let ((answer (if (predicate (car list) (cadr  ...
76   smallest                (let ((answer (if (predicate (car list) (cadr  ...
77   smallest                (let ((answer (if (predicate (car list) (cadr  ...
78   smallest                (let ((answer (if (predicate (car list) (cadr  ...
79   smallest                (let ((answer (if (predicate (car list) (cadr  ...
80   smallest                (let ((answer (if (predicate (car list) (cadr  ...
81   smallest                (let ((answer (if (predicate (car list) (cadr  ...
82   smallest                (let ((answer (if (predicate (car list) (cadr  ...
83   smallest                (let ((answer (if (predicate (car list) (cadr  ...
84   smallest                (let ((answer (if (predicate (car list) (cadr  ...
85   smallest                (let ((answer (if (predicate (car list) (cadr  ...
86   smallest                (let ((answer (if (predicate (car list) (cadr  ...
87   smallest                (let ((answer (if (predicate (car list) (cadr  ...
88   smallest                (let ((answer (if (predicate (car list) (cadr  ...
89   smallest                (let ((answer (if (predicate (car list) (cadr  ...
90   smallest                (let ((answer (if (predicate (car list) (cadr  ...
91   smallest                (let ((answer (if (predicate (car list) (cadr  ...
92   smallest                (let ((answer (if (predicate (car list) (cadr  ...
93   smallest                (let ((answer (if (predicate (car list) (cadr  ...
94   smallest                (let ((answer (if (predicate (car list) (cadr  ...
95   smallest                (let ((answer (if (predicate (car list) (cadr  ...
96   smallest                (let ((answer (if (predicate (car list) (cadr  ...
97   smallest                (let ((answer (if (predicate (car list) (cadr  ...
98   smallest                (let ((answer (if (predicate (car list) (cadr  ...
99   smallest                (let ((answer (if (predicate (car list) (cadr  ...
100  smallest                (let ((answer (if (predicate (car list) (cadr  ...
101  smallest                (let ((answer (if (predicate (car list) (cadr  ...
102  do-loop                 (cons (smallest remainder predicate) (quote ()))
103  do-loop                 (append answer (cons (smallest remainder predi ...
104  do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
105  %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
106  %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
107  do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
108  loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

“I wish I could start eliminating the tail call from the second call onwards...

Exercise 3: What trivial change can Louis make to his code for smaller that will enable tail recursion on all but the initial call to smaller? (Hint, the bold text in the following backtrace shows how this differs from the first backtrace.)

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are 10 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    smallest                (let ((answer (smallest list predicate))) answer)
3    do-loop                 (cons (smallest remainder predicate) (quote ()))
4    do-loop                 (append answer (cons (smallest remainder predi ...
5    do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
6    %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
7    %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
8    do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
9    loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

Louis seems to have gotten his wish and is currently making progress despite the existence of tail recursion. Cy D. Fect, however, is unimpressed. He complains “Sure, it is trivial to disable tail recursion whenever you desire, but I don't like guessing whether the compiler is going to emit a tail call, and I'd simply rather not learn. I'd prefer some sort of declaration or decoration so I can explicitly tell the compiler to not emit a tail call. Something like this:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (if (predicate (car list) (cadr list))
          ;; This branch should leave a backtrace - CDF
          (disable-tail-recursion 
             (smallest (cons (car list) (cddr list)) predicate))
          (smallest (cdr list) predicate))))

Exercise 4: Implement disable-tail-recursion as a macro.

Homework: Fix Louis's code.