Simulating binary addition - DrRacket Intermediate Student with Lambda

Question

As the title says, I'm a college student using DrRacket with Intermediate Student With Lambda language. My assignment is an algorithm that, given a string containing a binary number, displays as output the next number, operating only on the binary representation (thus, not converting to decimal, adding +1 and re-converting to binary). I've skipped the first three weeks of my course since I was abroad and now I'm trying to catch up and, as long I've understood, the professor's main goal now is to make us exercise on recursion (moreover, we are not allowed to use lists or cicles like the ones that are possible with do, only functions that are defined through lambda expressions).
I took several tries at the assignment and now my code looks like this:

; function called by the user

(define bin-succ
  (lambda (bin)    ; not-empty string of "0"s and "1"s
    (let ( (k (- (string-length bin) 1)) (post (make-string 0)) )
      (position bin k post)
      )
    )
  )

; actual recursive function of the code: it searches from the least significant
; bit to the most significant bit if there is any "0" in the string

(define position
  (lambda (bin k post)
    (cond ( (= k -1)
            (string-append "1" post) )
          ( (char=? (string-ref bin k) #\0)
            (string-append (substring bin 0 k) "1" post) )
          ( (char=? (string-ref bin k) #\1)
            ((position bin (- k 1) post)
            (string-append "0" post)) )
          )
    )
  )

At the moment, the algorithm works with numbers which last digit is 0, such as 0, 10, 11010, etc..., but when I declare as input a number ending in 1, the program highlights the last part of the code, in particular

((position bin (- k 1) post)
            (string-append "0" post))

and returns the error:

function call: expected a function after the open parenthesis, but received "11"

I've tried to use begin to make a list of expressions in a different function called by the third cond's case, that would re-call the function position, thus making the algorithm recursive again, but no luck since it says that begin isn't a defined function.
I may be overlooking something really easy (mostly due to the introductory classes I've skipped) or I may have taken this problem with an uncorrect mindset, but either way I'm stuck and I appreciate any helpful input.
Just a final question: also the use of else in the last cond case isn't accepted, can anyone explain me why? The fact that DrRacket uses multiple languages is puzzling me quite a lot since lots of documentation online isn't working with my current setup.

(position bin (- k 1) post) obviously returns "11" so it would be like calling ("11" (string-append "0" post)). What is the expected result from that? — Sylwester
Maybe you should change your title to "using string operator simulate binary addition" or simulate binary addition. — tjorchrt
@Sylwester Now I've understood my mistake, but at the moment of asking I was unintentionally trying to design this procedure as it was moreless a 'while' cycle (something like until you find a 0 in the number, just keep adding 0s to post and skip left). Reading your comment helped me understand a little better how I should re-arrange my mindset in order to learn this language, thank you. — Denis D'Ambrosi
@DenisD'Ambrosi Scheme doesn't have looping constructs as primitives. Eg. do is just syntax that becomes a letrec that is immediately called and where recursion is what makes it do more turns. If you were allowed to do (begin expr1 expr2) expr1 would only be for effect while only the result of expr2 would be the result. The student languages probably avoids side effects so a begin doesn't make sense. — Sylwester

Atharva Shukla Atharva Shukla · Accepted Answer · 2019-11-06T13:14:42

Maybe you've been looking at Racket documentation not ISL+ (Intermediate Student With Lambda) documentation so far? See https://docs.racket-lang.org/htdp-langs/intermediate-lam.html for the ISL+ documentation. Pressing f1 on a term from DrRacket takes you to documentation in the context of the language you're using.

((position bin (- k 1) post)
            (string-append "0" post))

This is function application. You're trying to apply (as an argument): (string-append "0" post) to a function (position bin (- k 1) post). However, position returns a String.

You can simply pass over the new post to the recursive call. And you can use else in the last clause too. This is the working code:

; String -> String
(define (bin-succ bin)
  (position bin (- (string-length bin) 1) ""))

; String Number String -> String
(define (position bin k post)
  (cond  [(= k -1)
          (string-append "1" post)]
         [(char=? (string-ref bin k) #\0)
          (string-append (substring bin 0 k) "1" post)]
         [else
          (position bin (- k 1) (string-append "0" post))]))

A cleaner solution would be to not have a counter:

(define (bin-succ bin)
  (cond [(string=? bin "1") "10"]
        [(string=? (last bin) "0") (string-append (all-but-last bin) "1")]
        [else (string-append (bin-succ (all-but-last bin)) "0")]))

(define (last str)
  (substring str (sub1 (string-length str)) (string-length str)))

(define (all-but-last str)
  (substring str 0 (sub1 (string-length str))))

Simulating binary addition - DrRacket Intermediate Student with Lambda

1 Answers