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.
Right, I brought it up as an instance of a class of problems that has this property of being easy to specify but difficult to implement correctly. It will know how to implement a binary search because a great deal of articles have been written about the correct way of implementing a binary search and the pitfalls of this one particular problem is very well documented.
It's almost unique in that the problem has a corpus of literature about how difficult they are to implement correctly, which pitfalls are common, and how to solve them. ChatGPT being able to regurgitate this solution is not a good demonstration of it's ability to solve general programming problems.
That's my general point: it's easier to say what you want than to implement it in a low-level (relative to English) language. Hence why English is a good programming language.
And LLMs aren't just good at binary search, they're good at lots of things.
Imagine you are in a room with a programmer who is unquestionably better and more expert than you are.
Now let's say you need to write a program. Would you be better off trying to write it yourself, or describing what you want to the better programmer, and letting them write it?
Obviously the latter!
Given a sufficiently advanced compatriot, English is the preferred programming language.
Now, are LLMs good enough? Probably not yet, but getting there rapidly!
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:
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:
So maybe now you can see how English might be a superior way to program.