These amazing new gate: fprog

Showing posts with label fprog_ru. Show all posts

Thursday, 2 June 2011

Хвостовая "рекурсия" и взаимная хвостовая "рекурсия" на C

Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией.^[1] Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию, что реализовано во многих оптимизирующих компиляторах.

Википедия

К сожалению, в таком языке как C, по стандарту, данная возможность является не положенной, в связи с чем, рекурсия останется как есть, и скушает много памяти. Ниже приведён код, в котором описывается небольшой набор типов данных и функций для того, что бы реализовать некоторое подобие хвостовой рекурсии ручками.

typedef struct ReturnValue (* RecurFunction) (void *);

struct ReturnValue {
  RecurFunction function;
  void * value;
};

void * recur(RecurFunction function, void * input) {
  struct ReturnValue tmp;
  tmp.value = input;
  tmp.function = function;
  do {
    tmp = tmp.function(tmp.value);
  } while (tmp.function != NULL);
  return tmp.value;
}

Основная идея этого решения следующая: функция во время своего вычисления, формирует структуру данных типа ReturnValue, в которой определяется в поле value результат вычисления или задаётся функция, которая должна быть вычислена в следующую "итерацию" и её аргументы. Ограничения и неудобства решения видны сразу, рекурсивная функция должна быть типа RecurFunction, на вход получать void* (а значит и преобразовывать типы), и её результат должен быть представлен типом ReturnValue. Это делает код довольно страшным...
Посмотрим на классический пример, а именно на вычисление факториала:

// Тип входных данных.
struct RecurFactorial {
  int n, acc;
};
struct ReturnValue factorial(void * input) {
  struct RecurFactorial * args = input; // Приведение типа данных.
  struct ReturnValue result;
  result.value = input; // Входные и результируещие данный одни и теже.
  if (args->n == 1) {
    // Функция на следующий запуск не устанавливается для завершения вычислений.
    result.function = NULL;
  } else {
    // Формируем результаты итерации.
    args->acc *= args->n;
    args->n -= 1;
    // Устанвливаем функцию на следующий запуск.
    result.function = factorial;
  }
  return result;
}

Теперь рассмотрим пример поинтереснее, с двумя взаимно-рекурсивными функциями. Реализуется алгоритм с примерно тем же поведением (и с ошибкой на списке нулевой длинны), что у кода на Haskell в этом посте про алгоритм определения конца списка.

struct RecurLoopInList {
  struct List * fastMarker, * slowMarker;
};

struct ReturnValue slowMarker(void * input);
struct ReturnValue fastMarker(void * input);

bool loopInList(struct List *head) {
  struct RecurLoopInList args;
  args.fastMarker = head->next;
  args.slowMarker = head;
  bool * resultP = recur(fastMarker, (void*)&args);
  bool result = *resultP;
  free(resultP);
  return result;
}

struct ReturnValue slowMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  result.value = input;
  args->slowMarker = args->slowMarker->next;
  result.function = fastMarker;
  return result;
}

struct ReturnValue fastMarker(void * input) {
  struct RecurLoopInList * args = input;
  struct ReturnValue result;
  if (args->fastMarker->next == NULL ||
      args->fastMarker->next->next == NULL) {
    bool * ans = malloc(sizeof(bool));
    *ans = false;
    result.value = (void*)ans;
    result.function = NULL;
  } else if (args->fastMarker->next == args->slowMarker ||
             args->fastMarker->next->next == args->slowMarker) {
    bool * ans = malloc(sizeof(bool));
    *ans = true;
    result.value = (void*)ans;
    result.function = NULL;
  } else {
    args->fastMarker = args->fastMarker->next->next;
    result.value = (void*)input;
    result.function = slowMarker;
  }
  return result;
}

Целиком весь код можно увидеть тут: https://gist.github.com/1003337

PS. есть ли другой подход, что бы сделать взаимно-рекурсивные функции на C без стека и платформо-независимо?

Один хороший человек с ником Powerfox предложил решение через контексты.

Friday, 30 July 2010

5 + 1 главных особенностей, которые необходимо знать о конструкторах в Scala

Вольный перевод данного поста: Top 5 Things to Know About Constructors in Scala и плюс ещё одна особенность, на которую волей случая наткнулся.

Я играюсь со Scala в течение нескольких месяцев, и одной из вещей, с котороми пришлось бороться после перехода с Java были конструкторы. Они похожи на конструкторы в Java, но синтаксис имеет отличия.
Что бы помочь вам быстрее начать пользоваться Scala, приведу пять основных особенностей связанных с конструкторами. Начнём:

1. Как сделать конструктор с параметром?

public class Foo() {
  public Bar bar;
  public Foo(Bar bar) {

    this.bar = bar;