[Home]

Insertion Sort in INTERCAL

Oh dear god, INTERCAL. This language is insane. This actually took me three days. I managed to figure out how to do comparison, branching, and looping, though, and once I got those down, things got a lot easier. That’s not saying much, though. Anyway, below is the INTERCAL code (with the PLEASEs removed because, while they are a hilarious part of the spec, they aren’t terribly interesting as part of the code), and then below that is roughly directly translated Python code, to give a slightly better idea of what’s going on.

You can download everything (the code, the translated Python code, a Makefile, and a Python script to add PLEASEs) in a zip file (02.zip).

INTERCAL (insertion.i)

DO NOTE: vim: set ft=intercal :
DO NOTE: Array length less than 2 is not checked but is an error
DO NOTE: Variables:
DO NOTE: ,1: Array
DO NOTE: .1: Increment scratch
DO NOTE: .2: Operand scratch
DO NOTE: .3: Result scratch
DO NOTE: .4: Overflow scratch
DO NOTE: .5: Array length
DO NOTE: .6: Iteration variable
DO NOTE: .7: Current array element
DO NOTE: .8: Another iteration variable
DO NOTE: .9: Another array element
DO NOTE: First, we read the length of the array
DO WRITE IN .5
DO ,1 <- .5
DO NOTE: Now we need to read in the values of the array
DO .6 <- #1
(1) DO FORGET #1
DO READ OUT .6
DO WRITE IN ,1 SUB .6
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (2) NEXT
DO NOTE: Only get here if Length > Index we just read into
DO (1) NEXT
(2) DO (3) NEXT
DO NOTE: Only get here if Length <= Index we just read into
DO (4) NEXT
(3) DO RESUME .4
(4) DO FORGET #2
DO NOTE: Now we can start the insertion sort
DO .6 <- #2
(5) DO FORGET #1
DO .7 <- ,1 SUB .6
DO .8 <- .6
DO (120) NEXT
DO NOTE: Nested loop
(6) DO FORGET #1
DO .9 <- ,1 SUB .8
DO NOTE: Check if .9 > .7
DO (102) NEXT
DO (12) NEXT
DO NOTE: Only get here if .9 > .7: Do loop body
DO (7) NEXT
(12) DO (13) NEXT
DO NOTE: Only get here if .9 <= .7: Break
DO (8) NEXT
(13) DO RESUME .4
(7) DO FORGET #1
DO .1 <- .8
DO (1020) NEXT
DO ,1 SUB .1 <- ,1 SUB .8
DO (120) NEXT
DO NOTE: Check if .8 > 0
DO .1 <- .8
DO .2 <- #65535
DO (1009) NEXT
DO NOTE: Now .4 <- #2 if .8 > 0 else #1
DO (22) NEXT
DO NOTE: Only get here if .8 > 0
DO (6) NEXT
(22) DO (23) NEXT
DO NOTE: Only get here if .8 == 0
DO (8) NEXT
(23) DO RESUME .4
DO NOTE: End of nested loop
(8) DO FORGET #2
DO NOTE: Place current element
DO .1 <- .8
DO (1020) NEXT
DO ,1 SUB .1 <- .7
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (32) NEXT
DO NOTE: Only get here if Length > Index we just processed
DO (5) NEXT
(32) DO (33) NEXT
DO NOTE: Only get here if Length <= Index we just processed
DO (34) NEXT
(33) DO RESUME .4
(34) DO FORGET #2
DO NOTE: Now we can output the result array
DO .6 <- #1
(41) DO FORGET #1
DO READ OUT ,1 SUB .6
DO NOTE: Checking and Increment
DO (101) NEXT
DO (110) NEXT
DO NOTE: Branching
DO (42) NEXT
DO NOTE: Only get here if Length > Index we just wrote out of
DO (41) NEXT
(42) DO (43) NEXT
DO NOTE: Only get here if Length <= Index we just wrote out of
DO GIVE UP
(43) DO RESUME .4
DO NOTE: The remainder of the file is subroutines
DO NOTE: Subroutine: .4 <- #2 if .2 > .1 else #1 (Writes .1 through .4)
DO NOTE: Underflow subtraction and then detect overflow on addition
(100) DO (1010) NEXT
DO .1 <- .3
DO (1009) NEXT
DO RESUME #1
DO NOTE: Subroutine: .4 <- #2 if .5 > .6 else #1 (Writes .1 through .4)
(101) DO .1 <- .6
DO .2 <- .5
DO (100) NEXT
DO RESUME #1
DO NOTE: Subroutine: .4 <- #2 if .9 > .7 else #1 (Writes .1 through .4)
(102) DO .1 <- .7
DO .2 <- .9
DO (100) NEXT
DO RESUME #1
DO NOTE: Subroutine: Increment .6 (Writes .1)
(110) DO .1 <- .6
DO (1020) NEXT
DO .6 <- .1
DO RESUME #1
DO NOTE: Subroutine: Decrement .8 (Writes .1 through .3)
(120) DO .1 <- .8
DO .2 <- #1
DO (1010) NEXT
DO .8 <- .3
DO RESUME #1

Python (insertion.py)

#!/usr/bin/env python3
# Array length less than 2 is not checked but is an error
# First, we read the length of the array
length = int(input())               # WRITE IN .5
# INTERCAL arrays are 1-indexed: simulating that with None at index 0
arr = [None] + [None] * length      # ,1 <- .5
# Now we need to read in the values of the array
i = 1                               # .6 <- #1
while True:                         # label (1)
    print('\n{}'.format(i))         # READ OUT .6
    arr[i] = int(input())           # WRITE IN ,1 SUB .6
    # Checking and Increment
    gt = (length > i)               # (101) NEXT
    i += 1                          # (110) NEXT
    # Branching
    if gt:
        # Only get here if Length > Index we just read into
        continue                    # (1) NEXT
    else:
        # Only get here if Length <= Index we just read into
        break                       # (4) NEXT
# Now we can start the insertion sort
i = 2                               # .6 <- #2
while True:                         # label (5)
    x = arr[i]                      # .7 <- ,1 SUB .6
    j = i - 1                       # .8 <- .6; (120) NEXT
    # Nested loop
    while True:                     # label (6)
        y = arr[j]                  # .9 <- ,1 SUB .8
        # Check if y > x
        gt = (y > x)                # (102) NEXT
        if gt:
            # Only get here if y > x: Do loop body
            pass                    # (7) NEXT
        else:
            # Only get here if x <= y: Break
            break                   # (8) NEXT
        arr[j + 1] = arr[j]         # .1 <- .8; (1020) NEXT; ,1 SUB .1 <- ,1 SUB .8
        j -= 1                      # (120) NEXT
        # Check if j > 0
        gt = (j > 0)                # .1 <- .8; .2 <- #65535; (1009) NEXT
        # Now gt = True if j > 0 else False
        if gt:
            # Only get here if j > 0
            continue                # (6) NEXT
        else:
            # Only get here if j == 0
            break                   # (8) NEXT
    # End of nested loop
    # Place current element
    arr[j + 1] = x                  # .1 <- .8; (1020) NEXT; ,1 SUB .1 <- .7
    # Checking and Increment
    gt = (length > i)               # (101) NEXT
    i += 1                          # (110) NEXT
    # Branching
    if gt:
        # Only get here if Length > Index we just processed
        continue                    # (5) NEXT
    else:
        # Only get here if Length <= Index we just processed
        break                       # (34) NEXT
i = 1 # .6 <- #1
while True:                         # label (41)
    print('\n{}'.format(arr[i]))    # READ OUT ,1 SUB .6
    # Checking and Increment
    gt = (length > i)               # (101) NEXT
    i += 1                          # (110) NEXT
    # Branching
    if gt:
        # Only get here if Length > Index we just wrote out of
        continue                    # (41) NEXT
    else:
        # Only get here if Length <= Index we just wrote out of
        raise SystemExit(0)         # GIVE UP