A Note on three Programming Paradigms

Nikolay Shilov,
A.P. Ershov Institute of Informatics Systems, Russian Academy of Sciences

 

Abstract

Full text pdf 350 KB

This paper is about a puzzle to be solved in three programming paradigms: logic, functional and imperative. It can be considered as a case study of algorithm inversion, since we start with logic algorithm, that answers the question "Is balancing M times sufficient for detecting a single fake in a set of coins?", and finishes with imperative algorithm, that effectively computes the minimal number of balancing that is sufficient for detection the fake. Functional paradigm is used for developing an intermediate functional algorithm that also computes the minimal number of balancing, but inefficiently, while the efficient imperative algorithm is a "lazy memoization" of the functional one.