Ops_ui

Lab 0x7

Review 

Goal: Learn Higher Order Functions

Review: Newish:
- bigint/4096_t - headers
- extended GCD - high order functions
- headers
  • There are no required exercises of this lab.
  • It is supplementary material to the BigRSA homework.
    • Specifically, it provides helper functions for BigRSA

Podman 

Setup

  • For this lab, I used the following Containerfile
Containerfile
  • You will note it includes LibGMP.
    • Read more
    • Watch more
    • LibGMP shouldn’t be used in the final product but can be helpful in testing.
    • I will make no use of LibGMP but you may wish to do so while working on the lab.
      • I will refer to it frequently and it may be worth fiddling around with.
  • I worked in an ops_ui.c and ops_ui.h file, that I used in BigRSA
    • It can be helpful to directly add todays work to 4096_t - or not, up to you.

Header 

Lambda 

Higher Order Functions

  • Despite my best efforts, there is no graceful way to implement within C functions which return other functions.
    • I did not say no way! I said no graceful way.
    • Using C++ is not graceful!
  • There is, I think, an extraordinarily graceful to implement functions which accept as a parameter/argument some other function(s).
    • We simply specify that an argument has some function type.
  • We begin with a minimal example.

ctype.h

  • One common application for functions is to check if a character is a printing character:
    • A number, like 0 or i?
    • A letter, like O or i?
    • A control character, like \0 or \n
    • A digit, like 0 or 1
    • A space, like or \n
  • ctypes.h provides functions to test each of these.
/* For some reason this is int -> int *?
int isalnum( int ch );
  • Let’s make a table.
    • In the leftmost column, we will print each of the first 127 characters
    • Then we we will have a column for each of the ctypes
    • We will specify T or F for “True” or “False” membership in the ctype.
    • So we need a way to go from character-to-character with a bunch of int-to-int functions.
  • Here are some functions to use:
isalnum
isalpha
isdigit
islower
isprint
ispunct
isspace
isupper
  • We can use them as follows:
tedious.c
#include <stdio.h>
#include <ctype.h>

int main() {
    char buf[8] = "aA1. _\t";
    if (isalnum(buf[0])) {
        printf("T");
    } else {
        printf("F");
    }
    printf("\n");
    return 0;
}
  • It would be tedious to write a wrapper function for each of these.
    • We treat them as a lambda function, a function for which we neither know nor care the name, and know only the type.
  • Let’s examine more closely these lines:
    if (isalnum(buf[0])) {
        printf("T");
    } else {
        printf("F");
    }
  • We:
    • Take a function name
    • Take an array name
    • Take an array index
    • Apply the function name to index element of the array.
    • Print based on the result.
  • Let’s write a function.
    • It doesn’t return anything, it just prints.
    • It takes a function… somehow.
    • It takes a character pointer for an array.
    • It takes a numberical value for an array index.
    char_to_bool(function, array, index)
  • This is not well-formed C - let’s add types.
void char_to_bool(function, char *array, int index) # should be size_t, but.
  • isalnum also has a type - the type int -> int in Python, but in C?
void char_to_bool(int (function)(int), char *array, int index).
- We say `function` is a type that given some `int` returns some `int`
  • How do we use it?
    • The same way we would any other function for which we know a name or alias!
    void char_to_bool(int (function)(int), char *array, int index) {
  if (function(array[index])) {
      printf("T");
  } else {
      printf("F");
  }
  return;
}
  • Put it altogether
goated.c
#include <stdio.h>
#include <ctype.h>

void char_to_bool(int (function)(int), char *array, int index) {
    if (function(array[index])) {
        printf("T");
    } else {
        printf("F");
    }
    return;
}

int main() {
    char buf[8] = "aA1. _\t";
    char_to_bool(isalnum, buf, 0);
    printf("\n");
    return 0;
}

Longer arrays

  • Why not examine the char in multiple ways?
    • We
goated.c
#include <stdio.h>
#include <ctype.h>

void char_to_bool(int (function)(int), char *array, int index) {
    if (function(array[index])) {
        printf("T");
    } else {
        printf("F");
    }
    return;
}

void char_to_bools(char *array, int index) {
    int (*functions[8])(int) = {
        isalnum,
        isalpha,
        isdigit,
        islower,
        isprint,
        ispunct,
        isspace,
        isupper
    }, i;
    for (i = 0 ; i < 8 ; i++) {
        char_to_bool(functions[i], array, index);
    }
    return;
}

int main() {
    char buf[8] = "aA1. _\t";
    char_to_bools(buf, 0);
    printf("\n");
    return 0;
}
  • We can see the output:

{.email}} TTFTTFFF

Closing thoughts

  • An astute will have noticed that:
    • All of the “big” operations have the same function type.
    • All of the “_ui” operations have the same function type.
    • All of the “_ui” operations can utilize the underlying “big” operation.
      • This is not efficient for computing performance, but is efficient from code reuse.

Tester 

  • Unusually for this lab I have provided a tester for the ops_ui files.
  • Separately, I have provided biggmp.c
    • This file uses the GMP library to implement 4096_t.
    • It is a “drop in replacement”
      • Remove 4096_t.c from your gcc command.
      • Replace it with biggmp.c
      • Add -lgmp flag to gcc
    • Compiling with 4096_t and biggmp should be functionally identical.
      • They will differ in how they handle overload, but there are notes in biggmp on how to fix that at a small performance cost.

Autograder

  • The interface implemented by the autograder may be informative here.
    • It uses a Python script.
    • It uses a dedicated .c file with a main function.
    • It differents from the 4096_t grader:
      • It uses gcc ../4096_t/4096_t.c ops_ui.c tester.c
      • It can use gcc ../4096_t/biggmp.c ops_ui.c tester.c -lgmp
      • You can change this if you use a different directory structure.
      • There is a better way to write these gcc commands that we will cover after midterm.
    • It uses Python subprocess to examine the results.
  • I was unable to achieve a bugfree multiply absent this interface, but was able to progress rapidly once I developed it.

BigMax 

  • I wrote two other “big” helper functions.
  • Can be completed as part of this lab, part of BigRSA, or not at all.
  • They aren’t exactly big x unsigned operations, but could live in the same file.

BigMax

  • I needed a way to see if things were bigger than other things.
  • My subtraction only worked if the initial argument, the minuend, was larger than the final argument, the subtrahend.
  • Additionally, computing extended gcd’s generally involves finding a maximal and minimal value.
  • I just returned a 0 or a 1 depending on whether the initial argument was the max.

BigMid, mid_ui

  • In LaTeX I am accustomed to denoted “\(a\) is divisible by \(b\)” or “\(b\) divides \(a\)” as follows: \[ a \mid b \]
  • This uses the LaTeX \mid command.
  • It is the same idea as a % b == 0
  • I wanted to call this div but that was already used for division.
  • I mostly used this for prime generation.