6 ms·

My favourite feature of Pharo (which I believe it inherited from Squeak) from my very limited experience with Smalltalk environments is the ability to search fo

My favourite feature of Pharo (which I believe it inherited from Squeak) from my very limited experience with Smalltalk environments is the ability to search for methods via example. In the Finder window, you can type an example of an input and the result that you want, for instance `2. -2`, and the system will search for a method to do that operation for you. In this case you'd see the "negated" method which given `2` spits out `-2`. https://www.youtube.com/watch?v=awAB4zHrlHI https://www.youtube.com/watch?v=awAB4zHrlHI

wk_end 6y ago
This seems like total magic. How on earth is that implemented?
- ssivark 6y ago
  Venturing a guess: Make up a unit test that runs on all relevant functions of the class (I.e. type) that the object “2” belongs to, and pick functions that pass the test.
  - spindle 6y ago
    Yes.
  - iso8859-1 6y ago
    How could that possibly be safe in a non-pure programming language? There could be a function that deletes the n first files found in the working directory.
    - noblethrasher 6y ago
      I remembering wondering about the same thing a few years ago, and came across this: https://stackoverflow.com/questions/30177559/how-does-find-by-example-work-in-the-pharo-finder/30178067#30178067 https://stackoverflow.com/questions/30177559/how-does-find-b...
- oh_sigh 6y ago
  for each function in known_functions: if function.apply(input) == output: return function
  - xkriva11 6y ago
    MethodFinder in Pharo is a litte bit smarter and does not use the list of known functions (unlike Squeak).
    - RodgerTheGreat 6y ago
      So how does it identify functions which are pure, and thus safe to pump random sample inputs through?
      - xkriva11 6y ago
        There is no magic; it does not know it for sure. But unlike the original MethodFinder, now the classes themselves decide about the approved selectors. In Squeak, the tool itself had a long whitelist of approved selectors. Moreover, the blacklists were updated.
      - KMag 6y ago
        I'm not sure how they do it, but I would be tempted to have some static analysis at save time. The static analysis can't be perfect in a Turing complete language embedded in an environment that admits impurity, but it can be proven conservative so that no impure methods are falsely marked as pure at save time. I've done something similar for commit-time code analysis to generate an error if a proven non-negative seed is passed to a Numerical Recipes in C-style random number generator (non-negative seeds silently ignored). Alternatively, if the interface to the OS itself is small enough, they could run their tests in a sandboxed environment where all methods to access the file system, network, clock, etc. are replaced with stubs that throw exceptions.
- disposedtrolley 6y ago
  It turns out the docs [1] try to explain how it works: > The method finder will take the input objects (receiver and arguments) and perform their permutation to be able to find more results. Then, it will lookup in the receiver's hierarchy the approved and forbidden methods to run on the hierarchy and run them on the permutation of objects. which sounds like an exhaustive search. I dug a little further and found this [2] which points to the actual implementation in the `MethodFinder` class. I don't know enough Smalltalk to decipher it :( [1] https://github.com/pharo-open-documentation/pharo-wiki/issues/142 https://github.com/pharo-open-documentation/pharo-wiki/issue... [2] https://csharp.developreference.com/article/18692966/How+does+find-by-example+work+in+the+Pharo+Finder%3F https://csharp.developreference.com/article/18692966/How+doe...
  - tom_mellior 6y ago
    > the actual implementation in the `MethodFinder` class. I don't know enough Smalltalk to decipher it :( For reference, here is the relevant class: https://github.com/pharo-project/pharo/blob/9ad3324bf8aff11ef0a3af00c1393c6bfd12e201/src/Tool-Finder/MethodFinder.class.st https://github.com/pharo-project/pharo/blob/9ad3324bf8aff11e... A core snippet is: foundPermutationSends := (receiver class allSelectorsToTestInMethodFinderWithArity: inputCollection size - 1) collect: [ :method | MethodFinderSend receiver: receiver deepCopy selector: method withArguments: args deepCopy ]. This means, roughly: - ask the receiver class (in the example above, the class of 2, which is something like SmallInteger) for "all the selectors (= method names) to test" with the given number of arguments. - for each of these methods, build a MethodFinderSend object, which is at this point is just a container holding a copy of the receiver object, the method to call on it, and a copy of the arguments to test with Then, given this collection of MethodFinderSend objects: ^ (self possibleSolutionsForInput: inputCollection) select: [ :send | send resultIn: expectedResult ]. This means: - execute the "resultIn:" method on each of the MethodFinderSend and return a collection of those where this returns true The implementation of this "resultIn:" method is in https://github.com/pharo-project/pharo/blob/c896913a00fa6e2bd37e07291b87df3776f42e8e/src/Tool-Finder/MethodFinderSend.class.st https://github.com/pharo-project/pharo/blob/c896913a00fa6e2b...: [ [ ^ expectedResult = (receiver perform: selector withArguments: arguments) ] onErrorDo: [ :anError | ^ false ] ] on: Deprecation do: [ :depr | ^ false ] This is, roughly: - try to perform the call - return false if there is an exception - otherwise, return true or false depending on whether the result equals the expected result So yes, it's an exhaustive search over the methods that the receiver's class promises are OK to test. If you write a method that tries to format the hard drive, and your class exports this method in its "selectors to test", then searching for a method on this class will attempt to format your hard drive.
- chriswarbo 6y ago
  VPRI has some nice writeups about extending the Squeak method finder in various ways: Improving on the Method Finder: http://www.vpri.org/pdf/m2009012_fnd_sine.pdf http://www.vpri.org/pdf/m2009012_fnd_sine.pdf Method finder for R: http://www.vpri.org/pdf/rn2013002_locatr.pdf http://www.vpri.org/pdf/rn2013002_locatr.pdf Connections to memoization: http://www.vpri.org/pdf/rn2017002_memoization.pdf http://www.vpri.org/pdf/rn2017002_memoization.pdf Larger-scale applications: http://www.vpri.org/pdf/tr2014003_callbymeaning.pdf http://www.vpri.org/pdf/tr2014003_callbymeaning.pdf

wk_end 6y ago

This seems like total magic. How on earth is that implemented?

ssivark 6y ago
Venturing a guess: Make up a unit test that runs on all relevant functions of the class (I.e. type) that the object “2” belongs to, and pick functions that pass the test.
- spindle 6y ago
  Yes.
- iso8859-1 6y ago
  How could that possibly be safe in a non-pure programming language? There could be a function that deletes the n first files found in the working directory.
  - noblethrasher 6y ago
    I remembering wondering about the same thing a few years ago, and came across this: https://stackoverflow.com/questions/30177559/how-does-find-by-example-work-in-the-pharo-finder/30178067#30178067 https://stackoverflow.com/questions/30177559/how-does-find-b...
oh_sigh 6y ago
for each function in known_functions: if function.apply(input) == output: return function
- xkriva11 6y ago
  MethodFinder in Pharo is a litte bit smarter and does not use the list of known functions (unlike Squeak).
  - RodgerTheGreat 6y ago
    So how does it identify functions which are pure, and thus safe to pump random sample inputs through?
    - xkriva11 6y ago
      There is no magic; it does not know it for sure. But unlike the original MethodFinder, now the classes themselves decide about the approved selectors. In Squeak, the tool itself had a long whitelist of approved selectors. Moreover, the blacklists were updated.
    - KMag 6y ago
      I'm not sure how they do it, but I would be tempted to have some static analysis at save time. The static analysis can't be perfect in a Turing complete language embedded in an environment that admits impurity, but it can be proven conservative so that no impure methods are falsely marked as pure at save time. I've done something similar for commit-time code analysis to generate an error if a proven non-negative seed is passed to a Numerical Recipes in C-style random number generator (non-negative seeds silently ignored). Alternatively, if the interface to the OS itself is small enough, they could run their tests in a sandboxed environment where all methods to access the file system, network, clock, etc. are replaced with stubs that throw exceptions.
disposedtrolley 6y ago
It turns out the docs [1] try to explain how it works: > The method finder will take the input objects (receiver and arguments) and perform their permutation to be able to find more results. Then, it will lookup in the receiver's hierarchy the approved and forbidden methods to run on the hierarchy and run them on the permutation of objects. which sounds like an exhaustive search. I dug a little further and found this [2] which points to the actual implementation in the `MethodFinder` class. I don't know enough Smalltalk to decipher it :( [1] https://github.com/pharo-open-documentation/pharo-wiki/issues/142 https://github.com/pharo-open-documentation/pharo-wiki/issue... [2] https://csharp.developreference.com/article/18692966/How+does+find-by-example+work+in+the+Pharo+Finder%3F https://csharp.developreference.com/article/18692966/How+doe...
- tom_mellior 6y ago
  > the actual implementation in the `MethodFinder` class. I don't know enough Smalltalk to decipher it :( For reference, here is the relevant class: https://github.com/pharo-project/pharo/blob/9ad3324bf8aff11ef0a3af00c1393c6bfd12e201/src/Tool-Finder/MethodFinder.class.st https://github.com/pharo-project/pharo/blob/9ad3324bf8aff11e... A core snippet is: foundPermutationSends := (receiver class allSelectorsToTestInMethodFinderWithArity: inputCollection size - 1) collect: [ :method | MethodFinderSend receiver: receiver deepCopy selector: method withArguments: args deepCopy ]. This means, roughly: - ask the receiver class (in the example above, the class of 2, which is something like SmallInteger) for "all the selectors (= method names) to test" with the given number of arguments. - for each of these methods, build a MethodFinderSend object, which is at this point is just a container holding a copy of the receiver object, the method to call on it, and a copy of the arguments to test with Then, given this collection of MethodFinderSend objects: ^ (self possibleSolutionsForInput: inputCollection) select: [ :send | send resultIn: expectedResult ]. This means: - execute the "resultIn:" method on each of the MethodFinderSend and return a collection of those where this returns true The implementation of this "resultIn:" method is in https://github.com/pharo-project/pharo/blob/c896913a00fa6e2bd37e07291b87df3776f42e8e/src/Tool-Finder/MethodFinderSend.class.st https://github.com/pharo-project/pharo/blob/c896913a00fa6e2b...: [ [ ^ expectedResult = (receiver perform: selector withArguments: arguments) ] onErrorDo: [ :anError | ^ false ] ] on: Deprecation do: [ :depr | ^ false ] This is, roughly: - try to perform the call - return false if there is an exception - otherwise, return true or false depending on whether the result equals the expected result So yes, it's an exhaustive search over the methods that the receiver's class promises are OK to test. If you write a method that tries to format the hard drive, and your class exports this method in its "selectors to test", then searching for a method on this class will attempt to format your hard drive.
chriswarbo 6y ago
VPRI has some nice writeups about extending the Squeak method finder in various ways: Improving on the Method Finder: http://www.vpri.org/pdf/m2009012_fnd_sine.pdf http://www.vpri.org/pdf/m2009012_fnd_sine.pdf Method finder for R: http://www.vpri.org/pdf/rn2013002_locatr.pdf http://www.vpri.org/pdf/rn2013002_locatr.pdf Connections to memoization: http://www.vpri.org/pdf/rn2017002_memoization.pdf http://www.vpri.org/pdf/rn2017002_memoization.pdf Larger-scale applications: http://www.vpri.org/pdf/tr2014003_callbymeaning.pdf http://www.vpri.org/pdf/tr2014003_callbymeaning.pdf