Introduction to CSE

LOFT (Lab of Software)

Jooyong Yi

What is Computer Science?

Alan Turing

  • 1912 June 23rd – 1954 June 7th
  • Founder of Computer Science
  • Turing Award: Nobel Prize of Computing

Turing Machine (1936)

Church-Turing Thesis

  • "Computable" = "Turing-computable"

  • Any algorithm can be implemented on a Turing machine.

The Imitation Game

Turing-Welchman Bombe Machine

vs

Theory of Computation (CSE332)

  • More details on the Turing machine
  • What can be computed?
  • And what cannot be computed?

Theory of Computation (CSE332)

  • Do you want to be the Eisntein of Computer Science?

Theory of Computation (CSE332)

  • Do you want to be the Eisntein of Computer Science?
  • Are you interested in quantum computing?

Principles of Programming Languages (CSE271)

Various Syntaxes of Function Calls

Semantics of Function Calls

Semantics of Function Calls (Call by value)

Semantics of Function Calls

Semantics of Function Calls

Semantics of Function Calls (Call by name)

Designing a Programming Language

Example: Old Expressions

This does not work

Why not working?

Why not working?

Example: Past Expressions

Example: Old and Past Expressions

Example: Old and Past Expressions

Introduction to Compilers (CSE411)

                 |----------| 
Source Program → | Compiler | → Target Program
                 |----------|
  • Source program: written in a human-readable language
  • Target program: written in a machine-interpretable language

Introduction to Compilers (CSE411)

  • Frontend
         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   IR      | → IR
Program  |       |            |        |   tree    | Analyzer |        | Generator |
         |-------|            |--------|           |----------|        |-----------|
  • Backend
     |-------------|         |-------------|          |-------------|
IR → |    Code     | → IR' → |    Code     | → IR'' → |    Code     | → Target
     | Optimizer 1 |         | Optimizer 2 |          |  Generator  |   Program
     |-------------|         |-------------|          |-------------|

Compiler: Lexer (Lexical Analyzer)

  • Given a source program, the lexer extracts the sequence of tokens.

Compiler: Parser (Syntax Analyzer)

  • Given a sequence of tokens, the parser extracts the parse tree.

Semantic Analyzer

  • Given a parse tree, the semantic analyzer detects semantic errors such as type errors.
  • The semantic analyzer can also modify the parse tree. In the example, the inttofloat operator is added to convert an integer 60 to the floating-point number.

Compiler: IR Generator

Compiler: Code Optimization via Code Analysis

Compiler: Code Generation

Compilers and Programming Systems of the Future

                       |----------| 
Buggy Source Program → | Compiler | → Fixed Target Program
                       |----------|

Program Repair

                  |-----------|                |-----------|
(Program, Spec) → |   Fault   | → Suspicious → |   Patch   | → Plausible
                  | Localizer |   Locations    | Generator |    Patches
                  |-----------|                |-----------|

Analysis-Based Program Repair

                  |-----------|                |-----------|                 |-----------|
(Program, Spec) → |   Fault   | → Suspicious → |  Program  | →    Patch    → |   Patch   | → Plausible
                  | Localizer |   Locations    | Analysis  |   Constraint    | Generator |    Patches
                  |-----------|                |-----------|                 |-----------|

Analysis-Based Program Repair

                  |-----------|                |-----------|                 |-----------|
(Program, Spec) → |   Fault   | → Suspicious → |  Program  | →    Patch    → |   Patch   | → Plausible
                  | Localizer |   Locations    | Analysis  |   Constraint    | Generator |    Patches
                  |-----------|                |-----------|                 |-----------|
  • Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis (ICSE'16)
  • DirectFix: Looking for Simple Program Repairs (ICSE'15)

High-Speed Automated Fixes

  • Goal: Fixing bugs fast
  • Funded by Meta and NRF

High-Speed Automated Fixes

  • Automated Program Repair from Fuzzing Perspective (ISSTA'23)

Finding Out Correct Patches

                  |-----------|                |-----------|                |-----------|
(Program, Spec) → |   Fault   | → Suspicious → |   Patch   | → Plausible →  |   Patch   | → Correct
                  | Localizer |   Locations    | Generator |    Patches     |   Oracle  |    Patch
                  |-----------|                |-----------|                |-----------|
  • Poracle: Testing Patches Under Preservation Conditions to Combat the Overfitting Problem of Program Repair (TOSEM'23)

What Kind of Bugs Can be Fixed?

  • General-purpose program repair
  • Special-purpose program repair
    • Memory leak repair

Memory Leak Repair

  • LeakPair: Proactive Repairing of Memory Leaks in Single Page Web Applications
    • 🏆 ACM Distinguished Paper award at ASE'23

Software Engineering

  • Analyzing user requirements
  • Designing the software
  • Programming
  • Testing
  • Debugging and Bug Fixing

Software Engineering

  • How to develop and maintain high-quality software with minimal effort?

Software Engineers of the Future

Software Engineers of the Future

  • Build software that automatically writes software

Software Engineers of the Future

  • Build software that automatically writes software
  • We should keep control over such software

Hierarchy of Computer Science Fields

⋮
Software Engineering
Programming Languages
Compilers
Operating Systems
Computer Architecture
⋮

Why CSE?

Why CSE?

  • High demand and high salary

Why CSE?

  • High demand and high salary
  • Wide spectrum of fields
    • Programming languages, compilers, operating systems, computer architecture, networks, artificial intelligence, ...

Why CSE?

  • World Travel
    • Software Engineering:
      • ICSE, FSE, ASE, ISSTA
    • Programming Languages:
      • PLDI, POPL, OOPSLA

Lecture Slides

https://www.jooyongyi.com/lectures/UNI111/introToCSE.html