You want one behavior from the perspective of the user's desire, but there will be a very large set of possible programs that will achieve that desire. So you just need to be precise w/r/t desire, not with the nitty gritty behavior. Traditional programming languages are great to expressing the nitty gritty behavior, and bad at capturing the desire.
Don't think of LLMs as akin to COBOL or Basic (or HyperTalk, is another great example) -- those are essentially rigid languages with a sprinkling of "Englishness" to try to make them seem less foreign to novice users. And yes, that just gets in the way once you become proficient in rigid languages.
But that's a completely different beast than programming in actual English.
So for example, the reason binary search (a simple algorithm) is hard to implement is because of the mismatch between easy to understand human desire and the pickiness of the rigid language designed for the machine.
Now, it is very easy to implement a correct binary search.
Tell ChatGPT:
> Write a binary search method in C#
It responds:
public static int Search(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1; // Return -1 if the target is not found
}
We can also ask it:
> Prove it is correct
It responds:
> To prove the correctness of the binary search algorithm, we can use a technique called loop invariant. A loop invariant is a condition that remains true for every iteration of the loop. In this case, the loop invariant is that the target element, if it exists in the array, will always be within the range defined by the left and right pointers.
> Loop Invariant: At the start of every iteration, if the target element exists in the array, it must be within the subarray arr[left, right].
> Initialization: At the beginning, left = 0 and right = arr.Length - 1, which covers the entire array. So, if the target element is present in the array, it must be within the initial range.
> Maintenance: During each iteration, the algorithm examines the middle element (mid = left + (right - left) / 2). There are three cases:
> If arr[mid] == target, the target element is found and returned.
> If arr[mid] < target, the target must be in the right half of the subarray. Therefore, we update left = mid + 1. Since the array is sorted, we are sure the target is in the range arr[mid + 1, right] if it exists in the array.
> If arr[mid] > target, the target must be in the left half of the subarray. Therefore, we update right = mid - 1. Since the array is sorted, we are sure the target is in the range arr[left, mid - 1] if it exists in the array.
> In cases 2 and 3, we have updated either the left or right pointer, maintaining the loop invariant for the next iteration.
> Termination: The loop terminates when left > right. Due to the loop invariant, if the target element exists in the array, it must be in the range arr[left, right]. Since left > right, this range is now empty, which means the target element is not in the array, so the algorithm returns -1.
> In conclusion, the binary search algorithm is correct, as it either returns the index of the target element if it exists in the sorted array, or -1 if it doesn't.
(OK, I'd quibble with that proof a little bit -- it was a little hand-wavy on why the loop must terminate.)
How about the broken binary search you linked to?
Ask ChatGPT:
> Can you find the bug in this java binary search implementation? [Code]
It responds:
> The given binary search implementation appears to be correct, assuming that the input array a is sorted in ascending order. However, there is a potential issue with integer overflow when calculating the middle index mid. To avoid this, you can calculate mid using the following line:
int mid = low + ((high - low) / 2);
So maybe now you can see how English might be a superior way to program.