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
© Emberlynn McKinney